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 G and specification E for a handful of proposals Π , 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 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 G+ , scoring each expansion in its context, and returns the first candidate satisfying E .
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 106 -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 PG , drawn so that program size grows to the right; each dot is one program. Prompted once with G and 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-Chat) (N=42)
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%)
–
0 (0%)
2 (1%)
k=5
31 (15%)
13 (19%)
9 (1%)
6 (6%)
7 (7%)
0 (0%)
–
4 (2%)
6 (4%)
all
42 (20%)
22 (31%)
11 (1%)
7 (7%)
7 (7%)
0 (0%)
15 (15%)
7 (4%)
18 (11%)
Synth. valid only
k=1
18 (9%)
5 (7%)
6 (1%)
3 (3%)
3 (3%)
0 (0%)
–
0 (0%)
2 (1%)
k=5
19 (9%)
9 (13%)
9 (1%)
3 (3%)
3 (3%)
0 (0%)
–
4 (2%)
6 (4%)
all
22 (11%)
12 (17%)
11 (1%)
4 (4%)
3 (3%)
0 (0%)
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 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 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.
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 106 ), 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 106 ), 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 106 ), 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 106 ), 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.
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.
André G. Pereira, Augusto B. Corrêa, Jendrik Seipp
Federal University of Rio Grande do Sul · Brazil · University of Oxford +3
LLMs can solve program synthesis tasks but remain inefficient and unreliable on hard instances requiring large combinatorial search. Given a small set of reasoning traces, we use coding agents to compile them into reusable symbolic program synthesizers over constrained DSLs. The resulting solvers require no LLM calls at test time and are strong standalone systems: symbolic solver ensembles reach 91.3% accuracy on PBEBench-Lite and 84.7% on PBEBench-Hard, outperforming LLMs with test-time scaling for the latter by +16.3 percentage points at zero LLM inference cost. They also complement LLM search, improving PBEBench-Hard accuracy from 68.4% to 85.8% while reducing reported token usage by 78%, and raising SLR-Bench hard-tier accuracy from 34.4% to 58.0% in a neuro-symbolic hybrid setting. Compared to directly using coding agents as per-instance solvers, induced solvers are substantially more Pareto-efficient, amortizing a small one-time construction cost over many zero-token executions. Finally, most solvers transfer zero-shot to a real historical linguistics task - predicting sound changes in natural language data - reaching 80.1% accuracy under ensembling and recovering some plausible linguistic rules. Together, these results show that reasoning traces can be compiled into reusable symbolic solvers that solve many tasks directly, complement LLM inference on hard cases, and provide a scalable route to domain-general solver induction. We release code and data for reproducibility.
Atharva Naik, Yash Mathur, Prakam +2
Carnegie Mellon University · Independent Researcher
LLMs can generate programs for ARC-AGI-2 tasks, but the provided compute only allows a small number of attempts to generate, debug and validate solutions. Genetic algorithms can search and test many more programs, but random search rarely starts in a useful neighborhood of the solution space. We combine the two methods through a compact domain specific language (DSL). First, a quantized Qwen3.5-4B LLM generates an initial set of programs for each ARCAGI-2 task. Then, we use those programs to seed an initial population of starting programs, and use genetic algorithms to evolve these programs towards a solution to the given task. The DSL is designed such that every mutated program remains valid and can be executed. The initial programs proposed by the LLM solve 2 (3.3%) of the first 60 tasks of the ARC-2 public evaluation set. The genetic algorithm solves an additional 4, giving 6 correct test outputs in total (10.0%). If we try using evolving solutions without this LLM seeding, we do not arrive at any solutions at all. The results show that genetic search can improve programs generated by LLMs and produce additional correct solutions.