Research map / Large language models / Agents, code and math
Program Synthesis via Test-Time Transduction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces transductive program synthesis (SYNTRA), which samples LLM programs, then uses an LLM transduction model to pick plausible test outputs on greedily chosen (maximin) test inputs to eliminate inconsistent hypotheses until one remains.
Problem
Program synthesis from few training examples is brittle on test inputs with edge cases; existing inductive and direct LLM approaches either generalize poorly or scale linearly in LLM calls with the number of test inputs.
Approach
Treat synthesis as active learning over a finite hypothesis class of program output tuples on test inputs; an LLM predicts outputs for selected test inputs and inconsistent hypotheses are eliminated, with test inputs chosen by a greedy maximin criterion to minimize LLM queries.
Key results
- On filtered Playgol, SYNTRA with maximin and gpt-4.1 reaches 93.3% task accuracy using 131 transduction calls versus 85.7% for LLM direct transduction with 476 calls.
- On filtered MBPP+ (10 of 50 test inputs), SYNTRA with maximin and gpt-4.1 reaches 85.9% task accuracy with 164 calls versus 59.7% for direct transduction with 1490 calls.
- On filtered 1D-ARC, SYNTRA with gpt-4.1 reaches 71.8% task accuracy versus 41.9% for direct transduction; the paper reports up to 196% relative improvement.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply SYNTRA maximin instead of direct LLM transduction | gpt-4.1 program synthesis · MBPP+ (1 train / 10 test) | Task Acc.: 59.7 -> 85.9 | Helped |
| use maximin query selection instead of random query selection (ablation) | SYNTRA with gpt-4.1 · MBPP+ (1 train / 10 test) | # tau Calls: 198 -> 164 | Helped |
| use maximin query selection instead of random query selection (ablation) | SYNTRA with gpt-4.1 · MBPP+ (1 train / 10 test) | Task Acc.: 84.6 -> 85.9 | Helped |
| use maximin query selection instead of random query selection (ablation) | SYNTRA with gpt-4.1 · Playgol (1 train / 4 test) | Task Acc.: 93.3 -> 93.3 | No clear effect |
| apply SYNTRA instead of random program selection | program synthesis on 1D-ARC · 1D-ARC | Task Acc.: 24.0 -> 71.8 | Helped |
| add SYNTRA to IID program sampling | program synthesis · MiniGrid DoorKey | Task accuracy: 57.1 -> 68.8 | Helped |
| add SYNTRA to IID program sampling | program synthesis · MiniGrid UnlockPickup | Task accuracy: 62.9 -> 67.6 | Helped |
| add SYNTRA to MoC | MoC program synthesis · 1D-ARC | Task accuracy: 16.7 -> 49.4 | Helped |
| replace AGA with IID program sampling (ablation) | program synthesis without SYNTRA · MBPP+ | Task accuracy: 64.8 -> 56.9 | Hurt |
| replace AGA with IID program sampling (ablation) | program synthesis with SYNTRA · Playgol | Task accuracy: 82.5 -> 82.5 | No clear effect |
| include all test inputs in the AGA synthesis prompt (ablation) | AGA program synthesis without SYNTRA · MBPP+ | Task accuracy: 64.8 -> 63.5 | Hurt |
| include all test inputs in the AGA synthesis prompt (ablation) | AGA program synthesis without SYNTRA · Playgol | Task accuracy: 72.7 -> 80.4 | Helped |
Surprising findings
- Random hypothesis sampling after output deduplicates performs much worse than random program sampling, indicating correct programs are sampled more often before deduplication.
- Direct LLM transduction beats the random-program synthesis baseline on Playgol and 1D-ARC but underperforms on MBPP+.
Limitations
- Requires visible test inputs that are meaningful; less effective when inputs are semantically meaningless.
- Does not improve synthesis of highly complex programs; synthesis remains a bottleneck.
- Transduction LLM biases may propagate to final outputs; single runs without error bars.
Experimental setup
Datasets: Playgol MBPP+ 1D-ARC MiniGrid (DoorKey, UnlockPickup) human-play state-action pairs
Benchmarks: Playgol MBPP+ 1D-ARC MiniGrid
Metrics: task accuracy example accuracy number of transduction model calls
Baselines: Random program Random hypothesis LLM direct transduction IID sampling MoC majority vote
Builds on: AGA Mixture of Concepts zero-shot chain-of-thought WorldCoder
Closest papers by meaning
- HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis (NeurIPS 2024 · similarity 0.89)
- Online Prompt Selection for Program Synthesis (AAAI 2025 · similarity 0.88)
- Once Upon an Input: Reasoning via Per-Instance Program Synthesis (NeurIPS 2025 · similarity 0.87)
- CodeChemist: Test-Time Scaling for Low-Resource Code Generation via Functional Knowledge Transfer (ICML 2026 · similarity 0.87)
- Property-Guided LLM Program Synthesis for Planning (NeurIPS 2026 · similarity 0.87)
- Self-Improving Language Models for Evolutionary Program Synthesis: A Case Study on ARC-AGI (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.