Narcissus: Program Synthesis Using Context-Aware LLM Approximations
作者: Tilman Hinnerichs, Sebastijan Dumancic, Neil Yorke-Smith
分类: cs.AI, cs.LG, cs.PL, cs.SE
发布日期: 2026-08-26
💡 一句话要点
提出Narcissus以解决编程语言固定任务的合成问题
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 程序合成 大型语言模型 上下文评分 编程自动化 智能编程助手
📋 核心要点
- 现有的编程合成方法在处理固定目标语言时，常常无法有效利用大型语言模型的能力，导致生成的程序不符合语法或规范。
- Narcissus通过保留提议的语法树，并在上下文中评分每个候选程序的扩展，确保错误提议不会完全遮蔽正确答案，从而提高合成效率。
- 在五个领域和两个搜索后端的实验中，Narcissus在每个预算下均超越静态指导，解决了40%的ARC任务，而原始提议仅解决了13%。
📝 摘要（中文）
大型语言模型（LLMs）在编程方面表现出色，但在目标语言固定的任务中表现不佳，常常导致程序违反语法或无法满足给定规范。现有的枚举合成器通过LLMs系统性地搜索语法正确的程序，但在处理LLM提议时，常常忽略了构造的上下文信息。本文提出的Narcissus合成器保留提议的语法树，并在上下文中对每个候选程序的扩展进行评分，确保错误的提议不会完全隐藏正确的解决方案。实验结果显示，Narcissus在多个领域和搜索后端中均优于静态指导，显著提高了程序合成的效率。
🔬 方法详解
问题定义：本文旨在解决在固定目标语言下，现有编程合成方法无法有效利用LLMs的能力，导致生成程序的语法错误和规范不符的问题。现有方法在处理LLM提议时，往往忽略了上下文信息，造成错误提议的影响被放大。
核心思路：Narcissus的核心思路是保留LLM提议的语法树结构，并在上下文中对每个候选程序的扩展进行评分。通过这种方式，错误的提议不会完全遮蔽正确的解决方案，而是延迟解决过程。
技术框架：Narcissus的整体架构包括提议生成、上下文评分和搜索策略三个主要模块。提议生成模块利用LLMs生成初步的程序提议，上下文评分模块对提议进行评分，搜索策略模块则负责在候选程序中寻找最佳解决方案。
关键创新：Narcissus的主要创新在于其上下文评分机制，该机制能够有效保留提议的语法树结构，并确保错误提议不会完全遮蔽正确答案。这与现有方法的静态指导形成了鲜明对比。
关键设计：在设计中，Narcissus引入了正则化项，确保每个规则都是可达的，从而避免错误提议的影响过于严重。此外，损失函数的设计也考虑了上下文信息的影响，使得评分更加准确。
🖼️ 关键图片
📊 实验亮点
在实验中，Narcissus在多个领域中表现优异，超越了静态指导，解决了40%的ARC任务，而原始提议仅解决了13%。此外，Narcissus在达到提议级程序时的效率提升达到了一个数量级，显示出其在编程合成领域的显著优势。
🎯 应用场景
Narcissus的研究成果在编程自动化、代码生成和软件开发工具等领域具有广泛的应用潜力。通过提高程序合成的效率和准确性，该方法可以帮助开发者更快速地生成符合特定语法和规范的代码，降低开发成本，提高生产力。未来，该技术可能会进一步推动智能编程助手的发展。
📄 摘要（原文）
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.