# HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 50 references that are in the map.
- First posted on arXiv 24 May 2024.

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

- [DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligence](https://mlsanity.com/paper/2401.14196/) (2024)
- [The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"](https://mlsanity.com/paper/2309.12288/) (2023)
- [Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solve](https://mlsanity.com/paper/2309.13638/) (2023)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [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)
- [Hypothesis Search: Inductive Reasoning with Language Models](https://mlsanity.com/paper/2309.05660/) (2023)
- [LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representations](https://mlsanity.com/paper/2305.18354/) (2023)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples](https://mlsanity.com/paper/1804.01186/) (2018)
- [Graphs, Constraints, and Search for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2210.09880/) (2022)
- [Reasoning Abilities of Large Language Models: In-Depth Analysis on the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2403.11793/) (2024)
- [BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration](https://mlsanity.com/paper/2007.14381/) (2020)
- [TF-Coder: Program Synthesis for Tensor Manipulations](https://mlsanity.com/paper/2003.09040/) (2020)
- [Program Synthesis using Conflict-Driven Learning](https://mlsanity.com/paper/1711.08029/) (2017)
- [Neural-guided, Bidirectional Program Search for Abstraction and Reasoning](https://mlsanity.com/paper/2110.11536/) (2021)
- [Just-in-Time Learning for Bottom-Up Enumerative Synthesis](https://mlsanity.com/paper/2010.08663/) (2020)
- [CrossBeam: Learning to Search in Bottom-Up Program Synthesis](https://mlsanity.com/paper/2203.10452/) (2022)
- [Large Language Model (LLM) as a System of Multiple Expert Agents: An Approach to solve the Abstraction and Reasoning Corpus (ARC) Challenge](https://mlsanity.com/paper/2310.05146/) (2023)
- [Generalized Planning for the Abstraction and Reasoning Corpus](https://mlsanity.com/paper/2401.07426/) (2024)
- [Grounding Data Science Code Generation with Input-Output Specifications](https://mlsanity.com/paper/2402.08073/) (2024)
- [Efficient Bottom-Up Synthesis for Programs with Local Variables](https://mlsanity.com/paper/2311.03705/) (2023)

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

- [Flow of Reasoning: Training LLMs for Divergent Reasoning with Minimal Examples](https://mlsanity.com/paper/2406.05673/) (2024)
- [A Survey on Inference Engines for Large Language Models: Perspectives on Optimization and Efficiency](https://mlsanity.com/paper/2505.01658/) (2025)
- [Towards Reliable Code-as-Policies: A Neuro-Symbolic Framework for Embodied Task Planning](https://mlsanity.com/paper/2510.21302/) (2025)
- [Tackling the Abstraction and Reasoning Corpus with Vision Transformers: the Importance of 2D Representation, Positions, and Objects](https://mlsanity.com/paper/2410.06405/) (2024)
- [Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Tasks](https://mlsanity.com/paper/2505.20047/) (2025)
- [ConceptSearch: Towards Efficient Program Search Using LLMs for Abstraction and Reasoning Corpus (ARC)](https://mlsanity.com/paper/2412.07322/) (2024)
- [Synthesizing Visual Concepts as Vision-Language Programs](https://mlsanity.com/paper/2511.18964/) (2025)
- [From Reasoning to Generalization: Knowledge-Augmented LLMs for ARC Benchmark](https://mlsanity.com/paper/2505.17482/) (2025)
- [ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis](https://mlsanity.com/paper/2605.05485/) (2026)
- [Context-Adaptive Synthesis and Compression for Enhanced Retrieval-Augmented Generation in Complex Domains](https://mlsanity.com/paper/2508.19357/) (2025)
- [System 2 Reasoning for Human-AI Alignment: Generality and Adaptivity via ARC-AGI](https://mlsanity.com/paper/2410.07866/) (2024)
- [Narcissus: Program Synthesis Using Context-Aware LLM Approximations](https://mlsanity.com/paper/2608.25657/) (2026)
- [Combining LLMs and Genetic Search for ARC-AGI-2](https://mlsanity.com/paper/2609.27242/) (2026)
- [DatalogBench: Evaluating Large Language Models on Text-to-Datalog Synthesis](https://mlsanity.com/paper/2609.37233/) (2026)
- [Assembling Insights for Agentic Machine Learning Engineering Systems](https://mlsanity.com/paper/2610.04927/) (2026)

## Abstract (arXiv)

Many structured prediction and reasoning tasks can be framed as program synthesis problems, where the goal is to generate a program in a domain-specific language (DSL) that transforms input data into the desired output. Unfortunately, purely neural approaches, such as large language models (LLMs), often fail to produce fully correct programs in unfamiliar DSLs, while purely symbolic methods based on combinatorial search scale poorly to complex problems. Motivated by these limitations, we introduce a hybrid approach, where LLM completions for a given task are used to learn a task-specific, context-free surrogate model, which is then used to guide program synthesis. We evaluate this hybrid approach on three domains, and show that it outperforms both unguided search and direct sampling from LLMs, as well as existing program synthesizers.