LLM-42: Enabling Determinism in LLM Inference with Verified Speculation

AI summary

Overview

• Research area: Machine learning systems and LLM serving infrastructure, specifically deterministic execution in high-throughput inference.
• Technical level: Advanced. The paper assumes familiarity with GPU kernels, floating-point reduction order, dynamic batching, KV caching, and speculative decoding.
• Scope: The paper analyzes the performance and engineering costs of batch-invariant computation and proposes LLM-42, a scheduling-based decode–verify–rollback approach that enforces determinism only for requests that need it, implemented on top of SGLang 0.5.3rc0.

What This Paper Is About

LLM inference is non-deterministic: the same prompt can produce different outputs across runs even with identical decoding parameters and hardware, because floating-point addition is non-associative and GPU kernels change their reduction order as batch sizes change under dynamic batching. The existing fix, batch-invariant computation, forces a single universal reduction strategy for every token, which removes determinism problems but also removes the optimizations that make batching fast, and it applies to every request whether or not determinism is wanted. LLM-42 instead lets the fast path decode normally and adds a lightweight verifier that replays a fixed-shape window of recent tokens, commits tokens that are guaranteed consistent, and rolls back the rest.

Key Contributions

1. The first systematic analysis of batch-invariant computation, quantifying its performance cost and engineering burden across GEMM, RMSNorm, and end-to-end serving throughput.
2. LLM-42, an alternate scheduling-based approach to deterministic inference built on four observations about token-level inconsistency rarity, shape-consistent kernel reductions, position-consistent reduction requirements, and selective determinism needs.
3. The decode–verify–rollback (DVR) protocol, which decodes optimistically with dynamic batching, verifies a fixed-size window under a fixed-shape reduction schedule, repairs the KV cache with verifier output, and guarantees forward progress.
4. Grouped verification, which verifies small fixed-size windows of multiple requests together (for example, 8 requests of 32 tokens each) to keep rollback costs low while amortizing verification overhead.
5. An implementation on top of SGLang, with a per-request API flag is_deterministic=True|False (default False), and a stated plan to release source code at https://github.com/microsoft/llm-42.

Main Findings

• Batch-invariant GEMM is much slower: On the authors' GPU, cuBLAS via torch.mm reaches up to 527 TFLOPS on the Llama-3.1-8B-Instruct down-projection shape, while the batch-invariant Triton kernel peaks at 194 TFLOPS, a 63% slowdown, attributed to the absence of split-K and newer hardware features such as Tensor Memory Accelerators and warp specialization.
• Batch-invariant RMSNorm is also slower: The Python-based version used in SGLang is up to 7x slower than the non-batch-invariant CUDA kernel; the Thinking Machines Triton kernel is substantially better but remains up to 50% slower than the fused CUDA implementation.
• One deterministic request penalizes the whole batch: With 10 concurrent non-deterministic requests the system generates 845 tokens/s; at batch size 11 non-deterministic it improves to 931 tokens/s (about 10%); if the new request requires determinism, throughput collapses by 56% to about 415 tokens/s because the entire batch is forced through batch-invariant kernels.
• Divergence is rare but then spreads fast: Using Llama-3.1-8B-Instruct on ShareGPT, 350 requests were first run at batch size one to get reference outputs, then re-run under dynamic batching at 6 queries per second with output length fixed to 512 tokens. In the common case hundreds of initial tokens match exactly, but once a token diverges the second consistent span is near zero for most requests.
• Most kernels are position-invariant, not batch-invariant: CuBLAS GEMM and RMSNorm (including fused RMSNorm + Residual under vLLM/SGLang defaults) are position-invariant but not batch-invariant; FlashAttention-3 with num_splits=1, multimem-based AllReduce on CUDA 13.0+, and tree-based AllReduce under specific NCCL settings are both batch- and position-invariant; ring-based AllReduce is neither.
• Verification cost falls sharply with window size: Profiling on an H100-PCIe GPU, per-token verification cost is up to 0.75 ms for small windows where the pass is memory-bound, dropping to 0.05 ms at a window size of 512, a reduction of 15x.
• Larger windows cause more rollbacks: Measuring 4096 ShareGPT requests online at 12 queries per second, more than half of requests complete with no rollback, but at window size 256 about 40% of requests see a rollback ratio of 50% or higher, versus only about 5% at window size 32. Recompute overhead is 6.81% at window size 32 and rises roughly linearly to 46.41% at window size 256.
• Selective determinism recovers nearly all throughput: When one of 11 requests requires determinism, LLM-42 reaches 911 tokens per second, 2.2x higher than SGLang's deterministic mode and within 3% of the non-deterministic best case.
• Offline throughput penalties differ by approach: Enabling deterministic inference in SGLang costs 24% (in=2048, out=512) to 36% (ShareGPT) throughput, attributed to batch-invariant kernels. LLM-42, even at 100% deterministic traffic, outperforms SGLang-Deterministic in all but one setting (ShareGPT), where it is 6% slower. On ArXiv, LLM-42 is within 8%, 2%, 1%, and 1% of best-case throughput at 5%, 10%, 20%, and 50% deterministic traffic respectively.
• Recomputation stays small in most configurations: With grouped verification over 8 requests of 64 tokens each at 100% deterministic traffic, recomputed tokens are 10.97% for ArXiv, 0.32% for ShareGPT, 0% for in=512/out=256, 0.07% for in=1024/out=256, 2.41% for in=1024/out=512, 2.08% for in=2048/out=256, under 0.01% for in=2048/out=512, and 1.55% for in=4096/out=512.
• Speculation depth is much longer than in speculative decoding: LLM-42 uses no approximation and only floating-point rounding errors as the source of deviation, achieving high acceptance rates and speculation of 32-64 tokens, versus 2-8 tokens for conventional speculative decoding, and it uses the same model for decoding and verification rather than separate draft and target models.
• Online inference results are not reported here: The content supplied describes online metrics (end-to-end request latency and time-to-first-token) but is truncated before those results appear.

Methodology in Plain English

The authors start by measuring what the leading alternative costs. They run GEMM and RMSNorm microbenchmarks comparing batch-invariant kernels from He et al. and SGLang's defaults, then measure end-to-end token throughput as one deterministic request joins a batch of non-deterministic ones.

They then characterize the problem itself. Using Llama-3.1-8B-Instruct on ShareGPT, they produce reference outputs at batch size one and compare them against outputs produced under dynamic batching at a load of 6 queries per second, defining "first consistent span" as the number of leading tokens that match and "second consistent span" as the matching stretch between the first and second divergence points. They also survey which common operators are batch-invariant versus position-invariant.

Their design rests on four observations: tokens from a consistent state are usually consistent; kernels apply the same reduction strategy to all inputs of a given shape; only position-consistent reductions are needed for determinism; and only some traffic needs determinism.

From these they build the decode–verify–rollback protocol. A request first goes through deterministic prefill (avoiding arbitrary inter-request batching, so no verifier is needed there). Then the fast path decodes candidate tokens under dynamic batching. The verifier replays a fixed number of tokens — padding with dummy tokens if fewer remain — so the shape is constant and the reduction order is fixed. If all tokens match, they are accepted plus the extra verifier-generated token. If some mismatch, only tokens up to the last match are committed, plus the verifier-generated token at that position, and the KV cache is truncated there and overwritten with the verifier's entries so future decode steps start from a consistent state. Each verification pass produces at least one new consistent token, so progress is guaranteed.

To handle the window-size trade-off, grouped verification verifies small windows from multiple requests together. The authors also describe configuration choices for consistency: FlashAttention-3 with the number of KV splits set to one during verification, multimem-based AllReduce where supported or tree-based AllReduce with a fixed NCCL configuration otherwise, and SGLang's sampler including multinomial_with_seed for non-greedy sampling. GEMM, RMSNorm, and FusedMoE kernels are reused unchanged.

Evaluation uses Llama-3.1-8B-Instruct (32 query heads, 8 KV heads, 32 layers) on four NVIDIA H100 PCIe GPUs with 80 GB HBM3 and 114 streaming multiprocessors each, with a host of 64 physical cores (128 hardware threads) and roughly 1.65 TB DRAM. Workloads are synthetic inputs of varying context length plus ShareGPT (92,812 requests; input length mean 304, median 136, standard deviation 491; output length mean 192, median 118, standard deviation 212) and ArXiv test split (5,941 requests; input length mean 7,017, median 6,435, standard deviation 3,479; output length mean 198, median 191, standard deviation 74). Deterministic traffic fractions tested are 2%, 5%, 10%, 20%, 50%, and 100%. Offline runs execute 4096 requests per configuration across eight workload configurations.

Why This Matters

Impact on research. The paper reframes determinism as a scheduling and verification problem rather than a kernel-design constraint, and argues that position-invariance is a strictly stronger property than determinism that is easier to reason about at the level of input shapes. This gives systems researchers an alternative to rewriting kernels for reproducibility.

Real-world applications.

• Evaluation runs, safety audits, and regression testing, where bit-level reproducibility is required.
• Reinforcement-learning training, where the paper states determinism improves reward stability.
• Large-scale integration testing and debugging of bugs that appear only under particular batching choices.
• Scientific reproducibility and traceability, cited as reasons determinism underpins trustworthy results.

Industry relevance. SGLang and vLLM have adopted batch-invariant kernels, and the paper measures a 56% throughput collapse when a single deterministic request enters a non-deterministic batch under that design. For serving operators, LLM-42's per-request is_deterministic flag means the cost of determinism scales with the fraction of traffic that asks for it rather than being a fixed tax on every request.

Future Directions

• Reporting the online inference results (end-to-end request latency and time-to-first-token) that the supplied content truncates before presenting.
• Extending or validating the approach across models beyond Llama-3.1-8B-Instruct and across hardware beyond the four H100 PCIe GPUs used, since the operator-level determinism choices (multimem versus tree-based AllReduce, FlashAttention-3 settings) are hardware and version dependent.
• Determining how best to tune grouped verification in practice: the paper shows a sharp trade-off between window size and recomputation overhead (6.81% at window size 32 versus 46.41% at window size 256) but does not establish a general rule for choosing window and group size.
• Addressing the workloads where LLM-42 does not win: it is 6% slower than SGLang-Deterministic on ShareGPT at 100% deterministic traffic, and ArXiv shows the highest recomputation at 10.97% and the most rollbacks (3,351 at 100% deterministic traffic).
• Whether better batch-invariant kernels could close the gap measured here is raised as an open possibility, with the authors noting it would require extensive model- and hardware-specific kernel development.

Target Audience

ML systems and inference-serving engineers who deploy LLMs at scale and need reproducibility; researchers working on GPU kernel determinism, floating-point reproducibility, or speculative decoding; and teams that maintain or evaluate serving frameworks such as SGLang and vLLM. Readers without background in GPU reduction strategies, dynamic batching, or KV-cache management will find the performance analysis accessible but the design and evaluation sections demanding.

Authors’ abstract

In LLM inference, the same prompt may yield different outputs across different runs. At the system level, this non-determinism arises from floating-point non-associativity combined with dynamic batching and GPU kernels whose reduction orders vary with batch size. A straightforward way to eliminate non-determinism is to disable dynamic batching during inference, but doing so severely degrades throughput. Another approach is to make kernels batch-invariant; however, this tightly couples determinism to kernel design, requiring new implementations. This coupling also imposes fixed runtime overheads, regardless of how much of the workload actually requires determinism. Inspired by ideas from speculative decoding, we present LLM-42, a scheduling-based approach to enable determinism in LLM inference. Our key observation is that if a sequence is in a consistent state, the next emitted token is likely to be consistent even with dynamic batching. Moreover, most GPU kernels use shape-consistent reductions. Leveraging these insights, LLM-42 decodes tokens using a non-deterministic fast path and enforces determinism via a lightweight verify-rollback loop. The verifier replays candidate tokens under a fixed-shape reduction schedule, commits those that are guaranteed to be consistent across runs, and rolls back those violating determinism. LLM-42 mostly re-uses existing kernels unchanged and incurs overhead only in proportion to the traffic that requires determinism.