God Does Not Play Dice: Enforcing Batch Invariance in Agentic Kernel Generation

• Conventional correctness and efficiency evaluations overlook whether an unchanged input produces consistent outputs as its execution context changes.BI requires an unchanged sample to produce exactly the same output across batch sizes and compositions when samples are semantically independent.Source: §1 · pp. 1–2
• 19 of 83 batch-applicable released artifacts (22.9%) contain confirmed BI violations.The 83 artifacts have a meaningful semantic batch dimension, among 131 released artifacts overall.Source: Table 1 · p. 2, §1 · p. 2
• BIEvolve adds BI enforcement as a plug-in to existing agents, reusing their optimization pipelines rather than replacing them.The approach addresses the limited kernel coverage of specialized system-specific methods while retaining existing agent capabilities.Source: §1 · pp. 2–3
• BIEvolve raises the BI pass rate from 67.6% to 91.9% while retaining 91.8% of baseline geometric mean speedup.The evaluation integrates BIEvolve into three representative LLM-based kernel optimization agents.Source: §1 · p. 2
• BIEvolve combines contract-guided static dependency analysis with dynamic validation across batch contexts, screening candidates before performance benchmarking.Rejected candidates receive actionable diagnostics to guide subsequent optimization attempts.Source: §1 · p. 2, Figure 1 · p. 3
• The authors describe this as the first work to make BI an acceptance criterion during LLM-driven GPU kernel optimization.Source: §1 · p. 3

2.1 GPU Kernel Execution and Nondeterminism

• Batch-dependent variation differs from run-to-run nondeterminism and environment changes because the target and execution environment stay fixed while surrounding batch context changes.Dynamic batching can change batch size, composition, workload shape, kernel variant, tiling, or work partitioning.Source: §2.1 · p. 3
• Because floating-point addition is not associative, changing reduction partitions or accumulation order can change output bits for an unchanged sample.In attention, workload-shape changes can alter tiling or Split-KV strategies and thereby change reduction order; Figure 2 illustrates batch-size-dependent split counts and page ranges.Source: §2.1 · pp. 3–4, Figure 2 · p. 4

2.2 Batch Invariance

• Batch invariance requires a preserved sample’s output to be bitwise identical across admissible batch contexts under the same hardware and software environment.The contexts may vary the sample’s batch size, composition, and position.Source: §2.2 · p. 4
• The optimization goal is a kernel that meets numerical correctness, is batch invariant across admissible contexts, and achieves high execution performance.Source: §2.2 · p. 4

3 Methodology

• BIEvolve operates as a plug-in to existing kernel agents, combining contract-driven static analysis with dynamic checks and returning actionable feedback when candidates fail.Accepted candidates proceed to speedup measurement.Source: §3 · pp. 4–5, Figure 3 · p. 5

3.1 DSL-Guided Static Analysis Module

• The source parser analyzes Python and Triton with AST-based dependency tracking and uses targeted dependency patterns for C/C++/CUDA, including embedded generated native code.For rejected candidates, diagnostics report the protected mechanism, source location, dependency path, and mechanism-specific repair guidance.Source: §3.1 · pp. 5–6
• The contract DSL declares batch-context sources and protected parameters, while the analyzer rejects direct, transitive, or control-dependent batch dependencies into protected parameters.Contracts are organized globally and by kernel family and subtype; dependencies that cannot be resolved statically, such as opaque runtime dispatch or autotuning, are left to dynamic validation.Source: §3.1 · pp. 5–6

3.2 Dynamic Validation Module

• Dynamic validation tests whether a reference-correct candidate produces identical outputs for an unchanged sample across batch contexts selected by kernel family or subtype.Higher-risk families such as attention receive additional contexts to exercise more execution boundaries.Source: §3.2 · p. 6

3.3 Plug into the Agent Loop

• BIEvolve inserts static BI analysis, reference correctness testing, and dynamic BI validation before performance benchmarking in the existing agent pipeline.A framework adapter preserves the agent’s original search and evaluation procedures while routing BI failures into its feedback path.Source: §3.3 · p. 7

4.1 Experimental Setup

• The controlled suite spans batch-applicable attention, linear attention, MoE, normalization, and sampling kernels, evaluated across three agent frameworks with matched turn budgets.The experiment uses K-Search, the Iterative Agent, and the Evolve Agent; each framework's vanilla and BI-aware runs use the same turn budget.Source: §4.1 · pp. 7–8

4.2 Main Results

• The Iterative Agent had the highest intervention rate at 43.6%, versus 23.1% for K-Search and 25.6% for Evolve Agent.Intervention rates can exceed final BI pass-rate gains because BIEvolve also filters violating intermediate candidates on tasks whose baseline final kernel passes BI.Source: §4.2 · p. 8
• BI pass rates rose from 75.7% to 97.4% for K-Search, 48.6% to 89.2% for the Iterative Agent, and 78.4% to 89.2% for Evolve Agent.Ordinary correctness changed from 94.9% to 97.4% for K-Search and remained 94.9% for both conditions in the other frameworks.Source: §4.2 · p. 8, Table 2 · p. 9
• Speedup retention was 86.4% for K-Search, 87.7% for the Iterative Agent, and 102.0% for Evolve Agent.For K-Search, geometric mean speedup was 35.39× for BI-aware generation versus 40.94× for vanilla generation.Source: §4.2 · p. 9
• Tasks with confirmed baseline BI violations had 86.0% aggregate retention, versus 95.7% for tasks without violations.Figure 5 groups tasks by whether their vanilla kernels had a confirmed BI violation.Source: Figure 5 · p. 9, §4.2 · p. 9

4.3 BIEvolve Component Ablation

• Full BIEvolve detected 92% of confirmed violations, versus 83% for static analysis and 55% for dynamic validation, while rejecting 2% of candidates without confirmed violations.Median evaluation time was 10.21 ms per candidate for full BIEvolve, versus 7.69 ms for static analysis and 2.24 ms for dynamic validation; the modules cover modeled dependency patterns and realized behavior, respectively.Source: §4.3 · pp. 9–10, Table 3 · p. 10

Kernel generation and optimization

• Kernel-generation work combines evaluation with feedback-driven generation, learned refinement, or structured search, while KernelBench and FlashInfer-Bench provide evaluation frameworks [32] [33] [34] [35] [36] [37] [38] [39] [40] [42] [43] [44] [45].Representative agents include Kevin, which trains multi-turn refinement with correctness and speedup rewards [46], and K-Search, which separates optimization planning from code implementation [2].Source: §5 · p. 10

BI kernels and deterministic inference

• Specialized BI kernels and serving modes control batch-dependent tiling or reduction schedules, but require careful engineering and do not validate arbitrary agent-generated candidates.Yuan et al. link changes in evaluation batch size and hardware configuration to numerical differences and divergent generated responses [51].Source: §5 · p. 10
• LLM-42 uses fixed-shape verification and rollback [8], while CoRun controls execution shapes through scheduling and padding [52]; these are complementary deterministic-serving designs, not agent-side BI protection.The paper's contribution concerns protecting BI as agents optimize kernel implementations.Source: §5 · pp. 10–11

6 Conclusion and Future Work

• For tasks with semantically independent samples, BI should be an explicit evaluation dimension alongside correctness and performance.The conclusion reports that BIEvolve removes most observed violations on the configured test domain while preserving conventional correctness and speedup.Source: §6 · p. 11
• Static analysis has limited cross-file coverage, and experiments measure batch dependence at kernel outputs rather than end-to-end effects on generation, evaluation, serving, or reinforcement learning.The paper names cross-file analysis and end-to-end assessment as future-work needs.Source: §6 · p. 11

Appendix Table of Contents

• The appendices cover kernel-family evidence, an example DSL contract, task selection and evaluation details, and late-stage search gains.Appendix C separates task coverage from protocol details.Source: Appendix Table of Contents · p. 15

A Problem evidence by kernel family and mechanism

• Table A1 summarizes confirmed violations and structural risks across kernel families, with mechanisms allowed to overlap.Its categories distinguish confirmed test results from risks identified by static inspection; “None” is not proof of absence.Source: A Problem evidence by kernel family… · p. 15, Table A1 · p. 15
• High means a confirmed violation rate of at least 50%, while Medium means at least one confirmed violation below that rate.Low indicates structural risk without a confirmed violation, not a measured low probability; N/A means no semantic batch dimension.Source: A Problem evidence by kernel family… · p. 15
• Mechanism categories include work partitioning, reduction order, algorithm selection, and expert routing, each potentially changing computation for a preserved sample across batch contexts.The listed patterns indicate potential risk, not a confirmed violation by themselves.Source: A Problem evidence by kernel family… · pp. 15–16

B Example DSL Contract

• The implemented contract marks batch symbols as sources and NUM_SPLITS and RNG_SEED as protected parameters, including their listed aliases.The analyzer rejects direct, transitive, and batch-derived control dependence from declared sources to protected sinks.Source: B Example DSL Contract · p. 16
• Dependencies that cannot be traced to a batch symbol declared in the contract fall outside the current static-analysis scope.Opaque algorithm selection, expert routing, and other undeclared runtime effects are assigned to the complementary dynamic validator.Source: B Example DSL Contract · p. 16
• The example contract’s NUM_SPLITS abstraction covers batch-dependent partitioning and reduction structure across aliases and kernel families.The contract listing uses executable syntax loaded directly by parse_contract_file(), rather than pseudocode.Source: B Example DSL Contract · p. 16

C.1 Task coverage

• Tasks require a meaningful semantic batch dimension and span attention, linear attention, MoE, normalization, and sampling.Attention coverage includes GQA, MLA, and DSA, plus representative paged/ragged and prefill/decode regimes.Source: §C.1 · p. 16
• The suite covers diverse kernel definitions across 1,180 benchmark workloads/shapes.It is designed for compact coverage, not exhaustive enumeration of FlashInfer configurations.Source: §C.1 · pp. 16–17
• Linear-attention tasks cover KDA and Gated DeltaNet, while selection favors distinct semantic and operator axes over largely duplicative configurations.The suite prioritizes higher-risk attention and linear-attention kernels while retaining broader operator coverage.Source: §C.1 · pp. 16–17

C.2 Protocol details

• Dynamic validation compares sample 0 bitwise between batch size one and larger batches containing the same unchanged sample.Each context preserves one target sample, and testing stops at the first mismatch.Source: §C.2 · p. 17
• Dynamic validation samples a finite subset of BI contexts, while static analysis traces all declared batch-context symbols to protected sinks.The combined modules are intended to enforce BI without exhaustive context enumeration.Source: §C.2 · p. 17
• Static-only, dynamic-only, and full BIEvolve configurations are evaluated on one shared pool of 200 candidates.The pool contains 100 independently confirmed BI violations and 100 candidates with no confirmed violation, selected across frameworks, generation modes, and major task families.Source: §C.2 · p. 17
• Independent labels require a local test that observes a bitwise output difference for the unchanged target sample; unclassifiable candidates are excluded.Labels are assigned independently of BIEvolve’s decisions.Source: §C.2 · p. 17
• Violation detection is the fraction of confirmed violations rejected, and false rejection is the fraction of candidates without confirmed violations rejected.Timing excludes LLM/API calls, compilation and setup, correctness testing, autotuning, and benchmarking; dynamic-validation timing includes GPU launches and synchronization.Source: §C.2 · p. 17

D Late-stage search gains

• The comparison covers 37 tasks after excluding two whose final kernels failed correctness.Tasks are grouped by the BI outcome of their baseline final kernel.Source: D Late-stage search gains · p. 17
• 26.30% versus 6.11%: BI-aware generation achieved the larger late-stage gain for tasks with confirmed BI violations in their baseline final kernels.Gain is relative change in geometric mean best-so-far speedup over the final five optimization turns.Source: D Late-stage search gains · pp. 17–18, Table A2 · p. 18
• The late-stage pattern does not establish performance beyond the fixed search budget.Table A2 measures final-five-turn search progress; main Figure 5 compares final speedups.Source: D Late-stage search gains · pp. 17–18