cs.LGSep 2, 2026
SaveMeasuring the Checker: Mutation Analysis for GPU-Kernel Benchmark Oracles
Organizations: National University of Singapore · Nanyang Technological University · CAIR, VinUniversity
Abstract
Benchmarks for LLM-generated GPU kernels decide correctness with a few random inputs and a loose floating-point tolerance, and their verdicts now feed leaderboards and reinforcement-learning rewards. Recent work agrees these checkers are weak and patches them by hand---extra input distributions, fuzzing recipes, tighter tolerances---with no way to measure whether any patch suffices. We introduce mutation analysis as an adequacy metric for kernel-benchmark oracles: deterministic rules inject 10{,}303 compilable faults into verified CUDA implementations of 188 KernelBench problems, 7{,}384 of them with an independent kill witness; any test protocol is scored by the fraction it detects. The official check misses one in six witnessed faults (16.9%), deterministically, and the misses are skewed by family: 8.7% of arithmetic faults escape, but 78.6% of precision faults do. The metric explains why (a tolerance blind band growing with reduction size; a measured ceiling on input aggressiveness set by legitimate floating-point variance), audits the strongest existing patch (KernelBench-Verified's gain splits into points from hidden inputs and from tighter tolerance, a split its authors could not compute), and exposes a published fuzzing recipe that rejects correct kernels 107 times. Optimizing suites over the kill matrix reaches 98.0% detection with two inputs per problem (94.8% held-out), and the measurement's fault taxonomy teaches a test generator more than the raw faults themselves. Across 48 whole architectures, the blindness grows with scale, concentrating in deep homogeneous pipelines, and two problems prove unrefereeable: their official references violate the benchmark's own tolerance against fp64. We release everything as KernelBench-M.
Figures & tables
Figure 1: The measurement pipeline. Block height is proportional to mutant count. Deterministic rules mutate 188 gate-verified CUDA substrates into 10,303 mutants; compilation, compiled-image hashing, and crash quarantine remove 2,050 (the red strip cut from beneath each block, split by cause), and a kill-witness search over validity-gated inputs admits 7,384 into the scoring denominator, quarantining the 869 that no valid input kills. The witnessed kill matrix (mutants inputs, filled = detected) records only inputs that pass the validity gate; an input that rejects the correct kernel (red column) is discarded. The matrix then scores any protocol, synthesizes minimal suites, and yields the fault taxonomy.
Figure 2: What the official check misses, and why. (a) Share of witnessed faults missed by the official protocol, by family ( at right): textbook arithmetic mutations are mostly caught; precision faults escape at the average rate. (b) The check accepts any error below (black line; grey region invisible to it; filled markers: the check fires, open: it accepts). Vacuity: the fault “return all zeros” has error (blue); as the softmax reduction grows it slides into the grey region and passes. Validity ceiling: the fp32 accumulation noise between two correct kernels grows with input scale ; on sign-mixed inputs the output cancels and the noise climbs out of the region, rejecting a correct kernel ( ); on same-sign inputs it stays deep inside (green).
| Operators (levels 1–2) | Architectures (level 3) | |
| Problems (substrates) | 189 | 48 |
| Mutation rules | 124 | 124 |
| Mutants generated | 10,303 | 12,589 |
| non-compiling | 1,594 | 38 |
| duplicate compiled image | 279 | 155 |
| equivalent to original | 177 | 35 |
Table 1: The mutation pipeline of Fig. 1 in numbers, at operator scale (levels 1–2) and architecture scale (level 3). “Distinct” counts mutants surviving compilation, compiled-image deduplication, and equivalence filtering; “witnessed” additionally requires a validity-gated input on which the mutant verifiably fails. The 124 rules split boundary 39, precision 30, semantic 22, synchronization 14, indexing 14, arithmetic 5; 96 fire with a witness (Table 2 ). Substrates total 44,270 lines of CUDA across 360 device kernels; at operator scale a problem carries 37 mutants at the median (199 at most) and 5 survivors (81 at most). The kill matrix comprises over 120,000 mutant–input evaluations, each mutant compiled in 84 ms by NVRTC versus 200 s through the torch extension path.
Figure 3: Population structure of the official check’s blindness at operator scale. (a) Per-problem miss rate, sorted: half the problems lose under 10% of witnessed faults, while a tail of transposed-convolution and reduction problems—exactly the shapes tolerance vacuity predicts—lose 40–73%. (b) Pooled miss rate under bootstrap subsampling of problems: the 90% band contracts onto 16.9%, so the headline is a property of the benchmark, not of our sample.
| Family | Rules | Witnessed | Missed | Example operators |
|---|---|---|---|---|
| Arithmetic | 5 | 3,349 | 8.7% | , , off-by-one constant |
| Indexing | 13 | 749 | 14.4% | axis swap, stride confusion, transposed access |
| Semantic | 18 | 858 | 14.9% | tie-breaking, fused-op reordering, flag flips |
| Boundary | 27 | 1,735 | 22.9% | guard deletion, ceil floor grid, tail drop |
| Synchronization | 6 | 400 | 27.8% | barrier removal, __syncwarp weakening |
| Precision | 27 | 271 | 78.6% | fp16 accumulators, no-stabilizer, fast-math |
Table 2: Operator taxonomy and where the official check fails. Witnessed mutants per family and the share the official five-input protocol misses. The gradient is the paper’s central empirical fact: textbook arithmetic mutations are mostly caught, while the implementation-level families real kernel bugs occupy—boundary, synchronization, precision—escape at to the rate.
Figure 4: Protocol audit on the unified denominator (8,215 witnessed mutants across 235 operator- and architecture-level problems). “Ours” is the official dense-random input plus one per-problem input chosen by set cover (§ 6 ). Hardened protocols improve on the official check (dashed line) but plateau below optimized selection at half the input budget; the fuzz baseline’s score comes with 107 false rejections of correct kernels. Fig. 5 dissects the blind band into its miss-patterns.
Figure 5: Anatomy of the blind band: the kill matrix collapsed to its distinct miss-patterns (UpSet form). Each column is one pattern of “which protocols miss this mutant” (filled = missed), its bar the number of operator-scale mutants with that pattern; left margins give each protocol’s total misses (cf. Fig. 4 ). The band’s core is the leftmost column: 643 mutants that every baseline misses and only our targeted suite detects. Each KBV scaling removes a different, partially overlapping slice (columns 2–5); the fuzzer removes more; our suite misses 10 of 7,320 in the residual mixed tail.
| Optimized, budget | Official | ||||
|---|---|---|---|---|---|
| Scored on | 5 random | ||||
| Full pool | 87.1% | 98.0% | 99.5% | 100.0% | 83.1% |
| Held-out mutants | 84.5% | 94.8% | 96.4% | 96.6% | 82.9% |
Table 3: Detection versus input budget on the witnessed level-1/2 pool. Held-out: suites selected on a 50% dev split of each problem’s mutants and scored only on the other half.
Figure 6: Synthesis results. (a) Detection versus input budget: greedy set cover on the kill matrix, scored on the full pool (solid) and on held-out mutants under dev-half selection (dashed). (b) Minimal full-coverage suite size per problem: median two inputs, maximum six. (c) Killing power of generated suites on 1,154 official-input survivors as generator knowledge grows (Table 4 ): the measurement-derived taxonomy beats both ignorance and white-box fault listings.
| Rung | Generator knows | Survivors killed | Validity |
|---|---|---|---|
| R0 random fuzz | nothing | 21.6% | 107 false kills |
| R1 naive prompt | “tests may miss subtle bugs” | 42.9% | 60/60 |
| R2 taxonomy & ceiling | fault families, safe magnitudes | 61.0% | 94% (accum.) |
| R3 white-box diffs | the mutated source sites | 57.3% | 55/56 |
Table 4: The knowledge ladder: identical task (kill 1,154 official-input survivors), increasing generator knowledge. Validity = share of generated suites that do not reject the correct kernel. The taxonomy rung accumulated more suites per problem than the single-shot rungs, so its edge over the naive prompt is an upper bound; the ordering is unaffected.
| Scale | Problems | Distinct | Survival (distinct) | Missed (witnessed) |
|---|---|---|---|---|
| Operators (levels 1–2) | 189 | 8,253 | 25.7% | 16.9% |
| Architectures (level 3) | 48 | 12,361 | 43.0% | 17.3% |
Table 5: Operator scale versus architecture scale. Distinct = behaviourally distinct compilable mutants; survival = share not killed by the official inputs; witnessed = mutants with a validity-gated kill witness. The level-3 witness search is far shallower (2–4 targeted suites per problem versus the full matrix at operator scale), so its witnessed miss rate is a conservative lower bound and its distinct-survival an upper bound.
Figure 7: Architecture-scale results (distinct-mutant accounting). (a) Survival by injection-depth quartile across 48 architectures: faults with more network downstream survive more. (b) Per-architecture survival versus pipeline depth: deep homogeneous pipelines (VGG, LSTM, MLP chains) approach opacity, while normalization- and branch-dense networks (ResNet-18, SwinMLP) remain checkable at any depth.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
| Operator | Family | Missed / witnessed | Rate | Example site |
|---|---|---|---|---|
| store-fp16 | precision | 169 / 183 | 92% | out[i] = (half)acc |
| mul2plus | arithmetic | 99 / 990 | 10% | delta * delta |
| loop-start-1 | boundary | 82 / 417 | 20% | for (int i = 0; |
| mul2div | arithmetic | 78 / 968 | 8% | value * norm_weight[c] |
| loop-bound-minus1 | boundary | 77 / 384 | 20% | i < hidden_size; i++ |
| plus2minus | arithmetic | 75 / 1,173 | 6% | variance + 1.0e-5 |
Table 6: Top mutation operators by officially-missed faults (operator scale, witnessed accounting). “Example site” shows a representative mutated source location.
| Rule | Description |
|---|---|
| Arithmetic (4 rules) | |
| minus2plus | AOR: - + |
| mul2div | AOR: * / |
| negate-store | UOI: negate stored expression |
| plus2minus | AOR: + - |
| Indexing (14 rules) | |
Table 7: The mutation-rule inventory loaded by the released mutator, by family. [TODO: the released rule files load 120 unique rules (7 definitions duplicate an existing pattern and are skipped); the main text counts 124. Reconcile.]
| Rung | Killed | Evaluated | Rate |
|---|---|---|---|
| R0 random fuzz | 249 | 1,154 | 21.6% |
| R1 naive prompt | 495 | 1,154 | 42.9% |
| R2 taxonomy & ceiling | 704 | 1,154 | 61.0% |
| R3 white-box diffs | 626 | 1,092 | 57.3% |
Table 8: Knowledge ladder, raw counts: survivors killed over survivors evaluated at each rung.