KREX: Shared-GPU Kernel Benchmarking Without Corrupting the Agent's Search

The kernel-agent wave has an unexamined dependency: every agent — OpenAI's AlphaEvolve-style systems, KernelBench leaderboards, Alibaba's production fleet — closes its loop through one primitive, measure this kernel's duration on a real GPU. A September 2026 paper from HKUST and Alibaba Group, KREX: Concurrent Kernel Benchmarking on Shared GPUs via Region-Granular Exclusivity (Tianyu Feng, Haoxuan Yu, Tianyuan Wu, Lingyun Yang, Daocheng Ying, Yuxiao Wang, Ruibo Fan, Yinghao Yu, Guodong Yang, Liping Zhang, Wei Wang, arXiv:2609.30057, cs.DC, September 24, 2026) starts from the operational scale of that primitive: their production environment runs over 300,000 kernel-benchmarking jobs per day across six GPU models from three vendors¹. And it names the coupling precisely: measurement fidelity is bought today by not sharing, which at this scale is enormous waste — because almost none of a benchmarking command actually needs the GPU alone.

The anti-hype framing the paper earns rather than claims: a corrupted measurement is not "slightly noisy data." It is a wrong gradient for an agent that walks whichever direction the numbers point. A slow benchmark wastes an iteration; a wrong benchmark actively optimizes toward noise, and the agent will happily keep the slower kernel because the measurement said it was faster. The paper's own fleet data has the smoking gun: under unprotected sharing, replayed benchmark durations inflate to 1.5×–3.2× their uncontended values (eight commands per GPU), and the inflation is colocated-workload-dependent — meaning it does not cancel in candidate comparisons. In one recorded trajectory of an agent optimizing an MoE token-alignment kernel, six of ten pairwise rankings among near-tied candidates reversed under sharing; the best candidate (truly 49.0 μs vs. the rival's 50.3 μs) measured worse (53.9 μs vs. 49.3 μs). The agent's search was not slowed; it was misdirected¹.

1. Where a benchmarking command actually spends its time

Strip a typical agent benchmarking command — import frameworks, compile the candidate kernel, generate inputs, check correctness against the reference, then time it — into phases, and the exclusivity requirement falls out of the structure:

• Framework imports and kernel compilation never touch the GPU at all.
• Input generation and correctness checks use the GPU, but a colocated workload can only delay them; it cannot change the tensors produced or the correctness verdict returned.
• Only the timed loop is load-sensitive: its output is the number the agent optimizes.

The paper's profile of a representative agent workload on their testbed: startup and compilation account for 81% of a command's median duration, the correctness check for 10%, and the timed loop for only 8.5% — 0.22 s out of a 2.6 s command¹. At command-granular exclusivity, the GPU is reserved for the entire 2.6 s to protect 0.22 s. A larger sample (1,069 commands from one hour of KREX-serial execution on an NVIDIA H20) puts the median critical-region fraction at 12%, with 73% of commands below 25%; per suite medians are 4.4% (KernelBench), 18.2% (FlashInfer-Trace), 22.7% (Atrex-Bench)¹.

And the coarser alternative is worse: session-granular reservation (one agent holds a GPU for its whole session) yields 3.4% device utilization in their profiled session, because GPU commands occupy 19.3% of wall-clock time and the device is active for only 17.4% of that¹.

2. Why naive sharing doesn't just slow agents — it points them the wrong way

Kernel agents rank candidates by relative measured duration. Contention noise doesn't average out of that comparison for two reasons the paper states explicitly. First, contention tends to inflate durations, so repeating measurements doesn't recover the uncontended value. Second, the inflation varies with colocated workloads, so it acts differently on the two candidates being compared — a bias, not a variance, in the comparator.

The hill-climbing arithmetic is brutal because real candidate gaps are small. When an improved candidate is 2–5% faster than its parent, and measurement noise is of the same order, the comparator's sign flips with substantial probability, and the agent accepts regressions believing them to be improvements. A small simulation of exactly this loop two candidate distributions with overlapping noise bands, Gaussian-average proxy, greedy accept-if-measured-faster:

# Cell 1: how measurement noise flips candidate rankings and misdirects a greedy search
import random
 
# Pairwise flips: candidate B is truly `gap` slower; the toy model averages
# N independent timed launches; per-launch relative noise ~ N(0, sigma).
def flip_rate(gap, sigma, n_launches, trials=20000, seed=2026):
    rng = random.Random(seed + int(gap * 1000) + int(sigma * 1000) + n_launches)
    eff = sigma / (n_launches ** 0.5)
    flips = 0
    for _ in range(trials):
        ma = 1.0 * (1 + rng.gauss(0, eff))
        mb = (1.0 + gap) * (1 + rng.gauss(0, eff))
        if mb < ma:
            flips += 1
    return flips / trials
 
print("P(measured ranking flips): B truly +gap slower, Gaussian average of N launches")
print("")
print(f"{'true gap':>9} {'sigma':>6} {'N=1':>7} {'N=10':>7} {'N=100':>7}")
for sigma in (0.01, 0.03, 0.05):
    for gap in (0.02, 0.03, 0.05):
        r1 = flip_rate(gap, sigma, 1)
        r10 = flip_rate(gap, sigma, 10)
        r100 = flip_rate(gap, sigma, 100)
        print(f"{gap*100:>8.0f}% {sigma*100:>5.0f}% {r1*100:>6.1f}% {r10*100:>6.1f}% {r100*100:>6.1f}%")
 
# Greedy hill-climb: accept a proposal only if its MEASURED duration beats the
# measured best. Proposals truly improve by 0-2% or regress by 0-5%.
def greedy(sigma, iters=500, seed=2026):
    r = random.Random(seed + int(sigma * 1000))
    best_true = 1.0
    wasted = 0
    for _ in range(iters):
        delta = r.uniform(-0.05, 0.02)
        cand_true = best_true * (1 + delta)
        m_best = best_true * (1 + abs(r.gauss(0, sigma)))
        m_cand = cand_true * (1 + abs(r.gauss(0, sigma)))
        if m_cand < m_best:
            if cand_true > best_true:
                wasted += 1
            best_true = cand_true          # agent trusts the measurement
    return wasted
 
print("")
print("Greedy hill-climb, 500 proposals, one measured comparison per proposal")
print("")
print(f"{'sigma':>6} {'regression accepts in 500 proposals':>36}")
for sigma in (0.01, 0.02, 0.04):
    w = greedy(sigma)
    print(f"{sigma*100:>5.0f}% {w:>36}")

P(measured ranking flips): B truly +gap slower, Gaussian average of N launches
 
 true gap  sigma     N=1    N=10   N=100
       2%     1%    8.0%    0.0%    0.0%
       3%     1%    1.9%    0.0%    0.0%
       5%     1%    0.0%    0.0%    0.0%
       2%     3%   31.6%    7.4%    0.0%
       3%     3%   24.4%    1.4%    0.0%
       5%     3%   12.5%    0.0%    0.0%
       2%     5%   38.9%   18.7%    0.2%
       3%     5%   33.7%    9.2%    0.0%
       5%     5%   24.3%    1.3%    0.0%
 
Greedy hill-climb, 500 proposals, one measured comparison per proposal
 
 sigma  regression accepts in 500 proposals
    1%                                   29
    2%                                   50
    4%                                   59

The second table counts regression acceptances among 500 proposals: 29 with 1% noise and 59 with 4% noise in this toy run. It does not claim that 29 or 59 of the accepted proposals were regressions. The first table uses an independent Gaussian mean proxy, not the median used by many real harnesses; its 1/√N reduction applies to random noise, not to contention bias. At 3% modeled single-shot noise and a 2% true gap, the proxy flip rate is 31.6% with N=1 and 7.4% with N=10. The paper's trajectory replay shows the same shape empirically: KREX's pairwise flip rates stay within three percentage points of an uncontended native repeat in every gap bucket, while unprotected sharing drags per-trajectory Kendall's τ (rank correlation) down to a median of 0.432 versus 0.820 for the native repeat itself, with KREX at 0.857¹².

3. KREX in one paragraph: exclusivity only where timing lives

KREX's interface is deliberately small: mark the critical region — the timing phase — and mark it completely; the runtime enforces the boundary for the whole command (requirement R1 in the paper), without modifying the kernel under test. Entering a region triggers a four-part handshake per GPU: block new competing GPU submissions (a shared-memory gate with epoch tagging, checked on every operation that could leave work on the device); drain outstanding GPU work from siblings (in-flight counters in each context process, so a racing submission is either covered by the drain or blocked before reaching the driver); freeze sibling process trees (per-tenant freezer cgroups, so a sibling's host thread cannot preempt the measuring threads and delay kernel launches); and pin the measuring command's submitting threads to reserved CPU cores — physical cores are partitioned into disjoint per-GPU slices for the whole run, because CPU contention alone measurably inflates reported durations¹. Outside marked regions, concurrent commands execute freely, backed by persistent context processes that hold pre-created GPU contexts and forward driver calls over asynchronous IPC. That last piece is not decoration: creating a CUDA context acquires a node-wide driver lock ("creating 64 CUDA contexts on one server takes more than 30 seconds even when requests are issued concurrently across different GPUs"), so under the per-command process model, command admission serializes across the entire node¹. Context pooling removes the recurring cost and is worth ~9% throughput on its own (KREX-serial at 17.5 cmds/min vs. native 16.0 on H20)¹.

4. The arithmetic of region-granular exclusivity

Why does confining exclusivity to 8.5–12% of a command suffice for fidelity and pay 3.4× in throughput? Because exclusivity is only expensive when held over the non-timing phases, and off-region concurrency is only cheap if the queueing structure lets commands actually overlap. The paper's steady-state numbers, with a toy model of the two constraints amortization of the serial critical fraction and the region-bound ceil:

# Cell 2: where a benchmarking command's wall-time actually goes, and what
# region-granular exclusivity recovers (numbers from arXiv:2609.30057v1)
import random
 
# KREX Fig. 1a: median command is 2.6 s: startup+compile 81%, correctness 10%,
# timed loop 8.5% (0.22 s). Fig. 6b (1069 commands on H20): median critical-
# region fraction 12%, 73% of commands below 25%; KernelBench 4.4%,
# FlashInfer-Trace 18.2%, Atrex-Bench 22.7%.
median_fractions = {"KernelBench": 4.4, "FlashInfer-Trace": 18.2,
                    "Atrex-Bench": 22.7, "all commands (median)": 12.0, "73rd pct": 25.0}
 
# Utilization perspective: session-granular reservation (E1) yields 3.4% GPU
# utilization because GPU commands cover only 19.3% of wall-clock and the
# device is active only 17.4% of that.
cmd_wall = 0.193
dev_active_of_cmd = 0.174
print(f"E1 session-granular reservation utilization: {cmd_wall * dev_active_of_cmd:.3f}x -> {cmd_wall * dev_active_of_cmd * 100:.1f}%")
 
# Simplified steady-state model of one GPU: on command-granular exclusivity
# (E2), commands of median duration D = 10.2 s (H20, Fig. 6a) run one at a
# time; with region-granular exclusivity (E3), the critical 12% stays serial
# but the rest (88%) can be overlapped by up to C colocated commands.
D = 10.2
frac = 0.12
for C in (1, 2, 4, 8, 16):
    # Optimistic Amdahl-style throughput proxy: serialize the marked fraction,
    # overlap the remainder across C commands. It does not model queueing,
    # GPU work outside regions, CPU contention or setup costs.
    per_cmd = D * (frac + (1 - frac) / C)
    print(f"C={C:2d}: effective resource time {per_cmd:5.2f} s "
          f"-> {D / per_cmd:4.1f}x E2 throughput (toy upper bound)")

E1 session-granular reservation utilization: 0.034x -> 3.4%
C= 1: effective resource time 10.20 s ->  1.0x E2 throughput (toy upper bound)
C= 2: effective resource time  5.71 s ->  1.8x E2 throughput (toy upper bound)
C= 4: effective resource time  3.47 s ->  2.9x E2 throughput (toy upper bound)
C= 8: effective resource time  2.35 s ->  4.3x E2 throughput (toy upper bound)
C=16: effective resource time  1.79 s ->  5.7x E2 throughput (toy upper bound)

The toy's serial-region floor is D × 12% = 1.22 s per command, or at most 8.3× the exclusive-command rate even with unlimited overlap. At C=16 it predicts 5.7× under optimistic assumptions, while KREX measures 54.8 versus 17.5 commands/min, or 3.1× over KREX-serial on H20. The median 12% critical fraction is not a constant per command; real off-region GPU work, CPU and context overheads, and queueing also limit throughput. The measured result is 3.4× over native on H20 and 2.6× on MI308X¹. Note also the ungated-sharing datapoint: with no protection at all, sharing on H20 reaches only 41.9 cmds/min, below KREX's 54.8, because KREX additionally uses MPS to improve off-region concurrency — corruption and throughput are not even in a clean trade-off here; the unprotected configuration loses on fidelity and can lose on throughput too¹.

5. Fidelity: the numbers, and why short kernels are structurally worse

The headline fidelity result on the throughput-optimized configuration: p95 timing inflation of 0.30% / 1.58% / 3.90% for kernels longer than 10 ms / 1 ms / 0.1 ms, measured against uncontended native references, as summarized in the paper abstract¹. On the >1 ms band the paper reports full distributions: P = 2.5% on H20 and 2.4% on MI308X, versus 154% and 150% for ungated sharing. Ablations show GPU protection (the gate/drain) provides most of that, and adding CPU protection drops single-shot p95 shift from 840 μs to 296 μs in the forwarding microbenchmark¹.

The paper's abstract reports p95 timing inflation for three nested kernel-duration cohorts:

These cohorts contain different kernels and overlap. Their lower bounds are not representative durations, so dividing the p95 percentages cannot test a fixed-overhead 1/d model or attribute the difference to sharing. Figure 8's selected throughput configurations report 2.5% on H20 and 2.4% on MI308X for >1 ms commands; those are a different aggregation from the abstract's 1.58%¹. Below 0.1 ms, even the native repeat has P = 12.1% on H20 and 7.6% on MI308X. That native variability makes small candidate gaps hard to rank reliably; KREX's H20 pairwise flip rates nonetheless stay within three percentage points of the native repeat in the studied gap buckets¹. Repeat timings and report uncertainty when a candidate gap is small.

6. What to keep and what to hedge

Keep: region marking as an interface is the right abstraction — it makes the fidelity contract explicit and cheap to enforce, and the paper demonstrates the machinery (in-flight counters, epoch-tagged gates, freezer cgroups, core slices) works across two vendors with a shared protocol. The throughput claims survive replay: 3.4×/2.6× vs. command-granular native, at inflation under 4% even on the shortest band, and the ranking-preservation experiment is the one an agent operator actually cares about¹.

Hedge: the trust boundary. KREX assumes cooperative candidates; regions are marked by the benchmarking code's author, and the paper states plainly that pool timeouts limit abuse but do not prevent it¹. A region can be drawn too narrowly (leaving load-sensitive work outside it) or too generously (re-creating command-granular exclusivity for your own commands); the runtime enforces what is marked, not what is true. The paper names region-level fairness and region-access starvation as unsolved scheduling problems — slot-based admission provides no per-tenant region-fairness guarantee¹. And AMD's configuration forgoes context pooling because the fidelity cost is greater than on NVIDIA, which is why MI308X lands at 2.6× rather than 3.4×: the mechanism is portable, the efficiency is hardware-tuned.

The general lesson outlives the system: in agentic optimization loops, the measurement primitive is the gradient. Sharing hardware without protecting the measured interval doesn't degrade the loop — it inverts the direction of travel for every decision made on a polluted number. KREX's contribution is showing that the protection covered a median 12% of command wall time in the sampled H20 workload, and that paying 0.3–3.9% p95 inflation on that protected slice buys back 2.6–3.4× the fleet throughput. That's a good trade for any operation running 300,000 benchmarking jobs a day, and a design pattern worth stealing wherever an agent closes its loop over shared measurement hardware.