Interactive Program Induction with Language Model Priors

arXiv cs.CL Papers

Summary

This paper proposes a Bayesian framework for interactive program induction where a language model serves as a prior over programs, deriving a greedy query-selection algorithm that provably converges after O((1/γ) log 1/p⁰(f*)) informative oracle queries. On the CodeARC benchmark, it improves accuracy over LM-only agents by up to 22 percentage points while using up to 10.5 fewer input-output examples.

arXiv:2611.18485v1 Announce Type: new 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 $p^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 $\mathcal{O}(\frac{1}{\gamma}\log 1/p^0(f^\star))$ informative oracle queries, and returns the target program $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.
Original Article
View Cached Full Text

Cached at: 11/16/26, 08:30 AM

# Interactive Program Induction with Language Model Priors
Source: [https://arxiv.org/html/2611.18485](https://arxiv.org/html/2611.18485)
###### 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 priorp0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{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𝒪⁡\(1γ​log⁡1/p0​\(f⋆\)\)\{\\color\[rgb\]\{0,0,0\}\\mathcal\{O\}\}\(\\tfrac\{1\}\{\{\\color\[rgb\]\{0,0,0\}\\gamma\}\}\\log 1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\)\)informative oracle queries, and returns the target programf⋆\{\\color\[rgb\]\{0,0,0\}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 to2222percentage points while observing up to10\.510\.5fewer input–output examples\.

![[Uncaptioned image]](https://arxiv.org/html/2611.18485v1/figs/github.png)[https://github\.com/chanr0/interactive\-program\-induction](https://github.com/chanr0/interactive-program-induction)

## 1Introduction

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\([Summers, 1977](https://arxiv.org/html/2611.18485#bib.bib47);[Lieberman, 2001](https://arxiv.org/html/2611.18485#bib.bib28);[Gulwani et al\., 2012](https://arxiv.org/html/2611.18485#bib.bib17);[Gulwani et al\., 2017](https://arxiv.org/html/2611.18485#bib.bib18)\), 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\([Gulwani, 2011](https://arxiv.org/html/2611.18485#bib.bib16)\)\.

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\([Solomonoff, 1964](https://arxiv.org/html/2611.18485#bib.bib46)\)\. Prior work restricts the program space to a hand\-designed domain\-specific language \(DSL\)\([Shapiro, 1983](https://arxiv.org/html/2611.18485#bib.bib42);[Gulwani et al\., 2017](https://arxiv.org/html/2611.18485#bib.bib18)\), at the cost of expressivity \(cf\.[App\.A](https://arxiv.org/html/2611.18485#A1)\)\. Within a DSL, the consistent programs can be enumerated, and the target one selected through human feedback, for instance by asking for further examples\([Mayer et al\., 2015](https://arxiv.org/html/2611.18485#bib.bib32);[Ji et al\., 2020](https://arxiv.org/html/2611.18485#bib.bib21)\), or through an oracle in place of a human\([Solar\-Lezama, 2008](https://arxiv.org/html/2611.18485#bib.bib45);[Jha et al\., 2010](https://arxiv.org/html/2611.18485#bib.bib20)\)\. Large language models trained on code\([Chen et al\., 2021](https://arxiv.org/html/2611.18485#bib.bib8);[Austin et al\., 2021](https://arxiv.org/html/2611.18485#bib.bib1);[Li et al\., 2022](https://arxiv.org/html/2611.18485#bib.bib27)\)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 \(2024\)](https://arxiv.org/html/2611.18485#bib.bib25)report a substantial gap to hand\-engineered systems on programming\-by\-example, and[Wei et al\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib50)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 priorp0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}over programs as inductive bias and a posterior that concentrates onf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}as input–output examples are observed, and we choose which inputs to query by sequential Bayesian experimental design\([Lindley, 1956](https://arxiv.org/html/2611.18485#bib.bib29);[MacKay, 1992](https://arxiv.org/html/2611.18485#bib.bib31);[Grand et al\., 2026](https://arxiv.org/html/2611.18485#bib.bib15);[Kobalczyk et al\., 2025](https://arxiv.org/html/2611.18485#bib.bib22)\)\. Using a notion of approximate equivalence between programs\([Rice, 1953](https://arxiv.org/html/2611.18485#bib.bib37), exact equivalence being undecidable,\)and an expected information gain criterion for query selection, we show that the algorithm terminates after𝒪⁡\(1γ​log⁡1/p0​\(f⋆\)\)\{\\color\[rgb\]\{0,0,0\}\\mathcal\{O\}\}\(\\tfrac\{1\}\{\{\\color\[rgb\]\{0,0,0\}\\gamma\}\}\\log 1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\)\)queries when every answer carries at leastγ\{\\color\[rgb\]\{0,0,0\}\\gamma\}bits\.[Dasgupta \(2004\)](https://arxiv.org/html/2611.18485#bib.bib9)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\([Wei et al\., 2025](https://arxiv.org/html/2611.18485#bib.bib50)\)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](https://arxiv.org/html/2611.18485#S4)\), and replace exact equivalence by agreement on a finite sample of inputs \([§2\.2](https://arxiv.org/html/2611.18485#S2.SS2)\)\.
- •When every answer carries at leastγ\{\\color\[rgb\]\{0,0,0\}\\gamma\}bits, we bound the number of queries by𝒪⁡\(1γ​log⁡1/p0​\(f⋆\)\)\{\\color\[rgb\]\{0,0,0\}\\mathcal\{O\}\}\(\\tfrac\{1\}\{\{\\color\[rgb\]\{0,0,0\}\\gamma\}\}\\log 1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\)\)per instance for any selection rule, and by the prior entropy overγ\{\\color\[rgb\]\{0,0,0\}\\gamma\}in expectation for the greedy rule\. We characterize when a wrong class is returned and give a PAC bound on the error \([§3](https://arxiv.org/html/2611.18485#S3)\)\.
- •On CodeARC, our method improves accuracy over the LM\-only agent on most evaluated language models, by up to2222percentage points with up to10\.510\.5fewer input–output examples\. Controls attribute the gains to the selection criterion and the importance weights \([§5](https://arxiv.org/html/2611.18485#S5),[§E\.4](https://arxiv.org/html/2611.18485#A5.SS4)\)\. We find that the miscalibration of the language model prior limits the accuracy of the method \([Fig\.3](https://arxiv.org/html/2611.18485#S5.F3)\)\.

## 2Information\-Theoretic Program Induction

We formalize interactive program induction as the problem of recovering atarget functionf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}from input–output observations that are revealed incrementally\. LetX\{\\color\[rgb\]\{0,0,0\}X\}be a countable set ofinputsandY\{\\color\[rgb\]\{0,0,0\}Y\}a countable set ofoutputs, and let the targetf⋆:X→Y\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\\colon\{\\color\[rgb\]\{0,0,0\}X\}\\to\{\\color\[rgb\]\{0,0,0\}Y\}be an unknown but fixed element of the candidate spaceYX\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}\. We observef⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}only through its behavior on selected inputs\. At each roundt\{\\color\[rgb\]\{0,0,0\}t\}we choose an inputx\(t\)∈X\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\in\{\\color\[rgb\]\{0,0,0\}X\}, thequery, and obtain its outputy\(t\)=f⋆​\(x\(t\)\)\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}=\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\(\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\)from the oracle\. Our goal is to return a functionf^\\widehat\{\{\\color\[rgb\]\{0,0,0\}f\}\}that closely approximatesf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}after as few queries as possible\.

### 2\.1Setup

A finite sample of input–output pairs does not pin down a target inYX\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}, since infinitely many functions agree on any finite subset ofX\{\\color\[rgb\]\{0,0,0\}X\}and disagree elsewhere\([Solomonoff, 1964](https://arxiv.org/html/2611.18485#bib.bib46)\)\. Recoveringf⋆\{\\color\[rgb\]\{0,0,0\}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 aprogram priorp0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}overYX\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}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 aninput distributionμ\{\\color\[rgb\]\{0,0,0\}\\mu\}overX\{\\color\[rgb\]\{0,0,0\}X\}, specifying the population of inputs on which the recovered function should agree withf⋆\{\\color\[rgb\]\{0,0,0\}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 thatp0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}has countable support withp0​\(f⋆\)\>0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,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 ofX\{\\color\[rgb\]\{0,0,0\}X\}\. In the setting most relevant to this work \(program synthesis over strings, whereX=Y=Σ∗\{\\color\[rgb\]\{0,0,0\}X\}=\{\\color\[rgb\]\{0,0,0\}Y\}=\{\\color\[rgb\]\{0,0,0\}\{\{\\color\[rgb\]\{0,0,0\}\\Sigma\}\}^\{\*\}\}\) the input distributionμ\{\\color\[rgb\]\{0,0,0\}\\mu\}has countably infinite support\. Comparing a candidate againstf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}on every input in this support is infeasible, and even integrating againstμ\{\\color\[rgb\]\{0,0,0\}\\mu\}to estimate disagreement requires structure we do not assume\. In the following, we derive the approximate notions of equivalence we use throughout\.

### 2\.2Approximate Equivalence

Two facts about the interactive setting force us to relax exact program equivalence\. First, exact equivalence of two computable functions is undecidable\([Rice, 1953](https://arxiv.org/html/2611.18485#bib.bib37)\), 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 whileX\{\\color\[rgb\]\{0,0,0\}X\}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μ\{\\color\[rgb\]\{0,0,0\}\\mu\}and \(ii\) can be certified by inspecting only finitely many inputs\. The first relaxation accomplishes \(i\) by declaringf\{\\color\[rgb\]\{0,0,0\}f\}equivalent tof⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}when their disagreement underμ\{\\color\[rgb\]\{0,0,0\}\\mu\}is small\. Forϵ∈\(0,1\)\{\\color\[rgb\]\{0,0,0\}\\epsilon\}\\in\(0,1\),

f∼ϵf⋆⇔errμ\(f\)≤ϵ,errμ\(f\)=defPrx∼μ\[f\(x\)≠f⋆\(x\)\]\.\\displaystyle\{\\color\[rgb\]\{0,0,0\}f\}\\sim\_\{\\color\[rgb\]\{0,0,0\}\\epsilon\}\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\\iff\{\\color\[rgb\]\{0,0,0\}\\mathrm\{err\}\_\{\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\\leq\{\\color\[rgb\]\{0,0,0\}\\epsilon\},\\qquad\{\\color\[rgb\]\{0,0,0\}\\mathrm\{err\}\_\{\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\\mathrel\{\\stackrel\{\{\\scriptstyle\\textnormal\{def\}\}\}\{\{=\}\}\}\\Pr\_\{\{\\color\[rgb\]\{0,0,0\}x\}\\sim\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\[\{\\color\[rgb\]\{0,0,0\}f\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)\\neq\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)\]\.\(1\)Checking∼ϵ\\sim\_\{\\color\[rgb\]\{0,0,0\}\\epsilon\}requires integration againstμ\{\\color\[rgb\]\{0,0,0\}\\mu\}, which we cannot do directly\. The second relaxation makes equivalence checkable\. We draw a random sampleS=\{x1,…,xN\}\{\\color\[rgb\]\{0,0,0\}S\}=\\\{\{\\color\[rgb\]\{0,0,0\}x\}\_\{1\},\\ldots,\{\\color\[rgb\]\{0,0,0\}x\}\_\{\\color\[rgb\]\{0,0,0\}N\}\\\}i\.i\.d\. fromμ\{\\color\[rgb\]\{0,0,0\}\\mu\}and replace agreement underμ\{\\color\[rgb\]\{0,0,0\}\\mu\}with agreement onS\{\\color\[rgb\]\{0,0,0\}S\},

f∼Sf⋆⇔f\(x\)=f⋆\(x\)for allx∈S\.\\displaystyle\{\\color\[rgb\]\{0,0,0\}f\}\\sim\_\{\\color\[rgb\]\{0,0,0\}S\}\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\\iff\{\\color\[rgb\]\{0,0,0\}f\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)=\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)\\text\{ for all \}\{\\color\[rgb\]\{0,0,0\}x\}\\in\{\\color\[rgb\]\{0,0,0\}S\}\.\(2\)Write\[f\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f\}\]\_\{\\sim\}\}for the∼S\\sim\_\{\\color\[rgb\]\{0,0,0\}S\}\-class off\{\\color\[rgb\]\{0,0,0\}f\}andYX/∼\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}/\{\\sim\}\}for the quotient, with\|YX/∼\|≤\|Y\|N\|\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}/\{\\sim\}\}\|\\leq\|\{\\color\[rgb\]\{0,0,0\}Y\}\|^\{\\color\[rgb\]\{0,0,0\}N\}\. BecauseS\{\\color\[rgb\]\{0,0,0\}S\}is finite,∼S\\sim\_\{\\color\[rgb\]\{0,0,0\}S\}can be verified on observed data\. BecauseS\{\\color\[rgb\]\{0,0,0\}S\}is drawn fromμ\{\\color\[rgb\]\{0,0,0\}\\mu\}, agreement onS\{\\color\[rgb\]\{0,0,0\}S\}also controlsμ\{\\color\[rgb\]\{0,0,0\}\\mu\}\-error with high probability over the draw\.

###### Proposition 2\.1\(PAC Error Bound, cf\.[Blumer et al\. 1987](https://arxiv.org/html/2611.18485#bib.bib4)\)\.

LetS=\{x1,…,xN\}\{\\color\[rgb\]\{0,0,0\}S\}=\\\{\{\\color\[rgb\]\{0,0,0\}x\}\_\{1\},\\ldots,\{\\color\[rgb\]\{0,0,0\}x\}\_\{\\color\[rgb\]\{0,0,0\}N\}\\\}be drawn i\.i\.d\. fromμ\{\\color\[rgb\]\{0,0,0\}\\mu\}\. With probability at least1−δ1\-\{\\color\[rgb\]\{0,0,0\}\\delta\}over the draw ofS\{\\color\[rgb\]\{0,0,0\}S\}, everyf∈\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}f\}\\in\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}withp0​\(f\)\>0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\>0satisfies

errμ​\(f\)≤ln⁡\(1/p0​\(f\)\)\+ln⁡\(1/δ\)N\.\\displaystyle\{\\color\[rgb\]\{0,0,0\}\\mathrm\{err\}\_\{\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\\leq\\frac\{\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\)\+\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\\delta\}\)\}\{\{\\color\[rgb\]\{0,0,0\}N\}\}\.\(3\)

The bound in[Eq\.3](https://arxiv.org/html/2611.18485#S2.E3)depends onf\{\\color\[rgb\]\{0,0,0\}f\}throughln⁡\(1/p0​\(f\)\)\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\)\. Anf\{\\color\[rgb\]\{0,0,0\}f\}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,∼\\simandYX/∼\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}/\{\\sim\}\}refer to∼S\\sim\_\{\\color\[rgb\]\{0,0,0\}S\}andYX/∼S\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}/\\sim\_\{\\color\[rgb\]\{0,0,0\}S\}for a fixed evaluation setS\{\\color\[rgb\]\{0,0,0\}S\}drawn once fromμN\{\\color\[rgb\]\{0,0,0\}\\mu\}^\{\\color\[rgb\]\{0,0,0\}N\}\.

### 2\.3Bayesian 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𝒟0⊂X×Y\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\\subset\{\\color\[rgb\]\{0,0,0\}X\}\\times\{\\color\[rgb\]\{0,0,0\}Y\}for the finite set of seed examples\(x,f⋆​\(x\)\)\(\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)\)given with the task\([Wei et al\., 2025](https://arxiv.org/html/2611.18485#bib.bib50)\), possibly empty, and𝒟t=𝒟0∪\{\(x\(s\),y\(s\)\)\}s=1t\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}=\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\\cup\\\{\(\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}s\}\)\},\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}s\}\)\}\)\\\}\_\{\{\\color\[rgb\]\{0,0,0\}s\}=1\}^\{\\color\[rgb\]\{0,0,0\}t\}for the dataset aftert\{\\color\[rgb\]\{0,0,0\}t\}oracle answers\. The posterior overYX\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}given𝒟t\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}is

p⁡\(f∣𝒟t\)=p0\(f\)⋅∏\(x,y\)∈𝒟t𝟙\{f\(x\)=y\}∑g∈YXp0\(g\)⋅∏\(x,y\)∈𝒟t𝟙\{g\(x\)=y\}\.\\displaystyle\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}f\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)=\\frac\{\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\\cdot\\prod\_\{\(\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}y\}\)\\in\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\}\\mathbbm\{1\}\\\{\{\\color\[rgb\]\{0,0,0\}f\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)=\{\\color\[rgb\]\{0,0,0\}y\}\\\}\}\{\\sum\_\{\{\\color\[rgb\]\{0,0,0\}g\}\\in\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}g\}\)\\cdot\\prod\_\{\(\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}y\}\)\\in\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\}\\mathbbm\{1\}\\\{\{\\color\[rgb\]\{0,0,0\}g\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)=\{\\color\[rgb\]\{0,0,0\}y\}\\\}\}\.\(4\)The posterior admits an equivalent recursive form,

p⁡\(f∣𝒟t\)\\displaystyle\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}f\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)=p\(f∣𝒟t−1\)⋅𝟙\{f\(x\(t\)\)=y\(t\)\}p⁡\(y\(t\)∣x\(t\),𝒟t−1\),\\displaystyle=\\frac\{\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}f\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\\cdot\\mathbbm\{1\}\\\{\{\\color\[rgb\]\{0,0,0\}f\}\(\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\)=\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\\}\}\{\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\},\(5a\)p⁡\(y∣x,𝒟t\)\\displaystyle\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)=def∑g∈YXp\(g∣𝒟t\)⋅𝟙\{g\(x\)=y\},\\displaystyle\\mathrel\{\\stackrel\{\{\\scriptstyle\\textnormal\{def\}\}\}\{\{=\}\}\}\\sum\_\{\{\\color\[rgb\]\{0,0,0\}g\}\\in\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}\}\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}g\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\\cdot\\mathbbm\{1\}\\\{\{\\color\[rgb\]\{0,0,0\}g\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)=\{\\color\[rgb\]\{0,0,0\}y\}\\\},\(5b\)wherep⁡\(y∣x,𝒟t\)\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)is the posterior predictive distribution of the output at an inputx\{\\color\[rgb\]\{0,0,0\}x\}\. The recursive form[Eq\.5a](https://arxiv.org/html/2611.18485#S2.E5.1)is the version we instantiate computationally in[§4](https://arxiv.org/html/2611.18485#S4)\.

#### Pushforward ontoYX/∼\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}/\{\\sim\}\}\.

By[Prop\.2\.1](https://arxiv.org/html/2611.18485#S2.Thmproposition1), it suffices to identify the∼\\sim\-class off⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}, since anyf∈\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}f\}\\in\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}has smallerrμ​\(f\)\{\\color\[rgb\]\{0,0,0\}\\mathrm\{err\}\_\{\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)with high probability overS\{\\color\[rgb\]\{0,0,0\}S\}\. The natural inference target is therefore the pushforward of the posterior onYX\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}onto the quotient,

p∼​\(\[f\]∼∣𝒟t\)=def∑g∈\[f\]∼p⁡\(g∣𝒟t\),\\displaystyle\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\\mathrel\{\\stackrel\{\{\\scriptstyle\\textnormal\{def\}\}\}\{\{=\}\}\}\\sum\_\{\{\\color\[rgb\]\{0,0,0\}g\}\\in\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f\}\]\_\{\\sim\}\}\}\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}g\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\),\(6\)which assigns to each equivalence class the total posterior mass of its members\.[Section2\.4](https://arxiv.org/html/2611.18485#S2.SS4)selects queries to concentratep∼\(⋅∣𝒟t\)\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)on a single class as quickly as possible\.

### 2\.4Greedy Information Gain Algorithm

We now describe an algorithm that constructs𝒟1,𝒟2,…\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{1\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{2\},\\ldotsby selecting a maximally informative queryx\(t\)∈S\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\in\{\\color\[rgb\]\{0,0,0\}S\}at a time\. Queries are selected fromS\{\\color\[rgb\]\{0,0,0\}S\}because that is where the classes are defined\. All programs in a class return the same output on everyx∈S\{\\color\[rgb\]\{0,0,0\}x\}\\in\{\\color\[rgb\]\{0,0,0\}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 somex∈S\{\\color\[rgb\]\{0,0,0\}x\}\\in\{\\color\[rgb\]\{0,0,0\}S\}, so queries inS\{\\color\[rgb\]\{0,0,0\}S\}suffice to identify\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\. Each query is chosen by the expected information gain criterion of Bayesian experimental design\([Lindley, 1956](https://arxiv.org/html/2611.18485#bib.bib29);[MacKay, 1992](https://arxiv.org/html/2611.18485#bib.bib31)\), with the equivalence class of the target as the quantity of interest\. More precisely, at each roundt=1,2,…\{\\color\[rgb\]\{0,0,0\}t\}=1,2,\\ldots:

1. 1\.Select\.Choose the inputx\(t\)∈S\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\in\{\\color\[rgb\]\{0,0,0\}S\}that maximizes the expected information gain\([Shannon, 1948](https://arxiv.org/html/2611.18485#bib.bib41);[MacKay, 1992](https://arxiv.org/html/2611.18485#bib.bib31)\)with respect top∼\(⋅∣𝒟t−1\)\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\), x\(t\)=argmaxx∈SH\[p∼\(⋅∣𝒟t−1\)\]−∑y∈Yp\(y∣x,𝒟t−1\)H\[p∼\(⋅∣𝒟t−1∪\{\(x,y\)\}\)\],\\displaystyle\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}=\\argmax\_\{\{\\color\[rgb\]\{0,0,0\}x\}\\in\{\\color\[rgb\]\{0,0,0\}S\}\}\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\\\!\\bigl\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\\bigr\]\-\\sum\_\{\{\\color\[rgb\]\{0,0,0\}y\}\\in\{\\color\[rgb\]\{0,0,0\}Y\}\}\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\\,\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\\\!\\bigl\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\\cup\\\{\(\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}y\}\)\\\}\)\\bigr\],\(7\)whereH⁡\[⋅\]\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\\cdot\]denotes the Shannon entropy andp\(⋅∣x,𝒟t−1\)\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)is the posterior predictive of[Eq\.5b](https://arxiv.org/html/2611.18485#S2.E5.2)\.
2. 2\.Query\.Observey\(t\)=f⋆​\(x\(t\)\)\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}=\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\(\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\)and set𝒟t=𝒟t−1∪\{\(x\(t\),y\(t\)\)\}\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}=\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\\cup\\\{\(\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\},\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\)\\\}\.
3. 3\.Update\.Computep\(⋅∣𝒟t\)\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)via[Eq\.5a](https://arxiv.org/html/2611.18485#S2.E5.1)and the pushforwardp∼\(⋅∣𝒟t\)\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)via[Eq\.6](https://arxiv.org/html/2611.18485#S2.E6)\.

Terminate at the first roundt≥0\{\\color\[rgb\]\{0,0,0\}t\}\\geq 0such that some classc^\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}reaches majority pushforward mass, i\.e\., whenp∼​\(c^∣𝒟t\)\>12\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\>\\tfrac\{1\}\{2\}, and return anyf^∈c^\\widehat\{\{\\color\[rgb\]\{0,0,0\}f\}\}\\in\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}\. Ifc^=\[f⋆\]∼\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}=\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}, the returnedf^\\widehat\{\{\\color\[rgb\]\{0,0,0\}f\}\}agrees withf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}onS\{\\color\[rgb\]\{0,0,0\}S\}, and[Prop\.2\.1](https://arxiv.org/html/2611.18485#S2.Thmproposition1)giveserrμ​\(f^\)≤\(ln⁡\(1/p0​\(f^\)\)\+ln⁡\(1/δ\)\)/N\{\\color\[rgb\]\{0,0,0\}\\mathrm\{err\}\_\{\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\}\(\\widehat\{\{\\color\[rgb\]\{0,0,0\}f\}\}\)\\leq\(\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\\widehat\{\{\\color\[rgb\]\{0,0,0\}f\}\}\)\)\+\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\\delta\}\)\)/\{\\color\[rgb\]\{0,0,0\}N\}except on an event of probability at mostPr\[c^≠\[f⋆\]∼\]\+δ\\Pr\[\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}\\neq\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\]\+\{\\color\[rgb\]\{0,0,0\}\\delta\}\.

## 3Query Complexity and Correctness Guarantees

We now derive a bound for the termination roundT\{\\color\[rgb\]\{0,0,0\}T\}of the greedy algorithm of[§2\.4](https://arxiv.org/html/2611.18485#S2.SS4)and characterize the returned program classc^\\widehat\{\{\\color\[rgb\]\{0,0,0\}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\)\.

Letf⋆∼p0\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\\sim\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}, conditional on the seed examples𝒟0\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}, and letH\[p∼\(⋅∣𝒟0\)\]<∞\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\]<\\inftybe the prior class entropy in bits\. Writeγ¯t=defmaxx∈S−log2⁡maxy⁡p⁡\(y∣x,𝒟t−1\)\{\\color\[rgb\]\{0,0,0\}\\bar\{\\gamma\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\\mathrel\{\\stackrel\{\{\\scriptstyle\\textnormal\{def\}\}\}\{\{=\}\}\}\\max\_\{\{\\color\[rgb\]\{0,0,0\}x\}\\in\{\\color\[rgb\]\{0,0,0\}S\}\}\-\\log\_\{2\}\\max\_\{\{\\color\[rgb\]\{0,0,0\}y\}\}\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)for the most information an answer to a query inS\{\\color\[rgb\]\{0,0,0\}S\}is guaranteed to carry at roundt\{\\color\[rgb\]\{0,0,0\}t\}\. The greedy strategy of[§2\.4](https://arxiv.org/html/2611.18485#S2.SS4)satisfies

1. \(i\)𝔼f⋆∼p0\[∑t=1Tγ¯t\]≤H\[p∼\(⋅∣𝒟0\)\]\\mathop\{\\mathbb\{E\}\}\_\{\{\\color\[rgb\]\{0,0,0\}f\}^\{\\star\}\\sim\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\}\\big\[\\sum\_\{\{\\color\[rgb\]\{0,0,0\}t\}=1\}^\{\{\\color\[rgb\]\{0,0,0\}T\}\}\{\\color\[rgb\]\{0,0,0\}\\bar\{\\gamma\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\\big\]\\leq\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\];
2. \(ii\)T≤N\{\\color\[rgb\]\{0,0,0\}T\}\\leq\{\\color\[rgb\]\{0,0,0\}N\}for every target;
3. \(iii\)ifγ¯t≥γ\>0\{\\color\[rgb\]\{0,0,0\}\\bar\{\\gamma\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\\geq\{\\color\[rgb\]\{0,0,0\}\\gamma\}\>0for allt≤T\{\\color\[rgb\]\{0,0,0\}t\}\\leq\{\\color\[rgb\]\{0,0,0\}T\}and everyf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}withp0​\(f⋆\)\>0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\)\>0, then𝔼f⋆∼p0\[T\]≤H\[p∼\(⋅∣𝒟0\)\]/γ\\mathop\{\\mathbb\{E\}\}\_\{\{\\color\[rgb\]\{0,0,0\}f\}^\{\\star\}\\sim\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\}\[\{\\color\[rgb\]\{0,0,0\}T\}\]\\leq\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\]/\{\\color\[rgb\]\{0,0,0\}\\gamma\}\.

At termination,Pr⁡\[c^=\[f⋆\]∼∣𝒟T\]=p∼​\(c^∣𝒟T\)\>12\\Pr\[\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}=\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\]=\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\)\>\\tfrac\{1\}\{2\}, i\.e\., forf⋆∼p0\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\\sim\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}the terminal mass is the exact probability that the returned program is∼S\\sim\_\{\\color\[rgb\]\{0,0,0\}S\}\-equivalent tof⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\.

###### Theorem 3\.2\(Per\-instance query complexity and correctness\)\.

Fixf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}withp0​\(f⋆\)\>0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\)\>0and letH\[p∼\(⋅∣𝒟0\)\]<∞\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\]<\\infty\. Writeγs=def−log2⁡maxy⁡p⁡\(y∣x\(s\),𝒟s−1\)\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}s\}\\mathrel\{\\stackrel\{\{\\scriptstyle\\textnormal\{def\}\}\}\{\{=\}\}\}\-\\log\_\{2\}\\max\_\{\{\\color\[rgb\]\{0,0,0\}y\}\}\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}s\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}s\}\-1\}\)for the information the answer to the query of rounds\{\\color\[rgb\]\{0,0,0\}s\}is guaranteed to carry\. Ifp∼​\(\[f⋆\]∼∣𝒟0\)≤12\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\\leq\\tfrac\{1\}\{2\}andγs≥γ\>0\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}s\}\\geq\{\\color\[rgb\]\{0,0,0\}\\gamma\}\>0for alls≤T\{\\color\[rgb\]\{0,0,0\}s\}\\leq\{\\color\[rgb\]\{0,0,0\}T\}, then any selection rule overS\{\\color\[rgb\]\{0,0,0\}S\}terminates after

T≤⌊1γ​log2​12​p∼​\(\[f⋆\]∼∣𝒟0\)⌋\+1\.\\displaystyle\{\\color\[rgb\]\{0,0,0\}T\}\\leq\\left\\lfloor\\frac\{1\}\{\{\\color\[rgb\]\{0,0,0\}\\gamma\}\}\\,\\log\_\{2\}\\frac\{1\}\{2\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\}\\right\\rfloor\+1\.\(8\)Moreover,c^≠\[f⋆\]∼\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}\\neq\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}if and only if some class with prior mass strictly greater thanp∼​\(\[f⋆\]∼∣𝒟0\)\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)is consistent with every query made\. In particular, if no class outweighs\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}under the prior, termination returnsc^=\[f⋆\]∼\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}=\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}, and under the hypotheses of[Eq\.8](https://arxiv.org/html/2611.18485#S3.E8)it does so within that bound\.

[Theorem3\.1](https://arxiv.org/html/2611.18485#S3.Thmtheorem1)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 inS\{\\color\[rgb\]\{0,0,0\}S\}and therefore at leastγ¯t\{\\color\[rgb\]\{0,0,0\}\\bar\{\\gamma\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}, the largest guaranteed information any query inS\{\\color\[rgb\]\{0,0,0\}S\}offers\.[Theorem3\.2](https://arxiv.org/html/2611.18485#S3.Thmtheorem2)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 overS\{\\color\[rgb\]\{0,0,0\}S\}with the guaranteed information of that rule’s own queries, and[§5](https://arxiv.org/html/2611.18485#S5)empirically evaluates several such rules\. In both, the rate of convergence is set byγ¯t\{\\color\[rgb\]\{0,0,0\}\\bar\{\\gamma\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}overS\{\\color\[rgb\]\{0,0,0\}S\}andγt\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}t\}at the selected query, which are determined by how the program prior spreads mass across classes and how finelyS\{\\color\[rgb\]\{0,0,0\}S\}, drawn from the input distribution, separates them\.

#### Improvement over non\-adaptive querying\.

Fix a target errorϵ\{\\color\[rgb\]\{0,0,0\}\\epsilon\}and confidenceδ\{\\color\[rgb\]\{0,0,0\}\\delta\}\. A non\-adaptive strategy draws inputs at random fromμ\{\\color\[rgb\]\{0,0,0\}\\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/\{\\color\[rgb\]\{0,0,0\}\\delta\}\)/\{\\color\[rgb\]\{0,0,0\}\\epsilon\}\)labeled inputs, since a program that disagrees withf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}on a set ofμ\{\\color\[rgb\]\{0,0,0\}\\mu\}\-massϵ\{\\color\[rgb\]\{0,0,0\}\\epsilon\}passesmmrandom inputs with probability\(1−ϵ\)m≥e−2​m​ϵ\(1\-\{\\color\[rgb\]\{0,0,0\}\\epsilon\}\)^\{m\}\\geq e^\{\-2m\{\\color\[rgb\]\{0,0,0\}\\epsilon\}\}forϵ≤12\{\\color\[rgb\]\{0,0,0\}\\epsilon\}\\leq\\tfrac\{1\}\{2\}\([Shalev\-Shwartz & Ben\-David, 2014](https://arxiv.org/html/2611.18485#bib.bib40), see, e\.g\.,\), and by[Prop\.2\.1](https://arxiv.org/html/2611.18485#S2.Thmproposition1)inputs of that order also suffice, up to theln⁡\(1/p0​\(f\)\)\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\)term\. The greedy algorithm needs an evaluation set of the same size, but the oracle labels only theT≤N\{\\color\[rgb\]\{0,0,0\}T\}\\leq\{\\color\[rgb\]\{0,0,0\}N\}inputs it queries\. Sincef⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}lies in its own class, that class has prior mass at leastp0​\(f⋆\)\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\)whateverS\{\\color\[rgb\]\{0,0,0\}S\}is, so under the hypotheses of[Thm\.3\.2](https://arxiv.org/html/2611.18485#S3.Thmtheorem2)the algorithm asks at most⌊1γ​log2​12​p0​\(f⋆\)⌋\+1\\lfloor\\tfrac\{1\}\{\{\\color\[rgb\]\{0,0,0\}\\gamma\}\}\\log\_\{2\}\\tfrac\{1\}\{2\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\)\}\\rfloor\+1queries, a number that does not depend onϵ\{\\color\[rgb\]\{0,0,0\}\\epsilon\}\. The non\-adaptive cost grows with1/ϵ1/\{\\color\[rgb\]\{0,0,0\}\\epsilon\}, while the adaptive cost is set by how plausible the target is under the prior\. The PAC certificate of[Prop\.2\.1](https://arxiv.org/html/2611.18485#S2.Thmproposition1)then holds for the returned program, conditional on the algorithm returning the target’s class\.

#### The role of\|S\|\|\{\\color\[rgb\]\{0,0,0\}S\}\|\.

Combining[Prop\.2\.1](https://arxiv.org/html/2611.18485#S2.Thmproposition1)with[Thms\.3\.1](https://arxiv.org/html/2611.18485#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2611.18485#S3.Thmtheorem2)gives a complete guarantee\. The greedy algorithm terminates after at most⌊1γ​log2​12​p∼​\(\[f⋆\]∼∣𝒟0\)⌋\+1\\lfloor\\tfrac\{1\}\{\{\\color\[rgb\]\{0,0,0\}\\gamma\}\}\\log\_\{2\}\\tfrac\{1\}\{2\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\}\\rfloor\+1queries when every answer carries at leastγ\{\\color\[rgb\]\{0,0,0\}\\gamma\}bits, for a target drawn from the prior it returns the target’s class with probabilityp∼​\(c^∣𝒟T\)\>12\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\)\>\\tfrac\{1\}\{2\}, and since[Prop\.2\.1](https://arxiv.org/html/2611.18485#S2.Thmproposition1)holds for every program in\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}simultaneously, the returned program satisfiesPr\[errμ\(f^\)\>\(ln\(1/p0\(f^\)\)\+ln\(1/δ\)\)/N\]≤Pr\[c^≠\[f⋆\]∼\]\+δ\\Pr\[\{\\color\[rgb\]\{0,0,0\}\\mathrm\{err\}\_\{\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\}\(\\widehat\{\{\\color\[rgb\]\{0,0,0\}f\}\}\)\>\(\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\\widehat\{\{\\color\[rgb\]\{0,0,0\}f\}\}\)\)\+\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\\delta\}\)\)/\{\\color\[rgb\]\{0,0,0\}N\}\]\\leq\\Pr\[\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}\\neq\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\]\+\{\\color\[rgb\]\{0,0,0\}\\delta\}\. The size of the evaluation set enters the two bounds in opposite directions\. A largerS\{\\color\[rgb\]\{0,0,0\}S\}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\|\|\{\\color\[rgb\]\{0,0,0\}S\}\|empirically in[Section5](https://arxiv.org/html/2611.18485#S5)\.

## 4Approximate Inference with a Language Model

The greedy algorithm of[§2\.4](https://arxiv.org/html/2611.18485#S2.SS4)requires the pushforward entropyH\[p∼\(⋅∣𝒟t\)\]\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}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 thepushforward from the weights\.

### 4\.1Language Model Proposal

#### Language model preliminaries\.

AnalphabetΣ\{\{\\color\[rgb\]\{0,0,0\}\\Sigma\}\}is a finite, non\-empty set of symbols,Σ∗\{\\color\[rgb\]\{0,0,0\}\{\{\\color\[rgb\]\{0,0,0\}\\Sigma\}\}^\{\*\}\}the set of all strings𝒙\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}formed fromΣ\{\{\\color\[rgb\]\{0,0,0\}\\Sigma\}\}\(including the empty string\), and\|𝒙\|\|\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\|the length of𝒙\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\. Alanguage modelpLM\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\_\{\\mathrm\{LM\}\}\}is a probability distribution overΣ∗\{\\color\[rgb\]\{0,0,0\}\{\{\\color\[rgb\]\{0,0,0\}\\Sigma\}\}^\{\*\}\}\. Theprefix probabilityp→LM​\(𝒙\)=def∑𝒙′∈Σ∗pLM​\(𝒙​𝒙′\)\{\\color\[rgb\]\{0,0,0\}\\vec\{\{\{\\color\[rgb\]\{0,0,0\}p\}\}\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\)\\mathrel\{\\stackrel\{\{\\scriptstyle\\textnormal\{def\}\}\}\{\{=\}\}\}\\sum\_\{\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}^\{\\prime\}\\in\{\\color\[rgb\]\{0,0,0\}\{\{\\color\[rgb\]\{0,0,0\}\\Sigma\}\}^\{\*\}\}\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\\,\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}^\{\\prime\}\)is the probability that a string drawn frompLM\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\_\{\\mathrm\{LM\}\}\}begins with𝒙\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\. Wheneverp→LM​\(𝒙\)\>0\{\\color\[rgb\]\{0,0,0\}\\vec\{\{\{\\color\[rgb\]\{0,0,0\}p\}\}\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\)\>0, theconditional prefix probabilityis

p→LM​\(𝒙′∣𝒙\)=def\{pLM​\(𝒙\)/p→LM​\(𝒙\)if​𝒙′=□,p→LM​\(𝒙​𝒙′\)/p→LM​\(𝒙\)otherwise,\\displaystyle\{\\color\[rgb\]\{0,0,0\}\\vec\{\{\{\\color\[rgb\]\{0,0,0\}p\}\}\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}^\{\\prime\}\\mid\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\)\\mathrel\{\\stackrel\{\{\\scriptstyle\\textnormal\{def\}\}\}\{\{=\}\}\}\\begin\{cases\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\)/\{\\color\[rgb\]\{0,0,0\}\\vec\{\{\{\\color\[rgb\]\{0,0,0\}p\}\}\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\)&\\text\{if \}\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}^\{\\prime\}=\{\\color\[rgb\]\{0,0,0\}\\raisebox\{\-0\.2pt\}\{$\{\\square\}$\}\},\\\\ \{\\color\[rgb\]\{0,0,0\}\\vec\{\{\{\\color\[rgb\]\{0,0,0\}p\}\}\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\\,\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}^\{\\prime\}\)/\{\\color\[rgb\]\{0,0,0\}\\vec\{\{\{\\color\[rgb\]\{0,0,0\}p\}\}\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\)&\\text\{otherwise,\}\\end\{cases\}\(9\)where□∉Σ\{\\color\[rgb\]\{0,0,0\}\\raisebox\{\-0\.2pt\}\{$\{\\square\}$\}\}\\notin\{\{\\color\[rgb\]\{0,0,0\}\\Sigma\}\}is a distinguished end\-of\-string delimiter\. Iterating[Eq\.9](https://arxiv.org/html/2611.18485#S4.E9)yields the autoregressive factorization

pLM​\(𝒙\)=p→LM​\(□∣𝒙\)​∏t=1\|𝒙\|p→LM​\(xt∣𝒙<t\),\\displaystyle\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\)=\{\\color\[rgb\]\{0,0,0\}\\vec\{\{\{\\color\[rgb\]\{0,0,0\}p\}\}\}\_\{\\mathrm\{LM\}\}\}\(\{\\color\[rgb\]\{0,0,0\}\\raisebox\{\-0\.2pt\}\{$\{\\square\}$\}\}\\mid\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\)\\prod\_\{\{\\color\[rgb\]\{0,0,0\}t\}=1\}^\{\|\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\|\}\{\\color\[rgb\]\{0,0,0\}\\vec\{\{\{\\color\[rgb\]\{0,0,0\}p\}\}\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}x\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\\mid\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\_\{<\{\\color\[rgb\]\{0,0,0\}t\}\}\),\(10\)which computespLM​\(𝒙\)\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\)from\|𝒙\|\+1\|\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\|\+1next\-token queries without enumeratingΣ∗\{\\color\[rgb\]\{0,0,0\}\{\{\\color\[rgb\]\{0,0,0\}\\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 \([App\.F](https://arxiv.org/html/2611.18485#A6)gives the prompts\), so that its distribution over completions is a distribution over source code\. Strictly, this makespLM\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\_\{\\mathrm\{LM\}\}\}a distribution over*implementations*, whereas a*program*is an input–output behavior, and two distinct strings𝒙1≠𝒙2\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\_\{1\}\\neq\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\_\{2\}may decode to the same function whilepLM​\(𝒙1\)≠pLM​\(𝒙2\)\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\_\{1\}\)\\neq\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\_\{2\}\)\. The equivalence relation∼\\simfrom[§2\.2](https://arxiv.org/html/2611.18485#S2.SS2)and the pushforwardp∼\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}from[§2\.3](https://arxiv.org/html/2611.18485#S2.SS3)collapse implementations that agree onS\{\\color\[rgb\]\{0,0,0\}S\}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\.10](https://arxiv.org/html/2611.18485#S4.E10)makes them tractable\.

At each roundt\{\\color\[rgb\]\{0,0,0\}t\}we encode the observed examples into a prompt\([Chan et al\., 2024](https://arxiv.org/html/2611.18485#bib.bib5)\), a context stringprompt⁡\(𝒟t\)∈Σ∗\{\\color\[rgb\]\{0,0,0\}\\mathrm\{prompt\}\}\(\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\\in\{\\color\[rgb\]\{0,0,0\}\{\{\\color\[rgb\]\{0,0,0\}\\Sigma\}\}^\{\*\}\}\([App\.F](https://arxiv.org/html/2611.18485#A6)\), and condition the LM on it\. Its completions are implementations𝒙∈Σ∗\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\\in\{\\color\[rgb\]\{0,0,0\}\{\{\\color\[rgb\]\{0,0,0\}\\Sigma\}\}^\{\*\}\}, each of which decodes to a function by execution\. The proposal over implementations is

qt​\(𝒙\)=defpLM​\(𝒙∣prompt⁡\(𝒟t\)\),\\displaystyle\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\)\\mathrel\{\\stackrel\{\{\\scriptstyle\\textnormal\{def\}\}\}\{\{=\}\}\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\_\{\\mathrm\{LM\}\}\}\(\{\{\\color\[rgb\]\{0,0,0\}\\bm\{x\}\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathrm\{prompt\}\}\(\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\),\(11\)and we take the program prior to be the proposal before any query,p0=defq0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\\mathrel\{\\stackrel\{\{\\scriptstyle\\textnormal\{def\}\}\}\{\{=\}\}\}\{\\color\[rgb\]\{0,0,0\}q\}\_\{0\}\. The fixed objectsp0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}andμ\{\\color\[rgb\]\{0,0,0\}\\mu\}define the guarantees of[§3](https://arxiv.org/html/2611.18485#S3), while the proposalqt\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}is an approximation mechanism whose quality affects practical efficiency but not the guarantees for the exact posterior\.

### 4\.2Importance Sampling Estimates

#### Importance weights\.

We drawM\{\\color\[rgb\]\{0,0,0\}M\}implementations fromqt\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}, writef1,…,fM\{\\color\[rgb\]\{0,0,0\}f\}\_\{1\},\\ldots,\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}M\}for their decoded functions andp0​\(fm\)\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\),qt​\(fm\)\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}\(\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\)for the densities of the sampled implementations, and assign self\-normalizing importance weights

wm=p0\(fm\)⋅∏\(x,y\)∈𝒟t𝟙\{fm\(x\)=y\}qt​\(fm\)\.\\displaystyle\{\\color\[rgb\]\{0,0,0\}w\}\_\{\\color\[rgb\]\{0,0,0\}m\}=\\frac\{\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\)\\cdot\\prod\_\{\(\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}y\}\)\\in\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\}\\mathbbm\{1\}\\\{\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)=\{\\color\[rgb\]\{0,0,0\}y\}\\\}\}\{\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}\(\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\)\}\.\(12\)Programs inconsistent with the observed data𝒟t\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}receive zero weight\. For consistent programs,p0​\(fm\)/qt​\(fm\)\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\)/\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}\(\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\)corrects for the mismatch between prior and proposal\. Becauseqt\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}is already conditioned on𝒟t\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}, it concentrates on consistent programs\. At round00the weights reduce to the consistency indicator, sincep0=q0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}=\{\\color\[rgb\]\{0,0,0\}q\}\_\{0\}\. Density ratios enter only when particles are resampled from a laterqt\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}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\.12](https://arxiv.org/html/2611.18485#S4.E12), which we do because intermediate reasoning and a tuned sampling temperature improve the sampled programs \([§E\.6](https://arxiv.org/html/2611.18485#A5.SS6)\)\.[SectionE\.4](https://arxiv.org/html/2611.18485#A5.SS4)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\.

#### Pushforward mass\.

The pushforward mass on a classc\{\\color\[rgb\]\{0,0,0\}c\}is a posterior expectation,p∼\(c∣𝒟t\)=𝔼f∼p\(⋅∣𝒟t\)\[𝟙\{f∈c\}\]\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)=\\mathop\{\\mathbb\{E\}\}\_\{\{\\color\[rgb\]\{0,0,0\}f\}\\sim\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\}\[\\mathbbm\{1\}\\\{\{\\color\[rgb\]\{0,0,0\}f\}\\in\{\\color\[rgb\]\{0,0,0\}c\}\\\}\], which the self\-normalized importance sampling \(SNIS\) estimator\([Owen, 2013](https://arxiv.org/html/2611.18485#bib.bib35)\)replaces by the weighted share of the particles in the class,

p^∼\(c∣𝒟t\)=∑m:fm∈cwm∑m=1Mwm,\\displaystyle\{\\color\[rgb\]\{0,0,0\}\{\\widehat\{\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}\}\}\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)=\\frac\{\\sum\_\{\{\\color\[rgb\]\{0,0,0\}m\}:\\,\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\\in\{\\color\[rgb\]\{0,0,0\}c\}\}\{\\color\[rgb\]\{0,0,0\}w\}\_\{\\color\[rgb\]\{0,0,0\}m\}\}\{\\sum\_\{\{\\color\[rgb\]\{0,0,0\}m\}=1\}^\{\\color\[rgb\]\{0,0,0\}M\}\{\\color\[rgb\]\{0,0,0\}w\}\_\{\\color\[rgb\]\{0,0,0\}m\}\},\(13\)where class membership is checked by comparing outputs onS\{\\color\[rgb\]\{0,0,0\}S\}, as two programs share a∼\\sim\-class if and only if they agree on everyx∈S\{\\color\[rgb\]\{0,0,0\}x\}\\in\{\\color\[rgb\]\{0,0,0\}S\}\.

#### Entropy and information gain\.

Plugging[Eq\.13](https://arxiv.org/html/2611.18485#S4.E13)into the definition of entropy gives the plug\-in estimator

H^\[p∼\(⋅∣𝒟t\)\]=−∑cp^∼\(c∣𝒟t\)log2p^∼\(c∣𝒟t\)\.\\displaystyle\\widehat\{\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\]=\-\\sum\_\{\\color\[rgb\]\{0,0,0\}c\}\{\\color\[rgb\]\{0,0,0\}\{\\widehat\{\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}\}\}\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\\log\_\{2\}\{\\color\[rgb\]\{0,0,0\}\{\\widehat\{\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}\}\}\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\.\(14\)The information gain for a candidate queryx\{\\color\[rgb\]\{0,0,0\}x\}is estimated by partitioning the particles by predicted outputfm​\(x\)\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\(\{\\color\[rgb\]\{0,0,0\}x\}\), computingH^\\widehat\{\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\}on each partition with renormalized weights, and weighting by the estimated posterior predictive

p^\(y∣x,𝒟t\)=∑m:fm​\(x\)=ywm∑m=1Mwm\.\\displaystyle\\widehat\{\{\\color\[rgb\]\{0,0,0\}p\}\}\(\{\\color\[rgb\]\{0,0,0\}y\}\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)=\\frac\{\\sum\_\{\{\\color\[rgb\]\{0,0,0\}m\}:\\,\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)=\{\\color\[rgb\]\{0,0,0\}y\}\}\{\\color\[rgb\]\{0,0,0\}w\}\_\{\\color\[rgb\]\{0,0,0\}m\}\}\{\\sum\_\{\{\\color\[rgb\]\{0,0,0\}m\}=1\}^\{\\color\[rgb\]\{0,0,0\}M\}\{\\color\[rgb\]\{0,0,0\}w\}\_\{\\color\[rgb\]\{0,0,0\}m\}\}\.\(15\)The greedy step of[§2\.4](https://arxiv.org/html/2611.18485#S2.SS4)is a finite maximization overS\{\\color\[rgb\]\{0,0,0\}S\}, withH^\\widehat\{\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\}in place ofH\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}andp^\\widehat\{\{\\color\[rgb\]\{0,0,0\}p\}\}in place ofp\{\\color\[rgb\]\{0,0,0\}p\}\.[Algorithm1](https://arxiv.org/html/2611.18485#alg1)summarizes the resulting procedure, with an effective\-sample\-size test that redraws the particles from the current proposal when the weights degenerate\.

Algorithm 1Greedy Information Gain Program Induction1\.Input distribution

μ\{\\color\[rgb\]\{0,0,0\}\\mu\}; program prior

p0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}; LM proposal

qt\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}; oracle for

f⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}; evaluation size

N\{\\color\[rgb\]\{0,0,0\}N\}; particle budget

M\{\\color\[rgb\]\{0,0,0\}M\}; ESS threshold

τESS\{\\color\[rgb\]\{0,0,0\}\\tau\_\{\\mathrm\{ESS\}\}\}\.

2\.Draw

S=\{x1,…,xN\}​∼i\.i\.d\.​μ\{\\color\[rgb\]\{0,0,0\}S\}=\\\{\{\\color\[rgb\]\{0,0,0\}x\}\_\{1\},\\ldots,\{\\color\[rgb\]\{0,0,0\}x\}\_\{\\color\[rgb\]\{0,0,0\}N\}\\\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}\{\\color\[rgb\]\{0,0,0\}\\mu\}\.⊳\\trianglerightFix evaluation set

3\.Sample

f1,…,fM∼q0\{\\color\[rgb\]\{0,0,0\}f\}\_\{1\},\\ldots,\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}M\}\\sim\{\\color\[rgb\]\{0,0,0\}q\}\_\{0\}; compute

wm\{\\color\[rgb\]\{0,0,0\}w\}\_\{\\color\[rgb\]\{0,0,0\}m\}via[Eq\.12](https://arxiv.org/html/2611.18485#S4.E12)\.⊳\\trianglerightInitialize particles

4\.

t←0\{\\color\[rgb\]\{0,0,0\}t\}\\leftarrow 0;

𝒟0←\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\\leftarrowseed examples\.

5\.whileno class

c\{\\color\[rgb\]\{0,0,0\}c\}has

p^∼​\(c∣𝒟t\)\>12\{\\color\[rgb\]\{0,0,0\}\{\\widehat\{\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}\}\}\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\>\\tfrac\{1\}\{2\}:

6\.

t←t\+1\{\\color\[rgb\]\{0,0,0\}t\}\\leftarrow\{\\color\[rgb\]\{0,0,0\}t\}\+1\.

7\.

x\(t\)←argmaxx∈SH^\[p∼\(⋅∣𝒟t−1\)\]−∑yp^\(y∣x,𝒟t−1\)H^\[p∼\(⋅∣𝒟t−1∪\{\(x,y\)\}\)\]\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\leftarrow\\argmax\_\{\{\\color\[rgb\]\{0,0,0\}x\}\\in\{\\color\[rgb\]\{0,0,0\}S\}\}\\,\\widehat\{\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\]\-\\sum\_\{\{\\color\[rgb\]\{0,0,0\}y\}\}\\widehat\{\{\\color\[rgb\]\{0,0,0\}p\}\}\(\{\\color\[rgb\]\{0,0,0\}y\}\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\\,\\widehat\{\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\\cup\\\{\(\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}y\}\)\\\}\)\]\.

8\.Observe

y\(t\)←f⋆​\(x\(t\)\)\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\leftarrow\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\(\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\);

𝒟t←𝒟t−1∪\{\(x\(t\),y\(t\)\)\}\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\\leftarrow\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\\cup\\\{\(\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\},\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\)\\\}\.⊳\\trianglerightQuery oracle

9\.for

m=1,…,M\{\\color\[rgb\]\{0,0,0\}m\}=1,\\ldots,\{\\color\[rgb\]\{0,0,0\}M\}:

10\.if

fm​\(x\(t\)\)≠y\(t\)\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}m\}\(\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\)\\neq\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}:

wm←0\{\\color\[rgb\]\{0,0,0\}w\}\_\{\\color\[rgb\]\{0,0,0\}m\}\\leftarrow 0
11\.Renormalize weights\.⊳\\trianglerightEliminate inconsistent particles

12\.if

ESS=\(∑mwm\)2/∑mwm2<τESS\\mathrm\{ESS\}=\\bigl\(\\sum\_\{\\color\[rgb\]\{0,0,0\}m\}\{\\color\[rgb\]\{0,0,0\}w\}\_\{\\color\[rgb\]\{0,0,0\}m\}\\bigr\)^\{2\}/\\sum\_\{\\color\[rgb\]\{0,0,0\}m\}\{\\color\[rgb\]\{0,0,0\}w\}\_\{\\color\[rgb\]\{0,0,0\}m\}^\{2\}<\{\\color\[rgb\]\{0,0,0\}\\tau\_\{\\mathrm\{ESS\}\}\}:

13\.Resample

f1,…,fM∼qt\{\\color\[rgb\]\{0,0,0\}f\}\_\{1\},\\ldots,\{\\color\[rgb\]\{0,0,0\}f\}\_\{\\color\[rgb\]\{0,0,0\}M\}\\sim\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}; recompute weights\.

14\.return

f^\\widehat\{\{\\color\[rgb\]\{0,0,0\}f\}\}in the majority class

c^=argmaxcp^∼​\(c∣𝒟t\)\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}=\\argmax\_\{\\color\[rgb\]\{0,0,0\}c\}\{\\color\[rgb\]\{0,0,0\}\{\\widehat\{\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}\}\}\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\.

#### Approximation gaps\.

Under absolute continuity of the posterior with respect toqt\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}\(i\.e\.,p⁡\(f∣𝒟t\)\>0⟹qt​\(f\)\>0\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}f\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\>0\\implies\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\>0\), exact weights, and finitely many classes, the SNIS estimatesp^∼​\(c∣𝒟t\)\{\\color\[rgb\]\{0,0,0\}\{\\widehat\{\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}\}\}\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)converge top∼​\(c∣𝒟t\)\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)asM→∞\{\\color\[rgb\]\{0,0,0\}M\}\\to\\infty\([Owen, 2013](https://arxiv.org/html/2611.18485#bib.bib35), e\.g\.,\), and sinceH^\\widehat\{\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\}is continuous in these estimates,H^\[p∼\(⋅∣𝒟t\)\]→H\[p∼\(⋅∣𝒟t\)\]\\widehat\{\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\]\\to\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\]by the continuous mapping theorem\. The guarantees of[§3](https://arxiv.org/html/2611.18485#S3)are stated for the exact posterior, and for finiteM\{\\color\[rgb\]\{0,0,0\}M\}two things can go wrong\. The particles may miss\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}entirely, or a wrong class may exceed the threshold before enough of them land in\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}, which the miscalibration of the prior makes common \([Fig\.3](https://arxiv.org/html/2611.18485#S5.F3)\)\.[SectionE\.5](https://arxiv.org/html/2611.18485#A5.SS5)varies the particle budget, and[Tab\.4](https://arxiv.org/html/2611.18485#A5.T4)and[App\.B](https://arxiv.org/html/2611.18485#A2)quantify how many runs terminate on a wrong class or without a consistent program\.

Table 1:Results across models and methods on the full anonymized CodeARC split\. Entries are means over55independent 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 of3030\.

## 5Experiments

We now evaluate the practical implications of our work on a programming induction benchmark in Python\([Wei et al\., 2025](https://arxiv.org/html/2611.18485#bib.bib50), CodeARC;\)\. 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\.

1. RQ1\.Does[Alg\.1](https://arxiv.org/html/2611.18485#alg1)improve accuracy and oracle cost over the CodeARC LM agent?
2. RQ2\.Does EIG ask queries with more guaranteed information than other selection criteria, and how much do the queries add over the prior alone?
3. RQ3\.How does the choice of evaluation set sizeN\{\\color\[rgb\]\{0,0,0\}N\}trade off convergence and correctness, as hypothesized in[§3](https://arxiv.org/html/2611.18485#S3.SS0.SSS0.Px2)?
4. RQ4\.What are the failure modes of language model priors in program induction?

### 5\.1Setup

#### Dataset\.

We evaluate the proposed approach on the inductive inference benchmark CodeARC\([Wei et al\., 2025](https://arxiv.org/html/2611.18485#bib.bib50)\), whose11141114Python functions are drawn from HumanEval\+, MBPP\+, and APPS and range from22to7474lines, 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 queryf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}on a chosen inputx\{\\color\[rgb\]\{0,0,0\}x\}to obtainf⋆​\(x\)\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\(\{\\color\[rgb\]\{0,0,0\}x\}\), and equivalence queries \(EQ\), which ask the oracle whether a candidatef^\\widehat\{\{\\color\[rgb\]\{0,0,0\}f\}\}equalsf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}and return a counterexample if it does not, under a fixed MQ and EQ invocation budget\.111We note that our setup is equivalent to the CodeARC setup if the EQ budget is 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[Wei et al\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib50), we provide a small number of*seed invocations*\(initial input–output examples that we also use to conditionμ\{\\color\[rgb\]\{0,0,0\}\\mu\}\), evaluating both11and1010seed invocations, and set the query budget to3030input–output pairs, which includes the seed invocations\. For consistency with their results, the CodeARC agent may additionally issue22equivalence queries, while our algorithm makes none and submits its returned program once for evaluation\. We evaluate on the full split and report means over55independent seed runs\. The input distributionμ\{\\color\[rgb\]\{0,0,0\}\\mu\}fixes the inputs on which agreement withf⋆\{\\color\[rgb\]\{0,0,0\}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 all1010seed invocations of the benchmark and keep it fixed across settings \([App\.D](https://arxiv.org/html/2611.18485#A4)\)\. For the models that overlap with[Wei et al\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib50), we reproduce their reported results within seed noise\.

#### Models\.

We evaluate our algorithm on six models of various sizes: Llama3\.2\-3B and Llama3\.1\-8B\([Llama Team, 2024](https://arxiv.org/html/2611.18485#bib.bib30)\), Qwen2\.5\-7B and Qwen2\.5\-32B\([Yang et al\., 2025](https://arxiv.org/html/2611.18485#bib.bib51)\), Olmo3\-7B\([Team Olmo et al\., 2025](https://arxiv.org/html/2611.18485#bib.bib48)\), and Ministral\-8B\([Mistral AI team, 2024](https://arxiv.org/html/2611.18485#bib.bib33)\)\. 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 convergesefficientlyon 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\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib50), we evaluate the correctness of the generated programs extrinsically using the differential testing toolMokav\([Etemadi et al\., 2025](https://arxiv.org/html/2611.18485#bib.bib12)\)\. We fixMokav’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\.

Figure 1:\(a\) Cumulative accuracy \(top\) and fraction of runs terminated \(bottom\) by round, for[Alg\.1](https://arxiv.org/html/2611.18485#alg1)under four query selection strategies, the CodeARC agent \(LM only\), and the per\-instance bound of[Thm\.3\.2](https://arxiv.org/html/2611.18485#S3.Thmtheorem2)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\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}t\}, by round, averaged over the runs still querying and pooled across models\. A dashed line marks the last round with at least200200runs of that strategy still querying, which is where the strategy has typically terminated\. 95% CIs over five seeds\.

### 5\.2Results

#### RQ1:[Algorithm1](https://arxiv.org/html/2611.18485#alg1)with EIG improves accuracy and query efficiency over the LM only agent\.

[Tab\.1](https://arxiv.org/html/2611.18485#S4.T1)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\+\.22\) as well as oracle querying efficiency \(up to10\.510\.5fewer 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\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib50), and our failure mode analysis in[Tab\.4](https://arxiv.org/html/2611.18485#A5.T4)\)\. Aside from this, the method commonly struggles with early termination due to early posterior concentration \(RQ4\), which is the case[Thm\.3\.2](https://arxiv.org/html/2611.18485#S3.Thmtheorem2)excludes, a heavier class that stays consistent with every answer\. Our ablation in[Fig\.5](https://arxiv.org/html/2611.18485#A5.F5)shows that the choice of proposal prompt and temperature reduces this\.

#### 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](https://arxiv.org/html/2611.18485#S5.F1)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\.70to\.99\.99guaranteed bits per query against\.31\.31to\.52\.52for 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](https://arxiv.org/html/2611.18485#S5.F1),[Tab\.6](https://arxiv.org/html/2611.18485#A5.T6)\)\. 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 \([Tabs\.1](https://arxiv.org/html/2611.18485#S4.T1)and[6](https://arxiv.org/html/2611.18485#A5.T6)\)\.[Table5](https://arxiv.org/html/2611.18485#A5.T5)reports the bound of[Thm\.3\.2](https://arxiv.org/html/2611.18485#S3.Thmtheorem2)on the EIG runs, which is attained in\.37\.37of them\.[SectionE\.4](https://arxiv.org/html/2611.18485#A5.SS4)further compares against uniform weights, minimax selection, and a compute\-matched propose\-and\-verify baseline\.

Figure 2:N\{\\color\[rgb\]\{0,0,0\}N\}ablation on three models\. Top: share of runs converging on\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\. Bottom: accuracy given convergence\. 95% CIs over runs, three seeds\.Figure 3:Calibration of the prior majority class, with ECE in the legend\. 95% CIs over five seeds\.

#### RQ3: LargerS\{\\color\[rgb\]\{0,0,0\}S\}makes convergence on the target’s class rarer but more reliable\.

[Figure3](https://arxiv.org/html/2611.18485#S5.F3)presents an ablation of the evaluation set sizeN\{\\color\[rgb\]\{0,0,0\}N\}from 2 to 256 for three models\. As predicted in[Section3](https://arxiv.org/html/2611.18485#S3.SS0.SSS0.Px2), a smallerN\{\\color\[rgb\]\{0,0,0\}N\}makes\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}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 withf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}onS\{\\color\[rgb\]\{0,0,0\}S\}\. AsS\{\\color\[rgb\]\{0,0,0\}S\}grows, convergence on\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}becomes rarer but a reliable indicator of correctness\. The rising conditional accuracy instantiates[Prop\.2\.1](https://arxiv.org/html/2611.18485#S2.Thmproposition1), since agreement withf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}on more sampled inputs means fewer disagreements on unseen ones\.

#### RQ4: The language model prior is miscalibrated\.

[Figure3](https://arxiv.org/html/2611.18485#S5.F3)is a calibration plot of the prior majority class against the CodeARC targets\.222The CodeARC targets may not coincide with the programs humans would consider plausible, against which the prior may be calibrated differently\.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](https://arxiv.org/html/2611.18485#S3.Thmtheorem2), a run converges on a wrong program if the prior strongly favors a wrong class, which this miscalibration makes common \([Tab\.4](https://arxiv.org/html/2611.18485#A5.T4)\)\.

## 6Conclusion

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𝒪⁡\(1γ​log⁡1/p0​\(f⋆\)\)\{\\color\[rgb\]\{0,0,0\}\\mathcal\{O\}\}\(\\tfrac\{1\}\{\{\\color\[rgb\]\{0,0,0\}\\gamma\}\}\\log 1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\)\)oracle invocations when every answer carries at leastγ\{\\color\[rgb\]\{0,0,0\}\\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\.

## References

- Austin et al\. \(2021\)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](https://arxiv.org/abs/2108.07732)\.
- Barke et al\. \(2024\)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](https://openreview.net/forum?id=5jt0ZSA6Co)\.
- Barnaby et al\. \(2025\)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](https://doi.org/10.1145/3763102)\.
- Blumer et al\. \(1987\)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](https://doi.org/10.1016/0020-0190(87)90114-1)\.
- Chan et al\. \(2024\)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](https://openreview.net/forum?id=FTpOwIaWUz)\.
- Chan et al\. \(2026\)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](https://doi.org/10.1145/3772318.3791265)\.
- Chen et al\. \(2023\)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](https://openreview.net/forum?id=ktrw68Cmu9c)\.
- Chen et al\. \(2021\)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](https://arxiv.org/abs/2107.03374)\.
- Dasgupta \(2004\)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/c61fbef63df5ff317aecdc3670094472\-Abstract\.html](https://proceedings.neurips.cc/paper/2004/hash/c61fbef63df5ff317aecdc3670094472-Abstract.html)\.
- Ellis et al\. \(2021\)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](https://doi.org/10.1145/3453483.3454080)\.
- Ellis et al\. \(2022\)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](https://doi.org/10.1038/s41467-022-32012-w)\.
- Etemadi et al\. \(2025\)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](https://doi.org/10.1016/j.jss.2025.112571)\.
- Golovin & Krause \(2011\)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](https://www.jair.org/index.php/jair/article/view/10731)\.
- Golovin et al\. \(2010\)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/1e6e0a04d20f50967c64dac2d639a577\-Abstract\.html](https://proceedings.neurips.cc/paper_files/paper/2010/hash/1e6e0a04d20f50967c64dac2d639a577-Abstract.html)\.
- Grand et al\. \(2026\)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](https://openreview.net/forum?id=EQhUvWH78U)\.
- Gulwani \(2011\)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](https://doi.org/10.1145/1926385.1926423)\.
- Gulwani et al\. \(2012\)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](https://doi.org/10.1145/2240236.2240260)\.
- Gulwani et al\. \(2017\)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](https://doi.org/10.1561/2500000010)\.
- Jha & Seshia \(2017\)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](https://doi.org/10.1007/s00236-017-0294-5)\.
- Jha et al\. \(2010\)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](https://doi.org/10.1145/1806799.1806833)\.
- Ji et al\. \(2020\)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](https://doi.org/10.1145/3385412.3386025)\.
- Kobalczyk et al\. \(2025\)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](https://openreview.net/forum?id=JAMxRSXLFz)\.
- Lake et al\. \(2015\)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](https://doi.org/10.1126/science.aab3050)\.
- Lee et al\. \(2025\)Kang\-il Lee, Jahyun Koo, Seunghyun Yoon, Minbeom Kim, Hyukhun Koh, Dongryeol 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](https://openreview.net/forum?id=YJx8AofTF5)\.
- Li & Ellis \(2024\)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](https://openreview.net/forum?id=xqc8yyhScL)\.
- Li et al\. \(2024\)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](https://doi.org/10.1007/978-3-031-65630-9_15)\.
- Li et al\. \(2022\)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](https://doi.org/10.1126/science.abq1158)\.
- Lieberman \(2001\)Henry Lieberman \(ed\.\)\.*Your Wish is My Command: Programming by Example*\.Morgan Kaufmann, 2001\.
- Lindley \(1956\)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](https://doi.org/10.1214/aoms/1177728069)\.
- Llama Team \(2024\)Llama Team\.The Llama 3 herd of models, 2024\.URL[https://arxiv\.org/abs/2407\.21783](https://arxiv.org/abs/2407.21783)\.
- MacKay \(1992\)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](https://doi.org/10.1162/neco.1992.4.4.590)\.
- Mayer et al\. \(2015\)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](https://doi.org/10.1145/2807442.2807459)\.
- Mistral AI team \(2024\)Mistral AI team\.Un Ministral, des Ministraux\.Mistral AI blog, October 2024\.URL[https://mistral\.ai/news/ministraux](https://mistral.ai/news/ministraux)\.
- Nowak \(2011\)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](https://doi.org/10.1109/TIT.2011.2169298)\.
- Owen \(2013\)Art B\. Owen\.*Monte Carlo Theory, Methods and Examples*\.[https://artowen\.su\.domains/mc/](https://artowen.su.domains/mc/), 2013\.
- Piriyakulkij et al\. \(2024\)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](https://openreview.net/forum?id=HXdAfK488A)\.
- Rice \(1953\)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](https://doi.org/10.1090/S0002-9947-1953-0053041-6)\.
- Saad et al\. \(2019\)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](https://doi.org/10.1145/3290350)\.
- Settles \(2012\)Burr Settles\.*Active Learning*\.Morgan & Claypool Publishers, 2012\.
- Shalev\-Shwartz & Ben\-David \(2014\)Shai Shalev\-Shwartz and Shai Ben\-David\.*Understanding Machine Learning: From Theory to Algorithms*\.Cambridge University Press, 2014\.
- Shannon \(1948\)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](https://doi.org/10.1002/j.1538-7305.1948.tb01338.x)\.
- Shapiro \(1983\)Ehud Y\. Shapiro\.*Algorithmic Program Debugging*\.MIT Press, 1983\.
- Shi et al\. \(2022\)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/](https://aclanthology.org/2022.emnlp-main.231/)\.
- Singhal et al\. \(2026\)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=pwSWrsBlsz](https://openreview.net/forum?id=pwSWrsBlsz)\.
- Solar\-Lezama \(2008\)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](https://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-177.html)\.
- Solomonoff \(1964\)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](https://doi.org/10.1016/S0019-9958(64)90223-2)\.
- Summers \(1977\)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](https://doi.org/10.1145/321992.322002)\.
- Team Olmo et al\. \(2025\)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 Hannaneh Hajishirzi\.Olmo 3, 2025\.URL[https://arxiv\.org/abs/2512\.13961](https://arxiv.org/abs/2512.13961)\.
- Tiwari et al\. \(2020\)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](https://arxiv.org/abs/2006.12638)\.
- Wei et al\. \(2025\)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=Q5pVZCrrKr](https://openreview.net/forum?id=Q5pVZCrrKr)\.
- Yang et al\. \(2025\)An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Haoran Wei, Huan Lin, Jian Yang, Jianhong 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](https://arxiv.org/abs/2412.15115)\.

## Appendix ARelated Work

#### Interactive and oracle\-guided program synthesis\.

Early works in oracle\-guided program synthesis include CEGIS\([Solar\-Lezama, 2008](https://arxiv.org/html/2611.18485#bib.bib45)\), and is formalized in works by[Jha et al\. \(2010\)](https://arxiv.org/html/2611.18485#bib.bib20)and[Jha & Seshia \(2017\)](https://arxiv.org/html/2611.18485#bib.bib19), where an automated verifier supplies counterexamples in place of a human\. Interactive disambiguation with human oracles was deployed in FlashFill by[Mayer et al\. \(2015\)](https://arxiv.org/html/2611.18485#bib.bib32)and studied theoretically by[Ji et al\. \(2020\)](https://arxiv.org/html/2611.18485#bib.bib21), who select questions by minimax over programs sampled from a PCFG posterior over a version space\.[Tiwari et al\. \(2020\)](https://arxiv.org/html/2611.18485#bib.bib49)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\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib3)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\([Lindley, 1956](https://arxiv.org/html/2611.18485#bib.bib29);[MacKay, 1992](https://arxiv.org/html/2611.18485#bib.bib31)\), applied sequentially as in active learning\([Settles, 2012](https://arxiv.org/html/2611.18485#bib.bib39)\)\.[Dasgupta \(2004\)](https://arxiv.org/html/2611.18485#bib.bib9)showed that greedy information\-gain maximization over a*finite*class uses at most4​ln⁡\(1/minh⁡p0​\(h\)\)4\\ln\(1/\\min\_\{h\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}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\. \(2010\)](https://arxiv.org/html/2611.18485#bib.bib14),[Golovin & Krause \(2011\)](https://arxiv.org/html/2611.18485#bib.bib13), and[Nowak \(2011\)](https://arxiv.org/html/2611.18485#bib.bib34)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\. \(2015\)](https://arxiv.org/html/2611.18485#bib.bib23)used hand\-designed generative models over strokes for few\-shot concept learning,[Ellis et al\. \(2021\)](https://arxiv.org/html/2611.18485#bib.bib10)bootstrapped reusable libraries via wake\-sleep inference,[Ellis et al\. \(2022\)](https://arxiv.org/html/2611.18485#bib.bib11)applied the same framework to linguistic theory synthesis, and[Saad et al\. \(2019\)](https://arxiv.org/html/2611.18485#bib.bib38)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\. \(2026\)](https://arxiv.org/html/2611.18485#bib.bib44)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\., 2024](https://arxiv.org/html/2611.18485#bib.bib36)\), task disambiguation including code generation\([Kobalczyk et al\., 2025](https://arxiv.org/html/2611.18485#bib.bib22)\), collaborative search games\([Grand et al\., 2026](https://arxiv.org/html/2611.18485#bib.bib15)\), and natural\-language database querying\([Chan et al\., 2026](https://arxiv.org/html/2611.18485#bib.bib6)\)\.[Lee et al\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib24)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\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib22)and[Lee et al\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib24)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\., 2021](https://arxiv.org/html/2611.18485#bib.bib8);[Austin et al\., 2021](https://arxiv.org/html/2611.18485#bib.bib1);[Li et al\., 2022](https://arxiv.org/html/2611.18485#bib.bib27)\)but struggle with programming by example without domain\-specific fine\-tuning\([Li & Ellis, 2024](https://arxiv.org/html/2611.18485#bib.bib25)\)\. HySynth\([Barke et al\., 2024](https://arxiv.org/html/2611.18485#bib.bib2)\)extracts a task\-specific PCFG from LLM samples to guide bottom\-up enumerative search, and[Li et al\. \(2024\)](https://arxiv.org/html/2611.18485#bib.bib26)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\., 2022](https://arxiv.org/html/2611.18485#bib.bib27)\), CodeT\([Chen et al\., 2023](https://arxiv.org/html/2611.18485#bib.bib7)\), and MBR\-exec\([Shi et al\., 2022](https://arxiv.org/html/2611.18485#bib.bib43)\), and our equivalence relation∼S\\sim\_\{\\color\[rgb\]\{0,0,0\}S\}is the same construction\.[Wei et al\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib50)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\.

## Appendix BLimitations

#### Computational cost\.

Each round of the algorithm requires potentially drawingM\{\\color\[rgb\]\{0,0,0\}M\}program samples from the LM proposalqt\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}, evaluating each on the inputs inS\{\\color\[rgb\]\{0,0,0\}S\}, 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\.[Tab\.2](https://arxiv.org/html/2611.18485#A2.T2)reports the cost per problem\.[Alg\.1](https://arxiv.org/html/2611.18485#alg1)makes3232to7878LM calls and samples about110110candidate programs, each of which it executes onS\{\\color\[rgb\]\{0,0,0\}S\}and on every query, against55to1010calls 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\.

Table 2:Computational cost per problem with11seed 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](https://arxiv.org/html/2611.18485#alg1)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\.

[Proposition2\.1](https://arxiv.org/html/2611.18485#S2.Thmproposition1)bounds the error under the input distributionμ\{\\color\[rgb\]\{0,0,0\}\\mu\}, which we instantiate by prompting an LM with the seed examples\. A single seed invocation suffices for the gains of[Tab\.1](https://arxiv.org/html/2611.18485#S4.T1), and rebuilding the evaluation set from the single visible seed example changes accuracy by at most\.02\.02on five of six models \([App\.D](https://arxiv.org/html/2611.18485#A4)\)\. The bound does not guarantee generalization beyondμ\{\\color\[rgb\]\{0,0,0\}\\mu\}\. A differential tester searches for a counterexample and may find one on an input thatμ\{\\color\[rgb\]\{0,0,0\}\\mu\}rarely produces, so the accuracies we report also measure how well agreement underμ\{\\color\[rgb\]\{0,0,0\}\\mu\}generalizes\. A prompt that describes the intended inputs more closely improves this generalization\.

#### Gap between theoretical and empirical correctness\.

[Theorems3\.1](https://arxiv.org/html/2611.18485#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2611.18485#S3.Thmtheorem2)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\.34to\.63\.63of runs in[Tab\.4](https://arxiv.org/html/2611.18485#A5.T4)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[Fig\.3](https://arxiv.org/html/2611.18485#S5.F3)often does\. The remaining errors are due to the models’ capability\. In\.13\.13to\.49\.49of the runs no sampled program is consistent with the observed examples, and the CodeARC agent built on the same models reaches\.06\.06to\.30\.30\([Tab\.1](https://arxiv.org/html/2611.18485#S4.T1)\)\. Stronger models narrow this gap, with Qwen2\.5\-32B reaching the highest accuracy in every setting\.

## Appendix CDeferred Proofs

### C\.1PAC Bound

See[2\.1](https://arxiv.org/html/2611.18485#S2.Thmproposition1)

###### Proof\.

Fixf\{\\color\[rgb\]\{0,0,0\}f\}withp0​\(f\)\>0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\>0\. SinceS\{\\color\[rgb\]\{0,0,0\}S\}consists ofN\{\\color\[rgb\]\{0,0,0\}N\}i\.i\.d\. draws fromμ\{\\color\[rgb\]\{0,0,0\}\\mu\}, the probability thatf\{\\color\[rgb\]\{0,0,0\}f\}agrees withf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}on all ofS\{\\color\[rgb\]\{0,0,0\}S\}is

PrS∼μN\[f∈\[f⋆\]∼\]=\(1−errμ\(f\)\)N≤exp\(−N⋅errμ\(f\)\),\\displaystyle\\Pr\_\{\{\\color\[rgb\]\{0,0,0\}S\}\\sim\{\\color\[rgb\]\{0,0,0\}\\mu\}^\{\\color\[rgb\]\{0,0,0\}N\}\}\\big\[\{\\color\[rgb\]\{0,0,0\}f\}\\in\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\big\]=\(1\-\{\\color\[rgb\]\{0,0,0\}\\mathrm\{err\}\_\{\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\)^\{\\color\[rgb\]\{0,0,0\}N\}\\leq\\exp\(\-\{\\color\[rgb\]\{0,0,0\}N\}\\cdot\{\\color\[rgb\]\{0,0,0\}\\mathrm\{err\}\_\{\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\),\(16\)where we used1−u≤e−u1\-u\\leq e^\{\-u\}\. Letτ⁡\(f\)=def\(ln⁡\(1/p0​\(f\)\)\+ln⁡\(1/δ\)\)/N\{\\color\[rgb\]\{0,0,0\}\\tau\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\\mathrel\{\\stackrel\{\{\\scriptstyle\\textnormal\{def\}\}\}\{\{=\}\}\}\(\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\)\+\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\\delta\}\)\)/\{\\color\[rgb\]\{0,0,0\}N\}be the right\-hand side of[Eq\.3](https://arxiv.org/html/2611.18485#S2.E3), and letBf\{\\color\[rgb\]\{0,0,0\}B\}\_\{\\color\[rgb\]\{0,0,0\}f\}be the event thatf∈\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}f\}\\in\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}anderrμ​\(f\)\>τ​\(f\)\{\\color\[rgb\]\{0,0,0\}\\mathrm\{err\}\_\{\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\>\{\\color\[rgb\]\{0,0,0\}\\tau\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\. The eventBf\{\\color\[rgb\]\{0,0,0\}B\}\_\{\\color\[rgb\]\{0,0,0\}f\}is empty iferrμ​\(f\)≤τ⁡\(f\)\{\\color\[rgb\]\{0,0,0\}\\mathrm\{err\}\_\{\{\\color\[rgb\]\{0,0,0\}\\mu\}\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\\leq\{\\color\[rgb\]\{0,0,0\}\\tau\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\. Otherwise[Eq\.16](https://arxiv.org/html/2611.18485#A3.E16)givesPrS∼μN\[Bf\]≤exp\(−N⋅τ\(f\)\)=δ⋅p0\(f\)\\Pr\_\{\{\\color\[rgb\]\{0,0,0\}S\}\\sim\{\\color\[rgb\]\{0,0,0\}\\mu\}^\{\\color\[rgb\]\{0,0,0\}N\}\}\[\{\\color\[rgb\]\{0,0,0\}B\}\_\{\\color\[rgb\]\{0,0,0\}f\}\]\\leq\\exp\(\-\{\\color\[rgb\]\{0,0,0\}N\}\\cdot\{\\color\[rgb\]\{0,0,0\}\\tau\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\)=\{\\color\[rgb\]\{0,0,0\}\\delta\}\\cdot\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\. The probability that any of these events occurs is at most the sum of their probabilities, so

PrS∼μN\[⋃f:p0​\(f\)\>0Bf\]≤∑f:p0​\(f\)\>0δ⋅p0\(f\)≤δ\.\\displaystyle\\Pr\_\{\{\\color\[rgb\]\{0,0,0\}S\}\\sim\{\\color\[rgb\]\{0,0,0\}\\mu\}^\{\\color\[rgb\]\{0,0,0\}N\}\}\\Big\[\\bigcup\_\{\{\\color\[rgb\]\{0,0,0\}f\}\\colon\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\>0\}\{\\color\[rgb\]\{0,0,0\}B\}\_\{\\color\[rgb\]\{0,0,0\}f\}\\Big\]\\leq\\sum\_\{\{\\color\[rgb\]\{0,0,0\}f\}\\colon\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\>0\}\{\\color\[rgb\]\{0,0,0\}\\delta\}\\cdot\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\\leq\{\\color\[rgb\]\{0,0,0\}\\delta\}\.\(17\)Assigning each program the failure probabilityδ⋅p0​\(f\)\{\\color\[rgb\]\{0,0,0\}\\delta\}\\cdot\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)instead ofδ/\|YX\|\{\\color\[rgb\]\{0,0,0\}\\delta\}/\|\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}\|replacesln⁡\|YX\|\\ln\|\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}Y\}^\{\{\\color\[rgb\]\{0,0,0\}X\}\}\}\|byln⁡\(1/p0​\(f\)\)\\ln\(1/\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\)and extends the bound to countably infinite program spaces\. On the complement of this event, everyf∈\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}f\}\\in\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}withp0​\(f\)\>0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f\}\)\>0satisfies[Eq\.3](https://arxiv.org/html/2611.18485#S2.E3)\. ∎

### C\.2Expected Query Complexity and Correctness

Throughout,S\{\\color\[rgb\]\{0,0,0\}S\}is fixed, and for a classc\{\\color\[rgb\]\{0,0,0\}c\}andx∈S\{\\color\[rgb\]\{0,0,0\}x\}\\in\{\\color\[rgb\]\{0,0,0\}S\}we writec⁡\(x\)\{\\color\[rgb\]\{0,0,0\}c\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)for the common output of the programs inc\{\\color\[rgb\]\{0,0,0\}c\}\. A class is*consistent*with𝒟t\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}ifc⁡\(x\(s\)\)=y\(s\)\{\\color\[rgb\]\{0,0,0\}c\}\(\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}s\}\)\}\)=\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}s\}\)\}for alls≤t\{\\color\[rgb\]\{0,0,0\}s\}\\leq\{\\color\[rgb\]\{0,0,0\}t\}, and\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}is consistent with every𝒟t\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\. Ties in[Eq\.7](https://arxiv.org/html/2611.18485#S2.E7)are broken by a fixed rule\.

###### Lemma C\.1\(Mass recursion\)\.

For every classc\{\\color\[rgb\]\{0,0,0\}c\}and1≤t≤T1\\leq\{\\color\[rgb\]\{0,0,0\}t\}\\leq\{\\color\[rgb\]\{0,0,0\}T\},

p∼​\(c∣𝒟t\)\\displaystyle\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)=p∼\(c∣𝒟t−1\)⋅𝟙\{c\(x\(t\)\)=y\(t\)\}p⁡\(y\(t\)∣x\(t\),𝒟t−1\),\\displaystyle=\\frac\{\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\\cdot\\mathbbm\{1\}\\\{\{\\color\[rgb\]\{0,0,0\}c\}\(\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\)=\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\\}\}\{\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\},\(18\)log2⁡1p∼​\(\[f⋆\]∼∣𝒟0\)\\displaystyle\\log\_\{2\}\\frac\{1\}\{\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\}=∑s=1tlog2⁡1p⁡\(y\(s\)∣x\(s\),𝒟s−1\)\+log2⁡1p∼​\(\[f⋆\]∼∣𝒟t\)\.\\displaystyle=\\sum\_\{\{\\color\[rgb\]\{0,0,0\}s\}=1\}^\{\{\\color\[rgb\]\{0,0,0\}t\}\}\\log\_\{2\}\\frac\{1\}\{\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}s\}\)\}\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}s\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}s\}\-1\}\)\}\+\\log\_\{2\}\\frac\{1\}\{\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\}\.\(19\)

###### Proof\.

All programs in a class agree onx\(t\)∈S\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\in\{\\color\[rgb\]\{0,0,0\}S\}, so summing[Eq\.5a](https://arxiv.org/html/2611.18485#S2.E5.1)overg∈c\{\\color\[rgb\]\{0,0,0\}g\}\\in\{\\color\[rgb\]\{0,0,0\}c\}gives[Eq\.18](https://arxiv.org/html/2611.18485#A3.E18)\. Forc=\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}c\}=\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}the indicator equals one, and unrolling overs≤t\{\\color\[rgb\]\{0,0,0\}s\}\\leq\{\\color\[rgb\]\{0,0,0\}t\}and taking logarithms gives[Eq\.19](https://arxiv.org/html/2611.18485#A3.E19)\. ∎

###### Lemma C\.2\(Greedy selection\)\.

LetH\[p∼\(⋅∣𝒟0\)\]<∞\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\]<\\infty\. For everyt≤T\{\\color\[rgb\]\{0,0,0\}t\}\\leq\{\\color\[rgb\]\{0,0,0\}T\}andx∈S\{\\color\[rgb\]\{0,0,0\}x\}\\in\{\\color\[rgb\]\{0,0,0\}S\}, the objective in[Eq\.7](https://arxiv.org/html/2611.18485#S2.E7)equalsH\[p\(⋅∣x,𝒟t−1\)\]\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\]\. Moreover,γt\>0\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}t\}\>0for allt≤T\{\\color\[rgb\]\{0,0,0\}t\}\\leq\{\\color\[rgb\]\{0,0,0\}T\}, no input is queried twice, andT≤N\{\\color\[rgb\]\{0,0,0\}T\}\\leq\{\\color\[rgb\]\{0,0,0\}N\}\.

###### Proof\.

Letc∼p∼\(⋅∣𝒟t−1\)\{\\color\[rgb\]\{0,0,0\}c\}\\sim\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\), whose entropy is at mostH\[p∼\(⋅∣𝒟0\)\]/p∼\(\[f⋆\]∼∣𝒟0\)<∞\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\]/\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)<\\infty\. The answery=c⁡\(x\)\{\\color\[rgb\]\{0,0,0\}y\}=\{\\color\[rgb\]\{0,0,0\}c\}\(\{\\color\[rgb\]\{0,0,0\}x\}\)is a function ofc\{\\color\[rgb\]\{0,0,0\}c\}with distributionp\(⋅∣x,𝒟t−1\)\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\), and by[Lem\.C\.1](https://arxiv.org/html/2611.18485#A3.Thmlemma1)the distribution ofc\{\\color\[rgb\]\{0,0,0\}c\}giveny\{\\color\[rgb\]\{0,0,0\}y\}isp∼\(⋅∣𝒟t−1∪\{\(x,y\)\}\)\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\\cup\\\{\(\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}y\}\)\\\}\)\. The chain rule for entropy gives

H\[p∼\(⋅∣𝒟t−1\)\]=H\[p\(⋅∣x,𝒟t−1\)\]\+∑y∈Yp\(y∣x,𝒟t−1\)H\[p∼\(⋅∣𝒟t−1∪\{\(x,y\)\}\)\],\\displaystyle\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\]=\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\]\+\\sum\_\{\{\\color\[rgb\]\{0,0,0\}y\}\\in\{\\color\[rgb\]\{0,0,0\}Y\}\}\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\\,\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\\cup\\\{\(\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}y\}\)\\\}\)\],\(20\)which is the first claim\. Fort≤T\{\\color\[rgb\]\{0,0,0\}t\}\\leq\{\\color\[rgb\]\{0,0,0\}T\}, no class has mass above12\\tfrac\{1\}\{2\}under𝒟t−1\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}, so two classes have positive mass and differ on somex′∈S\{\\color\[rgb\]\{0,0,0\}x\}^\{\\prime\}\\in\{\\color\[rgb\]\{0,0,0\}S\}\. ThenH\[p\(⋅∣x\(t\),𝒟t−1\)\]≥H\[p\(⋅∣x′,𝒟t−1\)\]\>0\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\]\\geq\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\\prime\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\]\>0, the predictive atx\(t\)\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}is not a point mass, andγt\>0\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}t\}\>0\. The predictive at a previously queried input is a point mass, so no input is queried twice\. Once all ofS\{\\color\[rgb\]\{0,0,0\}S\}is queried,\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}is the only consistent class, and thusT≤N\{\\color\[rgb\]\{0,0,0\}T\}\\leq\{\\color\[rgb\]\{0,0,0\}N\}\. ∎

###### Lemma C\.3\(Posterior as conditional law\)\.

Letf⋆∼p0\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\\sim\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}, conditional on the seed examples𝒟0\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\. For every classc\{\\color\[rgb\]\{0,0,0\}c\}and everyt≤T\{\\color\[rgb\]\{0,0,0\}t\}\\leq\{\\color\[rgb\]\{0,0,0\}T\}, we havePr⁡\[\[f⋆\]∼=c∣𝒟t\]=p∼​\(c∣𝒟t\)\\Pr\[\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}=\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\]=\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\.

###### Proof\.

The queries are a deterministic function of the answers received so far\. A target in classc\{\\color\[rgb\]\{0,0,0\}c\}therefore generates𝒟t\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}if and only ifc\{\\color\[rgb\]\{0,0,0\}c\}is consistent with it, that is,Pr⁡\[𝒟t∣\[f⋆\]∼=c\]=𝟙​\{c​consistent with​𝒟t\}\\Pr\[\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\\mid\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}=\{\\color\[rgb\]\{0,0,0\}c\}\]=\\mathbbm\{1\}\\\{\{\\color\[rgb\]\{0,0,0\}c\}\\text\{ consistent with \}\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\\\}\. Bayes’ rule withPr\[\[f⋆\]∼=c\]=p∼\(c∣𝒟0\)\\Pr\[\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}=\{\\color\[rgb\]\{0,0,0\}c\}\]=\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)gives the claim\. ∎

See[3\.1](https://arxiv.org/html/2611.18485#S3.Thmtheorem1)

###### Proof\.

Claim \(ii\) follows from[Lem\.C\.2](https://arxiv.org/html/2611.18485#A3.Thmlemma2)\. For \(i\), dropping the last term of[Eq\.19](https://arxiv.org/html/2611.18485#A3.E19)att=T\{\\color\[rgb\]\{0,0,0\}t\}=\{\\color\[rgb\]\{0,0,0\}T\}, which is non\-negative, gives∑t=1T−log2p\(y\(t\)∣x\(t\),𝒟t−1\)≤−log2p∼\(\[f⋆\]∼∣𝒟0\)\\sum\_\{\{\\color\[rgb\]\{0,0,0\}t\}=1\}^\{\{\\color\[rgb\]\{0,0,0\}T\}\}\-\\log\_\{2\}\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\\leq\-\\log\_\{2\}\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\. We take expectations overf⋆∼p0\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\\sim\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\. The right\-hand side becomesH\[p∼\(⋅∣𝒟0\)\]\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\]sincePr\[\[f⋆\]∼=c\]=p∼\(c∣𝒟0\)\\Pr\[\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}=\{\\color\[rgb\]\{0,0,0\}c\}\]=\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\. On the left\-hand side, the event\{T≥t\}\\\{\{\\color\[rgb\]\{0,0,0\}T\}\\geq\{\\color\[rgb\]\{0,0,0\}t\}\\\}is determined by𝒟t−1\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}, and by[Lem\.C\.3](https://arxiv.org/html/2611.18485#A3.Thmlemma3)the answery\(t\)\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\}given𝒟t−1\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}is distributed asp\(⋅∣x\(t\),𝒟t−1\)\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\), so that the conditional expectation of thet\{\\color\[rgb\]\{0,0,0\}t\}\-th term given𝒟t−1\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}isH\[p\(⋅∣x\(t\),𝒟t−1\)\]\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\]\. Summing overt≤N\{\\color\[rgb\]\{0,0,0\}t\}\\leq\{\\color\[rgb\]\{0,0,0\}N\}yields

𝔼f⋆∼p0\[∑t=1TH\[p\(⋅∣x\(t\),𝒟t−1\)\]\]≤H\[p∼\(⋅∣𝒟0\)\]\.\\displaystyle\\mathop\{\\mathbb\{E\}\}\_\{\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\\sim\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\}\\Big\[\\sum\_\{\{\\color\[rgb\]\{0,0,0\}t\}=1\}^\{\{\\color\[rgb\]\{0,0,0\}T\}\}\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\]\\Big\]\\leq\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\]\.\(21\)By[Lem\.C\.2](https://arxiv.org/html/2611.18485#A3.Thmlemma2)and because the Shannon entropy of a distribution is at least the negative logarithm of its largest probability,H\[p\(⋅∣x\(t\),𝒟t−1\)\]=maxx∈SH\[p\(⋅∣x,𝒟t−1\)\]≥γ¯t\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}t\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\]=\\max\_\{\{\\color\[rgb\]\{0,0,0\}x\}\\in\{\\color\[rgb\]\{0,0,0\}S\}\}\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}x\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}t\}\-1\}\)\]\\geq\{\\color\[rgb\]\{0,0,0\}\\bar\{\\gamma\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}, which proves \(i\)\. Keeping the last term of[Eq\.19](https://arxiv.org/html/2611.18485#A3.E19)and applying[Lem\.C\.3](https://arxiv.org/html/2611.18485#A3.Thmlemma3)once more shows that the left\-hand side equalsH\[p∼\(⋅∣𝒟0\)\]−𝔼\[H\[p∼\(⋅∣𝒟T\)\]\]\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\]\-\\mathop\{\\mathbb\{E\}\}\[\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\)\]\], so the only inequalities behind \(i\) areH\[p∼\(⋅∣𝒟T\)\]≥0\{\\color\[rgb\]\{0,0,0\}\\mathrm\{H\}\}\[\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\cdot\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\)\]\\geq 0and this lower bound on the Shannon entropy\. For \(iii\), the hypothesis givesγ​T≤∑t=1Tγ¯t\{\\color\[rgb\]\{0,0,0\}\\gamma\}\{\\color\[rgb\]\{0,0,0\}T\}\\leq\\sum\_\{\{\\color\[rgb\]\{0,0,0\}t\}=1\}^\{\{\\color\[rgb\]\{0,0,0\}T\}\}\{\\color\[rgb\]\{0,0,0\}\\bar\{\\gamma\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}for everyf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}withp0​\(f⋆\)\>0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\)\>0, and taking expectations and applying \(i\) gives the bound\. Finally, the returned classc^\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}is determined by𝒟T\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}, so[Lem\.C\.3](https://arxiv.org/html/2611.18485#A3.Thmlemma3)givesPr⁡\[c^=\[f⋆\]∼∣𝒟T\]=p∼​\(c^∣𝒟T\)\\Pr\[\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}=\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\]=\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\), which exceeds12\\tfrac\{1\}\{2\}by the stopping rule\. ∎

### C\.3Per\-Instance Query Complexity and Correctness

###### Lemma C\.4\(Mass growth\)\.

Fixf⋆\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}withp0​\(f⋆\)\>0\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}\{\\color\[rgb\]\{0,0,0\}p\}\}^\{0\}\}\(\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\)\>0\. Under any rule that selects queries fromS\{\\color\[rgb\]\{0,0,0\}S\}, for everyt≤T\{\\color\[rgb\]\{0,0,0\}t\}\\leq\{\\color\[rgb\]\{0,0,0\}T\},

p∼​\(\[f⋆\]∼∣𝒟t\)≥p∼​\(\[f⋆\]∼∣𝒟0\)⋅2∑s=1tγs,\\displaystyle\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\\big\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\\big\)\\geq\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\\cdot 2^\{\\sum\_\{\{\\color\[rgb\]\{0,0,0\}s\}=1\}^\{\{\\color\[rgb\]\{0,0,0\}t\}\}\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}s\}\},\(22\)and under the greedy ruleγs\>0\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}s\}\>0for everys\{\\color\[rgb\]\{0,0,0\}s\}\.

###### Proof\.

By definition ofγs\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}s\}, we havep⁡\(y\(s\)∣x\(s\),𝒟s−1\)≤2−γs\{\\color\[rgb\]\{0,0,0\}p\}\(\{\\color\[rgb\]\{0,0,0\}y\}^\{\(\{\\color\[rgb\]\{0,0,0\}s\}\)\}\\mid\{\\color\[rgb\]\{0,0,0\}x\}^\{\(\{\\color\[rgb\]\{0,0,0\}s\}\)\},\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\{\\color\[rgb\]\{0,0,0\}s\}\-1\}\)\\leq 2^\{\-\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}s\}\}, so[Eq\.19](https://arxiv.org/html/2611.18485#A3.E19)gives−log2⁡p∼​\(\[f⋆\]∼∣𝒟0\)≥∑s=1tγs−log2⁡p∼​\(\[f⋆\]∼∣𝒟t\)\-\\log\_\{2\}\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\\geq\\sum\_\{\{\\color\[rgb\]\{0,0,0\}s\}=1\}^\{\{\\color\[rgb\]\{0,0,0\}t\}\}\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}s\}\-\\log\_\{2\}\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\), which rearranges to[Eq\.22](https://arxiv.org/html/2611.18485#A3.E22)\. The greedy rule givesγs\>0\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}s\}\>0by[Lem\.C\.2](https://arxiv.org/html/2611.18485#A3.Thmlemma2)\. ∎

See[3\.2](https://arxiv.org/html/2611.18485#S3.Thmtheorem2)

###### Proof\.

If∑s≤tγs\>log2⁡12​p∼​\(\[f⋆\]∼∣𝒟0\)\\sum\_\{\{\\color\[rgb\]\{0,0,0\}s\}\\leq\{\\color\[rgb\]\{0,0,0\}t\}\}\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}s\}\>\\log\_\{2\}\\frac\{1\}\{2\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\}, then[Lem\.C\.4](https://arxiv.org/html/2611.18485#A3.Thmlemma4)givesp∼​\(\[f⋆\]∼∣𝒟t\)\>12\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}t\}\)\>\\tfrac\{1\}\{2\}and the algorithm has terminated by roundt\{\\color\[rgb\]\{0,0,0\}t\}\. Now lett\{\\color\[rgb\]\{0,0,0\}t\}be the right\-hand side of[Eq\.8](https://arxiv.org/html/2611.18485#S3.E8), which is the smallest integer witht​γ\>log2⁡12​p∼​\(\[f⋆\]∼∣𝒟0\)\{\\color\[rgb\]\{0,0,0\}t\}\{\\color\[rgb\]\{0,0,0\}\\gamma\}\>\\log\_\{2\}\\frac\{1\}\{2\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\}\. IfT\>t\{\\color\[rgb\]\{0,0,0\}T\}\>\{\\color\[rgb\]\{0,0,0\}t\}, then∑s≤tγs≥t​γ\\sum\_\{\{\\color\[rgb\]\{0,0,0\}s\}\\leq\{\\color\[rgb\]\{0,0,0\}t\}\}\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}s\}\\geq\{\\color\[rgb\]\{0,0,0\}t\}\{\\color\[rgb\]\{0,0,0\}\\gamma\}and the algorithm would have terminated by roundt\{\\color\[rgb\]\{0,0,0\}t\}, a contradiction\. For correctness, by[Eq\.4](https://arxiv.org/html/2611.18485#S2.E4)the posterior mass of every class consistent with𝒟T\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}is its prior mass divided by the same normalizer, so consistent classes are ordered under the posterior as under the prior\. Ifc^≠\[f⋆\]∼\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}\\neq\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}, thenp∼​\(c^∣𝒟T\)\>12\>p∼​\(\[f⋆\]∼∣𝒟T\)\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\)\>\\tfrac\{1\}\{2\}\>\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\)with both classes consistent, soc^\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}has strictly larger prior mass\. Conversely, if a consistent classc′\{\\color\[rgb\]\{0,0,0\}c\}^\{\\prime\}has larger prior mass than\[f⋆\]∼\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}, thenp∼​\(c′∣𝒟T\)\>p∼​\(\[f⋆\]∼∣𝒟T\)\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}c\}^\{\\prime\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\)\>\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{\\color\[rgb\]\{0,0,0\}T\}\), andc^=\[f⋆\]∼\\widehat\{\{\\color\[rgb\]\{0,0,0\}c\}\}=\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}would give a total mass above one\. ∎

## Appendix DExperimental Details

#### Infrastructure\.

All models are served using vLLM333https://docs\.vllm\.ai/en/, 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 useM=64\{\\color\[rgb\]\{0,0,0\}M\}=64particles, an evaluation set of sizeN=64\{\\color\[rgb\]\{0,0,0\}N\}=64, resample when the effective sample size falls belowτESS=4\{\\color\[rgb\]\{0,0,0\}\\tau\_\{\\mathrm\{ESS\}\}\}=4, and terminate once a class holds more than half of the posterior mass\. Runs that return a program observe2\.32\.3to2\.72\.7input–output examples on average, depending on the model\. The query budget we use and report is3030input–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μ\{\\color\[rgb\]\{0,0,0\}\\mu\}, instantiated with Llama3\.1\-8B at temperature1\.11\.1, conditioned on all1010seed invocations of the benchmark\. The evaluation set therefore draws on seed examples that the algorithm does not see at11seed invocation\. Its inputs coincide with a seed input in0\.3%0\.3\\%of the entries, and rebuilding it from the55visible seed examples changed the accuracy of Llama3\.2\-3B, Llama3\.1\-8B, and Qwen2\.5\-32B by at most\.02\.02on100100problems\. Rebuilding it from the single visible seed example on the full split changes accuracy by at most\.02\.02on five of six models and lowers that of Qwen2\.5\-32B from\.342\.342to\.280\.280\([Tab\.3](https://arxiv.org/html/2611.18485#A4.T3)\)\. 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](https://arxiv.org/html/2611.18485#S2.Thmproposition1)is with respect to this input distribution\. The proposal prompt and sampling temperature are selected per model on a screening set \([§E\.6](https://arxiv.org/html/2611.18485#A5.SS6),[Fig\.5](https://arxiv.org/html/2611.18485#A5.F5)\), and the prompts are given in[App\.F](https://arxiv.org/html/2611.18485#A6)\. The maximum context length is capped at 12288 tokens across all models\.

Table 3:Avg I/O and accuracy at11seed invocation with the evaluation set built from all1010seed invocations \(shared, as in[Tab\.1](https://arxiv.org/html/2611.18485#S4.T1)\) and from the single visible one, on the full anonymized split, means over33seeds\. Stars test against the shared evaluation set \(paired sign test,p∗⁣∗<\.01\{\}^\{\*\*\}p<\.01,∗∗∗p<\.001\{\}^\{\*\*\*\}p<\.001\)\.
#### Licensing\.

The CodeARC benchmark\([Wei et al\., 2025](https://arxiv.org/html/2611.18485#bib.bib50)\)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\.

## Appendix EAdditional Results

### E\.1Failure Modes

Table 4:Terminal state of the runs behind[Tab\.1](https://arxiv.org/html/2611.18485#S4.T1)at11seed invocation \(N=64\{\\color\[rgb\]\{0,0,0\}N\}=64, five seeds\), as a share of all runs, averaged over seeds as in[Tab\.1](https://arxiv.org/html/2611.18485#S4.T1)\. 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[Tab\.1](https://arxiv.org/html/2611.18485#S4.T1)\.[Table4](https://arxiv.org/html/2611.18485#A5.T4)decomposes the runs of[Tab\.1](https://arxiv.org/html/2611.18485#S4.T1)by their terminal state to explain the gap between the correctness guarantee of[Thm\.3\.1](https://arxiv.org/html/2611.18485#S3.Thmtheorem1)and the accuracies of[Tab\.1](https://arxiv.org/html/2611.18485#S4.T1)\. Most runs fail before the stopping rule applies\. In a large share of them, between\.13\.13and\.49\.49depending 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[Fig\.3](https://arxiv.org/html/2611.18485#S5.F3)\. 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](https://arxiv.org/html/2611.18485#A5.SS5)\) and the prompt \([§E\.6](https://arxiv.org/html/2611.18485#A5.SS6)\) affect accuracy more than the query selection strategy \([Tab\.6](https://arxiv.org/html/2611.18485#A5.T6)\)\.

### E\.2Per\-Instance Bound Analysis

Table 5:Termination roundT\{\\color\[rgb\]\{0,0,0\}T\}of EIG against its per\-instance bound derived in[Thm\.3\.2](https://arxiv.org/html/2611.18485#S3.Thmtheorem2),⌊1γ​log2​12​p∼​\(\[f⋆\]∼∣𝒟0\)⌋\+1\\lfloor\\tfrac\{1\}\{\{\\color\[rgb\]\{0,0,0\}\\gamma\}\}\\log\_\{2\}\\tfrac\{1\}\{2\{\\color\[rgb\]\{0,0,0\}p\_\{\\sim\}\}\(\{\\color\[rgb\]\{0,0,0\}\[\{\\color\[rgb\]\{0,0,0\}f^\{\\star\}\}\]\_\{\\sim\}\}\\mid\{\\color\[rgb\]\{0,0,0\}\\mathcal\{D\}\}\_\{0\}\)\}\\rfloor\+1\. Runs on the diagonal,\.37\.37of all runs, attain the bound\.[Table5](https://arxiv.org/html/2611.18485#A5.T5)compares, run by run, the termination round of EIG with the bound of[Thm\.3\.2](https://arxiv.org/html/2611.18485#S3.Thmtheorem2)evaluated on that run\. The bound is attained in\.37\.37of the runs, and is loose when the guaranteed information is not uniform over the queries of a run, sinceγ\{\\color\[rgb\]\{0,0,0\}\\gamma\}is the minimum over the run’s queries and a single uninformative query loosens the bound\.

### E\.3Query Selection Strategies

[Tab\.6](https://arxiv.org/html/2611.18485#A5.T6)reports, per model, the quantities of[Fig\.1](https://arxiv.org/html/2611.18485#S5.F1)at the end of the run for every query selection strategy of[Alg\.1](https://arxiv.org/html/2611.18485#alg1)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\.7](https://arxiv.org/html/2611.18485#S2.E7)\. 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\.06for every model\. The accuracy of a run is decided by whether the proposal contains a correct program \([§E\.1](https://arxiv.org/html/2611.18485#A5.SS1)\), 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\.

Table 6:Query selection strategies of[Alg\.1](https://arxiv.org/html/2611.18485#alg1)and the CodeARC agent with11seed 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 over55independent seeds \(33for 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 of3030\. Avgγt\{\\color\[rgb\]\{0,0,0\}\\gamma\}\_\{\\color\[rgb\]\{0,0,0\}t\}is the information the selected query is guaranteed to yield, averaged over all queries of the strategy\.
### E\.4Controls and Literature Baselines

[Tables7](https://arxiv.org/html/2611.18485#A5.T7),[8](https://arxiv.org/html/2611.18485#A5.T8)and[9](https://arxiv.org/html/2611.18485#A5.T9)separate the contributions of the importance weights, the selection rule, and the sampling budget\. All runs use11seed invocation and33seeds, and stars mark a paired sign test over problems and seeds \(p∗⁣∗<\.01\{\}^\{\*\*\}p<\.01,∗∗∗p<\.001\{\}^\{\*\*\*\}p<\.001\)\.[Table7](https://arxiv.org/html/2611.18485#A5.T7)replaces the importance weights by uniform weights over consistent programs, as in[Kobalczyk et al\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib22), and by the exact weights of the sampled completions\. The latter requires sampling at temperature11, so all three arms use it here\. The approximate weights of[§4\.2](https://arxiv.org/html/2611.18485#S4.SS2)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\.[Table8](https://arxiv.org/html/2611.18485#A5.T8)ports the selection rules of[Ji et al\. \(2020\)](https://arxiv.org/html/2611.18485#bib.bib21)and[Lee et al\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib24)\(minimax with uniform weights\) and of[Kobalczyk et al\. \(2025\)](https://arxiv.org/html/2611.18485#bib.bib22)\(EIG with uniform weights\) into[Alg\.1](https://arxiv.org/html/2611.18485#alg1), 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\.[Table9](https://arxiv.org/html/2611.18485#A5.T9)matches the sampling budget\. A propose\-and\-verify baseline draws112112programs, 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, on100100problems at sampling temperature11\. Stars test against uniform weights\.Table 8:Selection rules from the literature ported into[Alg\.1](https://arxiv.org/html/2611.18485#alg1), on100100problems at the sampling temperatures of the main experiments\. Stars test against our method\.Table 9:Accuracy of a compute\-matched propose\-and\-verify baseline \(112112sampled programs, no oracle queries\) and of our method on the full anonymized split\. Stars test against propose\-and\-verify\.
### E\.5Particle Budget

[Fig\.4](https://arxiv.org/html/2611.18485#A5.F4)varies the number of particlesM\{\\color\[rgb\]\{0,0,0\}M\}from22to256256for three models on100100problems with11seed invocation\. More particles produce more behavioral classes at round11, so the first query is more informative, and the algorithm ends with fewer input–output examples and higher accuracy\. Accuracy keeps rising past theM=64\{\\color\[rgb\]\{0,0,0\}M\}=64of the main experiments and does not saturate at256256, which agrees with the failure modes of[§E\.1](https://arxiv.org/html/2611.18485#A5.SS1), 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 use6464to limit the per\-round cost, which grows with the number of programs that have to be executed onS\{\\color\[rgb\]\{0,0,0\}S\}\([Tab\.2](https://arxiv.org/html/2611.18485#A2.T2)\)\.

Figure 4:Particle\-budget ablation with11seed invocation on100100problems\. We show the input–output examples observed, the accuracy, and the number of behavioral classes at round11against the number of particlesM\{\\color\[rgb\]\{0,0,0\}M\}, with 95% confidence intervals over33seeds\.
### E\.6Proposal Prompt and Sampling Temperature

The proposalqt\{\\color\[rgb\]\{0,0,0\}q\}\_\{\\color\[rgb\]\{0,0,0\}t\}depends on the prompt shown to the LM and on its sampling temperature\. We consider four prompts \(Prompts A–D,[App\.F](https://arxiv.org/html/2611.18485#A6)\), which differ in how strongly they ask for hypotheses that disagree on unseen inputs, and six temperatures between0\.70\.7and1\.31\.3\. We choose the prompt and temperature for each model in a preliminary screen over prompts and temperatures in this range\. The100100screening problems are part of the evaluation split\. Recomputing[Tab\.1](https://arxiv.org/html/2611.18485#S4.T1)on the remaining985985problems changes every entry by at most\.007\.007\.[Figure5](https://arxiv.org/html/2611.18485#A5.F5)reports the accuracy of the full algorithm over the grid of prompts and temperatures\. No prompt is best for every model\. With about100100problems per configuration, differences of a few hundredths are within sampling noise\. Ministral\-8B degrades at temperatures above1\.11\.1and Llama3\.2\-3B performs worst with the shortest prompt \(Prompt A\), with accuracy varying by\.18\.18and\.15\.15across the grid for these two models, compared with\.07\.07to\.12\.12for the others\.

Figure 5:Accuracy of our algorithm against the sampling temperature for each proposal prompt, with11seed invocation on100100problems\. Prompts are ordered by accuracy pooled overmodels and temperatures\.

## Appendix FPrompts

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\.

### F\.1Default 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\.

YouareasoftwareengineertaskedwithimplementingablackboxPythonfunction‘<FUNCTION\_NAME\>‘\.Yourgoalistoimplementthisfunctioncorrectly,ensuringitworksforALLpossiblevalidinputs,notjusttheexampleinputsprovided\.

Yourprimarygoalistogetthefunctionimplementationexactlyright\.

Yoursecondarygoalistominimizethenumberoffunctioninvocationsandimplementationattempts\.

GIVENEXAMPLES:

Functioninvocations:

<INPUT\_INVOCATIONS\>

Correspondingoutputs:

<OUTPUT\_INVOCATIONS\>

STRATEGYOVERVIEW:

Youshouldworkintwophases:

1\.EXPLORATIONPHASE:Usefunctioninvocationsstrategicallytofullyunderstandthefunction’sbehavior

2\.IMPLEMENTATIONPHASE:Onlyafterthoroughunderstanding,attemptanimplementation

Thisisthefirstiteration\.Youmustdecidebetweenoneofthefollowingtwooptions:

1\.Generatemorefunctioninvocationsinthesameformatasthegivenexamples\.Choosethisoptionifyouarenotconfidentabouthowthefunctionworks\.Eachinvocationshouldbestrategicallydesignedto:

\-Testaspecifichypothesisaboutthefunction’sbehavior

\-Exploreedgecases\(emptyinputs,negativenumbers,specialcharacters,etc\.\)

\-Refineyourunderstandingofpatternsintheoutput

\-Verifyyourassumptionssystematically

Youcangenerateupto<MAX\_INVOCATIONS\>functioninvocationsacrossalliterations\.Youmustgenerateexactly1invocationinthisiteration\.

Youshouldfirstreasonabouttheproblemandtheinvocationstogenerate\.Then,returnthefunctioninvocationsinthefollowingformat:

INVOCATIONS:

“‘python

print\(’Resulti:’\+str\(<FUNCTION\_NAME\>\(args\)\)\)

print\(’Resulti\+1:’\+str\(<FUNCTION\_NAME\>\(args\)\)\)

…

“‘

whereeachprintstatementisonanewline\.ONLYincludeexecutablePythoncodewithinthecodeblock\.Youmustspecify"INVOCATIONS"intheresponse\.

2\.Generateanimplementationof‘<FUNCTION\_NAME\>‘\.

Youhaveonly<MAX\_CHECKS\>debuggingcheckstotal\.Ifyourimplementationisincorrect,youloseonecheckandareshownacounterexample\.Ifyouexhaustallcheckswithincorrectimplementations,youCANNOTtakeanymoreactionsandyourfinalattemptwillbeconsideredyouranswer\.

YoushouldONLYchoosethisoptionifALLofthefollowingconditionsaremet:

\-Youhaveseenenoughdiverseexamplestounderstandthefunctioncompletely

\-Youhaveverifiedyourunderstandingthroughstrategicinvocations

\-Youhavetestededgecasesandcornercasesthoroughly

\-YoucanconfidentlydefinethefunctionforALLpossiblevalidinputs

\-Youhaveahighdegreeofcertaintyaboutyourimplementation

Ifyouchoosethisoption,youshouldfirstreasonabouttheproblemandtheimplementationtogenerate\.Then,returntheimplementationinthefollowingformat:

IMPLEMENTATION:

“‘python

def<FUNCTION\_NAME\>\(input1,input2,…\):

…

“‘

ONLYincludeexecutablePythoncodewithinthecodeblock\.Youmustspecify"IMPLEMENTATION"intheresponse\.

ReasonaboutwhichofthetwoactionsdescribedabovetoperformandthenONLYperformoneofthetwoactions,specifyingwhichaction\("INVOCATIONS"or"IMPLEMENTATION"\)youperformedintheresponse\.

Herearetheoutputsofthefunctioninvocationsfromthepreviousiteration:

<OUTPUT\_INVOCATIONS\>

STRATEGYUPDATE:

Basedonthenewdataabove,youshouldupdateyourunderstandingofthefunctionanddecideonyournextaction\.

Followingtheformatsdescribedpreviously,youmustdecidebetweenoneofthetwofollowingoptions:

1\.Generatemorefunctioninvocationstofurtherexplorethefunction’sbehavior\.Youhave<MAX\_INVOCATIONS\>functioninvocationsleftacrossallremainingiterations\.Youmustgenerateexactly1invocationinthisiteration\.

\[…sameINVOCATIONSformatblockasPromptB1…\]

2\.Generateanimplementationof‘<FUNCTION\_NAME\>‘\.

Youhave<MAX\_CHECKS\>debuggingchecksleft\.

\[…sameIMPLEMENTATIONformatblockasPromptB1…\]

ReasonaboutwhichofthetwoactionsdescribedabovetoperformandthenONLYperformoneofthetwoactions,specifyingwhichaction\("INVOCATIONS"or"IMPLEMENTATION"\)youperformedintheresponse\.

Theimplementationyougeneratedinthepreviousiterationfailedforthefollowinginput\(andpotentiallyotherinputs\):

<FAILED\_INPUTS\>

Yourimplementationwasincorrect\.Younowhave<MAX\_CHECKS\>debuggingchecksremaining\.

Thisfailureprovidesvaluableinformationaboutacaseyoudidn’taccountfor\.Youmustdecidebetween:

1\.Generatemorefunctioninvocationstobetterunderstandwhyyourimplementationfailed\.Youhave<MAX\_INVOCATIONS\>functioninvocationsleftacrossallremainingiterations\.Youmustgenerateexactly1invocationinthisiteration\.

Afterafailedimplementation,generatingtargetedinvocationsisalmostalwaysthebeststrategy;focuson:

\-Inputssimilartothefailedcasetounderstandthepatternyoumissed

\-Variationsofthefailedinputtoisolatetheexactbehavior

\-Edgecasesrelatedtothefailurepoint

\-Inputsthatcanhelpdiscriminatebetweencompetinghypotheses

\[…sameINVOCATIONSformatblockasPromptB1…\]

2\.Generatearevisedimplementationof‘<FUNCTION\_NAME\>‘\.

Youhave<MAX\_CHECKS\>debuggingchecks\.OnlychoosethisoptionifyouareabsolutelycertainyouunderstandwhyyourpreviousimplementationfailedANDyouareconfidentyournewimplementationaddressesthatissueANDaccountsforallotherpossibleinputs\.

\[…sameIMPLEMENTATIONformatblockasPromptB1…\]

ReasonaboutwhichofthetwoactionsdescribedabovetoperformandthenONLYperformoneofthetwoactions,specifyingwhichaction\("INVOCATIONS"or"IMPLEMENTATION"\)youperformedintheresponse\.

Herearetheoutputsofthefunctioninvocationsfromthepreviousiteration:

<OUTPUT\_INVOCATIONS\>

Now,synthesizealltheinformationyou’vegatheredacrossalliterations\.Analyzepatterns,edgecases,andthefunction’soverallbehavior\.

Generateyourfinalimplementationofthefunction\.Makesureithandlesallcases,includingtheonesyou’veexplicitlytestedandothersthatfollowthesamepattern\.

Returnthefinalimplementationinthefollowingformat:

“‘python

def<FUNCTION\_NAME\>\(input1,input2,…\):

…

“‘

ONLYincludeexecutablePythoncodewithinthecodeblock\.

### F\.2Proposal Prompts

These are the four proposal prompts of our algorithm, and[§E\.6](https://arxiv.org/html/2611.18485#A5.SS6)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\.

ImplementthehiddenPythonfunction‘<FUNCTION\_NAME\>‘\.

Functioninvocations:

<INPUT\_INVOCATIONS\>

Correspondingoutputs:

<OUTPUT\_INVOCATIONS\>

Returnexactlyoneimplementationusingonlythestructurebelowwithoutanyadditionalexplanations:

IMPLEMENTATION:

“‘python

def<FUNCTION\_NAME\>\(input1,input2,…\):

…

“‘

ImplementthehiddenPythonfunction‘<FUNCTION\_NAME\>‘fromtheexamplesbelow\.

GIVENEXAMPLES:

Functioninvocations:

<INPUT\_INVOCATIONS\>

Correspondingoutputs:

<OUTPUT\_INVOCATIONS\>

First,listconcretelyHOWtheexamplesunderdeterminethefunction:namespecificinputsNOTshownaboveonwhichtwovalidimplementationswoulddisagree\(edgecases,emptyinputs,ties,ordering,types,unusualcharacters\)\.ThenpickONEunresolvedinterpretation–notnecessarilythemostpopularone–andimplementit\.Theimplementationmustreproduceallgivenexamplesexactly\.Returnexactlyoneimplementationusingonlythestructurebelowwithoutanyadditionalexplanations:

IMPLEMENTATION:

“‘python

def<FUNCTION\_NAME\>\(input1,input2,…\):

…

“‘

YouareasoftwareengineertaskedwithimplementingablackboxPythonfunction‘<FUNCTION\_NAME\>‘fromasetofinput\-outputpairsprovidedbelow\.

Yourgoalistoimplementthisfunctioncorrectly,ensuringitworksforALLpossiblevalidinputs,notjusttheexampleinputsprovided\.

GIVENEXAMPLES:

Functioninvocations:

<INPUT\_INVOCATIONS\>

Correspondingoutputs:

<OUTPUT\_INVOCATIONS\>

Youshouldfirstbrieflyreasonabouttheproblemandallpossibleimplementationsthatmayleadtothisinput\-outputbehavior\.Everyproposedimplementationmustsatisfyallprovidedinput\-outputexamplesexactly\.Acrossproposals,favordiversityinhypothesesandcomplexity:includesimplerandmorestructuredalternatives\(forexampledirectformulas,conditionals,loops,helperfunctions,ordifferentalgorithmicstrategies\),whilestayingconsistentwiththeexamples\.Returnexactlyoneimplementationusingonlythestructurebelowwithoutanyadditionalexplanations:

IMPLEMENTATION:

“‘python

def<FUNCTION\_NAME\>\(input1,input2,…\):

…

“‘

YouareasoftwareengineertaskedwithimplementingablackboxPythonfunction‘<FUNCTION\_NAME\>‘fromasetofinput\-outputpairsprovidedbelow\.

Yourgoalistoimplementthisfunctioncorrectly,ensuringitworksforALLpossiblevalidinputs,notjusttheexampleinputsprovided\.

GIVENEXAMPLES:

Functioninvocations:

<INPUT\_INVOCATIONS\>

Correspondingoutputs:

<OUTPUT\_INVOCATIONS\>

IMPORTANT:thissamepromptisbeingsenttoyoumanytimesindependently,andyouranswersarepooledintoasetofcompetinghypotheses\.DoNOTdefaulttothesinglemostobviousimplementationeverytime\.TreatyouranswerasONEDRAWfromthespaceofalldistinctrulesthatreproducethegivenexamplesexactly,sampledinproportiontohowplausibleeachruleis\.DifferentdrawsshoulddisagreewitheachotheroninputsthatareNOTinthegivenexamples,whileallagreeingontheexamplesthemselves\.

Youshouldfirstbrieflyreasonabouttheproblemandenumerateseveralgenuinelydifferentrulesthatallreproducethegiveninput\-outputbehavior–theymaydifferinhowtheygeneralise\(edgecases,emptyornegativeorextremeinputs,types,ordering,off\-by\-oneboundaries\)orinalgorithmicstrategy\(directformula,conditionals,loops,recursion,helperfunctions,librarycalls\)\.ThenpickONEofthemandcommittoit\.Everyproposedimplementationmustsatisfyallprovidedinput\-outputexamplesexactly\.Returnexactlyoneimplementationusingonlythestructurebelowwithoutanyadditionalexplanations:

IMPLEMENTATION:

“‘python

def<FUNCTION\_NAME\>\(input1,input2,…\):

…

“‘

### F\.3Input Distribution Prompt

This prompt instantiates the input distributionμ\{\\color\[rgb\]\{0,0,0\}\\mu\}\. It is sampled repeatedly, once per problem and before the first query, and each parsed completion becomes one element ofS\{\\color\[rgb\]\{0,0,0\}S\}\.

YouarechoosingoneinformativetestinputforahiddenPythonfunction‘<FUNCTION\_NAME\>‘\.

Knownexamples:

Functioninvocations:

<INPUT\_INVOCATIONS\>

Correspondingoutputs:

<OUTPUT\_INVOCATIONS\>

ReplywithONLYtheINVOCATIONSblockbelow–nopreamble,noheadings,noexplanations,andnotextoutsidethefencedPythonblock\.

INVOCATIONS:

“‘python

print\(’Result1:’\+str\(solution\(args\)\)\)

“‘

Preferdiverseinputs\(edges,negatives,extremes,unusualstructures\)insidethesingleprint\(…\)line\.

## Appendix GAI 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\.

Similar Articles

Learning POMDP World Models from Observations with Language-Model Priors

Hugging Face Daily Papers

This paper introduces Pinductor, a method that uses language model priors to efficiently learn POMDP world models from limited observation-action data, achieving performance comparable to methods with privileged hidden state access while surpassing traditional tabular approaches.

Coding agents think ahead of time

Hacker News Top

This paper investigates how language models under coding agents internally represent the evolving program during iterative editing. The authors find that linear probes can decode program properties (e.g., parsing, test pass rate) from residual streams, and surprisingly, these representations predict future outcomes before the agent materializes edits, revealing a 'latent programming horizon'.