HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis
This addresses the challenge of scaling program synthesis for structured prediction tasks, offering a practical improvement over purely neural or symbolic methods.
The paper tackles the problem of program synthesis in unfamiliar domain-specific languages by introducing a hybrid approach that uses LLM completions to learn task-specific context-free surrogate models, which then guide synthesis. The method outperforms unguided search, direct LLM sampling, and existing synthesizers across three domains.
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.