Measuring the Checker: Mutation Analysis for GPU-Kernel Benchmark Oracles
Mingzhe Du, Anh Tuan Luu, Dong Huang, See-Kiong Ng
cs.LG, cs.PL
2026-09-02
On 10,303 CUDA mutants across 188 KernelBench problems, the official five-input check misses 16.9% of witnessed faults (78.6% of precision faults); two chosen inputs reach 98.0%.
GPU-kernel generation benchmarks such as KernelBench decide correctness with a handful of random inputs and a loose floating-point tolerance. Those verdicts now feed public leaderboards and the reward for reinforcement learning systems that write kernels. When the checker is blind, the model does not learn to write correct kernels. It learns to write kernels that pass.
The community has been patching. KernelBench-Verified adds four hidden distributions and a tighter tolerance, and published speedups fall from 1.43× to 0.88×. The Correctness Illusion seeds nine bugs by hand and proposes a fuzzer. robust-kbench hardens shapes and timing. Each effort patches. None of them can say which faults a patch covers and which it still misses. Ten hand-seeded bugs can look decisive while an entire fault family is unreachable by construction.
Researchers at the National University of Singapore and Nanyang Technological University take mutation analysis, a fifty-year-old software-engineering tool, and turn it into a score for kernel-benchmark oracles.
Mutation analysis asks what fraction of small injected faults a test suite detects. Four obstacles block a direct transplant to GPU kernels. The oracle is a graded numerical comparison, not exact equality. Inputs that are too aggressive reject correct kernels through legitimate floating-point accumulation-order noise. Equivalent mutants and oracle-blind mutants pollute the denominator. Compiling one mutant through the usual torch extension path takes about 200 s; ten thousand mutants would need GPU-years.
The pipeline is built around those four. For each problem a CUDA implementation that passes the official reference is kept as a mutation substrate; the oracle remains the benchmark's own reference. 124 deterministic rules span six families: arithmetic, indexing, semantic, boundary, synchronization, precision. NVRTC brings compile time to 84 ms, about 500×. Hashing compiled images drops duplicates and host-only no-ops. Crashes and hangs are quarantined. A mutant enters the scoring denominator only with a kill witness: a validity-gated input on which it verifiably fails. A protocol's score is the fraction it kills among 7,384 witnessed mutants. The official tolerance is atol = rtol = 10⁻² unless a protocol says otherwise.
Two mechanisms explain the misses. A tolerance vacuity band grows with reduction length: for softmax at d=393,216 the reference output averages about 2.5×10⁻⁶ per element, while official atol=10⁻² is four thousand times the signal, so an all-zeros kernel passes. A legitimate-variance ceiling: sign-mixed inputs scaled to 300 push two correct fp32 kernels past the official tolerance through accumulation order. Harsher inputs past that line are invalid, not stricter.
The official protocol (each problem's own getinputs(), five seeds) detects 6,136 of 7,384 witnessed faults: 83.1%. It misses 16.9%, one in six, and a bootstrap over problems shows this is a property of the suite, not of the sample. The median problem loses 10%; a tail of transposed-convolution and reduction problems loses 40–73%.
| Family | Witnessed | Official miss |
| Arithmetic | 3,349 | 8.7% |
| Indexing | 749 | 14.4% |
| Semantic | 858 | 14.9% |
| Boundary | 1,735 | 22.9% |
| Synchronization | 400 | 27.8% |
| Precision | 271 | 78.6% |
| All | 7,362 | 16.9% |
Textbook arithmetic is mostly caught. Boundary, synchronization, and precision faults, the ones real kernels actually hit, escape at three to nine times that rate. Precision faults miss at 78.6%; the tolerance forgives them by construction.
KernelBench-Verified's +8.5 points over the official protocol split into +4.0 from the four hidden distributions and +4.5 from the tighter tolerance. All four transforms rescale magnitude and never vary shape, so remainder-block boundary faults and index-arithmetic faults are unreachable by construction. A reconstructed Correctness-Illusion fuzzer reports 86.2%, and rejects correct kernels 107 times with invalid inputs.
Set cover on the kill matrix: a median of two inputs per problem covers every witnessed mutant, at most six. A two-input suite reaches 98.0% on the full pool and 94.8% held-out, against 83.1% for the official five. On a knowledge ladder for a test generator, a naive "tests may miss subtle bugs" prompt kills 42.9%; adding the fault taxonomy and the validity ceiling reaches 61.0%; showing the mutated source sites drops to 57.3%. Family-level abstraction beat white-box instances.
Across 48 whole networks (level-3), the witnessed miss rate is at least 17.3%, and survival among behaviourally distinct mutants is 43.0% against 25.7% at operator scale. Deep homogeneous pipelines are nearly opaque: VGG-19 and SqueezeNet at 90%, LSTM stacks at 77–87%. Normalization- and branch-dense nets stay checkable at depth: ResNet-18 (51 kernels) 11%, SwinMLP (71 kernels) 14%. Two problems are unrefereeable. For 48Mamba2ReturnY the official fp32 reference violates the benchmark tolerance against its own fp64 at 352 positions, with outputs at 10²⁰. For 45UNetSoftmax the deviation reaches 0.74, with 9,379 violations. No fp32 implementation, including the reference, can be judged on those two.
Kernel-writing RL now takes this checker as reward. Where the reward is blind on precision and synchronization, policies will sit in the vacuity band. KernelBench-Verified already showed the practical cost: headline speedups fall from 1.43× to 0.88× once the checker hardens. What was missing was a measuring stick. This paper builds one, and turns suite design into set cover.
Benchmark maintainers can patch by fault family rather than by adding more random seeds. Two chosen inputs beat the official five, so the issue is which tests, not how many. The release, KernelBench-M, includes rules, substrates, witnesses, and suites. The next patch to a kernel benchmark can ship with its coverage measured.
Adequacy is relative to a fault model. 124 rules over naive substrates cannot express tensor-core paths, double-buffered pipelines, some warp-level idioms, or multi-site interactions. The metric supports comparative claims (suite A catches faults suite B misses) and existence claims (this protocol misses these witnessed faults). It cannot certify a passing kernel correct, and it is not used that way.
Substrates are LLM-authored CUDA admitted by an automated gate, not sampled from submissions. Experiments ran on one H100. The level-3 witness search is shallower than at operator scale, so 17.3% is a floor. A realism probe asked an LLM for leaderboard-style optimized kernels on 60 problems; three were wrong, and both runtime bugs sat inside the boundary/guard and accumulation/semantic families. The sample is small. Tolerance is fixed at the benchmark's own 10⁻² by design; the effect of changing it is isolated in the Verified audit.