Testing Kernel Equivalence on Modern Code: Proofs of Equivalence for the Cases Language Models Get Wrong

In 1971, Terrence Pratt proposed a practical way to show that two programs compute the same thing, and nobody appears to have ever run it. His idea splits each program into kernel statements, which do the real work by writing outputs or performing input/output, and control statements, the branches and loop tests that only decide which kernel statements run. Two programs are kernel equivalent if, for every setting of the variables that feed the branches, they execute the same sequence of kernel operations. Pratt proved two things. First, kernel equivalence implies ordinary input-output equivalence. Second, it becomes decidable, meaning checkable by an algorithm that always finishes, when the control inputs range over finite domains (Kernel Equivalence of Programs and Proving Kernel Equivalence and Correctness by Test Cases; Kernel Equivalence: A Practical Approach to Program Equivalence). He claimed the procedure is practical because real programs have few, bounded control variables. His papers contain no implementation, no benchmark, and no measurement of that claim.

Modern evaluation of code equivalence needs exactly what his method offers: a cheap proof that two programs agree, not just a failure to find disagreement. Language models judging equivalence reach 96.5% on renamed-variable pairs but only 63.8% on pairs related by dead-code elimination, against a 50% coin flip (EquiBench). Human unit tests passed 18.7% of LBPP submissions that were in fact semantically different from the reference (Disproving Program Equivalence with LLMs). We propose to build a kernel-equivalence checker for subsets of Python and C, run it against these benchmarks, and measure directly when Pratt's practicality assumption holds. The checker will be paired with an existing counterexample searcher so that every program pair receives one of three verdicts: proven equivalent, proven different, or unknown.

Core Claim

Dead-code removal and control-flow restructuring change what a program looks like while preserving its kernel trace. We therefore claim that a kernel-equivalence checker can issue sound "equivalent" certificates on a substantial fraction of the EquiBench pairs where language models perform worst. We also claim that its failures will be predictable from Pratt's own stated limits: programs that may not terminate, control inputs with unbounded domains, and equivalences that depend on algebra, such as x + y versus y + x. There are two things to measure. One is the coverage-versus-soundness profile of a proof-side checker on standard benchmarks. The other is an empirical answer to a 50-year-old practicality claim, namely what fraction of real benchmark programs actually have small, finite control domains.

Two strands of prior work frame this. The first motivates it. PROBEGEN (Disproving Program Equivalence with LLMs) has a language model read both programs and propose inputs on which they should disagree. It can only disprove equivalence and says nothing when it finds no counterexample, which is the gap our checker fills. The second constrains it. A Theory of Equivalence-Preserving Program Embeddings proves that languages mixing arithmetic with bitwise logic have too many semantic equivalence classes for efficient canonical forms. Its BERT-Tiny experiments confirm the barrier empirically. We take this as a warning that any syntax-level method, ours included, should fail on EquiBench's x86-64 superoptimization pairs, and we predict that failure in advance rather than hide it.

Research Program

The checker has four parts, each following Pratt's construction. First, it builds the control-flow graph of a function from a restricted Python or C subset: no concurrency, and heap access only through arrays. Second, it runs Pratt's backtracing from the exit nodes to split variables into kernel variables, which reach outputs, and control variables, which reach only branch conditions. Statements that reach neither are dropped. This step is what should make dead-code-eliminated pairs coincide. Third, it enumerates assignments to the control inputs. When their domains are finite and small, this enumeration is exact and yields a certificate. When they are not, we fall back to a bounded enumeration and label the verdict "bounded-equivalent," a weaker claim reported separately. Fourth, it compares the two kernel operation sequences. For a principled relaxation that addresses the algebraic blindness Pratt acknowledged, the comparison is made up to a small, fixed set of sound rewrites: commutativity and associativity of integer addition and multiplication, and reordering of independent kernel statements.

When the checker cannot certify a pair, the pair is handed to a PROBEGEN-style white-box counterexample search. If that search finds a divergent input, the pair is "different." Otherwise it is "unknown." Because each side is sound in its own direction (the kernel side up to termination and the declared rewrites, the counterexample side because a divergent input is concrete evidence), any conflict between them exposes a bug in one side or an error in the benchmark's label. Alongside the checker, we instrument every benchmark program to record the number of control variables, their inferred domain sizes, loop-bound information, and which of Pratt's preconditions fail. Together these measurements are the empirical test of his practicality hypothesis.

Baselines

The naive reference point is the 50% random-guess accuracy that EquiBench reports for its balanced categories. A second trivial reference is exact abstract-syntax-tree match after variable renaming. It shows how much of each category surface normalization alone can solve.

The strongest learned competitor is the best language model on EquiBench, prompted zero-shot, few-shot, and with step-by-step reasoning. It reaches 82.3% overall, 63.8% on dead-code elimination, and 76.2% on CUDA scheduling (EquiBench). We will quote these numbers and also rerun one open model on our exact Python and C subset so that the comparison uses the same pairs. On the language-model side, beating it means our three-way system achieves higher accuracy on the pairs it decides, with at least half of each category decided. On dead-code elimination we set a stronger bar: near-100% precision on "equivalent" verdicts where the model is at 63.8%.

The strongest existing pipeline competitor is PROBEGEN run alone, with every pair it fails to disprove treated as equivalent. PROBEGEN reports a 90% counterexample-finding success rate at 4x lower compute than full search on LBPP (Disproving Program Equivalence with LLMs). No reported result was found on Lacuna for PROBEGEN on EquiBench. We will run PROBEGEN with the same model and the same inference budget in both conditions, with and without the kernel checker in front. The claim to beat is its false-equivalence rate, meaning the fraction of pairs it calls equivalent that are in fact different.

The compiler-normalization baseline is described under the next section, since it is the most serious threat. Two ablations isolate the key ingredient. The first compares full execution traces with no kernel/control split, which tests whether backtracing matters. The second removes the algebraic rewrite set, which tests whether the relaxation matters.

Why not just…?

Why not just run an optimizing compiler on both programs and diff the output? This is the real threat for the C dead-code category. EquiBench built those pairs with compiler dead-code elimination, so recompiling both sides may collapse many of them to identical code. We will implement it as a baseline: clang at a high optimization level, followed by a diff of the intermediate representation. If it matches the kernel checker on dead-code pairs, we will report that plainly. The kernel checker's claimed advantage then narrows to two areas. One is Python, which has no such optimizer. The other is control restructuring, such as swapping between loop forms or reordering branch trees, where optimizer output is not canonical. If the compiler diff also ties on those, the contribution reduces to the empirical audit of Pratt's hypothesis. We will frame it that way.

Why not just treat "PROBEGEN found no counterexample" as equivalence? Its 90% search success means roughly one in ten differing pairs slips through as equivalent. The same paper shows that weak evidence of equivalence inflates benchmark scores: its own tests missed 18.7% of wrong submissions. The experiment below measures how many pairs PROBEGEN leaves undecided that the kernel checker then certifies. It also measures how often "no counterexample found" is wrong on pairs whose labels are known.

Why not just use full formal verification in Dafny or Lean? The evidence says the proof step is the bottleneck. In VERINA, o3 reaches only 4.9% on proof generation, and about 20% after 64 rounds of compiler feedback. VeriEquivBench finds true bidirectional equivalence between code and specification in at most 2.65% of cases. Kernel equivalence requires no written proofs or specifications. It trades generality for a certificate computed by enumeration.

Why not just learn an equivalence embedding? The embedding theory predicts failure outside tractable languages, and its BERT-Tiny results degrade on bitvector arithmetic (A Theory of Equivalence-Preserving Program Embeddings). A learned model also gives no soundness guarantee, which is the property at issue here.

Proposed Experiments

The main experiment runs the three-way system on EquiBench's Python pairs (algorithmic variants and renaming) and C pairs (dead-code elimination), inside our supported subset. For each category we report the fraction of pairs certified equivalent, the fraction proven different, and the fraction left unknown, along with precision against EquiBench labels. As an out-of-scope check with a stated prediction, we run the same system on x86-64 superoptimization and CUDA pairs. We expect near-zero certification there, which would replicate the embedding paper's barrier on real code. If our certificates are nonetheless frequent there, that means the rewrite set is doing more than intended and needs auditing.

The second experiment tests Pratt's practicality claim directly. For every program in EquiBench's Python and C subsets and in LBPP, we report the distribution of control-variable counts and domain sizes. We also report the fraction of programs for which exact enumeration completes within a fixed time budget, together with checker runtime and memory, the metrics absent from Pratt's work. If most programs have unbounded control inputs, such as loop counts depending on input length, then the "bounded-equivalent" verdict carries the load, and we will say the original hypothesis fails as stated.

The decisive checks are consistency and label audit. On LBPP submissions that pass all unit tests, no pair we certify equivalent should be disproven by PROBEGEN. Any such conflict is either a checker bug or a violated precondition, and we will examine each case by hand. We will also report how many of the pairs PROBEGEN leaves undecided we can certify, which is the direct measure of the proof side's added value. On EquiBench, every disagreement between a kernel certificate and the dataset label will be inspected by hand. The result will show whether the compiler-generated labels contain errors, which EquiBench itself leaves open. The project is useful if certificates are near-perfectly precise and cover a large share of the dead-code and restructured Python pairs, where language models are near chance. It is informative even if coverage is low, because it would be the first measured answer to whether kernel equivalence is practical at all.