Search papers, labs, and topics across Lattice.
This paper introduces Narcissus, a novel program synthesizer that leverages context-aware approximations of large language model (LLM) proposals to systematically explore the space of syntactically correct programs. By maintaining proposals as syntax trees and scoring expansions based on contextual relevance, Narcissus effectively addresses the limitations of traditional enumerative synthesizers that rely on rule frequencies, which often overlook critical syntactic constructs. The results demonstrate that Narcissus significantly outperforms existing methods, achieving a 40% success rate on ARC tasks compared to just 13% with raw LLM proposals, all while eliminating the need for LLM calls during the search process.
Narcissus achieves a 40% success rate on challenging ARC tasks by intelligently leveraging context-aware program proposals, far surpassing traditional methods that rely on static guidance.
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.
