- 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
- 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.
- 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
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.
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:
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.
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).
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.
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!