利用测试输入动态优化程序生成，提升真实场景下的准确率与效率。
Program Synthesis via Test-Time Transduction
- 在生成时主动使用测试输入，通过排除不一致假设来精炼候选程序。
- 在四个基准上显著提升准确率，减少LLM调用次数，效率更高。
- 适合需要高鲁棒性的实际应用，尤其训练数据有限的场景。
我们提出一种新的程序合成范式——归纳式程序合成，明确在合成过程中利用测试输入。以往基于自然语言或输入输出样例的方法通常依赖训练样本泛化，但在训练数据有限、测试输入包含各种边缘情况的真实场景中表现不佳。为此，我们设计了一个新框架，将合成视为在由程序输出定义的有限假设类上的主动学习过程。使用大语言模型（LLM）预测选定测试输入的输出，并剔除不一致的假设；测试输入通过贪心最大化最小算法选取，以最小化LLM查询次数。我们在Playgol、MBPP+、1D-ARC和MiniGrid上的程序世界建模四个基准上评估该方法。结果表明，该方法在准确率和效率上均有显著提升。代码已开源：https://github.com/klee972/SYNTRA。
原文摘要 · Abstract (English)
We introduce transductive program synthesis, a new formulation of the program synthesis task that explicitly leverages test inputs during synthesis. While prior approaches to program synthesis--whether based on natural language descriptions or input-output examples--typically aim to generalize from training examples, they often struggle with robustness, especially in real-world settings where training examples are limited and test inputs involve various edge cases. To address this, we propose a novel framework that improves robustness by treating synthesis as an active learning over a finite hypothesis class defined by programs' outputs. We use an LLM to predict outputs for selected test inputs and eliminate inconsistent hypotheses, where the inputs are chosen via a greedy maximin algorithm to minimize the number of LLM queries required. We evaluate our approach on four benchmarks: Playgol, MBPP+, 1D-ARC, and programmatic world modeling on MiniGrid. We demonstrate that our method significantly improves program synthesis in both accuracy and efficiency. We release our code at https://github.com/klee972/SYNTRA.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。