Once Upon an Input: Reasoning via Per-Instance Program Synthesis
Authors: Adam Stein
Neelay Velingker
Mayur Naik
Eric Wong
Venue: NeurIPS 2025 poster ()
Keywords: program synthesis
reasoning
LLM
instance
chain of thought
neuro-symbolic
Primary area: deep_learning

Abstract: Large language models (LLMs) excel at zero-shot inference but continue to struggle with complex, multi-step reasoning. Recent methods that augment LLMs with intermediate reasoning steps such as Chain of Thought (CoT) and Program of Thought (PoT) improve performance but often produce undesirable solutions, especially in algorithmic domains.
We introduce Per-Instance Program Synthesis (PIPS), a method that generates and refines programs at the instance level using structural feedback without relying on task-specific guidance or explicit test cases. To further improve performance, PIPS incorporates a confidence metric that dynamically chooses between direct inference and program synthesis on a per-instance basis.
Experiments across three frontier LLMs and 30 benchmarks including all tasks of Big Bench Extra Hard (BBEH), visual question answering tasks, relational reasoning tasks, and mathematical reasoning tasks show that PIPS  improves the absolute harmonic mean accuracy by up to 8.6\% and 9.4\% compared to PoT and CoT respectively,
and reduces undesirable program generations by 65.1\% on the algorithmic tasks compared to PoT with Gemini-2.0-Flash.

Once Upon an Input: Reasoning via Per-Instance Program Synthesis
Adam Stein"
Neelay Velingker" Mayur Naik Eric Wong
(steinad, neelay, mhnaik, exwong) @seas upenn. edu Psenns University of Pennsylvania
Abstract
Large language models (LLMs) excel at zero-shot inference but continue to strug- gle with complex, multi-step reasoning. Recent methods that augment LLMs with intermediate reasoning steps such as Chain of Thought (CoT) and Program of Thought (PoT) improve performance but often produce undesirable solutions, especially in algorithmic domains. We introduce Per- Per-Instance Program Synthe- sis (PIPS), method that generates and refines programs at the instance-level using structural feedback without relying on task-specific guidance or explicit test cases. To further improve performance, PIPS incorporates a confidence metric that dynamically chooses between direct inference and program synthesis a per-instance basis. Experiments across three frontier LLMs and benchmarks including all tasks of Big Bench Extra Hard (BBEH), visual question answering tasks, relational reasoning tasks, and mathematical reasoning tasks show that PIPS improves the absolute harmonic mean accuracy by up to 8.6% and 9.4% compared to PoT and CoT respectively, and reduces undesirable program generations by 65.1 % the algorithmic tasks compared PoT with Gemini-2.0-Fin
1 Introduction
Large-scale pretraining endows LLMs with the ability to recognize common concepts and perform many tasks zero-shot fashion but they still struggle with multi-step reasoning [[-]]. Recent advances in inference-time reasoning strategies such Chain of Thought (CoT) and related work 4 have significantly improved LLMs' reasoning abilities. However, they remain unreliable 7710
and unfaithful, meaning the final answer is correct for the wrong reasons 1HE.).
Unlike LLM inference, program execution enforces precise, verifiable computation. Combining LLMs with program execution offers promising reasoning method: the LLM handles perceptual inference, mapping raw input to structured form, while algorithmic reasoning is offloaded to an executable program 22 14 15). Existing work neuro-symbolic learning as well methods such as Faithful Chain of Thought (FCoT) [16] and Program Aided Language Models (PAL) [I7] adopts this approach, however, they
single fixed program per task which causes problems when task instances are varied [18]. On the other hand, methods such as Program of Thought (PoT) 19] aim to enable LLMs to generate these programs in a zero-shot manner
instance-level.
While flexible, these methods often produce undesirable programs, due three challenges instance- level program synthesis: (1) open domain: determining for a given instance if program synthesis is preferable direct inference (via CoT) remains an open question, (2) no task specifications: there are no general specifications for how the correct program should behave to guide program search,
"These authors contributed equally to this work. "Code for experiments a demo open-sourced at
com htt.s//ww...ooo/ddddmnneee/////a
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Candidate inputs program
Extract symbolic input.
Execute program on symbolic Input.
synibols
Problem
Generator
Evaluator
>>>
solve (symbols)
2
Generate program.
def solve (eymbole)
Type errors? Hardcoded ans. Run-time errons?
Code
Interpreter
Prompt indicating all structural properties
Iteratively generate programs until an acceptable one found, then execute
Algorithmicity
selector
Directly respond using CoT to avoid generating and execuling trivial programs.
Figure I: Overview of Per-Instance Program Synthesis (PIPS). PIPS addresses the open-domain nature of reasoning problems by selecting between synthesis and CoT the instance-level, avoiding unnecessarily generating programs for non-algorithmic problems. For algorithmic problems, PIPS addresses the lack of task specifications structural checks. PIPS handles unstructured input via instance-specific symbolic extraction (step I) before program synthesis (step 2). Figure
iteratively synthesizing programs using feedback based on
2 shows an example where an undesirable program is rejected before producing an acceptable one which gives the correct answer upon execution (step 3).
and (3) unstructured imput: programs typically operate over structured input, but common reasoning problems are unstructured, requiring on-the-fly instance-level input understanding.
In this paper, we propose Per-Instance Program Synthesis, or PIPS, to solve reasoning problems at the instance-level. Figure T iilustrates how PIPS addresses the aforementioned challenges. To address the open domain nature of such problems, PIPS introduces an instance-level confidence metric to decide if the LLM is better suited solving the instance with program synthesis or direct inference. It then iteratively generates and evaluates programs using feedback based on structural checks (e.g. non-triviality, syntax, type errors), specifically designed to avoid the collapse to trivial solutions and ensure well-formed computation. To handle unstructured input, PIPS explicitly performs instance- specific symbolic extraction before synthesis, decoupling program search from perceptual inference. Unlike other iterative refinement and debugging methods for code generation [[5 20 21), not require explicit test cases, examples, or other forms of task specifications.
PIPS does
Our experiments demonstrate that PIPS significantly reduces the amount of undesirable programs produced compared to baselines, and this results in improved accuracy. Notably, PIPS reduces undesirable programs by 65.1 % for algorithmic benchmarks in the Big Bench Extra Hard (BBEH) suite 77 as well as 7 additional tasks including visual question answering and mathematical reasoning, resulting in an 8.6% absolute improvement in harmonic mean accuracy over POT. We also show that our confidence metric allows us to correctly switch between CoT and program synthesis for 65% % of cases, resulting in PIPS matching CoT accuracy for majority non-algorithmic tasks and even improving performance on majority algorithmic tasks.
Our contributions are as follows:
Per-Instance Program Synthesis (PIPS): An iterative program synthesis method guided by instance- specific feedback on program structure properties, improving reasoning by addressing the chal- lenges of per-instance program synthesis methods.
Synthesis Confidence Metric: We study the tradeoff between program synthesis and CoT for answering reasoning problems, and propose synthesis confidence metric which predicts, prior to generation, which approach is more likely to yield a correct solution for given model.
state-of-the-art accuracy: PIPS improves code utilization by 65.1% on algorithmic questions leading to an 8.6% improvement in harmonic mean accuracy over PoT across 30 frontier tasks.
2 The Challenges of Per-Instance Program Synthesis
reasoning problem is a pair (ar, y) X y where raw query consisting of unstructured data such natural language text or image, and y the answer which assume is represented

---

Generator
Generator
aymbols
symbols
....
'objects': ('color'
def solve (eymbols)
{
yeellow'
small block s_aapaaaaeeeeee "cube"
'material's
ruuberr
block
"brown"
'shape'
small small_block_ size = "small"
What number of other objjects are there the same material as the small block?
amall block materiatraall None for abj in ayabola("object=]] ["objects"] if obj ["shape"" small block shape
def solve (symbols):
reasoning in comment return 3
Code Interpreter
>> solve (symbole)
Evaluator
Evaluator
4
No type errors?
No type errors?
hardcoded
hardooded No run-lime errors?
No run-lime errors?
Figure 2: Example illustrating two iterations of the synthesis loop in PIPS.
symbolically (something that could be output by program). Existing methods for generating instance-level programs for solving reasoning problems, such as PoT. produce program P y to compute the correct answer. These programs take no input, similar to main function, but can be highly general since they are often generated in a Turing-complete language such as Python.
This problem-solving strategy naturally introduces three challenges. In short, algorithmic problems well-suited to program synthesis but non-algorithmic problems are inherently ill-suited; producing program cannot be guided by traditional specifications; and interfacing the unstructured input from the problem with the program requires on-the-fly instance-level perceptual understanding.
2.1 Non-Algorithmic Problems
Algorithmic
Algo.
Non-algo.
Placeholders
8..
PoT PIPS
HMean Accuracy
0.2
Trivial code Non-trivial code
Syntax
0.9
6.3
Tool use
Type
7.0
11.5
0.1
Tokens
Trivial
18.9
54.1
0.0
40
60
PIPS PoT
PIPS
POT
Percentage (%)
(a) Fraction output code with issues: trivial (hard-
Per-instance synthesis bascline performance mostly
coded answer), type (wrong return type), syntax (parser error), and placeholders (incomplete code). cates fraction of correct solutions with non-trivial code.
algorithmic vs. non-algorithmic problems. Shading indi-
Figure 3: Failures in existing approaches to per-instance program synthesis with Gemini-2.00FFi
The per-instance synthesis setting poses a tradcoff between program synthesis and direct inference reliability. In some cases, it is more reliable for LLM to solve a problem through loken-based reasoning (like CoT) than through program synthesis. Examples include tasks like emotion under- standing and summarization, which are not traditionally considered "algorithmic". We find that when existing per-instance synthesis methods are applied to these non-algorithmic settings, they will often output trivial programs that unnecessarily invoke the Python interpreter.
To study the algorithmicity of the problem instances across variety of datasets, we design an LLM- based classifier to determine if an instance is algorithmic, meaning it could be solved by executing non-trivial program. Using this classifier, we split our suite of datasets (which includes all tasks of BBEH as well as 7 additional tasks) into algorithmic ones which have majority of algorithmic

---

There tiny shiny object that is behind the big ball that is to the right of the big metallic thing behind the big brown cube; what is color?
How many large things are in front the cyan object and behind the brown matte ball?
large objects in
impoxt cV2 import numpy as
large_ Large_objects_ obwoocts_eellieeee beliind
Analyze the
deternine the number of
Load ( "mmage.pag'"
large objects front of the oyan object
ing
and behind the brown matte ball.
Define the coordinates of the region of interest (ROI)
Pot Solution
From the image, we can see that there are lazge objects fxont
oyan object:
Pot Solution
These coordinates are approximate and may need adjus tment
the netal sphere and yellow
x1, yl 600, 400
Top-left corner of the
There is large objest bebind the brown matte ball: the blue metal sphere.
x2, y2
Bottom-right coxner the
# Extract the ROI roi = ing ly) x1:x2]
large objects in front = large objects belindd =
$ Convert the ROI to the Bav color аpаcе bav sV2.cvtColor (xo1, cV2.CO1OR BCR2BSV) .... color detected
answer
large objects in front large objects Behind
Oulput:
Answer:
Code Output:
brown
(a) Trivial program.
(b) Program operating over raw image.
Two programs generated with PoT illustrating program synthesis failures. Part (a) shows trivial program where two variables are initialized to zero, but then several steps reasoning are performed in comments, leading to their values being hard-coded rather than computed with code. Part (b) shows an input-free program to process the input image itself which would be better done using the LLM's perceptual inference. Both programs result in the wrong answer. The corresponding programs produced by PIPS yield the correct answer in both cases and are shown in Appendix B
Figure 4:
instances, and non-algorithmic ones which have a majority non-algorithmic instances. Details of our classifier and the full task split is provided in Appendix A Overall, we find that not all tasks are purely algorithmic or non-algorithmic, meaning that algorithmicity is best determined on the instance-level. In addition, improves performance on the algorithmic tasks, while having a slightly negative impact for the non-algorithmic tasks. We follow the recommendation from Kazemi et al. 77 to evaluate harmonic mean accuracy since is a challenging metric that requires improvements on the hardest tasks to improve aggregate performance. For these non-algorithmic problems, PoT rarely outputs well-formed code. Instead of producing superficial code for non-algorithmic problems, we could skip program synthesis entirely with no harm to performance interpretability.
Figure 3b shows, code execution via PoT prompting significantly
2.2 Program Search without Specifications
Existing instance-level code generation methods often use the first generated program [19] or use minimal forms of program search due to the lack of any explicit specifications for how the correct program should behave. We find that this frequently leads to "trivial" programs which have an explicit return value hard-coded. Figure 3a shows that over 50% of PoT's outputs on algorithmic tasks fall into this category. The lack of behavioral specifications leaves the LLM the option of solving the task through direct inference with the final answer wrapped shows a trivial program produced by POT. Additionally, 6.3% of programs have syntax errors and 11.5% return the wrong type which is why is undesirable to always settle with the first generated program. Per-instance synthesis approaches suffer from these problems since they lack the necessary task specifications to perform traditional program search. Our full evaluation criteria including well-formed programs, type errors, and syntax errors is in Appendix G
program. Figure 4a
2.3 Interfacing Programs with Unstructured Data
The use of programs is best when their input a well-defined symbolic structure as opposed raw data (e.g. paragraph of text or an image). Since existing methods generate input-free programs, they must either hard-code the necessary structured input into the program (using the L.LM's perceptual understanding) or the code to process the unstructured input. Figure 4b shows example of

---

Algorithm PIPS: Synthesis Loop
Require: Input x E X, symbolic extractor c, maximum iterations It
Ensure: Program P such that (c(x)) =
1: Initialize 0
2: Extract symbols:
-((x)
3: Generate initial program: Po <- ro)
4: for = to k do
5: Evaluate program: F; < (.,))
6: if 1i Pass then
7: return
8: end
9: Update symbols if they have associated errors: r141 c(2; (r, ( (F)))
Generate revised program: P.+1 +- LLM(x;; (ry)0 (P:
11: end for
12: return Ps (Fallback if none pass)
program produced by PoT on the CLEVR task [22 wherein the program attempts to parse objects from an image using code instead of leveraging the strong perceptual understanding abilities of the LLM itself. Executing the program leads to an error caused by referencing a non-existent file.
We find that 12.7% of well-formed PoT code solutions the CLEVR and Leaf multimodal datasets use the OpenCV or Pillow libraries, representing a fundamentally brittle approach to input under- standing.
3 Per-Instance Program Synthesis (PIPS)
This section addresses the above three challenges with an approach to synthesize programs on per-instance basis without task specifications. We use the general problem-solving structure of ((((z)) where c: X' - R is function mapping from raw input space to permissible program baring-complete programming language. The next sections describe how we address the previous challenges with this problem-solving solving framework.
inputs and P R + a program
3.1 Selective Program Synthesis
While program synthesis allows for more faithful and sophisticated reasoning. there may still be specific problem instances where CoT should be used. The decision between synthesis and CoT for solving an instance depends both the algorithmic nature of the problem and the model's capabilities the two respective solving approaches. Formally, given a reasoning problem (I, y) E X' x y, we must choose between two strategies: (1) direct CoT reasoning via ÿ Mea((:) (ar), where Mas denotes chain of thought inference, or (2) program synthesis via ÿ = P(c(x)), where a synthesized program and c(x: is symbolic abstraction of the input z.
Since the decision depends on model's own problem-solving abilities, we elicit it from the model before it begins reasoning. Our self srof-promp method uses ten criteria to choose between CoT and program synthesis. Each criterion results in a confidence score from the model, forming a vector S(x) (p1(x), (z)()))))))) expected execution success, and robustness of logic. For reasoning models, we include ten additional criteria relating their reasoning abilities. Motivated by prior work demonstrating that LLMs can accurately estimate the likelihood that their answer to a question correct (23), we hypothesize that these criteria, which are agnostic the downstream task, be strong predictors for the LLMs success in per-instance synthesis. Full details of the criteria are in Appendix H..2
(1)(
[0, 1 These criteria assess factors like of formalization.
Given the model's own assessment of its abilities through these probing questions, the final switch decision can either derived in a fully zero-shot manner, or a held-out calibration set can be used to derive the decision from a learned logistic classifier, enabling the switch to leverage problem solving experience for higher accuracy.
3.2 Program Synthesis without Task Specifications
5

---

Traditional program synthesis searches the space of programs guided by task specification (either input-output examples or logical specification) which determine which programs are acceptable and which are not. To perform program synthesis with just single input, we leverage auxiliary forms of specifications based on generally undesirable failure modes of code generation. Formally, given an input x E X' which may consist of a request such as "How is Bob related to Alice" as well as image inputs like an image of a family tree, we want to find a program P such that P(c(z)) = where y is the true answer. Our goal is to search for P to optimize the following:
mjn M (P) xr c(x)) + XE(P,
where M is an LLM and E is a program evaluator which checks various properties of code based on static and dynamic analysis. To design the program evaluator E, study the common failure modes of LLM code generation in this setup without a feedback loop.
PIPS is an approach to solve for P. described in Algorithm [nd illustrated in Figure | E. consisting of an LLM and program interpreter, to flag any program P. matching any of the aforementioned patterns. If an issue is detected, E produces structural feedback to aid in fixing the problem. Issues with the structured input r; result a revised program input r++1 conditioned on the history of programs and inputs. If any of the evaluator feedback pertains to the synthesized program, then the generator produces a revised program Pi+1 conditioned on the feedback past programs. This iterative refinement continues for at most k steps, or until E(P., Ti, a) detects no issues. We note that (..T.,
We design
at the initial step 0, M is prompted to produce a program that does not contain these patterns.
3.3 Converting Raw Data to Symbolic Program Input
To address the issue of interfacing discrete programs with unstructured data, we explicitly abstract the unstructured data as structured program input before program generation. The input abstraction is done with the mapping and we use an LLM for this task due to their ability for understanding general unstructured data. Concretely, the LLM processes the input identify salient entities, their attributes, and the relationships between them that are pertinent to solving the instance. This requires the LLM to infer an ad hoc schema for the JSON structure, tailored to the specific semantics of the input, rather than have this schema be predetermined. While allowing for an LLM to decide how to abstract the input into a structured form is highly general, this can lead to mistakes or missed information from the input in this step. The synthesis loop described above iteratively fixes such issues in the data abstraction in coordination with program generation.
4 Experiments
This section studies whether PIPS addresses the challenges of per-instance program synthesis. RQ1 studies the empirical performance of PIPS, and RQ2. RQ3, and RQ4 correspond to each respective challenge laid out in Section 3
4.1 Setup
Datasets We evaluate our approach using 23 tasks sourced from the Big Bench Extra Hard (BBEH) benchmark (7]. These tasks span topics such as geometric understanding, deductive logical reasoning. and commonsense understanding. Furthermore, we extend this study to the visual reasoning tasks CLEVR (22) and Leaf [24], the relational reasoning task CLUTTR 25), and four mathematical reasoning tasks of MmniMath (66.. For all datasets, we reserve a random sample of 20% of the data for calibration of our confidence switch, and we evaluate on the remaining 80% of the data. We also evaluate the generalizability of a trained confidence switch in a leave-one-dataee out evaluation scheme as well as show that fully zero-shot confidence switch is also highly effective in Appendix H.
Models To evaluate our setup across a variety of different frontier LLMs, we use Gemini-2.0-Flast 27), GPT-4.1-mini (28), and o4-mini (2). Gemini-2. 2.00ni--.0--Fash is multimodal LLM, GPT-4.1-min LLM, and o4-mini is a multimodal LLM that was trained for
is a lightweight general-purper "reasoning" with long CoT before its final response.
Baselines We evaluate PIPS against Program of Thought (PoT) 4 Chain of Thought 4 and a code interpreter tool-use agent. PoT involves prompting an LLM to generate Python code to solve the

---

HMean Accuracy
All
Algorithmic
Non-Algorithmic
0.6
Method
0.4
CoT
PoT
0.2
CI
PIPS
0.0
GPT-4.1-mini
--
04-mini
GPT-4.1 GPT-4.1-mini 1-mini
Gemini-2.0-flash
04-mini
GPT-4.1-mini
2
04-mini
Figure 5: Harmonic mean accuracy over all 30 datasets (left), on the 17 majority algorithmic tasks
(middle), and on the 10 majority non-ae algorithmic (right) for PIPS and baselines using three state-of- the-art models. The breakdown per task per model is shown in Table C.3 Table C.2
and Table C.4
Accuracy Scaling
Code Issue Reduction
HMean Accuracy
0.20
Occurrence (%)
0.2
Issues
Trivial
0.18
Type
0.1
Syntax
Placeholders
0.16
0.14
10
10
2
5
Number of Iterations
Iterations
(a) Scaling of harmonic mean accuracy across all (b) Decrease in code issues with more synthesis itera- datasets with more synthesis iterations.
tions.
Figure 6: Accuracy and code quality scaling with more iterations of PIPS with Gemini-2.0-Flash
problem and then executing the code to get a final answer. Gemini Code Interpreter (CI) is an API tool that allows the model to synthesize and execute code in an agentic manner before producing its final response.
We evaluate another agentic baseline called PoT-retries which performs PoT, but regenerates the code until the code executes without any errors, well as CodeAct [30], and -foruug----hhughtss [3]] for
2l in Appendix D
4.2
RQ1: Does PIPS outperform baselines across datasets?
We compare PIPS to baselines in terms of overall performance. Harmonic mean aggregated results of datasets as well on just the algorithmic and non-algorithmic
PIPS compared to baselines over tasks are shown in Figure Overall, we see an absolute improvement of 8.6% in harmonic mean accuracy over PoT, with up to a 23.7% improvement in absolute accuracy over PoT (on BBEH Boolean Expressions) for Ceemini-2.0-Flase mini, and 5.7% absolute improvement over PoT for o4-mini. From the middle plot, we can see that PIPS provides significant improvements over the basclines (up to 15.9% in absolute harmonic accuracy for o4-mini) on the majority algorithmic problems, while not degrading in accuracy for the non-algorithmic tasks. Full results are included in Appendix C
0.8% absolute improvement over PoT for GPT-4.1-
We further study the performance of PIPS as the number of feedback iterations k. Even at A: meaning the evaluator is not used, PIPS outperforms PoT by harmonic mean difference of 5.6% and CI by 3.7%. This gap widens as we scale as shown in Figure Iteration successfully leads to more well-formed programs which subsequently improves correctness.

---

04-mini
Gemini-2.0-Fllahh
GPT-4.1-mini
Fraction of positives
Perfect
Perfect
Perfect
0.8
0.6
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Mean predicted probability
Figure 7: Calibration curve of our selection method between program synthesis and COT. We only consider questions where the choice between synthesis and CoT determines answer correctness, and positive instance is one correctly solved by code. Therefore, score of 0.8 should mean an 80% chance solving correctly with code and a 20% chance of solving correctly with COT.
We report the average cost of PIPS and baselines in Appendix E and show that PIPS additionally achieves lower cost than other iterative approaches.
Table I: Ablation study for BBEH tasks.
Method
HMean Accuracy (%)
PIPS
20.8
PIPS (no switch)
18.3
PIPS-O (no switch)
12.9
PIPS-O (no switch, symbols)
4.3
4.3 RQ2: How effective is switching between synthesis and CoT on the instance-level?
In this RQ we investigate whether our switch can effectively decide between synthesis and CoT be- fore committing to either option. As described in Section 2.1 this is important since alg-itgoii problems almost always result in trivial programs which are equivalent to CoT, but incur an unnec- essary call to the Python interpreter. Note that non-algorithmic instances occur even in majority algorithmic tasks. We show in Appendix F that encouraging non-trivial code for non-algorithmic instances with our iterative search process reduce performance.
To evaluate our switch, we focus on cases where affects the outcome -ie.. when either PIPS or CoT is correct, but not both. These comprise 24.8% of all samples across 30 benchmarks. For Gemini-2.0-Flash the switch selects the correct method 65.3% of the time, yielding a 2.2% absolute gain in harmonic mean accuracy (Table Fxample switch decisions are shown in Appendix H.3
Furthermore, we investigate the level of calibration our switching method, As illustrated in Figure 7 the switch is indeed well calibrated. Notable sources of deviation occur at the extremes. We further study the marginal contributions of each p; with respect S in Appendix [H44 Importantly, these results demonstrate the usefulness of an LLM's intrinsic understanding of its own problem solving abilities for choosing when program synthesis appropriate on an instance-level.
4.4 RQ3: Does PIPS improve code quality and correctness?
In this RQ, we seek study how PIPS improves code quality. First, we analyze the performance results to ensure that PIPS produces programs that are meaningful. To verify alignment, we filter PIPS and all baselines' code outputs by those that are well-formed according to our evaluator criteria described in Section 3.2 As seen previously in Figure 3b) PIPS produces significantly more well- formed programs than PoT when solving algorithmic problems, and the discrepancy in absolute the Temporal Sequence task. See Appendix for
percentage points go up to 53.7%

---

Table Performance boost from PIPS fixing PoT's code issues on BBEH algorithmic tasks. Boost reflects accuracy gain on samples where PIPS corrected PoT errors.
Issue Fixed by PIPS
Performance Boost (A Acc %)
Samples Fixed
Syntax Errors
20.0
200
Wrong Return Type
16.8
297
Placeholders
7.2
194
Hardcoded Answers
5.2
1 1138
the percent of well-formed programs produced by PIPS and PoT for each of the 30 datasets. Table studies the marginal impact of each type of fix on BBEH tasks.
Next, we focus mainly on questions that are considered algorithmic, as decided by the classifier described in Section 2.1 Focusing only on algorithmic samples across all benchmarks, Figure 3a demonstrates that PIPS can significantly reduce the issues exhibited in PoT. For example, the number of trivial programs is reduced by as much as 75.6%. Type and syntax issues are reduced by 49.2% and 86.8%. respectively. Lastly, the number of programs with placeholders are reduced by 36.3%. We study this more closely as iterations scale in Figure (bb) where we show as & increases from the percent occurrence of these undesirable properties decreases.
4.5
RQ4: Does PIPS reduce ineffective handling of structured data?
Unlike existing per-instance code generation methods, PIPS produces programs that take explicit structured input. For instance, for image input, PIPS may extract relevant objects from the image and pass these objects to the program logic of program reduces issues relating the incorrect handling of structured data, like that shown in Figure [b] perform a comparison of the code produced by PIPS with POT. While 12.7% of PoT well-formed code to the multimodal benchmarks (CLEVR and Leaf) used the OpenCV or Pillow libraries which are for image processing, our method never tries to manually process images.
list. To determine if this explicit separation of the data and
We also perform an ablation as shown the bottom two rows of Table 1 where we see that the use of explicit function inputs in PIPS leads to a 4% harmonic mean improvement on BBEH. Without explicit inputs, PIPS-O (no symbols), produces a single input-free free function, but first performing structured input extraction before code generation has significant performance improvement.
Related Work
Reasoning with Code Generation. L.LMs have been used to generate structured symbolic repre- programs in PDDL, SMT, or Datalog-to enable external reasoning. These approaches rely on hand-crafted prompts and fixed DSLs that limit generality and expressiveness. Others prompt LLMs to produce executable code in general-purpose languages to solve problems directly [17
sentations-sucls as semantic parses [14 16 32]
enabling stronger abstraction and reuse. However, such methods typically rely on few-shot prompts example- based verification (as in Soogramming-by-EEaaaeee
19 33
[15] 34 35). limiting their applicability to tasks with clear specs or test cases. In contrast, PIPS performs instance- program synthesis without requiring DSLs, specs, handcrafted templates, and uses structural feedback to iteratively refine programs.
Approaches which prompt an LLM to produce code to solve problem have been used in several domains beyond math and baxt- reasoning questions. ViperGPT and followup work tackle visual question answering problems (36] 37), Voyager applies to game playing [38], and Code as Policies focuses on the application of robot control [39]. Recently, general systems such as CodeAct 300 and OpenCodeInterpreter (40] have been proposed for solving problems via code generation similar to the previously mentioned solutions for each task.
Test- Time Optimization for Reasoning, Prompting strategies like Chain of Thought [4 41 and Tree of Thought (42) enhance LLM reasoning by decomposing problems or exploring multiple inference paths. Methods such as Hypothesis Search [15] and Self-Discover [43 further improve performance by searching over program hypotheses or reasoning formats. Recent work also explores L.MSs as code evaluators 44 45), but often requires human supervision or task-specific tuning. PIPS differs

---

by selecting between direct inference and code execution using learned confidence signal, achieving robust and adaptable test-time reasoning with minimal assumptions.
Limitations and Conclusion
In this paper, we focus on simple structural code properties since they occur often in generated code. Further work is needed to determine if there more undesirable patterns in LLM-generated code. In addition, PIPS does not optimally handle problems which are best solved partly with CoT and partly with program synthesis. Future work tackle methods for problem decomposition and composing program synthesis with other forms of reasoning. Finally, while PIPS offers interpretable reasoning when using code, the conversion of the input to symbolic form still lacks faithfulness guarantees.
We introduced Per-Instance Program Synthesis (PIPS), a method that dynamically synthesizes reasoning programs by leveraging general structural feedback. By focusing synthesis the instance- level, rather than the task-level, PIPS significantly outperforms prior code-based reasoning approaches such PoT well purely textual reasoning via CoT, and produces much less trivial code than prior work. The efficacy of PIPS for solving the most challenging reasoning problems through program synthesis underscores the promise of synthesis powerful means of enabling complex reasoning, in addition to the current paradigm of CoT-driven reasoning.
Acknowledgments and Disclosure of Funding
We thank Mayank Keoliya for his feedback and help with additional baselines during the rebuttal period.
This research was supported by the ARPA-H program on Safe and Explainable Al under the award D24AC00253-00, NSF Graduate Research Fellowship, Google Research Award, and gift from AWS AI to ASSET (Penn Engineering Center on Trustworthy Al).
References
[1] Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, et al. Faith and fate: Limits of transformers compositionality. Advances in Neural Information Processing Systems, 36: 70293-70332, 2023.
[2] Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Paul Saldyt, and Anil B Murthy. Position: LLMs can't 't plan, but can help planning in LLLM-oodulo frameworks. In Forty-first International Conference on Machine Learning, 2024. URL httpps://pppeeeeieeeeeeee
[3] Lexin Zhou, Wout Schellaert, Fernando Martinez-Plumedl Yael Kovos-Daval, Cèsar Ferri, and José Hernández-Orallo. Larger and more instructable language models become less reliable. Nature, 634(8032)661-68, 2024.
[4] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-though prompting elicits reasoning in large language models. Advances neural information processing systems, 35:24824 24837, 2022.
[5] OpenAI. Learning to reason with LLMs, September 2024. URL https: com/ index haadee/learning-to-reeeee with 11mmh
Accessed: 26 April 2025.
[6] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Ilms via reinforcement learning. arXiv preprinl arXiv:2501.12948 2025.
[7] Mehran Kazemi, Bahare Fatemi, Hritik Bansal, John Palowitch, Chrysovalantis Anastasiou, Sanket Vaibhav Mehta, Lalit K Jain, Virginia Aglietti, Disha Jindal, Peter Chen, al. Big-bench extra hard. arXiv preprint 29181770.. 2025.
10

---

[8] Xingyu Chen, Jiahao Xu, Tian Liang, Zhiwei He, Jianhui Pang, Dian Yu, Linfeng Song, Qiuzhi Liu. Mengfei Zhou, Zhuosheng Zhang, al. Do not think that much for 2+ 3=? on the overthinking of ol-like llms. arXiv preprint 2rXi::2422.21887 2024.
[9] Zayne Rea Sprague, Xi Ye, Kaj Bostrom, Swarat Chaudhuri, and Greg Durrett. MuSR: Testing the limits of chain-of-thought with multistep soft reasoning. In The Twelfth International Conference on Learning Representations, 2024. URL httpttt//pppeeereette waw.arrrvvie.net/orrr.nn net/forum?
ji=yyenyQzuei
[10] Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. Chain of thoughtlessness? an analysis of cot in planning. In The Thirty-eighth Anmual Conference on Neural Information Processing Systems, 2024. URL https://pppeereeiee http://ppparrreeeeooooooooooraaa met/forrumii
[11] Tamera Lanham, Anna Chen, Ansh Radhakrishnan, Benoit Steiner, Carson Denison, Danny Hernandez, Dustin Li, Esin Durmus, Evan Hubinger, Jackson Kermion, et al. Measuring faithfulness chain-of-thought reasoning. arXiv preprint arXiv:2307.13702, 2023.
[12] Yanda Chen, Joe Benton, Ansh Radhakrishnan, Jonathan Uesato Carson Denison, John Schul- man, Arushi Somani, Peter Hase, Misha Wagner Fabien Roger Vlad Mikulik, Sam Bowman, Jan Leike Jared Kaplan, al. Reasoning models don't always say what they think. Anthropic Research, 2025.
[13] Miles Turpin, Julian Michael, Ethan Perez, and Samuel Bowman. Language models don't always say what they think: Unfaithful explanations in chain-of-thought prompting. Advances in Neural Information Processing Systems, 36:74952-74965. 2023.
[14] Ziyang Li, Jiani Huang, Jason Liu, Felix Zhu, Eric Zhao, William Dodds, Neelay Velingker, Ra- jeev Alur, and Mayur Naik. Relational programming with foundational models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10635-10644, 2024.
[15] 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 on Learning Representations, 2024. URL id=G7UtIGQm
[16] Qing Lyu, Shreya Havaldar, Adam Stein, Li Zhang, Delip Rao, Eric Wong, Marianna Apidianaki, and Chris Bullsonn-Burch.. Faithful chain-of-thougle reasoning. In The 13th International Joint Conference on Natural Language Processing and the 3rd Conference of the Asia-Pacific Chapter of the Association for Computational Linguistics (JJCNLP-AACLE 2023), 2023.
[17] Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. Pal: Program-aided language models. In International Conference Machine Learning, pages 10764-10799. PMLR, 2023.
[18] Adam Stein, Aaditya Naik, Neelay Velingker, Mayur Naik, and Eric Wong. The road to generalizable securo-yymbolc learning should be paved with foundation models. arXiv preprint arXiv:2505.24874. 2025. URL htttttt////araie //t:://////ivia//a oww.oogg///////ooooo/oooooee argg/bbs25055 2505. 24874
[19] Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W. Cohen. Program of thoughts prompt- ing: Disentangling computation from reasoning for numerical reasoning tasks. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL
net/
Corumiid=Vf74ZPE6.
[20] Kavi Gupta, Peter Ebert Christensen, Xinyun Chen, and Dawn Song. Synthesize, execute and debug: Learning to repair for neural program synthesis. Advances in Neural Information Processing Systems, 33: 13:11768-17695 2020.
[21] Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. In The Twelfth International Conference on Learning Representations, 2024. URL
11

---

[22] Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2901-2910, 2017.
[23] Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, et al. Language models (mostly) know what they know. arXiv preprint arXiv:2207.052211 2022.
[24] Alaia Bolko-Breslin, Seewon Choi, Ziyang Li, Neelay Velingker, Rajeev Alur, Mayur Naik, and Eric Wong. Data-efficient learning with neural programs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. htttlt://///perrtee
net/forum?:d:=QXQY5aa.
[25] Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. CLUTRR:
A diagnostic benchmark for inductive reasoning from text. In Kentaro Inui, Jing Jiang, Vin- cent Ng. and Xiaojun Wan, editors, Proceedings of the 2019 Conference on Empirical Meth- ods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing TEMNLP-IJCNLL
pages 4506-4515, Hong Kong, China, Novem- ber 2019. Association for Computational Linguistics. doi: 10.18653/v1/D19. 1458 URL http:s///allaathoooog..ogg////// 14458/
[26] Bofci Gao, Feifan Song. Zhe Yang, Zefan Cai, Yibo Miao, Qingxiu Dong. Lei Li, Chenghao Ma. Liang Chen, Runxin Xu, Zhengyang Tang. Benyou Wang, Daoguang Zan, Shanghaoran Quan, Ge Zhang, Lei Sha, Yichang Zhang, Xuancheng Ren, Tianyu Liu, and Baobao Chang. Omni-MATH: A universal olympiad level mathematic benchmark for large language models. In The Thirteenth International Conference on Learning Representations, 2025. URL hntps
//openreview
[27] Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean- SannBtppisste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11800 2023.
[28] OpenAL. Introducing gpt-4.1 1 in the api. Accessed: 2025-05-16.
2025.
[29] OpenAL. Introducing openai 03 and o4-mini, April 2025. introducing-o3 -3- and o4-mini/ -34---------mmmmmm
Accessed: 2025-05-06.
[30] Xingyao Wang. Yangyi Chen, Lifan Yuan, Yizhe Zhang, Yunzhu Li, Hao Peng, and Heng Ji. Executable code actions elicit better Ilm agents. In Forty-first International Conference Machine Learning, 2024.
[31] Ling Yang, Zhaochen Yu, Tianjun Zhang. Shiyi Cao, Minkai Xu, Wentao Zhang, Joseph Gonzalez, and Bin Cui. Buffer of thoughts: Thought-augmentted reasoning with large language models. Advances in Neural Information Processing Systems, 37:1 13519-1135444 2024.
[32] Yilun Hao, Yang Zhang, and Chuchu Fan. Planning anything with rigor: General-purpose zero-shot planning with LLM--ased formalized programming. In The Thirteenth International Conference on Learning Representations, 2025. URL hattps://openree 1d=0K10aL6XuK
net/forum?
[33] Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang. Logic-LM: Empowering large language models with symbolic solvers for faithful logical reasoning. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023. URL https //openreview.net//eeeeeeeeeeeeee wtw.:eewww.eeffoouuueooo 2 WZnWXXM949ZH
[34] Wen-Ding Li and Kevin Ellis. Is programming by example solved by LLMs? In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https
[35] Eric Zelikman, Qian Huang, Gabriel Poesia, Noah Goodman, and Nick Haber. Parsel: Algo- rithmic reasoning with language models by composing decompositions. Advances in Neural Information Processing Systems, 36:3 1 1666-15233,,, 2023.
12

---

[36] Didac Surís, Sachit Menon, and Carl Vondrick. Vipergpt: Visual inference via python execution for reasoning. In Proceedings of the IEEE/CVF international conference on computer vision,
pages 11888-11888, 2023.
[37] Jaywon Koo, Ziyan Yang, Paola Cascante-Bonilly Baishakhi Ray. and Vicente Ordonez. PropTest:
Automatic property testing for improved visual programming. In Yaser Al-Onaizan, Mohit Bansal, and Yun-Nung Chen, editors, Findings of the Association for Computational Linguistics: EMNLP 2024, pages 8241-8256, Miami, Florida, USA, November 2024. As- sociation for Computational Linguistics. doi: 112286653/122224
htt.://................eaaaa htttps://cclanthol.. org httg/222..iindnngss.. www.diinnennnlpl........ 483/
URL
[38] Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https http://wwww..eeeffoooooooeddfefa
[39] Jacky Liang, Wenlong Huang, Fei Xia, Peng Xu, Karol Hausman, Brian Ichter, Pete Florence, and Andy Zeng. Code as policies: Language model programs for embodied control. arXiv preprint wwxiv:2209.07733, 2022.
[40] Tianyu Zheng, Ge Zhang, Tianhao Shen, Xucling Liu, Bill Yuchen Lin, Jie Fu, Wenhu Chen, and Integrating code generation with execution and refinement. In Lun-Wei Wei Ku, Andre Martins, and Vivek Srikumar, editors, Findings of the Association for Computational Linguistics: ACL 2024, pages 12834 12859, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10.18653/v1/22 10tp/./22222mf2 2ing24..nniigs-ac.7200 URL org/ 2024. 2.04..finniii.. fww.iinginniiii.. acl. 762/
Xiang Yue.
[41] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Advances in neural information processing systems, 15:22199-22211 2022.
[42] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances in neural information processing systems, 36: 1e111180-11828 11822, 2023.
[43] Pei Zhou, Jay Pujara, Xiang Ren, Xinyun Chen, Heng-Tze Tze Cheng, Quoc Le, Ed Chi, Denny Zhou, Swaroop Mishra, and Huaixiu Steven Zheng. Self-discover: Large language models self-compose reasoning structures. Advances in Neural Information Processing Systems, 37: 126032-1260S5 2024.
[44] Hunter Lightman. Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2024. URL https
//openreview
[45] Wojeiech Zaremba and Ilya Sutskever. Learning to execute. arXiv preprint arXiv: 2014.
[46] Vladimir Vapnik, The nature of statistical learning theory. Springer science business media, 1999.
13

---

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 paper's claims are supported in Sections and with experiments.
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 in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations are addressed Section d
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on 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 images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 an 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 proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
14

---

Justification:
There are no theoretical results presented in the paper.
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 the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix 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 of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide experimental details including the datasets and models used in Section and we provide the prompts used in Appendix I
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer 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 novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of 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 all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If 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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification: All of our code, as well as logs of queried closed LLMs, are provided in the supplemental materials. All experiments and studies are reproducible and open source.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. 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 (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https Coc//ooodeeesiseeeeeee wwwpobmmsssioooooooooooi for more details.
/nipss.cc/pulli//uuui
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. 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 possible in supplemental material (appended to the paper) 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 to understand the results?
Answer: [Yes]
Justification: All experimental hyperparameters. including those pertaining to data selection and model training, are provided in the Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We study our method over different seeds. The approximate error is always negligible and reported in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at 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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error 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 out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in 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:
The compute resources are described in Appendix
K
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or 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 well 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 into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We followed the 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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a 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: [Yes]
Justification: Social impact is discussed in Appendix
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.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied 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 an 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 a 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The method presented in this paper does not pose high risk for misuse.
Guidelines:
The answer NA means that the paper poses 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 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. Lieenses 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 cite all datasets and models used in the paper in Section 4
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset'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:
We do release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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 details about compensation (if any)?
Answer: [NA]
Justification:
We do not perform any crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 the main paper.
According the NeurIPS Code of Ethics, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
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.
Depending 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 expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification:
We describe in Section 4 whenever use LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neur//: http:p/s........eeeeeee////////. for what should or should not be described.
20

---

A Algorithmic Split of Datasets
We show the split of the BBEH datasets into algorithmic and non-algorithmic datasets in Table A. This split of datasets into the two groups used in analyzing the results the main body of the paper.
Table A.1: Percent of algorithmic problems in each dataset. We call the datasets with a majority of algorithmic problems the algorithmic datasets and the other datasets the non-algorithmic datasets.
Dataset
% Algorithmic
Non-algorithmic Datasets
Leaf'
0,000
Disambiguation qa
0.000
Sare triples
0.000
Nycc
0.000
Movie recommendation
0.000
Hyperbaton
0.015
Geometric shapes
0.040
Causal understanding
0.040
CLEVR
0,155
Linguini
0,175
Omnimath-4
0.305
Sportqa
0.345
Omnimath-3
0.410
Algorithmic Datasets
Clutrr
0.750
Spatial reasoning
0,810
Omnimath-2
0,835
Buggy tables
0,940
Web of lies
0,940
Boardgame qa
0,955
Object properties
0,960
Boolean expressions
0,960
Time arithmetic
0,970
Word sorting
0.980
Dyck languages
0.980
Temporal sequence
0,990
Omnimath-1
0.995
Object counting
0,995
Zebra puzzles
0,995
Multistep arithmetic
1.000
Shuffled objects
1.000
B PIPS Programs for Figure 4
The two corresponding solutions with PIPS to the problems shown in Figure 4a and Figure 4b are included in Figure B.1 and Figure B.2 respectively.
C Full Results
The full results over all 30 datasets for Gemini-2.0-Flassh GPT-4.1-mini, and 04-mini and included in
Table C3 Table C.4. and Table C.2 respectively. Results for an open-weights model, Qwen3-235B.
A22B, for BBEH tasks is included in Table C.5
21

---

symbols ('ojject':: colo'': 'rrenn, 'material's 'rubber', "shape' 'cube', "size' 'large', 'x': 0.1, 'y': 0.43,
2
('color': 'blue', 'material's 'metal', 'shape': 'sphere', 'size': 'large',
'x': 0.4, 'y': 0.3),
('color': 'yellow', 'material'; 'metal', 'shape': 'cube', 'size': 'large',
'x': 0.6, 1y:0033
4
('color': "cyan', 'material': 'rubber', 'shape': 'cylinder', 'size": 'small',
+ :x': 0.7, 'y': 0.3),
5
('color': 'brown', 'material'; 'rubber', 'shape': 'sphere', 'size'; 'large',
'x': 0.5, 'y': 0.63]}
6
7
def solve(symbols):
Calculates the number large objects in front of the cyan object and behind the brown matte ball.
Args:
symbols: á dictionery containing information about the objects in the image.
Returns:
15
The number of large objects in front of the cyan object and behind the brown + matte ball.
cyan_x next ((obj ["x"] for obj symbols ("obolsss"""ctss" if obj ["color"] "cyan"), None) brown_x next ( (obj ["x"] for obj in symbols["objectes if obj ["color"] == "brown"), None)
21
count 0
22
for obj in if obj s] == "large":
if obj ["x"] cyan_x and obj [x]]] brown_x:
count 1
26
return count
Figure B.1: Final symbols and generated program from PIPS for the instance shown in Figure Executing the code from PIPS results in the correct answer of 1.
D Additional Baselines
In this section, compare PIPS with an iterative refinement version of PoT, CodeAct [30], and Thoought- (BoT) BI] The method PoT-retries refers to our modified version PoT which regenerates the program if the produced program results in execution implementation provided with the smolagents library from huggingface. Finally, we use the code for BoT from Yang al. [1 for this baseline and additionally fixed several bugs which previously resulted high failure rate.
We use the CodeAct
Results for PoT-retries, CodeAct, BoT, and PIPS are included in Table D.9 We show results using Gemini-2.0-Flash over all BBEH tasks since BoT does not support the multimodal tasks.
E Reasoning Costs
In addition comparing the costs of different methods for using code for solving challenging reasoning problems, we also compare the cost in terms of number of tokens and dollar cost. TT shows average input, output, and dollar cost averaged over all datasets for Gemini-2.0-ffast We find that the iterative approaches (CodeAct and Buffer of Thoughts) increase cost by more than 10X
22

---

symbols ('objects': [
2
('color:: 'purple', 'materiall 'rubber', 'shape': 'sphere', 'size': 'large',
4 'x': 0.0},
3
('color': 'purple', 'material'' 'metal', 'shape': 'sphere', 'size': 'large',
'x': 1.0),
('color:: 'blue', 'material'; 'rubber', 'shape': cube', 'size': 'amall', 'x':
+ 2.03,
5
('color: gray', 'material': 'rubber', 'shape': 'cylinder', 'size': 'amall',
'x': 2.5),
color': 'brown, 'material'; 'rubber', 'shape': 'cube', 'size': 'large',
'x': 4.0),
7
coolor' 'yellow', 'material'; 'rubber', 'shape': 'sphere', 'size": 'large',
:x': 1.5),
('cllor: 'brown', 'material: 'metal', 'shape': 'sphere', 'size': 'small',
'x': 3.5},
('color:: 'red', 'material'; 'metal', 'shape': 'cube', 'size': 'small', 'x':
2.0},
('color': 'red', 'material'; 'metal', 'shape': 'cube', 'size': 'large', 'x': 5.0}]}
12
def solve(symbols):
Finds the color the tiny shiny object behind the big dall to the right of the big metallic thing behind the big brown cube.
15
Args:
symbols (dict); A dictionery containing information about the objects in the image.
19
Returns:
20
str: The color of the object.
objects ("obols("objects)
24
1. Pend the big brown cube big. brown_cubeeeeeoeoooooboobooobbee = next((obj for obj in objects if obj [bsapee""" == "cube" and obj [ooloor"]] == "brown" and obj [" == "large"), None)
28
2. Find the big metallic thing (red cube) to the reght of the big brown cube hig_metallic_the thiigggttnigg = next( for obj in objects if obj shappe" == "cube" and obj ["cloor]] == "red" and obj ["size]] == "large" and obj ["x"] big.browm_cuml cube ["x"]), None)
30
3. Find the closest big ball closest_bie baaest_bigbball = min((obj for obj in objects if obj ["shape"] = "sphere" and obj["size"] "large"), key=lambda obj: (bbj big.mettallic__hhnn[=""""
33
4. Pend the tiny shiny object (gold sphere) behind the big ball seayy_shiy_otte next ((oj for obj in objects [bh["eha -- "sphere"
and obj ["materiaa"] "metal" and obj ["izee"]] "small" and ["x"] closest_bbg..aat ["x"]), None)
return siny_shiny_object "attyy__oooccc"colrr"
Figure B.2: Final symbols and generated program from PIPS for the instance shown Figure The code returns "brown" which is the correct answer.
23

---

Table C.2: Accuracy and non non-trivial-code percentage for o4-mini. Best accuracy per row bolded.
Dataset
CoT
PoT
PoT Non-Trivial (%)
PIPS
PIPS Non-Trivial (%)
Buggy tables
0.275
0.512
85.6%
0.594
96.9%
Temporal sequence
0.325
0.306
92.5%
0,519
96.2%
Dyck languages
0.650
0.637
8.8%
0.606
88.8%
Multistep arithmetic
0.281
0.600
72.5%
0.631
87.5%
Time arithmetic
0.875
0.900
76.2%
0.894
87.5%
Shuffled objects
0.081
0.150
43.1%
0.344
71.2%
Web of lies
0.388
0.344
68.1%
0.525
70.6%
Object counting
0.850
0.812
93.1%
0,900
70.0%
Zebra puzzles
0.150
0.100
62.5%
0.231
68. 1%
Object properties
0.144
0.219
38.8%
0.344
65.6%
Boolean expressions
0.550
0.469
24.4%
0.419
63.7%
Spatial reasoning
0.463
0.506
60.6%
0.550
55.0%
Word sorting
0.806
0.775
46.2%
0.806
53.1%
0mnimath-2
0.812
0.706
56.9%
0.787
29.4%
Movie recommendation
0.819
0.744
10.6%
0.731
18.8%
Omnimath-1
0.925
0.925
78.1%
0.944
15.6%
Boardgame qa
0.688
0.637
10.6%
0.675
13.8%
Hyperbaton
0.206
0.194
34.4%
0.188
13.8%
Omnimath-3
0.556
0.356
36.9%
0.544
11.9%
Omnimath-4
0.662
0.419
31.2%
0.644
6.9%
Clutrr
0.762
0,800
1.2%
0.762
2.5%
Sportqa
0.287
0,256
0.0%
0.287
1.9%
Linguini
0.138
0.175
6.2%
0.138
1.2%
CLEVR
0.769
0.750
6.2%
0.769
0.6%
Causal understanding
0.581
0.550
0.6%
0.581
0.6%
Leaf
0.364
0.455
0.0%
0.364
0.0%
Geometric shapes
0.056
0.119
0.0%
0,087
0.0%
Disambiguation qa
0.562
0.573
0.0%
0.562
0.0%
Sare triples
0.338
0.300
0.0%
0.338
0.0%
Nyec
0.231
0.150
0.0%
0.231
0.0%
Harmonic Mcan
0.304
0.340
0.0%
0.397
0.1%
compared to PoT CoT, but PIPS is overall only 3-4X more expensive than CoT PoT while achieving much greater accuracy.
F Non-Trivial Program Synthesis on Non-Algorithmic Problems
We find that encouraging non-trivial programs for non-algorithmic problems leads to reduced per- formance. For instance, CoT with Gemini-2.0-Flash results in harmonic mean accuracy over all non-algorithmic datasets (as listed in Table A.I] of 0.199 while PoT results in lower value of 06166 and our method without switching results in 0.151. Producing non-trivial programs for non-algorithmic problems which shouldn's it be solved via code in the first place, harms performance. Therefore, a high performing general reasoning system needs to avoid program synthesis in such cases.
G Program Evaluation Criteria
The eight criteria we use to evaluate code within PIPS are included below. The input dependence criteria is meant catch when the program is trivial the proper output criteria catches cases where the program does not output the answer in the correct format, and we also include the symbol extraction issues criteria to find issues during the first step of symbol extraction.
Input dependence: Does the code use the input symbols to compute the answer?
Valid return: Does the code avoid returning None unless it is the correct answer?

---

Table C.3: Accuracy and code percentage for Gemini-2.0-4 2.0--Flshh Best aceuracy per row
bolded.
Dataset
CoT
PoT
PoT Non Mon-Trivial (%)
PIPS
PIPS Non-Trivial (%)
Shuffled objects
0.094
0.025
35.6%
0.537
0,188
98.15 18.1%
Buggy tables
0.019
0.100
99,4%
0.031
0.188
97.5%
Time arithmetic
0.438
0.331
82.5%
0.312
0.475
97.5%
Temporal sequence
0.006
0.006
42.5%
0.006
0.094
96.2%
Multistep arithmetic
0.144
0.037
87.5%
0.087
0.119
90.6%
Dyck languages
0.119
0.081
1.9%
0.106
0.050
90.0%
Boolean expressions
0.294
0.219
65.6%
0.325
0.456
86.2%
Object counting
0.144
0.119
98.1%
0.181
0.281
85.0%
Omnimath-1
0.850
0.838
57.5%
0.844
0.869
84.4%
Word sorting
0.287
0.525
48.8%
0,338
0.556
73.1%
Object properties
0.006
0.062
26.9%
0.125
0.163
71.9%
Spatial reasoning
0.231
0.237
12.5%
0.219
0.231
70.6%
CLEVR
0.637
0.619
26.2%
0.669
0.688
46.2%
Causal understanding
0.537
0.438
1.2%
0.544
0.537
15.6%
Clutrr
0.556
0.588
0.0%
0.662
0.506
13.8%
Linguini
0.144
0.113
1.9%
0.119
0.125
13.8%
Boardgame qa
0.463
0.419
5.0%
0.394
0.463
11.9%
Zebra puzzles
0.300
0.256
73.8%
0.131
0.275
10.0%
Geometric shapes
0.312
0.269
0.6%
0.388
0.300
9.4%
Sportqa
0.200
0.244
0,269
0.194
6.9%
Hyperbaton
0.031
0.019
46.2%
0,031
0.025
5.6%
Weh of lies
0.219
0.206
3.1%
0.188
0.219
2.5%
Movie recommendation
0.581
0.562
0.0%
0.556
0.569
2.5%
Disambiguation qa
0.448
0.417
0.0%
0.479
0.448
1.0%
Leaf
0.602
0.636
0.0%
0.102
0.602
0.0%
Sare triples
0.375
0.369
0.0%
0,344
0.375
0.0%
Nyeс
0.106
0.131
0.0%
0.113
0.106
0.0%
Omnimath-2 2
0.544
0.463
46.9%
0.544
0.544
0.0%
Omnimath-3
0.269
0.194
15.6%
0.275
0.269
0.0%
Omnimath-4
0.312
0.244
16.2%
0.319
0.312
0.0%
Harmonic Mean
0.107
0.115
0.0%
0.134
0.201
0.0%
Proper output: Does the code return (not print) the correct answer in the expected format?
No example usage: Does the code omit example calls or usage?
Simplifiability; Could the solution be implemented in simpler way?
Correctness bugs: Are there any bugs affecting correctness?
Symbol extraction issues: Are there any problems with the extracted input symbols?
Sanity check: Does the output pass a basic sanity check?
H
Switch Analysis
In this section, we go in-depth on the CoT vs. program synthesis switch design. First we discuss some additional evaluations involving evaluating the generalizability of the trained switch as well as evaluating zero-shot switch.
H.1 Switch Ablations
We perform ablations for the switch in PIPS and show the results in Table H.11 First, we show that if there is no calibration data available to train the switch, it can be used in zero-shot manner and still be highly performant. The zero-shot switch uses only the last of the ten questions as the final classifier value that training required.
To validate that training a classifier on any data (even from a different dataset) can still be useful, we perform saave--onedattstttooo evaluation. This involves training the switch all but one dataset
25

---

Table C.4: Accuracy and non-trivial-code percentage for ept-4.1-mmni-2025- Best accuracy per
Tow is bolded.
Dataset
CoT
PoT
PoT Non-Trivial (%)
PIPS
PIPS Non-Trivial (%)
Time arithmetic
0.588
0.706
93.1%
0.463
98.8%
Buggy tables
0.075
0,481
100.0%
0,406
98.1%
Multistep arithmetic
0.275
0.394
86.2%
0.494
96.2%
Dyck languages
0.150
0.175
6.9%
0.506
95.0%
Shuffee objects
0.119
0.256
68.8%
0.294
95.0%
Omnimath-1
0.894
0,875
76.2%
0.875
89.4%
Word sorting
0.681
0.600
73.1%
0.656
85.6%
Object counting
0.263
0.331
66.2%
0.287
83.1%
Temporal sequence
0.250
0.356
96.2%
0.275
82.5%
Boolean expressions
0.294
0.356
11.2%
0,469
79.4%
Spatial reasoning
0.181
0.394
48.1%
0.362
68.1%
Object properties
0.025
0.237
67.5%
0.175
60.0%
Omnimath-2
0.569
0.569
63.1%
0.556
59.4%
Web of lies
0.362
0,300
36.2%
0.219
58.8%
CLEVR
0.719
0.669
8.1%
0.700
53.8%
Zebra puzzles
0.194
0.150
36.2%
0.188
49.4%
Clutrr
0.662
0.562
0.6%
0.613
21.9%
Omnimath-3
0.338
0.244
35.6%
0.325
16.2%
Geometric shapes
0.344
0.294
16.9%
0.319
15.0%
Boardgame qa
0.512
0.500
81.2%
0,519
11.2%
Omnimath-4
0,463
0.312
28.7%
0.431
10.0%
Sportqa
0.169
0.244
2.5%
0,200
9.4%
Hyperbaton
0.087
0.062
4.4%
0,075
7.5%
Causal understanding
0.562
0.562
1.2%
0.550
5.6%
Linguini
0.094
0.144
1.2%
0.094
3.1%
Movie recommendation
0.606
0.475
8.8%
0.594
1.9%
Leaf
0.341
0.409
0.0%
0.341
0.0%
Disambiguation
0.552
0,500
1.0%
0.552
0.0%
Sare triples
0.287
0.331
10.0%
0.287
0.0%
Nyec
0.188
0.150
15.0%
0.188
0.0%
Harmonic Mean
0.211
0.297
0.3%
0.305
0.1%
and then evaluating PIPS over only the left out dataset and averaging performance over all datasets the left one. As shown in Table [..I this also performs nearly well as PIPS where the switch is trained over calibration set of data sampled from all datasets.
H.2 Switch Criteria
The full prompt for the switch is provided in Appendix | but we provide the 10 criteria we use within the prompt below. The criteria for determining an instance should be solved directly via CoT by program synthesis are the following:
Simple formalizability: Likelihood that the solution can be easily expressed as simple, deterministic code.
2. Straightforward executability: Likelihood that a first code attempt runs correctly without debugging.
3. Robust systematic search: Likelihood that systematic code (e.g., brute-force, recursion) reliably solves problem.
4. Manageable state representation: Likelihood that all necessary variables and concepts can be cleanly represented in code.
5. Structured knowledge encoding: Likelihood that required background knowledge can be encoded as rules data.
26

---

Table C.5: Accuracy for Qwen3-235B-A222 over all BBEH tasks. Best accuracy per row is bolded.
Dataset
CoT
PoT
PIPS
Word sorting
0.738
0.688
0.706
Dyck languages
0.438
0.200
0.456
Object counting
0.644
0.519
0.613
Object properties
0.319
0.475
0.250
Boardgame qa
0.744
0.838
0.744
Boolean expressions
0.600
0.362
0.631
Buggy tables
0.181
0.362
0.312
Spatial reasoning
0.512
0,506
0.519
Multistep arithmetic
0.550
0.544
0.275
Geometric shapes
0.237
0,200
0.237
Temporal sequence
0.294
0.331
0.350
Disambiguation qu
0.625
0.573
0.625
Causal understanding
0,569
0.456
0.569
Time arithmetic
0.613
0.750
0.700
Web of lies
0.812
0.631
0.812
Sare triples
0.281
0.194
0.281
Hyperbaton
0.287
0.287
0.287
Nyec
0.156
0.163
0.156
Sportqa
0,256
0.150
0.256
Linguini
0.175
0.150
0.175
Movie recommendation
0.738
0.719
0.738
Shuffled objects
0.144
0.056
0.569
Zebra puzzles
0.700
0.569
0.700
Harmonic Mean
0.355
0.289
0.386
Table C.6: Harmonic Mean Accuracy (All Datasets)
Method
gpt-4. -mmii
Gemini-22 Flash
o4-mini
CoT 0.211
0.107
0.304
PoT
0.297
0.115
0.340
PIPS 0.305
0,201
0.397
CI
0.000
0.134
0.000
6. Hallucination risk reduction: Likelihood that code avoids fabricated steps better than chain- of thougtt reasoning.
7. Arithmetic and data processing advantage: Likelihood that code handles arithmetic or data
processing more reliably.
8. Branching and case handling advantage: Likelihood that code handles special cases or branching logic more systematically.
9. Algorithmic reliability over heuristics: Likelihood that deterministic algorithm outperforms intuitive reasoning.
10. Overall comparative success: Likelihood that code yields a more reliable solution than chhin-of-thought reasoning.
Our full prompt asks the LLM itself to quantify each of these criteria and then we build a simple logistic classifier based on the LLM'' own judgements to determine when use program synthesis.
H.3 Examples of Switch Decisions
We show two questions from BBEH Word Sorting in Figure H.3 and the corresponding switch decisions for the different models. We also show a question from Omnimath-2 in Figure H.4 where the different CoT//ynthesis switch decisions made for different models.
27

---

Table C.7: Harmonic Mean Accuracy (Algorithmic Datasets)
Method
gpt-4.1-mini Gemini-2.0-Flasi
04-mini
CoT 0.187
0.079
0.339
PoT 0.357
0.094
0,389
PIPS 0.369
0.217
0.548
CI
0.112
Table C.8: Harmonic Mean Accuracy (Non-A Noon-Aloriihhmic Datasets)
Method
gpt-4.1-mini Gemini-2.0-FN
o4-mini
CoT
0.254
0.199
0.267
PoT
0.244
0.166
0,291
PIPS
0.248
0.184
0.292
CI
0.181
H.4 Question Analysis
We include the logistic regression weights for each of the ten questions in Appendix H.2 in Table H. The most important questions for the switch actually vary significantly between models. For Gemini 2.0-Flash, question and are the most important while for GPT-4.1-min it is question 8 and Finally, for o4-mini, questions 2 and are the most important. Interestingly, we see that questions 5, and 8 which are important for the non-reasoning models are related to the ability of the model to produce error-free code and avoid tedious steps using code while the reasoning model relies most on the criteria which concerns traditional problem algorithmicity rather than model capability.
I Prompts
All prompts used our evaluation and method are included below.
The prompt used to create the LLM-based classifier for question algorithmicity is the following.
Algorithmic Question Evaluation
You will deternine whether
target question be definitively solved by writing Python progran (algorithnic) or if it necessitates another form e Pythen solution nay import standard
reasoning (oon algorithni)) libraries, but cannot simply invoke external services, APIs, or LLKs. If the input containa inages, an algorithnic solution may use information nsnually extracted vithout needing interpret the inage itself.
Evaluate target quastion carefully against the folloxing criteria. Ansver each sub question rigorously with binary response (1 for yes, for no), ensuring high threshold cortainty:
1. Does the problen have explicitly defined imputs and outputs, such that alwaye yield identical outputs?
identical
2. Are there explicit, clearly stated rules, formulas, algorithns, or knovn e0 solving this problen?
daterministic procedures available
3. Does solving this problem strictly require exact conputation (no approxinations, intuitica, or interpretation)?
4. Can this problen structured computational terus vithout ambiguity?
fully formalized in clear mathematical, logical,
Can the solution nethod be deconposed into finite, clear, and unanbiguous sequence of computational staps?
universally recognized
objective standard veritying
correctnese of the solution?
solving problen inherently
repetitive
e
computations clearly suitable for autonation?
Are the inputs structured, quantifiable, and inherently suited to algorithnice manipulation?
Boes this problen clearly natch or clesely resenble a known, standardized e conputational problen type?
28

---

Table D.9: Harmonic mean accuracy computed over BBEH tasks for additional agentic baselines compared to PIPS on Gemini-2, 2.0-Flash. The highest accuracy is bolded.
Method
HMean Accuracy
PoT
0.095
PoT-retriee
0.098
CodeAct
0,040
BoT
0.027
PIPS
0.171
Table E. 10: Comparison of average token usage and cost across methods.
Method
Avg. Input Tokens
Avg. Output Tokens
Cost (USD)
PoT
1,115.96
1,333.98
$0.0006
CoT
1,099.77
1,475.87
$0.0007
CodeAct
80, 13.997.92
4,023.36
$0.0096
Buffer of Thoughts
340,927.19
123,655.35
$0.0835
PIPS
11,839.09
2,805.78
$0.0023
10. Is absolute correctness required (1.a,, no nargin for arror or subjective e interpretation)?
After thoroughly reasoning through these aub aub-queationa, append final determination the 11th element:
Dutput 1 if and only if all or zearly all (at least out of 10) ansvers are clearly indicating the problen definitively algorithmic.
0therzise, outpat 0, indicating the problan requires non non-atgorithmic reaseninge
IMPORTANT:
Before providing the binary list, explicitly
through each criterien carefully and thoroughly, clearly justifying your decisions. If uncertain anbiguous about criterion, default 0.
Provide your final ansver explicitly as an 11-element binary 1ist (ten ansvers- determination).
plus
Under no circumatances should attempt to anaver the actual target question
itself.
TARGET QUESTION:
The prompt used to extract the ten criteria for building our instance-level CoT or program synthesis switch is provided next.
CoT Synthesis Switch Criteria
You will salf rellart to eatimate whether are more lizely to correctly selver> given target questien by writing executable Python code or by using chsin-of-thoughe Ccaturel-languse reasoning.
INPORTANT:**
This is hypothetical evaluation.
attempt ansver, solve, code, or reason through target question ,x
Instead, you nust reflect carefully and conservatively on your expected ability if you
attempt solving the question through either nethod.
Solution Expectationa:
You may assune standard library nodules are alloved for code.
services, APIs, databases, or The code nust be self-contained and executable without internet access. Chain thoughht reasoning maet be clear, logically sound, and internslly e verifiable without external tools.
may
CRITICAL *UIDANCE:**
29

---

Table H.11: Ablations for the switch in PIPS compared using harmonic mean accuracy over all 30 datasets. The ZS-Switch uses only the model output from the final of the ten criteria as the final switch decision the leave-one-out (I.O)) setting trains the switch over but one dataset and then evaluates on the left out dataset and averages over all datasets being the left out one.
Models
PIPS w. ZS-Switch
PIPS w. LOO
PIPS
o4-mini
0.389
0.393
0.397
Gemini-22.-Flassh
0.199
0.180
0.208
GPT--41-mini
0.259
0.302
0.305
Q1
You are expert in word sorting. You will be provided with words the steps in form thoughts, arrange them alphahetical order. Your job is to identily mistake reasoning about
first step of the words. This can be misunderstanding the order of the alphabet or getting the werd or letter wrong or missing word entirely. Q: Sort following words alphabeticully: List: eloctron amputate morphism tire scald lawmon put- down fisapond expositor yosemite gourmet tramsplant novm stracture protagonist arab agree daisy delta eskimo Thought start by looking the
order
words
the list. The first letter: "electron": "c" (5), "amputate", "a" (1). "morphism": "mi" (13). "tire: "I" (20). "scald":
"s" (19). "lawmen": "I" (12). "puidown":: "p" (16). "fish- pond": "I" (6). "expositor": "e" (5). "yosemite": "y" (25).
"goumnet": "g" (7). "transplant". (20).
(14).
Q2
"structure": 's" (19). "protagonist": "p" (16). "amh": "a"
(I), "agroe": ; (l). "daisy": (4). "delta": "d" (4).
"eskimo": "e" (5).
Consider alphahet whose letters have order the English alphubet, except that and are the last Sort the following
Thought 15: have sorted all the words. The agree amputate arab delta daisy electron expositor eskimo fishpond gourmet lawmen morphism noon protagonis put- down scald structure tire transplant yosemite Q: there mistake in this sequence? Write "No" there are mis- takes, the number N there mistake Thought
alphubet and seporate them with comma: meden, oversimplifiations clonic, chaplin, kennan, postpone, squabble, ipsilatcral, misunderstandings.. canal, modifications, referring. coutterevohulionarees pyridine, cameroon, avalanche, ra- tionalizations, fortran, crachman
Figure H.3: Two questions from the BBEH Word Sorting task where the first question asks for determining which thought in model's CoT is incorrect and the second question asks for sorting list of words. The switch for these problems chooses answer QI with CoT for all models while answer Q2 with program synthesis for all models.
**Be cautious, not optimistic.*
Overestinating your capabilities will lead choosing nethod you cannot auccesafully complete.
you any uncertainty, complexity, anbiguity, your probability accordingly.
**Assme that even small mistakes cause failure* writing
ressening through complex taske.
+*Use conservative estimates If unsure betueen
options, exprefer loser probabilities rather than guessing high+s,
Here are the self roflectionn sub questions must ansver bypothetically:
Sinple Formelizabilityer +hat the probability that the full solution can be easily and diractly expressed as simple, detorninistic code, vithoutes needing complex tranafornations deep insight?*
sfrregggtforraard Executability
probability that firet attempt at vriting code would execute correctly vithout needing debugging, even problem
or complex aspacts?
Robuut Systematic Search*x *What is the probability that coding a systematic nethod (like brute search recuraion) reliably
30

---

Q1
A collection of 10000 points is formed by picking each point uniformly at random inside circle of radius 1. Let V be the expected number of points S which are vertices of containing every point of S.) Estimate N.
of the S. (The hull smallest convex polygon
Figure H.4:
A question from Omnimath-2 where both Gemini-2.0-Flash and GPT-4. 1-mini switch to CoT answer while o4-mini chooses program synthesis.
Table H.12: Logistic regression coefficients for the switch for each of the three models.
Model
Q1
Q2
Q3
Q4
Q5
Q6
Q7
Q8
Q9
Q10
Gemini-2.0-Flaa
0.14
0.03
0.12
0.15
-0.21
0.18
-0.09
0.03
0.10
gpt-4.1
0.40
0.42
0.20
0.28
0.22
0.15
-0.02
0.01
0.21
0.21
04-mini
0.22
0.04
0.16
0.24
0.27
-0.05
0.12
0.35
0.18
0.24
find correct anseer, edge-case errora7*
missing constraints introducing
Manageable State Representation"" What the probability that all intermediate concepts, variables, and conditions can be simply and explicitly represented state tracking?*
requiring difficult error error-proct prone
**Structured Knovledge Encodings* What is the probability that all required background knowledgo can be neatly encoded in code (e.g., as rulese formulas, data), rather than needing flexible, intuitive understandinge- batter suited to reasoning?*
s#Balucciattinn Risk Reduction** what is the probability that code execution would more reliably avoid fabricated stepa uncarranted e assumptions compared of ressoning?4
**Arithnetic Data Procassing Advantage** *What the probability that the problan requirea extensive or arror-prone arithmatic/data handling that could perform perfectly, fumble?
chain -hhoughht zould likely
BBanchiing and Case Bandling Advantagess What is the probability that the solution involves many branching conditions, special cases, or exceptions e> ohain-of-thoupe
that code handle systenatically
overlook?*
Algorittiiic Reliability
probability folloving daterministic algorithn in code sould reach the correct ansuer more reliably than relying on intuitive or heuristic ofain-of-thougl +
Neuristica
reasening?*
**0verall comparative Success** <Considering probability that code will ultimately produce correct solution more + reliably
-hougghh reasoning for quastion?*
After thoroughly reasoning through each criterion:
Output a aingle list of 10 probability scores (each between and 1) as your e FINAL ANSWER,
Scores 1-10 correspond to the ten sub sub-questione above.
Additionnsl Instructions:s
Explicitly reason through each criterion carefully before giving probabilitye
If uncertain or if the problem seems complex, favor lozer probabilities to - reflect difficulty.
Make sure to put only the list after FINAL ANSWER.
**Under no circunstances should you write, aketch, paeudocode, or attempt any the solutien iteelf during this reflection *4
TARGET QUESTION:
The prompt for generating the first program with PIPS in iteration one is the following.
31

---

PIPS Code Generator (Iteration
You will be given question and you must ansver it extracting relevant syabole in J808 format and then sriting Python progran to calculate the final
You MUST alvays extensively before outputting any symbols code.
keep going
problen
Workflov
## Problen Solving Steps
Firat relevant information fran input JSON. represent
the relevant information in as nuch of structured format as poasible to help further rensoning/procesttng Using the information extracted, determine reasonable approach solving the problen using code, such that executing the code will return the final
3. Write a Python progran to calculate and return the final ansver. lse commantac>
code The JSON nust be enclosed in a narıdovn code block and the Python function must separate markdoun code black single input called "aymbole" representing the JS0X information extracted. "_.,ssi___" statement and you can assune
explain
main() function.
"solve" and accept
Do not include any 'if __neme..
the JSDN will be loaded into the variable called "synbols" The Python code should not juat return the anaver or parform all reasoning in e
the
and instead leverage
itself perforn the reasoning.
Be careful that the code returne the answer as expected by the question, for instance, ,
multiple choice, the choice described in the question.
question
Be sure to always output a J80H cade block and a Python code block.
The prompt used to generate subsequent code solutions with PIPS by leveraging the evaluator output is shown below.
PIPS Code Generator (Iteration > 0)
Please fix isauea with code symbols or output "FINISHED".
The following is the result of evalusting the above code with the extracted + symbols.
Betura value: (output) Standard output: {stdout)
Exceptions: (arr]
The folloving is the sunmary issues found with the code or the extracted e> syabole by model:
{chacker_outpat)
If there any issues which inpact the correctness of the output code shich does nat hare the issues. Befere outputring any code, problen and If stuck, try outputting different code to solve the problen in different way. may also revise synbols in JSON code block. Only include information in the JSOX which is present in the originsl input to keep the code grounded in the specific + problem. Sone examples of symbol revisions certain symbols, providing further granularity, and adding information e originally missed.
please
plan
issuee.
extracted aymbola.
this, output
revised
changing the
of
If avorything is correct, output the word "FIXISHED" and nothing else.
Finally, the prompt for the code evaluator is shown below.
32

---

PIPS Evaluator
will given question of the code for solving the problem.
and you must judge guality
Look for any the following issues in the cade:
The code ahould be input dapendent, meaning it should use the input aymbols to OK the i.e. the reasoning itself be hardcoded, like a decision tree where the are hardcoded).
compute the
apecialized the input
The code ahould not return None unless "None" is the corract anaver.
The code should return the anever, not just print it. the question aake fore multiple choice ansxer, the cade should in the question. There should
the choice described
any exauple ussge
If there is simpler bugs
to solve the problem, please describe it. impact correctness
there any ansver, please deacribe then.
If there are any issues with the extracted symbole, please describe then as separate If it ls possible to sanity check the output of the code, please do so and - output and
issues the code.
any obvious issues could be fixed to avoid these issues.
describe
After anelyzing the code in depth, output concrete and concise summary of the issues that are present, do not include say code exauples. Please order the by impact The following are extracted syabols from the question in J8ON forust folloved by- takes
Python pregran computes the answer. Json (joon_str)
argunent called "syubols" and
python (code_atr)
Code execution result:
{output)
Standard output: (stdout)
Exceptions: (err)
Output and concise summary only the issues that present, not include any cade examples.
J Hyperparameters
For all models we used a temperature of For PIPS, we used a maximum of iterations all models.
K
Compute Resources
For most experiments rely API model access. All experiments cost $300 for Gemini-2.0-Flan S70 GPT-4.1-mint. and $700 for o4-mini (medium). Other experiments were run on a server with 96 Intel(R) Xeon(R) Gold 5318Y CPUs @ 2.10HHz with ITB of system RAM. The server also had 10x NVIDIA A100 80GB GPUs which were only used for local testing of open-weights models.
L Broader Impacts
PIPS offers significant potential benefits, including enhanced AI reliability, trust, transparency, and democratization of advanced problem-solving. However, like most systems built from powerful foundation models, it also presents important considerations. These include the potential for bias propagation from underlying models, challenges in ensuring the complexity and robustness dy- namically generated programs, and concerns regarding misuse. Continued research and development
33

---

must prioritize robust safeguards, fairness, transparency, and responsible deployment practices to harness the benefits while mitigating these potential negative impacts.
M Connection Transductive Learning
mistance-wise Program Synthesis can be connected to transductive learning [46] where function is learned to map from specific function inputs to specific outputs. The general philosophy is that one should not try to solve the general problem when the specific case is all one needs.
the space symbolic input and ) is the output space, and an unlabeled test sample x: E RR Our goal is to find program p: R > Y/ which has low error on the given sample, so p(x) = y. contrast, inductive program synthesis tries to find program p which generalizes, so it should achieve low error on samples from the same distribution as Dr.. To perform transductive program synthesis, we rely on minimizing an auxiliary "regularization" term, Q, over the test sample, representing form of test-time computation:
We are given labeled training set D { y/1 ) R x y where
ý arg min
((((x)) v)) + aip 21,,... Fem 2)
m
The regularization term can be implemented using probabilistic priors (e.g. the likelihood under some language model) or more complex heuristics involving static/dynamic code analysis. With powerful foundation models that perform zero-shot inference, even perform this type of learning without any training set.
Neuro-symbolic Instance-level Synthesis The above problem definition is specifically for prob- lems formulated for program synthesis, meaning the inputs are expressed in symbolic form. Can we apply such a method for problems expressed in natural language or even using images? To convert general problems into form which is conducive to program execution, we use a Neuro-Symbolic framework, specifically Prompt-Symbolic approach.
We now assume our samples come from an arbitrary raw input space, such as natural language, images, and other modalities. Using the traditional neuro-symbolic framework, first extract symbols from the raw input and then pass these symbols to a program. Let C' + R be a mapping from raw data symbols. Now we adapt the above formalism the following:
p. Ć = arg min
Σ ((((C(a))) vi) + 2CC, P,C.P, Im, x)
P.C
Intuitively, we find data symbols mapping Ö and program which perform well on a training set (if one available) and minimize the loss 52 over the given test samples. Notably, the program and raw data symbol mapping do need be general, they should be specialized for the test samples. In practice, the raw data to symbol mapping is often form of semantic parsing, which can be done through zero-shot prompting of foundation models, so the data symbol mapping is not modified on an instance-level.
34


Reviews:
[{"review_id": "fiGvwCR84l", "reviewer": "Reviewer_oWeE", "summary": "This paper introduces Per-Instance Program Synthesis (PIPS), a novel method that addresses the challenges of using large language models (LLMs) to generate and execute programs for complex reasoning tasks. The authors identify three key limitations of existing approaches like Program of Thought (PoT): the difficulty of deciding when to use program synthesis versus direct inference, the lack of task specifications to guide program generation, and the challenge of interfacing programs with unstructured input data. PIPS addresses these issues through an instance-level confidence metric that dynamically chooses between program synthesis and Chain of Thought reasoning, an iterative refinement process using structural feedback to improve program quality without requiring explicit test cases, and explicit symbolic extraction that converts unstructured input into structured program inputs before code generation. Experiments across 30 benchmarks including Big Bench Extra Hard tasks, visual reasoning, and mathematical problems using three frontier LLMs (Gemini-2.0-Flash, GPT-4.1-mini, and o4-mini) demonstrate that PIPS achieves up to 8.6% absolute improvement in harmonic mean accuracy over PoT and reduces undesirable program generations by 65.1%, while maintaining comparable performance to Chain of Thought on non-algorithmic tasks.", "questions": "- Could the authors try making a more comprehensive literature review to polish the related work section?", "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": "## Strengths\n\n+ This paper proposes a simple yet effective approach to enable the flexible reasoning of LLMs, considering both programming and CoT, and deciding case by case\n+ The paper addresses three fundamental challenges in per-instance program synthesis that have not been systematically tackled before: the open-domain nature of deciding when to use synthesis vs. direct inference, the lack of task specifications for program search, and the challenge of interfacing programs with unstructured data.\n+ The paper demonstrates rigorous experimental methodology by evaluating PIPS across 30 diverse benchmarks, which was specifically designed to test advanced reasoning capabilities where current LLMs struggle. The evaluation spans three frontier LLMs (Gemini-2.0-Flash, GPT-4.1-mini, and o4-mini) and shows consistent improvements, with up to 8.6% absolute improvement in harmonic mean accuracy over PoT and a significant reduction in undesirable program generations by 65.1%.\n\n## Weaknesses\n\nOverall, I appreciate this paper's simple yet effective approach, and I am very positive regarding its acceptance. \n\nOne weakness that bothers me a bit is that the paper misses the discussion regarding a few related works -- some of them might not be closely related to be used as baselines, but are worth discussing. For example, ViperGPT [1] implements a prominent framework for visual inference via Python execution, addresses remarkably similar problems by using LLMs to compose vision-and-language models into subroutines and generating Python code for visual reasoning tasks. PropTest [2] has also explored improving visual programming through property-based testing. I would suggest that the author should do a more comprehensive literature review over the related works, and update its related work section.\n\n[1] Dídac Surís, Sachit Menon, Carl Vondrick. ViperGPT: Visual Inference via Python Execution for Reasoning.\n\n[2] Jaywon Koo, Ziyan Yang, Paola Cascante-Bonilla, Baishakhi Ray, Vicente Ordonez. PropTest: Automatic Property Testing for Improved Visual Programming", "was_revised": true, "final_justification": "The authors' response mostly addresses my concern. I remain positive about this paper and I keep my score to show my support for its acceptance.", "rebuttal": "We thank the reviewer for their thoughtful comments and for recognizing the effectiveness and originality of our work. Following the reviewer’s comment about improving the breadth of our related work section, and the pointer to two relevant papers, we have revised the related work and believe it is much improved. We will add the following to the current related work section:\n\n> Approaches which prompt an LLM to produce code to solve a problem have been used in several domains beyond math and text-based reasoning questions. ViperGPT and followup work tackle visual question answering problems [1, 2], Voyager applies to game playing [3], and Code as Policies focusses on the application of robot control [4]. Recently, general systems such as CodeAct [5] and OpenCodeInterpreter [6] have been proposed for solving problems via code generation similar to the previously mentioned solutions for each task.\n>\n> [1] Surís, Dídac, Sachit Menon, and Carl Vondrick. \"Vipergpt: Visual inference via python execution for reasoning.\" ICCV 2023.\n>\n> [2] Koo, Jaywon, et al. \"PropTest: Automatic Property Testing for Improved Visual Programming.\" EMNLP Findings 2024.\n>\n> [3] Wang, Guanzhi, et al. \"Voyager: An Open-Ended Embodied Agent with Large Language Models.\" TMLR 2024.\n>\n> [4] Liang, Jacky, et al. \"Code as Policies: Language Model Programs for Embodied Control.\" ICRA 2023.\n>\n> [5] Wang, Xingyao, et al. \"Executable code actions elicit better llm agents.\" ICML 2024.\n>\n> [6] Zheng, Tianyu, et al. \"OpenCodeInterpreter: Integrating Code Generation with Execution and Refinement.\" ACL Findings 2024.\n\nWe then additionally include CodeAct as a baseline and results for Gemini 2.0 Flash are included in the response to reviewer ki2H. We see that CodeAct significantly underperforms even PoT. The full results will be included in the camera ready version."}, {"review_id": "eUQJcHJ9iY", "reviewer": "Reviewer_ki2H", "summary": "This paper introduces Per-Instance Program Synthesis (PIPS), a method designed to improve the multi-step reasoning abilities of large language models (LLMs). PIPS addresses the shortcomings of existing approaches like Program of Thought (PoT), which often produce undesirable solutions.The core of PIPS is to generate and refine programs at the individual instance level, guided by structural feedback rather than explicit test cases. The method includes two key innovations: A confidence metric that dynamically decides whether to solve a problem via program synthesis or direct inference on a per-instance basis;An iterative synthesis loop that uses an evaluator to check for structural flaws like hardcoded answers, type errors, or syntax issues, providing feedback to improve the program.", "questions": "1. The method’s upfront, binary choice between CoT and synthesis differs from  tool-use agent that dynamically interleave reasoning steps with tool execution. What is the fundamental advantage of this static choice over a dynamic approach, and should the baselines have included comparisons to such agents to better situate the contributions of PIPS?\n\n   - Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., & Cao, Y. (2023). ReAct: Synergizing Reasoning and Acting in Language Models. *International Conference on Learning Representations*.\n\n   - Paranjape, B., Korbak, F., Hall, C., Santoro, A., Lynch, C., & Hjelm, D. (2023). ART: Automatic multi-step reasoning and tool-use for large language models. *arXiv preprint arXiv:2303.09014*.\n\n2. Could the authors provide a detailed analysis of the computational overhead? Specifically, what is the average increase in end-to-end latency or total token consumption for PIPS when compared directly against the PoT baseline on the algorithmic tasks?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strengths\n\n- **Dynamic Adaptability**： By using a confidence metric to distinguish between tasks, PIPS selects the most appropriate solution path, which helps avoid wasting computational resources on problems not suited for program synthesis.\n\n### Weaknesses\n\n- **Questionable Generality**: The method's general applicability is uncertain, as its performance improvement on certain models, such as GPT-4.1-mini, is marginal.\n- **Limited Feedback Mechanism**: The feedback mechanism is limited because it primarily focuses on surface-level structural issues like syntax errors and hardcoded answers. It may not be able to detect or correct deeper logical errors within a program's algorithm.\n- **Computational Overhead**: Compared to single-pass methods like PoT, the iterative generation and evaluation process in PIPS results in higher computational costs and increased latency.", "was_revised": true, "final_justification": "The author's supplementary experiments on multiple models (including open source models) and method overhead dispelled my concerns about the robustness of the method.", "rebuttal": "We thank the reviewer for the thoughtful comments. We address the reviewer’s specific concerns in detail below.\n\n## Method Generality\n\nOur method results in only a 0.8% absolute increase in harmonic mean accuracy for GPT 4.1-mini, but this is our worst result out of many strong results across other models. We also emphasize that we follow the setting from the BBEH authors of using the harmonic mean accuracy over tasks which is a particularly challenging metric as it downweights easier tasks and significantly upweights the importance of the hard tasks. Even though harmonic mean accuracy improvement is low for GPT 4.1-mini, we see a 11.3% absolute improvement over PoT on Boolean Expressions and a 33.1% absolute improvement over PoT on Dyck Languages.\n\nIn addition, we are adding an open-weights model, Qwen3-235B-A22B-Instruct-2507. We report preliminary results over all of the BBEH tasks for this model and will include the complete results in the camera ready version. We observe a 1.3% absolute improvement in harmonic mean accuracy.\n\n| Dataset              | PoT   | CoT   | PIPS  |\n|----------------------|-------|-------|-------|\n| Word sorting         | 0.669 | 0.750 | 0.750 |\n| Dyck languages       | 0.169 | 0.419 | 0.456 |\n| Object counting      | 0.544 | 0.656 | 0.644 |\n| Object properties    | 0.475 | 0.338 | 0.331 |\n| Boardgame qa         | 0.844 | 0.738 | 0.738 |\n| Boolean expressions  | 0.325 | 0.600 | 0.594 |\n| Buggy tables         | 0.400 | 0.169 | 0.231 |\n| Spatial reasoning    | 0.550 | 0.525 | 0.525 |\n| Multistep arithmetic | 0.544 | 0.531 | 0.494 |\n| Geometric shapes     | 0.175 | 0.244 | 0.244 |\n| Temporal sequence    | 0.338 | 0.294 | 0.300 |\n| Causal understanding | 0.450 | 0.606 | 0.606 |\n| Time arithmetic      | 0.762 | 0.569 | 0.738 |\n| Web of lies          | 0.613 | 0.831 | 0.831 |\n| Sarc triples         | 0.181 | 0.287 | 0.287 |\n| Hyperbaton           | 0.256 | 0.287 | 0.287 |\n| Nycc                 | 0.169 | 0.131 | 0.131 |\n| Sportqa              | 0.163 | 0.281 | 0.281 |\n| Linguini             | 0.144 | 0.181 | 0.181 |\n| Movie recommendation | 0.750 | 0.725 | 0.725 |\n| Zebra puzzles        | 0.581 | 0.706 | 0.706 |\n| Harmonic Mean        | 0.326 | 0.366 | 0.379 |\n\n\n\nWe believe PIPS has a low effectiveness with GPT 4.1-mini because the model struggles at revising generated code based on the structural feedback we provide, due to its overall weak performance. For o4-mini, a model which performs better overall in terms of the baselines, we see that PIPS improves over PoT performance by 5.7% absolute harmonic mean accuracy. This trend is repeated for Qwen3-235B-A22B-Instruct-2507, which is also more performant in terms of baselines.\n\n\n\n## Upfront Choice Between CoT and Synthesis\n\nWe decided to use an upfront choice between CoT and synthesis since we observed that most of the reasoning problems we were considering were solvable directly by code when the problem was “algorithmic”. For these cases, the problem was that the model could determine that the problem was solvable via program synthesis, but when prompted to generate the code, it failed to produce well-formed code. Since this was the case, even for a system that can interleave code and CoT based reasoning, the problem with code synthesis would remain.\n\nA natural generalization of PIPS is to enable a dynamic problem-solving approach, perhaps where some subproblems are solved by synthesis and others by CoT. We believe this is an interesting future direction, but we did not find it characteristic of the BBEH problems we studied.\n\n## Agentic / Iterative Baselines\n\nWe note that the paper included an agentic baseline, the Gemini Code Interpreter, which we describe on line 188. To provide another agentic baseline, we have additionally evaluated the smolagents library implementation of a CodeAct [1] agent and we include the results below for Gemini-2.0-flash.\n\n| Dataset              | CodeAct (gemini-2.0-flash) |\n|----------------------|---------------------|\n| Word sorting         | 0.525               |\n| Dyck languages       | 0.044               |\n| Object counting      | 0.000               |\n| Object properties    | 0.006               |\n| Boardgame qa         | 0.325               |\n| Boolean expressions  | 0.256               |\n| Buggy tables         | 0.025               |\n| Spatial reasoning    | 0.287               |\n| Multistep arithmetic | 0.000               |\n| Geometric shapes     | 0.369               |\n| Temporal sequence    | 0.000               |\n| Disambiguation qa    | 0.469               |\n| Causal understanding | 0.512               |\n| Time arithmetic      | 0.256               |\n| Web of lies          | 0.206               |\n| Sarc triples         | 0.331               |\n| Hyperbaton           | 0.025               |\n| Nycc                 | 0.106               |\n| Sportqa              | 0.212               |\n| Linguini             | 0.125               |\n| Movie recommendation | 0.388               |\n| Shuffled objects     | 0.006               |\n| Zebra puzzles        | 0.031               |\n| Harmonic Mean        | 0.040               |\n\nWe find that CodeAct performs poorly due to several reasons. One issue is from multiple choice questions where the agent does not respond with a letter even when we explicitly give instructions for answer formatting. The other big problem can be seen for object counting and shuffled objects (two highly algorithmic tasks) where CodeAct performs very poorly due to approaching the problem by performing each low level computation with the Python interpreter and everything else with CoT rather than solving the high level problem with code. We will include CodeAct results for all models for the camera ready version.\n\nWe additionally include results for the Buffer of Thoughts [2] method over BBEH as suggested by another reviewer. This method uses other test problems from the same task to help with determining an effective method for solving other problems of the task. Overall, we find that this is highly ineffective for BBEH problems.\n\n| Dataset              | Buffer of Thoughts (gemini-2.0-flash) |\n|----------------------|--------------------|\n| Word sorting         | 0.463              |\n| Dyck languages       | 0.056              |\n| Object counting      | 0.006              |\n| Object properties    | 0.000              |\n| Boardgame qa         | 0.275              |\n| Boolean expressions  | 0.031              |\n| Buggy tables         | 0.000              |\n| Spatial reasoning    | 0.113              |\n| Multistep arithmetic | 0.000              |\n| Geometric shapes     | 0.006              |\n| Temporal sequence    | 0.000              |\n| Causal understanding | 0.362              |\n| Time arithmetic      | 0.100              |\n| Web of lies          | 0.087              |\n| Sarc triples         | 0.194              |\n| Hyperbaton           | 0.013              |\n| Nycc                 | 0.019              |\n| Sportqa              | 0.125              |\n| Linguini             | 0.006              |\n| Movie recommendation | 0.013              |\n| Zebra puzzles        | 0.069              |\n| Harmonic Mean        | 0.026              |\n\n[1] Wang, Xingyao, et al. \"Executable code actions elicit better llm agents, 2024.\" ICML 2024.\n[2] Buffer of Thoughts: Thought-Augmented Reasoning with Large Language Models. NeurIPS 2024.\n\n##  Limited Feedback Mechanism\n\nWhen we studied the failure modes of current models when generating code for solving reasoning problems, we found that the overwhelming majority of problems came from failing to generate code and the model resorting to textual reasoning. Since this was the most common issue prior to our work, our primary objective in this paper was to address this problem with a simple, but general framework. With this issue now addressed, we agree with the reviewer that more sophisticated forms of feedback will be necessary to address deeper problems such as logical errors now that the code is well-formed, and we are excited about future work in this direction.\n\n## Analysis of Computational Overhead\n\nWe include the average input and output tokens and the average cost for all methods below using Gemini 2.0 Flash with costs determined based on current Gemini API costs. We find that the iterative approaches (CodeAct and Buffer of Thoughts) increase cost over 10X compared to PoT or CoT, but PIPS is overall only 3-4X more expensive than CoT or PoT while achieving much greater accuracy.\n\n| Method    | Avg. Input Tokens | Avg. Output Tokens | Cost (USD) |\n|-----------|-------------------|--------------------|------------|\n| PoT       | 1115.96           | 1333.98            | $0.0006    |\n| CoT       | 1099.77           | 1475.87            | $0.0007    |\n| CodeAct   | 80137.92          | 4023.36            | $0.0096    |\n| Buffer of Thoughts | 340927.19 | 123655.35 | $ 0.0835 |\n| PIPS      | 11839.09          | 2805.78            | $0.0023    |"}, {"review_id": "CcIU70ZNvm", "reviewer": "Reviewer_JESL", "summary": "The paper proposes Per-Instance Program Synthesis (PIPS), a test-time reasoning framework that decides, for each input, based on an instance-level confidence metric, whether to answer with plain chain-of-thought (CoT) reasoning or to synthesize and iteratively refine a program. Specifically, when code is chosen, the LLM/reasoner generates a symbolic abstraction of the raw input, writes a program that consumes that abstraction, runs it, and receives feedback on syntax, type, hard-coded answers and other failure patterns. Across three  LLMs (Gemini-2.0-Flash, GPT-4.1-mini, o4-mini) and 30 benchmarks (23 BBEH tasks plus CLEVR, Leaf, CLUTTR and four OmniMath tasks) PIPS lifts harmonic-mean accuracy by up to 8.6% over PoT and cuts undesirable programs by 65.1% .", "questions": "Please refer to the weaknesses listed in Strengths And Weaknesses and address all.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n1. The paper clearly articulates three core limitations of instance-level code generation: when to invoke code, absence of formal specifications, and unstructured natural language inputs. The proposed pipeline is well-aligned with these issues.\n2. The approach is evaluated across diverse reasoning domains, such as language, vision-language, relational, and mathematical reasoning tasks, with comprehensive ablations on synthesis iterations, symbolic inputs, and code-switching heuristics.\n3. The authors commit to releasing prompts and compute details. The main paper also includes a section for limitations and societal considerations, demonstrating transparency.\n## Weaknesses\n1. Both conceptually and empirically, authors mainly discuss the proposed approach in comparision with CoT and PoT, overlooking more recent and relevant works such as [1] (which enhances the effectiveness of solving multi-step reasoning problems by using code prompts as intermediate prompts) and [2] (which curates a library of high-level code templates (“thought-templates”) distilled from solved problems; the proposed approach retrieves & instantiates a template, then executes it).\n2. All three LLMs used (o4-mini, Gemini-2.0-Flash, GPT-4.1-mini) are proprietary. The lack of open-source LLMs limits reproducibility and transparency.\n3. Holding out 20% of every task for calibration may inflate reported accuracy and is unrealistic for truly zero-shot settings.\n4. Efficiency aspect remains under-explored. Runtime overhead of iterative synthesis (plus interpreter calls) is not reported; Figure 6 shows accuracy vs iterations but not explicit numbers (e.g., token consumption and runtime).\n5. While the paper acknowledges potential errors in converting inputs to structured symbolic form (e.g., JSON) in Section 3.3, it offers no quantitative assessment of semantic fidelity or its impact on downstream performance.\n6. In Lines 195-196, the authors report that overall, \"a 0.8% absolute improvement over PoT for GPT-4.1-mini\". This improvement is trivial, and raises concerns about the approach’s diminishing returns as models improve. The paper should discuss this issue more explicitly.\n\n[1] When Do Program-of-Thought Works for Reasoning? AAAI 2024.\n\n[2] Buffer of Thoughts: Thought-Augmented Reasoning with Large Language Models. NeurIPS 2024 Spotlight.", "was_revised": true, "final_justification": "The author's additional experiments have addressed my concerns. I am therefore inclined to raise my rating to 4.", "rebuttal": "We thank the reviewer for the thoughtful comments. We address the reviewer’s specific concerns in detail below.\n\n## Baselines\n\nWhile the paper [1] does not present a zero-shot method for LLM reasoning, we have added a comparison with Buffer of Thoughts [2] as suggested by the reviewer. This method uses other test problems from the same task to help with determining an effective method for solving other problems of the task. Overall, we find that this is highly ineffective for BBEH problems, performing even worse than just CoT or PoT alone.\n\n| Dataset              | Buffer of Thoughts (gemini-2.0-flash) |\n|----------------------|--------------------|\n| Word sorting         | 0.463              |\n| Dyck languages       | 0.056              |\n| Object counting      | 0.006              |\n| Object properties    | 0.000              |\n| Boardgame qa         | 0.275              |\n| Boolean expressions  | 0.031              |\n| Buggy tables         | 0.000              |\n| Spatial reasoning    | 0.113              |\n| Multistep arithmetic | 0.000              |\n| Geometric shapes     | 0.006              |\n| Temporal sequence    | 0.000              |\n| Causal understanding | 0.362              |\n| Time arithmetic      | 0.100              |\n| Web of lies          | 0.087              |\n| Sarc triples         | 0.194              |\n| Hyperbaton           | 0.013              |\n| Nycc                 | 0.019              |\n| Sportqa              | 0.125              |\n| Linguini             | 0.006              |\n| Movie recommendation | 0.013              |\n| Zebra puzzles        | 0.069              |\n| Harmonic Mean        | 0.026              |\n\n\nWe note that we also included an agentic baseline in our original submission, the Gemini code interpreter, which we described on line 188. For another agentic baseline, we have included the smolagents implementation of a CodeAct agent, and we provide the results for all BBEH datasets using Gemini 2.0 Flash below. The complete results for all models will be included in the camera ready.\n\n| Dataset              | CodeAct (gemini-2.0-flash) |\n|----------------------|---------------------|\n| Word sorting         | 0.525               |\n| Dyck languages       | 0.044               |\n| Object counting      | 0.000               |\n| Object properties    | 0.006               |\n| Boardgame qa         | 0.325               |\n| Boolean expressions  | 0.256               |\n| Buggy tables         | 0.025               |\n| Spatial reasoning    | 0.287               |\n| Multistep arithmetic | 0.000               |\n| Geometric shapes     | 0.369               |\n| Temporal sequence    | 0.000               |\n| Disambiguation qa    | 0.469               |\n| Causal understanding | 0.512               |\n| Time arithmetic      | 0.256               |\n| Web of lies          | 0.206               |\n| Sarc triples         | 0.331               |\n| Hyperbaton           | 0.025               |\n| Nycc                 | 0.106               |\n| Sportqa              | 0.212               |\n| Linguini             | 0.125               |\n| Movie recommendation | 0.388               |\n| Shuffled objects     | 0.006               |\n| Zebra puzzles        | 0.031               |\n| Harmonic Mean        | 0.040               |\n\n[1] When Do Program-of-Thought Works for Reasoning? AAAI 2024.\n[2] Buffer of Thoughts: Thought-Augmented Reasoning with Large Language Models. NeurIPS 2024 Spotlight.\n\n## LLMs Used\n\nFollowing the reviewer’s suggestion, we have evaluated the Qwen3-235B-A22B-Instruct-2507 model as an open-weights model. We report preliminary results over all of the BBEH tasks for this model and will include the complete results in the camera ready version. We observe a 1.3% absolute improvement in harmonic mean accuracy.\n\n| Dataset              | PoT   | CoT   | PIPS  |\n|----------------------|-------|-------|-------|\n| Word sorting         | 0.669 | 0.750 | 0.750 |\n| Dyck languages       | 0.169 | 0.419 | 0.456 |\n| Object counting      | 0.544 | 0.656 | 0.644 |\n| Object properties    | 0.475 | 0.338 | 0.331 |\n| Boardgame qa         | 0.844 | 0.738 | 0.738 |\n| Boolean expressions  | 0.325 | 0.600 | 0.594 |\n| Buggy tables         | 0.400 | 0.169 | 0.231 |\n| Spatial reasoning    | 0.550 | 0.525 | 0.525 |\n| Multistep arithmetic | 0.544 | 0.531 | 0.494 |\n| Geometric shapes     | 0.175 | 0.244 | 0.244 |\n| Temporal sequence    | 0.338 | 0.294 | 0.300 |\n| Causal understanding | 0.450 | 0.606 | 0.606 |\n| Time arithmetic      | 0.762 | 0.569 | 0.738 |\n| Web of lies          | 0.613 | 0.831 | 0.831 |\n| Sarc triples         | 0.181 | 0.287 | 0.287 |\n| Hyperbaton           | 0.256 | 0.287 | 0.287 |\n| Nycc                 | 0.169 | 0.131 | 0.131 |\n| Sportqa              | 0.163 | 0.281 | 0.281 |\n| Linguini             | 0.144 | 0.181 | 0.181 |\n| Movie recommendation | 0.750 | 0.725 | 0.725 |\n| Zebra puzzles        | 0.581 | 0.706 | 0.706 |\n| Harmonic Mean        | 0.326 | 0.366 | 0.379 |\n\n\n## 20% Holdout Set for Calibration\n\nWe thank the reviewer for bringing this up. We agree that for a strict zero-shot setting, the use of a validation set is not very standard. We only use the validation set for the switch and do not use any of the validation samples in any of the prompts or for improving the downstream CoT or synthesis methods. It is possible to implement the switch without any validation samples by just using the value of the tenth question rather than training a classifier to combine all ten questions. This zero-shot switch correctly chooses between CoT and synthesis 60.3% of the time for the problems where the outcome correctness of CoT and synthesis differs. Since choosing the method which performs the best between CoT and synthesis on these problems results in only 51.2% accuracy, this result is much better than both CoT or synthesis alone, but slightly worse than the trained switch which achieves 65% accuracy. We also evaluate a leave-one-out evaluation setting where the switch used on one dataset is only trained on the 20% validation samples from other datasets. This method, called “PIPS w. LOO” shows that the switch generalizes to held out datasets rather than just held out samples.\n\nWe will include results for the setting with a switch implemented without any validation samples in our revised paper as well as the leave-one-out ablation. The PIPS w. LOO method still outperforms all baselines. For all models except GPT 4.1-mini (which already had the weakest performance), PIPS with a zero-shot switch still significantly outperforms the strongest baselines.\n\n| Models           | PIPS w. ZS Switch | PIPS w. LOO | PIPS  |\n|------------------|-------------------|-------------|-------|\n| o4-mini          | 0.389             | 0.393       | 0.397 |\n| Gemini 2.0 Flash | 0.199             | 0.180       | 0.208 |\n| GPT 4.1-mini     | 0.259             | 0.302       | 0.305 |\n\n## Cost Overhead of PIPS\n\nWe have calculated the average input and output tokens as well as average cost for each baseline method and PIPS for Gemini 2.0 Flash. We find that the iterative approaches (CodeAct and Buffer of Thoughts) increase cost over 10X compared to PoT or CoT, but PIPS is overall only 3-4X more expensive than CoT or PoT while achieving much greater accuracy.\n\n| Method    | Avg. Input Tokens | Avg. Output Tokens | Cost (USD) |\n|-----------|-------------------|--------------------|------------|\n| PoT       | 1115.96           | 1333.98            | $0.0006    |\n| CoT       | 1099.77           | 1475.87            | $0.0007    |\n| CodeAct   | 80137.92          | 4023.36            | $0.0096    |\n| Buffer of Thoughts | 340927.19 | 123655.35 | $ 0.0835 |\n| PIPS      | 11839.09          | 2805.78            | $0.0023    |\n\n## Quantitative Assessment of Semantic Fidelity of Input to Symbolic Mapping\n\nSince our method first abstracts the raw input into a symbolic form, represented as JSON, there may be issues in this raw-to-symbolic mapping, as noted by the reviewer. Our preliminary investigation revealed that the vast majority of problems occur in the code itself (shown in Figure 3) and the model is often very good at the input to symbolic form translation. Now that we have addressed some of the most common problems, we think finer-grained issues should be studied in greater depth in future work, such as carrying out annotation efforts to determine the fidelity of the raw input to symbolic form mapping.\n\n## Low Improvement for GPT 4.1-mini\n\nOur method results in only a 0.8% absolute increase in harmonic mean accuracy for GPT 4.1-mini, but this is our worst result out of many strong results across other models. In addition, we are adding an open-weights model, Qwen3-235B-A22B-Instruct-2507 (results are included above), where we see better results.\n\nWe believe PIPS has a low effectiveness with GPT 4.1-mini because the model struggles at revising generated code based on the structural feedback we provide, due to its overall weak performance. For o4-mini, a model which performs better overall in terms of the baselines, we see that PIPS improves over PoT performance by 5.7% absolute harmonic mean accuracy. Therefore, we still see that stronger models significantly benefit from using PIPS."}, {"review_id": "TcDZhmH6O7", "reviewer": "Reviewer_7yLF", "summary": "This work introduces Per-Instance Program Synthesis (\"PIPS\") which aims to increase accuracy on a variety of reasoning tasks.  Key elements include the detection of whether plain CoT is sufficient, or whether code should be written, with additional quality checks being applied to the code to ensure that it doesn't fall into a number of reasoning traps that the authors identified from other approaches.", "questions": "You state \"our confidence metric allows us to correctly switch between CoT and program synthesis for 65% of cases\" : As noted above, this seems as if it is a fairly weak classifier, somewhat undermining its significance.  Can I confirm that the results for the methods (other than PIPS) were also conducted on the 80% of the benchmark sets that were not held out as calibration data for the logistic classifier (L139) ?\n\nAm I correct in suggesting that the PoT implementation did not allow for code retries/rewrites when there were errors, whereas PIPS was given the opportunity for multiple self-correction loops (as illustrated in Figure 6)?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "One key element of PIPS seems to be the learned logistic classifier over features output by asking the LLM itself about its confidence in its own capabilities at answering the question with/without PoT.  While practical to implement, it doesn't seem as if this classifier achieves good accuracy in its determinations - which begs the question of whether there could be a simple probe (for a model with open weights, of course) that would perform better.\n\nThe investigation of failure modes for the code creation is of practical relevance - with the identification of 'failed structural properties' being a novel twist.  \n\nHowever, it seems that (from a quick look at the provided code) that the PoT implementation does not allow for regeneration/fixing of code errors, whereas PIPS is allowed re-tries.  This means that the PIPS method isn't purely benefiting from the structural property guardrails, but also from the ability to fix simple typo-style errors.  Choosing weak versions of the competitor baselines (as appears to be the case here, please correct me if I didn't find the correct code) isn't a good look.", "was_revised": true, "final_justification": "I'm raising, but fairly reluctantly : The method clearly works, and the experimental work is fine (and improved through the review process).  OTOH, this is still fundamentally a tweak to chose between two styles of model question answering - finessing on an analysis of model errors, rather than adding a new capability into the mix", "rebuttal": "We thank the reviewer for the thoughtful comments. We address the reviewer’s specific concerns in detail below.\n\n## Confidence Metric\n\nFor our confidence-based switch between CoT and code synthesis, the 65% reported accuracy is only over the problems where exactly one of synthesis or CoT gets the correct answer, so this excludes cases where both are correct or both incorrect. Out of these problems where the outcome of CoT and synthesis differ, the best performing method out of the two gets 51.2% accuracy, so 65% accuracy is a significant improvement over both CoT and synthesis. There is still room for improvement in this switch (possibly through probe-based approaches as suggested by the reviewer), but we wanted an approach that would be easy to apply to new models, which to-date often do not provide hidden state access.\n\n## Evaluation of Baselines on 80% Non-Heldout Data\n\nThe reviewer is correct that we evaluated all methods on the 80% of the data that was not included in the heldout set used for calibration.\n\n## Iterative Baselines\n\nThe reviewer is correct that the PoT baseline did not allow for regeneration and fixing of code errors. The original version of PoT and other related methods such as FCoT [1] and PAL [2] also do not reprompt the model if there are execution errors. To address this concern, we re-run PoT with retries.   Addionally, in our experiments, we included the Gemini code interpreter as a baseline which can iteratively write and debug code, as mentioned on line 188. For another such baseline, we have added the smolagents library implementation of CodeAct [3], which we find performs poorly on BBEH with gemini-2.0-flash. We will include the CodeAct results for all models in the camera ready version as well as Buffer of Thoughts (a baseline suggested by another reviewer).\n\n\n| Dataset              | CodeAct (gemini-2.0-flash) |\n|----------------------|---------------------|\n| Word sorting         | 0.525               |\n| Dyck languages       | 0.044               |\n| Object counting      | 0.000               |\n| Object properties    | 0.006               |\n| Boardgame qa         | 0.325               |\n| Boolean expressions  | 0.256               |\n| Buggy tables         | 0.025               |\n| Spatial reasoning    | 0.287               |\n| Multistep arithmetic | 0.000               |\n| Geometric shapes     | 0.369               |\n| Temporal sequence    | 0.000               |\n| Disambiguation qa    | 0.469               |\n| Causal understanding | 0.512               |\n| Time arithmetic      | 0.256               |\n| Web of lies          | 0.206               |\n| Sarc triples         | 0.331               |\n| Hyperbaton           | 0.025               |\n| Nycc                 | 0.106               |\n| Sportqa              | 0.212               |\n| Linguini             | 0.125               |\n| Movie recommendation | 0.388               |\n| Shuffled objects     | 0.006               |\n| Zebra puzzles        | 0.031               |\n| Harmonic Mean        | 0.040               |\n\n\n| Dataset              | Buffer of Thoughts (gemini-2.0-flash) |\n|----------------------|--------------------|\n| Word sorting         | 0.463              |\n| Dyck languages       | 0.056              |\n| Object counting      | 0.006              |\n| Object properties    | 0.000              |\n| Boardgame qa         | 0.275              |\n| Boolean expressions  | 0.031              |\n| Buggy tables         | 0.000              |\n| Spatial reasoning    | 0.113              |\n| Multistep arithmetic | 0.000              |\n| Geometric shapes     | 0.006              |\n| Temporal sequence    | 0.000              |\n| Causal understanding | 0.362              |\n| Time arithmetic      | 0.100              |\n| Web of lies          | 0.087              |\n| Sarc triples         | 0.194              |\n| Hyperbaton           | 0.013              |\n| Nycc                 | 0.019              |\n| Sportqa              | 0.125              |\n| Linguini             | 0.006              |\n| Movie recommendation | 0.013              |\n| Zebra puzzles        | 0.069              |\n| Harmonic Mean        | 0.026              |\n\n\nFinally, we perform an additional experiment where we resample a potential solution using PoT whenever the generated code results in a code related error or a null result. The following shows the harmonic mean accuracy over all BBEH tasks using Gemini 2.0 Flash as the base model. We see that resampling is minimally beneficial by itself.\n\n| Methods            | Harmonic Mean Acc. |\n|--------------------|--------------------|\n| PoT                | 0.095              |\n| PoT (with retries) | 0.098              |\n\n\n[1] Lyu, Qing, et al. \"Faithful chain-of-thought reasoning.\" IJCNLP-AACL 2023.\n[2] Gao, Luyu, et al. \"Pal: Program-aided language models.\" ICML 2023.\n[3] Wang, Xingyao, et al. \"Executable code actions elicit better llm agents.\" ICML 2024."}]

Author rebuttal:

Meta-review: This paper introduces Per-Instance Program Synthesis (PIPS), an approach that enhances the reasoning capabilities of large language models (LLMs) for complex tasks. PIPS addresses the limitations of existing methods, like Program of Thought (PoT), by dynamically deciding whether to use program synthesis or direct inference based on a confidence metric. Additionally, PIPS iteratively refines programs using structural feedback and converts unstructured inputs into structured program inputs through symbolic extraction.

The reviewers recognized the significance of PIPS in improving the performance of LLMs in multi-step reasoning, but they also raised concerns regarding the generalizability of PIPS, its computational overhead, and the limitations of its feedback mechanism. During the rebuttal phase, the authors effectively addressed these concerns through additional experiments and analysis. 

Based on the reviewers’ feedback and the authors’ thorough responses, we recommend accepting this submission. And we urge the authors to address the reviewers' remaining concern on the significance of performance gain in their camera ready version.
Decision: Accept (poster)