A new formal study says a model compiler-inlining procedure can guarantee that its final cost is no more than 2.5 times the best possible cost within the model. The result is a mathematical worst-case bound, not evidence that generated programs run 2.5 times slower on real machines.
The work, presented as an arXiv version 1 preprint dated 20 Aug 2026, asks whether compiler passes can be checked for performance and compile-time properties as well as for preserving a program’s meaning.
A narrow model of inlining
The proof of concept studies inline expansion. At each modeled call site, the formal choice is either to inline or to preserve the call, with all choices sharing a set of instruction-cache resources. The prototype is mechanized in Rocq, with its definitions and proofs checked as part of that formal development.
The model assigns each shared resource an affine, or linear, delay cost based on how many selected call sites use it. The procedure repeatedly changes a call site only when switching choices strictly lowers its delay, recalculating costs until no candidate can improve.
What the proofs guarantee
Within the formal language and transformation relation used in the prototype, the leaf-inlining transformation preserves semantics under bisimulation—the study’s formal way of matching the modeled behavior of the original and transformed programs.
Every accepted local improvement strictly lowers a global potential measure. The process therefore reaches a fixed point with no unilateral improvement, described in the study as a pure Nash equilibrium.
The paper also gives a symbolic upper bound on the number of accepted steps before convergence. With N candidate call sites, E cache-line resources and the stated bounds a_r ≤ A and b_r ≤ B, the bound is E(AN² + BN) accepted steps. After k accepted steps, at most E(AN² + BN) − k remain, alongside a coarse intermediate-cost bound written as C(s_k) ≤ 2(E(AN² + BN) − k).
The gap between a theorem and a compiler benchmark
The step bound counts accepted best-response steps, so it is not a wall-clock compile-time guarantee. The paper reports no wall-clock compile-time measurement.
The formal setting is narrow. All candidates are assumed to be leaf call sites, so inlining does not add new candidate calls to the worklist. Its cost model is the stated affine shared-resource model for instruction-cache performance.
The study calls the 2.5-times figure a Price of Anarchy guarantee: it compares the procedure’s final cost with the global minimum. The authors describe it as quite loose, and it does not show that the procedure reaches the global optimum or that the bound is tight for a particular architecture or program structure.
A proof artifact, not an empirical result
The Rocq development contains approximately 4,000 lines of code and zero admitted lemmas, according to the study. That measures how fully the proof artifact was mechanized; it is not a measure of generated-code speed or compiler performance.
The authors conclude that verified compiler passes should certify both performance bounds and convergence-time properties.
Paper data and sources
Original title: Formal Performance and Compile Time Guarantees for Compiler Optimization Heuristics
Authors: Nikil V. Shyamsunder
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text