acceptodds
Under review as a conference paper at ICLR 2027

Interactive Program Induction

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 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 identifies a target program up to approximate equivalence after informative oracle queries. 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.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
program induction, Bayesian active learning, large language models

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_4CyWOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes an information-theoretic framework for interactive program induction, where the goal is to recover an unknown program through input–output queries to an oracle. The method treats an LLM as a prior and proposal distribution over candidate programs, approximates the posterior using importance sampling, and groups programs into approximate equivalence classes based on their outputs on a finite evaluation set. At each iteration, it selects a query by maximizing expected information gain (EIG), eliminates inconsistent hypotheses, and terminates when an equivalence class reaches majority posterior mass. The paper also provides theoretical guarantees on query complexity and approximate correctness.

Critical strengths

The paper addresses a meaningful problem in interactive program synthesis and presents a unified Bayesian formulation of program induction with oracle feedback.

Critical weaknesses
  1. Insufficient comparisons with stronger query-selection baselines.

My primary concern is the lack of comparisons with more sophisticated query-selection strategies beyond uncertainty, diversity, and random selection. Table 1 primarily compares the proposed method against an LM-only agent (which is not using any query selection), which I do not find sufficiently convincing as the main baseline for establishing the practical significance of the proposed approach.

Furthermore, even the simplest query-selection strategies, such as uncertainty, diversity, and random selection, already provide substantial improvements over the LM-only baseline.

Interactive program synthesis and active learning have been extensively studied, and I suspect that stronger query-selection algorithms are available in the existing literature. The paper would benefit from more comprehensive discussions and comparisons with related work, including, but not limited to, 'Question Selection for Interactive Program Synthesis' (which is already cited but not sufficiently discussed) and 'Program Synthesis via Test-Time Transduction.'

Without such comparisons, it is difficult to assess whether the proposed method offers a meaningful improvement over established query-selection techniques.

  1. Limited methodological novelty and practical gains beyond established formulations.

A substantial portion of the paper is devoted to developing a Bayesian formulation of interactive program induction. However, Bayesian inference, posterior updating, and information-gain-based query selection are already well-established concepts.

If the authors can clarify a sufficiently distinctive methodological contribution relative to prior work, or demonstrate compelling practical advantages arising specifically from the proposed formulation, I would be willing to reconsider my assessment and raise my score.

Questions for authors

Comparison with stronger baselines: Why does the paper primarily compare against relatively simple query-selection strategies? Have the authors considered more sophisticated methods from interactive program synthesis and active learning, such as those discussed in Question Selection for Interactive Program Synthesis? How would the proposed EIG method compare against these approaches under the same experimental setting?

Novelty of the Bayesian formulation: What is the key methodological contribution that distinguishes the proposed framework from existing Bayesian active learning and information-gain-based query-selection methods? In particular, which aspects of the formulation or theoretical analysis are fundamentally new, rather than adaptations of established results?

2 comments

We thank the reviewer for taking the time to engage with our work! We appreciate the positive feedback about the problem’s meaningfulness. We address the reviewer’s concerns below:

  1. Methodological contributions: The core contribution of the paper is not the use of EIG for information gathering, which has been extensively studied (introduction/RW). For program induction in Turing-complete languages (such as Python), this formulation runs into two issues, and we address both: (a) the posterior over an infinite program space can neither be computed nor sampled exactly, and (b) infinitely many programs compute the same function, so identifying the target requires program equivalence, which is undecidable. Prior work does not address either. Ji et al. (2020) and Tiwari et al. (2020) limit their analysis to a finite hypothesis space. Kobalczyk et al. (2025) and Lee et al. (2025) drop the prior and weight language model samples uniformly, so their information gain is taken under the language model's sampling distribution, not the posterior. We use a language model prior with equivalence on inputs drawn from the input distribution to make interactive induction over a general-purpose language a well-posed Bayesian inference problem. Equivalence on drawn inputs is now decidable, which makes identifying the target well-defined, and yields a PAC bound on the returned program (Prop. 2.1). We further approximate the posterior by importance sampling from a language model proposal conditioned on the observed examples, which makes the EIG computable from the weighted samples. For the rebuttal, we ran our method with uniform weights on all six models (3 seeds), and our importance weighting requires up to 2.5 fewer input-output examples (p < .001, paired sign test; App. E.4 of the revised paper). We updated the related work accordingly and added an explicit list of contributions to the introduction.

  2. Which theoretical results are fundamentally new: Thm. 3.1 extends the greedy analysis of Dasgupta (2004) from finite hypothesis classes to an infinite program space. The remaining results are new to the best of our knowledge. Thm. 3.2 bounds the number of queries per instance for any selection rule, and states exactly when a wrong class is returned, namely when a class with more prior mass stays consistent with every query. Combined with Prop. 2.1, this bounds both the number of queries and the error of the returned program on unseen inputs. The guarantee also predicts that the evaluation set size trades off query cost against correctness, which we confirm empirically (RQ3).

  3. Comparison to stronger query-selection baselines: The LM-only agent selects its own queries and is the established CodeARC baseline. The random, uncertainty, and diversity strategies run within our framework, so their improvements over the LM-only agent are an effect of it. For the rebuttal, we ran experiments with minimax selection with uniform weights (Ji et al., 2020), which corresponds to the maximin selection of Lee et al. (2025), and EIG with uniform weights (Kobalczyk et al., 2025). We port only their selection rules into our framework, since the original methods rely on a finite program space (Ji et al.) or a fixed number of queries (Kobalczyk et al.). On Llama3.2-3B, Llama3.1-8B and Qwen2.5-32B (3 seeds), our method requires up to 0.9 fewer input-output examples than minimax and up to 2.1 fewer than EIG with uniform weights on all three (p < .01, paired sign test), at no significant difference in accuracy (App. E.4 of the revised paper). We added this discussion to the related work.

  4. Practical advantages: Our method improves accuracy over the LM-only agent by up to 22 percentage points with up to 10.5 fewer input-output examples (Table 1). Our importance weights require fewer oracle calls than the uniform weighting used in the literature (points 1 and 3). EIG asks the most informative queries and terminates in the fewest rounds among random, diversity, and uncertainty selection (RQ2). For the rebuttal, we also ran a compute-matched propose-and-verify baseline without oracle queries for all six models (3 seeds), which our method outperforms by up to 12 accuracy points, significantly on five of six (p < .01, paired sign test; App. E.4 of the revised paper). Our theory also carries over to practice. The per-instance bound of Thm. 3.2 holds empirically (App. E). Our stopping criterion is adaptive, where Kobalczyk et al. (2025) fix the number of queries. The evaluation set size lets practitioners trade off query cost against the error guarantee (RQ3).

We hope that these additional clarifications and results address the reviewer’s concerns!

Thank you for the response.

As, comparison to stronger query-selection baselines yields 'up to 0.9 fewer input-output examples than minimax and up to 2.1 fewer than EIG with uniform weights' (in part 3 of the response) makes the contribution questionable. Also, practical advantages (in part 4 of the response) is claiming a 10.5 fewer io examples required with table 1, but, it's again, not comparing with stronger baselines.

Therefore, I retain my assessment.

Reviewer_jU2iOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers the problem of synthesizing programs from input-output examples. In the interactive setting of this problem, the learner chooses the inputs on which an oracle returns an answer (in the spirit of the oracle-guided program synthesis work).

The paper proposes a greedy strategy where the learner picks the most informative input in each round. The paper establishes some theoretical bounds, based on certain assumptions. The information gain is estimated using sampling over the space of programs.

In the experiments, a language model is used as the program synthesizer, and results are reported on CodeARC benchmark, with reports of gains in accuracy and reduction in query rounds.

Critical strengths
  • The results presented in the paper are sound.
  • The findings are mostly inline with the prevailing understanding in the field of inductive program synthesis.
Critical weaknesses
  • The results are unfortunately not new. An arxiv paper from many years back titled "Information-theoretic user interaction" makes the same points for interactive program induction, including the idea of greedy selection of inputs and the use of weighted set of programs samples. The main difference is that rather than use a language model, a symbolic representation of the space of all consistent programs was used in that work. The findings are similar, although the evaluation and datasets are different (language models definitely help in allowing us to go beyond simple programs).

  • Proposition 2.1: It is not clear why/how 1/p(f) takes the place of what should have been the size of the hypothesis space H. If p(f) is the min support probability for any f, then I agree that 1/p(f) is a bound for |H|, but that is not what it is. I looked at the proof in Appendix C and it didn't help.

Questions for authors

The main question is what are the new findings here?

1 comment

We thank the reviewer for taking the time to engage with our work! We appreciate the positive comments about the soundness of the presented results. We address the reviewer’s concerns below:

  1. Novelty wrt Tiwari et al.: We thank the reviewer for sharing this reference, which we now include. We agree that greedy entropy-based selection is not new. However, Tiwari et al. operate in a hand-designed, non-Turing-complete DSL for string transformations, where the consistent programs form a finite set stored in a version space and sampled directly. We instead perform interactive program induction over a general-purpose language (Python), where consistent programs can’t be enumerated, and the information gain criterion is intractable. We approximate the posterior under a language model prior by importance sampling, and provide theoretical query-complexity guarantees (cf. Thms. 3.1 and 3.2), which hold in practice, and PAC guarantees on the returned program, which Tiwari et al. do not. We now state the points of differentiation more clearly in the related work and in the contributions of the introduction.

  2. Proposition 2.1: Our hypothesis space H\mathcal{H}, the set of all Python programs, is countably infinite, so ∣H∣|\mathcal{H}| is infinite and any bound in terms of ∣H∣|\mathcal{H}| is vacuous. The stated proposition is the standard Occam bound for this case (cf. Blumer et al. 1987), which splits the failure probability δ\delta across programs in proportion to the prior, δ⋅p0(f)\delta \cdot p^0(f), instead of uniformly δ/∣H∣\delta/|\mathcal{H}|. This yields ln⁡(1/p0(f))\ln(1/p^0(f)) instead of ln⁡∣H∣\ln|\mathcal{H}|, and the union bound still sums to at most δ\delta because the prior sums to at most 1. We added this explanation to the proof in App. C!

  3. New findings: (i) A language model prior with equivalence on inputs drawn from the input distribution makes interactive induction over a general-purpose language a well-posed Bayesian inference problem. Since the posterior over the infinite program space can neither be computed nor sampled directly, we approximate it by importance sampling from a language model proposal conditioned on the observed examples. For the rebuttal, we ran our method with uniform weights on all six models (3 seeds), and our importance weights require up to 2.5 fewer input-output examples (p < .001, paired sign test; App. E.4 of the revised paper). (ii) Greedy information gain terminates after O(1γlog⁡1/p0(f⋆))O(\frac{1}{\gamma}\log 1/p^0(f^\star)) informative queries, compared to Ω(log⁡(1/δ)/ε)\Omega(\log(1/\delta)/\varepsilon) for non-adaptive querying, and the per-instance bound is attained in .37 of the runs (App. E). In practice, language model priors are miscalibrated, leading to early termination on the wrong class, and often fail to propose a program consistent with the examples (App. E). (iii) The size of the evaluation set trades off convergence against correctness, as the theory predicts (RQ3). (iv) On CodeARC, the algorithm improves accuracy over the LM-only agent by up to 22 percentage points with up to 10.5 fewer input-output examples, and its queries significantly improve accuracy over the prior majority and require fewer rounds than random and diversity selection (Table 1, App. E). For the rebuttal, we also ran a compute-matched propose-and-verify baseline without oracle queries for all six models (3 seeds), which our method outperforms by up to 12 accuracy points, significantly on five of six (p < .01, paired sign test; App. E.4 of the revised paper).

We hope that these additional clarifications and results address the reviewer’s concerns!

Reviewer_sqbTOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies interactive program induction using an LLM prior over candidate programs. Programs are grouped based on their behavior on a sampled set of inputs, and the method selects new oracle queries using expected information gain. Posterior updates are approximated with importance sampling. The paper gives query-complexity and generalization results, and evaluates the method on CodeARC across six different models.

Critical strengths
  • The problem is interesting and well motivated. The framework gives a fairly clean way to combine program generation, execution, and active querying.

  • The empirical gains over the CodeARC agent are quite substantial for several models. For example, with 10 seed examples, Qwen2.5-32B improves from 29.9% to 41.5%.

  • The paper includes useful ablations on query selection, number of particles, and some analysis of the main failure modes.

Critical weaknesses
  1. The novelty relative to closely related work is not completely clear. LLM Priors for ERM over Programs (Singhal et al., ICML 2026), which is not cited, already studies LLM-induced distributions over executable programs together with verification and generalization guarantees. Also, Active Task Disambiguation with LLMs (Kobalczyk et al., ICLR 2025) already samples candidate programs, executes them on candidate inputs, and selects queries based on information gain. I think the paper should explain more clearly what is fundamentally new here, and ideally compare against some baselines with a similar program sampling approaches.

  2. The theoretical claims seem somewhat stronger than what is actually guaranteed. Theorem 3.2 bounds termination assuming every selected query has informativeness at least \gamma, but it does not guarantee recovery of an arbitrary target program. With the 1/2 stopping threshold, the method can in principle terminate on a wrong class if that class already has large prior mass. So the O(\log 1/p_0(f^\star)) identification claim feels a bit too strong unless the additional assumptions are stated very explicitly. Also, the dependence on 1/\gamma is important and should not be hidden.

I also think the interpretation of Proposition 2.1 needs some care. The proposition gives a high-probability guarantee for programs that agree with the target on S, but conditioning afterwards on the algorithm successfully returning the target class does not obviously preserve the same 1-\delta probability.

  1. The implemented importance weights do not exactly correspond to the actual proposal distribution. The density calculation ignores the intermediate reasoning and sampling temperature, even though both affect how programs are generated. This means the importance weights are systematically approximate, and this error does not necessarily disappear with more particles. Since these weights are used for query selection and stopping, I would like to see at least an ablation against uniform weights.

  2. Some experimental details make the oracle-efficiency numbers harder to interpret. In the 1-seed setting, the candidate input pool is still generated using all 10 seed examples. The authors do include a sensitivity experiment, which is helpful, but I think the main 1-seed experiment should ideally only use information available in that setting.

Also, failed runs are charged the full budget of 30 examples, even if they did not actually issue 30 oracle queries. So “Avg I/O” is not really just the number of examples observed. It would be much clearer to report actual oracle calls separately from this penalized metric.

  1. The gain from EIG itself seems fairly modest. Table 5 shows that EIG mostly improves query efficiency by around one example compared with random or simpler selection rules, while accuracy is generally very similar. At the same time, the full method samples far more programs than the CodeARC agent. So the overall system does work better in several cases, but it is not totally clear how much of the gain comes specifically from EIG, importance weighting, or simply spending more compute on candidate generation.
Questions for authors
  1. How does the method compare against a matched propose-and-verify baseline, for example with the same number of sampled programs?

  2. What happens if the importance weights are replaced by uniform weights over consistent programs?

  3. Do the 1-seed results remain similar when the input pool is generated only from that one visible seed example?

  4. Can the authors report actual number of oracle calls separately from the failure-penalized Avg I/O metric?

1 comment

We thank the reviewer for their careful reading and the positive comments about our theory and experiments! We address the reviewer’s concerns below:

  1. Novelty: Information gain as a selection criterion is not our contribution. We contribute the following. (1) The posterior over Python programs, and with it the EIG, is intractable. Kobalczyk et al. drop the prior and weight language model samples uniformly, so their information gain is taken under the language model's sampling distribution, not the posterior. We approximate the posterior by importance sampling, which significantly reduces oracle calls (point 4). (2) Instead of asking a fixed number of questions (Kobalczyk et al.) or until a single hypothesis is left (SYNTRA), our stopping criterion is adaptive and has a probabilistic interpretation (posterior majority). (3) Our approximate program equivalence on inputs drawn from the input distribution makes identifying the target decidable (exact program equivalence is undecidable), relates any program ff probabilistically to the target f⋆f^\star, and yields the convergence bounds of Thms. 3.1 and 3.2, which hold in practice. Singhal et al. study passive learning, which corresponds to the propose-and-verify control of point 3. We now discuss these references in the related work and list our contributions in the introduction.

  2. Proposition 2.1: Good point. A union bound fixes it, and we updated Prop. 2.1 accordingly:

Pr⁡[errμ(f^)>ln⁡(1/p0(f^))+ln⁡(1/δ)N]≤Pr⁡[c^≠[f⋆]∼]+δ\Pr\left\lbrack \mathrm{err}_{\mu}(\hat f) > \frac{\ln(1/p^0(\hat f)) + \ln(1/\delta)}{N} \right\rbrack \le \Pr\left\lbrack \hat c \neq \lbrack f^\star \rbrack_{\sim} \right\rbrack + \delta

  1. Modest EIG gain + compute: The relevant baseline is the LM only (CodeARC) agent, which our method improves on by 3 to 22 accuracy points on five of six models. (1) Random, diversity, and uncertainty selection are arms of our own algorithm. EIG improves over them mainly in Avg. I/O, and moderately in accuracy, since informative early queries steer resampling towards more promising programs (+3.7 points over random, p = 7e-11). (2) For the rebuttal, we ran a propose-and-verify baseline for all six models (3 seeds), which samples as many programs as our method (112), keeps those consistent with the seed examples and returns the majority. Our method is more accurate on all six models, by up to 12 points, significantly on five of six (p < .01, paired sign test; App. E.4 of the revised paper). Accuracy differences between selection rules are small because the target is among the initially sampled programs in only 13-23% of runs. On these runs our method reaches .69-.76 accuracy (App. E).

  2. Exact vs. uniform weights: For the rebuttal, we ran our method with uniform and with exact weights on all six models (3 seeds). Importance weights require up to 2.5 fewer input-output examples than uniform weights (up to 28%) on all six models (p < .001, paired sign test), at no significant difference in accuracy. The paper's approximate weights differ from the exact ones by at most 0.21 examples. Uniform weights correspond to Kobalczyk et al. (App. E.4 of the revised paper).

  3. 1-seed input pool: The input distribution fixes the inputs on which agreement with the target is measured, and with it what equivalence means. It is part of the problem and independent of the seed examples shown, so we keep it fixed across settings. For the rebuttal, we reran the 1-seed setting for all six models (3 seeds) with the pool generated only from the single visible seed example. Accuracy is relatively robust to this, with no significant change on five of six models (p > .01, paired sign test). Our method remains more accurate than the CodeARC agent on five of six models, by up to 16 points (p < .01, paired sign test), with up to 10 fewer input-output examples (App. D of the revised paper).

  4. Actual oracle calls: As in CodeARC's evaluation, failed runs are charged the full budget. The table reports actual and charged examples (1 seed invocation). Our method observes significantly fewer examples than the CodeARC agent in both cases on all six models.

ModelCodeARC, actualCodeARC, full budgetOurs, actualOurs, full budget
Llama3.2-3B19.0220.802.1615.82
Llama3.1-8B16.6020.202.2412.89
Qwen2.5-7B19.5420.772.209.01
Olmo3-7B13.3420.382.395.90
Ministral-8B16.2219.392.2213.54
Qwen2.5-32B11.1317.822.5110.83
  1. Minor: (i) Once no sampled program is consistent with the examples, all weights are 0 and the algorithm would run until the end of the budget, hence the full charge. (ii) Thm 3.2 does not claim recovery of an arbitrary target and states exactly when a wrong class is returned, and the abstract and conclusion now state γ\gamma explicitly.

We hope that these additional clarifications and results address the reviewer’s concerns!

Comments on the paper

1 comment

Dear reviewers,

Thank you for your work reviewing this paper!

The authors have submitted their responses. If you haven't already, please acknowledge them in a comment and adjust your reviews as needed. The discussion period finishes on November 18.

Best regards, Area Chair

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.