Program Synthesis via Test-Time Transduction
This addresses robustness issues in program synthesis for real-world applications where limited training data and edge cases are common, representing a novel method for a known bottleneck.
The paper tackles the problem of program synthesis robustness when training examples are limited and test inputs involve edge cases by introducing a transductive formulation that leverages test inputs during synthesis, demonstrating significant improvements in accuracy and efficiency on four benchmarks.
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.