用上下文感知的语法树改进大模型编程合成，让错误提案不掩盖解法。
Narcissus: Program Synthesis Using Context-Aware LLM Approximations
- 保留大模型生成的语法树，按上下文评分候选程序扩展
- 在五类任务中比静态引导快10倍，解决40%的ARC任务
- 无需搜索时调用大模型，适合高精度编程合成场景
大语言模型在编程上表现优异，但当任务限定目标语言时，若该语言结构在训练数据中罕见，其生成的程序常违反语法规则或无法满足规范。现有枚举式合成器通过将大模型建议近似为规则频次来引导搜索，但会丢失各构造成分的位置信息，并在建议遗漏规则时将其完全剪枝，恰好在大模型出错时发生。我们提出Narcissus，它保留大模型建议的语法树，基于上下文评估候选程序的每一步扩展：相同上下文下的建议是否延续相同模式？扩展是否重建了建议中重复的片段？引入正则化项确保每个规则都可被访问，使错误建议仅延迟求解，而不会隐藏解。在五个领域和两种搜索后端上，Narcissus在所有预算下均优于静态引导，且持续超越重新提示大模型修正自身建议的效果；它比原始建议提前一个数量级达到类似质量的程序，解决了40%的ARC任务（原始建议仅13%），整个搜索过程无需任何一次大模型调用。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。