cs.AINov 19, 2026

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

Authors: Edgar A. Duéñez-Guzmán, Eduardo Dueñez, Edgar Said Hernandez Sanchez, Suzanne Sadedin

Organizations: The University of Texas at San Antonio

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.

Figures & tables

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Aug 9, 2026

AI Evaluation Should Measure Verification Cost, Not Correctness Alone

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.
Nov 10, 2026

Code as Explanations: Executable and Verifiable LLM Explanations

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×\times to 100×\times 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.
Sep 28, 2026

Test-Time Scaling via Budgeted Multi-Attribute Verification

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.