Narcissus: Program Synthesis Using Context-Aware LLM Approximations

Tilman Hinnerichs; Sebastijan Dumancic; Neil Yorke-Smith

cs.AIAug 26, 2026

Narcissus: Program Synthesis Using Context-Aware LLM Approximations

Authors: Tilman Hinnerichs, Sebastijan Dumancic, Neil Yorke-Smith

Organizations: Delft University of Technology, The Netherlands

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.

Figures & tables

Figure 1: Overview of the Narcissus pipeline (on the SLIA task of abbreviating names to initials). (1) The LLM is prompted once with the grammar

\mathcal{G}

and specification

\mathcal{E}

for a handful of proposals

\Pi

, which are neither guaranteed solutions nor grammatical (e.g. concat(true,".") ). (2) Proposals are parsed into abstract syntax trees (ASTs) and repaired against the grammar (syntactically wrong sub-terms become typed holes); (3) recurring fragments are mined into macro-rules, extending the grammar to

\mathcal{G}^{+}

; (4) the proposal ASTs yield a context-aware heuristic (prefix alignment along the root-to-hole path, where _ marks a position the context ignores; sub-program reuse; regularization); and (5) heuristic-based search (e.g., bottom-up or genetic) enumerates programs in

\mathcal{G}^{+}

, scoring each expansion in its context, and returns the first candidate satisfying

\mathcal{E}

Panel of Figure 2 — Figure 2: Tasks solved vs. programs enumerated, for GPT-4o (GPT, dashed) and DeepSeek-V4-Flash (DS, solid) proposals. In (a), Narcissus is above the static prior at every budget, under both backends and both proposal models, and its DS curve rivals the static prior on GPT-4o proposals. In (b), the same ordering holds on a second domain: Narcissus beats the static heuristic for both proposal models, well above the raw proposals (dotted).

Method (proposal model)	Solved (/70)	AUC
Narcissus + Genetic (GPT-4o)	51.4	32.2%
Narcissus + BUS (GPT-4o)	49.0	30.7%
Static + BUS (GPT-4o)	48.0	23.5%
Static + Genetic (GPT-4o)	32.2	18.2%
Narcissus + Genetic (DeepSeek)	32.6	17.4%
Narcissus + BUS (DeepSeek)	30.0	14.9%

Table 1: SLIA (70 tasks): GPT-4o vs. DeepSeek proposals, by final tasks solved and by normalized AUC over programs enumerated. Higher AUC is better; genetic rows are averaged over 5 seeds, and the best value per proposal model is in bold. At each proposal quality Narcissus has the highest AUC, its AUC lead over the static heuristic exceeds its final-count lead (it reaches solutions sooner), and Narcissus on DeepSeek proposals matches the static prior on GPT-4o proposals.

Signals enabled	DeepSeek (/100)	GPT-4o (/70)
prefix + reuse + reg.	45.8	51.4
reuse + reg.	24.0	47.2
prefix + reg.	42.8	31.4
prefix + reuse	43.6	47.0
prefix	43.2	25.4
reuse	20.0	44.2

Table 2: RQ2: ablation of the three heuristic signals, by SLIA tasks solved (genetic backend, means over 5 seeds; out of

100

tasks with DeepSeek and out of

70

with GPT-4o proposals). Rows list the signals left on ( prefix , reuse , reg. ); the top row is the full heuristic. Which signal is load-bearing inverts with proposal quality: prefix alignment under the weaker DeepSeek proposals, sub-program reuse under the stronger GPT-4o proposals; regularization alone approximates unguided enumeration. Solve curves for all variants are in the appendix (Figure 10 ).

Figure 3: Per-size enumeration profile on the SLIA task stackoverflow2 (GPT-4o proposals; grey bars mark the sizes of the

41

proposals that parse to concrete programs). BFS spends its

10^{6}

-program budget below size five, the static prior (full BUS and width-

1000

beam, dashed, coinciding) spreads it thinly up to size

195

, and Narcissus concentrates it on the sizes the proposals occupy, solving the task alone among the three.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Why we search around the proposals , on the SLIA task of Figure 1 . The grammar induces the program space

\mathcal{P}_{\mathcal{G}}

, drawn so that program size grows to the right; each dot is one program. Prompted once with

\mathcal{G}

and

\mathcal{E}

, the LLM returns a few raw proposals (1): wrong, sometimes ungrammatical, but sitting close together in a small region of the space. Scoring programs by how often their rules occur in the proposals (2) covers that region, but with it every program built from the same rules at every size, most of them far larger than anything the proposals suggest. What is worth enumerating instead is the region around the proposals (3): their rules, in their places, at their size. It has to stay open, because the solution (4) can need a rule the proposals never used.

Group	$k$	SLIA (DeepSeek-Chat) (N=205)	SLIA (GPT-4o) (N=70)	BV (DeepSeek-Chat) (N=753)	DC (DeepSeek-Chat) (N=100)	DC (Haiku) (N=100)	ARC (DeepSeek-Reasoner) (N=100)	ARGA (DeepSeek-Chat) (N=160)	ARGA (GPT-4o) (N=160)
All proposals	$k=1$	27 (13%)	8 (11%)	6 (1%)	3 (3%)	6 (6%)	–	0 (0%)	2 (1%)
	$k=5$	31 (15%)	13 (19%)	9 (1%)	6 (6%)	7 (7%)	–	4 (2%)	6 (4%)
	all	42 (20%)	22 (31%)	11 (1%)	7 (7%)	7 (7%)	15 (15%)	7 (4%)	18 (11%)
Synth. valid only	$k=1$	18 (9%)	5 (7%)	6 (1%)	3 (3%)	3 (3%)	–	0 (0%)	2 (1%)
	$k=5$	19 (9%)	9 (13%)	9 (1%)	3 (3%)	3 (3%)	–	4 (2%)	6 (4%)
	all	22 (11%)	12 (17%)	11 (1%)	4 (4%)	3 (3%)	13 (13%)	7 (4%)	18 (11%)

Appendix

Table 3: Raw proposal accuracy per domain and proposal model. We report the number (and share) of tasks for which at least one of the first

k

proposals satisfies all examples; “all” uses every available proposal. The lower block counts only proposals that are syntactically valid in the target grammar, i.e. the language the synthesizer must search, which is the accuracy the search results should be compared against.

N

is the number of tasks for which proposals were collected from that model; it can exceed the evaluation subsets used in the experiments (e.g. DeepSeek proposals cover all

205

SLIA tasks while the search experiments use the standard

100

-task subset, and the GPT-4o column covers the

70

-task subset released with HySynth; the ARC (DeepSeek-Chat) column covers the

42

tasks prompted for that model). The ARC (DeepSeek-Reasoner) column covers the canonical

100

-task subset used for the full-ARC RQ1 experiment (Figure 12 ); only the “all” row is available for this subset, since the

k=1

k=5

breakdown has not been recomputed for it.

Figure 5: RQ1, full 100-task SLIA (DeepSeek proposals): tasks solved vs. programs enumerated (left) and vs. wall-clock time (right). With the same backend, Narcissus dominates the static prior at every budget on both axes, and reaches solutions orders of magnitude earlier than the static heuristic. The raw grammar-valid proposals (dashed) are shown for reference. The ordering is unchanged when guidance is charged for its own runtime, so the gain is not an artifact of counting enumerations only.

Figure 6: RQ1/RQ4, SLIA 70-task subset: GPT-4o vs. DeepSeek proposals, by programs enumerated (left) and wall-clock time (right). This is the time-axis counterpart of Figure 2 (a). At each proposal quality Narcissus leads under both backends, and Narcissus on the DeepSeek proposals rivals the static prior on the GPT-4o proposals.

Figure 7: RQ1, BV with divide-and-conquer (weak proposals): programs enumerated (left) and wall-clock time (right). Narcissus stays above unguided enumeration, while both static-prior variants collapse far below it, because they effectively prune the rules the weak proposals never mention. This is the core robustness result behind the claim that Narcissus ’s floor is plain enumeration. The unguided baseline enumerates the extended grammar

\mathcal{G}^{+}

, so it is not handicapped relative to the guided methods.

Figure 8: RQ1, BV without divide-and-conquer (plain synthesizer): programs enumerated (left) and wall-clock time (right). Without the divide-and-conquer decomposition every method solves far fewer of the

587

tasks, so the y-axis is clipped at

48

to keep the curves legible; the ordering of Figure 7 is largely preserved, with Narcissus remaining close to or above unguided enumeration while the static priors fall clearly below it. As in Figure 7 , the unguided baseline enumerates the extended grammar

\mathcal{G}^{+}

Figure 9: RQ1, DeepCoder (

100

tasks), DeepSeek vs. Haiku proposals: programs enumerated (left) and wall-clock time (right). DC has weak proposal support (

7\%

, Table 3 ), yet the RQ1 ordering holds for both proposal models and under both backends: Narcissus leads, the static prior trails, and unguided enumeration is the floor.

Panel of Figure 10 — Figure 10: RQ2: SLIA signal ablation (genetic backend) under weaker DeepSeek (top, 100 tasks) and stronger GPT-4o (bottom, 70 tasks) proposals, by programs enumerated (left) and wall-clock time (right). Every signal contributes but none accounts for the full heuristic, and which signal is load-bearing inverts with proposal quality: under the weaker DeepSeek proposals prefix alignment dominates, since removing it costs the most and it alone recovers almost the full heuristic, whereas under the stronger GPT-4o proposals sub-program reuse takes over that role instead. This is why Narcissus carries all three: they cover the full range of proposal support rather than any one succeeding everywhere.

Figure 11: RQ1, ARGA (

160

tasks), GPT-4o vs. DeepSeek proposals: programs enumerated (left) and wall-clock time (right). The left panel is the time-axis counterpart of Figure 2 (b). Under divide-and-conquer, Narcissus beats HySynth for both proposal models and stays well above the raw proposals (dotted).

Figure 12: RQ1, full ARC with the universal Hodel grammar (DeepSeek-Reasoner proposals): programs enumerated (left) and wall-clock time (right). This is the weakest-support setting in the paper. Narcissus rises well above the dotted line marking the proposals that are both correct and grammar-valid, i.e. guided search solves ARC tasks for which not a single grammar-valid proposal is correct: the proposals contribute fragments and partial structure, and the search assembles and corrects them.

Method	Final solved	AUC (% of universe)
Narcissus + Genetic (DeepSeek)	41.8	22.1%
HySynth (static + BUS) (DeepSeek)	38.0	18.2%
Static + Genetic (DeepSeek)	28.4	17.8%
Narcissus + BUS (DeepSeek)	40.0	16.5%
BFS (enhanced grammar)	28.0	16.1%
BFS (plain grammar)	22.0	13.3%

Appendix

Table 4: RQ1, SLIA (DeepSeek) : Enumeration axis AUC (programs enumerated, 1 to

10^{6}

), out of 100 problems.

Method	Final solved	AUC (% of universe)
Narcissus + Genetic (DeepSeek)	41.8	31.2%
Narcissus + BUS (DeepSeek)	40.0	24.2%
HySynth (static + BUS) (DeepSeek)	38.0	20.7%
Static + Genetic (DeepSeek)	28.4	19.0%
BFS (enhanced grammar)	28.0	18.7%
BFS (plain grammar)	22.0	15.1%

Appendix

Table 5: RQ1, SLIA (DeepSeek) : Time axis AUC (solving time, 0.03s to 300s (timeout)), out of 100 problems.

Method	Final solved	AUC (% of universe)
Narcissus + Genetic (GPT-4o)	51.4	49.6%
Narcissus + BUS (GPT-4o)	49.0	47.3%
HySynth (static + BUS) (GPT-4o)	48.0	36.9%
Narcissus + Genetic (DeepSeek)	32.6	29.4%
Static + Genetic (GPT-4o)	32.2	25.0%
Narcissus + BUS (DeepSeek)	30.0	24.8%

Appendix

Table 6: RQ1, SLIA: LLM comparison (GPT-4o vs. DeepSeek) : Time axis AUC (solving time, 0.03s to 300s (timeout)), out of 70 problems.

Method	Final solved	AUC (% of universe)
Narcissus + BUS	350.0	33.2%
Narcissus + Genetic	349.4	28.8%
BFS (unguided enumeration)	300.0	27.5%
HySynth (static + BUS)	102.0	8.8%
Static + Genetic	56.6	4.8%

Appendix

Table 7: RQ1, PBE_BV_Track_2018 (bitvector), divide-and-conquer : Enumeration axis AUC (programs enumerated, 1 to

10^{6}

), out of 587 problems.

Method	Final solved	AUC (% of universe)
Narcissus + BUS	350.0	60.7%
BFS (unguided enumeration)	300.0	51.6%
Narcissus + Genetic	349.4	42.8%
HySynth (static + BUS)	102.0	16.0%
Static + Genetic	56.6	7.6%

Appendix

Table 8: RQ1, PBE_BV_Track_2018 (bitvector), divide-and-conquer : Time axis AUC (solving time, 0.03s to 300s (timeout)), out of 587 problems.

Method	Final solved	AUC (% of universe)
Narcissus + Genetic	32.8	2.8%
Narcissus + BUS	26.0	2.6%
BFS (unguided enumeration)	27.0	2.5%
Static + Genetic	24.0	1.9%
HySynth (static + BUS)	18.0	1.8%

Appendix

Table 9: RQ1, PBE_BV_Track_2018 (bitvector), regular : Enumeration axis AUC (programs enumerated, 1 to

10^{6}

), out of 587 problems.

Method	Final solved	AUC (% of universe)
BFS (unguided enumeration)	27.0	3.8%
Narcissus + Genetic	32.6	3.4%
Narcissus + BUS	26.0	3.0%
Static + Genetic	24.0	2.3%
HySynth (static + BUS)	18.0	2.0%

Appendix

Table 10: RQ1, PBE_BV_Track_2018 (bitvector), regular : Time axis AUC (solving time, 0.03s to 300s (timeout)), out of 587 problems.

Method	Final solved	AUC (% of universe)
Narcissus + Genetic (DeepSeek)	32.6	19.8%
Narcissus + Genetic (Haiku)	30.6	19.7%
Narcissus + BUS (DeepSeek)	28.0	17.5%
Narcissus + BUS (Haiku)	26.0	16.5%
HySynth (static + BUS) (Haiku)	22.0	14.8%
HySynth (static + BUS) (DeepSeek)	20.0	13.6%

Appendix

Table 11: RQ1, DeepCoder: LLM comparison (DeepSeek vs. Haiku) : Enumeration axis AUC (programs enumerated, 1 to

10^{6}

), out of 100 problems.

Method	Final solved	AUC (% of universe)
Narcissus + Genetic (DeepSeek)	32.6	22.1%
Narcissus + Genetic (Haiku)	30.6	20.9%
Narcissus + BUS (DeepSeek)	28.0	18.9%
Narcissus + BUS (Haiku)	26.0	17.4%
HySynth (static + BUS) (Haiku)	22.0	15.6%
HySynth (static + BUS) (DeepSeek)	20.0	14.1%

Appendix

Table 12: RQ1, DeepCoder: LLM comparison (DeepSeek vs. Haiku) : Time axis AUC (solving time, 0.03s to 300s (timeout)), out of 100 problems.

Program Synthesis

Program synthesis automatically constructs executable programs from examples, specifications, demonstrations, or natural-language descriptions.

See all 182 papers

Property-Guided LLM Program Synthesis for Planning
May 15, 2026André G. Pereira, Augusto B. Corrêa, Jendrik SeippSymbolic Planning Counterexample-Guided Refinement
Federal University of Rio Grande do Sul · Brazil · University of Oxford +3
ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis
May 6, 2026Atharva Naik, Yash Mathur, Prakam +2Symbolic Reasoning LLM-Based Program Synthesis
Carnegie Mellon University · Independent Researcher
Combining LLMs and Genetic Search for ARC-AGI-2
Sep 23, 2026Val DyachenkoLarge Language Model-Guided Optimization Genetic Programming

May 15, 2026J/K move · Enter open · S save

Property-Guided LLM Program Synthesis for Planning

André G. Pereira, Augusto B. Corrêa, Jendrik Seipp

Federal University of Rio Grande do Sul · Brazil · University of Oxford+3

Symbolic Planning Counterexample-Guided Refinement LLM-Based Program Synthesis Program Synthesis Compiler-Guided Program Synthesis

Open paper AskPDF arXiv

LLMs have shown impressive success in program synthesis, discovering programs that surpass prior solutions. However, these approaches rely on simple numeric scores to signal program quality, such as the value of the solution or the number of passed tests. Because a score offers no guidance on why a program failed, the system must generate and evaluate many candidates hoping some succeed, increasing LLM inference and evaluation costs. We study a different approach: property-guided LLM program synthesis. Instead of scoring programs after evaluation, we check whether a candidate satisfies a formally defined property. When the property is violated, we stop the evaluation early and provide the LLM with a concrete counterexample showing exactly how the program failed. This feedback drastically reduces both the number of program generations and the evaluation cost, and can guide the LLM to generate stronger programs. We evaluate this approach on PDDL planning domains, asking the LLM to synthesize direct heuristic functions: every state reachable by strictly improving transitions has a strictly improving successor. A heuristic with this property leads hill-climbing algorithm directly to a goal state. A counterexample-guided repair loop generates one candidate program, checks the property over a training set, and returns the first case that violates the property. We evaluate our approach on ten planning domains with an out-of-distribution test set. The synthesized heuristics are effectively direct on virtually all test tasks, and compared to the best prior generation method our approach generates seven times fewer programs per domain on average, solves more tasks without using search, and requires several orders of magnitude less computation to evaluate candidates. Whenever a problem admits a verifiable property, property-guided LLM synthesis can reduce cost and improve program quality.

Abstract

Program Synthesis

Explore similar work

Property-Guided LLM Program Synthesis for Planning

ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis

Combining LLMs and Genetic Search for ARC-AGI-2