Program Synthesis via Test-Time Transduction
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908604093693952 |
|---|---|
| author | Lee, Kang-il Koo, Jahyun Yoon, Seunghyun Kim, Minbeom Koh, Hyukhun Lee, Dongryeol Jung, Kyomin |
| author_facet | Lee, Kang-il Koo, Jahyun Yoon, Seunghyun Kim, Minbeom Koh, Hyukhun Lee, Dongryeol Jung, Kyomin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_17393 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Program Synthesis via Test-Time Transduction Lee, Kang-il Koo, Jahyun Yoon, Seunghyun Kim, Minbeom Koh, Hyukhun Lee, Dongryeol Jung, Kyomin Artificial Intelligence Computation and Language 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. |
| title | Program Synthesis via Test-Time Transduction |
| topic | Artificial Intelligence Computation and Language |
| url | https://arxiv.org/abs/2509.17393 |