betaFeedback

WorksComputer Science

Interactive Program Induction with Language Model Priors

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.

https://github.com/chanr0/interactive-program-induction

Introduction

Many domain experts have a computer program clearly in mind that encodes certain rule-based behavior, but they cannot easily write it down themselves. For instance, a spreadsheet user often knows how they would like the column of names to be reformatted, but cannot write the regex. Similarly, a linguist knows how a sentence in their native language should be segmented, but cannot program the tokenizer. Inductive programming, also known as programming by example [47, 28, 17, 18], aims to bridge this gap by recovering the program from input–output examples. The paradigm has been deployed at scale for specific applications, most prominently in Microsoft Excel’s FlashFill [16].

However, recovering a target program from finite input–output examples is fundamentally ambiguous, since any finite set of examples is consistent with infinitely many programs that diverge on unseen data. Without an inductive bias, it is unclear which to choose [46]. Prior work restricts the program space to a hand-designed domain-specific language (DSL) [42, 18], at the cost of expressivity (cf. §A). Within a DSL, the consistent programs can be enumerated, and the target one selected through human feedback, for instance by asking for further examples [32, 21], or through an oracle in place of a human [45, 20]. Large language models trained on code [8, 1, 27] may help to go beyond DSLs by providing distributions over programs in a general-purpose language (e.g., Python). Still, when used as one-shot program inductors, they offer few mechanisms or guarantees for selecting the target among the many consistent programs. Li & Ellis [25] report a substantial gap to hand-engineered systems on programming-by-example, and Wei et al. [50] report limited success of LLM agents doing autonomous program induction in Python with oracle feedback. In this work, we propose an algorithm for interactive program induction over a general-purpose programming language, and derive theoretical guarantees on the number of oracle queries it requires and on the accuracy of the recovered program. To this end, we treat the target program as the unknown of a Bayesian inference problem, with a language model prior p0p^0 over programs as inductive bias and a posterior that concentrates on f⋆f^\star as input–output examples are observed, and we choose which inputs to query by sequential Bayesian experimental design [29, 31, 15, 22]. Using a notion of approximate equivalence between programs (exact equivalence being undecidable, Rice [37]), and an expected information gain criterion for query selection, we show that the algorithm terminates after O(1γlog⁡1p0(f⋆))O\left(\frac{1}{\gamma}\log\frac{1}{p^0(f^\star)}\right) queries when every answer carries at least γ\gamma bits. Dasgupta [9] analyzed this greedy rule over finite hypothesis classes, and our analysis carries over to programs because we measure agreement on a finite sample of inputs. Conditional on returning the target’s equivalence class, the returned program is approximately correct with high probability. Finally, we evaluate the practical implications on the CodeARC program induction dataset [50] and show that the algorithm improves accuracy over the CodeARC LM agent while reducing the number of required oracle calls in most evaluated settings.

In summary, our contributions are as follows:

  • We formulate interactive program induction in a general-purpose language as Bayesian active learning. Since the posterior over programs is intractable and program equivalence is undecidable, we approximate the posterior, and with it the expected information gain, by importance sampling with a language model as prior and proposal (§ 4), and replace exact equivalence by agreement on a finite sample of inputs (§ 2.2).

  • When every answer carries at least γ\gamma bits, we bound the number of queries by O(1γlog⁡1p0(f⋆))O\left(\frac{1}{\gamma}\log\frac{1}{p^0(f^\star)}\right) per instance for any selection rule, and by the prior entropy over γ\gamma in expectation for the greedy rule. We characterize when a wrong class is returned and give a PAC bound on the error (§ 3).

  • On CodeARC, our method improves accuracy over the LM-only agent on most evaluated language models, by up to 22 percentage points with up to 10.5 fewer input–output examples. Controls attribute the gains to the selection criterion and the importance weights (§ 5, §E.4). We find that the miscalibration of the language model prior limits the accuracy of the method (Figure 3).

Figure 3. Calibration of the prior majority class, with ECE in the legend. 95% CIs over five seeds.

Information-Theoretic Program Induction

We formalize interactive program induction as the problem of recovering a target function f⋆f^\star from input–output observations that are revealed incrementally. Let XX be a countable set of inputs and YY a countable set of outputs, and let the target f⋆:X→Yf^\star: X \to Y be an unknown but fixed element of the candidate space YXY^X. We observe f⋆f^\star only through its behavior on selected inputs. At each round tt we choose an input x(t)∈Xx^{(t)} \in X, the query, and obtain its output y(t)=f⋆(x(t))y^{(t)} = f^\star(x^{(t)}) from the oracle. Our goal is to return a function f^\hat{f} that closely approximates f⋆f^\star after as few queries as possible.

Setup

A finite sample of input–output pairs does not pin down a target in YXY^X, since infinitely many functions agree on any finite subset of XX and disagree elsewhere (Solomonoff [46]). Recovering f⋆f^\star therefore requires two pieces of additional structure, which together turn this ill-posed recovery problem into a well-posed Bayesian inference problem. The first is a program prior p0p^0 over YXY^X, which encodes the inductive bias. Many functions are consistent with a finite observation set, and the prior determines which of them are a priori plausible. The second is an input distribution μ\mu over XX, specifying the population of inputs on which the recovered function should agree with f⋆f^\star. The program prior decides which functions we prefer, and the input distribution decides where agreement is measured. We assume that programs are deterministic and that p0p^0 has countable support with p0(f⋆)>0p^0(f^\star) > 0. Whether a program halts on an input is undecidable, so evaluating whether it reproduces an observed output may not terminate. We therefore run every program with a time limit, and a program that raises or exceeds this limit on an input returns a distinguished error output, so every program defines a function on all of XX. In the setting most relevant to this work (program synthesis over strings, where X=Y=Σ∗X = Y = \Sigma^\ast) the input distribution μ\mu has countably infinite support. Comparing a candidate against f⋆f^\star on every input in this support is infeasible, and even integrating against μ\mu to estimate disagreement requires structure we do not assume. In the following, we derive the approximate notions of equivalence we use throughout.

Approximate Equivalence

Two facts about the interactive setting force us to relax exact program equivalence. First, exact equivalence of two computable functions is undecidable (Rice, [37]), so no algorithm can take two such functions and decide whether they agree on every input. Second, two functions can be compared on any single input by running them, but the query budget is finite while XX is typically infinite, so agreement on every input cannot be certified by exhaustive testing. We therefore want an equivalence relation that (i) measures disagreement under the population μ\mu and (ii) can be certified by inspecting only finitely many inputs. The first relaxation accomplishes (i) by declaring ff equivalent to f⋆f^\star when their disagreement under μ\mu is small. For ϵ∈(0,1)\epsilon\in(0,1),

f∼ϵf⋆⟺err⁡μ(f)≤ϵ,err⁡μ(f)=defPr⁡x∼μ[f(x)≠f⋆(x)].(1)f \sim_{\epsilon} f^\star\Longleftrightarrow\operatorname{err}_{\mu}(f) \le\epsilon,\qquad\operatorname{err}_{\mu}(f) \mathrel{\overset{\mathrm{def}}{=}} \Pr_{x\sim\mu}[f(x) \ne f^\star(x)]. \tag*{(1)}

Checking ∼ϵ\sim_{\epsilon} requires integration against μ\mu, which we cannot do directly. The second relaxation makes equivalence checkable. We draw a random sample S={x1,…,xN}S = \{x_1,\ldots,x_N\} i.i.d. from μ\mu and replace agreement under μ\mu with agreement on SS,

f∼Sf⋆⟺f(x)=f⋆(x) for all x∈S.(2)f \sim_S f^\star\Longleftrightarrow f(x) = f^\star(x)\text{ for all }x \in S. \tag*{(2)}

Write [f]∼[f]_{\sim} for the ∼S\sim_S-class of ff and YX/∼Y^X/\sim for the quotient, with ∣YX/∼∣≤∣Y∣N\lvert Y^X/\sim\rvert\le\lvert Y\rvert^N. Because SS is finite, ∼S\sim_S can be verified on observed data. Because SS is drawn from μ\mu, agreement on SS also controls μ\mu-error with high probability over the draw.

Proposition 2.1 (PAC Error Bound, cf. Blumer et al. [4]). Let S={x1,…,xN}S = \{x_1,\ldots,x_N\} be drawn i.i.d. from μ\mu. With probability at least 1−δ1-\delta over the draw of SS, every f∈[f⋆]∼f \in[f^\star]_{\sim} with p0(f)>0p^0(f)>0 satisfies

err⁡μ(f)≤ln⁡(1/p0(f))+ln⁡(1/δ)N.(3)\operatorname{err}_{\mu}(f) \le\frac{\ln(1/p^0(f))+\ln(1/\delta)}{N}. \tag*{(3)}

Proof. In §C. ■

The bound in Eq. (3) depends on ff through ln⁡(1/p0(f))\ln(1/p^0(f)). An ff with more prior mass gets a smaller error bound from the same evaluation set, or reaches a given error bound with a smaller evaluation set. Throughout the remainder of the paper, for notational brevity, ∼\sim and YX/∼Y^X/\sim refer to ∼S\sim_S and YX/∼SY^X/\sim_S for a fixed evaluation set SS drawn once from μN\mu^N.

Bayesian Updating

With the equivalence relation in place, we set up the Bayesian inference machinery on which our query selection rule will operate.

Update rule. Write D0⊂X×YD_0 \subset X \times Y for the finite set of seed examples (x,f⋆(x))(x,f^\star(x)) given with the task (Wei et al., [50]), possibly empty, and Dt=D0∪{(x(s),y(s))}s=1tD_t = D_0 \cup\{(x^{(s)},y^{(s)})\}_{s=1}^t for the dataset after tt oracle answers. The posterior over YXY^X given DtD_t is

p(f∣Dt)=p0(f)⋅∏(x,y)∈Dt1{f(x)=y}∑g∈YXp0(g)⋅∏(x,y)∈Dt1{g(x)=y}.(4)p(f\mid D_t)=\frac{p^0(f)\cdot\prod_{(x,y)\in D_t}\mathbb{1}\{f(x)=y\}}{\sum_{g\in Y^X}p^0(g)\cdot\prod_{(x,y)\in D_t}\mathbb{1}\{g(x)=y\}}. \tag*{(4)}

The posterior admits an equivalent recursive form,

p(f∣Dt)=p(f∣Dt−1)⋅1{f(x(t))=y(t)}p(y(t)∣x(t),Dt−1),(5)p(f\mid D_t)=\frac{p(f\mid D_{t-1})\cdot\mathbb{1}\{f(x^{(t)})=y^{(t)}\}}{p(y^{(t)}\mid x^{(t)},D_{t-1})}, \tag*{(5)}
p(y∣x,Dt)=def∑g∈YXp(g∣Dt)⋅1{g(x)=y},(6)p(y\mid x,D_t)\mathrel{\overset{\mathrm{def}}{=}}\sum_{g\in Y^X}p(g\mid D_t)\cdot\mathbb{1}\{g(x)=y\}, \tag*{(6)}

where p(y∣x,Dt)p(y\mid x,D_t) is the posterior predictive distribution of the output at an input xx. The recursive form from Eq. (5a) is the version we instantiate computationally in § 4.

Pushforward onto YX/∼Y^X/\sim. By Prop. 2.1, it suffices to identify the ∼\sim-class of f⋆f^\star, since any f∈[f⋆]∼f \in[f^\star]_\sim has small err⁡μ(f)\operatorname{err}_\mu(f) with high probability over SS. The natural inference target is therefore the pushforward of the posterior on YXY^X onto the quotient,

p∼([f]∼∣Dt)=def∑g∈[f]∼p(g∣Dt),(7)p_\sim([f]_\sim\mid\mathcal{D}_t) \mathrel{\mathop{=}^{\mathrm{def}}} \sum_{g \in[f]_\sim} p(g \mid\mathcal{D}_t), \tag*{(7)}

which assigns to each equivalence class the total posterior mass of its members. § 2.4 selects queries to concentrate p∼(⋅∣Dt)p_\sim(\cdot\mid\mathcal{D}_t) on a single class as quickly as possible.

Greedy Information Gain Algorithm

We now describe an algorithm that constructs D1,D2,…\mathcal{D}_1, \mathcal{D}_2, \ldots by selecting a maximally informative query x(t)∈Sx^{(t)} \in S at a time. Queries are selected from SS because that is where the classes are defined. All programs in a class return the same output on every x∈Sx \in S, so the answer to such a query eliminates whole classes and never splits one, and the posterior stays a distribution over the same classes. Any two distinct classes disagree on some x∈Sx \in S, so queries in SS suffice to identify [f⋆]∼[f^\star]_\sim. Each query is chosen by the expected information gain criterion of Bayesian experimental design (Lindley, [29]; MacKay, [31]), with the equivalence class of the target as the quantity of interest. More precisely, at each round t=1,2,…t = 1, 2, \ldots:

  1. Select. Choose the input x(t)∈Sx^{(t)} \in S that maximizes the expected information gain (Shannon, [41]; MacKay, [31]) with respect to p∼(⋅∣Dt−1)p_\sim(\cdot\mid\mathcal{D}_{t-1}),

x(t)=argmax⁡x∈S H[p∼(⋅∣Dt−1)]−∑y∈Yp(y∣x,Dt−1)H[p∼(⋅∣Dt−1∪{(x,y)})],(8)x^{(t)} = \underset{x \in S}{\operatorname{argmax}}\ \mathbb{H}[p_\sim(\cdot\mid\mathcal{D}_{t-1})] - \sum_{y \in Y} p(y \mid x, \mathcal{D}_{t-1}) \mathbb{H}[p_\sim(\cdot\mid\mathcal{D}_{t-1} \cup\{(x,y)\})], \tag*{(8)}

where H[⋅]\mathbb{H}[\cdot] denotes the Shannon entropy and p(⋅∣x,Dt−1)p(\cdot\mid x, \mathcal{D}_{t-1}) is the posterior predictive of Eq. (5b).

  1. Query. Observe y(t)=f⋆(x(t))y^{(t)} = f^\star(x^{(t)}) and set Dt=Dt−1∪{(x(t),y(t))}\mathcal{D}_t = \mathcal{D}_{t-1} \cup\{(x^{(t)}, y^{(t)})\}.

  1. Update. Compute p(⋅∣Dt)p(\cdot\mid\mathcal{D}_t) via Eq. (5a) and the pushforward p∼(⋅∣Dt)p_\sim(\cdot\mid\mathcal{D}_t) via Eq. (7).

Terminate at the first round t≥0t \ge0 such that some class c^\hat{c} reaches majority pushforward mass, i.e., when p∼(c^∣Dt)>12p_\sim(\hat{c} \mid\mathcal{D}_t) > \frac{1}{2}, and return any f^∈c^\hat{f} \in\hat{c}. If c^=[f⋆]∼\hat{c} = [f^\star]_\sim, the returned f^\hat{f} agrees with f⋆f^\star on SS, and Prop. 2.1 gives err⁡μ(f^)≤(ln⁡(1/p0(f^))+ln⁡(1/δ))/N\operatorname{err}_\mu(\hat{f}) \le(\ln(1/p^0(\hat{f})) + \ln(1/\delta))/N except on an event of probability at most Pr⁡[c^≠[f⋆]∼]+δ\Pr[\hat{c} \ne[f^\star]_\sim] + \delta.

Query Complexity and Correctness Guarantees

We now derive a bound for the termination round TT of the greedy algorithm of § 2.4 and characterize the returned program class c^\hat{c}. Both are stated in terms of the entropy of the prior over classes and of the information a round is guaranteed to yield, which depends on the queries available in the evaluation set and on which of them the selection strategy picks.

Theorem 3.1 (Expected query complexity and correctness). Let f⋆∼p0f^\star\sim p^0, conditional on the seed examples D0\mathcal{D}_0, and let H[p∼(⋅∣D0)]<∞\mathbb{H}[p_\sim(\cdot\mid\mathcal{D}_0)] < \infty be the prior class entropy in bits. Write γˉt=defmax⁡x∈S−log⁡2max⁡yp(y∣x,Dt−1)\bar{\gamma}_t \mathrel{\mathop{=}^{\mathrm{def}}} \max_{x \in S} -\log_2 \max_y p(y \mid x, \mathcal{D}_{t-1}) for the most information an answer to a query in SS is guaranteed to carry at round tt. The greedy strategy of § 2.4 satisfies

(i) Ef⋆∼p0[∑t=1Tγˉt]≤H[p∼(⋅∣D0)]\mathbb{E}_{f^\star\sim p^0}\left[\sum_{t=1}^{T} \bar{\gamma}_t\right] \le\mathbb{H}[p_\sim(\cdot\mid\mathcal{D}_0)];

(ii) T≤NT \le N for every target;

(iii) if γˉt≥γ>0\bar{\gamma}_t \ge\gamma> 0 for all t≤Tt \le T and every f⋆f^\star with p0(f⋆)>0p^0(f^\star) > 0, then Ef⋆∼p0[T]≤H[p∼(⋅∣D0)]/γ\mathbb{E}_{f^\star\sim p^0}[T] \le\mathbb{H}[p_\sim(\cdot\mid\mathcal{D}_0)]/\gamma.

At termination, Pr⁡[c^=[f⋆]∼∣DT]=p∼(c^∣DT)>12\Pr[\hat{c} = [f^\star]_\sim\mid\mathcal{D}_T] = p_\sim(\hat{c} \mid\mathcal{D}_T) > \frac{1}{2}, i.e., for f⋆∼p0f^\star\sim p^0 the terminal mass is the exact probability that the returned program is ∼\sim-equivalent to f⋆f^\star.

Proof. In §C. ▪

Theorem 3.2 (Per-instance query complexity and correctness). Fix f⋆f^\star with p0(f⋆)>0p^0(f^\star)>0 and let H[p∼(⋅∣D0)]<∞\mathrm{H}[p_{\sim}(\cdot\mid\mathcal{D}_0)]<\infty. Write γs=def−log⁡2max⁡yp(y∣x(s),Ds−1)\gamma_s \overset{\mathrm{def}}{=}-\log_2\max_y p(y\mid x^{(s)},D_{s-1}) for the information the answer to the query of round ss is guaranteed to carry. If p∼([f⋆]∼∣D0)≤12p_{\sim}([f^\star]_{\sim}\mid\mathcal{D}_0)\le\frac{1}{2} and γs≥γ>0\gamma_s\ge\gamma>0 for all s≤Ts\le T, then any selection rule over SS terminates after

T≤⌊1γlog⁡212p∼([f⋆]∼∣D0)⌋+1.(9)T\le\left\lfloor\frac{1}{\gamma}\log_2\frac{1}{2p_{\sim}([f^\star]_{\sim}\mid\mathcal{D}_0)}\right\rfloor+1. \tag*{(9)}

Moreover, c^≠[f⋆]∼\hat{c}\ne[f^\star]_{\sim} if and only if some class with prior mass strictly greater than p∼([f⋆]∼∣D0)p_{\sim}([f^\star]_{\sim}\mid\mathcal{D}_0) is consistent with every query made. In particular, if no class outweighs [f⋆]∼[f^\star]_{\sim} under the prior, termination returns c^=[f⋆]∼\hat{c}=[f^\star]_{\sim}, and under the hypotheses of Eq. (8) it does so within that bound.

Proof. In §C. ■

Thm. 3.1 bounds the number of queries in expectation over targets drawn from the prior. It is specific to the greedy rule, whose query has the largest expected information in SS and therefore at least γˉt\bar{\gamma}_t, the largest guaranteed information any query in SS offers. Thm. 3.2 bounds the number of queries for a fixed target program. Its proof does not use the greedy rule, so the bound applies to every selection rule over SS with the guaranteed information of that rule’s own queries, and § 5 empirically evaluates several such rules. In both, the rate of convergence is set by γˉt\bar{\gamma}_t over SS and γt\gamma_t at the selected query, which are determined by how the program prior spreads mass across classes and how finely SS, drawn from the input distribution, separates them.

Improvement over non-adaptive querying. Fix a target error ϵ\epsilon and confidence δ\delta. A non-adaptive strategy draws inputs at random from μ\mu, has the oracle label all of them, and accepts a program that agrees with the target on every one. It needs Ω(log⁡(1/δ)/ϵ)\Omega(\log(1/\delta)/\epsilon) labeled inputs, since a program that disagrees with f⋆f^\star on a set of μ\mu-mass ϵ\epsilon passes mm random inputs with probability (1−ϵ)m≥e−2mϵ(1-\epsilon)^m\ge e^{-2m\epsilon} for ϵ≤12\epsilon\le\frac{1}{2} (see, e.g., [40]), and by Prop. 2.1 inputs of that order also suffice, up to the ln⁡(1/p0(f))\ln(1/p^0(f)) term. The greedy algorithm needs an evaluation set of the same size, but the oracle labels only the T≤NT\le N inputs it queries. Since f⋆f^\star lies in its own class, that class has prior mass at least p0(f⋆)p^0(f^\star) whatever SS is, so under the hypotheses of Thm. 3.2 the algorithm asks at most ⌊1γlog⁡212p0(f⋆)⌋+1\left\lfloor\frac{1}{\gamma}\log_2\frac{1}{2p^0(f^\star)}\right\rfloor+1 queries, a number that does not depend on ϵ\epsilon. The non-adaptive cost grows with 1/ϵ1/\epsilon, while the adaptive cost is set by how plausible the target is under the prior. The PAC certificate of Prop. 2.1 then holds for the returned program, conditional on the algorithm returning the target’s class.

The role of ∣S∣|S|. Combining Prop. 2.1 with Thms. 3.1 and 3.2 gives a complete guarantee. The greedy algorithm terminates after at most ⌊1γlog⁡212p∼([f⋆]∼∣D0)⌋+1\left\lfloor\frac{1}{\gamma}\log_2\frac{1}{2p_{\sim}([f^\star]_{\sim}\mid\mathcal{D}_0)}\right\rfloor+1 queries when every answer carries at least γ2\frac{\gamma}{2} bits, for a target drawn from the prior it returns the target’s class with probability p∼(c^∣DT)p_{\sim}(\hat{c}\mid\mathcal{D}_T), and since Prop. 2.1 holds for every program in [f⋆]∼[f^\star]_{\sim} simultaneously, the returned program satisfies Pr⁡[err⁡μ(f^)>(ln⁡(1/p0(f^))+ln⁡(1/δ))/N]≤Pr⁡[c^≠[f⋆]∼]+δ\Pr[\operatorname{err}_{\mu}(\hat{f})>(\ln(1/p^0(\hat{f}))+\ln(1/\delta))/N]\le\Pr[\hat{c}\ne[f^\star]_{\sim}]+\delta. The size of the evaluation set enters the two bounds in opposite directions. A larger SS makes the error bound tighter, but it also refines ∼\sim, so the target’s class shrinks, its prior mass decreases, and the query bound grows. We evaluate the effect of ∣S∣|S| empirically in § 5.

Approximate Inference with a Language Model

The greedy algorithm of § 2.4 requires the pushforward entropy H[p∼(⋅∣Dt)]\mathrm{H}[p_{\sim}(\cdot\mid\mathcal{D}_t)], a sum over equivalence classes weighted by posterior mass. The posterior is a distribution over the countably infinite support of the prior, so neither it nor this sum can be computed exactly. We approximate the posterior by a weighted set of programs sampled from a language model, and compute the pushforward from the weights.

Language Model Proposal

Language model preliminaries. An alphabet Σ\Sigma is a finite, non-empty set of symbols, Σ∗\Sigma^{*} the set of all strings xx formed from Σ\Sigma (including the empty string), and ∣x∣|x| the length of xx. A language model pLMp_{\mathrm{LM}} is a probability distribution over Σ∗\Sigma^{*}. The prefix probability p⃗LM(x)=def∑x′∈Σ∗pLM(xx′)\vec{p}_{\mathrm{LM}}(x) \mathrel{\overset{\mathrm{def}}{=}} \sum_{x^{\prime}\in\Sigma^{*}}p_{\mathrm{LM}}(xx^{\prime}) is the probability that a string drawn from pLMp_{\mathrm{LM}} begins with xx. Whenever p⃗LM(x)>0\vec{p}_{\mathrm{LM}}(x)>0, the conditional prefix probability is

p⃗LM(x′∣x)=def{pLM(x)/p⃗LM(x)if x′=□,p⃗LM(xx′)/p⃗LM(x)otherwise,(10)\vec{p}_{\mathrm{LM}}(x^{\prime}\mid x) \mathrel{\overset{\mathrm{def}}{=}} \begin{cases} p_{\mathrm{LM}}(x)/\vec{p}_{\mathrm{LM}}(x) & \text{if } x^{\prime}=\square,\\ \vec{p}_{\mathrm{LM}}(xx^{\prime})/\vec{p}_{\mathrm{LM}}(x) & \text{otherwise,} \end{cases} \tag*{(10)}

where □∉Σ\square\notin\Sigma is a distinguished end-of-string delimiter. Iterating Eq. (10) yields the autoregressive factorization

pLM(x)=p⃗LM(□∣x)∏t=1∣x∣p⃗LM(xt∣x<t),(11)p_{\mathrm{LM}}(x)=\vec{p}_{\mathrm{LM}}(\square\mid x)\prod_{t=1}^{|x|}\vec{p}_{\mathrm{LM}}(x_t\mid x_{<t}), \tag*{(11)}

which computes pLM(x)p_{\mathrm{LM}}(x) from ∣x∣+1|x|+1 next-token queries without enumerating Σ∗\Sigma^{*}. The same definitions apply to a language model conditioned on a context string.

Proposal over programs. An LM is a distribution over strings, but our algorithm needs distributions over programs. We obtain them by prompting the LM with input–output examples and asking for a program consistent with them (§F gives the prompts), so that its distribution over completions is a distribution over source code. Strictly, this makes pLMp_{\mathrm{LM}} a distribution over implementations, whereas a program is an input–output behavior, and two distinct strings x1≠x2x_1\ne x_2 may decode to the same function while pLM(x1)≠pLM(x2)p_{\mathrm{LM}}(x_1)\ne p_{\mathrm{LM}}(x_2). The equivalence relation ∼\sim from §2.2 and the pushforward p∼p_{\sim} from §2.3 collapse implementations that agree on SS into a single class, so the algorithm operates at the level of programs, indifferent to syntactic differences between implementations, while sampling and density evaluation happen at the level of implementations, where Eq. (11) makes them tractable.

At each round tt we encode the observed examples into a prompt ([5]), a context string prompt⁡(Dt)∈Σ∗\operatorname{prompt}(\mathcal{D}_t)\in\Sigma^{*} (§F), and condition the LM on it. Its completions are implementations x∈Σ∗x\in\Sigma^{*}, each of which decodes to a function by execution. The proposal over implementations is

qt(x)=defpLM(x∣prompt⁡(Dt)),(12)q_t(x)\mathrel{\overset{\mathrm{def}}{=}}p_{\mathrm{LM}}(x\mid\operatorname{prompt}(\mathcal{D}_t)), \tag*{(12)}

and we take the program prior to be the proposal before any query, p0=defq0p^{0}\mathrel{\overset{\mathrm{def}}{=}}q_0. The fixed objects p0p^{0} and μ\mu define the guarantees of §3, while the proposal qtq_t is an approximation mechanism whose quality affects practical efficiency but not the guarantees for the exact posterior.

Importance Sampling Estimates

Importance weights. We draw MM implementations from qtq_t, write f1,…,fMf_1,\ldots,f_M for their decoded functions and p0(fm)p^{0}(f_m), qt(fm)q_t(f_m) for the densities of the sampled implementations, and assign self-normalizing importance weights

wm=p0(fm)⋅∏(x,y)∈Dt1{fm(x)=y}qt(fm).(13)w_m=\frac{p^{0}(f_m)\cdot\prod_{(x,y)\in\mathcal{D}_t}\mathbb{1}\{f_m(x)=y\}}{q_t(f_m)}. \tag*{(13)}

Programs inconsistent with the observed data Dt\mathcal{D}_t receive zero weight. For consistent programs, p0(fm)/qt(fm)p^{0}(f_m)/q_t(f_m) corrects for the mismatch between prior and proposal. Because qtq_t is already conditioned on Dt\mathcal{D}_t, it concentrates on consistent programs. At round 0 the weights reduce to the consistency indicator, since p0=q0p^{0}=q_0. Density ratios enter only when particles are resampled from a later qtq_t. Both densities are then the probability the LM assigns to the extracted code block under the respective prompt, without the reasoning that precedes it and without the sampling temperature. The weights are therefore an approximation to Eq. (13), which we do because intermediate reasoning and a tuned sampling temperature improve the sampled programs (§E.6). §E.4 compares them to the exact weights of the sampled completions and to uniform weights. The approximate and exact weights perform on par, and both require significantly fewer input–output examples than uniform weights.

Greedy Information Gain Program Induction algorithm

Figure 1.

Pushforward mass. The pushforward mass on a class cc is a posterior expectation, p∼(c∣Dt)=Ef∼p(⋅∣Dt)[1{f∈c}]p_{\sim}(c \mid D_t) = \mathbb{E}_{f \sim p(\cdot\mid D_t)}[1\{f \in c\}], which the self-normalized importance sampling (SNIS) estimator [35] replaces by the weighted share of the particles in the class,

p^∼(c∣Dt)=∑m:fm∈cwm∑m=1Mwm.(14)\hat{p}_{\sim}(c \mid D_t) = \frac{\sum_{m:f_m\in c} w_m}{\sum_{m=1}^{M} w_m}. \tag*{(14)}

where class membership is checked by comparing outputs on SS, as two programs share a ∼\sim-class if and only if they agree on every x∈Sx \in S.

Entropy and information gain. Plugging Eq. (14) into the definition of entropy gives the plug-in estimator

H^[p∼(⋅∣Dt)]=−∑cp^∼(c∣Dt)log⁡2p^∼(c∣Dt).(15)\hat{H}[p_{\sim}(\cdot\mid D_t)] = -\sum_c \hat{p}_{\sim}(c \mid D_t)\log_2\hat{p}_{\sim}(c \mid D_t). \tag*{(15)}

The information gain for a candidate query xx is estimated by partitioning the particles by predicted output fm(x)f_m(x), computing H^\hat{H} on each partition with renormalized weights, and weighting by the estimated posterior predictive

p^(y∣x,Dt)=∑m:fm(x)=ywm∑m=1Mwm.(16)\hat{p}(y \mid x,D_t) = \frac{\sum_{m:f_m(x)=y}w_m}{\sum_{m=1}^{M}w_m}. \tag*{(16)}

The greedy step of § 2.4 is a finite maximization over SS, with H^\hat{H} in place of HH and p^\hat{p} in place of pp. Alg. 1 summarizes the resulting procedure, with an effective-sample-size test that redraws the particles from the current proposal when the weights degenerate.

Approximation gaps. Under absolute continuity of the posterior with respect to qtq_t (i.e., p(f∣Dt)>0⇒qt(f)>0p(f \mid D_t) > 0 \Rightarrow q_t(f) > 0), exact weights, and finitely many classes, the SNIS estimates p^∼(c∣Dt)\hat{p}_{\sim}(c \mid D_t) converge to p∼(c∣Dt)p_{\sim}(c \mid D_t) as M→∞M \to\infty (e.g., [35]), and since H^\hat{H} is continuous in these estimates, H^[p∼(⋅∣Dt)]→H[p∼(⋅∣Dt)]\hat{H}[p_{\sim}(\cdot\mid D_t)] \to H[p_{\sim}(\cdot\mid D_t)] by the continuous mapping theorem. The guarantees of § 3 are stated for the exact posterior, and for finite MM two things can go wrong. The particles may miss [f⋆]∼[f^\star]_{\sim} entirely, or a wrong class may exceed the threshold before enough of them land in [f⋆]∼[f^\star]_{\sim}, which the miscalibration of the prior makes common (Figure 3). §E.5 varies the particle budget, and Table 4 and §B quantify how many runs terminate on a wrong class or without a consistent program.

Table 4: Terminal state of the runs behind Table 1 at 1 seed invocation (N=64N = 64, five seeds), as a share of all runs, averaged over seeds as in Table 1. A run converges when one class exceeds half of the posterior mass. The five rows partition the runs, and the two rows with a correct program sum to the accuracy of Table 1.

Llama3.2-3BLlama3.1-8BQwen2.5-7BQwen2.5-32BOlmo3-7BMinistral-8B
Not converged, no proposal consistent with the oracle’s answers.49.38.24.30.13.40
Not converged, query budget exhausted.00.00.00.01.01.00
Not converged, program correct.00.00.00.01.00.00
Converged, program wrong.34.40.52.36.63.42
Converged, program correct.17.21.23.33.24.17
Accuracy over all runs.17.21.23.33.24.17

Table 4.

Experiments

We now evaluate the practical implications of our work on a programming induction benchmark in Python (CodeARC; [50]). Its reference method, which we call the CodeARC LM agent, prompts a language model to autonomously choose the inputs to query, propose an implementation, and terminate when it feels confident, with no posterior over programs and no criterion for the choice of inputs. Our experiments aim to address four questions.

RQ1. Does Alg. 1 improve accuracy and oracle cost over the CodeARC LM agent?

RQ2. Does EIG ask queries with more guaranteed information than other selection criteria, and how much do the queries add over the prior alone?

RQ3. How does the choice of evaluation set size NN trade off convergence and correctness, as hypothesized in § 3?

RQ4. What are the failure modes of language model priors in program induction?

Setup

Dataset. We evaluate the proposed approach on the inductive inference benchmark CodeARC ([50]), whose 1114 Python functions are drawn from HumanEval+, MBPP+, and APPS and range from 2 to 74 lines, from entry-level tasks to competition problems. Similarly to our setup, the benchmark simulates an inductive inference scenario where a language modeling agent needs to find diverse Python functions from input–output pairs through membership queries (MQ), which query f⋆f^{\star} on a chosen input xx to obtain f⋆(x)f^{\star}(x), and equivalence queries (EQ), which ask the oracle whether a candidate f^\hat{f} equals f⋆f^{\star} and return a counterexample if it does not, under a fixed MQ and EQ invocation budget.1 We use the anonymized split, which replaces all function names with a generic identifier and so suppresses any cues for the program prior. Following [50], we provide a small number of seed invocations (initial input–output examples that we also use to condition μ\mu), evaluating both 1 and 10 seed invocations, and set the query budget to 30 input–output pairs, which includes the seed invocations. For consistency with their results, the CodeARC agent may additionally issue 2 equivalence queries, while our algorithm makes none and submits its returned program once for evaluation. We evaluate on the full split and report means over 5 independent seed runs. The input distribution μ\mu fixes the inputs on which agreement with f⋆f^{\star} is measured, and with it what equivalence means. It is part of the problem and independent of the seed invocations shown, so we condition it on all 10 seed invocations of the benchmark and keep it fixed across settings (§D). For the models that overlap with [50], we reproduce their reported results within seed noise.

Figure 1 (PDF p. 9). (a) Cumulative accuracy (top) and fraction of runs terminated (bottom) by round, for Alg. 1 under four query selection strategies, the CodeARC agent (LM only), and the per-instance bound of Thm. 3.2 aggregated over the EIG runs. The termination panels use the runs whose initial particles contain the target’s class. A run is terminated once it reaches the total query budget. (b) The information the selected query is guaranteed to yield, γt\gamma_t, by round, averaged over the runs still querying and pooled across models. A dashed line marks the last round with at least 200 runs of that strategy still querying, which is where the strategy has typically terminated. 95% CIs over five seeds.

Models. We evaluate our algorithm on six models of various sizes: Llama3.2-3B and Llama3.1-8B [30], Qwen2.5-7B and Qwen2.5-32B [51], Olmo3-7B [48], and Ministral-8B [33]. We use the instruction-tuned variant of every model. We chose these models for their differing performance on the CodeARC benchmark.

Baselines and Evaluation. To test whether our algorithm converges efficiently on the target program, we compare it to the full CodeARC baselines in terms of average number of input–output examples observed and accuracy upon termination. CodeARC equivalence queries give the baseline strictly more oracle access than our method when the EQ budget exceeds 1, so CodeARC @ 2 EQ is a more powerful oracle setting. Following Wei et al. [50], we evaluate the correctness of the generated programs extrinsically using the differential testing tool MOKAV [12]. We fix MOKAV’s test-generating language model to Qwen2.5-32B, the best-performing model, for all evaluated models and both methods, so that accuracies are comparable across models.

Results

RQ1: Alg. 1 with EIG improves accuracy and query efficiency over the LM only agent. Table 1 shows that the proposed method improves over the LM only (CodeARC) agent in most of the evaluated settings in terms of the final accuracy (up to +.22) as well as oracle querying efficiency (up to 10.5 fewer input–output examples). A gap to perfect accuracy remains, which we attribute to the models’ general performance ceiling in proposing valid code matching the shown input–output pairs (cf. Wei et al. [50], and our failure mode analysis in Table 4). Aside from this, the method commonly struggles with early termination due to early posterior concentration (RQ4), which is the case Thm. 3.2 excludes, a heavier class that stays consistent with every answer. Our ablation in Figure 5 shows that the choice of proposal prompt and temperature reduces this.

ModelMethodAvg I/O ↓Acc. ↑Avg I/O ↓Acc. ↑
Llama3.2-3BLM only (CodeARC)19.02 ± 0.44.134 ± .01427.55 ± 0.16.125 ± .014
Alg. 1 with EIG (ours)15.82 ± 0.36.166 ± .01025.13 ± 0.14.176 ± .008
Llama3.1-8BLM only (CodeARC)16.60 ± 0.14.129 ± .01526.86 ± 0.14.142 ± .009
Alg. 1 with EIG (ours)12.89 ± 0.55.212 ± .01122.77 ± 0.20.273 ± .015
Qwen2.5-7BLM only (CodeARC)19.54 ± 0.26.148 ± .01027.88 ± 0.19.156 ± .015
Alg. 1 with EIG (ours)9.01 ± 0.42.229 ± .00820.92 ± 0.11.322 ± .017
Qwen2.5-32BLM only (CodeARC)11.13 ± 0.06.250 ± .01118.75 ± 0.08.299 ± .014
Alg. 1 with EIG (ours)10.83 ± 0.32.334 ± .02419.66 ± 0.20.415 ± .010
Olmo3-7BLM only (CodeARC)13.34 ± 0.16.064 ± .00721.42 ± 0.15.113 ± .016
Alg. 1 with EIG (ours)5.90 ± 0.33.240 ± .01419.62 ± 0.17.332 ± .013
Ministral-8BLM only (CodeARC)16.22 ± 0.12.239 ± .01322.91 ± 0.18.264 ± .013
Alg. 1 with EIG (ours)13.54 ± 0.28.170 ± .01023.65 ± 0.24.226 ± .012

Table 1. Results across models and methods on the full anonymized CodeARC split. Entries are means over 5 independent seeds with 95% confidence intervals over seeds. Avg I/O is the average number of input–output examples observed, including the seed invocations, out of a budget of 30.

Figure 5. Accuracy of our algorithm against the sampling temperature for each proposal prompt, with 1 seed invocation on 100 problems. Prompts are ordered by accuracy pooled over models and temperatures.

RQ2: EIG asks the most informative queries and terminates in the fewest rounds, at an accuracy within noise of the other criteria. The termination panels of Fig. 1 condition on runs whose initial particles contain the target’s class, for all strategies alike. Compared to the other selection criteria within the proposed algorithm, EIG selects the most informative queries, .70 to .99 guaranteed bits per query against .31 to .52 for diversity and random selection, terminates in the fewest rounds, and reaches an accuracy within the seed intervals of the best criterion for every model (Fig. 1, Table 6). The queries yield a significant improvement over two controls, prior majority, which returns a program from the majority class of the initial particles without any query, and the CodeARC agent, which selects its queries heuristically (Table 1 and Table 6). Table 5 reports the bound of Thm. 3.2 on the EIG runs, which is attained in .37 of them. §E.4 further compares against uniform weights, minimax selection, and a compute-matched propose-and-verify baseline.

TT12345≥6\geq6
177738718210893331
2–106112604694
3––19281840
4–––1318
5–––––3

Table 5. Termination round TT of EIG against its per-instance bound derived in Thm. 3.2, ⌊1γlog⁡212p∼([f⋆]∼∣D0)⌋+1\left\lfloor\frac{1}{\gamma}\log_{2}\frac{1}{2p_{\sim}([f^\star]_{\sim}\mid\mathcal{D}_{0})}\right\rfloor+1. Runs on the diagonal, .37 of all runs, attain the bound.

Table 6: Query selection strategies of Alg. 1 and the CodeARC agent with 1 seed invocation on the full anonymized CodeARC split. Prior majority returns a program from the majority class of the initial particles without calling the oracle. Entries are means over 5 independent seeds (3 for prior majority) with 95% confidence intervals over seeds. Avg I/O is the average number of input–output examples observed, including the seed invocation, out of a budget of 30. Avg γt\gamma_t is the information the selected query is guaranteed to yield, averaged over all queries of the strategy.

ModelMethodAvg I/O ↓Acc. ↑Avg γt\gamma_t (bits) ↑
Llama3.2 3BLM only (CodeARC)19.03 ±0.44.134 ±.014–
Llama3.2 3BPrior majority (no query)–.146 ±.017–
Llama3.2 3BEIG15.81 ±0.36.167 ±.010.697 ±.008
Llama3.2 3BUncertainty15.76 ±0.18.165 ±.007.590 ±.010
Llama3.2 3BDiversity15.96 ±0.22.166 ±.008.360 ±.004
Llama3.2 3BRandom16.15 ±0.30.158 ±.016.362 ±.022
Llama3.1 8BLM only (CodeARC)16.59 ±0.13.130 ±.015–
Llama3.1 8BPrior majority (no query)–.179 ±.015–
Llama3.1 8BEIG12.88 ±0.55.212 ±.011.765 ±.039
Llama3.1 8BUncertainty13.05 ±0.51.210 ±.010.640 ±.028
Llama3.1 8BDiversity13.33 ±0.43.204 ±.013.387 ±.016
Llama3.1 8BRandom13.78 ±0.37.200 ±.011.382 ±.014
Qwen2.5 7BLM only (CodeARC)19.55 ±0.25.149 ±.009–
Qwen2.5 7BPrior majority (no query)–.168 ±.006–
Qwen2.5 7BEIG9.00 ±0.42.230 ±.008.796 ±.019
Qwen2.5 7BUncertainty9.24 ±0.38.229 ±.008.676 ±.022
Qwen2.5 7BDiversity9.52 ±0.20.213 ±.010.433 ±.004
Qwen2.5 7BRandom9.95 ±0.27.213 ±.008.448 ±.009
Qwen2.5 32BLM only (CodeARC)11.12 ±0.06.250 ±.011–
Qwen2.5 32BPrior majority (no query)–.217 ±.016–
Qwen2.5 32BEIG10.84 ±0.32.335 ±.023.722 ±.079
Qwen2.5 32BUncertainty11.08 ±0.28.378 ±.035.608 ±.050
Qwen2.5 32BDiversity11.07 ±0.36.316 ±.005.313 ±.025
Qwen2.5 32BRandom11.59 ±0.59.353 ±.020.337 ±.046
Olmo3 7BLM only (CodeARC)13.35 ±0.16.063 ±.007–
Olmo3 7BPrior majority (no query)–.159 ±.031–
Olmo3 7BEIG5.90 ±0.33.241 ±.014.990 ±.026
Olmo3 7BUncertainty6.01 ±0.31.249 ±.027.856 ±.036
Olmo3 7BDiversity6.58 ±0.34.235 ±.016.521 ±.005
Olmo3 7BRandom7.13 ±0.29.243 ±.037.519 ±.019
Ministral 8BLM only (CodeARC)16.22 ±0.12.239 ±.013–
Ministral 8BPrior majority (no query)–.136 ±.020–
Ministral 8BEIG13.53 ±0.27.171 ±.010.791 ±.026
Ministral 8BUncertainty13.63 ±0.17.170 ±.003.679 ±.023
Ministral 8BDiversity14.00 ±0.34.162 ±.011.389 ±.031
Ministral 8BRandom14.67 ±0.50.156 ±.006.385 ±.027

Table 6.

RQ3: Larger SS makes convergence on the target’s class rarer but more reliable. Figure 2 presents an ablation of the evaluation set size NN from 2 to 256 for three models. As predicted in §3, a smaller NN makes [f⋆]∼[f^\star]_{\sim} coarse, since equivalence then requires agreement on only a few inputs. The posterior concentrates early on such a coarse class, and the program returned from it is often rejected by the oracle despite agreeing with f⋆f^\star on SS. As SS grows, convergence on [f⋆]∼[f^\star]_{\sim} becomes rarer but a reliable indicator of correctness. The rising conditional accuracy instantiates Prop. 2.1, since agreement with f⋆f^\star on more sampled inputs means fewer disagreements on unseen ones.

Figure 2. NN ablation on three models. Top: share of runs converging on [f⋆]∼[f^\star]_{\sim}. Bottom: accuracy given convergence. 95% CIs over runs, three seeds.

RQ4: The language model prior is miscalibrated. Figure 3 is a calibration plot of the prior majority class against the CodeARC targets.2 For every model, the majority class is the target’s class far less often than its prior mass suggests. The prior is thus confident early, while Bayesian inductive inference relies on the prior to keep alternatives plausible until the data rule them out. By Thm. 3.2, a run converges on a wrong program if the prior strongly favors a wrong class, which this miscalibration makes common (Table 4).

Conclusion

We presented a Bayesian active-learning approach for efficient program induction with oracle feedback that uses a language model as both the program prior and the importance-sampling proposal. We proved that the greedy information-gain algorithm terminates after O(1qlog⁡1p0(f⋆))O\left(\frac{1}{q}\log\frac{1}{p^0(f^\star)}\right) oracle invocations when every answer carries at least γ\gamma bits, and introduced an equivalence relation that yields a PAC certificate on population error. Empirically, the algorithm improves accuracy and reduces oracle calls over the CodeARC agent in most evaluated settings, and its queries improve over returning the prior’s majority class. We see this work as a step toward principled human-in-the-loop program induction, where the same framework can accommodate richer oracle models, such as noisy users, and structured priors.

Related Work

Interactive and oracle-guided program synthesis. Early works in oracle-guided program synthesis include CEGIS [45], and is formalized in works by Jha et al. [20] and Jha & Seshia [19], where an automated verifier supplies counterexamples in place of a human. Interactive disambiguation with human oracles was deployed in FlashFill by Mayer et al. [32] and studied theoretically by Ji et al. [21], who select questions by minimax over programs sampled from a PCFG posterior over a version space. Tiwari et al. [49] select inputs that maximize the entropy of the outputs of sampled programs, weighted by a ranking heuristic. All of these operate over a finite DSL and use heuristic or symbolic distinguishability criteria. We work over a countably infinite program space and derive query-complexity bounds from the program prior.

Active learning for program synthesis. Barnaby et al. [3] discuss active learning in the neurosymbolic setting, where neural components can mispredict and cause convergence failures. Their constrained conformal evaluation is complementary to our work, which assumes a symbolic target and bounds query complexity information-theoretically. Our query-selection criterion is an instance of Bayesian experimental design [29, 31], applied sequentially as in active learning [39]. Dasgupta [9] showed that greedy information-gain maximization over a finite class used at most 4ln⁡(1/np0(h))4\ln(1/n p^0(h)) times the expected number of queries of the optimal strategy. We bound the number of queries of the greedy rule over a countable program space by measuring agreement on a finite sample of inputs, and replace enumeration with importance sampling under an LM proposal. Our query bounds depend on the size of the evaluation set, because a larger set separates more programs into distinct classes. A finite hypothesis class has no such dependence. Golovin et al. [14], Golovin & Krause [13], and Nowak [34] show that greedy rules over finite classes use nearly as few queries as the best possible adaptive plan of queries, which is intractable to compute. We bound the number of queries directly and make no such theoretical comparison.

Bayesian program induction. Bayesian priors over programs underlie a long line of work. Lake et al. [23] used hand-designed generative models over strokes for few-shot concept learning, Ellis et al. [10] bootstrapped reusable libraries via wake-sleep inference, Ellis et al. [11] applied the same framework to linguistic theory synthesis, and Saad et al. [38] sampled probabilistic programs from PCFG posteriors. These systems trade expressivity for tractability through a hand-crafted DSL or generative model. We keep the Bayesian perspective but substitute a language model for the hand-crafted prior, using importance sampling to make inference tractable over an unrestricted program space. Singhal et al. [44] use a language model to propose programs for empirical risk minimization on a fixed sample and give generalization guarantees. We select the examples interactively.

Information-seeking questions with language models. Several works select questions by expected information gain over hypotheses sampled from a language model, for natural-language rules on a Zendo-style task (Piriyakulkij et al. [36]), task disambiguation including code generation (Kobalczyk et al. [22]), collaborative search games (Grand et al. [15]), and natural-language database querying (Chan et al. [6]). Lee et al. [24] select inputs by maximin over the outputs of language-model-sampled programs, with a language model predicting outputs in place of the oracle. Kobalczyk et al. [22] and Lee et al. [24] treat sampled hypotheses as equally likely. We weight them by importance sampling under an explicit program prior. We apply this idea to program induction with an input–output oracle and derive query-complexity and correctness guarantees under an explicit program prior.

LLMs for program synthesis. LLMs achieve strong results on natural-language-specified code generation (Chen et al. [8]; Austin et al. [1]; Li et al. [27]) but struggle with programming by example without domain-specific fine-tuning (Li & Ellis [25]). HySynth (Barke et al. [2]) extracts a task-specific PCFG from LLM samples to guide bottom-up enumerative search, and Li et al. [26] pursue a similar direction using syntactic guidance. Both treat the LM as a one-shot prior over a fixed DSL, without user interaction or posterior updating. Grouping sampled programs by their outputs on a set of inputs is used to select a submission in AlphaCode (Li et al. [27]), CodeT (Chen et al. [7]), and MBR-exec (Shi et al. [43]), and our equivalence relation ∼\sim is the same construction. Wei et al. [50] introduced CodeARC, an interactive benchmark where agents iteratively query a hidden oracle and input selection is left to the agent’s heuristics. We use the LM as a prior and importance sampling proposal within a Bayesian framework and choose oracle membership queries to maximize expected information gain.

Limitations

Computational cost. Each round of the algorithm requires potentially drawing MM program samples from the LM proposal qtq_t, evaluating each on the inputs in SS, and recomputing importance weights and entropy estimates over the candidate pool. Larger evaluation sets, larger particle budgets, and longer programs all compound this cost, and the per-round latency is dominated by LM inference. Table 2 reports the cost per problem. Alg. 1 makes 32 to 78 LM calls and samples about 110 candidate programs, each of which it executes on SS and on every query, against 5 to 10 calls for the agent. Its wall-clock time per problem is nevertheless below the agent’s in our setup, since the agent’s calls are long generations and it keeps querying for most of its budget. The query-efficiency gains we report are savings in oracle effort, and the compute cost is in LM calls and program executions. Finally, the importance weights at resampling require the LM’s token log-probabilities of a program under two prompts, which closed APIs may not expose.

ModelMethodWall-clock (s) ↓LM calls ↓Programs
Llama3.2 3BAlg. 1 with EIG (ours)10233.1112.9
LM only (CodeARC)2894.72.6
Llama3.1 8BAlg. 1 with EIG (ours)18449.8110.9
LM only (CodeARC)3307.12.8
Qwen2.5 7BAlg. 1 with EIG (ours)14272.2106.4
LM only (CodeARC)2997.42.5
Qwen2.5 32BAlg. 1 with EIG (ours)24477.8105.1
LM only (CodeARC)9919.32.5
Olmo3 7BAlg. 1 with EIG (ours)25872.0108.6
LM only (CodeARC)35010.10.9
Ministral 8BAlg. 1 with EIG (ours)18232.1115.5
LM only (CodeARC)4106.62.6

Table 2. Computational cost per problem with 1 seed invocation on the full anonymized CodeARC split, means over runs. LM calls are generation requests to the language model. Programs are the candidate programs sampled by Alg. 1 and the implementations submitted by the agent. Wall-clock times were measured on different clusters under concurrent load and are indicative.

Dependence on the input distribution. Prop. 2.1 bounds the error under the input distribution μ\mu, which we instantiate by prompting an LM with the seed examples. A single seed invocation suffices for the gains of Table 1, and rebuilding the evaluation set from the single visible seed example changes accuracy by at most .02 on five of six models (§D). The bound does not guarantee generalization beyond μ\mu. A differential tester searches for a counterexample and may find one on an input that μ\mu rarely produces, so the accuracies we report also measure how well agreement under μ\mu generalizes. A prompt that describes the intended inputs more closely improves this generalization.

Gap between theoretical and empirical correctness. Thms. 3.1 and 3.2 hold for the exact posterior. The algorithm works with a finite particle approximation of it, and with priors that are sometimes concentrated on a wrong class. Both account for the .34 to .63 of runs in Table 4 that converge on a wrong program, since a wrong class can exceed the threshold before enough particles land in the target’s class, or hold most of the prior mass, as the miscalibrated prior of Figure 3 often does. The remaining errors are due to the models’ capability. In .13 to .49 of the runs no sampled program is consistent with the observed examples, and the CodeARC agent built on the same models reaches .06 to .30 (Table 1). Stronger models narrow this gap, with Qwen2.5-32B reaching the highest accuracy in every setting.

Deferred Proofs

PAC Bound

Proposition 2.1 (PAC Error Bound, cf. Blumer et al. [4]). Let S={x1,…,xN}S = \{x_1,\ldots,x_N\} be drawn i.i.d. from μ\mu. With probability at least 1−δ1-\delta over the draw of SS, every f∈[f⋆]∼f \in[f^\star]_{\sim} with p0(f)>0p^0(f)>0 satisfies

err⁡μ(f)≤ln⁡(1/p0(f))+ln⁡(1/δ)N.(17)\operatorname{err}_{\mu}(f) \le\frac{\ln(1/p^0(f))+\ln(1/\delta)}{N}. \tag*{(17)}

Proof. Fix ff with p0(f)>0p^0(f)>0. Since SS consists of NN i.i.d. draws from μ\mu, the probability that ff agrees with f⋆f^\star on all of SS is

Pr⁡S∼μN[f∈[f⋆]∼]=(1−err⁡μ(f))N≤exp⁡(−N⋅err⁡μ(f)),(18)\Pr_{S\sim\mu^N}\left[f \in[f^\star]_{\sim}\right] = (1-\operatorname{err}_{\mu}(f))^N \le\exp(-N\cdot\operatorname{err}_{\mu}(f)), \tag*{(18)}

where we used 1−u≤e−u1-u\le e^{-u}. Let τ(f):=(ln⁡(1/p0(f))+ln⁡(1/δ))/N\tau(f)\mathrel{\vcentcolon=}(\ln(1/p^0(f))+\ln(1/\delta))/N be the right-hand side of Eq. (3), and let BfB_f be the event that f∈[f⋆]∼f\in[f^\star]_{\sim} and err⁡μ(f)>τ(f)\operatorname{err}_{\mu}(f)>\tau(f). The event BfB_f is empty if err⁡μ(f)≤τ(f)\operatorname{err}_{\mu}(f)\le\tau(f). Otherwise Eq. (18) gives Pr⁡S∼μN[Bf]≤exp⁡(−N⋅τ(f))=δ⋅p0(f)\Pr_{S\sim\mu^N}[B_f]\le\exp(-N\cdot\tau(f))=\delta\cdot p^0(f). The probability that any of these events occurs is at most the sum of their probabilities, so

Pr⁡S∼μN[⋃f:p0(f)>0Bf]≤∑f:p0(f)>0δ⋅p0(f)≤δ.(19)\Pr_{S\sim\mu^N}\left[\bigcup_{f:p^0(f)>0}B_f\right]\le\sum_{f:p^0(f)>0}\delta\cdot p^0(f)\le\delta. \tag*{(19)}

Assigning each program the failure probability δ⋅p0(f)\delta\cdot p^0(f) instead of δ/∣YX∣\delta/|Y^X| replaces ln⁡∣YX∣\ln|Y^X| by ln⁡(1/p0(f))\ln(1/p^0(f)) and extends the bound to countably infinite program spaces. On the complement of this event, every f∈[f⋆]∼f\in[f^\star]_{\sim} with p0(f)>0p^0(f)>0 satisfies Eq. (3).

Expected Query Complexity and Correctness

Throughout, SS is fixed, and for a class cc and x∈Sx\in S we write c(x)c(x) for the common output of the programs in cc. A class is consistent with DtD_t if c(x(s))=y(s)c(x^{(s)})=y^{(s)} for all s≤ts\le t, and [f⋆]∼[f^\star]_{\sim} is consistent with every DtD_t. Ties in Eq. (8) are broken by a fixed rule.

Lemma C.1 (Mass recursion). For every class cc and 1≤t≤T1 \le t \le T,

p∼(c∣Dt)=p∼(c∣Dt−1)⋅1{c(x(t))=y(t)}p(y(t)∣x(t),Dt−1).(20)p_{\sim}(c \mid D_t) = \frac{p_{\sim}(c \mid D_{t-1}) \cdot\mathbb{1}\{c(x^{(t)}) = y^{(t)}\}}{p(y^{(t)} \mid x^{(t)}, D_{t-1})}. \tag*{(20)}
log⁡21p∼([f⋆]∼∣D0)=∑s=1tlog⁡21p(y(s)∣x(s),Ds−1)+log⁡21p∼([f⋆]∼∣Dt).(21)\log_2 \frac{1}{p_{\sim}([f^\star]_{\sim} \mid D_0)} = \sum_{s=1}^{t} \log_2 \frac{1}{p(y^{(s)} \mid x^{(s)}, D_{s-1})} + \log_2 \frac{1}{p_{\sim}([f^\star]_{\sim} \mid D_t)}. \tag*{(21)}

Proof. All programs in a class agree on x(t)∈Sx^{(t)} \in S, so summing Eq. (5a) over g∈cg \in c gives Eq. (20). For c=[f⋆]∼c = [f^\star]_{\sim} the indicator equals one, and unrolling over s≤ts \le t and taking logarithms gives Eq. (21). ■

Lemma C.2 (Greedy selection). Let H[p∼(⋅∣D0)]<∞H[p_{\sim}(\cdot\mid D_0)] < \infty. For every t≤Tt \le T and x∈Sx \in S, the objective in Eq. (8) equals H[p(⋅∣x,Dt−1)]H[p(\cdot\mid x, D_{t-1})]. Moreover, γt>0\gamma_t > 0 for all t≤Tt \le T, no input is queried twice, and T≤NT \le N.

Proof. Let c∼p∼(⋅∣Dt−1)c \sim p_{\sim}(\cdot\mid D_{t-1}), whose entropy is at most H[p∼(⋅∣D0)]/p∼([f⋆]∼∣D0)<∞H[p_{\sim}(\cdot\mid D_0)]/p_{\sim}([f^\star]_{\sim} \mid D_0) < \infty. The answer y=c(x)y = c(x) is a function of cc with distribution p(⋅∣x,Dt−1)p(\cdot\mid x, D_{t-1}), and by Lem. C.1 the distribution of cc given yy is p∼(⋅∣Dt−1∪{(x,y)})p_{\sim}(\cdot\mid D_{t-1} \cup\{(x,y)\}). The chain rule for entropy gives

H[p∼(⋅∣Dt−1)]=H[p(⋅∣x,Dt−1)]+∑y∈Yp(y∣x,Dt−1)H[p∼(⋅∣Dt−1∪{(x,y)})],(22)H[p_{\sim}(\cdot\mid D_{t-1})] = H[p(\cdot\mid x,D_{t-1})] + \sum_{y \in Y} p(y \mid x,D_{t-1}) H[p_{\sim}(\cdot\mid D_{t-1} \cup\{(x,y)\})], \tag*{(22)}

which is the first claim. For t≤Tt \le T, no class has mass above 12\frac{1}{2} under Dt−1D_{t-1}, so two classes have positive mass and differ on some x′∈Sx' \in S. Then H[p(⋅∣x(t),Dt−1)]≥H[p(⋅∣x′,Dt−1)]>0H[p(\cdot\mid x^{(t)},D_{t-1})] \ge H[p(\cdot\mid x',D_{t-1})] > 0, the predictive at x(t)x^{(t)} is not a point mass, and γt>0\gamma_t > 0. The predictive at a previously queried input is a point mass, so no input is queried twice. Once all of SS is queried, [f⋆]∼[f^\star]_{\sim} is the only consistent class, and thus T≤NT \le N. ■

Lemma C.3 (Posterior as conditional law). Let f⋆∼p0f^\star\sim p^0, conditional on the seed examples D0D_0. For every class cc and every t≤Tt \le T, we have Pr⁡[[f⋆]∼=c∣Dt]=p∼(c∣Dt)\Pr[[f^\star]_{\sim} = c \mid D_t] = p_{\sim}(c \mid D_t).

Proof. The queries are a deterministic function of the answers received so far. A target in class cc therefore generates DtD_t if and only if cc is consistent with it, that is, Pr⁡[Dt∣[f⋆]∼=c]=1{c consistent with Dt}\Pr[D_t \mid[f^\star]_{\sim} = c] = \mathbb{1}\{c\text{ consistent with }D_t\}. Bayes’ rule with Pr⁡[[f⋆]∼=c]=p∼(c∣D0)\Pr[[f^\star]_{\sim} = c] = p_{\sim}(c \mid D_0) gives the claim. ■

Theorem 3.1 (Expected query complexity and correctness). Let f⋆∼p0f^\star\sim p^0, conditional on the seed examples D0D_0, and let H[p∼(⋅∣D0)]<∞H[p_{\sim}(\cdot\mid D_0)] < \infty be the prior class entropy in bits. Write

γˉt≔max⁡x∈S−log⁡2max⁡yp(y∣x,Dt−1)\bar{\gamma}_t \coloneqq\max_{x \in S} -\log_2 \max_y p(y \mid x,D_{t-1})

for the most information an answer to a query in SS is guaranteed to carry at round tt. The greedy strategy of §2.4 satisfies

  • (i) Ef⋆∼p0[∑t=1Tγˉt]≤H[p∼(⋅∣D0)]\mathbb{E}_{f^\star\sim p^0}\left[\sum_{t=1}^{T}\bar{\gamma}_t\right] \le H[p_{\sim}(\cdot\mid D_0)];

  • (ii) T≤NT \le N for every target;

  • (iii) if γˉt≥γ>0\bar{\gamma}_t \ge\gamma> 0 for all t≤Tt \le T and every f⋆f^\star with p0(f⋆)>0p^0(f^\star) > 0, then Ef⋆∼p0[T]≤H[p∼(⋅∣D0)]/γ\mathbb{E}_{f^\star\sim p^0}[T] \le H[p_{\sim}(\cdot\mid D_0)]/\gamma.

At termination, Pr⁡[c^=[f⋆]∼∣DT]=p∼(c^∣DT)>12\Pr[\widehat{c} = [f^\star]_{\sim} \mid D_T] = p_{\sim}(\widehat{c} \mid D_T) > \frac{1}{2}, i.e., for f⋆∼p0f^\star\sim p^0 the terminal mass is the exact probability that the returned program is ∼S\sim_S-equivalent to f⋆f^\star.

Proof. Claim (ii) follows from Lem. C.2. For (i), dropping the last term of Eq. (21) at t=Tt = T, which is non-negative, gives ∑t=1T−log⁡2p(y(t)∣x(t),Dt−1)≤−log⁡2p∼([f⋆]∼∣D0)\sum_{t=1}^{T} -\log_2 p(y^{(t)} \mid x^{(t)},D_{t-1}) \le-\log_2 p_{\sim}([f^\star]_{\sim} \mid D_0). We take expectations over f⋆∼p0f^\star\sim p^0. The right-hand side becomes H[p∼(⋅∣D0)]H[p_{\sim}(\cdot\mid D_0)] since Pr⁡[[f⋆]∼=c]=p∼(c∣D0)\Pr[[f^\star]_{\sim} = c] = p_{\sim}(c \mid D_0). On the left-hand side, the event {T≥t}\{T \ge t\} is determined by Dt−1D_{t-1}, and by Lem. C.3 the answer y(t)y^{(t)} given Dt−1D_{t-1} is distributed as p(⋅∣x(t),Dt−1)p(\cdot\mid x^{(t)},D_{t-1}), so that the conditional expectation of the tt-th term given Dt−1D_{t-1} is H[p(⋅∣x(t),Dt−1)]H[p(\cdot\mid x^{(t)},D_{t-1})]. Summing over t≤Nt \le N yields

Ef⋆∼p0[∑t=1TH[p(⋅∣x(t),Dt−1)]]≤H[p∼(⋅∣D0)].(23)\mathbb{E}_{f^\star\sim p^0}\left[\sum_{t=1}^{T} H[p(\cdot\mid x^{(t)},D_{t-1})]\right] \le H[p_{\sim}(\cdot\mid D_0)]. \tag*{(23)}

By Lem. C.2 and because the Shannon entropy of a distribution is at least the negative logarithm of its largest probability, H[p(⋅∣x(t),Dt−1)]=max⁡x∈SH[p(⋅∣x,Dt−1)]≥γˉtH[p(\cdot\mid x^{(t)},D_{t-1})] = \max_{x \in S} H[p(\cdot\mid x,D_{t-1})] \ge\bar{\gamma}_t, which proves (i). Keeping the last term of Eq. (21) and applying Lem. C.3 once more shows that the left-hand side equals H[p∼(⋅∣D0)]−E[H[p∼(⋅∣DT)]]H[p_{\sim}(\cdot\mid D_0)]-\mathbb{E}[H[p_{\sim}(\cdot\mid D_T)]], so the only inequalities behind (i) are H[p∼(⋅∣DT)]≥0H[p_{\sim}(\cdot\mid D_T)]\ge0 and this lower bound on the Shannon entropy. For (iii), the hypothesis gives γT≤∑t=1Tγˉt\gamma T\le\sum_{t=1}^{T}\bar{\gamma}_t for every f⋆f^\star with p0(f⋆)>0p^0(f^\star)>0, and taking expectations and applying (i) gives the bound. Finally, the returned class c^\hat{c} is determined by DTD_T, so Lem. C.3 gives Pr⁡[c^=[f⋆]∼∣DT]=p∼(c^∣DT)\Pr[\hat{c}=[f^\star]_{\sim}\mid D_T]=p_{\sim}(\hat{c}\mid D_T), which exceeds 12\frac{1}{2} by the stopping rule. ■

Per-Instance Query Complexity and Correctness

Lemma C.4 (Mass growth). Fix f⋆f^\star with p0(f⋆)>0p^0(f^\star)>0. Under any rule that selects queries from SS, for every t≤Tt\le T,

p∼([f⋆]∼∣Dt)≥p∼([f⋆]∼∣D0)⋅2∑s=1tγs,(24)p_{\sim}([f^\star]_{\sim}\mid D_t)\ge p_{\sim}([f^\star]_{\sim}\mid D_0)\cdot2^{\sum_{s=1}^{t}\gamma_s}, \tag*{(24)}

and under the greedy rule γs>0\gamma_s>0 for every ss.

Proof. By definition of γs\gamma_s, we have p(y(s)∣x(s),Ds−1)≤2−γsp(y^{(s)}\mid x^{(s)},D_{s-1})\le2^{-\gamma_s}, so Eq. (21) gives −log⁡2p∼([f⋆]∼∣D0)≥∑s=1tγs−log⁡2p∼([f⋆]∼∣Dt)-\log_2p_{\sim}([f^\star]_{\sim}\mid D_0)\ge\sum_{s=1}^{t}\gamma_s-\log_2p_{\sim}([f^\star]_{\sim}\mid D_t), which rearranges to Eq. (24). The greedy rule gives γs>0\gamma_s>0 by Lem. C.2. ■

Theorem 3.2 (Per-instance query complexity and correctness). Fix f⋆f^\star with p0(f⋆)>0p^0(f^\star)>0 and let H[p∼(⋅∣D0)]<∞H[p_{\sim}(\cdot\mid D_0)]<\infty. Write γs:=−log⁡2max⁡yp(y∣x(s),Ds−1)\gamma_s\mathrel{\mathop:}=-\log_2\max_y p(y\mid x^{(s)},D_{s-1}) for the information the answer to the query of round ss is guaranteed to carry. If p∼([f⋆]∼∣D0)≤12p_{\sim}([f^\star]_{\sim}\mid D_0)\le\frac{1}{2} and γs≥γ>0\gamma_s\ge\gamma>0 for all s≤Ts\le T, then any selection rule over SS terminates after

T≤⌈1γlog⁡212p∼([f⋆]∼∣D0)⌉+1.(25)T\le\left\lceil\frac{1}{\gamma}\log_2\frac{1}{2p_{\sim}([f^\star]_{\sim}\mid D_0)}\right\rceil+1. \tag*{(25)}

Moreover, c^≠[f⋆]∼\hat{c}\ne[f^\star]_{\sim} if and only if some class with prior mass strictly greater than p∼([f⋆]∼∣D0)p_{\sim}([f^\star]_{\sim}\mid D_0) is consistent with every query made. In particular, if no class outweighs [f⋆]∼[f^\star]_{\sim} under the prior, termination returns c^=[f⋆]∼\hat{c}=[f^\star]_{\sim}, and under the hypotheses of Eq. (8) it does so within that bound.

Proof. If ∑s≤tγs>log⁡212p∼([f⋆]∼∣D0)\sum_{s\le t}\gamma_s>\log_2\frac{1}{2p_{\sim}([f^\star]_{\sim}\mid D_0)}, then Lem. C.4 gives p∼([f⋆]∼∣Dt)>12p_{\sim}([f^\star]_{\sim}\mid D_t)>\frac{1}{2} and the algorithm has terminated by round tt. Now let tt be the right-hand side of Eq. (8), which is the smallest integer with tγ>log⁡212p∼([f⋆]∼∣D0)t\gamma>\log_2\frac{1}{2p_{\sim}([f^\star]_{\sim}\mid D_0)}. If T>tT>t, then ∑s≤tγs≥tγ\sum_{s\le t}\gamma_s\ge t\gamma and the algorithm would have terminated by round tt, a contradiction. For correctness, by Eq. (4) the posterior mass of every class consistent with DTD_T is its prior mass divided by the same normalizer, so consistent classes are ordered under the posterior as under the prior. If c^≠[f⋆]∼\hat{c}\ne[f^\star]_{\sim}, then p∼(c^∣DT)>12>p∼([f⋆]∼∣DT)p_{\sim}(\hat{c}\mid D_T)>\frac{1}{2}>p_{\sim}([f^\star]_{\sim}\mid D_T) with both classes consistent, so c^\hat{c} has strictly larger prior mass. Conversely, if a consistent class c′c' has larger prior mass than [f⋆]∼[f^\star]_{\sim}, then p∼(c′∣DT)>p∼([f⋆]∼∣DT)p_{\sim}(c'\mid D_T)>p_{\sim}([f^\star]_{\sim}\mid D_T), and c^=[f⋆]∼\hat{c}=[f^\star]_{\sim} would give a total mass above one. ■

Experimental Details

Infrastructure. All models are served using vLLM3, with tensor parallelism and GPU memory scaled to model size. Models up to 8B parameters were run on a single GPU, while 32B models used either four 24 GB GPUs in parallel or a single 96 GB GPU. All servers run vLLM’s batch-invariant kernels, so that seeded sampling is reproducible under concurrent load. Models are loaded in bfloat16. The algorithm’s sampling and query-selection loop runs on a separate CPU-only node and communicates with the model server over an SSH tunnel.

Model parameters. We use M=64M = 64 particles, an evaluation set of size N=64N = 64, resample when the effective sample size falls below τESS=4\tau_{\mathrm{ESS}} = 4, and terminate once a class holds more than half of the posterior mass. Runs that return a program observe 2.3 to 2.7 input–output examples on average, depending on the model. The query budget we use and report is 30 input–output pairs, which includes the seed invocations. The evaluation set is shared across models. For each problem, we draw the evaluation set once from the input distribution μ\mu, instantiated with Llama3.1-8B at temperature 1.1, conditioned on all 10 seed invocations of the benchmark. The evaluation set therefore draws on seed examples that the algorithm does not see at 1 seed invocation. Its inputs coincide with a seed input in 0.3% of the entries, and rebuilding it from the 5 visible seed examples changed the accuracy of Llama3.2-3B, Llama3.1-8B, and Qwen2.5-32B by at most .02 on 100 problems. Rebuilding it from the single visible seed example on the full split changes accuracy by at most .02 on five of six models and lowers that of Qwen2.5-32B from .342 to .280 (Table 3). Our method remains more accurate than the CodeARC agent on all models but Ministral-8B (p<.01p < .01, paired sign test) and observes fewer input–output examples on average on all but Qwen2.5-32B, as with the shared evaluation set. We keep the shared evaluation set for all settings. The guarantee of Prop. 2.1 is with respect to this input distribution. The proposal prompt and sampling temperature are selected per model on a screening set (§E.6, Figure 5), and the prompts are given in §F. The maximum context length is capped at 12288 tokens across all models.

Table 3: Avg I/O and accuracy at 1 seed invocation with the evaluation set built from all 10 seed invocations (shared, as in Table 1) and from the single visible one, on the full anonymized split, means over 3 seeds. Stars test against the shared evaluation set (paired sign test, **p<.01p < .01, ***p<.001p < .001).

ModelLM only (CodeARC) Avg I/OLM only (CodeARC) Acc.Ours, shared Avg I/OOurs, shared Acc.Ours, rebuilt from 1 seed Avg I/OOurs, rebuilt from 1 seed Acc.
Llama3.2 3B19.18±0.2819.18 \pm0.28.129±.023.129 \pm.02315.93±0.6215.93 \pm0.62.169±.022.169 \pm.02215.96±0.7215.96 \pm0.72.157±.016.157 \pm.016
Llama3.1 8B16.58±0.3016.58 \pm0.30.134±.007.134 \pm.00712.73±1.4212.73 \pm1.42.218±.017.218 \pm.01713.28±0.4813.28 \pm0.48**.205±.031.205 \pm.031
Qwen2.5 7B19.57±0.3119.57 \pm0.31.153±.013.153 \pm.0138.95±0.948.95 \pm0.94.231±.021.231 \pm.0219.49±0.679.49 \pm0.67**.231±.021.231 \pm.021
Olmo3 7B13.35±0.1113.35 \pm0.11.063±.005.063 \pm.0055.89±0.645.89 \pm0.64.243±.030.243 \pm.0305.84±0.305.84 \pm0.30.224±.028.224 \pm.028
Ministral 8B16.24±0.2216.24 \pm0.22.242±.009.242 \pm.00913.65±0.6313.65 \pm0.63.169±.027.169 \pm.02714.14±0.5414.14 \pm0.54.165±.024.165 \pm.024
Qwen2.5 32B11.13±0.1311.13 \pm0.13.248±.025.248 \pm.02511.14±0.6211.14 \pm0.62.342±.027.342 \pm.02711.30±0.7811.30 \pm0.78.280±.012.280 \pm.012***

Table 3.

Licensing. The CodeARC benchmark [50] is released under the Apache 2.0 license. Llama3.1-8B and Llama3.2-3B are released under the Llama 3.1 and Llama 3.2 Community Licenses respectively. Qwen2.5-7B and Qwen2.5-32B are released under the Apache 2.0 license. Olmo3-7B is released under the Apache 2.0 license, and Ministral-8B under the Mistral Research License.

Additional Results

Failure Modes

Table 4 decomposes the runs of Table 1 by their terminal state to explain the gap between the correctness guarantee of Thm. 3.1 and the accuracies of Table 1. Most runs fail before the stopping rule applies. In a large share of them, between .13 and .49 depending on the model, no sampled program is consistent with the oracle’s answers, so the posterior is empty. In most of the remaining runs the posterior converges on a wrong program, owing to the proposal placing its mass on a plausible alternative that survives the few queries, as expected from the miscalibrated prior of Figure 3. Runs that keep querying until the budget is exhausted are rare, so the query budget does not limit accuracy. Both failure modes stem from the proposal. Accordingly, the particle budget (§E.5) and the prompt (§E.6) affect accuracy more than the query selection strategy (Table 6).

Per-Instance Bound Analysis

Table 5 compares, run by run, the termination round of EIG with the bound of Thm. 3.2 evaluated on that run. The bound is attained in .37 of the runs, and is loose when the guaranteed information is not uniform over the queries of a run, since γ\gamma is the minimum over the run’s queries and a single uninformative query loosens the bound.

Query Selection Strategies

Table 6 reports, per model, the quantities of Fig. 1 at the end of the run for every query selection strategy of Alg. 1 and for the CodeARC agent, together with the average information the selected queries are guaranteed to yield. All strategies score the same candidate inputs under the same weighted particle posterior and differ only in the score. EIG maximizes the estimated information gain about the equivalence class, Eq. (8). Uncertainty sampling maximizes the number of distinct outputs predicted by the particles of nonzero weight. Diversity maximizes the smallest character-trigram distance, one minus the Jaccard similarity, to the inputs already queried. Random draws an input uniformly. The strategies differ in the guaranteed information. EIG guarantees close to one bit per query, uncertainty sampling somewhat less, and diversity and random selection about half as much. This ordering carries over to the number of input–output examples, where the informed strategies save about one example per run against random selection, but not to accuracy, where all four strategies differ by at most .06 for every model. The accuracy of a run is decided by whether the proposal contains a correct program (§E.1), which every strategy then finds within a few queries. The information criterion therefore saves oracle calls at the same accuracy. Against the CodeARC agent, it improves both for all models but Ministral-8B.

Controls and Literature Baselines

Table 7 to Table 9 separate the contributions of the importance weights, the selection rule, and the sampling budget. All runs use 1 seed invocation and 3 seeds, and stars mark a paired sign test over problems and seeds (∗∗p<.01**p < .01, ∗∗∗p<.001***p < .001). Table 7 replaces the importance weights by uniform weights over consistent programs, as in Kobalczyk et al. [22], and by the exact weights of the sampled completions. The latter requires sampling at temperature 1, so all three arms use it here. The approximate weights of §4.2 and the exact weights perform on par, and both require significantly fewer input–output examples than uniform weights for all six models, at no significant difference in accuracy. Table 8 ports the selection rules of Ji et al. [21] and Lee et al. [24] (minimax with uniform weights) and of Kobalczyk et al. [22] (EIG with uniform weights) into Alg. 1, keeping the proposal, evaluation set, and stopping rule fixed. Both require significantly more input–output examples than our method, at no significant difference in accuracy. Table 9 matches the sampling budget. A propose-and-verify baseline draws 112 programs, the average number our method samples, keeps those consistent with the seed example, and returns a program of the majority class. Our method is significantly more accurate for five of six models.

Table 7: Importance weights against uniform weights, on 100 problems at sampling temperature 1. Stars test against uniform weights.

ModelAvg I/O ↓Acc. ↑
ModelUniformApproximateExactUniformApproximateExact
Llama3.2 3B18.24 ±2.1216.68 ±2.63***16.67 ±2.64***.133 ±.051.143 ±.025.139 ±.029
Llama3.1 8B14.87 ±.7313.10 ±.54***12.89 ±.84***.167 ±.064.173 ±.000.180 ±.015
Qwen2.5 7B11.04 ±1.7510.07 ±2.20***10.08 ±2.19***.187 ±.029.163 ±.101.180 ±.073
Olmo3 7B8.75 ±1.626.28 ±1.10***6.27 ±1.12***.256 ±.046.229 ±.038.239 ±.061
Ministral 8B14.37 ±1.0013.21 ±1.21***13.07 ±1.53***.197 ±.082.193 ±.090.159 ±.066
Qwen2.5 32B10.54 ±1.229.18 ±1.57***9.18 ±1.57***.296 ±.141.303 ±.106.282 ±.102

Table 7.

Table 8: Selection rules from the literature ported into Alg. 1, on 100 problems at the sampling temperatures of the main experiments. Stars test against our method.

ModelAvg I/O ↓Acc. ↑
ModelOursMinimax, unif.EIG, unif.OursMinimax, unif.EIG, unif.
Llama3.2 3B15.49 ±3.2716.37 ±3.33**15.84 ±2.65**.153 ±.076.146 ±.077.170 ±.053
Llama3.1 8B13.49 ±1.9214.01 ±2.90**14.09 ±0.96***.185 ±.058.195 ±.063.182 ±.090
Qwen2.5 32B9.55 ±3.1310.45 ±3.71***11.60 ±1.31***.263 ±.017.293 ±.086.290 ±.103

Table 8.

ModelPropose-and-verifyOurs
Llama3.2 3B.159 ± .019.169 ± .022
Llama3.1 8B.183 ± .018.219 ± .015***
Qwen2.5 7B.175 ± .010.232 ± .018***
Olmo3 7B.160 ± .032.243 ± .031***
Ministral 8B.148 ± .010.169 ± .028**
Qwen2.5 32B.224 ± .011.342 ± .028***

Table 9. Accuracy of a compute-matched propose-and-verify baseline (112 sampled programs, no oracle queries) and of our method on the full anonymized split. Stars test against propose-and-verify.

Particle Budget

Figure 4 varies the number of particles MM from 2 to 256 for three models on 100 problems with 1 seed invocation. More particles produce more behavioral classes at round 1, so the first query is more informative, and the algorithm ends with fewer input–output examples and higher accuracy. Accuracy keeps rising past the M=64M = 64 of the main experiments and does not saturate at 256, which agrees with the failure modes of §E.1, since the runs that converge on a wrong program or on none are runs in which no correct program was sampled, and a larger particle set samples one more often. We use 64 to limit the per-round cost, which grows with the number of programs that have to be executed on SS (Table 2).

Figure 4. Particle-budget ablation with 1 seed invocation on 100 problems. We show the input–output examples observed, the accuracy, and the number of behavioral classes at round 1 against the number of particles MM, with 95% confidence intervals over 3 seeds.

Proposal Prompt and Sampling Temperature

The proposal qtq_t depends on the prompt shown to the LM and on its sampling temperature. We consider four prompts (Prompts A–D, §F), which differ in how strongly they ask for hypotheses that disagree on unseen inputs, and six temperatures between 0.7 and 1.3. We choose the prompt and temperature for each model in a preliminary screen over prompts and temperatures in this range. The 100 screening problems are part of the evaluation split. Recomputing Table 1 on the remaining 985 problems changes every entry by at most .007. Figure 5 reports the accuracy of the full algorithm over the grid of prompts and temperatures. No prompt is best for every model. With about 100 problems per configuration, differences of a few hundredths are within sampling noise. Ministral-8B degrades at temperatures above 1.1 and Llama3.2-3B performs worst with the shortest prompt (Prompt A), with accuracy varying by .18 and .15 across the grid for these two models, compared with .07 to .12 for the others.

Prompts

We show each prompt as the text the model receives, with placeholders for problem-specific content written as <NAME>. All prompts are sent as a user message.

Default CodeARC Prompts

The baseline is a multi-turn conversation. Prompt B1 opens it. Depending on the model’s previous action, Prompt B2 or B3 is appended as the next user message, and Prompt B4 closes the conversation.

Prompt B1: first turn

You are a software engineer tasked with implementing a blackbox Python function `<FUNCTION_NAME>`. Your goal is to implement this function correctly, ensuring it works for ALL possible valid inputs, not just the example inputs provided.

Your primary goal is to get the function implementation exactly right.
Your secondary goal is to minimize the number of function invocations and implementation attempts.

GIVEN EXAMPLES:
Function invocations:
<INPUT_INVOCATIONS>

Corresponding outputs:
<OUTPUT_INVOCATIONS>

STRATEGY OVERVIEW:
You should work in two phases:
1. EXPLORATION PHASE: Use function invocations strategically to fully understand the function's behavior
2. IMPLEMENTATION PHASE: Only after thorough understanding, attempt an implementation

This is the first iteration. You must decide between one of the following two options:
1. Generate more function invocations in the same format as the given examples.
   Choose this option if you are not confident about how the function works. Each invocation should be strategically designed to:
   - Test a specific hypothesis about the function's behavior
   - Explore edge cases (empty inputs, negative numbers, special characters, etc.)
   - Refine your understanding of patterns in the output
   - Verify your assumptions systematically

You can generate up to <MAX_INVOCATIONS> function invocations across all iterations. You must generate exactly 1 invocation in this iteration.

You should first reason about the problem and the invocations to generate. Then, return the function invocations in the following format:

INVOCATIONS:

python print('Result i: ' + str(<FUNCTION_NAME>(args))) print('Result i+1: ' + str(<FUNCTION_NAME>(args)))

where each print statement is on a new line. ONLY include executable Python code within the code block. You must specify "INVOCATIONS" in the response.

  1. Generate an implementation of <FUNCTION_NAME>.

You have only <MAX_CHECKS> debugging checks total. If your implementation is incorrect, you lose one check and are shown a counterexample. If you exhaust all checks with incorrect implementations, you CANNOT take any more actions and your final attempt will be considered your answer.

You should ONLY choose this option if ALL of the following conditions are met:

  • You have seen enough diverse examples to understand the function completely

  • You have verified your understanding through strategic invocations

  • You have tested edge cases and corner cases thoroughly

  • You can confidently define the function for ALL possible valid inputs

  • You have a high degree of certainty about your implementation

If you choose this option, you should first reason about the problem and the implementation to generate. Then, return the implementation in the following format:

IMPLEMENTATION:

python def <FUNCTION_NAME>(input1, input2, ...): ...

ONLY include executable Python code within the code block. You must specify "IMPLEMENTATION" in the response.

Reason about which of the two actions described above to perform and then ONLY perform one of the two actions, specifying which action ("INVOCATIONS" or "IMPLEMENTATION") you performed in the response.

Prompt B2: next turn, after the model requested invocations

Here are the outputs of the function invocations from the previous iteration:

<OUTPUT_INVOCATIONS>

STRATEGY UPDATE:

Based on the new data above, you should update your understanding of the function and decide on your next action.

Following the formats described previously, you must decide between one of the two following options:

  1. Generate more function invocations to further explore the function's behavior. You have <MAX_INVOCATIONS> function invocations left across all remaining iterations. You must generate exactly 1 invocation in this iteration.

[...same INVOCATIONS format block as Prompt B1,...]

  1. Generate an implementation of <FUNCTION_NAME>. You have <MAX_CHECKS> debugging checks left.

[...same IMPLEMENTATION format block as Prompt B1...]

Reason about which of the two actions described above to perform and then ONLY perform one of the two actions, specifying which action ("INVOCATIONS" or "IMPLEMENTATION") you performed in the response.

Prompt B3: next turn, after a submitted implementation failed

The implementation you generated in the previous iteration failed for the following input (and potentially other inputs):

<FAILED_INPUTS>

Your implementation was incorrect. You now have <MAX_CHECKS> debugging checks remaining.

This failure provides valuable information about a case you didn't account for. You must decide between:

  1. Generate more function invocations to better understand why your implementation failed. You have <MAX_INVOCATIONS> function invocations left across all remaining iterations. You must generate exactly 1 invocation in this iteration. After a failed implementation, generating targeted invocations is almost always the best strategy; focus on:

    • Inputs similar to the failed case to understand the pattern you missed

    • Variations of the failed input to isolate the exact behavior

    • Edge cases related to the failure point

    • Inputs that can help discriminate between competing hypotheses

[...same INVOCATIONS format block as Prompt B1...]

  1. Generate a revised implementation of <FUNCTION_NAME>. You have <MAX_CHECKS> debugging checks. Only choose this option if you are absolutely certain you understand why your previous implementation failed AND you are confident your new implementation addresses that issue AND accounts for all other possible inputs.

[...same IMPLEMENTATION format block as Prompt B1...]

Reason about which of the two actions described above to perform and then ONLY perform one of the two actions, specifying which action ("INVOCATIONS" or "IMPLEMENTATION") you performed in the response.

Prompt B4: final turn, once all debugging checks are used

Here are the outputs of the function invocations from the previous iteration:

<OUTPUT_INVOCATIONS>

Now, synthesize all the information you've gathered across all iterations. Analyze patterns, edge cases, and the function's overall behavior.

Generate your final implementation of the function. Make sure it handles all cases, including the ones you've explicitly tested and others that follow the same pattern.

Return the final implementation in the following format:

```python def <FUNCTION_NAME>(input1, input2, ...): ... ```

ONLY include executable Python code within the code block.

Proposal Prompts

These are the four proposal prompts of our algorithm, and §E.6 describes which one is used for each model. The examples displayed are the seed invocations and all queries answered so far. The program prior uses the same prompt, displaying only the seed invocations.

Prompt A

````text Implement the hidden Python function <FUNCTION_NAME>.

Function invocations: <INPUT_INVOCATIONS>

Corresponding outputs: <OUTPUT_INVOCATIONS>

Return exactly one implementation using only the structure below without any additional explanations: IMPLEMENTATION:

def <FUNCTION_NAME>(input1, input2, ...):
...

````

Prompt B

````text Implement the hidden Python function <FUNCTION_NAME> from the examples below.

GIVEN EXAMPLES: Function invocations: <INPUT_INVOCATIONS>

Corresponding outputs: <OUTPUT_INVOCATIONS>

First, list concretely HOW the examples underdetermine the function: name specific inputs NOT shown above on which two valid implementations would disagree (edge cases, empty inputs, ties, ordering, types, unusual characters). Then pick ONE unresolved interpretation -- not necessarily the most popular one -- and implement it. The implementation must reproduce all given examples exactly. Return exactly one implementation using only the structure below without any additional explanations: IMPLEMENTATION:

def <FUNCTION_NAME>(input1, input2, ...):
...

````

Prompt C

````text You are a software engineer tasked with implementing a blackbox Python function <FUNCTION_NAME> from a set of input-output pairs provided below. Your goal is to implement this function correctly, ensuring it works for ALL possible valid inputs, not just the example inputs provided.

GIVEN EXAMPLES: Function invocations: <INPUT_INVOCATIONS> ```` Corresponding outputs: <OUTPUT_INVOCATIONS>

You should first briefly reason about the problem and all possible implementations that may lead to this input-output behavior. Every proposed implementation must satisfy all provided input-output examples exactly. Across proposals, favor diversity in hypotheses and complexity: include simpler and more structured alternatives (for example direct formulas, conditionals, loops, helper functions, or different algorithmic strategies), while staying consistent with the examples. Return exactly one implementation using only the structure below without any additional explanations: IMPLEMENTATION:

def <FUNCTION_NAME>(input1, input2, ...):
    ...

Prompt D

You are a software engineer tasked with implementing a blackbox Python function <FUNCTION_NAME> from a set of input-output pairs provided below. Your goal is to implement this function correctly, ensuring it works for ALL possible valid inputs, not just the example inputs provided.

GIVEN EXAMPLES: Function invocations: <INPUT_INVOCATIONS>

Corresponding outputs: <OUTPUT_INVOCATIONS>

IMPORTANT: this same prompt is being sent to you many times independently, and your answers are pooled into a set of competing hypotheses. Do NOT default to the single most obvious implementation every time. Treat your answer as ONE DRAW from the space of all distinct rules that reproduce the given examples exactly, sampled in proportion to how plausible each rule is. Different draws should disagree with each other on inputs that are NOT in the given examples, while all agreeing on the examples themselves.

You should first briefly reason about the problem and enumerate several genuinely different rules that all reproduce the given input-output behavior -- they may differ in how they generalise (edge cases, empty or negative or extreme inputs, types, ordering, off-by-one boundaries) or in algorithmic strategy (direct formula, conditionals, loops, recursion, helper functions, library calls). Then pick ONE of them and commit to it. Every proposed implementation must satisfy all provided input-output examples exactly. Return exactly one implementation using only the structure below without any additional explanations: IMPLEMENTATION:

def <FUNCTION_NAME>(input1, input2, ...):
    ...

Input Distribution Prompt

This prompt instantiates the input distribution μ\mu. It is sampled repeatedly, once per problem and before the first query, and each parsed completion becomes one element of SS.

Input distribution prompt

````text You are choosing one informative test input for a hidden Python function <FUNCTION_NAME>.

Known examples: Function invocations: <INPUT_INVOCATIONS>

Corresponding outputs: <OUTPUT_INVOCATIONS>

Reply with ONLY the INVOCATIONS block below--no preamble, no headings, no explanations, and no text outside the fenced Python block.

INVOCATIONS:

print('Result 1: ' + str(solution(args)))

Prefer diverse inputs (edges, negatives, extremes, unusual structures) inside the single print(...) line. ````

AI Use Statement

We used generative AI tools for brainstorming, to polish writing and mathematical proofs, and to find some of the related work. We reviewed all AI-generated text and retrieved resources and take full responsibility for the content of the paper.

References

  1. [1]Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and Charles Sutton. Program synthesis with large language models, 2021. URL https://arxiv.org/abs/2108.07732.
  2. [2]Shraddha Barke, Emmanuel Anaya Gonzalez, Saketh Ram Kasibatla, Taylor Berg-Kirkpatrick, and Nadia Polikarpova. HySynth: Context-free LLM approximation for guiding program synthesis. In Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=5jt0ZSA6cO.arxiv.org/abs/2405.15880
  3. [3]Celeste Barnaby, Qiaochu Chen, Ramya Ramalingam, Osbert Bastani, and Işıl Dillig. Active learning for neurosymbolic program synthesis. Proceedings of the ACM on Programming Languages, 9 (OOPSLA2), 2025. URL https://doi.org/10.1145/3763102.
  4. [4]Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Occam’s razor. Information Processing Letters, 24(6):377–380, 1987. URL https://doi.org/10.1016/0020-0190(87)90114-1.
  5. [5]Robin S. M. Chan, Reda Boumasmoud, Anej Svete, Yuxin Ren, Qipeng Guo, Zhijing Jin, Shauli Ravfogel, Mrinmaya Sachan, Bernhard Schölkopf, Mennatallah El-Assady, and Ryan Cotterell. On affine homotopy between language encoders. In Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=FTpOwIAwUZ.arxiv.org/abs/2406.02329
  6. [6]Robin Shing Moon Chan, Rita Sevastjanova, and Mennatallah El-Assady. PleaSQLarify: Visual pragmatic repair for natural language database querying. In Proceedings of the CHI Conference on Human Factors in Computing Systems, 2026. URL https://doi.org/10.1145/3772318.3791265.
  7. [7]Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen. CodeT: Code generation with generated tests. In International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=ktrw68Cmu9c.arxiv.org/abs/2207.10397
  8. [8]Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. Evaluating large language models trained on code, 2021. URL https://arxiv.org/abs/2107.03374.
  9. [9]Sanjoy Dasgupta. Analysis of a greedy active learning strategy. In Conference on Neural Information Processing Systems, 2004. URL https://proceedings.neurips.cc/paper/2004/hash/c61fbef63df5ff317aecd c3670094472-Abstract.html.
  10. [10]Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke B. Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua B. Tenenbaum. DreamCoder: Bootstrapping inductive program synthesis with wake-sleep library learning. In Proceedings of the ACM SIGPLAN International Conference on Programming Language Design and Implementation, 2021. URL https://doi.org/10.1145/3453483.3454080.
  11. [11]Kevin Ellis, Adam Albright, Armando Solar-Lezama, Joshua B. Tenenbaum, and Timothy J. O’Donnell. Synthesizing theories of human language with Bayesian program induction. Nature Communications, 13:5024, 2022. URL https://doi.org/10.1038/s41467-022-32012-w.
  12. [12]Khashayar Etemadi, Bardia Mohammadi, Zhendong Su, and Martin Monperrus. Mokav: Execution-driven differential testing with LLMs. Journal of Systems and Software, 230:112571, 2025. URL https://doi.org/10.1016/j.jss.2025.112571. Preprint. Under review.
  13. [13]Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427–486, 2011. URL https://www.jair.org/index.php/jair/article/view/10731.arxiv.org/abs/1003.3967
  14. [14]Daniel Golovin, Andreas Krause, and Debajyoti Ray. Near-optimal Bayesian active learning with noisy observations. In Conference on Neural Information Processing Systems, 2010. URL https://proceedings.neurips.cc/paper_files/paper/2010/hash/1e60a04d20f50967c64dac2d639a577-Abstract.html.arxiv.org/abs/1010.3091
  15. [15]Gabriel Grand, Valerio Pepe, Joshua B. Tenenbaum, and Jacob Andreas. Shoot first, ask questions later? Building rational agents that explore and act like people. In International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=EQhUvWH78U.arxiv.org/abs/2510.20886
  16. [16]Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In Proceedings of the Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 2011. URL https://doi.org/10.1145/1926385.1926423.
  17. [17]Sumit Gulwani, William R. Harris, and Rishabh Singh. Spreadsheet data manipulation using examples. Communications of the ACM, 55(8):97–105, 2012. URL https://doi.org/10.1145/2240236.2240260.
  18. [18]Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. Program synthesis. Foundations and Trends in Programming Languages, 4(1–2):1–119, 2017. URL https://doi.org/10.1561/2500000010.
  19. [19]Susmit Jha and Sanjit A. Seshia. A theory of formal synthesis via inductive learning. Acta Informatica, 54:693–726, 2017. URL https://doi.org/10.1007/s00236-017-0294-5.
  20. [20]Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. Oracle-guided component-based program synthesis. In Proceedings of the ACM/IEEE International Conference on Software Engineering, 2010. URL https://doi.org/10.1145/1806799.1806833.
  21. [21]Ruyi Ji, Jingjing Liang, Yingfei Xiong, Lu Zhang, and Zhenjiang Hu. Question selection for interactive program synthesis. In Proceedings of the ACM SIGPLAN International Conference on Programming Language Design and Implementation, 2020. URL https://doi.org/10.1145/3385412.3386025.
  22. [22]Katarzyna Kobalczyk, Nicolas Astorga, Tennison Liu, and Mihaela van der Schaar. Active task disambiguation with LLMs. In International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=JAMxRSXLfz.arxiv.org/abs/2502.04485
  23. [23]Brenden M. Lake, Ruslan Salakhutdinov, and Joshua B. Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266):1332–1338, 2015. URL https://doi.org/10.1126/science.aab3050.
  24. [24]Kang-il Lee, Jahyun Koo, Seunghyun Yoon, Minbeom Kim, Hyukhun Koh, Dongyeol Lee, and Kyomin Jung. Program synthesis via test-time transduction. In Conference on Neural Information Processing Systems, 2025. URL https://openreview.net/forum?id=YJx8AofTF5.arxiv.org/abs/2509.17393
  25. [25]Wen-Ding Li and Kevin Ellis. Is programming by example solved by LLMs? In Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=xqc8yyhScL.arxiv.org/abs/2406.08316
  26. [26]Yixuan Li, Julian Parsert, and Elizabeth Polgreen. Guiding enumerative program synthesis with large language models. In International Conference on Computer Aided Verification, 2024. URL https://doi.org/10.1007/978-3-031-65630-9_15.
  27. [27]Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d’Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. Competition-level code generation with AlphaCode. Science, 378(6624):1092–1097, 2022. URL https://doi.org/10.1126/science.abq1158. Preprint. Under review.
  28. [28]Henry Lieberman (ed.). Your Wish is My Command: Programming by Example. Morgan Kaufmann, 2001.
  29. [29]Dennis V. Lindley. On a measure of the information provided by an experiment. Annals of Mathematical Statistics, 27:986–1005, 1956. URL https://doi.org/10.1214/aoms/1177728069.
  30. [30]Llama Team. The Llama 3 herd of models, 2024. URL https://arxiv.org/abs/2407.21783.
  31. [31]David J. C. MacKay. Information-based objective functions for active data selection. Neural Computation, 4(4):590–604, 1992. URL https://doi.org/10.1162/neco.1992.4.4.590.
  32. [32]Mikaël Mayer, Gustavo Soares, Maxim Grechkin, Vu Le, Mark Marron, Oleksandr Polozov, Rishabh Singh, Benjamin Zorn, and Sumit Gulwani. User interaction models for disambiguation in programming by example. In Proceedings of the Annual ACM Symposium on User Interface Software and Technology, 2015. URL https://doi.org/10.1145/2807442.2807459.
  33. [33]Mistral AI team. Un Mistral, des Ministraux. Mistral AI blog, October 2024. URL https://mistral.ai/news/ministraux.
  34. [34]Robert D. Nowak. The geometry of generalized binary search. IEEE Transactions on Information Theory, 57(12):7893–7906, 2011. URL https://doi.org/10.1109/TIT.2011.2169298.
  35. [35]Art B. Owen. Monte Carlo Theory, Methods and Examples. https://artowen.su.domains/mc/, 2013.
  36. [36]Wasu Top Piriyakulkij, Cassidy Langenfeld, Tuan Anh Le, and Kevin Ellis. Doing experiments and revising rules with natural language and probabilistic reasoning. In Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=HXdAfK488A.
  37. [37]H. Gordon Rice. Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society, 74:358–366, 1953. URL https://doi.org/10.1090/S0002-9947-1953-0053041-6.
  38. [38]Feras A. Saad, Marco F. Cusumano-Towner, Ulrich Schaechtle, Martin C. Rinard, and Vikash K. Mansinghka. Bayesian synthesis of probabilistic programs for automatic data modeling. Proceedings of the ACM on Programming Languages, 3(POPL):1–32, 2019. URL https://doi.org/10.1145/3290350.
  39. [39]Burr Settles. Active Learning. Morgan & Claypool Publishers, 2012.
  40. [40]Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
  41. [41]Claude E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27(3):379–423, 1948. URL https://doi.org/10.1002/j.1538-7305.1948.tb01338.x.
  42. [42]Ehud Y. Shapiro. Algorithmic Program Debugging. MIT Press, 1983.DOI
  43. [43]Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, and Sida I. Wang. Natural language to code translation with execution. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2022. URL https://aclanthology.org/2022.emnlp-main.231/.arxiv.org/abs/2204.11454
  44. [44]Shivam Singhal, Priyadarsi Mishra, Eran Malach, and Tomer Galanti. LLM priors for ERM over programs. In International Conference on Machine Learning, 2026. URL https://openreview.net/forum?id=pwSWrsB1sZ.arxiv.org/abs/2510.14331
  45. [45]Armando Solar-Lezama. Program Synthesis by Sketching. PhD thesis, University of California, Berkeley, 2008. URL https://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-177.html.
  46. [46]Ray J. Solomonoff. A formal theory of inductive inference. Part I. Information and Control, 7(1):1–22, 1964. URL https://doi.org/10.1016/S0019-9958(64)90223-2. Preprint. Under review.
  47. [47]Phillip D. Summers. A methodology for LISP program construction from examples. Journal of the ACM, 24(1):161–175, 1977. URL https://doi.org/10.1145/321992.322002.
  48. [48]Team Olmo, Allyson Ettinger, Amanda Bertsch, Bailey Kuehl, David Graham, David Heineman, Dirk Groeneveld, Faeze Brahman, Finbarr Timbers, Hamish Ivison, Jacob Morrison, Jake Poznanski, Kyle Lo, Luca Soldaini, Matt Jordan, Mayee Chen, Michael Noukhovitch, Nathan Lambert, Pete Walsh, Pradeep Dasigi, Robert Berry, Saumya Malik, Saurabh Shah, Scott Geng, Shane Arora, Shashank Gupta, Taira Anderson, Teng Xiao, Tyler Murray, Tyler Romero, Victoria Graf, Akari Asai, Akshita Bhagia, Alexander Wettig, Alisa Liu, Aman Rangapur, Chloe Anastasiades, Costa Huang, Dustin Schwenk, Harsh Trivedi, Ian Magnusson, Jaron Lochner, Jiacheng Liu, Lester James V. Miranda, Maarten Sap, Malia Morgan, Michael Schmitz, Michal Guerquin, Michael Wilson, Regan Huff, Ronan Le Bras, Rui Xin, Rulin Shao, Sam Skjonsberg, Shannon Zejiang Shen, Shuyue Stella Li, Tucker Wilde, Valentina Pyatkin, Will Merrill, Yapei Chang, Yuling Gu, Zhiyuan Zeng, Ashish Sabharwal, Luke Zettlemoyer, Pang Wei Koh, Ali Farhadi, Noah A. Smith, and Hannan Hajishirizi. Olmo 3, 2025. URL https://arxiv.org/abs/2512.13961.
  49. [49]Ashish Tiwari, Arjun Radhakrishna, Sumit Gulwani, and Daniel Perelman. Information-theoretic user interaction: Significant inputs for program synthesis, 2020. URL https://arxiv.org/abs/2006.12638.
  50. [50]Anjiang Wei, Tarun Suresh, Jiannan Cao, Naveen Kannan, Yuheng Wu, Kai Yan, Thiago S. F. X. Teixeira, Ke Wang, and Alex Aiken. CodeARC: Benchmarking reasoning capabilities of LLM agents for inductive program synthesis. In Conference on Language Modeling, 2025. URL https://openreview.net/forum?id=Q5pVZcrrK.arxiv.org/abs/2503.23145
  51. [51]An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianghong Tu, Jianwei Zhang, Jianxin Yang, Jiaxi Yang, Jingren Zhou, Junyang Lin, Kai Dang, Keming Lu, Keqin Bao, Kexin Yang, Le Yu, Mei Li, Mingfeng Xue, Pei Zhang, Qin Zhu, Rui Men, Runji Lin, Tianhao Li, Tianyi Tang, Tingyu Xia, Xingzhang Ren, Xuancheng Ren, Yang Fan, Yang Su, Yichang Zhang, Yu Wan, Yuqiong Liu, Zeyu Cui, Zhenru Zhang, and Zihan Qiu. Qwen2.5 technical report, 2025. URL https://arxiv.org/abs/2412.15115.

Paper details

vlnc:W_2cny7nha
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

generative AI tools

View statement
Looking for related papers…
Contents