Language models paired with program verifiers can now write code together with a machine-checked proof that it meets its specification. The proofs say nothing about speed, though. On competition problems translated into Dafny (a programming language whose compiler proves programs correct against written specifications), the best agent produced 52 verified programs on the medium split, and only 6 of them passed the original runtime tests. The rest ran out of time or memory (DafnyProver: Agentic Verified Code Generation in Dafny). "Verified" and "usable" have come apart. The usual fix is to trust the model's own judgment about how fast its code will run, and that is the one thing code models are demonstrably bad at: they cannot reliably trace loop counts or state changes across even a few statements.
We propose putting running time inside the proof. Each synthesized program carries a ghost cost counter, meaning a proof-only variable that is erased at compilation and incremented on every loop iteration and recursive call. The specification then requires the counter to stay below a bound derived from the problem's input limits, so the same verifier that checks correctness also rejects programs that are asymptotically too slow. The model no longer has to simulate its code's cost in its head. It has to produce code and a proof that the verifier accepts, and the verifier returns concrete counterexamples when the cost bound fails. The trusted addition is small: a syntactic pass that inserts counter increments. We test the idea on competitive programming, and as a transfer domain we use the numerical kernels that correct chromatic aberration in flat-lens cameras, where "correct but slow" is exactly the failure that matters.
Core Claim
The verified-but-slow failure is a specification gap, not a limit of verification. Stating resource bounds in the language the verifier already checks should raise the rate of programs that are both verified and pass runtime tests far more than asking the model to reason about complexity. That rate is the metric we care about. The claim has a diagnostic half. Models' inability to simulate execution internally is what causes verified-slow programs, and a model's error in predicting its own program's step count should predict whether that program will time out. If both halves hold, formal cost counters work as a substitute for a capacity current models lack. They are not a redundant check on something the model could have done itself.
The claim differs from its closest relative, AxDafny (DafnyProver). AxDafny uses a proposer–reviewer loop driven by Dafny counterexamples to reach 92.7% on DafnyBench and 56.4% on LCB-Pro-Dafny. It identifies the runtime gap and leaves it open, because its specifications are purely input–output relations. We keep its loop and change what the verifier is asked to prove.
Research Program
Cost instrumentation. The first component is the instrumentation pass. It inserts steps := steps + 1 at loop heads and function entries, and adds a precondition/postcondition pair that threads the counter through calls. Each problem's specification gains a clause of the form
$$\text{steps} \le c \cdot f(n),$$
where $n$ is the input size, $f$ is a target growth function such as $n$ or $n \log_2 n$, and $c$ is a constant.
The target $f$ comes from the problem's stated constraints. We use the standard competitive-programming rule that roughly $10^8$ elementary steps fit in the time limit. Targets are fixed by hand from reference solutions and audited, so they are part of the trusted specification rather than something the model chooses.
Trusted computing base. Following the trusted-computing-base discipline, meaning the code that must be unconditionally trusted, we deliberately keep the new trusted code tiny. The inspiration is the LCF style, where untrusted automation can only produce theorems through a small checked kernel, and Platzer's move of replacing hard-coded side-condition checkers with one small substitution algorithm (Uniform Substitution at One Fell Swoop). The model never touches the instrumentation. It sees only the instrumented specification, so it cannot game the counter by deleting increments.
We do not claim to shrink Dafny's own trusted base; Dafny and Z3 remain trusted, as in AxDafny. We do validate the pass empirically. Compiled programs are run with a real operation counter, and we check that measured counts never exceed the proven bound. Any violation is a bug in our trusted pass and is reported.
Diagnostic study of internal simulation. Before each verification call, the model predicts its program's step count at two input sizes, in the style of the output-prediction task in CRUXEval. We then relate prediction error to eventual time-limit failures. CRUXEval and CodeSense motivate this study. CodeSense reports that frontier models fall below 30% on single-statement C blocks and drop from about 50% to about 20% as Python blocks grow from one to three statements. Nobody has connected that weakness to the verified-slow phenomenon.
Imaging kernels as a transfer domain. We write roughly thirty specified tasks drawn from computational chromatic-aberration correction. These include spatial versus fast-Fourier-transform convolution, Wiener-style frequency-domain division as used after the extended-depth-of-focus metalenses of Huang et al., and the patch-wise least-squares step of cross-channel transfer from Peng. In these tasks a naive correct implementation is quadratic in kernel size where a fast one is not.
Floating-point soundness is a known hard boundary. Chatterjee et al. needed a dedicated safe-rounding interval scheme just to certify Markov decision process values. We therefore specify these kernels over fixed-point integers and treat that as a scoping constraint, not a solved problem. EverCrypt and HACL×N motivate the domain choice. They show verified code can match hand-tuned assembly once the algorithm is right, and we target the prior step of getting the algorithm right.
Baselines
Naive references. The do-nothing reference is single-shot generation without the agent loop, reported at 11.6% verified on LCB-Pro-Dafny. The second reference is a verified-only rate, which counts programs as successful when they verify, regardless of runtime.
Strongest existing method. The strongest competitor is AxDafny as described in DafnyProver. It is the best reported system on exactly this benchmark and the paper that documents the gap. Its reported numbers are 56.4% verified overall (75% easy, 52% medium, 28% hard), with only 6 of the 52 verified medium programs passing runtime tests.
We re-run it with the same base model, the same number of verifier calls and wall-clock budget per problem, and the same memory module. The only change is that the cost-counter clause is added to the specification. Beating it means a clearly higher verified-and-passes-runtime rate on the medium and hard splits under an equal call budget, without a statistically significant drop in the verified-only rate.
Complexity-prompted AxDafny. This baseline gives the model the input constraints and the required complexity class in natural language and asks it to reason about cost step by step before writing code. It isolates whether the formal check adds anything beyond telling the model what is needed.
Execution-feedback AxDafny. The final loop also receives runtime results on automatically generated large stress inputs, with identical call budgets. We consider this the most serious competitor, discussed below.
Ablations. An ablation keeps the counter in the specification but removes cost-related counterexamples from the feedback. This separates the value of the verifier's diagnostic signal from that of the stronger acceptance test.
Why not just…?
Why not just ask the model to reason about complexity? This bets on the capacity the evidence says is missing. CodeSense shows sharp decay in statement-level tracing, and CRUXEval reports that chain-of-thought can reduce accuracy for smaller models. The complexity-prompted baseline measures this directly. The diagnostic study shows whether prediction error on the model's own step counts tracks time-limit failures. If complexity prompting closes most of the gap, our core claim fails and we will say so.
Why not just run stress tests and feed back timeouts? This is a real threat. Large-input profiling may catch most quadratic solutions and could match our pass rate. It has two weaknesses. It gives no guarantee beyond the inputs tried, and its feedback ("too slow") is less actionable than a verifier counterexample pointing at the loop whose bound fails. The execution-feedback baseline settles the pass-rate question. If it ties, the contribution narrows to the all-inputs guarantee. We then report the hybrid (cost proof plus stress feedback) as the practical recommendation instead of claiming superiority.
Why not just put complexity requirements in the natural-language task description? Natural-language requirements are unchecked, so a program that ignores them still verifies. The complexity-prompted baseline is exactly this configuration. Comparing it with the full method quantifies what a machine-checked requirement buys over a stated one.
Proposed Experiments
Main experiment. All methods run on LCB-Pro-Dafny, all three splits, under equal budgets. The primary metric is the verified-and-passes-runtime rate. Secondary metrics are the verified-only rate, verifier calls to success, and the fraction of failures caused by cost-proof difficulty rather than wrong algorithms. The decisive check is the medium split, where the reference point is 6 of 100.
Proof burden. The main risk is that proving bounds involving $n \log n$ overwhelms Z3's nonlinear arithmetic. We therefore report the verified rate with and without the cost clause on problems whose reference solutions are known fast. That separates "harder to prove" from "correctly rejected."
Diagnostic correlation. On all synthesized programs, we correlate step-count prediction error with runtime failure, controlling for problem difficulty.
Transfer test. Every method runs on the imaging-kernel set, where we measure the fraction of verified kernels that meet the fast complexity class, plus measured runtime on 1.4-megapixel inputs. Peng's cross-channel method reports about 7 seconds per image on a desktop CPU, and Huang et al. report about 2 seconds for Wiener deconvolution. Those serve as unverified reference points, not as numbers we expect to beat. No reported result was found on Lacuna for any verified implementation of these kernels.
Instrumentation soundness. An audit compares proven bounds with measured operation counts across all accepted programs. The target is zero violations.
References
- DafnyProver: Agentic Verified Code Generation in Dafny
- Uniform Substitution at One Fell Swoop
- CRUXEval: A Benchmark for Code Reasoning, Understanding and Execution
- CodeSense: a Real-World Benchmark and Dataset for Code Semantic Reasoning
- Extended Depth of Focus Metalenses for Achromatic Computational Imaging
- Revisiting Cross-Channel Information Transfer for Chromatic Aberration Correction
- Fixed Point Certificates for Reachability and Expected Rewards in MDPs
- EverCrypt: A Fast, Verified, Cross-Platform Cryptographic Provider
- HACL×N: Verified Generic SIMD Crypto (for all your favorite platforms)