Combining classical tools and language models improves recursive program synthesis
Symbolic Synthesis with Token-Level LLM Guidance
Programming Languages
Summary
The paper tackles the problem of writing recursive programs from logical rules. The authors combine traditional program synthesis methods with smaller large language models (LLMs) by using the LLM's next-token predictions to guide the search for correct programs. Their method filters out incorrect and duplicate program parts early using classical techniques, improving efficiency and success rates. Experiments show this combined approach solves almost all tested synthesis problems while the LLM or classical synthesis alone solve far fewer.
What this means in practice
- •For software developers: Automatically generate recursive code snippets from formal specifications for faster development and prototyping.
- •For ai tool builders: Build hybrid synthesis tools that combine lightweight LLMs with symbolic checks to improve program generation accuracy and coverage.$Commercial implications: Enables creation of commercial programming assistants that reliably generate recursive code, suitable for integration in IDEs and developer platforms.
Authors
Derek Egolf, Stavros Tripakis
Abstract
We propose a synergistic combination of classical program synthesis techniques and contemporary large language models (LLMs) to solve the problem of recursive program synthesis from first-order logic specifications. Our approach leverages the strengths of both paradigms: we use LLMs as a source of statistical bias to guide the search for a correct program. At the same time we use techniques from classical synthesis to short-circuit on semantically incorrect prefixes and to avoid sampling semantically equivalent responses. The statistical bias is derived from the next-token distribution of an LLM, which is highly context-dependent. We operate with the understanding that (1) there is some class of synthesis instances that can be discharged by small models and symbolic tools, and (2) every other instance can be decomposed into these instances. Therefore, our intention is to expand the reach of small, open-weight LLMs and symbolic synthesis techniques, not to compete with proprietary frontier models on every possible instance. These are different tools for different jobs. In our experimental evaluation, we find that our method solves more benchmarks than either small LLMs or classical synthesis techniques alone. Our method solves 30/32 benchmarks using only a Qwen2.5 model with 32 billion parameters. Qwen2.5 solves 0 benchmarks on its own, and only solves a few additional benchmarks when combined with traditional constrained decoding techniques.