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 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 informative oracle queries, and returns the target program 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 over programs as inductive bias and a posterior that concentrates on 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 queries when every answer carries at least 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 bits, we bound the number of queries by per instance for any selection rule, and by the prior entropy over 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 from input–output observations that are revealed incrementally. Let be a countable set of inputs and a countable set of outputs, and let the target be an unknown but fixed element of the candidate space . We observe only through its behavior on selected inputs. At each round we choose an input , the query, and obtain its output from the oracle. Our goal is to return a function that closely approximates after as few queries as possible.
Setup
A finite sample of input–output pairs does not pin down a target in , since infinitely many functions agree on any finite subset of and disagree elsewhere (Solomonoff [46]). Recovering 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 over , 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 over , specifying the population of inputs on which the recovered function should agree with . 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 has countable support with . 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 . In the setting most relevant to this work (program synthesis over strings, where ) the input distribution has countably infinite support. Comparing a candidate against on every input in this support is infeasible, and even integrating against 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 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 and (ii) can be certified by inspecting only finitely many inputs. The first relaxation accomplishes (i) by declaring equivalent to when their disagreement under is small. For ,
Checking requires integration against , which we cannot do directly. The second relaxation makes equivalence checkable. We draw a random sample i.i.d. from and replace agreement under with agreement on ,
Write for the -class of and for the quotient, with . Because is finite, can be verified on observed data. Because is drawn from , agreement on also controls -error with high probability over the draw.
Proposition 2.1 (PAC Error Bound, cf. Blumer et al. [4]). Let be drawn i.i.d. from . With probability at least over the draw of , every with satisfies
Proof. In §C. ■
The bound in Eq. (3) depends on through . An 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, and refer to and for a fixed evaluation set drawn once from .
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 for the finite set of seed examples given with the task (Wei et al., [50]), possibly empty, and for the dataset after oracle answers. The posterior over given is
The posterior admits an equivalent recursive form,
where is the posterior predictive distribution of the output at an input . The recursive form from Eq. (5a) is the version we instantiate computationally in § 4.
Pushforward onto . By Prop. 2.1, it suffices to identify the -class of , since any has small with high probability over . The natural inference target is therefore the pushforward of the posterior on onto the quotient,
which assigns to each equivalence class the total posterior mass of its members. § 2.4 selects queries to concentrate on a single class as quickly as possible.
Greedy Information Gain Algorithm
We now describe an algorithm that constructs by selecting a maximally informative query at a time. Queries are selected from because that is where the classes are defined. All programs in a class return the same output on every , 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 , so queries in suffice to identify . 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 :
Select. Choose the input that maximizes the expected information gain (Shannon, [41]; MacKay, [31]) with respect to ,
where denotes the Shannon entropy and is the posterior predictive of Eq. (5b).
Query. Observe and set .
Update. Compute via Eq. (5a) and the pushforward via Eq. (7).
Terminate at the first round such that some class reaches majority pushforward mass, i.e., when , and return any . If , the returned agrees with on , and Prop. 2.1 gives except on an event of probability at most .
Query Complexity and Correctness Guarantees
We now derive a bound for the termination round of the greedy algorithm of § 2.4 and characterize the returned program class . 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 , conditional on the seed examples , and let be the prior class entropy in bits. Write for the most information an answer to a query in is guaranteed to carry at round . The greedy strategy of § 2.4 satisfies
(i) ;
(ii) for every target;
(iii) if for all and every with , then .
At termination, , i.e., for the terminal mass is the exact probability that the returned program is -equivalent to .
Proof. In §C. ▪
Theorem 3.2 (Per-instance query complexity and correctness). Fix with and let . Write for the information the answer to the query of round is guaranteed to carry. If and for all , then any selection rule over terminates after
Moreover, if and only if some class with prior mass strictly greater than is consistent with every query made. In particular, if no class outweighs under the prior, termination returns , 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 and therefore at least , the largest guaranteed information any query in 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 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 over and at the selected query, which are determined by how the program prior spreads mass across classes and how finely , drawn from the input distribution, separates them.
Improvement over non-adaptive querying. Fix a target error and confidence . A non-adaptive strategy draws inputs at random from , has the oracle label all of them, and accepts a program that agrees with the target on every one. It needs labeled inputs, since a program that disagrees with on a set of -mass passes random inputs with probability for (see, e.g., [40]), and by Prop. 2.1 inputs of that order also suffice, up to the term. The greedy algorithm needs an evaluation set of the same size, but the oracle labels only the inputs it queries. Since lies in its own class, that class has prior mass at least whatever is, so under the hypotheses of Thm. 3.2 the algorithm asks at most queries, a number that does not depend on . The non-adaptive cost grows with , 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 . Combining Prop. 2.1 with Thms. 3.1 and 3.2 gives a complete guarantee. The greedy algorithm terminates after at most queries when every answer carries at least bits, for a target drawn from the prior it returns the target’s class with probability , and since Prop. 2.1 holds for every program in simultaneously, the returned program satisfies . The size of the evaluation set enters the two bounds in opposite directions. A larger makes the error bound tighter, but it also refines , so the target’s class shrinks, its prior mass decreases, and the query bound grows. We evaluate the effect of empirically in § 5.
Approximate Inference with a Language Model
The greedy algorithm of § 2.4 requires the pushforward entropy , 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 is a finite, non-empty set of symbols, the set of all strings formed from (including the empty string), and the length of . A language model is a probability distribution over . The prefix probability is the probability that a string drawn from begins with . Whenever , the conditional prefix probability is
where is a distinguished end-of-string delimiter. Iterating Eq. (10) yields the autoregressive factorization
which computes from next-token queries without enumerating . 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 a distribution over implementations, whereas a program is an input–output behavior, and two distinct strings may decode to the same function while . The equivalence relation from §2.2 and the pushforward from §2.3 collapse implementations that agree on 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 we encode the observed examples into a prompt ([5]), a context string (§F), and condition the LM on it. Its completions are implementations , each of which decodes to a function by execution. The proposal over implementations is
and we take the program prior to be the proposal before any query, . The fixed objects and define the guarantees of §3, while the proposal is an approximation mechanism whose quality affects practical efficiency but not the guarantees for the exact posterior.
Importance Sampling Estimates
Importance weights. We draw implementations from , write for their decoded functions and , for the densities of the sampled implementations, and assign self-normalizing importance weights
Programs inconsistent with the observed data receive zero weight. For consistent programs, corrects for the mismatch between prior and proposal. Because is already conditioned on , it concentrates on consistent programs. At round 0 the weights reduce to the consistency indicator, since . Density ratios enter only when particles are resampled from a later . 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.

Figure 1.
Pushforward mass. The pushforward mass on a class is a posterior expectation, , which the self-normalized importance sampling (SNIS) estimator [35] replaces by the weighted share of the particles in the class,
where class membership is checked by comparing outputs on , as two programs share a -class if and only if they agree on every .
Entropy and information gain. Plugging Eq. (14) into the definition of entropy gives the plug-in estimator
The information gain for a candidate query is estimated by partitioning the particles by predicted output , computing on each partition with renormalized weights, and weighting by the estimated posterior predictive
The greedy step of § 2.4 is a finite maximization over , with in place of and in place of . 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 (i.e., ), exact weights, and finitely many classes, the SNIS estimates converge to as (e.g., [35]), and since is continuous in these estimates, by the continuous mapping theorem. The guarantees of § 3 are stated for the exact posterior, and for finite two things can go wrong. The particles may miss entirely, or a wrong class may exceed the threshold before enough of them land in , 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 (, 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-3B | Llama3.1-8B | Qwen2.5-7B | Qwen2.5-32B | Olmo3-7B | Ministral-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 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 on a chosen input to obtain , and equivalence queries (EQ), which ask the oracle whether a candidate equals 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 ), 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 fixes the inputs on which agreement with 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, , 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.
| Model | Method | Avg I/O ↓ | Acc. ↑ | Avg I/O ↓ | Acc. ↑ |
| Llama3.2-3B | LM only (CodeARC) | 19.02 ± 0.44 | .134 ± .014 | 27.55 ± 0.16 | .125 ± .014 |
| Alg. 1 with EIG (ours) | 15.82 ± 0.36 | .166 ± .010 | 25.13 ± 0.14 | .176 ± .008 | |
| Llama3.1-8B | LM only (CodeARC) | 16.60 ± 0.14 | .129 ± .015 | 26.86 ± 0.14 | .142 ± .009 |
| Alg. 1 with EIG (ours) | 12.89 ± 0.55 | .212 ± .011 | 22.77 ± 0.20 | .273 ± .015 | |
| Qwen2.5-7B | LM only (CodeARC) | 19.54 ± 0.26 | .148 ± .010 | 27.88 ± 0.19 | .156 ± .015 |
| Alg. 1 with EIG (ours) | 9.01 ± 0.42 | .229 ± .008 | 20.92 ± 0.11 | .322 ± .017 | |
| Qwen2.5-32B | LM only (CodeARC) | 11.13 ± 0.06 | .250 ± .011 | 18.75 ± 0.08 | .299 ± .014 |
| Alg. 1 with EIG (ours) | 10.83 ± 0.32 | .334 ± .024 | 19.66 ± 0.20 | .415 ± .010 | |
| Olmo3-7B | LM only (CodeARC) | 13.34 ± 0.16 | .064 ± .007 | 21.42 ± 0.15 | .113 ± .016 |
| Alg. 1 with EIG (ours) | 5.90 ± 0.33 | .240 ± .014 | 19.62 ± 0.17 | .332 ± .013 | |
| Ministral-8B | LM only (CodeARC) | 16.22 ± 0.12 | .239 ± .013 | 22.91 ± 0.18 | .264 ± .013 |
| Alg. 1 with EIG (ours) | 13.54 ± 0.28 | .170 ± .010 | 23.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.
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | 777 | 387 | 182 | 108 | 93 | 331 |
| 2 | – | 106 | 112 | 60 | 46 | 94 |
| 3 | – | – | 19 | 28 | 18 | 40 |
| 4 | – | – | – | 1 | 3 | 18 |
| 5 | – | – | – | – | – | 3 |
Table 5. Termination round of EIG against its per-instance bound derived in Thm. 3.2, . 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 is the information the selected query is guaranteed to yield, averaged over all queries of the strategy.
| Model | Method | Avg I/O ↓ | Acc. ↑ | Avg (bits) ↑ |
| Llama3.2 3B | LM only (CodeARC) | 19.03 ±0.44 | .134 ±.014 | – |
| Llama3.2 3B | Prior majority (no query) | – | .146 ±.017 | – |
| Llama3.2 3B | EIG | 15.81 ±0.36 | .167 ±.010 | .697 ±.008 |
| Llama3.2 3B | Uncertainty | 15.76 ±0.18 | .165 ±.007 | .590 ±.010 |
| Llama3.2 3B | Diversity | 15.96 ±0.22 | .166 ±.008 | .360 ±.004 |
| Llama3.2 3B | Random | 16.15 ±0.30 | .158 ±.016 | .362 ±.022 |
| Llama3.1 8B | LM only (CodeARC) | 16.59 ±0.13 | .130 ±.015 | – |
| Llama3.1 8B | Prior majority (no query) | – | .179 ±.015 | – |
| Llama3.1 8B | EIG | 12.88 ±0.55 | .212 ±.011 | .765 ±.039 |
| Llama3.1 8B | Uncertainty | 13.05 ±0.51 | .210 ±.010 | .640 ±.028 |
| Llama3.1 8B | Diversity | 13.33 ±0.43 | .204 ±.013 | .387 ±.016 |
| Llama3.1 8B | Random | 13.78 ±0.37 | .200 ±.011 | .382 ±.014 |
| Qwen2.5 7B | LM only (CodeARC) | 19.55 ±0.25 | .149 ±.009 | – |
| Qwen2.5 7B | Prior majority (no query) | – | .168 ±.006 | – |
| Qwen2.5 7B | EIG | 9.00 ±0.42 | .230 ±.008 | .796 ±.019 |
| Qwen2.5 7B | Uncertainty | 9.24 ±0.38 | .229 ±.008 | .676 ±.022 |
| Qwen2.5 7B | Diversity | 9.52 ±0.20 | .213 ±.010 | .433 ±.004 |
| Qwen2.5 7B | Random | 9.95 ±0.27 | .213 ±.008 | .448 ±.009 |
| Qwen2.5 32B | LM only (CodeARC) | 11.12 ±0.06 | .250 ±.011 | – |
| Qwen2.5 32B | Prior majority (no query) | – | .217 ±.016 | – |
| Qwen2.5 32B | EIG | 10.84 ±0.32 | .335 ±.023 | .722 ±.079 |
| Qwen2.5 32B | Uncertainty | 11.08 ±0.28 | .378 ±.035 | .608 ±.050 |
| Qwen2.5 32B | Diversity | 11.07 ±0.36 | .316 ±.005 | .313 ±.025 |
| Qwen2.5 32B | Random | 11.59 ±0.59 | .353 ±.020 | .337 ±.046 |
| Olmo3 7B | LM only (CodeARC) | 13.35 ±0.16 | .063 ±.007 | – |
| Olmo3 7B | Prior majority (no query) | – | .159 ±.031 | – |
| Olmo3 7B | EIG | 5.90 ±0.33 | .241 ±.014 | .990 ±.026 |
| Olmo3 7B | Uncertainty | 6.01 ±0.31 | .249 ±.027 | .856 ±.036 |
| Olmo3 7B | Diversity | 6.58 ±0.34 | .235 ±.016 | .521 ±.005 |
| Olmo3 7B | Random | 7.13 ±0.29 | .243 ±.037 | .519 ±.019 |
| Ministral 8B | LM only (CodeARC) | 16.22 ±0.12 | .239 ±.013 | – |
| Ministral 8B | Prior majority (no query) | – | .136 ±.020 | – |
| Ministral 8B | EIG | 13.53 ±0.27 | .171 ±.010 | .791 ±.026 |
| Ministral 8B | Uncertainty | 13.63 ±0.17 | .170 ±.003 | .679 ±.023 |
| Ministral 8B | Diversity | 14.00 ±0.34 | .162 ±.011 | .389 ±.031 |
| Ministral 8B | Random | 14.67 ±0.50 | .156 ±.006 | .385 ±.027 |
Table 6.
RQ3: Larger makes convergence on the target’s class rarer but more reliable. Figure 2 presents an ablation of the evaluation set size from 2 to 256 for three models. As predicted in §3, a smaller makes 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 on . As grows, convergence on becomes rarer but a reliable indicator of correctness. The rising conditional accuracy instantiates Prop. 2.1, since agreement with on more sampled inputs means fewer disagreements on unseen ones.
Figure 2. ablation on three models. Top: share of runs converging on . 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 oracle invocations when every answer carries at least 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 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 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 program samples from the LM proposal , evaluating each on the inputs in , 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 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.
| Model | Method | Wall-clock (s) ↓ | LM calls ↓ | Programs |
| Llama3.2 3B | Alg. 1 with EIG (ours) | 102 | 33.1 | 112.9 |
| LM only (CodeARC) | 289 | 4.7 | 2.6 | |
| Llama3.1 8B | Alg. 1 with EIG (ours) | 184 | 49.8 | 110.9 |
| LM only (CodeARC) | 330 | 7.1 | 2.8 | |
| Qwen2.5 7B | Alg. 1 with EIG (ours) | 142 | 72.2 | 106.4 |
| LM only (CodeARC) | 299 | 7.4 | 2.5 | |
| Qwen2.5 32B | Alg. 1 with EIG (ours) | 244 | 77.8 | 105.1 |
| LM only (CodeARC) | 991 | 9.3 | 2.5 | |
| Olmo3 7B | Alg. 1 with EIG (ours) | 258 | 72.0 | 108.6 |
| LM only (CodeARC) | 350 | 10.1 | 0.9 | |
| Ministral 8B | Alg. 1 with EIG (ours) | 182 | 32.1 | 115.5 |
| LM only (CodeARC) | 410 | 6.6 | 2.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 , 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 . A differential tester searches for a counterexample and may find one on an input that rarely produces, so the accuracies we report also measure how well agreement under 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 be drawn i.i.d. from . With probability at least over the draw of , every with satisfies
Proof. Fix with . Since consists of i.i.d. draws from , the probability that agrees with on all of is
where we used . Let be the right-hand side of Eq. (3), and let be the event that and . The event is empty if . Otherwise Eq. (18) gives . The probability that any of these events occurs is at most the sum of their probabilities, so
Assigning each program the failure probability instead of replaces by and extends the bound to countably infinite program spaces. On the complement of this event, every with satisfies Eq. (3).
Expected Query Complexity and Correctness
Throughout, is fixed, and for a class and we write for the common output of the programs in . A class is consistent with if for all , and is consistent with every . Ties in Eq. (8) are broken by a fixed rule.
Lemma C.1 (Mass recursion). For every class and ,
Proof. All programs in a class agree on , so summing Eq. (5a) over gives Eq. (20). For the indicator equals one, and unrolling over and taking logarithms gives Eq. (21). ■
Lemma C.2 (Greedy selection). Let . For every and , the objective in Eq. (8) equals . Moreover, for all , no input is queried twice, and .
Proof. Let , whose entropy is at most . The answer is a function of with distribution , and by Lem. C.1 the distribution of given is . The chain rule for entropy gives
which is the first claim. For , no class has mass above under , so two classes have positive mass and differ on some . Then , the predictive at is not a point mass, and . The predictive at a previously queried input is a point mass, so no input is queried twice. Once all of is queried, is the only consistent class, and thus . ■
Lemma C.3 (Posterior as conditional law). Let , conditional on the seed examples . For every class and every , we have .
Proof. The queries are a deterministic function of the answers received so far. A target in class therefore generates if and only if is consistent with it, that is, . Bayes’ rule with gives the claim. ■
Theorem 3.1 (Expected query complexity and correctness). Let , conditional on the seed examples , and let be the prior class entropy in bits. Write
for the most information an answer to a query in is guaranteed to carry at round . The greedy strategy of §2.4 satisfies
(i) ;
(ii) for every target;
(iii) if for all and every with , then .
At termination, , i.e., for the terminal mass is the exact probability that the returned program is -equivalent to .
Proof. Claim (ii) follows from Lem. C.2. For (i), dropping the last term of Eq. (21) at , which is non-negative, gives . We take expectations over . The right-hand side becomes since . On the left-hand side, the event is determined by , and by Lem. C.3 the answer given is distributed as , so that the conditional expectation of the -th term given is . Summing over yields
By Lem. C.2 and because the Shannon entropy of a distribution is at least the negative logarithm of its largest probability, , which proves (i). Keeping the last term of Eq. (21) and applying Lem. C.3 once more shows that the left-hand side equals , so the only inequalities behind (i) are and this lower bound on the Shannon entropy. For (iii), the hypothesis gives for every with , and taking expectations and applying (i) gives the bound. Finally, the returned class is determined by , so Lem. C.3 gives , which exceeds by the stopping rule. ■
Per-Instance Query Complexity and Correctness
Lemma C.4 (Mass growth). Fix with . Under any rule that selects queries from , for every ,
and under the greedy rule for every .
Proof. By definition of , we have , so Eq. (21) gives , which rearranges to Eq. (24). The greedy rule gives by Lem. C.2. ■
Theorem 3.2 (Per-instance query complexity and correctness). Fix with and let . Write for the information the answer to the query of round is guaranteed to carry. If and for all , then any selection rule over terminates after
Moreover, if and only if some class with prior mass strictly greater than is consistent with every query made. In particular, if no class outweighs under the prior, termination returns , and under the hypotheses of Eq. (8) it does so within that bound.
Proof. If , then Lem. C.4 gives and the algorithm has terminated by round . Now let be the right-hand side of Eq. (8), which is the smallest integer with . If , then and the algorithm would have terminated by round , a contradiction. For correctness, by Eq. (4) the posterior mass of every class consistent with is its prior mass divided by the same normalizer, so consistent classes are ordered under the posterior as under the prior. If , then with both classes consistent, so has strictly larger prior mass. Conversely, if a consistent class has larger prior mass than , then , and 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 particles, an evaluation set of size , resample when the effective sample size falls below , 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 , 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 (, 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, **, ***).
| Model | LM only (CodeARC) Avg I/O | LM only (CodeARC) Acc. | Ours, shared Avg I/O | Ours, shared Acc. | Ours, rebuilt from 1 seed Avg I/O | Ours, rebuilt from 1 seed Acc. |
| Llama3.2 3B | ||||||
| Llama3.1 8B | ** | |||||
| Qwen2.5 7B | ** | |||||
| Olmo3 7B | ||||||
| Ministral 8B | ||||||
| Qwen2.5 32B | *** |
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 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 (, ). 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.
| Model | Avg I/O ↓ | Acc. ↑ | ||||
| Model | Uniform | Approximate | Exact | Uniform | Approximate | Exact |
| Llama3.2 3B | 18.24 ±2.12 | 16.68 ±2.63*** | 16.67 ±2.64*** | .133 ±.051 | .143 ±.025 | .139 ±.029 |
| Llama3.1 8B | 14.87 ±.73 | 13.10 ±.54*** | 12.89 ±.84*** | .167 ±.064 | .173 ±.000 | .180 ±.015 |
| Qwen2.5 7B | 11.04 ±1.75 | 10.07 ±2.20*** | 10.08 ±2.19*** | .187 ±.029 | .163 ±.101 | .180 ±.073 |
| Olmo3 7B | 8.75 ±1.62 | 6.28 ±1.10*** | 6.27 ±1.12*** | .256 ±.046 | .229 ±.038 | .239 ±.061 |
| Ministral 8B | 14.37 ±1.00 | 13.21 ±1.21*** | 13.07 ±1.53*** | .197 ±.082 | .193 ±.090 | .159 ±.066 |
| Qwen2.5 32B | 10.54 ±1.22 | 9.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.
| Model | Avg I/O ↓ | Acc. ↑ | ||||
| Model | Ours | Minimax, unif. | EIG, unif. | Ours | Minimax, unif. | EIG, unif. |
| Llama3.2 3B | 15.49 ±3.27 | 16.37 ±3.33** | 15.84 ±2.65** | .153 ±.076 | .146 ±.077 | .170 ±.053 |
| Llama3.1 8B | 13.49 ±1.92 | 14.01 ±2.90** | 14.09 ±0.96*** | .185 ±.058 | .195 ±.063 | .182 ±.090 |
| Qwen2.5 32B | 9.55 ±3.13 | 10.45 ±3.71*** | 11.60 ±1.31*** | .263 ±.017 | .293 ±.086 | .290 ±.103 |
Table 8.
| Model | Propose-and-verify | Ours |
| 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 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 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 (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 , with 95% confidence intervals over 3 seeds.
Proposal Prompt and Sampling Temperature
The proposal 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.
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:
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,...]
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:
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...]
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 . It is sampled repeatedly, once per problem and before the first query, and each parsed completion becomes one element of .
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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]Henry Lieberman (ed.). Your Wish is My Command: Programming by Example. Morgan Kaufmann, 2001.
- [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]Llama Team. The Llama 3 herd of models, 2024. URL https://arxiv.org/abs/2407.21783.
- [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]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]Mistral AI team. Un Mistral, des Ministraux. Mistral AI blog, October 2024. URL https://mistral.ai/news/ministraux.
- [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]Art B. Owen. Monte Carlo Theory, Methods and Examples. https://artowen.su.domains/mc/, 2013.
- [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]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]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]Burr Settles. Active Learning. Morgan & Claypool Publishers, 2012.
- [40]Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
- [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]Ehud Y. Shapiro. Algorithmic Program Debugging. MIT Press, 1983.DOI
- [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]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]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]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]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]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]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]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]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.




