cs.CLNov 13, 2026

Interactive Program Induction with Language Model Priors

Authors: Robin Shing Moon Chan, Ryan Cotterell

Organizations: ETH Zürich

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 p0p^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 O(1γlog⁡1/p0(f⋆))\mathcal{O}(\frac{1}γ\log 1/p^0(f^\star)) informative oracle queries, and returns the target program f⋆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.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Induction and Inquiry via Probabilistic Reasoning over Language and Code

    Sep 1, 2026Wasu Top Piriyakulkij, Sam Acquaviva, Cassidy Langenfeld +2Cognitive ModelingActive Learning

  2. Measuring in-context algorithmic reasoning in language models against an exact Bayes-optimal standard

    Aug 3, 2026Hector Zenil, Luan OzelimLLM EvaluationBayesian Inference

  3. PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics

    May 29, 2025Atharva Naik, Prakam, Yash Mathur +6Program SynthesisInductive Inference