PaperlayerView exact revision on arXiv

Source-linked AI summary

Narcissus: Program Synthesis Using Context-Aware LLM Approximations

Tilman Hinnerichs, Sebastijan Dumancic, Neil Yorke-Smith

arXiv:2608.25657v1cs.AIcs.LGcs.PLcs.SE

TL;DR

LLMs and static proposal priors struggle when synthesis must obey rare fixed grammars, because priors ignore construct context and can suppress rules proposals miss. Narcissus preserves proposal trees, adds recurring fragments, and scores expansions contextually while keeping every rule reachable. Across five domains and two search backends, it consistently outperforms static guidance and re-prompting, including 40% ARC accuracy versus 13% for raw proposals.

  • Problem

    LLM proposals and static rule-frequency guidance are limited for fixed, rare grammars because proposals can be ungrammatical or incorrect, while static priors ignore context and underweight missed rules.

  • Method

    Narcissus parses and repairs one-time LLM proposals into syntax trees, mines recurring fragments into grammar extensions, and scores each expansion using context-aware signals without querying the LLM during search.

  • Results

    Across five domains and two search backends, Narcissus beats static guidance on all benchmarks and plain re-prompting; on ARC it solves 40% of tasks versus 13% for raw proposals.

  • Takeaways & Limitations

    Context-aware proposal guidance improves over static priors and direct re-prompting while retaining access to every grammar rule when proposals are misleading.

  • Takeaways & Limitations

    Narcissus is designed to exploit proposal support and to degrade gracefully when support is low, with reachability constraining guidance rather than guaranteeing fast solutions.

Abstract

from arXiv · show

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.

Introduction

LLMs often fail when programs must use rare, fixed grammars, while static proposal frequencies ignore context and can block rules absent from faulty proposals. Narcissus instead compiles repaired proposal trees into context-aware, regularized guidance and improves synthesis across domains and search backends.

  • Motivation: Fixed target languages expose a weakness of LLM programming workflows because rare grammar constructs are often replaced by familiar functions, producing ungrammatical or incorrect programs.Retrying largely resamples the same mistakes, and the best proposal model solves at most a third of benchmark tasks outright.
  • Motivation: Static rule frequencies lose where constructs belong and give negligible weight to rules absent from proposals, precisely when search must correct faulty proposals.They capture neither context-specific placement nor repeated sub-term structure.
  • Narcissus: Narcissus parses and repairs proposals as ASTs, mines recurring fragments into macro-rules, and scores grammar expansions using prefix alignment, sub-program reuse, and regularization.The LLM is prompted once before search, and the resulting heuristic is consulted without further LLM calls.
  • Narcissus: A positive regularization floor keeps every grammar rule reachable, so misleading proposals can delay the solution without hiding it entirely.This preserves solvability while still prioritizing proposal-supported expansions.
  • Results: Across five domains and two search backends, Narcissus beats static guidance on all benchmarks and outperforms plain re-prompting.The evaluation uses cost-based bottom-up beam and genetic top-down search with proposals ranging from mostly correct to almost never grammar-valid.
  • Results: 40% of ARC tasks are solved by Narcissus versus 13% by raw proposals, while proposal-like programs are reached about an order of magnitude sooner.The comparison uses raw proposals constrained to the target grammar.

Preliminaries

Program synthesis finds programs in a grammar that satisfy a specification, commonly input-output examples. Enumerative search systematically constructs and tests candidates, using top-down or bottom-up strategies because the program space grows exponentially.

  • Program Synthesis: Program synthesis searches for a program in a grammar-defined language that satisfies a specification, commonly a set of input-output examples.A candidate solves the task when it produces every specified output for its corresponding input.
  • Enumerative Search: Enumerative search builds programs from grammar rules, tests complete candidates against the specification, and stops when one passes.Top-down search expands open positions from the start symbol, whereas bottom-up search composes complete sub-terms.
  • Enumerative Search: Because the number of programs grows exponentially with program size, synthesizers use heuristics to decide which candidates to explore first.These heuristics determine search order without changing the grammar-defined candidate language.

Problem Statement

The problem is to construct a proposal-derived heuristic whose scores depend on partial-program context, remain cheap across millions of expansions, and preserve access to every grammar rule. This differs from static priors, which assign each rule one context-independent score.

  • Search States: A search state is a partial program containing holes, and an expansion fills one hole with a grammar rule; only complete programs can be tested against the specification.The heuristic controls which expansions the search explores first.
  • Heuristic Requirements: The desired heuristic must condition expansion scores on the partial program, be cheap enough for millions of expansions, and keep every grammar rule reachable.The proposals are sampled once before search and serve as guidance rather than answers.
  • Heuristic Requirements: A context-aware heuristic H(r | p, Π) scores rule r for a partial program p using proposals Π, with the score depending on both p and r.This contrasts with a static grammar prior that gives each rule the same score wherever it is used.
  • Heuristic Requirements: The heuristic may reorder grammar exploration arbitrarily, but misleading proposals must delay rather than entirely hide a solution.This reachability requirement preserves a chance of solving tasks even when proposal guidance is wrong.

Narcissus

Narcissus samples and repairs LLM proposals once, mines recurring fragments, and guides enumerative synthesis with a context-aware heuristic without querying the LLM during search. Its heuristic combines context alignment, reusable sub-programs, proposal-suggested size, and a positive floor so search remains complete under weak proposals.

  • Pipeline: Narcissus samples proposals once, repairs them into syntax trees, mines recurring sub-programs as macro-rules, and compiles them into a search heuristic.The resulting search operates over an extended grammar containing the mined shortcuts.
  • Heuristic: The heuristic scores each grammar-rule expansion at an open position using three signals: prefix alignment, sub-program reuse, and regularization.Higher scores indicate more promising expansions, while each signal captures a distinct way proposals can inform the choice.
  • Heuristic: Prefix alignment uses the conditional share of proposals that continue with the same rule after matching the partial program’s surrounding context.A rule common overall receives no prefix support when it does not occur in the current context.
  • Heuristic: Sub-program reuse rewards rules that rebuild fragments recurring across proposals, including mined fragments, independently of their surrounding context.This helps when proposals share local pieces but assemble them into different overall structures.
  • Heuristic: Regularization favors program sizes near those of repaired proposals, while the positive floor C > 0 keeps every grammar rule reachable.When proposals provide no signal, all expansions receive the floor and search degenerates to unguided enumeration.
  • Search backends: The heuristic guides both genetic top-down search and cost-based bottom-up beam search, with subtree mutation sampling rules from the context-weighted distribution.Genetic mutation can preserve useful fragments while changing the surrounding structure; the beam caps memory while reaching deeper programs under a limited budget.

Experimental Evaluation

Across five domains and two search backends, Narcissus consistently outperforms static LLM guidance, remains safe with weak proposals, and reaches proposal-like programs faster.

  • Overall evaluation: Narcissus beats static LLM-guided synthesis across five domains and under both bottom-up beam and genetic top-down search.The evaluation spans SLIA, BV, DeepCoder, ARC, and ARGA, with shared proposal and per-task budgets.
  • RQ1: Context-aware guidance: At every SLIA enumeration budget, Narcissus outperforms the static prior under both backends and both proposal models.With only 25 DeepSeek proposals per task, it remains robust while static guidance degrades.
  • RQ1: Context-aware guidance: 41.8 SLIA tasks are solved on the full 100-task set, versus about 28 by fragments alone and 28.4 by a static prior.This isolates context-aware guidance as the main source of the gain rather than proposal-mined fragments alone.
  • RQ1: Weak proposals: 350 of 587 BV tasks are solved by Narcissus, compared with 302 by unguided enumeration, while static priors solve 102 or 57.Regularization keeps rules reachable, preventing weak proposals from turning guidance into a restrictive constraint.
  • RQ2: Ablations: Prefix alignment is decisive for weaker DeepSeek proposals, whereas sub-program reuse becomes load-bearing for larger GPT-4o proposals.Regularization alone approximates unguided enumeration, and no single signal dominates across proposal qualities.
  • RQ3: Search efficiency: Narcissus reaches the proposal region about 12× sooner than the static heuristic on SLIA with DeepSeek proposals.It concentrates enumeration near proposal-indicated sizes, unlike BFS’s tiny-program bias and the static prior’s long tail.
  • RQ4: Proposal quality: 47% of SLIA tasks are solved from DeepSeek proposals with Narcissus, exceeding direct GPT-4o sampling at 31% and DeepSeek sampling at 20%.Narcissus also matches the static prior on GPT-4o proposals and gains more in AUC than in final count.

Related Work

Prior approaches either repeatedly query an LLM, embed it inside search, or compile context-free guidance that loses structural placement and misses unseen rules.

  • LLM-in-the-loop alternatives: Sample-and-check and self-repair approaches keep drawing from models unfamiliar with the target language and do not systematically search it.Re-prompting fixes syntax only partially and gains little on correctness in the described baseline.
  • LLM-in-the-loop alternatives: LLM-embedded symbolic search restores systematic search but requires model calls that grow with search effort.Narcissus replaces those repeated calls with tree lookups after one proposal-sampling stage.
  • Static approximations: Static LLM approximations compile sampled programs into fixed guidance, while related methods use grammar-repaired seeds or whole-program similarity.These approaches differ from Narcissus’s context-aware expansion scoring.
  • Learned search heuristics: Earlier learned heuristics can condition probabilities on surrounding structure but generally lack knowledge of the current task.Their training or adaptation is not based on the task-specific proposal set in the way Narcissus is.

Conclusion and Future Work

Narcissus converts LLM proposals into context-aware, reusable search guidance without querying the model during search, while leaving several extensions open.

  • Conclusion: Narcissus asks where a grammar rule occurs, rather than only how often it occurs, and never prunes rules from search.This lets it correct poor proposals while retaining complete grammar reachability.
  • Future work: Future work could learn per-task signal weights from proposal size and agreement instead of fixing all three weights equally.The current weights are fixed at one, and the authors suggest adapting them to which signals a task supports.
  • Future work: Sharing mined fragments across tasks could turn per-task grammar extensions into a reusable library.The paper currently discards mined fragments after each task.
  • Conclusion: The method applies wherever an LLM can propose but cannot reliably produce grammatical programs, offering a cheap alternative to keeping it in the search loop.The supported scope is proposal-guided synthesis over a fixed grammar and specification.
  • Proposal protocol: The proposal prompt requires syntactically valid DSL programs satisfying all examples and forbids calls outside the supplied grammar.It also instructs the model to prefer simple correct programs and output only the program.
  • Re-prompting protocol: The re-prompting baseline feeds failing proposals and execution feedback back to the LLM for up to three correction rounds.The framing distinguishes ungrammatical programs from grammatical programs with wrong outputs.

C Raw Proposal Accuracy

Table 3 measures raw proposal accuracy by domain and proposal model, distinguishing all proposals from those syntactically valid in the target grammar. The valid-proposal block is the appropriate baseline for search results.

  • Proposal accuracy: The lower block counts only proposals syntactically valid in the target grammar.This is the accuracy against which search results should be compared.
  • Interpretation: Figure 4 illustrates why rule frequencies alone cover programs of many sizes, whereas proposal locations preserve rules in their places and at their sizes.The search region must remain open because a solution may require a rule absent from the proposals.
  • Proposal accuracy: Table 3 reports the number and share of tasks solved by at least one proposal among the first k proposals or all available proposals.The “all” row uses every available proposal.
  • Coverage scope: Proposal coverage is reported separately by domain and proposal model, with N indicating the number of tasks for which proposals were collected.Collected-task counts can exceed the evaluation subsets used in experiments.

D Hyperparameter Selection

Narcissus selects one configuration through small sweeps on SLIA and reuses it unchanged across domains. Equal signal weights and a genetic population of 50 provide the chosen trade-offs.

  • Selection procedure: Both free hyperparameters are tuned by small SLIA sweeps and then reused unchanged in every other domain.Reported results therefore use one domain-independent configuration.
  • Signal weights: Setting wprefix, wreuse, wreg, and C to 1 solved the most tasks throughout the signal-weight sweep.No skewed assignment consistently improved over equal weighting of the three signals.
  • Genetic population size: A genetic population size of 50 gave the best trade-off between final solve rate and running time.Larger populations solved marginally more tasks but exhausted the wall-clock budget on fewer tasks.
  • Beam pool: The beam-search backend uses a pool of 1000 to match the beam width used for comparison with HySynth’s unbounded queue.

E Additional Results: Solve Curves

The additional results provide cumulative solve curves across domains, proposal models, and search settings. Curves are shown against both enumerated-program and wall-clock budgets, with stochastic genetic results averaged over five seeds.

  • Curve presentation: Cumulative solve curves use programs enumerated and wall-clock time as separate budget axes.Program counts are implementation- and hardware-independent, while wall-clock time includes each method’s guidance cost.
  • Curve presentation: Stochastic genetic-method curves report means over five seeds with shaded bands showing spread across seeds.
  • DeepCoder and HySynth: Figures 5 and 6 cover DeepSeek proposals on 100 DeepCoder tasks and the 70-task HySynth subset under both proposal models.Figure 6 is the wall-clock counterpart of Figure 2(a).
  • BV: Figures 7 and 8 compare BV with and without the divide-and-conquer decomposition used in the main text.
  • Proposal models: Figure 9 compares DeepSeek and Haiku proposals on the 100-task DeepCoder benchmark.

E.4 RQ2: Signal Ablation

The ablation examines how Narcissus’s guidance signals relate to solve curves and normalized early-solving performance. AUC captures the average benchmark share solved across logarithmic budgets.

  • Signal ablation: Figure 10 reports the full signal ablation with one row per proposal model.Its reuse-only variant also mines recurring fragments into grammar macro-rules, so it is not equivalent to the static heuristic.
  • Additional domains: Figure 11 covers ARGA and Figure 12 covers full ARC over the Hodel grammar.Figure 11 is the wall-clock counterpart of Figure 2(b).
  • Evaluation metrics: A cumulative solve curve tracks the number of tasks solved against either programs enumerated or solving time.The budget ranges from 1 to 10^6 programs or 0.03s to the 300s timeout.
  • Evaluation metrics: AUC is the normalized area under the solve curve, representing the average benchmark share solved over log-budget.It weights each budget decade equally and rewards steeper rises.
  • Evaluation metrics: AUC is the only quantity comparable across domains because it is normalized for benchmark size and budget range.

F.2 Full AUC Tables

The full AUC tables and accompanying figures evaluate solving performance across enumeration and wall-clock budgets, showing Narcissus consistently ahead of static guidance and robust when proposal support is weak.

  • Bitvector: Narcissus remains above unguided enumeration on bitvector tasks, while static-prior variants fall below it when weak proposals omit useful grammar rules.This ordering largely persists without divide-and-conquer, although every method solves fewer tasks.
  • DeepCoder: Narcissus leads both static guidance and unguided enumeration on DeepCoder despite only 7% proposal support.The same ordering holds across DeepSeek and Haiku proposals and across both search backends.
  • Signal ablation: Signal ablations show that all heuristic signals contribute, but the load-bearing signal changes with proposal quality.Prefix alignment dominates under weaker DeepSeek proposals, whereas the strongest signal differs under stronger GPT-4o proposals.
  • ARC: On full ARC with the universal Hodel grammar, guided search solves tasks lacking any single correct grammar-valid proposal by assembling proposal fragments and partial structure.The figure compares Narcissus against the dotted baseline of correct, grammar-valid raw proposals.
Loading 2608.25657v1…