mlsanityData to 7 Oct 2026

HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis

arXiv 2405.15880 ↗First posted 24 May 2024cs.PL cs.AIcited by 14

Not on the map. Why?

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.

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

Builds on

22 of 50 references.

References · 22

  1. 2024DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligencecited by 1,154
  2. 2023The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"cited by 399
  3. 2023Embers of Autoregression: Understanding Large Language Models Through the Problem They are Trained to Solvecited by 175
  4. 2020DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learningcited by 159
  5. 2016DeepCoder: Learning to Write Programscited by 145
  6. 2017RobustFill: Neural Program Learning under Noisy I/Ocited by 124
  7. 2023Hypothesis Search: Inductive Reasoning with Language Modelscited by 119
  8. 2023LLMs and the Abstraction and Reasoning Corpus: Successes, Failures, and the Importance of Object-based Representationscited by 81
  9. 2023Tractable Control for Autoregressive Language Generationcited by 65
  10. 2018Neural-Guided Deductive Search for Real-Time Program Synthesis from Examplescited by 39
  11. 2022Graphs, Constraints, and Search for the Abstraction and Reasoning Corpuscited by 32
  12. 2024Reasoning Abilities of Large Language Models: In-Depth Analysis on the Abstraction and Reasoning Corpuscited by 32
10 more
  1. 2020BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Explorationcited by 30
  2. 2020TF-Coder: Program Synthesis for Tensor Manipulationscited by 27
  3. 2017Program Synthesis using Conflict-Driven Learningcited by 26
  4. 2021Neural-guided, Bidirectional Program Search for Abstraction and Reasoningcited by 23
  5. 2020Just-in-Time Learning for Bottom-Up Enumerative Synthesiscited by 18
  6. 2022CrossBeam: Learning to Search in Bottom-Up Program Synthesiscited by 18
  7. 2023Large Language Model (LLM) as a System of Multiple Expert Agents: An Approach to solve the Abstraction and Reasoning Corpus (ARC) Challengecited by 11
  8. 2024Generalized Planning for the Abstraction and Reasoning Corpuscited by 10
  9. 2024Grounding Data Science Code Generation with Input-Output Specificationscited by 7
  10. 2023Efficient Bottom-Up Synthesis for Programs with Local Variablescited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 6; 2026: 4.

14 papers.

Sort:

By area:

  1. 2024Flow of Reasoning: Training LLMs for Divergent Reasoning with Minimal Examplescited by 29
  2. 2025A Survey on Inference Engines for Large Language Models: Perspectives on Optimization and Efficiencycited by 12
  3. 2025Towards Reliable Code-as-Policies: A Neuro-Symbolic Framework for Embodied Task Planningcited by 10
  4. 2024Tackling the Abstraction and Reasoning Corpus with Vision Transformers: the Importance of 2D Representation, Positions, and Objectscited by 9
  5. 2025Grammars of Formal Uncertainty: When to Trust LLMs in Automated Reasoning Taskscited by 9
  6. 2024ConceptSearch: Towards Efficient Program Search Using LLMs for Abstraction and Reasoning Corpus (ARC)cited by 8
  7. 2025Synthesizing Visual Concepts as Vision-Language Programscited by 6
  8. 2025From Reasoning to Generalization: Knowledge-Augmented LLMs for ARC Benchmarkcited by 2
  9. 2025Context-Adaptive Synthesis and Compression for Enhanced Retrieval-Augmented Generation in Complex Domainscited by 1
  10. 2026ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesiscited by 1
  11. 2024System 2 Reasoning for Human-AI Alignment: Generality and Adaptivity via ARC-AGIcited by 0
  12. 2026Narcissus: Program Synthesis Using Context-Aware LLM Approximationscited by 0
2 more
  1. 2026Combining LLMs and Genetic Search for ARC-AGI-2cited by 0
  2. 2026DatalogBench: Evaluating Large Language Models on Text-to-Datalog Synthesiscited by 0