Program Synthesis via Test-Time Transduction
Authors: Kang-il Lee
Jahyun Koo
Seunghyun Yoon
Minbeom Kim
Hyukhun Koh
Dongryeol Lee
Kyomin Jung
Venue: NeurIPS 2025 poster ()
Keywords: program synthesis
code generation
large language models
world models
Primary area: applications
TL;DR: We introduce transductive program synthesis: synthesizing programs using test inputs.

Abstract: 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.

Program Synthesis via Test-Time Transduction
Kang-il Lee'
Jahyun Koo?
Seunghyun Yoon
Minbeom Kim
Hyukhun Koh²
Dongryeol Lee'
Kyomin Jung
Dept. of ECE, Scoul National University ?IPAI, Scoul National University
Adobe Research
[4bkang,kjun) @snu. ac.kr
Abstract
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 input-output examples-typicalle ttyicaally aim generalize from training examples, they often struggle with robustness, especially in real-world settings where train- ing examples are limited and test inputs involve various edge cases. To address this, we propose a novel framework that improves robustness by treating syn- thesis as an active learning over finite hypothesis class defined by programs' outputs. We use an LLM to predict outputs for selected test inputs and elimi- nate inconsistent hypotheses, where the inputs chosen via greedy maximin algorithm to minimize the number of LLM queries required. We evaluate our approach on four benchmarks: Playgol, MBPP+, ID-ARC, and programmatic world modeling on MiniGrid. We demonstrate that our method significantly im- proves program synthesis in both accuracy and efficiency. We release our code https://gt h/tgggttuubb.... com kwtp/////eeeee...a
Introduction
Program synthesis is the task of generating programs from a given specification, where the format of the specification vary widely depending the problem setting. Recent approaches to program synthesis using large language models [47 30 rely on a natural language description, usually accompanied by few test cases, to produce a program. In inductive program synthesis, the model operates without a natural language deseription, using only a set of input-output examples [9]. A common strategy in both lines of work involves sampling or enumerating multiple 48 38
candidate programs and selecting those that satisfy the specification by executing them on the provided training examples. However, relatively little attention has been paid settings where test inputs are available at synthesis time, i.c., the transductive learning scenario.
Vapnik famously advocated for transductive inference 45 with the principle: "When solving problem of interest, do not solve a more general problem as an intermediate step." the context of program synthesis, this suggests that full generalization through induction may not be necessary if the goal is to predict outputs for fixed set of test inputs. Such transductive scenarios are common in real-world applications such spreadsheet automation or data transformation, where the goal is to synthesize one-off' program that correctly completes a given set of test inputs (Figure these settings, the number of training examples is often limited, they typically filled manually by users. As a result, programs synthesized from few examples may lack robustness when applied to the test inputs, especially if those inputs include edge cases (i.e., inputs that are atypical compared to the training examples or expose corner-case bugs in program logic). This limitation arises from
Cooresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Spreadsheet
Program
bobuctio
lambda spliitt (0)))))ppst)(((
*ilmenncchsttree 7666 5525 Adelsdorf, Germany
Adelsdorr
An Der Urania 211 1244 Anteigginiicch Germany
Agbiis pwigch
Progmm pulputs
Ground trush
3. Uffrau Strese 1464 2520 Fellheim, Germany
Felmhim
Fellheim
Scherwezentrasee 7308 Mammhelm friedrichsfeld, Germany 5 Alstericugchussee 3040 2047 Megesheim, Germany
Friedrichsffldd
Mannheim Friedrichsfeld
Megesheim
Megesheim
An example of transductive program synthesis. Given the training examples (rows 1 and 2) as input, the inductive program synthesizer generates a program that satisfies these examples. However, this program produces an incorrect output for the test input in row 4, which represents an edge case.
Figure I:
epistemic uncertainty; the model is uncertain about what kinds of inputs will appear at test time. To address this, we introduce transductive program synthesis: an approach that explicitly leverages the available test inputs during synthesis to reduce uncertainty and produce more robust programs.
In this work, we formalize transductive program synthesis and propose SYNTRA (SYNthesis-by- TRA TRAnsduction) framework to improve the robustness of programs. The input to transductive program synthesis consists of program specification and set of N test inputs, and the goal is to synthesize program that produces correct outputs on those test inputs. A straightforward approach to this problem might be to feed an LLM with the specification and test inputs and then either ask the model to (1) generate a program that satisfies them, or (2) directly predict the test outputs. However, both approaches suffer from poor scalability; their efficiency and performance degrade rapidly as the number of test inputs increases.
Alternatvvel, approach this problem learning over finite hypothesis class. The hypothesis class H is defined as a set of N-tuples, consisting of program outputs on the test inputs, where the programs are generated by program synthesis model based on the given specification. In our work, we implement the model using an LLM for its capability to generate code in general-purpose languages (e.g.. Python). The programs' outputs construct H. We assume realizable setting, in which there exists at least one hypothesis h- e H. that matches all ground truth outputs. The objective is to identify this correct hypothesis h².
inputs are collected and deduplicated to
To achieve this, we leverage a transduction model that observes a test input and program outputs candidates, and selects one output pseudo-label. Hypotheses inconsistent with this pseudo- label are eliminated from the current version of the hypothesis class. This process of transductive prediction and hypothesis elimination is repeated iteratively until single hypothesis remains. Here, the number of queries to the transduction model depends on which inputs are queried and in what order. To minimize this cost, we propose a greedy maximin algorithm, which selects the test input that eliminates the largest number of hypotheses in the worst case. We instantiate the transduction model using an LLM, leveraging pscudo-labels. As result, our framework offers the best of both worlds: program synthesis (precision, efficiency and interpretability) and LLMs (common sense and world knowledge).
reasoning abilities and world knowledge to produce high-accuracy
We evaluate our method on four program synthesis datasets: Playgol [)] an inductive program- ming benchmark for string transformation. MBPP+ BI) benchmark for generating code from a natural language description, ID-ARC [49]. a visual reasoning benchmark, and programmatic
world modeling on MiniGrid 7 environment. On these benchmarks, our algorithm significantly
outperforms purely inductive (26 or transductive [33] methods. Moreover, by choosing test inputs according to the maximin criterion, we achieve comparable accuracy with substantially fewer LLM calls (halving the extra LLM calls above the lower bound) than when selecting inputs at random. We also empirically show that the number of required query increases sublinearly with the number of inputs, making it scalable to large test sets.
Our contributions are as follows:
We formulate transductive program synthesis as a new task.
We propose SYNTRA, a general framework that significantly improves the robustness of program synthesis on edge cases, by leveraging test inputs through a transduction model.
We instantiate this framework using large language models and evaluate it on four datasets, showing up 196% improvements in task accuracy.
2

---

2 Related Work
2.1 Program Synthesis with LLMs
Large language models have recently emerged as powerful tools for program synthesis, significantly advancing the automation of software development tasks. Models such as Codex 3 and Code Llama 39 have demonstrated strong performance on benchmarks like HumanEval and MBPP M.
Several works have explored enhancing program synthesis by using execution feedback to iteratively refine candidate programs [8
23
43 and by generating diverse solutions and selecting the best
candidate based on test case results 29
30
32 or functional consensus [25 2 42] Despite these
advances, the reliability of generated programs remains a challenge, particularly the presence of edge cases or under-specified tasks [31 4. Our work seeks to improve robustness in such settings by leveraging available test inputs and the LLM's transductive prediction capability.
2.2 Inductive Program Synthesis
Our work on transductive program synthesis is closely related to the extensively studied area of inductive program synthesis. aims to generate program from input-output examples. with the synthesized program expected to generalize to unseen inputs. Applications of inductive synthesis
include string transformation [7
22 spreadsheet automation [
list processing 40 visual
reasoning g 28
symbolic regression
and graphics generation
R
Early approaches to inductive program synthesis mostly relied on hand-crafted domain-specific languages (DSLs) to limit the space of possible programs [5] 35
Recently, LLMs have emerged as powerful tools for inductive synthesis tasks, due their ability leverage extensive pre-trained knowledge and code generation capabilities in general-purposs languages such as Python 48 46).
Most of the mentioned works assume scenarios in which the number of training examples is sufficient to uniquely determine a single program. Some studies have explored designing optimal inputs for induction 37 [5) and using direct transductive prediction when program induction fails 28 While researchers adopt Bayesian program learning [21] 12, 36) to address uncertainty and learning from few examples, its primary focus is learning a prior from training data rather than leveraging multiple test inputs during inference. Our work explicitly makes use of test inputs and proposes an effective methodology for addressing them.
3 Transductive Program Synthesis and SYNTRA Framework
We begin by formally defining the task of transductive program synthesis. We then describe the most general form of the -rannddiib (SYNTRA) framework, followed by a detailed explanation in Section 4 of how we instantiate this framework using large language models.
3.1 Problem Definition
Our problem formulation closely resembles that of transductive inference. Given an input set X and output set J7, consider a function f* X + )2 with specification S. S includes M train input-output pairs {(x,, y:)) y.) E (X' x y) where (*((x; = yi for all E [M], and (optionally) a natural language task description t. Also, there
N N test inputs { visible the system. The goal of the task is to predict the test outputs (ū.).N {f (ā.)) given S and (
In transductive program synthesis, predictions for the outputs are made by first synthesizing a program f. and then applying it to the test inputs. We expect f to produce correct outputs for the given test inputs; the primary concern here is not the overall correctness or generality of f. but rather its accuracy on the specific test set. Nevertheless, producing a predictive model in the form of an executable program offers several advantages, as will be discussed further in Section 6
3.2 Sy (SYNTRA)
We frame the above problem active learning problem over a finite hypothesis class.
3

---

Algorithm 1: SYNTRA
Input: Specification S with training examples {(rg, - Test inputs { Program
synthesis model Ø; Transduction model
Output: Hypothesis h*
Function Yí, V):
2 return (1100/ E V}
3 p o(5)
// Generate programs // Filter by training examples // Get execution results and deduplicate // Initial version space
4 p + E Plf(r)) = yg. yj. [M]}
5 H < exe_ uee_dedu((Pp (a:)-m))
Vo + H
7 t + 0
8 while [Vl > do
I - arg [a gengg)((.v.) 1( V.nid & fy}l // A set of maxes of mins
10
8" + arg minser Eyer(t,y) len(y)
// Tie-break by shorter outputs // Transductive prediction // Eliminate inconsistent hypotheses
" (S, Y(i, V.))
12
V4+ f ( V [
++
end
is return h" E V4
Hypothesis class The construction of the hypothesis class H (Alg. L13-16) follows these steps:
1. Generate set of candidate programs P using a program synthesis model a.
Filter the programs to retain only those that satisfy all M provided training input-output pairs.
M
This step yields p -f A f(z,) =4
EEP
3. Execute the programs in p' on the N test inputs and deduplicate the execution results to construct our hypothesis class H not programs themselves, but the outputs of those programs.
((z)), f x xfi)))
P'). Note that the elements of H are
Since the hypothesis class defined above is only verified against the training input-output pairs, must select a hypothesis that robustly generalizes the diverse cases that may appear in the test inputs. To this end, iteratively repeat the process of input query selection, transductive prediction, and hypothesis climination until only single hypothesis remains.
To leverage the power the trans- duction model, must decide which input query for prediction. The number of queries required to eliminate all but one hypothesis depends which inputs are selected and in what order, making this choice a critical component the method. We select input based on criterion that greedily maximizes the number of hypotheses eliminated the worst case (Alg. L9--100)
Input query selection
h2
hz
hg
hg
min
A
C
82
D
D
E
1
X
F
G
G
1
Figure 2: An example the max- imin algorithm. The numbers of eliminated hypotheses in the worst are shown in the "min" column.
To describe what our maximin criterion does: for each input, we first consider the worst-case prediction by the transduction model-thin that is. the scenario in which the prediction eliminates the fewest hypotheses (as illustrated in the "min" column of Figure 2 We then select the input for which this minimum number climinated hypotheses is maximized (Ā, in Figure 2
Let us denote the i-th element of h as h[j), and the deduplicated output set for input ä; and hypothesis class H. as DA In other words. V ( E H). Then our proposed criterion to select the input index 1" can be represented as follows.
arg max min (h E H|h + y DEM.
(I)

---

While this approach does not guarantee globally optimal solution, it can be seen as greedy algorithm that makes locally optimal decision at each iteration. If we can assume that each query eliminates at least certain fixed proportion of hypotheses, then this approach requires O(log [H]
queries. Similar query selection mechanisms are widely used in the active learning literature [10 34
where it is well understood that outperforming such greedy algorithms is often provably hard [8] in the absence of additional information.
When tie occurs in the maximin value, we break ties by selecting the input whose set of possible output candidates has the shortest total length. This reduces the length of the input passed to the transduction model in the next step, helping to reduce computational cost and alleviate reasoning
burden.
Transductive prediction The next step is to use the transduction model T to predict the output for the selected input (Alg. LLI).. Presumably, the transduction model is implemented using an LLM, due to its extensive world knowledge acquired from vast corpora and strong reasoning capabilities. The model's input consists of the specification S, selected test input ã;-- for which the output is be predicted, and the set of candidate outputs Vv-, .u- The model's output ý is one of the elements from the candidate output set.
9 T(S, ã.- V-rHH)
(2)
Hypothesis elimination As the final step of each iteration, we eliminate all hypotheses that are inconsistent with the output predicted by the transduction model (Alg. LL2). We define the version space iteration denoted as Ve, as the set of hypotheses consistent with all training and test observations collected up to iteration t.
V (h V.- V--I = ú), Vo H
4 LLM-Based Instantiation
So far, we have described the most general form of the SYNTRA framework. In this section, we provide details how we instantiate this framework using LLM, focusing the implementation of the program synthesis model a and the transduction model т.
4.1 Program Synthesis Model
In our work, the program synthesis model a is function that takes program information input and generates a set of candidate programs. We implement this model by prompting an LLM. The simplest approach is providing the LLM with a natural language instruction and program specification, and then obtaining multiple candidate programs through repeated IID sampling. A crucial consideration here is the semantic diversity of the generated programs, diversity directly influences the expressiveness of the hypothesis space and thus significantly impacts the final system performance. However, IID sampling from the most powerful LLMs available today often results in programs with limited semantic diversity (24).
To overcome this limitation, we prompt the LLM to first generate distinct algorithms (implemen- tations) for solving the given programming task. Subsequently, we prompt the LLM to translate each algorithm into executable Python code. By generating algorithm lists of length e through rounds of IID sampling, we ultimately obtain a total of candidate programs as P. In Appendix C.2 observe that this approach indeed boosts diversity, leading an increased number of tasks for which at least one correct program is generated. Henceforth, we refer to this approach as AGA (Autoregressively Generated Algorithms).
4.2 Transduction Model
In our framework, the role of the transduction model is to predict the output corresponding to a given input. The choice of LLM for implementing the transduction model is presumed to be more capable than the one used for the program synthesis model. This because the program synthesis model needs to generate multiple candidate programs, making computation the main bottleneck. In contrast, the transduction model expected to be called fewer times, but each prediction must be highly accurate. We instantiate this model using two types of LLMs (gpt-4. 4. 2225500-14 or
5

---

11--40-min-2222--0---1 and compare their performance in Section 5.2
Specifically, the LLM
instructed to predict the correct output for a given test input, conditioned on the specification and candidate outputs. Additionally, we use zero-shot chain-of-thougee prompting [20) to encourage explicit reasoning by the L.M.. Since the L..M's output not guaranteed to exactly match one of the candidate outputs, we use fuzzy string matching to select the candidate that is most similar to
the LLM's prediction. We set the temperature of the program synthesis model to 1 and that of the transduction model to 0.7. Detailed prompts for both models are in Appendix B
5
Experiment
5.1 Dataset
Playgol
MBPP+
1D-ARC
MiniGrid
"Conger, NinnesotaaMM)"
Write function check whether contains given or not.
[0,0,1,0,0,0,100
Hall(0,,0) 8); Goal (1,
hall(0,1); Agent(1, detee_,irreretiee 9))
"State: Minnesata"
[[3, 7], [3, 7]]
False
[8,1,1,
actionn left
"rinceton, NeM (tu)"
[[4, 3}, [4, 3]]
True
Mall(0, 0);; (o)) (o.1) Agent(3, directions(S, [8,0,111,,,,,,,,,000
[0,1,0,0,1,0,00,00]
State: New Jersey"
[['r'), []]
True
Figure 3: Examples of Playgol, MBPP+, ID-ARC and MiniGrid domain. Test outputs are highlighted in green.
We apply transductive program synthesis to four domains: string transformation, Python programming. visual reasoning, and programmatic world modeling (Figure 3). The string transformation domain is central to spreadsheet automation technologics, such as FlashFill [17] and Smart Fill [1]. Among the available datasets, select Playgo [ real-world dataset originally designed for inductive programming, as our benchmark In Playgol, the original task is to generate a program consistent with set of given input-output examples. Each task in Playgol provides five input-output examples; to simulate realistic conditions involving epistemic uncertainty, we use only one example as a training example and treat the remaining four examples as inputs.
For the Python programming domain, we use the MBPP+ dataset K to evaluate our methodology. Compared MBPP M. MBPP+ provides significantly more diverse and numerous test cases, making especially suitable for evaluating our framework, which assumes many available test inputs and potential edge cases. Furthermore, MBPP+ provides natural language instructions describing the desired functionality for each task. This setting mirrors realistic scenarios where a user provides input data along with instruction specifying the task to be performed. MBPP+ provides least 52 input-output pairs for every task; we utilize one example as training data and between 5 and 50 examples test cases.
In the visual reasoning domain, we use ID-ARC 49). ID-ARC a ID version of the challenging 2D grid visual reasoning benchmark, ARC R and it includes a variety of visual concepts (e.g., fill, flip, mirror, denoise, etc.). In this benchmark, we use example as the training set and examples as the test set.
Finally, we validate SYNTRA's ability on programmatic world modeling (c.g. WorldCoder complex task that requires modeling interaction mechanisms between different entities and actions. We used two MiniGrid 7 environments (DoorKey, UnlockPickup), and focused on generating a transition function that, given the current state and action, outputs the next state. In our experiment, the synthesis model receives the current state, action list, and natural language mission as input, and generates the world models. The transduction model's role is select the most plausible next state candidate among multiple world model predictions. For evaluation, given a state and an action, the world model selected by SYNTRA predicts the next state, which we then compare to the ground truth next state. The state and action pairs for evaluation are collected from human play. This task is well-suited for transductive program synthesis, the action space is typically known beforehand and can serve as a visible test input. Since programmatic world modeling differs nature from the three domains discussed earlier, we present it separately in Section 5.4
"The name "Playgol" originally refers to an inductive logic programming system 9 We use the name here to refer to the string transformation dataset introduced in that work.
We manually corrected some mislabeled tasks of the dataset.

---

5.2 Main Results
Our primary focus in this section the learning over the hypothesis class defined earlier. Therefore, we filter out tasks where learning is trivial. Specifically, we only retain tasks where the hypothesis class H. constructed by o contains both correct and incorrect candidate hypotheses. After this filtering. we obtain 119 tasks with 4 test inputs from Playgol, 149 tasks with 50 test inputs from MBPP+, and 124 tasks with test inputs from DD-RCC for our evaluation.
Table 1: Comparison of different approaches the filtered Playgol and MBPP+ datasets. Filtering is based on the 32 programs generated using AGA (c = 4, 8) with 3p--40-mmmi-2024007--- 20244007-8.
Playgol train 4 test)
MBPP+ (1 train / 10
Approach
Task Acc.
Example Acc.
# Calls
Task Acc.
Example Acc.
#r Calls
Random program
66.6
79.9
70.6
88.2
Random hypothesis Vo
37.6
62.7
43.4
76.8
gpt-4.1 I for
LLM direct transduction
33
85.7
93.7
476
59.7
87.2
1490
SYNTRA w/ random query
93.3
96.0
144
84.6
94.1
198
SYNTRA maximin
93.3
96.3
131
85.9
95.6
gpt-do-mini for
LLM direct transduction
33
72.3
87.4
476
35.6
75.0
1490
SYNTRA w/ random query
91.6
95.5
140
75.2
90.4
190
SYNTRA w/ maximin
93.3
96.3
132
73.2
89.5
163
In Table and 2 we evaluate our proposed methodology against several baselines. In this experi- ment, use 10 test inputs out of 50 for MBPP+. We report two pri- mary accuracy metrics: task-level accuracy, defined as the percent- age of tasks for which all test out- puts are predicted correctly, and example-level accuracy, detined as the proportion of correctly pre- dicted test outputs. Additionally, we report the number of transduction model calls as measure of efficiency (see Section 6 for more
Table 2: Comparison of different approaches the filtered ID- ARC dataset. Filtering is based on the 128 programs generated using MoC (26 with gpt-4. maiii-n0255 04-14.
ID-ARC (1 trin test)
Approach
Task Acc.
Example Acc.
# r Calls
Random program J P
24.0
28.7
gpt-4.1
L.LM direct transduction
+
41.9
68.1
372
SYNTRA A w/ random query
71.8
82.1
179
SYNTRA w/ maximin
71.8
80.8
159
detailed discussion on computational cost). We compare SYNTRA with the following ablations.
Random program selects program uniformly random from the set of candidates that consistent with the training example (i.e., from P in our algorithm).
Random hypothesis first deduplicates the outputs of the programs to form a hypothesis class, then samples single hypothesis uniformly at random from this set. This baseline performs significantly worse than the random program bascline, suggesting that correct programs are sampled more frequently before output-based deduplication.
LLM direct transduction bypasses program synthesis entirely and instead asks the LLM to directly predict test outputs given the training example and test inputs. The prompt explicitly instructs the LLM to reason step-by-step. Interestingly, this approach outperforms the synthesis baseline (random program) on Playgol and ID-ARC but underperforms on MBPP+. We attribute this to the fact that Playgol and ID-ARC tasks often benefit from world knowledge and pattern recognition (a strength LLMs), whereas MBPP+ tasks tend to be more algorithmic in nature (a strength of programs), A key limitation of direct LLM transduction is that the number of LLM calls scales linearly with the number of test inputs, making the method computationally impractical when the test set is large.
SYNTRA with random query is variant of SYNTRA, which randomly selects the input query (from those with at least two possible output candidates) as an ablation of the maximin criterion. As shown in the table, this approach already yields significant improvements over all baselines in both domains and with both models. The performance gain especially pronounced when using a more capable model like gpt-4.1.
7

---

SYNTRA with maximin criterion is the full version of our method, including the maximin imput selection criterion. Compared to the random query variant, this method substantially reduces the number of transduction model calls, particularly in MBPP+, where the number of test inputs is larger. This result highlights the efficiency and scalability of our SYNTRA framework.
Appendix C.1
presents additional experimental results using smaller open-source LLMs. Additionally, Appendix D provides examples where our methodology succeeds and fails, along with an analysis of its strengths and weaknesses.
Task:level Example-lovel Accuracy
Num. Transduction Model
Performance Set
16
Tannburt en Medde Cate
34
84
20-
62-
Example -Nammn
wrccrr -a Sandom
Example Bandam Quiry
Arc Maemn
380
Bandsm Query
Lower Bound
Maximi
88
Yosk
86-
140
Random Quary
Maximin
120
Mumber
Number Irputs
Number
Figure Experimental results on test input scaling and the unseen test set.
Scaling test set size In real-world applications, program synthesis is especially valuable when the number of test imputs is large that manual processing is cumbersome. To simulate such conditions, we leverage the abundant test cases in MBPP+. Specifically, we vary the number of visible test inputs provided to the system: 10, 20, and 40. For each setting, measure accuracy and the number of transduction model calls.
In Figure we observe that task-level and example-level accuracy remain relatively stable regardless of the number of test inputs. In terms of transductive model call counts, the number of calls increases sub-linearly with the number of test inputs, demonstrating the scalability of our framework. Notably, the gap between the maximin and random query methods also widens as the test set grows. In addition, we indicate a "lower bound," the number of tasks where the initial hypothesis class Vo contains at least two distinet hypotheses. This value serves as a rather conservative lower bound on the number of necessary LLM calls, since at least one query is needed to resolve any ambiguity (the true minimum number of calls is likely higher). When comparing the number of LLM calls to this lower bound, we find that the maximin criterion approaches roughly twice the efficiency of the random query strategy. These results indicate that the maximin algorithm significantly improves the efficiency of the SYNTRA framework.
Performance on unseen test set Next, we investigate how well the programs synthesized via SYNTRA generalize to unseen test set. The unseen test set is constructed by selecting 10 test inputs from the 50 available in MBPP+, while the remaining 40 are used as test inputs visible to the system. We run SYNTRA using 5. 10, 20, or 40 of these visible test inputs and measure the task-level accuracy of the resulting program on the unseen test set.
The results in Figure 4 show a general trend: as the number of visible test inputs increases. the accuracy on the unseen test set also improves. When using 20 or more visible test inputs, the accuracy on the unseen test set approaches the task accuracy reported in Table T This suggests that programs synthesized via SYNTRA from a sufficiently large number of test inputs can be expected to perform comparably well even on new, unseen inputs.
5.3 Variations on Program Synthesis Model
Up to this point, we have focused on how efficiently and robustly our method can select a correct program from fixed hypothesis class constructed by particular synthesis model. However, when considering expected performance over all tasks, the choice of synthesis model becomes critically important. In this section, we examine how the choice of synthesis model affects overall performance on the full, unfiltered datasets. this experiment, we use test inputs for Playgol, 50 test inputs for MBPP+, and 3 test inputs for ID-ARC.
8

---

II sampling The AGA approach we use first generates algorithms autoregressively and then translates each into Python code. As a result, the resulting programs do not strictly follow the LLM's output distribution. This deliberate "flattening" of the output probability boosts diversity, which benefits more challenging tasks [26 30 However, may reduce the likelihood of sampling correct program in easier tasks, where the correct solution is already highly probable under the model's 's natural distribution. To investigate this phenomenon in the context of our work, we consider more standard approach for the synthesis model: IID sampling of programs from fixed prompt. We evaluate how this affects end-to-end performance.
Table 3 (IID) shows the performance of randomly selecting a program from those obtained via IID sam- pling. On Playgol and ID-ARC, IID slightly outperforms AGA.
Table 3: Task accuracies (%) of various approaches.
Approach
Playgol
MBPP+
1D-ARC
AGA
72.7
64.8
23,9
AGA + SYNTRA
82,5
72.4
37.8
IID
76.9
56.9
25.0
IID SYNTRA
82.5
59.1
38.9
MoC (26]
78.1
71.4
However, in MBPP+, performance drops significantly. This suggests that MBPP+ tasks benefit more from the diversity encouraged by AGA, which increases the chance of synthesizing robust program.
MoC + SYNTRA
83.7
74.0
49.4
AGA + test inputs as prompt
80.4
63.5
AGA + test inputs as prompt SYNTRA
84.6
70.3
IID test inputs prompt
83.2
49.3
Interestingly, the performance gap between AGA and IID on Playgol disappears when we apply SYNTRA (AGA SYNTRA v.s. IID + SYNTRA). This indicates that AGA did generate the correct program, but was underrepresented in the overall program pool and thus unlikely to be selected-SYNTRA was able to recover it. In contrast, on MBPP+, applying SYNTRA A does not close the gap between AGA and IID, implying that IID sampling failed to generate the correct program at all, leaving opportunity for SYNTRA recover it. These observations underscore the value of weveerstt--nhhnnee strategies like AGA, especially when combined with effective verification mechanisms like SYNTRA.
Ad Advanced model We also examine the impact final performance when SYNTRA is applied to state-of-ther the-art program synthesis model. We use Mixture Concepts (MoC) [26), a recent inductive program synthesis approach based on LLMs. MoC first generates distinct elementary concepts that may help solve the problem, then produces natural language hypotheses based on these concepts, and synthesizes Python programs based the hypotheses. For MBPP+, we made minor modification by including the natural language task description in the prompt.
The results in the table show that MoC alone yields mixed outcomes depending the benchmark. However, when combined with SYNTRA, performance improves even further, outperforming all other approaches we compared. This demonstrates that the SYNTRA framework can be layered on top of existing strong program synthesis models to push performance beyond current limits.
Test inputs as prompt straightforward way to directly improve the output distribution of an LLMM-hased program synthesis model is to include test inputs in the prompt, explicitly instructing the model to generate program that generalizes to those inputs. While intuitive, this approach is not scalable, the prompt length increases proportionally with the number of test inputs.
As shown Table 3 (test inputs as prompt), this method can indeed be beneficial cases like Playgol, where the number of test inputs is relatively small. However, for MBPP+, including test inputs in the prompt leads to performance drop for both AGA and IID. This likely results from the excessive prompt wengghhiinorpprattnng all 50 test inputs may overwhelm the LLM and hinder its reasoning ability. These limitations further highlight the importance of scalable alternatives such as SYNTRA, which can robustly select correct programs without overloading the prompt.
5.4 Programmatic World Modeling on MiniGrid

---

Finally, we apply SYNTRA to programmatic world modeling on MiniGrid. Both the synthesis and trans- duction models are gpt-4. 1-mini---ee manni-222504---0 We sample 16 IID programs per state, and used example-level accuracy to compute transition func-
Table 4: Task accuracies (%) on MiniGrid.
Approach
DoorKey
UnlockPickup
IID
57.1
62.9
IID SYNTRA
68.8
67.6
tion accuracy. In Table 4 SYNTRA shows substan- tial benefit for the world model synthesis task as well. SYNTRA enables learning more accurate world model, which would likely result in more efficient planning or policy learning.
A good example that illustrates how SYNTRA helps in this task is coordinate notation. In the MiniGrid state representation we used, the positive directions are to the right and downward, and this sign convention can be inferred from the coordinates of surrounding objects. Since this convention is not obvious at the outset, actions such as turn 1eft or turn right are not always implemented correctly during the synthesis stage. However, the transduction model, by directly observing the candidate output states, was able identify the correct one.
6 Discussion
Extension to online learning and human-in-the-loop Our methodology naturally extends to online or retain the corresponding program and, when across candidate programs. In such cases, the system can invoke the transduction model to update the version space accordingly. Moreover, in situations where the transduction model's confidence is low, the system can selectively ask the user for label, enabling interactive program synthesis with minimal human intervention.
settings. After identifying final hypothesis through SYNTRA, we
input arrives, detect behavioral divergence
Transductive program synthesis v.s. LLM direct transduction In our experiments, we compared transductive program synthesis and LLM direct transduction primarily by measuring the number of transduction model calls. When considering the full pipeline, the program synthesis method includes a preliminary step of generating 32 candidate programs. such cases, direct LLM prediction may result in fewer total calls. However, in our experimental setup, we used a smaller model for synthesis and larger model for transduction, prioritizing prediction quality over generation cost. SYNTRA typically required more than three calls per task, making the overall cost lower for SYNTRA despite the initial synthesis step. Furthermore, as the number of test inputs increases, the cost of direct transduction increases linearly, whereas our method remains more stable.
Beyond efficiency, transductive program synthesis offers significant advantages over direct trans- duction in terms of performance, interpretability, and extensibility to online or human- -n---n-tttt in-the-loop workflows. In domains where some tasks are inherently difficult to express through code, hybrid approach that ensembles program synthesis with direct prediction may be more effective (28
Probabilistic perspective Rather than performing probabilistic inference over programs directly, approach constructs hypothesis class by deduplicating execution results and eliminates hypothe- ses based on transductive predictions. This design choice is intended to ensure broad applicability, even to models where program probabilities synthesis models based on enumerative search. If such probabilities were available, our framework could incorporate probabilistic strategies. For instance, instead of maximin criteria, we could adopt uncertainty-base strategies or more sophisticated methods like query-by-committe [4]. These directions offer promising extensions for future work.
difficult to estimate, such black-box L.LMs or
Conclusion
We introduced transductive program synthesis, new framework that leverages test inputs during synthesis to improve the robustness and efficiency of program generation. By combining LLM-based program synthesis with transductive prediction and hypothesis elimination, our SYNTRA framework significantly outperforms baselines in terms of accuracy and efficiency. This framework is scalable, interpretable, and extensible; offering a promising direction for robust real-world program synthesis.
10

---

www.s//ppppe/20///////.a Acknowledgments and Disclosure of Funding
This work was partly supported by Institute of Information & communications Technology Plan- ning & Evaluation (IITP) grant funded by the Korea government(MSIT) (No.RS-2022-112201 184, Development and Study of AI Technologies Inexpensively Conform Evolving Policy on Ethics, 60%), and Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea governmen((MSIT) [NO.RS- -0001-2-21111111443 Artificial Intelligence Gradu- ate School Program (Seoul National University) & RR--222---1221111 Artificial Intelligence Innovation Hub (Artificial Intelligence Institute, Seoul National University)]. K. Jung is with ASRI, Scoul National University. Korea.
References
[1] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2 077.07332, 2021.
[2] Jingchang Chen, Hongxuan Tang, Zheng Chu, Qianglong Chen, Zekun Wang, Ming Liu, and Bing Qin. Divide-and-comquer meets consensus: Unleashing the power of functions in code generation. In The Thirty- Annual Conference on Neural Information Processing Systems, 2024. URL https
//openreview.o net wwee//orrumidddoffAA/iii
[3] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.0337
2021.
[4] QiHong Chen, Jiachen Yu, Jiawei Li, Jiecheng Deng, Justin Tian Jin Chen, and Iftekhar Ahmed. A deep dive into large language model code generation mistakes: What and why? arXiv preprint 2ix:::2111111111 2024.
[5] Xinyun Chen, Chang Liu, and Dawn Song. Deccution-guides neural program synthesis. In Interna- tional Conference Learning Representations, 2019. URL | Higf0iAqYm
[6] Xinyun Chen, Petros Maniatis, Rishabh Singh, Charles Sutton, Hanjun Dai, Max Lin, and Denny Zhou. Spreadsheetcoder: Formula prediction from semi-structured context. In Marina Meila and Tong Zhang, editors. Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1661-1672. PMLR, 18-24 Jul 2021. URL mlr. press/v139/chennI1: chen2 1m. html
[7] Maxime Chevalier-Boisvert,, Bolun Dai, Mark Towers, Rodrigo De Lazcano Perez- Vicente, Lucas Willems, Salem Lahlou, Suman Pal, Pablo Samuel Castro, and K Terry. Minigrid & miniworld: Modular customizable reinforcement learning environments for goal-oriented tasks. In Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023. URL httpp:// openreview terts/formmidd-PPp spm-
[8] François Chollet. On the measure of intelligence. arXiv preprint arXiv:1911.01547, 2019.
[9] Andrew Cropper. Playgol: Learning programs through play. In Proceedings of the Twenty-Eiee Eight International Joint Conference Artificial Intelligence, IJCAI-19, pages 6074-6080. International Joint Conferences on Artificial Intelligence Organization, 2019. doi: 10.24963/icaii20199844) URLiattps //doi.org/10. 24963/ijcai 2019/841
[10] Sanjoy Dasgupta. Analysis of greedy active learning strategy. In L. Saul, Y. Weiss, and T.. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2004. URI hhttts: http::/ppooceeigg.eeeeeee (tt.eeeeearrSsr33eeeecceeeeeeeee
[11] Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishahh Singh, Ahdel rahman Mohamed, and Pushmeet Kohli. RobustFill: Neural program learning under noisy I/O. In Doina Precup and Yee whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 990-998. PMLR, 06-11 Aug 2017. URL htttp:://proceediieee
mlr. www.spressweee http:///dddvvvllloe .ttml
[12] Kevin Ellis. Human like few-shot leaming via bayesian reasoning over natural language. In Thirty Conference on Neural Information Processing Systems, 2023. http:hhtss///pptt id-dVnhdm9MIg
net/forum?

---

[13] Kevin Ellis. Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer. Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua B. Tenenbaum. Dreamcoder: bootstrapping inductive program synthesis with wake-sleep library learning. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2021, page 3558 New York, NY, USA, 2021. Association for Computing Machinery, ISBN 978 1450383912 12. doi: 10.1 10.1145/343348.
3454080. URL http:: //do:::///oooooo orgg org/10..// 1145/3453488 3453433 34444434533333
3454080
[14] Google. Use smart fill in sheets to automate data entry. URL answer 191119991152211111
[15] Gabriel Grand, Valerio Pepe, Jacob Andreas, and Joshua B Tenenbaum. Loose lips sink ships: Asking questions in battleship with languageiinformed program sampling, arXiv preprint arXiv:2402. 2402, 2024.
[16] Arya Grayeli, Atharva Sehgal, Omar Costilla Reyes, Miles Cranmer, and Swarat Chaudhuri. Symbolic regression with a learned concept library. In The eiihty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:// ott.
[17] Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. SIGPLAN
Not. 4611))117-330 January 2011. ISSN 1362-1340. doi: 10. 10.1145/1125844419926 URL https
//doi.org//a 10ogg//0...0 1eee111111111/1 1926423
[18] Laurent Hyatil and Ronald L. Rivest. Constructing optimal binary decision trees is np-compeete Informa- tion Processing Letters, 5(1):15- 17, 1976. ISSN 0020-0190. doi: http:///bb..rrg//o00000/00000000
90095-8. URL htttt::/ http://wwwwccenceerretttccc http:///ww.............a.aaaaaaa
[19] Ruhma Khan, Sumit Gulwani, Vu Le, Arjun Radhakrishna, Ashish Tiwari, and Gust Verbruggen. Lim- guided compositional program synthesis. arXiv preprint arXiv:2503.15400 2025.
[20] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. http:://t////ooto /owp://eeeeeeeeeeee/mmom .ntt/ formm"id==2TBb5yyyyf
[21] Brenden M. Lake, Ruslan Salakhutdinov, and Joshua B. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 35066266 1338, 2015, doi: 0tt26//cienne..ab305555.
URL https://wwww http::/wwwwwwwwwceeeeeeeeee science. ort//oii//aaooooooto http://iaa////////// http:/aa......../...../. wwtp:///////cncce/.eeeeaae aab3050
[22] Tessa Lau, Steven A Wolfman, Pedro Domingos, and Daniel S Weld. Programming by demonstration using version space algebra, Machine Learning, 53:111- 156, 2003.
[23] Hung Le. Yue Wang, Akhilesh Deepak Gotmare, Silvio Savarese, and Steven Hoi. CodeRL: Mastering code generation through pretrained models and deep reinforcement learning. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
/tattps::/oppnrevviie http:://///ppoorrrrreeeeee////e/
[24] Florian Le Bronnce, Alexandre Verine, Benjamin Negrevergne, Yann Chevaleyre, and Alexandre Allauzen. Exploring precision and recall to assess the quality and diversity of LLMs. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pages 1 1144,, Bangkok. Thailand, August 2024. Association for Computational Linguistics. doi: 10.18655/w1/2024..cc
URL https
//aclanthology.orgg//// 2024 acl acl-long long. 616/
[25] Kang-il Lee, Segwang Kim, and Kyomin Jung. Weakly supervised semantic parsing with execution-basee based spurious program filtering, In Houda Bouamor. Juan Pino. and Kalika Bali, editors. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 6884-6894, Singapore, December 2023. Association for Computational Linguistics. doi: 1..18653/11/2223.comm www..p-mmmpppm........ m25. U http:/:///aaaaahahaaaa www.nnhhoooy..ooooooooo wog.loogogoooooooooo....o. wwwp//gg...../e.ee/// 2023. emnlp-main.
[26] Kang-il Lee, Hyukhun Koh, Dongryeol I Lee, Seunghyun Yoon, Minsung Kim, and Kyomin Jung. Gener- ating diverse hypotheses for inductive reasoning. In Luis Chiruzzo, Alan Ritter, and Lu Wang, editors, Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Com- putational Linguistics: Human Language Technologies (Volume I: Long Papers), pages 8461-886 8474, Albuquerque, New Mexico, April 2025. Association for Computational Linguistics. ISBN 979-8-89176- 189-6. https:: http::/:s///acaahhoooooo/oo org/ 2025 naacl- long. 429/
[27] Wen- Dinn Li and Kevin Ellis. Is programming by example solved by LLMs? In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024, URL httpss:/opppn:t eview. net/forum? id=xqc8yyhScL
12

---

[28] Wen-Ding Li, Keya Hu, Carter Larsen. Yuging Wu, Simon Alford. Caleb Woo. Spencer M. Dunn. Hao Tang. Wei-Long Zheng, Yewen Pu, and Kevin Ellis. Combining induction and transduction for abstract reasoning, The Thirleenth International Conference on Learning Representations, 2025. URL https://openrevierv
id 1d-umdotAAADD
[29] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond. Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. Competition-levee code generation with alphacode. Science, 578(6624))1092-1009 2022.
[30] Jonathan Light, Yue Wu, Yiyou Sun, Wenchao Yu, Yanchi Liu, Xujiang Zhao, Ziniu Hu, Haifeng Chen, and Wei Cheng. SFS: Smarter code space search improves LLM inference scaling. In The Thirteenth International Conference on Learning Representations, 2025. URL http::: id=MCHuGDkExFF
ner/forum?
[31] Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang. Is your code generated by chatGPT really correct? rigorous evaluation of large language models for code generation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. htt///ttss///pponeeeeee..te torroru id-1qvx610Cu7
[32] Noble Saji Mathews and Meiyappan Nagappan. Test-driven development for code generation. arXiv preprint 2rxiv:2402.13322 13521, 2024.
[33] Suvir Mirchandani, Fei Xia. Pete Florence, brian ichter, Danny Driess, Montserrat Gonzalez Arenas. Kanishka Rao, Dorsa Sadigh, and Andy 7eng. Large language models as general pattern machines. In 7th Annual Conference on Robot Learning, 2023. URL RcZMI8MSyE]
[34] Robert Nowak. Noisy generalized binary search. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 22. Curran As- sociates, Inc., 2009. URL h https: httttp:://proceednnggg
156331877dd3380c33600022222 Papper
[35] Augustus Odena and Charles Sutton. Learning to represent programs with property signatures. In International Conference on Learning Representations, 2020. URL htttps://openeeviie..eeee///////
[36] Alessandro B. Palmarini, Christopher Lucas, and Siddharth N. Bayesian program learning by decompil- ing amortized knowledge. Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlctt, and Felix Berkenkamp, editors, Proceedings of the 41 International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 39042-39055 39055. PMLR, 21-27 Jul 2024. URL httpps:/pproeeddinng mmr wwwppppeaaaaaaaa /eteaa///33///ppm httpaaa/223//pamaariii http//palmaaininn/ 24a. .ttll
[37] Wasu Top Piriyakulkij. Cassidy Langenfeld, Tuan Anh Iee, and Kevin Ellis. Doing experiments and revising rules with natural language and probabilistic reasoning. In The Thirty-eighth Annual Conference Neural Information Procexsing Systems. 2024. /tttpllttt:///peeeett
net oorwmmmmmm Fid-HXAAFK488A
[38] Linlu Qiu, Liwei Jiang, Ximing La, Melanie Sclar, Valentina Pyatkin, Chandra Bhagavatula, Bailin Wang, Yoon Kim, Yejin Choi, Nouha Dziri, and Xiang Ren. Phenomenal yet puzzling: Testing inductive reasoning capabilities of language models with hypothesis retinement. In The Tweifih International Conference on Learning Representations, 2024. URL htLhhttss///pereeieeee
net http/forummiide ootooo/dddooo77aaaa22a
[39] Baptiste Roziere, Jonas Gehring, Fabian Glocckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, et al. Code llama: Open foundation models for code. arXiv preprint arXi: 12950, 2023.
[40] Joshua Stewart Rule. The child as hacker building more human-like models of learning. PhD thesis, Massachusetts Institute of Technology, 2020.
[41] H. S. Seung, M. Opper, and H. Sompolinsky. Query by committee. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, page 287-294, New York, NY, USA, 1992. Association for Computing Machinery. ISBN 089791497X. doi: 10.1145/130385. 130417. htt.tsss.
//doi.org//3 wtt.g//..111////11 1044//3331388 130417
[42] Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zeutlemoye, and Sida I. Wang. Natural language to code translation with execution. Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 5533-3546, Abu Dhabi, United Arab Emirates, Decem- ber 2022. Association for Computational Linguistics. URL https:://previiii aclanthology. org/
emnlp- 22 inw.ennnnttnn2222....mmm2 emnlp- 2211
13

---

[43] Hao Tang, Keya Hu, Jin Peng Zhou. Si Cheng Zhong. Wei-Long Zheng, Xujie Si, and Kevin Ellis. Code re- pair with LLMs gives exploration-exxloottionn tradeoff. In The Thirty-eighth Annual Conference Neu- Information Processing Systems, 2024.
[44] Hao Tang, Darren Yan Key, and Kevin Ellis. Worldeoder. model-based LLM agent: Building world models by writing code and interacting with the environment. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. http://ps//ppppprrrrore/ee//rrrp
[45] Vladimir Vapnik. Statistical Learning Theory. Wiley, 1998.
[46] Gust Verbruggen, Ashish Tiwari. Mukul Singh. Vu Le, and Sumit Gulwani. Execution- within- prompt search for programming-b--exxaeee Representations, 2025. URL [ttLltttt///operreiiee net Sttt//ormmmm--PPY66Wr7755
In The Thirteenth International Conference on Learning
[47] Evan Wang, Federico Cassano, Catherine Wu, Yunfeng Bai, William Song. Vaskar Nath, Ziwen Han, Sean M. Hendryx. Summer Yue, and Hugh Zhang. Planning in natural language improves LLM search for code generation. In The Thirteenth International Conference on Learning Representations, 2025. URL https::/openrrevew nwt/teettunnneeee ?ndrrmmidd-ii 4d-48WAZhHHH
[48] Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah Goodman. Hypothesis search: Inductive reasoning with language models. In The Twelfth International Conference Learning Representations, 2024. URL https://oppeareweee htgp:porrrroooooooooouuuruoaao.o wwtpfoormm.dd-/uull...
[49] Yudong Xu, Wenhao Li, Pashootan Vaczipoor, Scott Sanner, and Elias Boutros Khalil. LLMs and the abstraction and reasoning corpus: Successes, failures, and the importance object-based representations. Transactions on Machine Learning Research, 2024, ISSN 1835-8856. (tLhttps: URL //tppp/eee//eeeiee...... net/ forum? ? 11=
14

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction provide an overview of the paper's contributions, assumptions, and key ideas.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: In Section 6 we explain that our approach may incur higher costs compared to
direct LLM transduction. state the weaknesses of our framework the Section 5.2 and
Appendix D
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
15

---

Answer:
[NA]
Justification:
This paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We presented the algorithm of our methodology (Algorithm[] TD. and in Section we provided comprehensive details on the dataset, hyperparameters, and prompts used.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
We plan to release the code and data after the paper is accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //ips.cc//pill wttpcccpppppppppeeeeeeeeeeeeeeee httpa/////iieee/eeSuuuniisissss Coodeooomisssssseeeeeeee wwwssnoiicccyyyccc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
See Section S
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Due the high computational cost of using LLMs in experiments, conducted only a single run.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Since we primarily used APIs, there is no specific environment to report. The computational cost is discussed in detail in Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttps://eeurips:: wwtpeeerrrrssccpuuleeeeeeeeeeeee http:pp.....pp.......acaa.aaaaa.
Answer: [Yes]
Justification:
We checked NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work focuses on program synthesis and we do not expect any direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cited the papers for datasets we used.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
19

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
20

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [Yes]
Justification: We have explained how LLMs are utilized in both the methodology and the experiments.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neurre /t/CCooffeeencs///2222 for what should or should be described.
21

---

natural language A Limitation
While SYNTRA demonstrates strong performance, scalability, and explainability across multiple domains, it is important to recognize its limitations.
First, our approach relies on the assumption that visible test inputs exist. This assumption is critical for enabling the transduction model evaluate and filter candidate programs. domains where such inputs are absent or unobservable, the method becomes less applicable. However, this limitation can be partially addressed by generating test inputs with the LLM.
Second, SYNTRA is less effective in settings where inputs are semantically meaningless, In such cases, the LLM cannot effectively exploit its prior world knowledge, limiting the benefits of framework.
Third, although SYNTRA select the optimal program from mixture of correct and incorrect candidates, does not inherently improve the synthesis of highly complex programs. For problems that require deep search reasoning, the synthesis step remains bottleneck.
Finally, because LLMs are used as transduction models, undesirable biases present in the models may propagate to the final outputs. This raises concerns about faimess, safety, and robustness.
B
Prompts
Here, we present the prompts used for program synthesis and transduction models. The prompts below are all designed for use on Playgol. For MBPP+, we additionally prepended the natural language task description directly before the input-output examples.
Prompt for Program Synthesis Model Algorithm Generation
You will be given a list of input output pairs. There are multiple algorithms that transform each input to the corresponding output.
Generate algorithms for the transformation
form.
These algorithms should be distinct; they map the given input to the output but implemented in various ways.
Please format your algorithms as follows:
{{
"algorithm",
2: "algorithm",
}}
Input-outpar pairs: (INPUU_OUTPUT_PATRS)
Algorithms:
22

---

Prompt for Program Synthesis Model Code Generation
You will be given list of imput paput-outpus pairs and algorithm described in natural language.
Implement the given algorithm in Python function 'fn that maps the following inputs to their corresponding outputs.
Please format your Python function as follous:
"python
def fx(x):
is (INPUT_
Your code here
return # is (OUTRUT_FORMAT)
Input-outpen pairs: (INPUT_OUTPUT_PATRS)
Algorithm: (ALGORITHM)
Python function:
Prompt for Transduction Model
Based given input output pairs, select which of the outputs is most plausible for given input.
Think step-by-step and enclose your ansver with cs at the end of your response.
Input-output pairs: (INPUI_OUTPUT_PAIRS)
Test input: (TEST_INPUT)
Test output candidates: (
23

---

C Additional Results
C.1 Results with Additional LLMs
In this section, we present experimental results Playgol using more smaller open-source models. Specifically, we used Llama-3.. Inssrrt as the program synthesis model and Llama-3. 1-t...1-77--I-t-U as the transduction model.
Table 5: Comparison of different approaches the filtered Playgol dataset consisting of 124 tasks. Filtering is based on the programs generated using AGA.
Playgol (1 train test)
Approach
Task Acc.
Example Acc.
# Calls
Random program f pp'
62.5
74.8
Random hypothesis Vo
34.9
56.0
Llama-3. 1-70B-Instruch for
LLM direct transduction [3
58.1
84.3
476
SYNTRA A w/ random query
71.0
81.5
140
SYNTRA w/ maximin
78.2
84.8
128
While the overall performance is low compared to GPT-hased models, the trend of improvements achieved by SYNTRA remains consistent (Table
We also evaluate performance on the unfiltered Playgol dataset using wider range of LLMs, including gemma-3-27b-it, Claude Sonnet 4, and DeepSeek- DeepSeck-V3-0524, In this setting, we use the same LLM as both the synthesis model and the transductive model.
Table 6: Task accuracies (%) of different approaches and LLMs on the unfiltered Playgol dataset.
Approach
gemma-3-27b-it
Claude Sonnet 4
DeepSeek-V V3-03324
AGA
66.5
82.8
80.0
AGA + SYNTRA
72.0
89.8
90.2
While absolute accuracy varied across model types, we consistently observed that SYNTRA improves performance.
C.2 Program Diversity
Table 7: Comparison of program diversity.
Approach
Playgol
MBPP+
IID (Section
5.3
4.32
3.29
AGA
6.65
7.20
Here, we demonstrate the semantic diversity the programs generated by the IID and AGA methods. We define semantic diversity in terms of behavioral equivalence. The numbers in Table represent the average number of programs, out of the 32 generated, that produce unique execution results on the training and test inputs. As shown, AGA significantly boosts diversity compared to IID sampling. This increased diversity raises the likelihood that correct program is included in the program pool, thereby offering more opportunities for SYNTRA A to improve final performance.
C.3 Comparison with Majority Vote
compared the performance majority vote (MV) and SYNTRA. MV, majority vote was taken over outputs of generated programs, so there may not be program exactly matching all the submitted outputs. In our experiment, MV does provide some improvement, but it's smaller than SYNTRA.
24

---

Table 8: Task accuracies (%) of majority vote (MV) and SYNTRA on unfiltered dataset.
Approach
Playgol
MBPP+
ID-ARC
56.9
25.0
I + MV
77.5
55.7
28.9
M SYNTRA
82.5
59.1
38.9
C.4 Scaling Compute
Below are results when using MoC on the MBPP+ dataset with sample counts of 32, 64, and 128. In our experiments, MoC alone did not show clear compute scaling effect, likely because (1) with as many as 128 concepts, the relevance of newly generated concepts diminished, and (2) as the number of programs increased, the ratio incorrect programs also increased, raising the chance of wrong guess when randomly selecting outputs. However, with SYNTRA, at least the second issue is mitigated, resulting compute scaling benefits.
Table 9: Task accuracies (%) by the number of generated programs on unfiltered MBPP+ dataset.
Approach
32
64
128
McC
78.1
80.9
77.8
MoC SYNTRA
83.7
84.3
85.5
D
Case Study
D.1
Successful Cases
The task to extract the country name. The edge case here lies in the test input selected during the first iteration, where the state name appears between the city and country names. As result, some programs extract the state name ("OR") instead of the country ("USA"). In this case, the transduction model correctly selected the ground truth "USA", effectively eliminating the hypotheses that extracted the state name.
Example 1
Dataset: Playgol
Input-output pairs:
Input: "ILP 2009, Leuven, Belgium, July 02-04, 2009"
Output: "Belgium"
Iteration
Test input: "ILP 2007, Corvallis, OR, USA, June 19-21, 2007" Output candidates: ["OR", "USA", ""]
Transduction model prediction: "USA" GT output: "USA"
Change in the number of hypotheses: 6
Iteration 2
Test input: "ILP 2012, Dubrovnik, Croatia, September 17-19, 2012" Output candidates: ["Croatia", ""] Transduction model prediction: "Croatia"
GT output: "Croatia"
Change in the number of hypotheses: 2
Example In this task, the edge case arises in Iteration 2, where the challenge is how to handle situations with only occurrence of the character be removed. The transduction model chose remove the single occurrence rather than leave it unchanged, which aligned with the ground truth output.
Dataset: MBPP+
Task description: Write a Python function to remove the first and last occurrence of given character from the string.
25

---

Input-output pairs:
Input: ["hello", "1"]
Output: "heo"
Iteration
Test input: ["xxx", "x"]
Output candidates: ["x", ""] Transduction model prediction: "x" GT output: "x"
Change in the number of hypotheses: 8
Iteration 2
Test input: ["xrworlaaada", "x"]
Output candidates: ["rworlaaada", "xrworlaaada", "worlaaada"] Transduction model prediction: "rworlaaada"
GT output: "rworlaaada"
Change in the number of hypotheses: 4
Iteration 3
Test input: ["lo", "a"]
Output candidates: ["ValueError( ("suuuesrrrrrrsuiiiiiiii ('substring not found)"", "lo"] Transduction model prediction: "lo"
GT output: "lo"
Change in the number hypotheses:
D.2 Failed Cases
In this problem, is difficult use world knowledge resolve uncertainty. The correct program logic is to output the substring up to (but not including) the first uppercase letter. However, based on the given training example alone, program that outputs the first three characters of the input string could also satisfy it. Since the input strings in this problem are meaningless and arbitrary, there is little information available determine which of the two programs correct. In such cases, it would be preferable to query the user in order to generate program that aligns with their intent.
Example 1
Dataset: Playgol
Input-outpin pairs:
Input: wwordigghrbrrrplzzzairiqqwe
Output: "wor"
Iteration 1
Test input: "horplggrwbooeiggvrryyhttt Output candidates: ["htv", "" "htvp"]
Transduction model prediction: "htv"
GT output: "htvp"
Change in the number of hypotheses: 3
Example This is a case where the ambiguity present in the task description is reflected in the hypothesis class.
Dataset: MBPP+
Task description: Write a function that checks whether a string contains the "a" character followed by two three "b" characters. Input-output pairs:
Input: "ac"
Output: False
Iteration
Test input:
Output candidates: [True, False, None] Transduction model prediction: False
GT output: False
Change in the number of hypotheses: -> 2
Iteration
Test input: "abbbba"
26

---

Output candidates: [False, True] Transduction model prediction: False GT output: True Change in the number of hypotheses: ->
27


Reviews:
[{"review_id": "VRg2Hz22ve", "reviewer": "Reviewer_2PpF", "summary": "This method proposes a new code generation setting, in which in addition to a pronlem description, a few test inputs are known (but not the golden output). They propose to leverage outputs from running the code snippet on these test inputs, by having the LLM select which outputs it considers the most well-fitting to the original description,  as a semi-symbolic method to increase performance of LLM generated code.", "questions": "- Did the authors experiment with the LLM just generating additional test inputs by itself? This seems like a trivial way to potentially increase performance even on non-transduction datasets and might further strengthen the method (also cf Code Agents which build their own test cases to cross-check their code repairs).\n- The main benefit of your maximin approach to hypothesis elimination appears to be reduction of LLM queries. I would assume that the corresponding queries are quite cheap and random queries sometimes outperform maximin - so did you consider any other order of querying that might maximize the likelihood of picking the best matching hypothesis (trading off queries)?\n- Table 1: how does your method compare to other approaches to trade of queries vs performance such as CoT/reasoning, self-consistency, etc? I think this would be interesting to show as well.\n- Did you also try other models than GPT-4o and 4.1? I think it would be especially interesting to see if this can improve performance of weaker models or introduces additional confusion.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "I think the idea presented in the paper is interesting and original. The paper is well-structured and overall clearly written.\n\nRegarding the evaluation, I have a number of points.\n- MBPP+ appears to be almost solved by the method presented. You even report that you had to filter out samples where the models consistently generate correct solutions (Line 227), resulting in a rather small dataset. Maybe you can instead try more complicated benchmarks such as Rust programs [1,2] or LBPP [3]\n- The formulation in Line 233/234 is a bit unclear: does \"predicted correctly\" refer to the LLM predicting the output correctly or the resulting program computing the correct output?\n- In Figure 4, it seems that increasing test case as inputs may result in decreasing performance. This appears unintuitive and not discussed - do you have an intuition on why this is happening? Is the model more likely to wrongly mark test outputs?\n- A general question is how diverse the test inputs to the MBPP test cases are. Do 40 test inputs generally already cover all relevant edge cases? Do the remaining 10 unseen test cases cover relevant edge cases? Can you somehow quantify this by i.e., measuring the line coverage of each test input on the golden solution and checking whether all test inputs cover all lines?\n\n[1] BabelCode MBPP (https://huggingface.co/datasets/gabeorlanski/bc-mbpp)  \n[2] Khatry et al., \"CRUST-Bench: A Comprehensive Benchmark for C-to-safe-Rust Transpilation\", arXiv 2025  \n[3] Matton et al., \"On Leakage of Code Generation Evaluation Datasets\", EMNLP 2024", "was_revised": true, "final_justification": "The main concern of myself and the other reviewers was that this papers evaluation of models and datasets was insufficient as thorough evidence for the effectiveness of the method. This was adequately addressed by additional experiments during the rebuttal. All other minor issues have been resolved as well.", "rebuttal": "Thank you for the thoughtful review and suggestions for improvements. Below we respond to your main points.\n\n> MBPP+ appears to be almost solved by the method presented. You even report that you had to filter out samples where the models consistently generate correct solutions (Line 227), resulting in a rather small dataset. Maybe you can instead try more complicated benchmarks.\n\nThank you for the suggestion. Below, we present performance results on two challenging tasks, 1D-ARC [1] and programmatic world modelling on MiniGrid [2].\n\n1D-ARC is a difficult benchmark, with a task accuracy of only 25% even when generating 128 programs per question. Below are the results using the MoC [3] method, generating 128 programs per task, with and without the application of SYNTRA. You can see that applying SYNTRA significantly improves performance.\n\nResults on filtered dataset\n\n| 1D-ARC (1 train / 3 test) | task acc. | example acc. | # transductive call |\n| --- | --- | --- | --- |\n| Random program | 24.0 | 28.7 | - |\n| LLM direct transduction | 41.9 | 68.1 | 372 |\n| SYNTRA w/ random query | **71.8** | **82.1** | 179 |\n| SYNTRA w/ maximin | **71.8** | 80.8 | **159** |\n\nBelow are the full dataset results when using MoC, AGA, and IID as synthesis models, each with and without SYNTRA. Again, you can see SYNTRA provides a large performance boost.\n\nResults on full dataset\n\n|  | 1D-ARC |\n| --- | --- |\n| MoC | 16.7 |\n| MoC + SYNTRA | **49.4** |\n| IID | 25.0 |\n| IID + SYNTRA | 38.9 |\n| AGA | 23.9 |\n| AGA + SYNTRA | 37.8 |\n\nNext, we validate SYNTRA’s ability on programmatic world modelling (e.g. WorldCoder [4])–a complex task that requires modeling interaction mechanisms between different entities and actions. We used two MiniGrid environments (DoorKey, UnlockPickup), and focused on generating a transition function that, given the current state and action, outputs the next state.\n\nIn our experiment, the synthesis model receives the current state, action list, and natural language mission as input, and generates the world models. The transduction model’s role is to select the most plausible next state candidate among multiple world model predictions. For evaluation, given a state and an action, the world model selected by SYNTRA predicts the next state, which we then compare to the ground truth next state. The state and action pairs for evaluation are collected from human play. This task is well-suited for transductive program synthesis, since the action space is typically known beforehand and can serve as a visible test input.\n\nBoth the synthesis and transduction models are gpt-4.1-mini. We sampled 16 IID programs per state, and used example-level accuracy to compute transition function accuracy. Again, SYNTRA was found to provide substantial benefit for the world model synthesis task as well.\n\n|  | DoorKey | UnlockPickup |\n| --- | --- | --- |\n| IID | 57.1 | 62.9 |\n| IID + SYNTRA | **68.8** | **67.6** |\n\n[1] Xu et al. (2023), LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations, TMLR.\n\n[2] Chevalier-Boisvert et al. (2023), Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks, NeurIPS D&B.\n\n[3] Lee et al. (2025), Generating Diverse Hypotheses for Inductive Reasoning, NAACL.\n\n[4] Tang et al. (2024), WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment, NeurIPS\n\n> does \"predicted correctly\" refer to the LLM predicting the output correctly or the resulting program computing the correct output?\n\nIt refers to the latter. We will revise this part to make it clearer.\n\n> In Figure 4, it seems that increasing test case as inputs may result in decreasing performance.\n\nWe believe the variability shown in Figure 4 is simply due to differences between random seeds. There is not a consistent trend of decrease, as in some cases performance remains similar or even rises again depending on the approach, so it is not consistent. However, if we were to name a possible cause for performance drop, as the number of test cases increases, the number of candidate hypotheses usually increases, which may make it harder to select the correct one.\n\n> A general question is how diverse the test inputs to the MBPP test cases are.\n\nIn MBPP+ [5], which we used, a large number of new test cases are created, and the test cases are reduced while maximally preserving the GT program’s branch coverage, so we believe it is likely that a sufficient number of edge cases are included.\n\n[5] Liu et al., Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation, NeurIPS 2023.\n\n> Did the authors experiment with the LLM just generating additional test inputs by itself?\n\nWe have not tried this, but it is a very good idea! We expect performance to be somewhere between SYNTRA and the baseline, but since a visible test set would not be needed, it could be broadly applicable and is a promising method for inductive program synthesis. We will add this to the discussion.\n\n> Did you consider any other order of querying that might maximize the likelihood of picking the best matching hypothesis (trading off queries)?\n\nThe most naive approach to maximizing the likelihood of picking the best matching hypothesis is to use all inputs as queries and aggregate the results via majority voting, etc. This is the most accurate, but the compute cost increases linearly with the number of tests, so it’s not optimal. Although we don’t have an immediate idea for a method that jointly optimizes cost and performance, this would be a good direction for future work.\n\n> How does your method compare to other approaches to trade off queries vs performance such as CoT/reasoning, self-consistency, etc?\n\nCoT is already used as a prompting strategy in all baselines, so we compared the performance of self-consistency (SC) and SYNTRA. For self-consistency, a majority vote was taken over outputs of generated programs, so there may not be a program exactly matching all the submitted outputs. In our experiment, SC does provide some improvement, but it’s smaller than SYNTRA.\n\n|  | Playgol | MBPP+ | 1D-ARC |\n| --- | --- | --- | --- |\n| IID | 76.9 | 56.9 | 25.0 |\n| IID + SC | 77.5 | 55.7 | 28.9 |\n| IID + SYNTRA | **82.5** | **59.1** | **38.9** |\n\n> Did you also try other models than GPT-4o and 4.1? I think it would be especially interesting to see if this can improve performance of weaker models or introduces additional confusion.\n\nIn Appendix B.1, there are experiments using the smaller open source models Llama-3.1-8B-Instruct and Llama-3.1-70B-Instruct. Additionally, below are results for gemma-3-27b-it, claude 4 sonnet, and DeepSeek-V3-0324 on the full, unfiltered dataset. SYNTRA shows consistent performance gains regardless of model size and type.\n\n|  | gemma-3-27b-it | claude 4 sonnet | DeepSeek-V3-0324 |\n| --- | --- | --- | --- |\n| AGA | 66.5 | 82.8 | 80.0 |\n| AGA + SYNTRA | 72.0 | 89.8 | 90.2 |"}, {"review_id": "p8vSfqPhIe", "reviewer": "Reviewer_vRSo", "summary": "This paper introduces transductive program synthesis, a new task.  And this paper proposes a framework, SYNTRA, that treats program synthesis as an active learning problem over a finite set of hypotheses, where each hypothesis corresponds to the outputs of a candidate program on the test set. To efficiently find the correct solution, SYNTRA uses a transductive LLM to predict the output for each test input, which is selected using a greedy maximin algorithm to minimize the number of LLM queries. This method demonstrated significant improvements in accuracy compared to traditional inductive and transductive techniques on MBPP and Playgol.", "questions": "Please see my comments above.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n1. The code is open-sourced, which helps replication.\n2. The paper is well-written and easy to follow.\n3. This paper introduces a new task, transductive program synthesis, which I think is indeed valuable and interesting for real-world scenarios.\n4. According to the experimental results, the proposed framework is effective on accuracy.\n\nWeakness:\n1. There is a strong assumption behind the proposed framework. That is, there is at least one correct program in the initially generated sets. If there is not, all of the computations in this framework are meaningless.\n2. For transductive models, it highly relies on the generated pseudo-label to remove hypotheses. Similar to weakness 1, this can not be mitigated if the pseudo-label is wrong.\n3. The reason why the above two limitations do not have a significant negative influence on the framework performance is that the two evaluated benchmarks are too easy for current LLMs. (At least I am quite familiar with MBPP, and I am sure it is too easy for GPT-4o or GPT-4o mini that are used for evaluation). I suggest that the authors should evaluate the proposed framework on more challenging benchmarks.\n4. Although the authors reported in Table 1 that there are fewer # $\\tau$ Calls, the authors do not discuss the # $\\sigma$ Calls compared with the baseline methods.", "was_revised": true, "final_justification": "I am convinced by the authors' rebuttal. Indeed, selecting the correct program among a mix of correct and incorrect programs is itself an important contribution. And the author's privide additional experiments to address my concern.", "rebuttal": "Thank you for the thoughtful review and suggestions for improvements. Below we respond to your main points.\n\n> There is a strong assumption behind the proposed framework. That is, there is at least one correct program in the initially generated sets. If there is not, all of the computations in this framework are meaningless.\n\nWe agree that our methodology assumes the existence of at least one correct program. However, selecting the correct program among a mix of correct and incorrect programs is itself an important contribution, because such situations are quite common in practice. As can be seen in the performances on Table 2 and other benchmarks presented below, SYNTRA substantially boosts performance calculated across full dataset (including those where there are no correct programs at all). Moreover, even if there is no correct program, SYNTRA can still find good programs that are correct for many inputs, thereby improving example-level accuracy. We would also like to emphasize that our paper is the first to propose the task of transductive program synthesis and a system to address it, which we hope will inspire a variety of future research directions aimed at improving this approach. We believe that exploring methods to mitigate the issue you raised would be a promising direction for future research.\n\n> For transductive models, it highly relies on the generated pseudo-label to remove hypotheses. Similar to weakness 1, this can not be mitigated if the pseudo-label is wrong.\n\nWe agree that our methodology depends on the accuracy of pseudo-labels. However, the performances in Table 1, Table 2, and on more challenging benchmarks below empirically show that these pseudo-labels are quite accurate.\n\nAs a potential solution to this issue, one could perform multiple samplings and use a majority vote as the pseudo-label. Alternatively, instead of using a hard label, it might be possible to use a soft label, which could provide opportunities to recover from errors. For example, in the transduction model, after sampling pseudo-labels multiple times, one could train a light-weight model with these pseudo-labels to obtain a distribution over the hypotheses.\n\n> The reason why the above two limitations do not have a significant negative influence on the framework performance is that the two evaluated benchmarks are too easy for current LLMs. I suggest that the authors should evaluate the proposed framework on more challenging benchmarks.\n\nAs empirical evidence that the above two limitations do not have a significant negative influence even on harder benchmarks, we present results on challenging program synthesis tasks such as 1D-ARC [1] and programmatic world modelling on MiniGrid [2].\n\n1D-ARC is a difficult benchmark, with a task accuracy of only 25% even when generating 128 programs per question. Below are the results using the MoC [3] method, generating 128 programs per task, with and without the application of SYNTRA. You can see that applying SYNTRA significantly improves performance.\n\nResults on filtered dataset\n\n| 1D-ARC (1 train / 3 test) | task acc. | example acc. | # transductive call |\n| --- | --- | --- | --- |\n| Random program | 24.0 | 28.7 | - |\n| LLM direct transduction | 41.9 | 68.1 | 372 |\n| SYNTRA w/ random query | **71.8** | **82.1** | 179 |\n| SYNTRA w/ maximin | **71.8** | 80.8 | **159** |\n\nBelow are the full dataset results when using MoC, AGA, and IID as synthesis models, each with and without SYNTRA. Again, you can see SYNTRA provides a large performance boost.\n\nResults on full dataset\n\n|  | 1D-ARC |\n| --- | --- |\n| MoC | 16.7 |\n| MoC + SYNTRA | **49.4** |\n| IID | 25.0 |\n| IID + SYNTRA | 38.9 |\n| AGA | 23.9 |\n| AGA + SYNTRA | 37.8 |\n\nNext, we validate SYNTRA’s ability on programmatic world modelling (e.g. WorldCoder [4])–a complex task that requires modeling interaction mechanisms between different entities and actions. We used two MiniGrid environments (DoorKey, UnlockPickup), and focused on generating a transition function that, given the current state and action, outputs the next state.\n\nIn our experiment, the synthesis model receives the current state, action list, and natural language mission as input, and generates the world models. The transduction model’s role is to select the most plausible next state candidate among multiple world model predictions. For evaluation, given a state and an action, the world model selected by SYNTRA predicts the next state, which we then compare to the ground truth next state. The state and action pairs for evaluation are collected from human play. This task is well-suited for transductive program synthesis, since the action space is typically known beforehand and can serve as a visible test input.\n\nBoth the synthesis and transduction models are gpt-4.1-mini. We sampled 16 IID programs per state, and used example-level accuracy to compute transition function accuracy. Again, SYNTRA was found to provide substantial benefit for the world model synthesis task as well.\n\n|  | DoorKey | UnlockPickup |\n| --- | --- | --- |\n| IID | 57.1 | 62.9 |\n| IID + SYNTRA | **68.8** | **67.6** |\n\n[1] Xu et al. (2023), LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations, TMLR.\n\n[2] Chevalier-Boisvert et al. (2023), Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks, NeurIPS D&B.\n\n[3] Lee et al. (2025), Generating Diverse Hypotheses for Inductive Reasoning, NAACL.\n\n[4] Tang et al. (2024), WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment, NeurIPS.\n\n> Although the authors reported in Table 1 that there are fewer # $\\tau$ Calls, the authors do not discuss the # $\\sigma$ Calls compared with the baseline methods.\n\nThe reason # $\\sigma$ Calls were not reported in the table is because the number of synthesis model calls is the same for all approaches—40 per problem (8 for AGA’s algorithm generation, 32 for code generation). We will make this point clearer in the experiment section. In addition, a more detailed discussion of the costs of $\\sigma$ and $\\tau$ calls and compute cost can be found in L355–L363."}, {"review_id": "THW2KlPZqW", "reviewer": "Reviewer_gBJE", "summary": "The paper proposes a program synthesis framework called **SYNTRA** (Synthesis-by-Transduction) for tackling programming-by-example problems. SYNTRA first gathers all synthesized candidate programs that pass the given training examples. It then obtains deduplicated test output candidates by executing these programs. Finally, it eliminates candidate programs by querying an LLM to determine which input-output pair appears most consistent with the training examples. SYNTRA repeats this process for several rounds until only one program remains. The paper conducts experiments on the Playgol and MBPP+ benchmarks and achieves significant improvements compared to baseline methods.", "questions": "- In each round, when the transduction model makes a prediction based on the input-output pairs, does it tend to favor the output that appears most frequently among the candidates?\n- What is the average number of candidate programs that pass all the training examples but produce different outputs on the test inputs for the Playgol and MBPP+ benchmarks?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\n- **Quality:**\n\n  The paper proposes a conceptually neat, scalable, and generalizable approach to reliably select the correct program from among plausible candidates that pass all the training examples. It offers an intuitive way to leverage test inputs when the training examples alone are insufficient to disambiguate among hypotheses, mirroring how humans often solve problems using both training and test examples.\n\n- **Significance:**\n\n  - SYNTRA significantly improves performance on the Playgol benchmark, compared to the randomly selected program, increasing accuracy from 66.6% to 93.3%, and also boosts MBPP+ performance from 70.6% to 75.2%.\n  - Furthermore, as more test inputs are provided, SYNTRA’s performance continues to improve on unseen test datasets, demonstrating strong scalability and generalization.\n\n- **Clarity:**\n\n  The paper is well-written, easy to follow, and clearly explains the methodology and results.\n\n**Weakness**\n\n- The paper only conducts experiments using the GPT-4o-mini model for program synthesis and GPT-4o-mini and GPT-4.1 for transduction. Including results with different model types and sizes would strengthen the paper’s conclusions.\n- Evaluating SYNTRA on a broader range of programming-by-example tasks would provide a more compelling and comprehensive understanding of its effectiveness.\n- Comparing against a majority-vote baseline would also be a valuable addition.\n- It would be interesting to analyze how SYNTRA scales with increased compute during the program synthesis stage, particularly when generating more diverse hypotheses and a larger pool of candidate programs.", "was_revised": true, "final_justification": "I am raising my score from 4 to 5 for the following reasons:\n\n1. The paper proposes a conceptually neat, scalable, and generalizable approach for reliably selecting the correct program from among plausible candidates that pass all training examples.\n\n2. The authors have expanded their evaluation in two key ways:\n- They tested the method across various state-of-the-art (SOTA) and smaller LLMs, strengthening the significance and robustness of the experimental results.\n- They included two additional benchmarks: 1D-ARC (a PBE benchmark) and MiniGrid (a world-modeling benchmark), both of which showed significant performance gains, further demonstrating the method’s generalization ability and effectiveness.\n\n3. The method achieves notable performance improvements over other widely used baseline approaches.", "rebuttal": "Thank you for the thoughtful review and suggestions for improvements. Below we respond to your main points.\n\n> The paper only conducts experiments using the GPT-4o-mini model for program synthesis and GPT-4o-mini and GPT-4.1 for transduction. Including results with different model types and sizes would strengthen the paper’s conclusions.\n\nAppendix B.1 includes experiments using the smaller open-source models Llama-3.1-8B-Instruct and Llama-3.1-70B-Instruct. Additionally, results for gemma-3-27b-it, claude 4 sonnet, and DeepSeek-V3-0324 are provided below. These results are for the unfiltered full dataset. Consistent performance improvements are observed regardless of model size or type.\n\n|  | gemma-3-27b-it | claude 4 sonnet | DeepSeek-V3-0324 |\n| --- | --- | --- | --- |\n| AGA | 66.5 | 82.8 | 80.0 |\n| AGA + SYNTRA | 72.0 | 89.8 | 90.2 |\n\n> Evaluating SYNTRA on a broader range of programming-by-example tasks would provide a more compelling and comprehensive understanding of its effectiveness.\n\nTo validate our methodology on a broader range of program synthesis tasks, we present performance results on two challenging tasks, 1D-ARC [1] and programmatic world modelling on MiniGrid [2].\n\n1D-ARC is a PBE benchmark that requires reasoning skills more related to human cognitive priors. It is a more difficult benchmark, with a task accuracy of only 25% even when generating 128 programs per question. Below are the results using the MoC [3] method, generating 128 programs per task, with and without the application of SYNTRA. You can see that applying SYNTRA significantly improves performance.\n\nResults on filtered dataset\n\n| 1D-ARC (1 train / 3 test) | task acc. | example acc. | # transductive call |\n| --- | --- | --- | --- |\n| Random program | 24.0 | 28.7 | - |\n| LLM direct transduction | 41.9 | 68.1 | 372 |\n| SYNTRA w/ random query | **71.8** | **82.1** | 179 |\n| SYNTRA w/ maximin | **71.8** | 80.8 | **159** |\n\nBelow are the full dataset results when using MoC, AGA, and IID as synthesis models, each with and without SYNTRA. Again, you can see SYNTRA provides a large performance boost.\n\nResults on full dataset\n\n|  | 1D-ARC |\n| --- | --- |\n| MoC | 16.7 |\n| MoC + SYNTRA | **49.4** |\n| IID | 25.0 |\n| IID + SYNTRA | 38.9 |\n| AGA | 23.9 |\n| AGA + SYNTRA | 37.8 |\n\nNext, we validate SYNTRA’s ability on programmatic world modelling (e.g. WorldCoder [4])–a complex task that requires modeling interaction mechanisms between different entities and actions. We used two MiniGrid environments (DoorKey, UnlockPickup), and focused on generating a transition function that, given the current state and action, outputs the next state.\n\nIn our experiment, the synthesis model receives the current state, action list, and natural language mission as input, and generates the world models. The transduction model’s role is to select the most plausible next state candidate among multiple world model predictions. For evaluation, given a state and an action, the world model selected by SYNTRA predicts the next state, which we then compare to the ground truth next state. The state and action pairs for evaluation are collected from human play. This task is well-suited for transductive program synthesis, since the action space is typically known beforehand and can serve as a visible test input.\n\nBoth the synthesis and transduction models are gpt-4.1-mini. We sampled 16 IID programs per state, and used example-level accuracy to compute transition function accuracy. Again, SYNTRA was found to provide substantial benefit for the world model synthesis task as well.\n\n|  | DoorKey | UnlockPickup |\n| --- | --- | --- |\n| IID | 57.1 | 62.9 |\n| IID + SYNTRA | **68.8** | **67.6** |\n\n[1] Xu et al. (2023), LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations, TMLR.\n\n[2] Chevalier-Boisvert et al. (2023), Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks, NeurIPS D&B.\n\n[3] Lee et al. (2025), Generating Diverse Hypotheses for Inductive Reasoning, NAACL.\n\n[4] Tang et al. (2024), WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment, NeurIPS.\n\n> Comparing against a majority-vote baseline would also be a valuable addition.\n\nWe compared the performance of majority vote (self-consistency, SC) and SYNTRA. For SC, a majority vote was taken over outputs of generated programs, so there may not be a program exactly matching all the submitted outputs. In our experiment, SC does provide some improvement, but it’s smaller than SYNTRA.\n\n|  | Playgol | MBPP+ | 1D-ARC |\n| --- | --- | --- | --- |\n| IID | 76.9 | 56.9 | 25.0 |\n| IID + SC | 77.5 | 55.7 | 28.9 |\n| IID + SYNTRA | **82.5** | **59.1** | **38.9** |\n\n> It would be interesting to analyze how SYNTRA scales with increased compute during the program synthesis stage, particularly when generating more diverse hypotheses and a larger pool of candidate programs.\n\nBelow are results when using MoC on the MBPP+ dataset with sample counts of 32, 64, and 128. In our experiments, MoC alone did not show a clear compute scaling effect, likely because (1) with as many as 128 concepts, the relevance of newly generated concepts diminished, and (2) as the number of programs increased, the ratio of incorrect programs also increased, raising the chance of a wrong guess when randomly selecting outputs. However, with SYNTRA, at least the second issue is mitigated, resulting in compute scaling benefits.\n\n|  | 32 | 64 | 128 |\n| --- | --- | --- | --- |\n| MoC | 78.1 | 80.9 | 77.8 |\n| MoC + SYNTRA | **83.7** | **84.3** | **85.5** |\n\n> In each round, when the transduction model makes a prediction based on the input-output pairs, does it tend to favor the output that appears most frequently among the candidates?\n\nSince the output candidates are deduplicated before being given to the model, each output only appears once, so this does not happen.\n\n> What is the average number of candidate programs that pass all the training examples but produce different outputs on the test inputs for the Playgol and MBPP+ benchmarks?\n\nThe requested information corresponds to the cardinality of the initial version space $\\mathcal{V}_0$. Below are the average cardinalities of $\\mathcal{V}_0$ for Playgol, MBPP+, and the newly added 1D-ARC dataset. All use AGA, and the numbers in parentheses indicate the number of generated programs.\n\n|  | Playgol | MBPP+ | 1D-ARC |\n| --- | --- | --- | --- |\n| Avg. cardinality of $\\mathcal{V}_0$ | 3.21 (32) | 2.96 (32) | 9.65 (128) |"}, {"review_id": "HpozR4SXQB", "reviewer": "Reviewer_Sgwn", "summary": "The paper considers the problem of generating programs given input-output examples (and optionally natural language). The general idea is to sample different candidate programs, and then decide between them by asking an LLM to transduce the right output for holdout tests, and preferring programs that yield outputs that align with the transductive predictions. They evaluate on text editing and MBPP problems, and consider both closed and open models.\n\nThe primary contribution of the paper is its creative method. This is an original and interesting way of leveraging holdout testcases, and of combining inductive and transductive reasoning. Because the transductive queries are expensive, they also have a clever but simple way of picking which test to try next, which is inspired by active learning criteria and works well in practice.", "questions": "Why do you set the temperature of the transduction model to be nonzero, given that you only call it once?", "limitations": "There could be a better discussion of weaknesses. Appendix C gives examples of failure modes, but would be better to synthesize a summary in the main text of the weaknesses. An obvious one is that you need access to holdout tests.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. Creativity of the method\n2. Simple enough to implement in an afternoon, but reasonably technically sophisticated\n3. Thorough evaluation, considering many different dimensions upon which to measure the system, and a range of reasonable ablations and variations (but see weakness 1)\n4. Practicality of the method. Programming-by-Examples is a real problem, and in the real world, you do actually have holdout tests that you have access to ahead of time\n\nWeakness: (**Note every one of these weaknesses was satisfactorily addressed during the rebuttal**)\n1. The program synthesis tasks that they evaluate on are frankly not very difficult\n2. They consider OpenAI models and Llama models, but could also evaluate others such as Claude, DeepSeek, etc\n3. I worry that this paper could be a little bit niche for NeurIPS. Overall I think their focus on Programming-by-Examples is fine for NeurIPS, but it's borderline, particularly given weakness (1).\n\nnitpicks:\n1. eq 3: I think you mean $\\hat{y}$ instead of $\\tilde{y}$\n2. The name Autoregressively Generated Algorithms seems gratuitous. Why not just call them programs?\n3. The figure placement could be better; it's best to have figures slightly after/beside the text that discusses them.\n4. The title is way too short and uninformative.\n\n**Note to authors**: I'm currently scoring this as borderline accept but if you're willing to fix some of the issues that I raise then I'm willing to change it to accept.", "was_revised": true, "final_justification": "I'm very impressed with the new experiments on the extra domains, which shows that it can be applied to more challenging problems, and that it is not going to be viewed as niche for a NeurIPS audience. I've raised my score and think it would be a valuable contribution to the proceedings.\n\nI hope that the authors choose a more informative title however, like \"Program Synthesis with Hold-Out Transduction\" or \"Program Synthesis with Test-Example Transduction\", or just anything which emphasizes that this is transduction on the test examples.", "rebuttal": "Thank you for the thoughtful review and support for our work. Below we respond to your main points.\n\n> The program synthesis tasks that they evaluate on are frankly not very difficult\n\nWe agree that Playgol and MBPP+ might be relatively easy for the most capable LLMs available today. Below, we provide results on more challenging program synthesis tasks: 1D-ARC [1] and programmatic world modelling on MiniGrid [2].\n\n1D-ARC is a difficult benchmark, with task accuracy of only 25% even when generating 128 programs. Below are the results using the MoC [3] methodology for 128 generated programs, where we can see that applying SYNTRA significantly improves performance.\n\nResults on filtered dataset\n\n| 1D-ARC (1 train / 3 test) | task acc. | example acc. | # transductive call |\n| --- | --- | --- | --- |\n| Random program | 24.0 | 28.7 | - |\n| LLM direct transduction | 41.9 | 68.1 | 372 |\n| SYNTRA w/ random query | **71.8** | **82.1** | 179 |\n| SYNTRA w/ maximin | **71.8** | 80.8 | **159** |\n\nBelow are the full dataset results when using MoC, AGA, and IID as synthesis models, each with and without SYNTRA. Again, you can see SYNTRA provides a large performance boost.\n\nResults on full dataset\n\n|  | 1D-ARC |\n| --- | --- |\n| MoC | 16.7 |\n| MoC + SYNTRA | **49.4** |\n| IID | 25.0 |\n| IID + SYNTRA | 38.9 |\n| AGA | 23.9 |\n| AGA + SYNTRA | 37.8 |\n\nNext, we validate SYNTRA’s ability on programmatic world modelling (e.g. WorldCoder [4])–a complex task that requires modeling interaction mechanisms between different entities and actions. We used two MiniGrid environments (DoorKey, UnlockPickup), and focused on generating a transition function that, given the current state and action, outputs the next state.\n\nIn our experiment, the synthesis model receives the current state, action list, and natural language mission as input, and generates the world models. The transduction model’s role is to select the most plausible next state candidate among multiple world model predictions. For evaluation, given a state and an action, the world model selected by SYNTRA predicts the next state, which we then compare to the ground truth next state. The state and action pairs for evaluation are collected from human play. This task is well-suited for transductive program synthesis, since the action space is typically known beforehand and can serve as a visible test input.\n\nBoth the synthesis and transduction models are gpt-4.1-mini. We sampled 16 IID programs per state, and used example-level accuracy to compute transition function accuracy. Again, SYNTRA was found to provide substantial benefit for the world model synthesis task as well.\n\n|  | DoorKey | UnlockPickup |\n| --- | --- | --- |\n| IID | 57.1 | 62.9 |\n| IID + SYNTRA | **68.8** | **67.6** |\n\n[1] Xu et al. (2023), LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations, TMLR.\n\n[2] Chevalier-Boisvert et al. (2023), Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks, NeurIPS D&B.\n\n[3] Lee et al. (2025), Generating Diverse Hypotheses for Inductive Reasoning, NAACL.\n\n[4] Tang et al. (2024), WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment, NeurIPS.\n\n> They consider OpenAI models and Llama models, but could also evaluate others such as Claude, DeepSeek, etc\n\nBelow are results for gemma-3-27b-it, claude 4 sonnet, and DeepSeek-V3-0324 on the unfiltered full dataset. We observe consistent performance improvements regardless of model size or type.\n\n|  | gemma-3-27b-it | claude 4 sonnet | DeepSeek-V3-0324 |\n| --- | --- | --- | --- |\n| AGA | 66.5 | 82.8 | 80.0 |\n| AGA + SYNTRA | 72.0 | 89.8 | 90.2 |\n\n> I worry that this paper could be a little bit niche for NeurIPS\n\nAs the experiment results on 1D-ARC and programmatic world model synthesis tasks above demonstrate, transductive program synthesis and SYNTRA can be applied to a diverse range of tasks beyond classical PBE tasks. In 1D-ARC, the pattern recognition strengths of transduction provided substantial benefits in visual inductive reasoning tasks. In MiniGrid, SYNTRA enabled learning a more accurate world model, which would likely result in more sample-efficient planning or policy learning. We believe this has appeal beyond the program synthesis community, extending to the inductive reasoning and RL communities. Furthermore, it is worth noting that PBE, in the sense of building predictive models from data, is a general machine learning paradigm. In the real world, some tasks are more efficiently solved with programs, while others are suited to neural networks. From this perspective, the method proposed in our paper is general and applicable to a wide range of areas.\n\n> eq 3: I think you mean $\\hat{y}$ instead of $\\tilde{y}$\n\nThank you. We also found the same mislabeling at L163, and will fix it accordingly.\n\n> The name Autoregressively Generated Algorithms seems gratuitous. Why not just call them programs?\n\nWe felt a distinction was needed between sampling programs iid using the same prompt, and this particular methodology. For clarification: “autoregressively” here does not mean the tokens themselves are generated autoregressively, but rather that multiple algorithms (natural language form) are generated sequentially in a single LLM session, which results in more diversity among the generated programs.\n\n> The figure placement could be better.\n\nThank you. We will incorporate this feedback.\n\n> The title is way too short and uninformative.\n\nWith the title, we wished to emphasize that we are proposing a new task, rather than a method.\n\n> Why do you set the temperature of the transduction model to be nonzero, given that you only call it once?\n\nThis was purely a performance-based choice. The final performance was better with a temperature of 0.7 compared to 0. Setting temperature >0 even when generating only a single response is also commonly observed to yield better results in reasoning tasks.\n\n> There could be a better discussion of weaknesses. Appendix C gives examples of failure modes, but would be better to synthesize a summary in the main text of the weaknesses.\n\nThank you for the suggestion. We will add a dedicated limitations section. It will cover the following points:\n\n- The assumption that visible test inputs exist is necessary.\n- The method is less effective in domains/problems where the inputs are completely meaningless, making it hard for the LLM to leverage its world knowledge.\n- SYNTRA selects the optimal program from mixtures of correct and incorrect programs, but does not enhance the ability to synthesize truly complex programs for hard problems.\n- Since LLMs are used as transduction models, any undesirable biases present in the LLM may be reflected in the final output."}]

Author rebuttal:

Meta-review: The paper proposes SYNTRA, a novel framework that improves robustness in program synthesis by treating synthesis as an active learning problem over a finite hypothesis class defined by candidate programs’ outputs. Test inputs are chosen via a greedy maximin algorithm to reduce the number of required LLM queries.

Strengths:
- Interesting, creative, and original idea that is scalable and generalizable for reliably selecting correct programs among candidates (2PpF, gBJE, Sgwn)
- Introduces transductive program synthesis, which is valuable and relevant for real-world applications (vRSo, Sgwn)
- Strong experimental results demonstrating effectiveness of the framework in improving accuracy (vRSo, gBJE, Sgwn)

Weaknesses:
- Benchmarks used are relatively easy; more complex benchmarks or broader programming-by-example tasks would strengthen the claims (2PpF, vRSo, Sgwn, gBJE). However, the authors added additional benchmarks during rebuttal.
- Experiments initially focused on OpenAI models only (gBJE, Sgwn); the authors already addressed this issue in rebuttal with results on gemma-3-27b-it, Claude 4 Sonnet, and DeepSeek-V3-0324.
- Relies on the strong assumption that at least one correct program exists in the initial candidate set (vRSo).

Overall, SYNTRA presents a creative and original framework with solid empirical performance and a novel perspective on program synthesis. While some assumptions and benchmark choices limit its strength, the contribution is promising and well-motivated.
Decision: Accept (poster)