Research map / Large language models / Agents, code and math
Once Upon an Input: Reasoning via Per-Instance Program Synthesis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Per-Instance Program Synthesis (PIPS), which generates and iteratively refines programs per instance using structural checks instead of test cases, and uses a self-assessed confidence switch to choose between program synthesis and CoT.
Problem
Instance-level program synthesis (e.g., PoT) often yields undesirable programs (trivial hard-coded answers, type/syntax errors, placeholders, brittle handling of unstructured inputs) and LLMs do not know when program synthesis beats direct CoT reasoning.
Approach
Per-instance synthesis loop guided by structural feedback (non-triviality, syntax, type errors) with no test cases; an LLM first abstracts unstructured input into symbolic JSON, and a self-prompted confidence score over ten criteria decides between CoT and program synthesis per instance.
Key results
- PIPS improves harmonic mean accuracy over PoT by 8.6% absolute across 30 datasets with Gemini-2.0-Flash.
- PIPS reduces undesirable (trivial/placeholder/type/syntax) programs by 65.1% on algorithmic tasks versus PoT with Gemini-2.0-Flash.
- The confidence switch selects the correct method 65.3% of the time on disagreement cases for Gemini-2.0-Flash, giving a 2.2% harmonic mean gain.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PIPS instead of PoT | Gemini-2.0-Flash, GPT-4.1-mini, and o4-mini · 30 datasets | HMean Accuracy: 8.6% | Helped |
| use PIPS instead of CoT | Gemini-2.0-Flash, GPT-4.1-mini, and o4-mini · 30 datasets | HMean Accuracy: 9.4% | Helped |
| add the confidence switch (ablation) | PIPS · BBEH tasks | HMean Accuracy (%): 18.3 -> 20.8 | Helped |
| add iterative evaluator feedback (ablation) | PIPS without the confidence switch · BBEH tasks | HMean Accuracy (%): 12.9 -> 18.3 | Helped |
| add structured input symbols (ablation) | PIPS[0] without the confidence switch · BBEH tasks | HMean Accuracy (%): 4.3 -> 12.9 | Helped |
| use PIPS instead of PoT | o4-mini · Buggy tables | accuracy: 0.512 -> 0.594 | Helped |
| use PIPS instead of PoT | o4-mini · Temporal sequence | accuracy: 0.306 -> 0.519 | Helped |
| use PIPS instead of CoT | o4-mini · Dyck languages | accuracy: 0.650 -> 0.606 | Hurt |
| use PIPS instead of PoT | o4-mini · Time arithmetic | accuracy: 0.900 -> 0.894 | Hurt |
| use PIPS instead of PoT | o4-mini · Shuffled objects | accuracy: 0.150 -> 0.344 | Helped |
| use PIPS instead of PoT | Gemini-2.0-Flash · BBEH algorithmic tasks | undesirable program generations: 65.1% | Helped |
| increase synthesis iterations from k=0 (ablation) | PIPS · 30 datasets | HMean Accuracy: 5.6% | Helped |
Surprising findings
- Over 50% of PoT outputs on algorithmic tasks are trivial programs with hard-coded answers.
- PoT code execution slightly hurts performance on non-algorithmic tasks.
Limitations
- Only simple structural code properties are checked; other undesirable code patterns are not explored.
- Does not handle problems best solved partly by CoT and partly by program synthesis.
- Conversion of input to symbolic form lacks faithfulness guarantees.
Experimental setup
Datasets: BBEH (23 tasks) CLEVR Leaf CLUTRR OmniMath (4 tasks)
Benchmarks: BBEH CLEVR Leaf CLUTRR OmniMath
Metrics: harmonic mean accuracy accuracy non-trivial code percentage well-formed program rate calibration
Baselines: Program of Thought Chain of Thought Gemini Code Interpreter PoT-retries CodeAct Buffer-of-Thoughts
Builds on: Program of Thought Chain of Thought Program Aided Language Models CodeAct
Closest papers by meaning
- Training Language Models to Reason Efficiently (NeurIPS 2025 · similarity 0.89)
- A Theoretical Study on Bridging Internal Probability and Self-Consistency for LLM Reasoning (NeurIPS 2025 · similarity 0.89)
- Think Deep, Not Just Long: Measuring LLM Reasoning Effort via Deep-Thinking Tokens (ICML 2026 · similarity 0.89)
- Reasoning-as-Logic-Units: Scaling Test-Time Reasoning in Large Language Models Through Logic Unit Alignment (ICML 2025 · similarity 0.89)
- Exploring the Limits of Sub-Billion Language Model Reasoners with Open Training Recipes (ICLR 2026 · similarity 0.88)
- ReGenesis: LLMs can Grow into Reasoning Generalists via Self-Improvement (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.