Program Synthesis via Test-Time Transduction

Thank you for the thoughtful review and support for our work. Below we respond to your main points.

The program synthesis tasks that they evaluate on are frankly not very difficult

We 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].

1D-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.

Results on filtered dataset

Below 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.

Results on full dataset

Next, 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.

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

Both 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.

[1] Xu et al. (2023), LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations, TMLR.

[2] Chevalier-Boisvert et al. (2023), Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks, NeurIPS D&B.

[3] Lee et al. (2025), Generating Diverse Hypotheses for Inductive Reasoning, NAACL.

[4] Tang et al. (2024), WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment, NeurIPS.

They consider OpenAI models and Llama models, but could also evaluate others such as Claude, DeepSeek, etc

Below 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.

I worry that this paper could be a little bit niche for NeurIPS

As 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.

eq 3: I think you mean $\hat{y}$ instead of $\tilde{y}$

Thank you. We also found the same mislabeling at L163, and will fix it accordingly.

The name Autoregressively Generated Algorithms seems gratuitous. Why not just call them programs?

We 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.

The figure placement could be better.

Thank you. We will incorporate this feedback.

The title is way too short and uninformative.

With the title, we wished to emphasize that we are proposing a new task, rather than a method.

Why do you set the temperature of the transduction model to be nonzero, given that you only call it once?

This 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.

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.

Thank you for the suggestion. We will add a dedicated limitations section. It will cover the following points:

• The assumption that visible test inputs exist is necessary.
• 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.
• 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.
• Since LLMs are used as transduction models, any undesirable biases present in the LLM may be reflected in the final output.

Having the extra domains (1D ARC and world modelling) really pushes the paper over the threshold. Thanks for your effort, and good luck.

I still think the title should be changed. How about "Program Synthesis with Hold-Out Transduction"? or "Program Synthesis with Test-Example Transduction"

Thank you for the thoughtful review and suggestions for improvements. Below we respond to your main points.

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.

Appendix 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.

Evaluating SYNTRA on a broader range of programming-by-example tasks would provide a more compelling and comprehensive understanding of its effectiveness.

To 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].

1D-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.

Results on filtered dataset

Below 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.

Results on full dataset

Next, 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.

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

Both 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.

[1] Xu et al. (2023), LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations, TMLR.

[2] Chevalier-Boisvert et al. (2023), Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks, NeurIPS D&B.

[3] Lee et al. (2025), Generating Diverse Hypotheses for Inductive Reasoning, NAACL.

[4] Tang et al. (2024), WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment, NeurIPS.

Comparing against a majority-vote baseline would also be a valuable addition.

We 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.

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.

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

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?

Since the output candidates are deduplicated before being given to the model, each output only appears once, so this does not happen.

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?

The 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.

Thank you for the thoughtful review and suggestions for improvements. Below we respond to your main points.

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.

We 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.

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.

We 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.

As 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.

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.

As 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].

1D-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.

Results on filtered dataset

Below 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.

Results on full dataset

Next, 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.

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

Both 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.

[1] Xu et al. (2023), LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations, TMLR.

[2] Chevalier-Boisvert et al. (2023), Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks, NeurIPS D&B.

[3] Lee et al. (2025), Generating Diverse Hypotheses for Inductive Reasoning, NAACL.

[4] Tang et al. (2024), WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment, NeurIPS.

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.

The 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.

Thank you for the thoughtful review and suggestions for improvements. Below we respond to your main points.

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.

Thank you for the suggestion. Below, we present performance results on two challenging tasks, 1D-ARC [1] and programmatic world modelling on MiniGrid [2].

1D-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.

Results on filtered dataset

Below 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.

Results on full dataset

Next, 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.

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

Both 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.

[1] Xu et al. (2023), LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations, TMLR.

[2] Chevalier-Boisvert et al. (2023), Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks, NeurIPS D&B.

[3] Lee et al. (2025), Generating Diverse Hypotheses for Inductive Reasoning, NAACL.

[4] Tang et al. (2024), WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment, NeurIPS

does "predicted correctly" refer to the LLM predicting the output correctly or the resulting program computing the correct output?

It refers to the latter. We will revise this part to make it clearer.

In Figure 4, it seems that increasing test case as inputs may result in decreasing performance.

We 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.

A general question is how diverse the test inputs to the MBPP test cases are.

In 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.

[5] Liu et al., Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation, NeurIPS 2023.

Did the authors experiment with the LLM just generating additional test inputs by itself?

We 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.

Did you consider any other order of querying that might maximize the likelihood of picking the best matching hypothesis (trading off queries)?

The 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.

How does your method compare to other approaches to trade off queries vs performance such as CoT/reasoning, self-consistency, etc?

CoT 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.

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.

In 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.