# Program Synthesis via Test-Time Transduction

arXiv: https://arxiv.org/abs/2509.17393 · HTML: https://mlsanity.com/paper/2509.17393/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 51 references that are in the map.
- First posted on arXiv 22 Sep 2025.

## Builds on (most cited first, 30 of 33)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation](https://mlsanity.com/paper/2305.01210/) (2023)
- [CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning](https://mlsanity.com/paper/2207.01780/) (2022)
- [Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks](https://mlsanity.com/paper/2306.13831/) (2023)
- [Large Language Models as General Pattern Machines](https://mlsanity.com/paper/2307.04721/) (2023)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Natural Language to Code Translation with Execution](https://mlsanity.com/paper/2204.11454/) (2022)
- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment](https://mlsanity.com/paper/2402.12275/) (2024)
- [Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement](https://mlsanity.com/paper/2310.08559/) (2023)
- [Planning In Natural Language Improves LLM Search For Code Generation](https://mlsanity.com/paper/2409.03733/) (2024)
- [Symbolic Regression with a Learned Concept Library](https://mlsanity.com/paper/2409.09359/) (2024)
- [LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations](https://mlsanity.com/paper/2305.18354/) (2023)
- [Combining Induction and Transduction for Abstract Reasoning](https://mlsanity.com/paper/2411.02272/) (2024)
- [Code Repair with LLMs gives an Exploration-Exploitation Tradeoff](https://mlsanity.com/paper/2405.17503/) (2024)
- [SpreadsheetCoder: Formula Prediction from Semi-structured Context](https://mlsanity.com/paper/2106.15339/) (2021)
- [Exploring Precision and Recall to assess the quality and diversity of LLMs](https://mlsanity.com/paper/2402.10693/) (2024)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [Doing Experiments and Revising Rules with Natural Language and Probabilistic Reasoning](https://mlsanity.com/paper/2402.06025/) (2024)
- [Human-like Few-Shot Learning via Bayesian Reasoning over Natural Language](https://mlsanity.com/paper/2306.02797/) (2023)
- [Divide-and-Conquer Meets Consensus: Unleashing the Power of Functions in Code Generation](https://mlsanity.com/paper/2405.20092/) (2024)
- [Learning to Represent Programs with Property Signatures](https://mlsanity.com/paper/2002.09030/) (2020)
- [Loose LIPS Sink Ships: Asking Questions in Battleship with Language-Informed Program Sampling](https://mlsanity.com/paper/2402.19471/) (2024)
- [A Deep Dive Into Large Language Model Code Generation Mistakes: What and Why?](https://mlsanity.com/paper/2411.01414/) (2024)
- [Playgol: learning programs through play](https://mlsanity.com/paper/1904.08993/) (2019)
- [Generating Diverse Hypotheses for Inductive Reasoning](https://mlsanity.com/paper/2412.13422/) (2024)

## Built on by (most cited first, 4 of 4)

- [A Survey of Inductive Reasoning for Large Language Models](https://mlsanity.com/paper/2510.10182/) (2025)
- [LiSA: Lifelong Safety Adaptation via Conservative Policy Induction](https://mlsanity.com/paper/2605.14454/) (2026)
- [Don't Let Me Ask for It: LLMs Show Deficiencies in Active Multi-Turn Information Acquisition for Abductive Inference](https://mlsanity.com/paper/2608.03388/) (2026)
- [Confidence-Gated Transductive Test Generation for Code Reranking](https://mlsanity.com/paper/2609.12489/) (2026)

## Abstract (arXiv)

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.