PaperlayerView exact revision on arXiv

Source-linked AI summary

Measuring the Checker: Mutation Analysis for GPU-Kernel Benchmark Oracles

Mingzhe Du, Anh Tuan Luu, Dong Huang, See-Kiong Ng

arXiv:2609.22220v1cs.LGcs.PL

TL;DR

Kernel-benchmark checkers are patched without a way to measure whether those changes cover faults, despite their role in model rankings and reinforcement-learning rewards. The paper adapts mutation analysis to graded numerical oracles, scoring protocols against witnessed faults. The official check misses 16.9% of witnessed faults, while the measurement also supports coverage-optimized suites and fault-taxonomy-guided test generation.

  • Problem

    Kernel-benchmark checkers are patched with new inputs, fuzzing, and tighter tolerances, but prior validation against at most a handful of seeded bugs cannot measure which faults a patch covers.

    Source: §1 · p. 1

  • Method

    The authors adapt mutation analysis to numerical oracles by injecting deterministic faults into verified CUDA substrates and scoring protocols against mutants with validity-gated kill witnesses.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    The official KernelBench check misses 16.9% of witnessed faults; 78.6% of precision faults escape, versus 8.7% of arithmetic mutations.

    Source: §1 · p. 2

  • Takeaways & Limitations

    KernelBench-M makes checker coverage measurable and releases the fault pool, witnesses, suites, and pipeline for assessing future protocols.

    Source: §10 · p. 10

    The 124-rule fault model cannot represent some tensor-core paths, double-buffered pipelines, warp-level idioms, or multi-site interactions, and cannot certify a passing kernel correct.

    Source: §9 · p. 10

Abstract

from arXiv · show

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 \emph{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 \textbf{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 $+4.0$ points from hidden inputs and $+4.5$ from tighter tolerance, a split its authors could not compute), and exposes a published fuzzing recipe that rejects \emph{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 \href{https://huggingface.co/datasets/Elfsong/KernelBench-M}{KernelBench-M}.

1 INTRODUCTION

GPU-kernel checker verdicts now rank models, gate experiments, and reward reinforcement learning, yet existing patches do not measure which faults they cover. This paper adapts mutation analysis to numerical oracles and finds that the official check misses 16.9% of witnessed faults.

1 INTRODUCTION

  • Checker verdicts now rank models, gate generated kernels for production experiments, and serve as reinforcement-learning rewards, so weak checks can reward kernels that merely pass.The paper describes this as a divergence between learning to write correct kernels and learning to pass the checker.Source: §1 · p. 1
  • Prior checker patches add hidden inputs, tighter tolerances, or fuzzing, but validating against a handful of hand-seeded bugs cannot show whether they cover important faults.The paper identifies the missing question as whether a patch covers faults that matter and what it still misses.Source: §1 · p. 1
  • Mutation analysis scores protocols against witnessed faults, using validity-gated inputs and a kill matrix to make numerical-oracle coverage measurable.The pipeline filters compiled mutants and quarantines those that crash or have no valid kill witness.Source: §1 · pp. 1–2, Figure 1 · p. 2
  • The official KernelBench check misses 16.9% of witnessed faults; 78.6% of precision faults escape, versus 8.7% of arithmetic mutations.The measurement uses faults with kill witnesses so that only provably detectable mutants enter the denominator.Source: §1 · p. 2

2 TWO FAULTS THE OFFICIAL CHECK CANNOT SEE

  • For a softmax reduction over 393,216 elements, the reference averages 2.5 × 10^-6 per element while atol = 10^-2, so an all-zeros output passes.The paper reports that this blind band widens systematically with reduction size.Source: §2 · p. 2
  • Reseeding cannot expose some faults when official inputs stay in [0, 1): deleting ReLU is then the identity, and removing softmax max-subtraction is unobservable.Survival under these inputs follows from the distribution's support, not sampling luck.Source: §2 · p. 2

3 MUTATION ANALYSIS FOR GRADED NUMERICAL ORACLES

This section establishes mutation analysis for graded numerical checkers and applies it to measure the official protocol’s blind spots, showing how tolerance, input validity, and mutant adjudication shape the score.

3 MUTATION ANALYSIS FOR GRADED NUMERICAL ORACLES

  • At d=64, the largest undetectable relative error is 0.39, rising to 2.5 × 10^3 at d=393,216; input scaling must also stay below the validity ceiling for correct fp32 kernels.On a K=4096 reduction, sign-mixed inputs scaled by 300 can push a correct kernel past official tolerance, while same-sign inputs of far larger magnitude remain safe.Source: §3 · p. 3, Figure 2 · p. 4
  • Only mutants with a concrete, validity-gated kill witness enter the denominator; later targeted inputs found witnesses for 431 previously surviving mutants.Equivalent and oracle-blind candidates without witnesses remain outside the witnessed denominator.Source: §3 · p. 3, §4 · p. 5
  • The pipeline admits gate-verified CUDA substrates, applies 124 deterministic rules across six families, filters mutants, and scores protocols against witnessed faults.NVRTC compilation takes 84 ms per mutant versus about 200 seconds through the torch extension path.Source: §3 · p. 3, Table 1 · p. 4

4 HOW STRONG IS THE OFFICIAL CHECK?

  • 83.1% of witnessed faults are detected by the official five-seed protocol, while 16.9% escape; half of problems miss under 10%, but a tail misses 40–73%.The pooled 16.9% rate persists under bootstrap resampling across problems.Source: §4 · p. 3, Figure 3 · p. 5
  • 78.6% of precision faults, 27.8% of synchronization faults, and 22.9% of boundary faults escape, versus a 91% catch rate for textbook mutations.The fault-family gradient shows that implementation-level faults escape more often than textbook arithmetic mutations.Source: §4 · p. 4, Table 2 · p. 5
  • Softmax has 28 tolerance-blind survivors versus 9 for log-softmax, while dense-random inputs alone kill 90 mutants, so targeted inputs complement rather than replace them.The empirically optimal suite shape is one dense-random input plus one or two structure-targeted inputs.Source: §4 · p. 5

5 AUDITING HARDENED CHECKERS

The audit compares hardened checker protocols on a shared pool of witnessed mutants. It shows that input scaling leaves structural blind spots, while aggressive fuzzing can reject correct kernels.

5 AUDITING HARDENED CHECKERS

  • At half the input budget, hardened protocols plateau below optimized selection, while the fuzz baseline’s score includes 107 false rejections of correct kernels.Figure 4 compares protocols on the unified denominator; “Ours” combines the official dense-random input with one per-problem input chosen by set cover.Source: Figure 4 · p. 6
  • 643 mutants are missed by every baseline and detected only by the targeted suite; that suite misses 10 of 7,320 in the residual mixed tail.The kill-matrix patterns show that each KernelBench-Verified scaling removes a different, partially overlapping slice, while the fuzzer removes more.Source: Figure 5 · p. 6
  • +8.5 points over the official protocol came from KernelBench-Verified, split between +4.0 points from hidden distributions and +4.5 from tighter tolerance.The unified audit covers 8,215 witnessed mutants across 235 operator- and architecture-level problems; the authors report that KernelBench-Verified did not quantify this split.Source: §5 · p. 6
  • Because the four KernelBench-Verified transforms change magnitude but not shape or structure, remainder-block boundary and index-arithmetic faults remain unreachable.Adding more scaled configurations cannot reach those faults by construction.Source: §5 · p. 6
  • The reconstructed fuzzer’s 86.2% detection partly comes from invalid inputs: its largest magnitudes caused 107 rejections of correct kernels.An early audit also falsely rejected correct kernels after guessing a larger magnitude than KernelBench-Verified’s published ×3; the authors attribute that error to their guess, not the protocol.Source: §5 · pp. 6–7

6 FROM MEASUREMENT TO SYNTHESIS

The kill matrix supports suite construction as a set-cover problem and provides a basis for testing held-out mutants. Measurement-derived fault-family knowledge also helps a generator detect faults more effectively than concrete fault examples do.

6 FROM MEASUREMENT TO SYNTHESIS

  • At the official five-input budget, an optimized suite detects every witnessed mutant, versus 83.1% for the official check; full coverage needs a median of two inputs per problem.One dense-random input plus one targeted input suffices for 86 of 152 problems with a non-trivial witnessed pool, and no problem needs more than six.Source: §6 · p. 7
  • Dev-selected suites detect 94.8% of held-out mutants at budget two, with an approximately 3-point generalization gap.Selection used one 50% hash split of each problem’s witnessed mutants and evaluation used the other half.Source: §6 · p. 7
  • Targeted suites built with the blind-spot taxonomy, per-family attack playbook, and input-validity ceiling killed 431 previously un-killed mutants with 94% suite validity.The gate rejected the remaining 6% of suites for ceiling violations.Source: §6 · p. 8
  • The measurement-derived taxonomy nearly triples detection over the fuzz baseline, rising from 21.6% to 61.0%; shown ten concrete mutants, the generator overfits them, whereas family-level knowledge generalizes across the pool.The comparison uses the identical task of killing 1,154 official-input survivors; the taxonomy rung accumulated more suites per problem, making its edge over the naive prompt an upper bound.Source: §6 · p. 8, Table 4 · p. 8

7 DOES DEPTH HIDE FAULTS?

Architecture-level checking is weaker than operator-scale checking, with blindness concentrated in deep homogeneous pipelines. Related work addresses checker weaknesses through patches or test augmentation, but the cited approaches do not measure kernel-benchmark oracle strength.

7 DOES DEPTH HIDE FAULTS?

  • 17.3% of witnessed architecture-level faults escape the official inputs versus 16.9% at operator scale; the distinct-mutant upper bound is 43.0% versus 25.7%, concentrated in deep homogeneous pipelines.VGG-19 and SqueezeNet each have 90% survival, while ResNet-18 and SwinMLP remain comparatively checkable despite depth.Source: §7 · p. 8, Figure 7 · p. 9

8 RELATED WORK

  • KernelBench, TritonBench, and related efforts patch or exploit kernel-checking weaknesses, but none measures oracle strength.KernelBench-Verified, robust-kbench, and The Correctness Illusion are among the cited patching efforts.Source: §8 · p. 9
  • Test-augmentation and RTL-audit work also assesses benchmark tests, but those domains lack graded numerical oracles and their tolerance-vacuity and validity-ceiling problems.The paper identifies these two mechanisms as distinguishing the kernel setting.Source: §8 · p. 9
  • Prior GPU mutation-testing work scores developer suites on hand-written kernels, without targeting benchmark oracles or validity-gating inputs against floating-point variance.Related compiler-testing work generates equivalent variants to expose miscompilation, unlike this paper’s inequivalent variants for weak checkers.Source: §8 · p. 10
  • Set-cover suite minimization and mutation-guided test generation are established lines of work that this paper situates alongside its approach.The cited suite-minimization work includes Harrold et al. (1993) and Yoo & Harman (2012).Source: §8 · p. 10

9 LIMITATIONS

The paper bounds its adequacy claims by the mutation fault model, substrate selection, hardware, and level-3 witness search. It also reports a small realism probe, reproducibility details, ethics scope, and a conclusion favoring measured checker coverage.

9 LIMITATIONS

  • Adequacy is relative to the fault model: the 124 rules on naive substrates omit tensor-core paths, double-buffered pipelines, some warp-level idioms, and multi-site interactions.The metric supports comparative and witnessed-fault claims, but cannot certify that a passing kernel is correct.Source: §9 · p. 10
  • Three of 60 LLM-written optimized kernels were incorrect; both runtime bugs fell within the taxonomy, though the bug sample was small.The exercise also exposed a harness blind spot triggered by launch-bounds-qualified kernels.Source: §9 · p. 10
  • Results use LLM-authored, gate-verified substrates and one GPU generation (H100); the level-3 study covers 48 of 50 architectures and has shallower witness search.The shallower search makes the architecture-level result a one-sided bound; tolerance is fixed at the benchmark’s 10^-2 setting.Source: §9 · p. 10

10 CONCLUSION

  • The conclusion presents mutation analysis as a way to measure checker coverage, explain misses, audit patches, and optimize suites for held-out faults.The paper says its fault taxonomy teaches a test generator more than raw faults alone and releases the pool, witnesses, suites, and pipeline as KernelBench-M.Source: §10 · p. 10

REPRODUCIBILITY STATEMENT

  • The measurement campaign used approximately 30 GPU-hours on a single NVIDIA H100 with PyTorch 2.7.1 and NVRTC 12.6.The paper states that released journals and scripts regenerate the kill matrix, protocol audit, and set-cover suites.Source: REPRODUCIBILITY STATEMENT · p. 11

ETHICS STATEMENT

  • The audit uses no human subjects, personal data, or deployed systems, and is intended to reduce rather than enable reward hacking.The paper says audited benchmarks and reimplemented patches are used under published terms.Source: ETHICS STATEMENT · p. 11

THE USE OF LARGE LANGUAGE MODELS

  • LLMs authored substrates, mutation-family mining, input suites, knowledge-ladder rungs, and realism-probe kernels, with outputs checked before contributing to results.The paper reports that all numbers derive from released journals and that no LLM output entered unverified.Source: THE USE OF LARGE LANGUAGE MODELS · p. 11

A OPERATOR INVENTORY: WHERE THE MISSES COME FROM

Officially missed faults vary sharply by mutation operator: arithmetic faults are usually caught, while precision and implementation-level faults often escape.

A OPERATOR INVENTORY: WHERE THE MISSES COME FROM

B MUTATION-RULE INVENTORY

The released mutator applies deterministic source rewrites organized into mutation families and developed in successive waves. The inventory spans arithmetic, indexing, synchronization, numerical-precision, and input-sensitive faults, with distinct mechanisms for why tests miss them.

B MUTATION-RULE INVENTORY

  • Each mutation rule is a deterministic source rewrite, and each match site yields a mutant; rules were added in three waves from base operators, survivor analysis, and numerically subtle sites.The rule brief used to guide mining ships with the artifact.Source: B MUTATION-RULE INVENTORY · p. 13
  • The Table 7 caption flags a count discrepancy: the released rule files load 120 unique rules, while the main text counts 124.Source: Table 7 · p. 14
  • Input-domain evasion occurs when original inputs conceal a change, such as positive values hiding a removed absolute value or tiny negative values exposing it.Other examples include thresholds, clamps, and reduction sentinels that differ only on particular input ranges.Source: B MUTATION-RULE INVENTORY · p. 14
  • Tolerance absorption hides small numerical changes, including omitted reduction terms and perturbed constants, unless inputs or tighter tolerances expose them.The inventory also describes shape-alignment evasion and benign races masked by similar lane values or redundant barriers.Source: B MUTATION-RULE INVENTORY · pp. 15–16
  • The listed rules include synchronization changes, wrong indexing or partner selection, and precision changes such as storing through an fp16 roundtrip.Examples include removing barriers, selecting a wrong block axis, and reading a wrong partner within a tree-reduction stage.Source: B MUTATION-RULE INVENTORY · pp. 14–17

C KNOWLEDGE LADDER: RAW COUNTS AND PROMPTS

This section reports raw kill counts for the knowledge ladder and documents the evaluated survivor sets and generation briefs.

C KNOWLEDGE LADDER: RAW COUNTS AND PROMPTS

  • R1 and R3 generate one suite file per problem per rung, while R3 excludes a problem after two CUDA-context crashes.The evaluator's crash re-entry guard skips that problem, excluding 62 survivors from R3 evaluation.Source: C KNOWLEDGE LADDER: RAW COUNTS AND… · p. 17
  • Table 8 reports survivors killed over survivors evaluated at each knowledge-ladder rung.All rungs target the same 1,154 official-input survivors across 30 problems; R3 is scored on 1,092 after excluding 62 survivors from a problem skipped by the evaluator.Source: Table 8 · p. 17, C KNOWLEDGE LADDER: RAW COUNTS AND… · p. 17
  • R1 and R3 use verbatim generator briefs, while R2 reuses the targeted-suite generation brief from §6.The invocation adds only the assigned problem name and substrate path.Source: C KNOWLEDGE LADDER: RAW COUNTS AND… · p. 17
Loading 2609.22220v1…