基于语言模型先验的交互式程序归纳方法研究
Interactive Program Induction with Language Model Priors
AI 导读
一项 arXiv 预印本研究提出以贝叶斯视角处理从有限输入输出示例恢复程序的歧义问题,学习者主动选择信息量最大的输入并向用户等 oracle 查询输出。该贪心查询选择算法经证明在 O((1/γ)log 1/p⁰(f*)) 次查询后可返回目标程序,并用语言模型作为先验、以重要性采样估计查询目标。
正文 · 原文
Abstract:Program induction refers to the process in which a learner aims to recover a program from a few given input-output examples. This paradigm broadens programming access by letting users demonstrate the rule-based behavior they want to apply to unseen data, instead of having to implement it themselves. However, recovering a program from finite input-output examples is fundamentally ambiguous, as a finite set of input-output examples is theoretically consistent with infinitely many programs whose output diverges on unseen inputs. We view this problem from a Bayesian perspective, where, given a prior $p^0$ over programs, identifying the target program means concentrating posterior probability mass on it by observing additional input-output examples. In the interactive program induction setting, the learner chooses maximally informative inputs and queries an oracle, such as the user, for their outputs. We derive a greedy query-selection algorithm and show that it terminates after $\mathcal{O}(\frac{1}{\gamma}\log 1/p^0(f^\star))$ informative oracle queries, and returns the target program $f^\star$ up to approximate equivalence when no other class outweighs it under the prior. The algorithm uses a language model as the prior under a PAC-style relaxation of program equivalence, where the query-selection objective is estimated using importance sampling. On the CodeARC benchmark, the algorithm improves accuracy over the LM only agent by up to 22 percentage points while observing up to 10.5 fewer input-output examples.
| Comments: | Preprint. 28 pages, 5 figures, 9 tables |
| Subjects: | Computation and Language (cs.CL); Artificial Intelligence (cs.AI); Machine Learning (cs.LG) |
| ACM classes: | I.2.7; I.2.6; H.1.2 |
| Cite as: | arXiv:2611.18485 [cs.CL] |
| (or arXiv:2611.18485v1 [cs.CL] for this version) | |
| https://doi.org/10.48550/arXiv.2611.18485 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Robin Chan [view email]
[v1]
Fri, 13 Nov 2026 17:59:55 UTC (202 KB)
来源:arXiv cs.AI · arxiv.org