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

• URL: http://arxiv.org/abs/2605.05485v1
• Date: Wed, 06 May 2026 22:08:17 GMT
• Title: ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis
• Abstract summary: LLMs can solve program synthesis tasks but remain inefficient and unreliable on hard instances requiring large search.<n>We use coding agents to compile reasoning traces into reusable symbolic program synthesizers over constrained DSLs.<n>The resulting solvers require no LLM calls at test time and are strong standalone systems.
• Score: 5.1817559908145565
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  We present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton.<n>The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding.<n> Empirical evaluations on Dream-7B and LLaDA-8 show substantial accuracy gains across various tasks.
  arXiv  Detail & Related papers  (2026-07-08T05:48:57Z)
• LLM-as-a-Verifier: A General-Purpose Verification Framework [74.40111651545979]
  We introduce LLM-as-a-Verifier, a general-purpose verification framework.<n>It provides fine-grained feedback for agentic tasks without requiring additional training.<n>It achieves state-of-the-art performance on several benchmarks.
  arXiv  Detail & Related papers  (2026-07-06T17:59:35Z)
• Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers [52.23061619664667]
  Large Language Models (LLMs) struggle to solve complex problems through direct reasoning, so recent neuro-symbolic systems increasingly use them to synthesize executable solvers.<n>We introduce CP-SynC-XL, a benchmark of 100 problems (4,577 instances), and evaluate three solver--construction paradigms: native algorithmic search (Python), constraint modeling through a Python solver API (Python + OR-Tools), and declarative constraint modeling.
  arXiv  Detail & Related papers  (2026-05-12T17:15:45Z)
• Evaluating Prompting and Execution-Based Methods for Deterministic Computation in LLMs [1.2957535240267326]
  Large Language Models (LLMs) have demonstrated strong capabilities in natural language understanding and reasoning.<n>We systematically evaluate multiple prompting strategies, including Chain-of-Thought (CoT), Least-to-Most decomposition, Program-of-Thought (PoT), and Self-Consistency (SC)<n>Our results show that standard prompting methods achieve only moderate accuracy on sequence-based tasks.
  arXiv  Detail & Related papers  (2026-05-04T23:32:37Z)
• Assessing Coherency and Consistency of Code Execution Reasoning by Large Language Models [5.692204231573854]
  This paper proposes CES, a task to evaluate the abilities of LLMs in simulating program execution and using that reasoning in programming tasks.<n>CES introduces the notion of coherence to determine whether the simulation complies with commonsense execution logic, even if the predicted values along the simulations are incorrect.<n>CES also introduces a novel metric to measure reasoning consistency across tests with the same or different prime path coverage in a spectrum: strong, weak, and random.
  arXiv  Detail & Related papers  (2025-10-16T18:48:12Z)
• SLR: Automated Synthesis for Scalable Logical Reasoning [23.14914698597022]
  We introduce SLR, an end-to-end framework for systematic evaluation and training of Large Language Models (LLMs)<n>Given a user's task specification, SLR automatically synthesizes an instruction prompt for an inductive reasoning task.<n>Using SLR, we create SLR-Bench, a benchmark comprising 19k prompts organized into 20 curriculum levels.
  arXiv  Detail & Related papers  (2025-06-18T18:10:30Z)
• Scalable LLM Math Reasoning Acceleration with Low-rank Distillation [57.922185576872444]
  We propose a resource-efficient distillation method to recover lost capabilities from deploying efficient inference methods.<n>With original weights unperturbed, roughly 1% of additional parameters, and only 20K synthetic training samples, we are able to recover much if not all of the math capabilities lost.
  arXiv  Detail & Related papers  (2025-05-08T17:51:24Z)
• BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions [72.56339136017759]
  We introduce BigCodeBench, a benchmark that challenges Large Language Models (LLMs) to invoke multiple function calls as tools from 139 libraries and 7 domains for 1,140 fine-grained tasks.<n>Our evaluation shows that LLMs are not yet capable of following complex instructions to use function calls precisely, with scores up to 60%, significantly lower than the human performance of 97%.<n>We propose a natural-language-oriented variant of BigCodeBench, BigCodeBench-Instruct, that automatically transforms the original docstrings into short instructions only with essential information.
  arXiv  Detail & Related papers  (2024-06-22T15:52:04Z)
• MEIC: Re-thinking RTL Debug Automation using LLMs [18.964523115622928]
  This work introduces a novel framework, Make Each Iteration Count (MEIC) MEIC is suitable for identifying and correcting both syntax and function errors. To evaluate our framework, we provide an open-source dataset comprising 178 common RTL programming errors.
  arXiv  Detail & Related papers  (2024-05-10T22:32:39Z)
• PAL: Program-aided Language Models [112.94785609781503]
  We present Program-Aided Language models (PaL) to understand natural language problems. PaL offloads the solution step to a programmatic runtime such as a Python interpreter. We set new state-of-the-art results in all 12 benchmarks.
  arXiv  Detail & Related papers  (2022-11-18T18:56:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.