betaFeedback

WorksComputer Science

The Price of an Explanation: What Demanding Verifiable Artifacts Costs, and What It Buys Back

Abstract

Generative models produce many candidate solutions but provide no intrinsic signal by which to rank them. One mitigation is to demand a verifiable artifact: a program that can be executed against the available evidence. A common concern is that requiring executable verification incurs costs in both solution quality and computational budget. We measure these two costs on the 120120-task ARC-AGI-2 evaluation set. Demanding a verifiable artifact from an LLM reduced the score from 9393 to 6868 of 120120 tasks (77%77\% to 57%57\%). Of those 2525 tasks, 2121 were reached by no program-producing configuration we ran, at any budget, by sampling or by search; yet for 2727 of the 2828 tasks that only the answer-only arm solved, some program arm held a program that reproduced every demonstration and still failed the test. The bottleneck is obtaining an explanation that generalizes, not finding one. A short evolutionary search over two already-sampled programs, at no additional model cost, beats best-of-22 sampled code by 9.2±1.49.2 \pm 1.4 tasks, and over a single sampled program beats 11-shot sampling by 9.9±1.39.9 \pm 1.3. Moreover, because a program can be checked against the training examples, any program-producing protocol can terminate early once a task is explained: under the same stopping rule, best-of-nn sampling declines up to 38%38\% of its budget and the evolved arm up to 49%49\%, whereas an answer-only baseline cannot terminate early. Applying the same methodology to decoder synthesis for quantum error correction yields interpretable decoders evaluated against a certified panel of published decoders on held-out exam shots.

Introduction

Large language models (LLMs) are increasingly finding applications in science [45, 6, 19]. Their ability to ingest and synthesize vast amounts of information makes them an appealing tool for hypothesis generation, literature review, experimental design, and more [46]. However, substantial risks arise when incorporating LLMs into the scientific process [17, 4], including confidently claiming plausible-sounding but ultimately wrong results [38, 42]. A common mitigation is to demand a verifiable artifact from the LLM in the form of code, even when the problem is not intrinsically a coding one [28, 34, 49, 23]. The code acts not only as an answer, but as a verifiable explanation of where the answer comes from. However, demanding verifiability incurs a cost, for example in the form of additional inference-time computation [43] or repeated sampling [9].

Program synthesis driven by a language model and steered by an evaluator has produced results in mathematics [34], algorithms [40] and robotics [28], among others. Self-consistency and best-of-nn sampling [48] are the established baselines for any such loop. On ARC specifically, sampling programs from a language model and filtering them on the demonstrations is the method of Greenblatt [2024] and of hypothesis search [47]; BARC [26] trains the generator on synthetic tasks and combines program induction with direct output prediction, and HySynth [3] uses the model as a learned prior over a grammar that guides enumerative synthesis. Improving model-written code by evolutionary variation is the subject of evolution through large models [25], language-model crossover [31] and LLM-guided genetic improvement [10]. While these works investigate how to maximize program-synthesis accuracy, they do not isolate what requiring an executable program costs relative to a matched answer-only baseline on the same model, nor quantify how much inference budget verification recovers via early termination; providing those controlled measurements is the primary contribution of this paper.

Code, unlike free-form natural language, admits verification by formal proof, which LLMs can increasingly generate [18] at token budgets in the hundreds of millions [24], or more cheaply by generating and verifying together [27]. Verifier-guided search over code in Dafny and Coq [7] and neurosymbolic self-debugging for mathematical code [33] both report more accurate code at lower cost; in both, the problem space admits no non-verifiable answer, so no cost comparison with an answer-only baseline is possible. Here we consider problems whose solutions do not require a verifiable artifact, but where one could be demanded, on the Abstraction and Reasoning Corpus, ARC-AGI-2 [11, 13]. Each ARC task consists of train input-output pairs exemplifying rules that transform an input grid into an output grid, which must then be applied to held-out test inputs. The benchmark is purposefully small (1,000 training, 120 evaluation tasks) to resist purely data-driven approaches in favor of abstraction and reasoning.

Producing the correct output grids is sufficient to succeed in ARC. One may, however, additionally demand that the solution be given as code that maps the inputs to the desired outputs (Figure 1). That is, one can demand a verifiable explanation. A successful strategy to achieve high scores in the ARC-AGI-1 version of the benchmark was to create domain-specific languages (DSLs) and search that space, sometimes aided by a language model [22, 12]. However, the most successful strategies for ARC-AGI-2 use DSLs more incidentally, to generate large datasets of ARC-like tasks, thus shifting the problem space back to where data-driven approaches perform well [14]. This strategy allowed language models to dominate the ARC-AGI-2 Kaggle competition.

Figure 1. A verifiable artifact. Task 1818057f of the public ARC-AGI-2 evaluation set: three worked examples, an unseen input, and the program our search returned. The rule, which is to recolor every plus-shaped yellow cluster light blue, is stated nowhere and must be inferred, and what is submitted is the program rather than the grid. The program is written in the restricted vocabulary of a domain-specific language (DSL; highlighted in blue; 4 and 8 are ARC’s color codes for yellow and light blue). It reproduces all three worked examples; a program with that property is what we call an explanation, and its cost is what this paper measures. On the unseen input it reproduces the held-out answer exactly. Four other set_cell lines are elided where marked.

Here, we first quantify the costs of verifiability by asking one leading model to codify its solutions using a DSL derived exclusively from the ARC-AGI-2 training tasks. Second, we explore how a brief, effectively free search process on generated code—making no further model calls—can mitigate, and in some cases negate, these costs. We used a simple evolutionary algorithm for this search, though other search procedures (e.g., Monte Carlo tree search [44]) could be substituted. Finally, we transfer the methodology to a real-world domain, quantum error correction [20], where we synthesize a new decoder (error-correcting algorithm) of the belief-propagation family [37] with ordered-statistics post-processing (BP+OSD) [36, 39] for bivariate-bicycle codes [8].

Methods

The methodology we evaluate composes a language model with evolutionary search: the model proposes candidate programs, scored on the train pairs, filtered and ranked. The search uses steady-state grammatical evolution [35] (MAP-Elites [32] in § 3.5 and § 3.6), and our LLM-only baselines are best-of-BB computed from the first BB samples of one ordered cache rather than from independent re-runs. We compare three experimental arms (Figure 2):

Figure 2. Solves against realized spend. The answer-only arm (orange stars) predicts outputs directly. Solutions cost 1.39×k1.39 \times k per task, because each test input requires a separate LLM call. The explainable arm (navy circles) is shown at fixed best-of-nn program sampling (Figure 3 and Table 4 also give it the stopping rule). The evolved arm (cyan diamonds) has an LLM call budget BB used for seeding up to 2 solutions for evolution, and for in-loop LLM improvements afterwards; it stops once it holds two distinct train-perfect candidates (§ 3.4). Per-point bars are within-run replica noise (E, 3 replicas), within-style draw noise (X), or block-and-run noise (A0).

Answer-only (A0) Direct LLM prediction of output grids, without an executable explanation.

Explainable (X) Independent LLM program sampling steered to use the DSL.

Evolved (explainable) (E) LLM-seeded DSL programs refined via evolutionary search and optional in-loop LLM calls.

Nothing about an answer-only (A0) candidate can be checked before it is scored. An explainable arm (X and E) instead produces candidate solve functions, executes each against the training pairs, and scores it by the fraction of correct outputs. Train-perfection—reproducing all of the train outputs—is what makes a candidate an explanation, a verifiable property of the artifact whose soundness we measure in § 3.5. Two properties of a program artifact should be distinguished: verifiability comes from execution against the demonstrations and belongs to any program, in a DSL or in free Python (§ 3.2), whereas the DSL governs what a search can do with the artifact and what a reader can audit as a bounded vocabulary.

Submission rule, shared by X and E. ARC allows two attempts per test input. Both program arms submit the same way: candidates are ranked by train score (ties broken in favor of the later sample), attempt 1 is the top candidate, and attempt 2 is the highest-ranked candidate whose test predictions differ from attempt 1’s, a diversity hedge that inspects only the test inputs. At B=2B=2 the explainable arm holds two samples and submits both whenever their predictions differ, so the train-score ranking cannot change what it submits; the paired comparison of § 3.3 therefore does not depend on the ranking rule. Its contribution for B>2B > 2 is measured in App. § 10.

We use gemini-3.5-flash (medium thinking budget) across all arms as a capable reasoning model that does not saturate the benchmark (< 95% accuracy). The search never sees test outputs, and an evolved run stops once it holds two train-perfect programs with distinct predictions: training fitness and the candidate’s own outputs on the test inputs are the only signals a run may use. The explainable arm is reported at a fixed best-of-BB throughout, and § 3.4 also evaluates it under the same stopping rule.

Substrate and credit rule. All ARC results are on the full 120-task ARC-AGI-2 public evaluation set. ARC’s protocol is best-of-2 per test input and 45 of the 120 tasks carry more than one test input

(167 in all.) We use the scoring protocol of the ARC leaderboard—score each input independently, report the task’s mean [ARC Prize Foundation, 2026]—everywhere except Table 1. In that table, we use strict credit to count which tasks have been solved (i.e., every test input has the correct output). The two are never mixed inside a comparison.

tasks solved
A0, grid prediction (no explanation available)93
best explainable arm (E, at any budget)68
union of explainable arms (X ∪ E)72
union across all arms (A0 ∪ X ∪ E)100
solved by A0 only (no program arm)28
solved only with an explanation7

Table 1. The cost of demanding a verifiable artifact, on 120 ARC-AGI-2 evaluation tasks, DSL prompt. The union row is an oracle over the explainable arms, not a protocol (§3.1). This table uses strict credit rather than leaderboard score, because set differences require a binary verdict per task. Every arm enters as the majority of its three runs.

The answer-only (A0) and explainable (X) arms. A0 predicts grids directly, taking k=12k=12 samples and two attempts by majority vote; because it has no program to re-run, it pays per test input (16.7 calls/task at k=12k=12). The explainable arm X steers the LLM to write DSL code transforming train inputs into outputs; all sampling curves read a single ordered k=16k=16 cache per style so that best-of-BB for B∈{1,2,4,8,16}B \in\{1, 2, 4, 8, 16\} is a nested prefix of the same samples.

The evolved arm (E). Given a per-task LLM call budget B∈{1,2,4,8,16}B \in\{1, 2, 4, 8, 16\}: (i) sample min⁡(2,B)\min(2, B) seed programs using X’s prompt; (ii) if both are train-perfect with distinct test predictions, submit both and stop; (iii) if one is train-perfect, lock it as attempt 1 and evolve, seeded with both, for a hedged attempt 2; (iv) if neither is, evolve seeded with both and submit a hedged best-of-2. Evolution spends any remaining budget on in-loop LLM calls at rate p=0.03p = 0.03 per birth while budget lasts.

The DSL, error bars, and QEC transfer. From a conceptual analysis of the 1,000 training tasks (App. A), we built a 91-function Python DSL without inspecting the 120 evaluation tasks (free-form Python is compared in App. B). We report E[solves], using the directly measured run-to-run spread of 1.86 solves (App. D) rather than within-run replica noise (SE 0.5–1.1) for cross-run comparisons. To test transferability, we instantiate the same design on decoder synthesis for the [[72,12,6]]\left[\left[72, 12, 6\right]\right] bivariate-bicycle qLDPC code [8] with a 38-operation BP+OSD DSL [36, 39] (App. I).

Results

The cost of demanding a verifiable artifact

We compare the answer-only arm A0 against the explainable arms on the 120-task evaluation set as solved-task sets rather than as rates, so that the cost of the demand can be written as a set difference. To place all arms on a common basis, a task is credited to an arm in Table 1 if it is solved in a majority (at least two) of its three runs: three replicas for E, three seed draws for X, and three runs for A0. The union of explainable arms is taken over the two program protocols, X (best-of-16 sampling) and E (pooled over B∈{1,2,4,8,16}B \in\{1, 2, 4, 8, 16\}), both under the DSL prompt.

The cost of demanding a verifiable artifact can be measured in two ways: (1) The computational cost: the A0 arm at one sample per test input (1.39 calls/task) scores 63.8 (leaderboard credit); the evolved arm reaches that level at B=8B=8 (64.7, 5.16 calls) and the explainable arm at B=16B=16 (66.3, 9.9 calls), inside the 1.8–4.2 solve spread across seed draws. (2) The accuracy cost: at the answer-only arm’s largest budget (k=12k=12, 16.7 LLM calls), the demand costs 93−68=2593 - 68 = 25 solved tasks (Table 1). Against the union of DSL program arms, 28 tasks solved by A0 were solved by no DSL arm, at any budget, by sampling or by search, while 7 were solved only by a DSL arm (net 21; the remaining 4 is an oracle margin over the union, which no single protocol achieves without knowing in advance which arm to run). Adding the free-form prompt of § 3.2 (fourteen program arms in all) raises the union from 72 to 81, leaving 21 tasks reached by no program configuration we ran against 9 solved only by one—bounds over our finite configuration set and one model, not properties of the program representation. Figure 2 shows the spend curve.

The exchange is two-way: seven tasks are solved only by an arm that produced an explanation, whereas no answer-only run reached them across three runs of twelve samples per test input. Crucially, of the 28 tasks solved only by A0, 27 had a train-perfect program in at least one program arm (pooled across X’s three draws and E’s nine runs); thus a program explaining the demonstrations was found on nearly all of them, and what was submitted did not generalize (§ 3.5, App. § 11). The two subsets also differ in structure: 54% of A0-only tasks carry multiple test inputs versus 26% of tasks solved by both modalities, and their input grids are larger (median 456 vs. 316 cells). Because A0 receives k=12k=12 samples per test input (16.7 calls per task, more than the B≤16B \le16 budgets of the program arms), the comparison is unfavorable to the program arms on budget by construction.

The cost of using a DSL

We re-ran both program arms with a second prompt that provides no DSL and requests pure Python with NumPy and SciPy; evolutionary search then ingests the model’s code as an abstract syntax tree, the representation grammatical evolution operates on.

Free-form code leads the DSL in the explainable arm at every budget, in 15 of 15 (budget × draw) cells. Under evolution it still leads at every budget, but the gap is sign-unstable across seed draws, and evolution adds more to the DSL arm (+9.2 solves) than to the free-form arm (+6.1), so the two nearly tie at B=2B=2 (App. § 6). This reflects a trade-off between model fluency and structured search: the DSL lowers initial sampling accuracy but provides a bounded, auditable vocabulary amenable to AST-level evolutionary operators, whereas free-form Python leverages the model’s pretraining fluency at the cost of 4.4× higher native-library crash rates (§ 4.1). Verifiability is identical for both.

Search over programs already purchased

Because an explanation is checkable against the training pairs without a model call, it can drive syntactic search over already-sampled programs. We compare the evolved arm at B=kB=k against the best-of-kk explainable arm for k∈{1,2}k \in\{1, 2\}, where both arms consume the same seed program(s) and the evolved arm spends nothing further on the model; pairing on three independent seed draws cancels the seed-draw variance that dominates each arm separately.

Given the same model calls, the evolved arm outperforms the explainable arm by +9.89±1.26+9.89 \pm1.26 solves at one call (+9.7+9.7, +12.2+12.2, +7.8+7.8; paired tt-test p=0.016p=0.016) and +9.22±1.40+9.22 \pm1.40 at two (+10.0+10.0, +6.5+6.5, +11.2+11.2; p=0.022p=0.022), each mean ±\pm SE over three paired seed draws (strict credit: +8.67±0.96+8.67 \pm0.96 and +7.56±1.68+7.56 \pm1.68; free-form: +7.56±1.21+7.56 \pm1.21 and +6.11±1.03+6.11 \pm1.03; Table 2, Figure 2). Evolution is worth at least a doubling of the seed budget at no additional API cost, trading model calls for modest wall time (mean 100 s, median 7 s per task at B=2B=2 under a 900 s deadline; App. E).

cellspendevolvedexplainableΔ\Delta
B=1B=1, dsl151.741.8+9.9
B=1B=1, no_dsl153.045.4+7.6
B=2B=2, dsl258.449.2+9.2
B=2B=2, no_dsl260.354.2+6.1
B=4B=4, dsl3.3860.756.4+4.3
B=8B=8, dsl5.1664.760.7+4.0
B=16B=16, dsl8.0966.963.2+3.8
B=4B=4, no_dsl3.2365.961.8+4.1
B=8B=8, no_dsl4.8766.166.0+0.0
B=16B=16, no_dsl7.2068.467.6+0.8

Table 2. Comparison of the evolved (E) and explainable (X) arms at matched realized spend. At B≤2B \le2 the evolved arm spends calls only on seeds (one at B=1B=1, two at B=2B=2) plus syntactic search, paired draw-for-draw on draws 1–3 (§3.3); at B≥4B \ge4, remaining budget funds in-loop model calls and the explainable column interpolates the k=16k=16 sampling curve (draws 1, 2, 4) in log⁡2\log_2 calls. Because the per-cell spread across seed draws is 1.8–4.2 solves, no individual in-loop row is statistically distinguishable from zero; the gain is largest at B≤2B \le2, where no in-loop calls are made.

An adaptive stopping rule

A program that reproduces every train example is, by the protocol’s rule, finished. This property belongs to the artifact, not to the search: an arm that samples programs sequentially can apply the same stopping rule, whereas the answer-only arm has no executable check against the demonstrations (sample consensus [1] tests agreement, not verification). We measure realized spend as a fraction of permitted budget for both program arms at B∈{4,8,16}B \in\{4, 8, 16\} over three seed draws, giving the explainable arm the rule offline on the same ordered sample caches (stop once two train-perfect programs with distinct predictions are held; App. F).

Figure 3 shows the result (also visible in Figure 2, where every evolved point above B=2B=2 sits left of its budget’s tick). The sampler declines 10%, 23% and 38% of its budget at B=4B=4, 8, 16 while scoring within 2 solves of fixed best-of-BB (66.3 vs. 66.3 at $B=16). The evolved arm declines 15%, 36% and 49% at 66.9 solves at B=16B=16 (8.09 calls/task), saving additional in-loop budget once a task is explained. Stopping at the first explanation saves 73% at B=16B=16 but loses ten solves (56.0), because the first train-perfect program is often not the right one (§3.5). Verifiability is thus not only an audit property paid for at the end, but a scheduling property that pays back during the run to any protocol holding a checkable artifact.

Figure 3. Savings due to the stopping rule: the share of its permitted budget each program arm declines, DSL prompt, mean over three independent seed draws. Navy: the explainable arm given the rule—sequential sampling that stops once it holds two train-perfect programs with distinct predictions (App. F). Cyan: the evolved arm, whose remaining budget buys in-loop model calls. The answer-only arm, run at fixed kk, has no checked signal on which to stop. The two arms’ solves at these points are within 0.6 of each other at B=16B=16 (66.3 against 66.9) and within the seed-draw spread everywhere (Table 4).

Soundness of the explanation, and the generalization gap

An explanation is, in practice, a necessary but not sufficient condition for correctness. Across 1,079 of 1,080 trials (three search arms ×\times three in-loop rates ×\times 120 tasks; one lost to a dead worker), *lucky matches—programs that produce the correct test output without reproducing the train pairs—number 0–2 per cell. Filtering by train-perfection therefore discards almost nothing it should have kept, thus justifying the stopping rule of §3.4.

An explanation of the demonstrations is often not the rule. The converse direction does not hold: 106 of 120 tasks yielded a train-perfect explanation, yet at most 68 converted to a solve, so on at least 38 of the 106 tasks (36%) the verified explanation failed to generalize. The binding constraint was not finding a program consistent with the demonstrations, but obtaining and selecting one that captures the intended rule. At B=16B=16 (three draws) a train-perfect program was sampled on 102–106 tasks and one also test-correct on 71–72, while the selector converted 61–64 (an oracle over the sampled pool recovers 8–11 solves). Nor is it search budget: quadrupling both search caps changed no outcome across 188 budget-bound cells, and stopping at the first explanation lost ten solves (§3.4).

Consistent with this, a learned selector did not close the gap. A classifier trained on the ARC training split to rank candidate programs (gradient-boosted and logistic models, held-out AUC 0.95–0.97) re-ranked the submission in 41% of cells (90% of cells where the selector chooses both attempts), yet changed solved tasks by less than the variance across four control runs of the same arm (55.5 ± 0.19 vs. 55.3 and 55.7). Although the same classifier improved selection by +4.4 solves on pools of independent LLM samples, features that discriminate among independent samples (prediction consensus, rank, and score gaps) fail to separate the closely related genealogical variants produced by a search that halts at train-perfection. Even so, an executable artifact is what makes this gap observable and diagnosable, whereas an answer-only model conceals it entirely.

Evolutionary search without a language model solved nothing. We found no train-perfect programs across 120 tasks and three seeded replicas, measured on the same DSL vocabulary as every other arm reported here. The explanation’s value therefore derives from the composition of a generator that proposes with a verifiable artifact that filters and guides, and not from the search machinery on its own.

Transfer: decoder synthesis for quantum error correction

To assess transferability, we applied the same methodology to synthesize quantum error-correction decoders for the [[72,12,6]][[72, 12, 6]] bivariate-bicycle code under circuit-level noise at p=0.004p = 0.004 (App. § 13, Düñez et al. (2026)). Every result is adjudicated on 200,000 held-out exam shots (read once per frozen algorithm, never fed back into optimization) against a panel of published decoders written in the 38-operation DSL and certified per shot against the authors’ implementations (ldpc, relay-bp). Inside the search, cost is measured by a seven-counter primitive-level work proxy fitted to native Rust execution across 252 programs (R2=0.998R^2 = 0.998, Kendall τ=0.973\tau= 0.973 rank agreement with wall-clock time on the fitting nodes and τ=0.935\tau= 0.935 on the benchmark workstation); adjudicated cost verdicts must hold on both the work proxy (at a 1.4× margin) and clean single-core wall-clock time per shot, which agree within 1.01–1.26× on every timed finalist with zero proxy verdicts refused.

Auditing reference implementations via the DSL. Writing BP+OSD-0 in the DSL exposed a message-damping parameter that the reference ldpc package does not export. Undamped, the flooding min-sum front end exhibits a 47.66% logical error rate (LER) versus 5.15% when damped at 1.04× the belief-propagation work (9.3× fewer errors), and re-parameterizing each ldpc decoder with damping yields a 17.1–41.0× speed-up (split B, 200 000 shots). Expressing reference algorithms in the same transparent vocabulary as candidate solutions thus enabled auditing the baseline itself.

The evolved decoders hold the fast end of the front; the published ones hold the accurate end. On split A the damped reference P2-d reads 5.45% LER at 8.82 ms per shot. The evolved C03 (seeded from the panel, no language model) reads 4.18% at 5.66 ms (0.64× the reference’s time, 23% fewer errors, z=+31.8z = +31.8); C04 and C10, evolved from random code, read 4.14% and 4.07%. Faithfully implemented ambiguity clustering (BP+AC, P10) reads 3.57% at 31.8 ms; the authors’ Relay-BP reads 3.17% at 190.0 ms (stop 5) and 2.80% at 270.6 ms (stop 9); ldpc’s tuned BP+OSD-0 reads 4.39% at 903.8 ms. The time–error front over these rows has seven decoders: four evolved at the fast end, BP+AC and the two Relay-BP points at the accurate end. Relay-BP is the most accurate published decoder on these shots, at 21.6–30.7× the reference’s time.

The composition with the language model in the loop. Five runs of the hybrid arm (352 founding model calls per run, then p=0.001p = 0.001 per birth) produced E083: 3.17% LER (6 347 errors in 200,000 exam shots, split B) at 36.2 ms per shot, more accurate than the damped reference (z=+53.8z = +53.8) and our BP+AC port (z=+7.5z = +7.5), less accurate than Relay-BP (z=−8.8z = -8.8 at stop 9; −9.8-9.8 against the authors’ package), structurally novel (call-multiset distance 2 to its nearest panel member), at 3.9×3.9 \times the reference’s cost (Table 6, Figure 4). Matched by seed, the hybrid arm beat random founders 5 of 5 and expert-panel seeds 0 of 5: the language model lifted a random-founder search to panel-class accuracy but did not improve accuracy over seeding directly from the expert panel—mirroring the ARC finding that the evolved arm’s gain is concentrated at seeding rather than in-loop calls. The answer-only analogue on QEC is a learned decoder, a neural network trained on shots [29, 15, 5, 30], whose algorithm is implicit in its weights and assessable only by behavior [41], whereas a DSL decoder is the explanation itself. For the LLM-driven and free-form analogues, AlphaEvolve [34] given the same DSL generated 5,144 programs (167 M tokens); its champion AE-DSL reads 4.26% LER at 52.9 ms and is outperformed by E083 on the same shots (z=+28.7z = +28.7) at 0.69× its time, while AlphaEvolve in unconstrained free-form Python synthesized an exact F2_2 solver (1.95% LER at 168 ms/shot) outside the fast real-time regime.

Table 6: Exam-split accuracy and cost on 200 000 held-out shots of split B. Proxy and pinned-core time are in units of the damped reference P2-d on one pinned Intel Xeon Platinum 8581C core (the two rulers of the cost-model paragraph above); ms/shot is the clean single-process time on the benchmark workstation (Apple M3 Ultra), where the reference reads 8.91 ms (8.74 ms in the relay-bp timing session, giving 19.7× and 31.0× for stops 5 and 9). zz is McNemar on the discordant shots, positive when the row is right more often than the comparator. The package rows carry no proxy and were not timed on the pinned core. Rows are ordered by LER within each block. Two bars are reported: primary is more accurate than the reference and not dominated by a panel member; stretch adds cheaper than the reference by the 1.4× margin on both rulers. E083’s and AE-DSL’s proxy and pinned-core ratios were measured in a separate session on the same core.

decoderarm / rulerLER %proxy ×P2-dtime ×P2-dms/shotz vs P2-dz vs P10note
E083hybrid (LLM in loop)3.173.883.4836.2+53.8+7.5primary; novel (P10 at 2)
C14seeded, work proxy3.212.42.145—+54.7+9.4primary; retuning of BP+AC (P10 at 0)
C10unseeded, wall-clock4.042.72.38929.0+35.9−22.0primary (from scratch)
C04unseeded, work proxy4.072.01.88220.6+35.8−20.6primary (from scratch)
C08seeded, wall-clock4.160.570.5346.96+33.1−19.6stretch (both rulers)
C03seeded, work proxy4.170.580.5655.66+33.4−19.6stretch (both rulers)
C09seeded, wall-clock4.320.540.5375.42+30.8−22.5stretch (both rulers)
C07seeded, wall-clock4.690.460.4566.15+23.3−31.9stretch (both rulers)
AE-FreeAlphaEvolve (free-form)1.95——168——exact F2F_2 solver, outside the DSL
AE-DSLAlphaEvolve (DSL)4.263.283.0952.9+30.2−24.75,144 LLM calls
Relay-BP (pkg)published, stop 92.82——272.0+58.6+16.7relay-bp package
P5 Relay-BPpanel port, stop 92.8640.035.57—+58.0+15.5DSL port of Relay-BP
Relay-BP (pkg)published, stop 53.17——172.8+51.3+7.0relay-bp package
P10 BP+ACpanel (faithful)3.443.02.6731.8+48.9—45 prod-sum sweeps, κ\kappa=0.1
P3 BP+OSD-CSpanel (ldpc pt.)3.8426.0—372.35+36.7−11.530 serial sweeps, order 60
P3-dpanel (damped CS)4.22——21.71+28.8−21.110 damped sweeps, order 60
P2 BP+OSD-0panel (ldpc pt.)4.3525.1—365.08+25.8−25.730 serial prod-sum sweeps
P2-d (ref.)panel reference5.531.01.008.91—−48.910 damped min-sum sweeps

Table 6.

Two discovered decoders in the 38-operation DSL

Figure 4. Two discovered decoders in the 38-operation DSL, after dead-code pruning (prediction-identical to the unpruned programs on 32 768 validation shots). solve_e083 (from the LLM-in-the-loop hybrid arm) combines ambiguity clustering’s marked-row reduction and narrow block enrichment (κ=0.04\kappa= 0.04) with a weight-1 combination-sweep search (Scope.OSD_CS) and a logical-class majority vote, sitting at call-multiset distance 2 from P10 (BP+AC) and reducing its error rate by 7.6% (z=+7.5z = +7.5). solve_c03 replaces BP+AC’s 45-sweep product-sum front end and weight-2 search with 9 damped min-sum sweeps and a weight-1 block vote, cutting errors by 23% relative to P2-d at 0.64× its time.

Discussion

Demanding a verifiable artifact cost 25 of 120 ARC tasks (28 reached by no DSL arm, 21 by no program arm across both prompts) and returned a capability an answer-only option cannot provide at any budget: a run that certifies its own completion, declining up to 38% of the budget under sampling and 49% under search while converting already-purchased samples better than best-of-nn sampling (+9.2 ± 1.4 solves at B=2B=2). On QEC, the same methodology yields interpretable decoders adjudicated on held-out exam shots across two cost rulers (§ 3.6).

One subtlety in the accuracy cost deserves reflection. ARC-AGI-2 training examples are designed so that human subjects converge on the intended test outputs, yet they admit countless algorithmic explanations that fail on the test inputs: human cognitive priors, not abstract logic alone, select the “correct” rule. Our system found valid training explanations for 106 of the 120 tasks, but the answer-only arm solved, but converted at most 68 because the demonstrations under-specify the intended rule (§ 3.5). On ARC this is a limitation of the generator, DSL, or selector; in scientific discovery, generating valid hypotheses that human intuition discounts can be a feature, surfacing candidates scientists might overlook. As models trained on human-preferred text increasingly both produce and review research, insisting on executable explanations consistent with the evidence—and searching beyond initial proposals—provides a check against plausible-sounding errors at a modest cost, which future work can reduce by strengthening selection, refining the DSL, prompting an answer-only model to synthesize a program explaining its committed prediction post hoc (a protocol we did not evaluate), or pairing code synthesis with formal proof [18, 7, 27].

Limitations

In-loop LLM calls never scored below best-of-nn code at matched spend, but no in-loop cell clears the seed-draw spread; the evolved arm’s margin is largest at seeding (B≤2B \le2), and evolutionary search without an LLM solved nothing on ARC-AGI-2. On QEC, Relay-BP (190–271 ms/shot) and AlphaEvolve’s unconstrained exact solver (168 ms/shot) reach lower error rates on the exam shots, while decoders evolved in the DSL lead the fast end of the time–error front and the sub-50 ms regime on one code and noise model. Replicating the ARC arms on gemini-3.8-flash (App. § 12) reproduced the conversion margin (−8.22±0.24-8.22 \pm0.24 DSL, +5.50±0.42+5.50 \pm0.42 free-form, paired) while the answer-only lead widened past 30 tasks at every budget; neither design excludes pretraining memorization of the public evaluation split. Finally, free-form code incurs 4.4× more native library crash sentinels than DSL code, and all findings remain tied to the specific DSLs, models, and search operators tested. Disclaimer on use of AI: Beyond the LLM experiments reported, Claude Opus, Claude Fable, and Gemini were used to draft and revise this manuscript; all claims and text have been human-reviewed and verified.

The DSL for ARC

We initially constructed two human-designed prototype DSLs to express solutions to ARC training tasks: one based on whole-grid transformations and pixel-level operators, and a second that parsed grids into a relational tree of objects inspired by scene graphs. Neither prototype alone was sufficiently expressive to capture the breadth of the training corpus.

We therefore used gemini-3.1-pro to analyze all 1,000 training tasks and extract the 1–3 most salient transformation concepts per task, organizing them into an inverted index mapping each concept to the training tasks it spans. Combining this concept index with the two prototype DSLs, we iteratively synthesized the final DSL over six stages with the assistance of Claude Code. Each stage selected the highest-coverage concepts not yet represented (covering at least three training tasks), implemented typed operations for them, and verified reference solutions on those tasks, interleaved with refactoring passes that consolidated recurring idioms into shared primitives.

The resulting DSL defines categorical enum constants (e.g., orientation, 4- or 8-connectivity), geometric value types (such as bounding boxes and pixel sprites), and 91 pure functions partitioned into pixel-level operations (24%), bounding-box operations (27%), and higher-level relational and object concepts (49%). Below is a representative function from the vocabulary:

def holes(grid: np.ndarray, background: int = 0) -> list[Sprite]:
    """Enclosed background regions (not reaching the border) as sprites,
    row-major.

    The witness companion to ‘‘fill_holes‘‘: each hole carries the
    underlying (background-colored) cells, so painting is ‘‘paste_all(g,
    [recolor(h, c) for h in holes(g)])‘‘, and the has-a-hole test is
    ‘‘count(holes(as_grid(s))) > 0‘‘
    """
    if grid.size == 0:
        return []
    labels, n_labels = ndimage.label(grid == background)
    border = np.unique(
        np.concatenate([labels[0], labels[-1], labels[:, 0], labels[:, -1]])
    )
    found = [
        _sprite_from_mask(grid, labels == i)
        for i in range(1, n_labels + 1)
        if i not in border
    ]
    return sorted(found, key=lambda s: (s.row, s.col))

Explainable code without a DSL

In addition to the DSL prompt, we evaluated both program arms using LLM-generated free-form Python code (with NumPy and SciPy). The full results across budgets appear in App. C.

Setup. The two prompt styles differ only in whether the generator is steered to the restricted ARC vocabulary. We compare them within each arm across the five budgets and three seed draws, yielding 15 (budget × draw) cells for the explainable arm X.

Restricting the generator to the DSL lowers raw sampling accuracy at low budgets: free-form code leads in all 15 cells, by +1.7 to +12.2 solves. Under evolutionary search at B=2B=2, however, the two styles nearly tie at 58.4 versus 60.3 (free-form) solves—58.6 versus 61.4 after correcting for native-library crash sentinels (§4.1)—well within the ≈ 2.1-solve spread across seed draws, because evolutionary search adds +9.2 solves to the DSL arm compared to +6.1 for free-form code. The mechanism is structural: AST mutation and recombination operate over the DSL’s typed primitives, making DSL programs more amenable to evolutionary editing, whereas unconstrained Python better matches the language model’s pretraining distribution.

While DSL code is consistently lower than free-form code under pure sampling (15 of 15 cells), under evolution the style difference is smaller than the seed-draw variance: −3.3, +1.5, and +6.2 solves across the three draws at B=16B=16, and −2.8-2.8, +4.5+4.5, and +2.5+2.5 at B=8B=8. As noted in § 2, the DSL is not what makes an artifact verifiable: an unconstrained Python solve function is tested against the demonstrations in exactly the same manner. Rather, the DSL governs how effectively search can manipulate the artifact and how readily a human reader can audit the allowed primitives.

The in-loop budget: what spending more calls during the search buys

Section 3.3 evaluated evolutionary search over at most two seed programs at zero additional API cost. This appendix examines the effect of spending additional model calls inside the evolutionary loop across B∈{4,8,16}B \in\{4, 8, 16\}.

The evolved arm’s call budget serves two distinct roles: up to two calls purchase initial seed programs, whereas calls above B=2B=2 fund in-loop LLM mutations during search. Table 2 evaluates the second role by comparing each evolved cell against the explainable arm interpolated to the same realized call spend.

No individual B≥4B \ge4 row exceeds the 1.8–4.2-solve seed-draw spread. Across the column, the evolved arm’s advantage over pure sampling is largest at B≤2B \le2, where zero in-loop calls are made (+9.89 ±\pm 1.26 and +7.56 ±\pm 1.21 at B=1B=1; +9.22 ±\pm 1.40 and +6.11 ±\pm 1.03 at B=2B=2, paired on draws 1–3; against the unpaired k=16k=16 sampling draws 1, 2, 4, the corresponding differences are +13.5, +8.6, +11.1, and +6.2), and diminishes as in-loop calls are added (+4.3 →\to +4.0 →\to +3.8 for DSL and +4.1 →\to +0.0 →\to +0.8 for free-form code).

We do not attach paired zz-scores to the B≥4B \ge4 rows because, unlike at B≤2B \le2 (where both arms read the exact same one or two samples of draws 1–3), the evolved arm’s realized spend at B≥4B \ge4 is a random variable determined by early stopping and falls between the discrete budgets of the k=16k=16 sampling curve (draws 1, 2, 4). We therefore report the pooled log⁡2\log_2-interpolated comparison alongside the measured between-draw spread.

Variance decomposition: provider non-determinism and seed draws

Cross-run comparisons in this study are governed by two sources of variance beyond within-run evolutionary stochasticity, and we measured both directly. First, to isolate in-loop LLM provider non-determinism, we executed eight runs of a single cell (dsl, B=8B=8) holding both the initial seed cache and the evolutionary random seed fixed across all 120 tasks:

67.8, 66.3, 66.8, 63.8, 67.8, 68.3, 66.8, 63.3  mean 66.40, sd 1.86 (df = 7).

Twenty-three of the 120 tasks yielded different scores across runs despite an identical search seed and identical initial samples, reflecting non-determinism in the provider’s in-loop responses. Decomposed against the ≈0.9\approx0.9-solve within-run replica standard error, the shared run-level offset is 1.63 solves, which does not average down across within-run replicas; a three-replica cell therefore carries SE = 1.71 solves (and on strict credit the same eight runs score 63, 61, 61, 60, 63, 64, 62, 58, with sd 1.93).

Seed-draw variance and why low-budget comparisons are paired. Because the eight runs above shared a frozen seed cache, their 1.86-solve spread captures only in-loop response variance and omits the variance of the initial seed draw itself. Re-running the B=2B=2 evolved arm across three independent seed draws quantifies that initial-seed component: the between-draw standard deviation is 2.24 solves (dsl) and 2.02 (no_dsl), compared to 0.19 across four repetitions on a single frozen draw—so the error bar from a frozen draw was an order of magnitude too small (the first of the three re-runs reproduced the original 59.33 solves across all 120×3120 \times3 task-replica cells identically, confirming zero code drift). Because the seed-draw offset is shared across replicas of a given draw, we pair the B≤2B \le2 comparisons in §3.3 draw-for-draw on the identical seed caches, canceling the between-draw variance rather than inflating the error bar.

Protocol and cost details

Explainable curves are nested prefixes. Each prompt style uses ordered k=16k=16 sample caches that record every model completion in generation order, including syntax or runtime failures. Best-of-BB at every budget BB is evaluated on the prefix of the first BB samples of that cache, pairing the sampling curves with the evolved arm’s initial seeds at zero extra API cost and allowing offline replay under alternative selection or stopping rules.

Calls and tokens. Model calls are the primary protocol variable; token counts are reported as a second curve and never merged with calls into a single unit, as divergence between the two is itself informative. On the evaluation split under gemini-3.5-flash, seeding calls average 38.2k tokens (dsl) and 32.5k (no_dsl), and in-loop calls average ≈22\approx22k tokens. Calls on the evaluation split cost 1.7–2×2\times what training-split calls cost, so any cost basis taken from a training-split pilot must be scaled before it is applied.

Wall-clock deadline. Evolutionary search is bounded by a fixed 900 s wall-clock deadline per task.

Total compute across arms. Although calls are the protocol variable, the arms differ in what a call returns and in the CPU work performed between calls. Under gemini-3.5-flash, client logs recorded the explainable arm’s token usage above but did not log token counts for the answer-only arm. Under gemini-3.8-flash (App. H), provider-side telemetry on the days each arm ran in isolation records 26.7k tokens per successful call for the answer-only arm (4.9k input, 21.8k output across 4,007 calls) versus 29.3k for the explainable arm (6.1k input, 23.2k output across 5,773 calls): internal reasoning tokens dominate both responses, and a model call consumes within 10% the same total tokens whether it emits grids or code, so calls are a fair unit across arms at a fixed model. Between calls, the evolved arm expends CPU time evaluating candidate programs; Table 3 reports the search wall time per cell, net of in-loop model latency.

cellmean smedian sp90 sevaluationscalls/task
B=1B=1132224343,8821.01
B=2B=210073183,2511.99
B=4B=410243692,5213.38
B=8B=89333472,0555.16
B=16B=167332531,7568.09

Table 3. Search wall time per (task, replica) cell of the evolved arm, DSL prompt, three seed draws, net of in-loop model latency; the deadline is 900 s. Evaluations are candidate programs scored per cell.

The explainable arm given the stopping rule

Because any candidate program can be executed against the training pairs, a sequential sampling baseline can apply the same early-stopping criterion as the evolved arm. We evaluate the explainable arm under this rule offline using the ordered k=16k=16 sample caches: samples are drawn in generation order (counting failed samples toward the call budget) until a stopping criterion is met, and the held candidates are submitted via the shared rule of § 2. Stop at two halts once two train-perfect programs with distinct test predictions are held (matching the evolved arm’s stage (ii)); stop at one halts at the first train-perfect program. Whenever the stopping criterion does not trigger before budget BB is exhausted, the submission is identical to fixed best-of-BB. Table 4 reports both stopping rules alongside the evolved arm and an ablation in which attempt 2 is selected fitness-free (the earliest sample whose test prediction differs from attempt 1’s), which bounds the contribution of train-score ranking above B=2B=2 (at B=2B=2 the two rules coincide).

BBX, fixed solvesX, fixed fitness-freeX, stop at two solvesX, stop at two r/BX, stop at one solvesX, stop at one r/BE solvesE r/B
247.347.347.31.0044.00.7458.41.00
459.358.657.40.9049.80.5460.70.85
863.160.362.60.7753.50.3864.70.64
1666.362.266.30.6256.00.2766.90.51

Table 4. The explainable arm with and without the stopping rule, DSL prompt, leaderboard E[solves]E[\mathrm{solves}] over three seed draws (draws 1, 2 and 4 for the explainable columns, the three sixteen-sample caches; draws 1–3 for the evolved arm, which is why best-of-2 reads 47.3 here and 49.2 in Table 2); “r/B” is realized calls over permitted budget. The evolved arm’s row is the three-draw replication of Table 2. Under the free-form prompt, stop-at-two similarly achieves 62.8, 66.9, and 69.1 solves at r/B 0.88, 0.74, and 0.59 for B=4,8,16B=4, 8, 16.

Three conclusions follow from Table 4. First, sequential sampling with the stop-at-two rule loses no accuracy at B=16B=16 and at most 1.9 solves at B=4B=4 while declining 10–38% of its budget; the evolved arm declines a larger fraction at every budget while scoring at or above the sampler, showing that early termination is a property of the verifiable artifact and the additional saving comes from evolutionary search finding a second explanation without further model calls. Second, stopping at the first explanation declines 73% of the budget at B=16B=16 but loses 10.3 solves (56.0 vs. 66.3), confirming that the first train-perfect program frequently overfits the demonstrations (§ 3.5). Third, ranking attempt 2 by train score contributes 0.7, 2.8, and 4.1 solves to the explainable arm at B=4,8,16B=4, 8, 16 relative to a fitness-free second attempt, and zero at B=2B=2, confirming that the paired B≤2B \le2 margins in § 3.3 are unaffected by candidate ranking.

Which tasks each arm solves

Table 5 summarizes structural properties of the four solved-task subsets of Table 1, together with the number of tasks in each subset for which at least one program arm found a train-perfect program (pooled across the explainable arm’s three k=16k=16 draws and the evolved arm’s nine B=2B=2 runs, a wider pool than the single-arm count of 106 in § 3.5). Because the subsets are small, we report descriptive medians and proportions rather than hypothesis tests. Two patterns stand out: tasks solved only by A0 more frequently involve multiple test inputs (54% vs. 26%) and larger input grids (median 456 vs. 316 cells) than tasks solved by both modalities; and a train-perfect program existed for 27 of the 28 A0-only tasks, so on these tasks the DSL could express a program consistent with the demonstrations; what was missing was one that generalized to the test input (§ 3.5).

setnnexplained>1>1 test inputgrid sideinput cellssize changecolors
A0 only282754%3045632%9
explanation only7743%2531029%9
both656326%2431634%8
neither201350%2727430%8

Table 5. Table 1’s four solved-task subsets by task property (medians unless stated); “explained” counts tasks for which at least one program arm held a train-perfect program.

A second model

We replicated the answer-only, explainable, and B=2B=2 evolved arms on gemini-3.8-flash across three seed draws (k=8k=8 caches, both prompt styles, with the evolved arm seeded from the first two samples of each cache). Paired on the seed draw, the evolved arm outperforms best-of-2 sampling by +8.22 ± 0.24 (DSL) and +5.50 ± 0.42 (free-form) solves, reproducing the conversion margins of §3.3 with the DSL again gaining more from evolutionary search than free-form code. Across k=1,2,4,8k = 1, 2, 4, 8 samples per test input, the answer-only arm scores 94.9, 104.1, 107.7, and 110.2 of 120, compared to 55.3, 61.3, 69.5, and 73.0 for free-form sampling and 47.2, 55.4, 60.0, and 67.0 for DSL sampling; thus, the gap between direct grid prediction and program synthesis widens on the stronger model. Whether pretraining exposure to the public evaluation split contributes to either model’s performance cannot be separated by this experimental design.

QEC domain details

This appendix describes the apparatus of §3.6—the code, the DSL, the panel and the cost model—and gives the detailed readings behind that section. The full adjudication and novelty audit appear in the companion paper [16].

Code and noise model. The target is the [[72,12,6]][[72, 12, 6]] bivariate-bicycle qLDPC code [8] under circuit-level noise—not code-capacity or phenomenological noise—at a single rate p=0.004p = 0.004 on five channels: two-qubit depolarizing after each CNOT, single-qubit depolarizing on idling qubits, a flip on every reset, a flip on every ancilla measurement, and a flip on the final data measurement, over six rounds of syndrome extraction in the ZZ basis. Decoding runs on the detector error model (DEM) that circuit compiles to: 432 detectors and 12 observables per shot, over roughly 1.6×1041.6 \times10^{4} fault mechanisms (16,164 in the instance we measured; the DEM’s structure is set by the circuit, so only the probabilities move with pp). Under circuit-level noise, the DEM’s columns represent correlated fault mechanisms rather than independent qubit errors, which is precisely the regime where belief propagation alone stalls on degenerate codes and where the post-processing family spanned by the DSL exists.

Shots are generated once, with the splits written by the generator rather than carved out by any consumer: 600,000 train / 200,000 validation / 200,000 exam. Finalists are frozen before the exam split is read, so no selection decision ever sees the shots it is judged on, and each evaluated algorithm reads the exam split once. The physical error rate is an axis rather than a constant—the datasets span p∈{0.001,0.002,0.003,0.004}p \in\{0.001, 0.002, 0.003, 0.004\}—and the campaigns reported here evolve at p=0.004p = 0.004: at lower error rates plain belief propagation decodes nearly every shot, leaving too few post-processor-decided shots to resolve differences across candidates at an affordable sample size.

The DSL: 38 operations in eight groups. The evolved program is solve(state) → state, called once per shot. There is no step-function driver: ensembles, decimation loops, and retry rounds are ordinary for and if statements inside the evolved program, so evolutionary search operates directly on control flow rather than on a fixed parameter vector. The vocabulary is the published decoder family’s component catalog, grouped as: prepare (9—LLR initialization and scaling, DEM sparsification, relabeling, column masking, syndrome-conditioned priors, alternative check bases, check inactivation, degeneracy cutting), engine (5—the BP kernel, its convergence predicate, posterior reseeding, oscillation ranking, candidate validity), ranking (5), clusters (7—seeding, growth, syndrome-guided reduction, marked-row reduction, block enrichment, validity, forest construction), solvers (3), local search (2), control (5—candidate admission, selection, and a branch/advance/prune frontier), and assembly (2).

An operation is admitted when it is a component of a published BP post-processor and runs inside a per-shot budget that the operation itself enforces (2 000 BP sweeps, 256 operation calls, 10 100 candidate corrections, and 982 256 GF(2) column operations per shot, with a 60× mean work cap per evaluation). Two exclusions bound what the search could find. Four prepare operations are artifact-gated: they index into a per-code table built offline (permutations, GF(2) row operations, piece-to-parent maps, degeneracy generators), and on a dataset shipped without that table they act as documented no-ops rather than raising errors. Additionally, one catalog entry, an LP-relaxation soft engine, is deliberately omitted: the parity polytope requires exponentially many forbidden-set inequalities per check, added lazily over repeated solves, across 432 checks that must be decoded within a per-shot budget where an entire BP run costs ∼1\sim1 ms. That is a cost judgment, not an oversight, and it is the one place the vocabulary is narrower than the literature it spans.

The panel, and how it is certified. Published decoders are implemented by hand in the same DSL, in both callable and source form, so a baseline is a program in the same language as a candidate and not a different kind of object: plain BP (P1); BP+OSD-0 at ldpc’s tuned point (30 serial product-sum sweeps, P2) and with a damped flooding min-sum front end (10 sweeps, α=0.625\alpha= 0.625, γ=0.3\gamma= 0.3, P2-d, the cost reference); BP+OSD-CS at order 60 (30 serial product-sum sweeps, P3, and damped, P3-d); BPGD (P4); Relay-BP (P5); BP+SI (P6); the LSD cluster decoders at order 0 and order μ\mu (P7, P8); ordered Tanner forests (P9); ambiguity clustering (BP+AC, 45 parallel product-sum sweeps, γ=0.3\gamma= 0.3, κ=0.1\kappa= 0.1, P10); beam search (P11); degeneracy cutting (P12); and check-agnosia (P13, structurally void here). Where the authors’ own implementation exists the member is certified against it per shot, which is stricter than comparing error rates: BP, BP+OSD-0, BP+OSD-CS and BP+LSD against ldpc (same fault vector on every jointly-converged shot), and Relay-BP against the authors’ relay-bp package (marginals to 10−610^{-6}, hard decisions shot for shot). Ambiguity clustering has no public implementation and is certified shot for shot (16,384/16,384 shots across four settings and two noise rates) against an independent re-implementation of its published stages.

The cost model: a deterministic proxy and wall-clock verification. Raw wall-clock time is noisy inside a shared compute fleet: on one-vCPU actors sharing a physical core, a worker’s reference calibration drifted by 51% (95th percentile) with a 30% re-run flag rate. Selection therefore needs a deterministic cost model whose units cost the same wherever they are spent, and whose counters see every cost: a proxy over coarse operation counts prices interpreter overhead and conflates operations of very different cost (min-sum vs. product-sum BP edges, dense vs. sparse OSD trial evaluations, and data-dependent comparison sorts whose branch-prediction cost varies 4×4\times across key distributions). The proxy was therefore built on a native implementation of the DSL in Rust in two steps. First, operations whose runtime depended on data values no counter can observe were made data-blind while preserving predictions bit-for-bit: adaptive comparison sorts on posteriors were replaced by a four-lane interleaved stable LSD radix argsort, flip-count sorting by a four-lane counting sort, and repeated cluster-frontier B-tree lookups (which crossed L1 cache past ∼\sim2,000 entries) by a front-end bitset. Second, work was instrumented at the primitive level across seven deterministic counters: min-sum BP edge updates (weight 1.00), product-sum BP edge updates (1.91, reflecting the 0.52 cost ratio), 64-bit GF(2) elimination words (0.28), candidate-enumeration solution words (2.25), and ranking/scan elements (0.30), plus DSL operation calls (0.00) and AST interpreter ticks (0.00) recorded as observers. Fitted by non-negative least squares (weighted by 1/measured time1/\sqrt{\text{measured time}}) across 252 programs (79 operation ladders, 23 panel members and variants, and 150 generator programs with 45 held out) on Intel Xeon Platinum 8581C nodes, the proxy achieves R2=0.998R^2 = 0.998, an in-sample 95th-percentile relative error of 11.8% (21.2% held out), a widest bootstrap weight-cone half-width of 22.3%, and a 1.4×\times resolution arm (over a 1.31×\times floor, in units of P2-d’s 1292.58 weighted units per shot). Crucially for evolutionary selection, which depends on cost ordering, the frozen proxy’s rank correlation with measured wall-clock time across the 252 programs is Kendall τ=0.973\tau= 0.973 (Spearman 0.998) on the fitting nodes and τ=0.935\tau= 0.935 (Spearman 0.992) on the Apple M3 Ultra benchmark workstation—picking the same cheapest program as wall-clock time in 98.0% of size-3 tournaments, with only 0.01% of pairs separated by more than the 1.4×\times margin ordered differently. We also ran a calibrated wall-clock search arm reserving 2 vCPUs (one physical core) per actor and re-calibrating against P2-d every 500 evaluations, which reduced calibration drift to a median of 0.9 % (0 % flag rate). Every adjudicated cost verdict is required to hold on both rulers—the frozen work proxy and pinned-core wall-clock time—and on all timed finalists the two agree within 1.01–1.26×\times with zero proxy verdicts refused (Table 6).

Two exam splits. Results are reported on two exam splits of 200,000 shots each, A and B (s20260904 and s20261004 in the companion paper [16]). The time–error front below was read on A; the adjudication of Table 6, the hybrid arm and the AlphaEvolve rows were read on B. A decoder’s error rate differs slightly between the two (C03 reads 4.18% on A and 4.17% on B), so every number names its split and no comparison mixes them.

The time–error front on split A. The damped reference P2-d reads 5.45% LER at 8.82 ms per shot. The evolved C03 (seeded from the panel, no language model) reads 4.18% at 5.66 ms (0.64× the reference’s time, 23% fewer errors, z=+31.8z = +31.8); C04 and C10, evolved from random code, read 4.14% and 4.07%. Faithfully implemented ambiguity clustering (BP+AC, P10) reads 3.57% at 31.8 ms; the authors’ Relay-BP reads 3.17% at 190.0 ms (stop 5) and 2.80% at 270.6 ms (stop 9); the ldpc package’s BP+OSD-0 at its tuned point reads 4.39% at 903.8 ms. The time–error front over these rows has seven decoders: four evolved at the fast end, BP+AC and the two Relay-BP points at the accurate end. Relay-BP is the most accurate decoder among these rows, at 21.6–30.7× the reference’s time.

Inspecting a baseline in the DSL: the belief-propagation stage of BP+OSD. Writing BP+OSD-0 in the DSL exposed a message-damping parameter that the ldpc package does not export. The parameter matters because the cheap front end is unusable without it: on validation shots, undamped flooding min-sum reads 47.66% LER (512 shots) against 5.15% damped (4 096 shots) at 1.04× the belief-propagation work, and ldpc given the same undamped settings fails in the same way (47.4% on 1 206 shots). The package’s tuned point avoids the failure with a serial product-sum schedule, which is more accurate and much more expensive. Within our engine, on split B (200 000 shots), replacing the tuned front end by the damped one makes BP+OSD-0 41.0× faster at 1.27× the errors (z=+25.8z = +25.8 in favor of the tuned point) and BP+OSD-CS 17.1× faster at 1.10× the errors (z=+9.2z = +9.2). This is a speed–accuracy trade that a readable baseline makes visible, not a defect in the package: its tuned points remain the more accurate. The comparison of the package itself with our damped reference on split A (903.8 ms against 8.82 ms) additionally contains the difference between ldpc’s C++ and our Rust engine, and the two were timed on different workstations of the same model.

The hybrid arm and the AlphaEvolve arms on split B. Five runs of the hybrid arm (352 founding model calls per run, then p=0.001p = 0.001 per birth) produced E083: 3.17% LER (6 347 errors in 200,000 exam shots) at 36.2 ms per shot, more accurate than the damped reference (z=+53.8z = +53.8) and our BP+AC port (z=+7.5z = +7.5), less accurate than Relay-BP (z=−8.8z = -8.8 against our port at stop 9; −9.8-9.8 against the authors’ package), at 3.9× the reference’s cost (Table 6, Figure 4). Its nearest panel member is BP+AC at call-multiset distance 2, passing the structural novelty bar by replacing BP+AC’s per-cluster block-vote search with global OSD-CS enumeration followed by logical-class voting. Matched by seed, the hybrid arm beat random founders 5 of 5 and expert-panel seeds 0 of 5. AlphaEvolve [34] given the same DSL generated 5,144 programs (167M tokens); its champion AE-DSL reads 1.26% LER at 52.9 ms and is outperformed by E083 on the same shots (z=+28.7z = +28.7) at 0.69× its time. AlphaEvolve writing free-form Python synthesised an exact F₂ solver, AE-Free, which reads 1.95% LER (3 904 errors) at 168 ms per shot: the most accurate row we measured on this split, ahead of the authors’ Relay-BP at stop 9 (2.82%, 5 635 errors, 270.6 ms), outside the fast real-time regime. The timings of the package rows, of E083 and of the AlphaEvolve rows come from separate sessions on the benchmark workstation.

Exam-split comparison and discovered programs. Table 6 reports the exam-split accuracy and cost across both rulers on the 200 000 held-out shots of split B, alongside the clean workstation timings, and Figure 4 prints the pruned DSL source of the hybrid champion E083 and the fast-front champion C03.

Training-shot stratification. A shot is one sample of the syndrome-extraction circuit’s noisy measurement record together with the true logical outcome; decoding it yields a correction that is either logically correct or erroneous. At p=0.004p = 0.004, most shots are decoded correctly by plain belief propagation and by every candidate, so a uniform training draw spends most of its evaluation budget on shots that do not separate competing post-processors. The campaigns reported in § 3.6 therefore draw training shots using a two-stratum, importance-weighted sampler that over-samples the stratum where plain BP fails—the shots on which the post-processing stages decide the outcome—while weighting each stratum by its population share so that the estimated logical error rate remains unbiased. Because the stratum boundary is defined by plain BP (a fixed panel member) on the training split alone, it is independent of the candidate being evaluated. Conversely, stratifying on *shots where

def solve_e083(state):  # Hybrid (LLM + evolution): 3.17% LER (split B), 36.2 ms/shot
    state = run_bp(state, 18, BpRule.PRODUCT_SUM, 1.0, 0.0, Schedule.PARALLEL, 0.625)
    state = reduce_marked_rows(state, True)
    state = enrich_blocks(state, 0.04, True)
    state = enumerate_patterns(state, 1, 16, Scope.OSD_CS)
    return vote_logicaL_classes(state)


def solve_c03(state):    # Fast-front, seeded: 4.17% LER (split B), 5.66 ms/shot
    state = run_bp(state, 9, BpRule.MIN_SUM, 0.7710, 0.0031, Schedule.PARALLEL, 0.3107)
    state = reduce_marked_rows(state, True)
    state = enrich_blocks(state, 0.0412, True)
    return enumerate_patterns(state, 1, 4000, Scope.BLOCK_VOTE)

the reference decoder BP+OSD-0 fails rewards candidates for exploiting the reference’s specific failure modes and inverted pairwise decoder rankings on nine of ten benchmarked pairs; that stratum is therefore excluded. Every exam result is evaluated on an unweighted, uniform draw of the exam split.

References

  1. [1]Pranjal Aggarwal, Aman Madaan, Yiming Yang, and Mausam. Let’s sample step by step: Adaptive-consistency for efficient reasoning and coding with LLMs. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 12375–12396, Singapore, 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023.emnlp-main.761.DOI
  2. [3]Shraddha Barke, Emmanuel Anaya Gonzalez, Saketh Ram Kasibatla, Taylor Berg-Kirkpatrick, and Nadia Polikarpova. HySynth: Context-free LLM approximation for guiding program synthesis. In Advances in Neural Information Processing Systems, volume 37, 2024.arxiv.org/abs/2405.15880
  3. [4]Abeba Birhane, Atoosa Kasirzadeh, David Leslie, and Sandra Wachter. Science in the age of large language models. Nature Reviews Physics, 5(5):277–280, 2023.DOI
  4. [5]John Blue, Harshil Avlani, Zhiyang He, Liu Ziyin, and Isaac L. Chuang. Machine learning decoding of circuit-level noise for bivariate bicycle codes. Quantum, 2026. arXiv:2504.13043.DOI
  5. [6]Daniil A Boiko, Robert MacKnight, Ben Kline, and Gabe Gomes. Autonomous chemical research with large language models. Nature, 624(7992):570–578, 2023.DOI
  6. [7]David Brandfonbrener, Simon Henniger, Sibi Raja, Tarun Prasad, Chloe Loughridge, Federico Cassano, Sabrina Ruixin Hu, Jianang Yang, William E Byrd, Robert Zinkov, et al. VerMCTS: Synthesizing multi-step programs using a verifier, a large language model, and tree search. arXiv preprint arXiv:2402.08147, 2024.arxiv.org/abs/2402.08147
  7. [8]Sergey Bravyi, Andrew W. Cross, Jay M. Gambetta, Dmitri Maslov, Patrick Rall, and Theodore J. Yoder. High-threshold and low-overhead fault-tolerant quantum memory. Nature, 627:778–782, 2024.DOI
  8. [9]Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787, 2024.arxiv.org/abs/2407.21787
  9. [10]Alexander E. I. Brownlee, James Callan, Karine Even-Mendoza, Alina Geiger, Carol Hanna, Justyna Petke, Federica Sarro, and Dominik Sobania. Enhancing genetic improvement mutations using large language models. In Search-Based Software Engineering (SBSE 2023), volume 14415 of Lecture Notes in Computer Science, pages 153–159. Springer, 2023.DOI
  10. [11]François Chollet. On the measure of intelligence. arXiv preprint arXiv:1911.01547, 2019.arxiv.org/abs/1911.01547
  11. [12]François Chollet, Mike Knoop, Gregory Kamradt, and Bryan Landers. ARC Prize 2024: Technical report. arXiv preprint arXiv:2412.04604, 2024.arxiv.org/abs/2412.04604
  12. [13]François Chollet, Mike Knoop, Gregory Kamradt, Bryan Landers, and Henry Pinkard. ARC-AGI-2: A new challenge for frontier AI reasoning systems. arXiv preprint arXiv:2505.11831, 2025.arxiv.org/abs/2505.11831
  13. [14]François Chollet, Mike Knoop, Gregory Kamradt, and Bryan Landers. ARC Prize 2025: Technical report. arXiv preprint arXiv:2601.10904, 2026.arxiv.org/abs/2601.10904
  14. [15]Yoni Choukroun and Lior Wolf. Deep quantum error correction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 64–72, 2024.
  15. [16]Eduardo Dueñez, Edgar Said Hernandez Sanchez, Edgar A Dueñez-Guzmán, and Suzanne Sadedin. Evolving decoding algorithms for quantum error correction. In EvoRobust: Self-Evolving Diversity-Driven Search for Robust AI Systems (NeurIPS 2026 Workshop), 2026.arxiv.org/abs/2611.25880
  16. [17]Benedikt Fecher, Marcel Hebing, Melissa Laufer, Jörg Pohle, and Fabian Sofsky. Friend or foe? Exploring the implications of large language models on the science system. AI & Society, 40(2):447–459, 2025.
  17. [18]Emily First, Markus N Rabe, Talia Ringer, and Yuriy Brun. Baldur: Whole-proof generation and repair with large language models. In Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 1229–1241, 2023.arxiv.org/abs/2303.04910
  18. [19]Yolanda Gil, Mark Greaves, James Hendler, and Haym Hirsh. Amplify scientific discovery with artificial intelligence. Science, 346(6206):171–172, 2014.DOI
  19. [20]Daniel Gottesman. Stabilizer codes and quantum error correction. California Institute of Technology, 1997.
  20. [22]Michael Hodel. Addressing the Abstraction and Reasoning Corpus via procedural example generation. arXiv preprint arXiv:2404.07353, 2024.arxiv.org/abs/2404.07353
  21. [23]Thomas Hubert, Rishi Mehta, Laurent Sartran, Miklós Z Horváth, Goran Žužić, Eric Wieser, Aja Huang, Julian Schrittwieser, Yannick Schroeker, Hussain Masoom, et al. Olympiad-level formal mathematical reasoning with reinforcement learning. Nature, 651(8106):607–613, 2026.DOI
  22. [24]Lefteris Lazaropoulos and Zoe Paraskevopoulou. Foundational refinement proofs for deployed bytecode, at the price of tokens. arXiv preprint arXiv:2607.26306, 2026.
  23. [25]Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, and Kenneth O. Stanley. Evolution through large models. In Wolfgang Banzhaf, Penousal Machado, and Mengjie Zhang, editors, Handbook of Evolutionary Machine Learning, Genetic and Evolutionary Computation, pages 331–366. Springer, Singapore, 2024.arxiv.org/abs/2206.08896
  24. [26]Wen-Ding Li, Keya Hu, Carter Larsen, Yuqing Wu, Simon Alford, Caleb Woo, Spencer M. Dunn, Hao Tang, Wei-Long Zheng, Yewen Pu, and Kevin Ellis. Combining induction and transduction for abstract reasoning. In International Conference on Learning Representations, 2025.arxiv.org/abs/2411.02272
  25. [27]Zenan Li, Ziran Yang, Peiyang Song, Zhaoyu Li, and Kaiyu Yang. P³: Joint program-and-proof planning for verified code generation. arXiv preprint arXiv:2608.09277, 2026.arxiv.org/abs/2608.09277
  26. [28]Jacky Liang, Wenlong Huang, Fei Xia, Peng Xu, Karol Hausman, Brian Ichter, Pete Florence, and Andy Zeng. Code as policies: Language model programs for embodied control. In 2023 IEEE International conference on robotics and automation (ICRA), pages 9493–9500. IEEE, 2023.arxiv.org/abs/2209.07753
  27. [29]Ye-Hua Liu and David Poulin. Neural belief-propagation decoders for quantum error-correcting codes. Physical Review Letters, 122(20):200501, 2019.DOI
  28. [30]Zejun Liu, Anqi Gong, and Bryan K. Clark. Decoding quantum low density parity check codes with diffusion. arXiv preprint arXiv:2509.22347, 2025.arxiv.org/abs/2509.22347
  29. [31]Elliot Meyerson, Mark J. Nelson, Herbie Bradley, Adam Gaier, Arash Moradi, Amy K. Hoover, and Joel Lehman. Language model crossover: Variation through few-shot prompting. ACM Transactions on Evolutionary Learning and Optimization, 4(4):27:1–27:40, 2024.DOI
  30. [32]Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909, 2015.DOI
  31. [33]Sina Bagheri Nezhad, Yao Li, and Ameeta Agrawal. SymCode: A neurosymbolic approach to mathematical reasoning via verifiable code generation. In Findings of the Association for Computational Linguistics: EACL 2026, pages 1489–1503, 2026.
  32. [34]Alexander Novikov, Ngân Vũ, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco JR Ruiz, Abbas Mehrabian, et al. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131, 2025.arxiv.org/abs/2506.13131
  33. [35]Michael O’Neill and Conor Ryan. Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language, volume 4 of Genetic Programming Series. Springer US, Boston, MA, 2003. ISBN 978-1-4613-5077-9. doi: 10.1007/978-1-4615-0447-4. URL https://doi.org/10.1007/978-1-4615-0447-4.
  34. [36]Pavel Panteleev and Gleb Kalachev. Degenerate quantum LDPC codes with good finite length performance. Quantum, 5:585, 2021.DOI
  35. [37]Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA, 1988.
  36. [38]Valentin Rodionov and Shamil Assylbekov. TRACES: A benchmark for epistemic reliability in scientific reasoning by LLMs. arXiv preprint arXiv:2608.11415, 2026.arxiv.org/abs/2608.11415
  37. [39]J oschka Roffe, David R. White, Simon Burton, and Earl Campbell. Decoding across the quantum low-density parity-check code landscape. Physical Review Research, 2(4):043423, 2020.DOI
  38. [40]Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. Mathematical discoveries from program search with large language models. Nature, 625:468–475, 2024.
  39. [41]Emrullah Şahin, Naciye Nur Arslan, and Durmuş Özdemir. Unlocking the black box: an in-depth review on interpretability, explainability, and reliability in deep learning. Neural Computing and Applications, 37:859–965, 2025.DOI
  40. [42]Adi Simhi, Itay Itzhak, Fazl Barez, Gabriel Stanovsky, and Yonatan Belinkov. Trust me, I’m wrong: LLMs hallucinate with certainty despite knowing the answer. In EMNLP (Findings), pages 14665–14688, 2025.arxiv.org/abs/2502.12964
  41. [43]Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aniral Kumar. Scaling LLM test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024.arxiv.org/abs/2408.03314
  42. [44]Maciej Świechowski, Konrad Godlewski, Bartosz Sawicki, and Jacek Mańdziuk. Monte Carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, 56(3):2497–2562, 2023.DOI
  43. [45]Ross Taylor, Marcin Kardas, Guillem Cucurull, Thomas Scialom, Anthony Hartshorn, Elvis Saravia, Andrew Poulton, Viktor Kerkez, and Robert Stojnic. Galactica: A large language model for science. arXiv preprint arXiv:2211.09085, 2022.arxiv.org/abs/2211.09085
  44. [46]Hanchen Wang, Tianfan Fu, Yuanqi Du, Wenhao Gao, Kexin Huang, Ziming Liu, Payal Chandak, Shengchao Liu, Peter Van K latwyk, Andreea Deac, et al. Scientific discovery in the age of artificial intelligence. Nature, 620(7972):47–60, 2023a.DOI
  45. [47]Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah D. Goodman. Hypothesis search: Inductive reasoning with language models. In International Conference on Learning Representations, 2024.arxiv.org/abs/2309.05660
  46. [48]Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In International Conference on Learning Representations (ICLR), 2023b.arxiv.org/abs/2203.11171
  47. [49]Huaiyuan Ying, Shuo Zhang, Linyang Li, Zhejian Zhou, Yunfan Shao, Zhaoye Fei, Yichuan Ma, Jiawei Hong, Kuikun Liu, Ziyi Wang, et al. InternLM-Math: Open math large language models toward verifiable reasoning. arXiv preprint arXiv:2402.06332, 2024.arxiv.org/abs/2402.06332

Paper details

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

views · 2

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents