Once Upon an Input: Reasoning via Per-Instance Program Synthesis

AI summary

Overview

Research area: Large language model reasoning and neuro-symbolic program synthesis (arXiv category cs.CL), sitting at the intersection of LLM inference-time strategies, code generation, and program synthesis.

Technical level: Advanced. The paper assumes familiarity with chain-of-thought prompting, program-of-thought prompting, program evaluation (syntax/type analysis), and calibration of confidence scores.

Scope: The paper introduces Per-Instance Program Synthesis (PIPS), a method that decides per problem instance whether to answer with a synthesized-and-refined program or with direct chain-of-thought reasoning, and evaluates it across 30 benchmarks and three frontier LLMs.

What This Paper Is About

Large language models can answer many questions zero-shot but still struggle with complex multi-step reasoning. Existing code-based approaches such as Program of Thought (PoT) ask the model to write a Python program per problem and execute it, but this frequently yields bad programs — hard-coded answers, syntax errors, wrong return types, or placeholder code — especially on problems that are not really algorithmic. PIPS tackles this by synthesizing and iteratively refining a program for each individual instance using only structural feedback (no test cases or task specifications), and by first deciding whether the instance should be solved with a program at all or with direct chain-of-thought inference.

Key Contributions

1. Per-Instance Program Synthesis (PIPS): An iterative program synthesis loop guided by instance-specific feedback on structural properties of the generated code, designed to address the specific failure modes of per-instance program generation (open-domain applicability, absence of task specifications, and unstructured inputs).

2. A synthesis confidence metric: A self-prompting switch in which the model scores ten task-agnostic criteria (plus ten additional criteria for reasoning models), producing a confidence vector that predicts — before generation — whether program synthesis or chain-of-thought is more likely to yield the correct answer for that instance.

3. Empirical results across 30 benchmarks and three frontier models: PIPS improves absolute harmonic mean accuracy by up to 8.6% over PoT and 9.4% over CoT, and reduces undesirable program generations by 65.1% on algorithmic tasks compared to PoT with Gemini-2.0-Flash.

4. Open-source release: Code for the experiments and a demo are released at https://github.com/adaminsky/pips.

Main Findings

• Overall accuracy gains: Across all 30 datasets, PIPS improves absolute harmonic mean accuracy by up to 8.6% over PoT and 9.4% over CoT. Per-model improvements over PoT were up to 23.7% absolute accuracy for Gemini-2.0-Flash (on the BBEH Boolean Expressions task), 0.8% for GPT-4.1-mini, and 5.7% for o4-mini.

• Largest gains on algorithmic tasks: On the majority algorithmic tasks, PIPS improves absolute harmonic accuracy by up to 15.9% for o4-mini, while not degrading accuracy on the non-algorithmic tasks.

• Feedback iteration drives the gains: Even at k = 0, where the evaluator is not used, PIPS outperforms PoT by a harmonic mean difference of 5.6% and the Gemini Code Interpreter baseline by 3.7%. The gap widens as the number of iterations scales.

• Code quality improves substantially: Among algorithmic samples, trivial programs are reduced by as much as 75.6%, type and syntax issues by 49.2% and 86.8% respectively, and programs containing placeholders by 36.3%. PIPS also produces significantly more well-formed programs than PoT, with the gap reaching 53.7% absolute percentage points on the Temporal Sequence task.

• The failure modes of PoT are quantified: Over 50% of PoT's outputs on algorithmic tasks are trivial programs with hard-coded return values; 6.3% have syntax errors and 11.5% return the wrong type. On the multimodal CLEVR and Leaf datasets, 12.7% of well-formed PoT code solutions use the OpenCV or Pillow libraries — a brittle approach to input understanding that PIPS never attempts, since it never tries to manually process images.

• Marginal impact of each fix type (BBEH algorithmic tasks): Syntax errors fixed gave a 20.0 percentage-point accuracy boost across 200 samples; wrong return type 16.8 points across 297 samples; placeholders 7.2 points across 194 samples; hardcoded answers 5.2 points across 1138 samples.

• The switch works and is well calibrated: Considering only the 24.8% of samples across the 30 benchmarks where either PIPS or CoT is correct but not both, the switch picks the correct method 65.3% of the time for Gemini-2.0-Flash, yielding a 2.2% absolute gain in harmonic mean accuracy. The calibration curve shows the switch is well calibrated, with notable deviation at the extremes.

• Ablation on BBEH harmonic mean accuracy: Full PIPS reaches 20.8%; without the switch 18.3%; PIPS-0 (no switch) 12.9%; PIPS-0 with neither switch nor symbolic extraction 4.3%. Explicit structured function inputs alone account for a 4% harmonic mean improvement on BBEH.

• Cost: The paper reports average cost in Appendix E and states PIPS achieves lower cost than other iterative approaches.

Methodology in Plain English

The method breaks problem solving into three parts.

Deciding whether to write code. Before any reasoning happens, the model is asked a set of probing questions about the instance — ten criteria covering things like whether the problem is easy to formalize, whether code execution is likely to succeed, and whether the logic is robust, plus ten more for reasoning-trained models. Each yields a confidence score, giving a vector in [0,1]^10. A decision to use either chain-of-thought or program synthesis is then made either fully zero-shot or with a logistic classifier trained on a held-out calibration set. The researchers reserve a random 20% of the data for calibration and evaluate on the remaining 80%, and they also test a leave-one-dataset-out scheme and a zero-shot switch.

Turning messy input into structured input. Because programs need structured inputs but reasoning problems come as text or images, an LLM first extracts salient entities, their attributes, and their relations into an ad-hoc schema (for example JSON) tailored to that specific instance. This decouples perceptual understanding from the program logic. The extraction step is denoted c, so the overall structure is y = P(c(x)).

Searching for a good program without specifications. Traditional program synthesis needs a specification (input-output examples or a logical spec). Since only one input is available, PIPS instead uses an evaluator that flags generally undesirable properties of generated code — triviality (hard-coded answers), syntax errors, type errors, and placeholders. An initial program is generated, the evaluator checks it, and if any issue is found the evaluator produces structural feedback. Feedback about the program leads to a revised program; feedback about the extracted symbols leads to revised symbol extraction. This repeats for at most k iterations, or stops as soon as the evaluator detects no issues. The goal is framed as minimizing an LLM term plus a weighted evaluator term.

Evaluation setup. The experiments use 23 Big Bench Extra Hard (BBEH) tasks plus 7 additional tasks (CLEVR, Leaf, CLUTTR, and four OmniMath tasks), for 30 datasets total, tested on Gemini-2.0-Flash, GPT-4.1-mini, and o4-mini. Baselines are Program of Thought, Chain of Thought, and the Gemini Code Interpreter tool-use agent, with PoT-retries, CodeAct, and Buffer-of-Thoughts additionally reported for Gemini-2.0-Flash in the appendix. An LLM-based classifier labels instances as algorithmic or non-algorithmic; the paper reports results split into 17 majority algorithmic tasks and 10 majority non-algorithmic tasks, and notes that algorithmicity is best determined at the instance level rather than the task level.

Why This Matters

Impact on research. The paper argues that the right unit of decision for code-based reasoning is the instance, not the task, and backs this with evidence that tasks are not cleanly algorithmic or non-algorithmic. It also shows that useful "specifications" for program search can be derived from generic structural properties of bad generated code rather than from task-specific test cases. That is a meaningful shift for neuro-symbolic methods like PAL, Faithful Chain of Thought, and PoT, which rely on fixed programs per task or on example-based verification. The finding that a model's own estimate of its abilities predicts which reasoning mode will succeed also connects to work on LLM self-evaluation.

Real-world applications.

• Building reasoning agents that route between code execution and direct generation, avoiding pointless interpreter calls on tasks like summarization or emotion understanding.
• Visual question answering and multimodal reasoning, where the paper's structured-extraction step substitutes for fragile image-processing code written with OpenCV or Pillow.
• Mathematical and relational reasoning tools that need verifiable, executable derivations rather than text-only answers.
• Code assistants and tool-use pipelines that need automatic detection and repair of trivial, syntactically broken, or placeholder-laden generated code without any human-provided tests.

Industry relevance. Reducing code-book/trivial solutions by 65.1% and cutting unnecessary interpreter calls directly addresses cost and reliability concerns in deployed code-generation agents. The reported lower cost relative to other iterative approaches matters for serving these methods at scale, and the open-sourced code and demo lower the barrier to adoption.

Future Directions

• Discovering more failure patterns. The authors state that PIPS focuses on simple structural code properties because they occur often, and that further work is needed to determine whether LLM-generated code contains other undesirable patterns worth checking for.
• Hybrid reasoning within a single problem. PIPS does not optimally handle problems best solved partly with chain-of-thought and partly with program synthesis; the authors call for problem decomposition and composition methods.
• Faithfulness of the symbolic extraction step. While code execution gives interpretable reasoning, the conversion of raw input to symbolic form still lacks faithfulness guarantees.
• Understanding the switch further. The paper reports calibration deviations at the extremes and studies marginal contributions of each criterion for the confidence score, leaving room for improving the selector itself.

Target Audience

Researchers and practitioners working on LLM reasoning, inference-time methods, and neuro-symbolic or code-based problem solving will benefit most. It is also relevant to engineers building tool-use and code-execution agents who care about automatically rejecting and repairing bad generated programs without test cases, and to readers interested in calibration and self-evaluation of LLMs.

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