{"ID":2867511,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.17393","arxiv_id":"2509.17393","title":"Program Synthesis via Test-Time Transduction","abstract":"We introduce transductive program synthesis, a new formulation of the program synthesis task that explicitly leverages test inputs during synthesis. While prior approaches to program synthesis--whether based on natural language descriptions or input-output examples--typically aim to generalize from training examples, they often struggle with robustness, especially in real-world settings where training examples are limited and test inputs involve various edge cases. To address this, we propose a novel framework that improves robustness by treating synthesis as an active learning over a finite hypothesis class defined by programs' outputs. We use an LLM to predict outputs for selected test inputs and eliminate inconsistent hypotheses, where the inputs are chosen via a greedy maximin algorithm to minimize the number of LLM queries required. We evaluate our approach on four benchmarks: Playgol, MBPP+, 1D-ARC, and programmatic world modeling on MiniGrid. We demonstrate that our method significantly improves program synthesis in both accuracy and efficiency. We release our code at https://github.com/klee972/SYNTRA.","short_abstract":"We introduce transductive program synthesis, a new formulation of the program synthesis task that explicitly leverages test inputs during synthesis. While prior approaches to program synthesis--whether based on natural language descriptions or input-output examples--typically aim to generalize from training examples, t...","url_abs":"https://arxiv.org/abs/2509.17393","url_pdf":"https://arxiv.org/pdf/2509.17393v3","authors":"[\"Kang-il Lee\",\"Jahyun Koo\",\"Seunghyun Yoon\",\"Minbeom Kim\",\"Hyukhun Koh\",\"Dongryeol Lee\",\"Kyomin Jung\"]","published":"2025-09-22T06:53:32Z","proceeding":"cs.AI","tasks":"[\"cs.AI\",\"cs.CL\"]","methods":"[\"Large Language Model\"]","has_code":false,"code_links":[{"ID":609473,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_id":2867511,"paper_url":"https://arxiv.org/abs/2509.17393","paper_title":"Program Synthesis via Test-Time Transduction","repo_url":"https://github.com/klee972/SYNTRA","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}