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 120-task ARC-AGI-2 evaluation set. Demanding a verifiable artifact from an LLM reduced the score from 93 to 68 of 120 tasks (77% to 57%). Of those 25 tasks, 21 were reached by no program-producing configuration we ran, at any budget, by sampling or by search; yet for 27 of the 28 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-2 sampled code by 9.2±1.4 tasks, and over a single sampled program beats 1-shot sampling by 9.9±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-n sampling declines up to 38% of its budget and the evolved arm up to 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.
Figures & tables
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.
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 explanation
7
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.
Figure 2: Solves against realized spend. The answer-only arm (orange stars) predicts outputs directly. Solutions cost 1.39×k per task, because each test input requires a separate LLM call. The explainable arm (navy circles) is shown at fixed best-of- n program sampling (Figure 3 and Table 4 also give it the stopping rule). The evolved arm (cyan diamonds) has an LLM call budget B 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).
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 k , has no checked signal on which to stop. The two arms’ solves at these points are within 0.6 of each other at B=16 ( 66.3 against 66.9 ) and within the seed-draw spread everywhere (Table 4 ).
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
cell
spend
evolved
explainable
Δ
B=1 , dsl
1
51.7
41.8
+9.9
B=1 , no_dsl
1
53.0
45.4
+7.6
B=2 , dsl
2
58.4
49.2
+9.2
B=2 , no_dsl
2
60.3
54.2
+6.1
B=4 , dsl
3.38
60.7
56.4
+4.3
B=8 , dsl
5.16
64.7
60.7
+4.0
Appendix
Table 2: Comparison of the evolved (E) and explainable (X) arms at matched realized spend . At B≤2 the evolved arm spends calls only on seeds (one at B=1 , two at B=2 ) plus syntactic search, paired draw-for-draw on draws 1 – 3 (§ 3.3 ); at B≥4 , remaining budget funds in-loop model calls and the explainable column interpolates the k=16 sampling curve (draws 1,2,4 ) in log2 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≤2 , where no in-loop calls are made.
cell
mean s
median s
p90 s
evaluations
calls/task
B=1
132
22
434
3,882
1.01
B=2
100
7
318
3,251
1.99
B=4
102
4
369
2,521
3.38
B=8
93
3
347
2,055
5.16
B=16
73
3
253
1,756
8.09
Appendix
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.
X, fixed
X, stop at two
X, stop at one
E
B
solves
fitness-free
solves
r/B
solves
r/B
solves
r/B
2
47.3
47.3
47.3
1.00
44.0
0.74
58.4
1.00
4
59.3
58.6
57.4
0.90
49.8
0.54
60.7
0.85
8
63.1
60.3
62.6
0.77
53.5
0.38
64.7
0.64
16
66.3
62.2
66.3
0.62
56.0
0.27
66.9
0.51
Appendix
Table 4: The explainable arm with and without the stopping rule, DSL prompt, leaderboard E[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,16 .
set
n
explained
>1 test input
grid side
input cells
size change
colors
A0 only
28
27
54%
30
456
32%
9
explanation only
7
7
43%
25
310
29%
9
both
65
63
26%
24
316
34%
8
neither
20
13
50%
27
274
30%
8
Appendix
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.
decoder
arm / ruler
LER %
proxy × P2-d
time × P2-d
ms/shot
z vs P2-d
z vs P10
note
E083
hybrid (LLM in loop)
3.17
3.88
3.48
36.2
+53.8
+7.5
primary; novel (P10 at 2)
C14
seeded, work proxy
3.21
2.4
2.145
—
+54.7
+9.4
primary; retuning of BP+AC (P10 at 0)
C10
unseeded, wall-clock
4.04
2.7
2.389
29.0
+35.9
−22.0
primary (from scratch)
C04
unseeded, work proxy
4.07
2.0
1.882
20.6
+35.8
−20.6
primary (from scratch)
C08
seeded, wall-clock
4.16
0.57
0.534
6.96
+33.1
−19.6
stretch (both rulers)
C03
seeded, work proxy
4.17
0.58
0.565
5.66
+33.4
−19.6
stretch (both rulers)
Appendix
Table 6: Exam-split accuracy and cost on 200000 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 ). z 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.
The reliability of AI generative models is typically measured by output correctness, yet in practice it depends on the effort required to verify those outputs. We argue that current evaluation metrics overlook a critical failure mode: Verification-Cost Errors (VCEs), defined as incorrect input-output pairs that a declared fraction of the verifier population fails to identify within the verification budget available in a given deployment context. Unlike standard notions of "hallucination", VCEs are defined operationally, by the failure of correct identification within budget rather than by any property of the output itself. Plausibility and authoritative presentation are hypothesised contributors to that failure, not defining conditions. To capture this asymmetry, we introduce the notion of verification cost relative to a deployment budget as an operational dimension that current evaluation does not routinely capture. The quantity is presented as a conceptual instrument rather than a finalized metric. Evidence from code generation and multi-modal document understanding shows that high benchmark accuracy can mask significant verification effort in practice. We therefore take the position that correctness alone is insufficient as a measure of reliability. AI evaluation should explicitly account for verification cost, reflecting whether errors can be detected under realistic resource constraints.
Hitachi, Ltd., Tokyo, Japan · Hitachi Rail, Naples, Italy · Department of Information Engineering, Computer Science and Mathematics, University of L’Aquila, Italy
As large language models (LLMs) increasingly make consequential decisions and solve problems alongside humans, we must understand how models arrive at their conclusions. Understanding how an LLM behaves requires observing it across multiple inputs, yet free-text explanations such as chain-of-thought (CoT) are generated per instance and cannot be easily verified on new inputs. We propose {code explanations to address the mismatch in how LLM explanations are generated versus how they are evaluated: a program explains LLM behavior across a dataset of inputs, and its execution enables automatic verification. We define Consistency metric that measures the fraction of inputs on which the program reproduces the LLM's outputs, and use it to evaluate and select candidate programs. Across three open-source code-capable LLMs and eight tasks, we find that LLMs can produce highly consistent code explanations in several settings. Code explanations are also 6× to 100× shorter than CoT, and better align with model behavior in 9 out of 24 settings. However, consistency is significantly lower on tasks with more complex linguistic components, where generated programs reproduce model outputs no more frequently than an uninformative explanation baseline, and these programs often rely on longer hard-coded patterns. In experiments with Claude Opus 5.5, providing the model with consistency feedback and code execution improves explanation consistency across tasks, but consistency remains significantly lower on more complex tasks. Our findings establish executable code as a novel, verifiable, and compact approach to explaining LLM behavior and highlight verification feedback as a promising direction for improving explanation consistency. The code for this paper is at https://github.com/rajesh-lab/code-as-explanations.
Verifying LLM-generated answers under a shared computational budget requires jointly deciding which candidates to inspect and which verification attributes to evaluate. We formulate this problem as multi-attribute good-arm identification under a global budget: each candidate is an arm evaluated along several costly attributes, and the goal is to certify as many candidates as possible whose mean scores exceed the prescribed thresholds on all attributes. We propose BMA-GAI, an algorithm that combines cost-aware arm selection with adaptive sampling of attributes. Every observation serves both to guide adaptive allocation and to support anytime-valid certification, which removes the need for a separate confirmation stage. We establish an asymptotic coverage guarantee for BMA-GAI and derive a matching information-theoretic converse that characterizes the intrinsic complexity of the problem, thereby proving that BMA-GAI is first-order optimal away from critical budget levels. Experiments on synthetic benchmarks and an LLM answer-verification task show that BMA-GAI allocates the verification budget more efficiently and certifies more high-quality candidates than competing methods.
Bo Xue, Ji Cheng, Shen-Huan Lyu +2
City University of Hong Kong · Hohai University · Zhejiang University