KernelOPT's Agentic Kernel Search: The Verification Cascade Works, The Speedup Fades With Difficulty

A September 2026 Red Hat paper sends a five-agent LLM system after GPU kernels — and the story is not the headline speedup, it is how fast the headline fades when problems get harder. KernelOPT: Dispatch-Aware Agentic Search for GPU Kernel Optimization (Poddar, Prasad, Samanta, Chakraborty and colleagues at Red Hat, arXiv:2609.30059, cs.DC, submitted September 24, 2026) reports geometric-mean speedups over torch.compile of 1.40× on KernelBench Level 1, 1.15× on Level 2, and 1.07× on Level 3 — across all problems per level, with the 51/100, 31/100 and 12/50 optimization counts in parentheses right next to them¹. Read those counts as part of the headline and the curve becomes the finding: per-problem pass rates fall from 71% (51 optimized + 20 matched) to 66% to 30% as difficulty rises, and the achieved speedup of the solved remainder falls in parallel¹.

That is the honest way this result should circulate, and to the paper's credit it largely does: outcome categories are reported explicitly, fallbacks preserve the compiler baseline at 1.0× by design, and the paper's own all-250 geomean is 1.23× — below every level headline, exactly the pattern a pass-rate-weighted fade produces. What this guide adds is the arithmetic: which denominator the numbers use, what the fade looks like when you plot effective speedup against pass rate, the Amdahl-style ceiling that vendor-library preservation imposes (61 of 85 fallbacks are pure cuBLAS/cuDNN dominance — the structural reason Level 3 gains so little), and why the paper's four-gate verification cascade — especially the float64-fallback model-level check — is the part most likely to outlive the benchmark numbers.

1. What KernelOPT is: structure-respecting, not black-box

The background fact everything else follows from: a model compiled by PyTorch Inductor is not one kernel. It is a structured artifact in which the compiler has already made dispatch decisions — cuBLAS for GEMM, cuDNN for convolution, Triton for the pointwise and reduction glue in between¹. The compiler's library dispatch decisions are typically sound; what is suboptimal is the quality of the remaining Triton code. Earlier LLM kernel optimizers (KernelAgent, AccelOpt, K-Search) generally treat a model as a black box and optimize kernels one at a time, without respecting those dispatch decisions or verifying the re-stitched model end-to-end¹.

KernelOPT takes the structure seriously. In multi-kernel mode it runs torch.compile with max_autotune, detects the extern library calls by regex over the Inductor output, flags them as needs_triton_replacement: False, and never touches them. The five agents — planner, executor, summarizer (the AccelOpt triad²), plus a profiler agent and a deterministic strategy analyst — work exclusively on the Triton-generated sub-kernels and on fusible groups of them. The profiler runs NVIDIA Nsight Compute at --set full with kernel replay and distills the report into Speed-of-Light throughput, duration, register pressure, occupancy and the top-3 NCU rules ranked by estimated speedup; the strategy analyst classifies the bottleneck tier deterministically (near-optimal if any SOL exceeds 80%, memory-bound, compute-bound, or underutilized)¹. The planner proposes up to N plans per iteration inside a beam search (UCB with c = 1.4) over a rooted tree of kernel states; the executor receives compile errors and correctness failures as in-conversation feedback with up to K retries; a meltdown detector forces diversity when the last six plan directions collapse to two or fewer unique approaches¹. Hyperparameters are fixed across all 250 problems with no per-level tuning: T = 5 iterations, N = 4 plans, K = 4 retries, beam width B = 4 — on a single H200 with Claude Sonnet 4.6, roughly 1,100 GPU-hours total, individual models ranging from 6 minutes to 66 hours¹.

Why fix cuBLAS and cuDNN in place instead of letting the LLM rewrite them too? Because the alternative is measured and it is bad. The ablation study removes exactly one component at a time on 50 sampled problems: removing beam search or NCU profiling drops optimization success from 38% to 10%, removing the perf gate to 6% — and removing Inductor-aware synthesis (on Level 2 only) drops it to zero out of 20, because the LLM burns every attempt trying to replace hand-tuned vendor-library calls and produces "pervasive regressions"¹. The paper's own conclusion from this is exactly right and refreshingly anti-hype: the efficacy rests on structural orchestration, not on the LLM's raw coding ability.

2. The four-gate cascade: why the fallback baseline survives

The verification function is the heart of the paper. Formally, the problem is argmin over the (intractable) space of syntactically valid Triton programs of kernel wall-clock time, subject to a verification predicate — and crucially, if no candidate satisfies the predicate, the system returns the compiler baseline unchanged¹. The predicate is a conjunction of four gates, applied sequentially:

1. Static validation — dry-run execution catches syntax errors and crashes before any numerical comparison.
2. Multi-seed correctness — three random seeds, allclose at rtol/atol 10^-3 against the eager PyTorch reference, loose enough to admit valid TF32 candidates during search; failures feed straight back to the executor as in-conversation error messages.
3. Model-level correctness (V_model) — after optimization, the re-stitched whole model is checked end-to-end at the stricter 10^-4 tolerance, with the float64 fallback this guide comes to in section 5. Because Inductor externalizes model parameters as explicit kernel arguments, a naive input generator would fill weights with random values and produce meaningless outputs; KernelOPT captures the exact flat argument list with a backend-capture trick so real model state flows through verification¹.
4. Performance gate (V_perf) — the wall-clock time of the re-stitched model must come in at or under gamma = 1.03 times the compiled baseline's time, measured with subprocess-isolated do_bench (25 ms warmup, 100 ms rep) so CUDA state cannot leak between measurements¹.

Gate 4 is the component most systems in this lineage lack, and the paper demonstrates its necessity concretely: all 15 Level-1 performance-gate rejections were kernels that were genuinely faster per kernel — up to 5.84× per-kernel NCU improvement on kernel 049 — but marginally slower as a model, because replacing an Inductor-fused path with a standalone Triton kernel re-introduces dispatch overhead. Without the gate those 15 would have shipped as "improvements." With it, they become honest fallbacks¹. That is the whole design philosophy in one gate: better to return the compiler's answer than to report a win that an end-to-end measurement refutes.

3. The headline, checked: which denominator, and what the fade means

The abstract states the geomeans "across all problems" — and the paper's own outcome definitions make this load-bearing rather than a flourish: a Matched result "replaces the baseline and contributes its measured speedup to the geometric mean," synthesis failures return the Inductor AOT baseline "which matches the compiler baseline," and fallbacks are rejected candidates whose problems keep the 1.0× compiler output¹. So unsolved problems enter the mean at 1.0× by construction. The cell below reconstructs all three level geomeans from the paper's own Table 1 — the outcome counts of Panel A plus the speedup histogram of Panel B — to confirm which denominator reproduces the reported numbers, and then lays out the fade explicitly.

import math
 
# Reconstruct the reported geomeans from the paper's own Table 1:
# Panel B histogram of the 94 optimized kernels (per-level counts, bucket
# midpoints as proxies) + Panel A outcome counts. Unsolved problems keep
# the torch.compile baseline, i.e. they enter the geomean at 1.0x.
buckets = [(">=10x", [4, 1, 0], 20.0), ("[5,10x)", [6, 4, 0], 7.0),
           ("[2,5x)", [7, 0, 2], 3.2), ("[1.5,2x)", [2, 2, 1], 1.7),
           ("[1.1,1.5x)", [8, 8, 4], 1.27), ("[1.01,1.1x)", [24, 16, 5], 1.05)]
# per level: N, (optimized, matched-opt, synth-fail, fallback), reported geomean
LEVELS = [("L1", 100, (51, 20, 13, 16), 1.40),
          ("L2", 100, (31, 35, 0, 34), 1.15),
          ("L3", 50, (12, 3, 0, 35), 1.07)]
 
gm = lambda vals: math.prod(vals) ** (1 / len(vals))
print(f"{'level':5} {'reported':>9} {'all-N midpoint':>14} {'solved-only':>12}")
for li, (lv, N, (opt, mopt, sf, fb), reported) in enumerate(LEVELS):
    vals = [mid for _, per, mid in buckets for _ in range(per[li])]
    all_n = vals + [1.0] * (N - len(vals))      # unsolved at 1.0x
    solved = vals + [1.0] * max(opt + mopt - len(vals), 0)
    print(f"{lv:5} {reported:8.2f}x {gm(all_n):13.2f}x {gm(solved):11.2f}x")
 
print()
print("pass rates and the per-level fade, unsolved = 1.0x by design:")
for lv, n, k, geo in (("L1", 100, 71, 1.40), ("L2", 100, 66, 1.15),
                      ("L3", 50, 15, 1.07)):
    print(f"  {lv}: passed {k}/{n} = {k / n:4.0%}, level geomean {geo:.2f}x")
allp = 1.40 ** 100 * 1.15 ** 100 * 1.07 ** 50
print(f"  paper All-250 geomean: {allp ** (1 / 250):.2f}x < every level headline")

Output from a real run (Python 3, deterministic, no RNG):

level  reported all-N midpoint  solved-only
L1        1.40x          1.43x        1.66x
L2        1.15x          1.16x        1.25x
L3        1.07x          1.08x        1.31x
 
pass rates and the per-level fade, unsolved = 1.0x by design:
  L1: passed 71/100 =  71%, level geomean 1.40x
  L2: passed 66/100 =  66%, level geomean 1.15x
  L3: passed 15/50 =  30%, level geomean 1.07x
  paper All-250 geomean: 1.23x < every level headline

The reconstruction confirms the reading: only the all-problems denominator (unsolved at 1.0×) reproduces the reported geomeans within histogram-midpoint error. The solved-only alternative would have to produce 1.66×/1.25×/1.31× — noticeably above every reported number — so the paper is not quietly giving us a cherry-picked denominator; the fade is inside the reported numbers. But the reporting still deserves one honest footnote: the parenthetical "(51/100)" in the abstract counts only the Optimized category, while the geomean includes the 20 Matched(results near 1.0×) too — and the heavy tail does a lot of work. Five of the biggest wins are Level-1 algebraic rewrites — a diagonal matmul recognizing O(N^3) → O(N^2) structure (88.63×), triangular-matrix operands with skip-zero iteration (20.26×, 14.04×), batched-diagonal structure (11.38×), symmetric-matrix structure (8.65×)¹ — cases where Inductor dispatches a generic cuBLAS GEMM for a problem that has exploitable mathematical structure. These are exactly the problems a compiler's fixed pattern-match set cannot see and an LLM can, and they say something important about where the remaining wins live: less in scheduling micro-optimization than in recognizing problem structure the compiler treats generically.

The fade itself has two multiplying factors, and they compound: the pass rate falls (71% → 66% → 30%) and the speedup achievable on what passes falls (1.40× → 1.15× → 1.07×). On Level 3 — 50 full model architectures from 3-layer MLPs to 259-kernel LLaMA variants — the system produces twelve optimized and three matched results and hands 35 of 50 problems back to the compiler. The next section is why that is structural, not a prompt-engineering shortfall.

4. The ceiling: library dominance and Amdahl on a preserved dispatch graph

Preserving vendor calls is what makes KernelOPT robust — and it is also what bounds it. Of the 85 fallbacks across all levels, 61 are library dominance: 37 GEMM-dominant (28 L2, 9 L3) where cuBLAS matmuls consume the majority of wall time and only thin Triton epilogues (under 1% of runtime) remain optimizable, and 24 Conv-dominant (6 L2, 18 L3) where cuDNN dominates in VGG-, ResNet-, EfficientNet- and MobileNet-style models¹. In the GEMM-dominant cases the agents do produce faster epilogue kernels — and the re-stitched model still comes out slower, because the epilogue dispatch overhead eats the sub-1% opportunity. The performance gate converts every one of those into a baseline-preserving fallback rather than a false win.

This is Amdahl's law applied to a dispatch graph with a frozen region, and it deserves exact numbers. If vendor calls take fraction f of the model's wall time and remain exactly as they are, and the LLM makes the remaining Triton sub-kernels S times faster, the model-level speedup ceiling is 1/(f + (1-f)/S). No amount of agent iteration moves f, because moving f would mean replacing cuBLAS with LLM-written Triton — which the ablation shows collapses to zero successes and pervasive regressions. The cell puts the search's structural ceiling in numbers, including the per-kernel speedup demanded just to clear the 3% performance-gate margin — trivial while f is moderate, but diverging as f approaches 1/gamma ≈ 97.1%, beyond which no Triton speedup, however large, buys a measurable model-level gain:

import math
 
def ceiling(f, S):
    # Amdahl with a frozen vendor region of fraction f,
    # Triton remainder sped up by factor S.
    return 1.0 / (f + (1.0 - f) / S)
 
print("graph-level ceiling vs vendor fraction f, Triton speedup S:")
print(f"{'f':>5} " + " ".join(f"{'S=' + str(s):>7}" for s in (2, 5, 10, 100)))
for f in (0.5, 0.7, 0.8, 0.9, 0.95, 0.99):
    row = [ceiling(f, S) for S in (2, 5, 10, 100)]
    print(f"{f:4.0%} " + "  ".join(f"{c:6.2f}x" for c in row))
 
print()
print("the paper's < 1% epilogue case (GEMM-dominant fallbacks, f = 99%):")
for S in (10, 100):
    print(f"  epilogue {S}x faster -> model {ceiling(0.99, S):.4f}x "
          f"(gate margin gamma = 1.03 not even approached)")
 
print()
print("Triton speedup S required for a model-level 1.03x (gate threshold):")
print("from 1.03 = 1/(f + (1-f)/S):")
for f in (0.3, 0.5, 0.7, 0.9, 0.95):
    # solve 1.03 = 1/(f + (1-f)/S) for S:
    #   f + (1-f)/S = 1/1.03  =>  S = (1-f)/(1/1.03 - f)
    S = (1.0 - f) / (1.0 / 1.03 - f)
    print(f"  f = {f:4.0%}: S = {S:8.1f}x")

Output from a real run (Python 3, deterministic):

graph-level ceiling vs vendor fraction f, Triton speedup S:
    f     S=2     S=5    S=10   S=100
 50%   1.33x    1.67x    1.82x    1.98x
 70%   1.18x    1.32x    1.37x    1.42x
 80%   1.11x    1.19x    1.22x    1.25x
 90%   1.05x    1.09x    1.10x    1.11x
 95%   1.03x    1.04x    1.05x    1.05x
 99%   1.01x    1.01x    1.01x    1.01x
 
the paper's < 1% epilogue case (GEMM-dominant fallbacks, f = 99%):
  epilogue 10x faster -> model 1.0091x (gate margin gamma = 1.03 not even approached)
  epilogue 100x faster -> model 1.0100x (gate margin gamma = 1.03 not even approached)
 
Triton speedup S required for a model-level 1.03x (gate threshold):
from 1.03 = 1/(f + (1-f)/S):
  f =  30%: S =      1.0x
  f =  50%: S =      1.1x
  f =  70%: S =      1.1x
  f =  90%: S =      1.4x
  f =  95%: S =      2.4x

The table explains the fade without any appeal to "harder problems confuse the LLM." Level-1 problems are single operators; some have exploitable algebraic structure (the tail wins) and many are pointwise/reduction kernels where the Triton share of runtime is near 100% — so f is small and the ceiling is generous. Level-3 problems are full architectures whose runtime is dominated by matmuls and convolutions the system forbids itself from touching: f is large, the ceiling collapses toward 1.0×, and the required per-kernel speedup explodes on approach to the 97% wall (at f = 95% it already takes a 2.4× Triton rewrite to buy a 3% model-level gain (34× at f = 97%)). The paper's conclusion gestures at the right next step — tuning vendor library configurations (algorithm selection, workspace size, math mode) rather than replacing the calls — and notes that since 72% of fallbacks arise from cuBLAS/cuDNN dominance, that is where the recoverable performance actually lives¹.

This is also the fair benchmark caveat: 1.07× on Level 3 is a small gain on precisely the problem class production inference cares about, and it is bounded by design choices that are nonetheless correct — the ablation proves the alternative is zero wins plus regressions.

5. Why float64 model-level verification: compounding per-kernel noise

The most technically interesting gate is Gate 3's float64 fallback, and it addresses a failure mode that per-kernel testing structurally cannot see: error propagation through the graph. Gate 2 checks each candidate kernel in isolation against the eager reference at a loose 10^-3 tolerance across three seeds — fine for filtering broken candidates during search. But a compiled model is a chain: small per-kernel numerical deltas that individually sit far inside tolerance can compound through depth, and conversely a correct kernel using TF32 tensor cores can fail a naive strict comparison that a baseline-order-dependent artifact would pass.

KernelOPT's Gate 3 handles both directions with an error ratio rather than an absolute threshold. It computes three outputs: the optimized kernel's FP32 output, the baseline kernel's FP32 output, and the baseline kernel's FP64 output as a high-precision reference. Then d_ref is the L^inf distance between the two baselines (FP32 minus FP64 — the baseline's own FP32 rounding error) and d_opt is the distance from the optimized FP32 output to the FP64 reference. When d_ref is at least 10^-8, the error ratio rho = d_opt/d_ref is compared against a bound of 10: correct TF32 kernels land in rho roughly between 1 and 3 (different-but-legitimate FP32 accumulation orders), algorithmically incorrect kernels land above 100 — three orders of magnitude of separation, which is why a single threshold works¹. When d_ref is below 10^-8 (exact operations like max or argmax, where any deviation is a real bug) the check falls back to a scale-relative comparison, and an absolute bound handles fused kernels whose separated-operation reference anchors precision artificially¹.

Why is the FP64 reference necessary rather than simply comparing optimized FP32 against baseline FP32? Because both are noisy around the true value, and the structured question is not "do they match" but "is the optimized kernel's deviation from truth in the same band as the baseline's own deviation." The cell simulates exactly this: a depth-d chain of numerically benign stages (each stamping elements with a few ULP32 of relative error — trivially inside per-stage tolerance), against both a noise-free reference and a bugged alternative that adds a systematic half-epsilon-per-stage bias that any single-stage 10^-3 test waves through:

import random, math
 
random.seed(260930059)
ULP = 2.0 ** -23             # float32 unit in the last place
 
def chain_error(depth, u0, trials=400, n=256):
    """Max end-to-end relative error over trials chains of depth stages.
    Each stage multiplies every element by (1 + U(-u0, u0)); the
    noise-free twin provides the reference value."""
    worst = 0.0
    for _ in range(trials):
        noisy = quiet = 1.0
        for _ in range(depth):
            noisy *= 1.0 + random.uniform(-u0, u0)  # one noisy stage
            quiet *= 1.0                              # noise-free twin
        worst = max(worst, abs(noisy - quiet) / quiet)
    return worst
 
print("per-stage relative noise: U(-3 ULP32, +3 ULP32) ~ 3.6e-07")
print("one such stage passes allclose(rtol=1e-3, atol=1e-3) ~1000x over")
print(f"{'depth d':>8} {'mean of 5 runs, max rel E2E error':>32}")
for d in (1, 4, 12, 32, 64):
    vals = [chain_error(d, 3 * ULP) for _ in range(5)]
    print(f"{d:8d} {sum(vals) / len(vals):32.2e}")
 
print()
print("Gate 3's error ratio for (a) an honest chain, (b) a chain with a")
print("systematic +5e-4/stage bias -- a bug a per-stage 1e-3 test accepts:")
d_ref = sum(chain_error(32, 3 * ULP) for _ in range(50)) / 50
d_honest = chain_error(32, 3 * ULP)
d_bugged = d_ref + 32 * 5e-4                     # bias accumulates linearly
print(f"  honest : rho = {d_honest / max(d_ref, 1e-30):7.2f}   (paper band: 1..10, accept)")
print(f"  bugged : rho = {d_bugged / max(d_ref, 1e-30):7.0f}   (paper band: >100, reject)")

Output from a real run (Python 3, seed 260930059):

per-stage relative noise: U(-3 ULP32, +3 ULP32) ~ 3.6e-07
one such stage passes allclose(rtol=1e-3, atol=1e-3) ~1000x over
 depth d mean of 5 runs, max rel E2E error
       1                         3.57e-07
       4                         1.08e-06
      12                         2.28e-06
      32                         3.64e-06
      64                         5.38e-06
 
Gate 3's error ratio for (a) an honest chain, (b) a chain with a
systematic +5e-4/stage bias -- a bug a per-stage 1e-3 test accepts:
  honest : rho =    1.10   (paper band: 1..10, accept)
  bugged : rho =    4502   (paper band: >100, reject)

Two readings. First, the honest chain's end-to-end error grows roughly with sqrt(depth) (random signs cancel; 3.6e-7 per stage becomes about 3.6e-6 at depth 32) — real compounding, but two orders of magnitude below any tested tolerance, and crucially the same size as the baseline's own deviation from truth, which is what rho near 1 means and why the honest kernel passes. Second, the bugged chain: each stage adds only 5e-4 of systematic bias — half the per-stage tolerance, individually undetectable — but bias accumulates linearly with depth while cancellation keeps the honest noise band tiny, so at depth 32 the ratio lands in the thousands, far past the 100 band that the paper reports for algorithmically incorrect kernels. A per-kernel test at 10^-3 accepts every stage of that chain; only a model-level measurement against a float64 reference sees the difference between noise and bias. For a 259-kernel LLaMA variant, this is not a corner case — it is the difference between a verification scheme that can detect wrong fast kernels and one that can only detect broken ones. The paper's own E2E numbers confirm the gate is not merely decorative: only 2 of 250 problems fail at Gate 3, which is the verification working as intended — bad candidates mostly die earlier at the cheaper gates.

6. What generalizes, what does not

The fair summary is two sentences. As an engineering result, KernelOPT is the strongest evidence yet that LLM kernel optimization needs structure: dispatch-awareness alone is the difference between 38% and 0% success, NCU guidance and beam search each eliminate 74% of the optimizations (19 → 5), and the four-gate cascade turns the field's usual reporting bias (correct-per-kernel-but-slower-model wins get reported anyway) into measured, baseline-preserving fallbacks¹. As a performance result, it quantifies the agentic fade honestly: 1.40× when problems are Triton-shaped, 1.07× — barely above noise — when problems are GEMM-shaped models, and the mechanism is not the LLM getting confused but a frozen vendor region that Amdahl prices exactly.

The caveats are the usual ones plus one design-specific limit. The study is single-GPU inference on one H200 with one frontier LLM, no comparison numbers against other tools (deliberately — hardware and framing differences make metric transfer invalid, the authors argue), NCU profiling requires elevated GPU counter permissions and drives roughly 60 K tokens per profiling prompt, and the beam-based search is not cheap (roughly 1,100 GPU-hours for 250 problems)¹. The guidelines in the repo were extracted after the evaluation and ship as cold-start context, so they are not responsible for the reported numbers — a disclosure the paper makes unprompted and which speaks well of its hygiene.

What this space should be judged on going forward, if the fade is the finding, is not headline geomeans at all. It is whether the approach can move f — either by safe vendor-library configuration search (the paper's own proposed direction: cuBLAS algorithm selection, workspace size, math mode), or by formal-verification-backed replacement of library calls, which is a much harder problem than Triton-sub-kernel rewriting. Until then, expect the honest composite number — 1.23× over all 250 problems, dominated by the Level-1 tail — and not the 1.40×, to be what production reuse actually delivers.