Narcissus：基于上下文感知LLM近似的程序合成

大语言模型（LLM）擅长编程，但当任务指定目标语言时则不然：当提示中的语法在其训练数据中罕见时，其程序通常违反语法或无法满足给定规格。枚举式合成器在大语言模型引导下系统搜索语法正确的程序空间；最先进方法将LLM提议近似为规则频率来引导搜索，这会丢失每个构造所处的位置信息，并在提议恰好出错时把所有未被提议覆盖的规则剪枝掉。我们提出Narcissus，一个把提议保留为语法树并在上下文中为候选程序每次扩展打分的合成器：具有相同周围结构的提议是否以同样方式延续？该扩展是否重建了提议中重复出现的片段？一个正则项保证每条规则都保持可达，因此错误的提议只会延迟求解而无法把解隐藏掉。跨五个领域与两种搜索后端，Narcissus在所有预算下都胜过静态引导，并持续优于让LLM重新提示以修复自身提议的做法；它提前一个数量级得到与提议质量相当的程序，并在ARC任务上解决40%的任务（原始提议仅解决13%），且搜索期间不调用任何LLM。