Interactive program induction method uses language model priors to query users efficiently
A new arXiv paper frames program induction as a Bayesian learning problem, deriving a greedy query algorithm that reportedly beats a language-model-only agent on CodeARC.
In plain words
Program induction means learning a rule from a handful of input-output examples, so users can show what they want instead of coding it. The catch is that many different programs can fit the same examples yet behave differently on new data. The authors propose an interactive method where the learner picks informative questions to ask a user, guided by a language model's expectations.
What was announced
The paper, whose abstract is the available source, treats recovery of a target program as concentrating posterior probability on it as more examples arrive. Because any finite set of examples is consistent with infinitely many programs that diverge on unseen inputs, the authors argue a Bayesian view is needed. In their interactive setting, the learner selects maximally informative inputs and queries an oracle, such as the user, for the outputs.
The authors derive a greedy query-selection algorithm and report a termination guarantee: it stops after a number of informative oracle queries that scales logarithmically with the inverse of the target program's prior probability, returning the target up to approximate equivalence when no other class outweighs it under the prior. The method uses a language model as the prior, relaxes program equivalence in a PAC-style way, and estimates the query objective via importance sampling. On the CodeARC benchmark, the authors report accuracy gains of up to 22 percentage points over a language-model-only agent while observing up to 10.5 fewer input-output examples.
What it does not show
- The evidence is the paper's abstract only; the full article, experimental setup and peer review status are not available, and the reported results are author claims not independently confirmed.
Sources
Source-support review completed 17 Nov 2026. This story was drafted with AI assistance and checked against retained source passages. Automated checking is not independent verification.
Coverage: arXiv: abstract.
Updates and corrections
No corrections so far.
First published 17 Nov 2026
New to the subject? AI from the Ground Up starts from the beginning.