Narcissus: Program Synthesis Using Context-Aware LLM Approximations
Tilman Hinnerichs, Sebastijan Dumancic, and Neil Yorke-Smith (TU Delft) present Narcissus, an enumerative program synthesizer that keeps LLM proposals as syntax trees and scores each expansion in context, without a single LLM call during search.
Ask this paper
Rule frequencies throw away structure: The prior state of the art compresses LLM proposals into rule frequencies, losing where each construct belongs and pruning every rule the proposals miss, precisely when the proposals are wrong.
Context-aware expansion scoring: Narcissus asks whether a proposal with the same surrounding structure continues the same way, and whether an expansion rebuilds a fragment the proposals repeat.
Regularization keeps wrong proposals recoverable: A term keeps every rule reachable, so bad proposals delay the solution instead of hiding it. That is the property re-prompting cannot provide.
40 percent of ARC versus 13 percent raw: Across five domains and two search backends, it beats static guidance at every budget and reaches proposal-like programs an order of magnitude sooner.
Why it matters: Zero LLM calls during search means the model's contribution is fully amortized up front, which is a very different cost curve from agentic re-prompting loops.
Abstract
Large language models (LLMs) excel at programming, but not when the task fixes the target language: prompted with a grammar rare in their training data, their programs usually break the grammar or fail the given specification. Enumerative synthesizers search the space of syntactically correct programs systematically guided by LLMs; the state of the art guides them by approximating LLM proposals into rule frequencies, which loses where each construct belongs and prunes every rule the proposals miss, exactly when the proposals are wrong. We present Narcissus, a synthesizer that keeps the proposals as syntax trees and scores each expansion of a candidate program in its context: does a proposal with the same surrounding structure continue the same way, and does the expansion rebuild a fragment the proposals repeat? A regularization term keeps every rule reachable, so wrong proposals delay the solution but cannot hide it. Across five domains and two search backends, Narcissus beats static guidance at every budget and consistently outperforms re-prompting the LLM to fix its own proposals; it reaches proposal-like programs an order of magnitude sooner and solves $40\%$ of ARC tasks where the raw proposals solve $13\%$, all without a single LLM call during search.