# ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis

arXiv: https://arxiv.org/abs/2605.05485 · HTML: https://mlsanity.com/paper/2605.05485/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 23 of its 28 references that are in the map.
- First posted on arXiv 6 May 2026.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 23 of 23)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [PAL: Program-aided Language Models](https://mlsanity.com/paper/2211.10435/) (2022)
- [Executable Code Actions Elicit Better LLM Agents](https://mlsanity.com/paper/2402.01030/) (2024)
- [ReWOO: Decoupling Reasoning from Observations for Efficient Augmented Language Models](https://mlsanity.com/paper/2305.18323/) (2023)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [TroVE: Inducing Verifiable and Efficient Toolboxes for Solving Programmatic Tasks](https://mlsanity.com/paper/2401.12869/) (2024)
- [Top-Down Synthesis for Library Learning](https://mlsanity.com/paper/2211.16605/) (2022)
- [LILO: Learning Interpretable Libraries by Compressing and Documenting Code](https://mlsanity.com/paper/2310.19791/) (2023)
- [ReGAL: Refactoring Programs to Discover Generalizable Abstractions](https://mlsanity.com/paper/2401.16467/) (2024)
- [BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration](https://mlsanity.com/paper/2007.14381/) (2020)
- [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024)
- [HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis](https://mlsanity.com/paper/2405.15880/) (2024)
- [Case2Code: Scalable Synthetic Data for Code Generation](https://mlsanity.com/paper/2407.12504/) (2024)
- [SLR: Automated Synthesis for Scalable Logical Reasoning](https://mlsanity.com/paper/2506.15787/) (2025)
- [ToolLibGen: Scalable Automatic Tool Creation and Aggregation for LLM Reasoning](https://mlsanity.com/paper/2510.07768/) (2025)
- [Programming by Examples Meets Historical Linguistics: A Large Language Model Based Approach to Sound Law Induction](https://mlsanity.com/paper/2501.16524/) (2025)
- [PBE Meets LLM: When Few Examples Aren't Few-Shot Enough](https://mlsanity.com/paper/2507.05403/) (2025)
- [When Tools Hurt LLM Reasoning: State-Dependent Belief Revision under External Evidence](https://mlsanity.com/paper/2508.15754/) (2025)
- [When Do Tools and Planning Help Large Language Models Think? A Cost- and Latency-Aware Benchmark](https://mlsanity.com/paper/2601.02663/) (2026)
- [PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics](https://mlsanity.com/paper/2505.23126/) (2025)
- [A Compute-Matched Re-Evaluation of TroVE on MATH](https://mlsanity.com/paper/2507.22069/) (2025)

## Built on by (most cited first, 2 of 2)

- [Narcissus: Program Synthesis Using Context-Aware LLM Approximations](https://mlsanity.com/paper/2608.25657/) (2026)
- [Agent in a Bottle: Can LLM Agents Turn Their Capabilities Into Cheap, Scalable Artifacts?](https://mlsanity.com/paper/2610.08775/) (2026)

## Abstract (arXiv)

LLMs can solve program synthesis tasks but remain inefficient and unreliable on hard instances requiring large combinatorial search. Given a small set of reasoning traces, we use coding agents to compile them into reusable symbolic program synthesizers over constrained DSLs. The resulting solvers require no LLM calls at test time and are strong standalone systems: symbolic solver ensembles reach 91.3% accuracy on PBEBench-Lite and 84.7% on PBEBench-Hard, outperforming LLMs with test-time scaling for the latter by +16.3 percentage points at zero LLM inference cost. They also complement LLM search, improving PBEBench-Hard accuracy from 68.4% to 85.8% while reducing reported token usage by 78%, and raising SLR-Bench hard-tier accuracy from 34.4% to 58.0% in a neuro-symbolic hybrid setting. Compared to directly using coding agents as per-instance solvers, induced solvers are substantially more Pareto-efficient, amortizing a small one-time construction cost over many zero-token executions. Finally, most solvers transfer zero-shot to a real historical linguistics task - predicting sound changes in natural language data - reaching 80.1% accuracy under ensembling and recovering some plausible linguistic rules. Together, these results show that reasoning traces can be compiled into reusable symbolic solvers that solve many tasks directly, complement LLM inference on hard cases, and provide a scalable route to domain-general solver induction. We release code and data for reproducibility.