Interactive Program Induction with Language Model Priors
arXiv cs.AI · 14 Nov 2026, 03:59 AEST
The paper discusses interactive program induction, where a learner recovers a program from input-output examples. It presents a greedy query-selection algorithm that improves accuracy and reduces the number of examples needed.
Key facts
- Program induction refers to the process in which a learner aims to recover a program from a few given input-output examples.
- 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.
- We derive a greedy query-selection algorithm and show that it terminates after $ (rac{1}γ ext{log }1/p^0(f^ ext{star}))$ informative oracle queries, and returns the target program $f^ ext{star}$ up to approximate equivalence when no other class outweighs it under the prior.
- 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.
Read aloud
The paper discusses interactive program induction, where a learner recovers a program from input-output examples. It presents a greedy query-selection algorithm that improves accuracy and reduces the number of examples needed. Program induction refers to the process in which a learner aims to recover a program from a few given input-output examples. We view this problem from a Bayesian perspective, where, given a prior $p^zero$ over programs, identifying the target program means concentrating posterior probability mass on it by observing additional input-output examples. We derive a greedy query-selection algorithm and show that it terminates after $ rac one γ ext log one/p^zero f^ ext star $ informative oracle queries, and returns the target program $f^ ext star $ up to approximate equivalence when no other class outweighs it under the prior. On the CodeARC benchmark, the algorithm improves accuracy over the LM only agent by up to twenty two percentage points while observing up to ten point five fewer input-output examples.
Sources in this cluster
- Interactive Program Induction with Language Model Priors
arXiv cs.AI · 14 Nov 2026, 03:59 AEST