Verified Stepping Stones: Program Optimization as a Cascade of Decidable Hops

Language models can now rewrite programs into faster ones, but no one can prove the rewrites correct. Checking that two programs compute the same function is undecidable in general. It stays decidable, and cheap in practice, only when the two programs line up closely enough that no loop invariant has to be invented. Solar cells and photodiodes face a structurally similar problem. A single large energy drop between two materials wastes carriers, so engineers insert intermediate materials whose levels sit between the two, and the carriers descend a staircase of small steps. We propose the same move for verified optimization. The model produces a chain of intermediate programs in which every adjacent pair differs by a rewrite small enough that equivalence falls inside a decidable, solver-friendly fragment. Correctness of the whole chain then follows by transitivity, even when the direct source-to-final comparison is far outside what any checker can handle.

The concrete claim is this. Constraining a language-model optimizer so that each hop is "checkable" should give a higher rate of proven speedups than either optimizing freely and checking the end result, or accepting intermediate steps on test evidence. By "checkable" we mean that the equivalence query for the hop reduces to loop-free, fixed-width bit-vector formulas via a lockstep correspondence between loops. We also expect an intermediate hop size to maximize verified progress per unit of compute. Hops that are too small waste model calls. Hops that are too large break the loop correspondence, the checker times out, and the candidate is lost. This is the analogue of carriers lost at an oversized energy offset.

What exists and what is missing

Three lines of work motivate this proposal. SemRep trains a model to generate semantically equivalent programs as an intermediate representation. At inference it runs an evolutionary search over "stepping stones," intermediate variants that unlock later optimizations. On KernelBench it reports 43.1% higher correctness than Kevin-32B, and it reaches top-tier agent performance with 25% less inference compute. Its equivalence signal, however, is equivalence modulo inputs, meaning agreement on a finite test suite. The authors acknowledge this leaves room for reward hacking. We keep its stepping-stone search and replace test agreement with proof at every hop.

EquiBench constrains the design. Its best model reaches 82.3% overall, but only 63.8% on dead-code elimination and 76.2% on CUDA scheduling, and it is biased toward calling equivalent pairs inequivalent. The EquiBench authors also found that few-shot and chain-of-thought prompting give only marginal gains. This rules out using a model as its own equivalence judge.

CodeARC shows that ten input-output examples often underspecify the target function; o3-mini reaches only 52.7% even with a counterexample oracle. That result is further evidence that test agreement is a weak correctness signal.

The method-supplying work comes from verification. TVOC sidesteps compiler verification by checking each individual compilation instance, using a correspondence between source and target. We use the same idea per hop, with the difference that our hops are chosen by a learned model rather than fixed by compiler passes. Multi-stage pipelines such as The SemGuS Toolkit, SymRTLO, and the BMC-then-CEGAR flow in Cimatti et al. stage cheap filters before expensive proof. Those pipelines stage the checker. We instead shape the object being checked: the generator is asked to produce transitions that the checker can decide. That is the part of the design that corresponds to a stepped energy gradient.

The decidability literature supplies the rationale for where to draw the line. Kobayashi and Cotton-Barratt et al. show how a single added feature, such as a mutable reference, tips equivalence into undecidability. Dixon et al. show how structural restrictions (bounded concurrency, restricted semaphore protocols) recover decidability. Our restriction is analogous but applies to pairs: a hop is admissible when it preserves loop structure, so the check needs no invariant.

The Counting Power of Transformers proves that verifying Transformers themselves is undecidable. We never verify the model, only its outputs, so that result does not bind us.

Core Claim

Let a chain be $P_0 \to P_1 \to \dots \to P_k$, where $P_0$ is the source program and $P_k$ the optimized one. A hop $P_i \to P_{i+1}$ is admissible if a structural matcher finds a one-to-one correspondence between their loops. Given that correspondence, equivalence reduces to quantifier-free bit-vector queries over loop bodies and exits, which is a decidable problem, and those queries must be solved within a solver budget $\tau$. An admissible chain certifies $P_0 \equiv P_k$.

We claim three things. First, admissibility is learnable: a model can be trained to propose admissible hops at high rate. Second, chains reach larger verified speedups than direct end-to-end rewrites, whose correctness usually requires invariants that no solver will find. Third, verified speedup per GPU-hour is non-monotone in the allowed hop size.

Research Program

We would build three components.

The first is the hop checker. It takes C and loop-bearing x86-64 functions and performs structural loop matching in the style of translation validation. It then discharges the per-segment obligations with a bit-vector SMT solver at budget $\tau$. If matching fails, the hop is rejected outright, with no fallback to invariant search. This keeps each hop inside the decidable fragment.

The second is the hop generator. We start from an open 32B code model at SemRep's scale and fine-tune it with group relative policy optimization, the same reinforcement-learning recipe SemRep uses. The reward is admissibility plus measured speedup, replacing SemRep's test-agreement reward. Because rejections are proofs of non-admissibility rather than failed tests, the reward cannot be satisfied by code that merely passes tests.

The third is the cascade search. This is SemRep's evolutionary loop in which each child must be an admissible hop from its parent. Uphill steps, where the program gets temporarily slower, are allowed, as in SemRep. The analysis side varies a hop-size budget, measured as tree edit distance or number of loop regions touched. This lets us map verified yield against hop size and test the predicted interior optimum.

Baselines

The naive reference point is the unoptimized source, with speedup 1.0 and trivially verified. Alongside it we run direct end-to-end rewriting: the same base model rewrites once, and we attempt to verify the final pair with the same checker and a much larger solver budget. This measures how often direct verification simply fails.

The strongest existing competitor is SemRep. It is the only system in the file that already uses stepping stones and reports large gains, including 43.1% higher correctness than Kevin-32B on KernelBench. We would retrain it with its test-agreement reward on the same base model, data, and GRPO step count, and give it the same inference budget. We then report two numbers for it. The first is its tested correctness. The second is its proven correctness: the fraction of its outputs that our checker certifies, whether by the direct check or by retroactively matching its own intermediate chain. We also measure its false-accept rate under heavy differential fuzzing on held-out inputs. Beating SemRep means a higher proven-speedup rate at equal compute, together with a lower false-accept rate, and no more than a modest loss in raw tested speedup.

A compiler baseline runs standard optimization passes with per-pass translation validation, following TVOC. This represents verified optimization without learning.

The key ablation keeps our trained generator and search but accepts hops by test agreement rather than proof, with an identical budget. This isolates whether the decidability constraint itself, rather than extra training, produces the gain.

Why not just…?

Why not just verify the final program directly with a stronger solver? Direct equivalence between a source and a heavily restructured target generally requires loop invariants. That is exactly the undecidable part, so budget alone does not help. Still, this is a real threat on short, loop-light functions. The direct end-to-end baseline, run with a solver budget ten times larger than the per-hop budget, measures it. If direct checking certifies most final outputs, the cascade is unnecessary and we would say so.

Why not just add more tests or fuzzing to SemRep? More tests shrink but never close the gap. CodeARC shows that modest example sets routinely underspecify functions, and SemRep's authors name reward hacking as a live risk. Our test-reward ablation, evaluated under a held-out fuzzing campaign much larger than the training tests, quantifies how many "correct" outputs are wrong. If that rate is near zero on these benchmarks, the practical case for proofs weakens to one about auditability. The note would report that honestly.

Why not just let the model judge equivalence? EquiBench's 63.8% on dead-code elimination and its bias against equivalent pairs, which prompting does not fix, make a model judge unusable as a gate for correctness.

Why not just use the compiler's own verified passes? The compiler passes are sound but limited to the rewrites compiler authors anticipated. The compiler baseline tells us whether learned hops find speedups outside that set. If they do not, the learned generator adds nothing.

Proposed Experiments

The primary suite uses the C dead-code-elimination and x86-64 superoptimization categories of EquiBench, repurposed as optimization sources. In these categories our fragment is most natural, and the file reports that models are weakest there (63.8% on dead-code elimination). The second suite uses AlgoTune tasks restricted to C translations with fixed-width integer arithmetic. As a stretch, we use KernelBench kernels at fixed tensor shapes, where bounded shapes make loop bodies finite. For KernelBench, the SemRep figure of +43.1% correctness over Kevin-32B is the reported reference; no reported proven-correctness number for any system was found on Lacuna.

The metrics are proven-speedup rate (fraction of tasks with a certified speedup above 1.1x), geometric-mean certified speedup, false-accept rate under held-out fuzzing, and GPU-plus-solver hours per certified speedup.

Three checks decide the proposal. First, proven-speedup rate must exceed SemRep's proven rate at equal compute on the primary suite. Second, the test-reward ablation must show that the gain comes from the admissibility constraint. Third, the hop-size sweep must show an interior maximum in certified speedup per hour. If yield instead rises monotonically with hop size, the stepped-gradient story is wrong and the right design is simply "rewrite big, check hard."