TLDR: A new method called SYNTRA improves program synthesis by actively using test inputs during the generation process. It leverages large language models to predict outputs for selected test cases, iteratively eliminating incorrect program hypotheses. This approach significantly boosts accuracy and efficiency across various programming tasks, especially for handling edge cases, and scales well with more test inputs.
A new research paper introduces a novel approach to program synthesis, a field focused on automatically generating computer programs from specifications. This method, termed “transductive program synthesis,” explicitly uses test inputs during the program creation process to enhance robustness and efficiency.
Traditionally, program synthesis methods, whether based on natural language descriptions or input-output examples, aim to create programs that generalize well from training data. However, these methods often struggle with real-world scenarios where training examples are limited and test inputs might include unusual or “edge” cases. This can lead to programs that are not robust enough.
To tackle this, the researchers propose a framework called SYNTRA (SYNthesis-by-TRAnsduction). SYNTRA views program synthesis as an active learning problem. It starts by generating a set of candidate programs using a program synthesis model, often powered by a large language model (LLM). These candidates are then filtered to ensure they satisfy any provided training examples.
The core innovation lies in how SYNTRA leverages test inputs. Instead of just generating a program and hoping it works on all tests, SYNTRA actively queries an LLM to predict outputs for specific test inputs. These test inputs are chosen strategically using a “greedy maximin algorithm.” This algorithm selects the input that is expected to eliminate the largest number of inconsistent program hypotheses in the worst-case scenario, thereby minimizing the total number of LLM queries needed.
Once the LLM predicts an output for a chosen test input, any candidate programs whose outputs are inconsistent with this prediction are eliminated from the “hypothesis class.” This iterative process of input selection, LLM prediction, and hypothesis elimination continues until only a single, most robust program remains. This approach combines the precision and interpretability of program synthesis with the common sense and world knowledge capabilities of LLMs.
The SYNTRA framework was evaluated across four diverse benchmarks: Playgol (string transformation), MBPP+ (Python programming from natural language), 1D-ARC (visual reasoning), and programmatic world modeling on MiniGrid. The results demonstrate that SYNTRA significantly improves program synthesis in both accuracy and efficiency compared to purely inductive or other transductive methods. For instance, on some benchmarks, it showed up to 196% improvements in task accuracy.
A key finding was the efficiency gain from the maximin input selection criterion, which substantially reduced the number of calls to the transduction model (LLM) compared to random query selection. This makes the method more scalable, especially as the number of test inputs grows, with the number of required queries increasing sub-linearly.
The research also explored different ways to instantiate the program synthesis model, including an “Autoregressively Generated Algorithms” (AGA) approach that boosts program diversity, and integrating SYNTRA with state-of-the-art models like Mixture of Concepts (MoC). In all cases, SYNTRA consistently improved performance, highlighting its ability to be layered on top of existing strong synthesis models.
While powerful, SYNTRA does have limitations. It relies on the availability of visible test inputs, may be less effective for inputs that are semantically meaningless, and doesn’t inherently improve the synthesis of extremely complex programs. Additionally, biases from the LLMs used could propagate to the final outputs.
Also Read:
- AI Learns to Fix C++ Code: A New Approach to Compilation Repair
- A Structured Approach to Generating Comprehensive Software Repositories
This work presents a promising direction for creating more robust and efficient program synthesis systems for real-world applications. You can read the full paper here: Program Synthesis via Test-Time Transduction.
