Once Upon an Input: Reasoning via Per-Instance Program Synthesis
Adam Stein, Neelay Velingker, Mayur Naik, Eric Wong · 2025
Read Once Upon an Input: Reasoning via Per-Instance Program Synthesis by Adam Stein, Neelay Velingker, Mayur Naik, Eric Wong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22849.txt.
Introduction
Hard reasoning tasks may suit a custom program better than prose. Adam Stein, Neelay Velingker, Mayur Naik, and Eric Wong propose such a route in 2025. It is called Per-Instance Program Synthesis, or PIPS. For each input, it writes and refines a program. Structural feedback guides the refinement.
No task specific guidance is needed. No explicit test cases are needed either. A confidence score picks a strategy per instance. It chooses direct inference or program synthesis. Tests span thirty benchmarks and three frontier models. PIPS raised accuracy over chain and program baselines. It also cut undesirable program outputs sharply. Algorithmic tasks showed the clearest gains.
Catalog record
| CREATOR | Adam Stein, Neelay Velingker, Mayur Naik, Eric Wong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-22849
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Once Upon an Input: Reasoning via Per-Instance Program Synthesis Adam Stein, Neelay Velingker, Mayur Naik, Eric Wong 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. 1 1 1 Code for experiments and a demo is open-sourced at https://github.com/adaminsky/pips . 1 Introduction Large-scale pretraining endows LLMs with the ability to recognize common concepts and perform many tasks in a zero-shot fashion but they still struggle with multi-step reasoning [ 1 , 2 , 3 ] . Recent advances in inference-time reasoning strategies such as Chain of Thought (CoT) and related work [ 4 , 5 , 6 ] have significantly improved LLMs’ reasoning abilities. However, they remain unreliable [ 7 , 8 , 9 , 10 ] and unfaithful, meaning the final answer is correct for the wrong reasons [ 11 , 12 , 13 ] . Unlike LLM inference, program execution enforces precise, verifiable computation. Combining LLMs with program execution offers a promising reasoning method: the LLM handles perceptual inference, mapping raw input to structured form, while algorithmic reasoning is offloaded to an executable program [ 2 , 14 , 15 ] . Existing work on neuro-symbolic learning as well as methods such as Faithful Chain of Thought (FCoT) [ 16 ] and Program Aided Language Models (PAL) [ 17 ] adopts this approach, however, they use a 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 on an instance-level . While flexible, these methods often produce undesirable programs, due to three challenges in instance-level program synthesis: (1) open domain : determining for a given instance if program synthesis is preferable to 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, and (3) unstructured input : programs typically operate over structured input, but common reasoning problems are unstructured, requiring on-the-fly instance-level input understanding. Figure 1 : Overview of Per-Instance Program Synthesis ( PIPS ). PIPS addresses the open-domain nature of reasoning problems by selecting between synthesis and CoT at the instance-level, avoiding unnecessarily generating programs for non-algorithmic problems. For algorithmic problems, PIPS addresses the lack of task specifications by iteratively synthesizing programs using feedback based on structural checks . PIPS handles unstructured input via instance-specific symbolic extraction (step 1) before program synthesis (step 2). Figure 2 shows an example where an undesirable program is rejected before producing an acceptable one which gives the correct answer upon execution (step 3). In this paper, we propose Per-Instance Program Synthesis, or PIPS , to solve reasoning problems at the instance-level. Figure 1 illustrates 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 to 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 [ 20 , 15 , 21 ] , PIPS does not require explicit test cases, examples, or other forms of task specifications. 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 [ 7 ] 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 challenges of per-instance program synthesis methods. • Synthesis Confidence Metric: We study the tradeoff between program synthesis and CoT for answering reasoning problems, and we propose a synthesis confidence metric which predicts, prior to generation, which approach is more likely to yield a correct solution for a 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. Figure 2 : Example illustrating two iterations of the synthesis loop in PIPS . 2 The Challenges of Per-Instance Program Synthesis A reasoning problem is a pair (x,y)\in\mathcal{X}\times\mathcal{Y} where x is a raw query consisting of unstructured data such as natural language text or an image, and y is the answer which we assume is represented symbolically (something that could be output by a program). Existing methods for generating instance-level programs for solving reasoning problems, such as PoT, produce a program P:\varnothing\to\mathcal{Y} to compute the correct answer. These programs take no input, similar to a 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 are well-suited to program synthesis but non-algorithmic problems are inherently ill-suited; producing a 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 (a) Fraction of output code with issues: trivial (hard-coded answer), type (wrong return type), syntax (parser error), and placeholders (incomplete code). (b) Per-instance synthesis baseline performance on mostly algorithmic vs. non-algorithmic problems. Shading indicates fraction of correct solutions with non-trivial code. Figure 3 : Failures in existing approaches to per-instance program synthesis with Gemini-2.0-Flash. The per-instance synthesis setting poses a tradeoff between program synthesis and direct inference reliability. In some cases, it is more reliable for an LLM to solve a problem