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

Raja Gond; Aditya K Kamath; Ramachandran Ramjee; Ashish Panwar

Source-linked AI summary

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

Raja Gond, Aditya K Kamath, Ramachandran Ramjee, Ashish Panwar

arXiv:2601.17768v2Jan 25, 2026cs.LGcs.AIcs.DC

TL;DR

LLM inference can vary across runs because floating-point reductions change with dynamic batching, while existing deterministic approaches require costly batch-invariant kernels and burden every request. LLM-42 uses speculative-decoding-inspired decode–verify–rollback scheduling to enforce determinism selectively, reusing existing kernels. Its overhead scales with deterministic traffic, and it retains near-peak performance when that traffic is low.

Problem
Dynamic batching and batch-dependent GPU reduction orders make identical prompts nondeterministic, while batch-invariant kernels impose fixed overhead and require substantial kernel changes.
Method
LLM-42 uses a fast decoding path followed by fixed-shape verification and rollback, committing only tokens that pass deterministic replay.
Results
LLM-42’s overhead is proportional to deterministic traffic, retaining near-peak performance at low deterministic traffic, whereas SGLang incurs up to 56% overhead in deterministic mode.
Takeaways & Limitations
Determinism can be enforced selectively for workloads such as evaluation and auditing without making it a fixed cost for creative or otherwise nondeterministic workloads.
Takeaways & Limitations
The prototype’s verification pass adds latency to all requests, even when determinism is not required.

Abstract

from arXiv · show

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.

1 Introduction

LLM-42 addresses nondeterministic LLM inference by separating fast token generation from selective determinism enforcement. It uses speculative-decoding-inspired verification and rollback to preserve throughput while avoiding the fixed costs of batch-invariant kernels.

Motivation: Determinism matters for debugging, reinforcement-learning reward stability, integration testing, scientific reproducibility, and traceability.The paper distinguishes these needs from creative workloads that benefit from controlled stochasticity.
Motivation: Floating-point non-associativity and batch-dependent GPU reduction schedules cause identical prompts to produce different outputs across runs.This affects operators including matrix multiplication, attention, and normalization.
Limitations of Existing Approaches: Batch-invariant computation guarantees determinism but sacrifices adaptive parallelism, requires new kernel implementations, and imposes overhead on every request.Examples include losing split-K acceleration and maintaining a parallel deterministic kernel stack.
LLM-42 Design: LLM-42 repurposes speculative decoding into a scheduling-based decode–verify–rollback protocol that verifies candidate tokens using fixed-size replay windows.The fast path generates tokens efficiently, while the verifier commits consistent tokens and rolls back mismatches.
LLM-42 Design: Verification-window size trades verification overhead against recomputation cost, motivating grouped verification to balance the two.Smaller windows cost more to verify, while larger windows can trigger longer rollbacks after mismatches.
Results: LLM-42 reuses existing kernels and makes overhead proportional to deterministic traffic, retaining near-peak performance when that traffic is low while SGLang incurs up to 56% overhead in deterministic mode.The approach also supports selective enforcement, leaving nondeterministic workloads unverified.

2 Background and Motivation

LLM inference becomes non-deterministic when dynamic batching changes GPU reduction schedules for floating-point operations. Batch-invariant kernels remove this variation but constrain performance and impose costs across requests.

Sources of non-determinism: Dynamic batching changes batch sizes and GPU reduction strategies, so non-associative floating-point accumulation can produce inconsistent numerical results.These effects arise in operators such as GEMMs, attention, normalization, and communication primitives.
Sources of non-determinism: Split-K GEMM parallelism improves parallelism but changes the reduction tree according to matrix shape, producing different numerical results for the same token across runs.The reduction dimension is partitioned across thread blocks before partial results are combined.
Batch-invariant computation: Batch-invariant computation uses a universal reduction strategy, eliminating batch-dependent reductions but coupling determinism to kernel design.Existing systems use provided or newly implemented batch-invariant kernels.
Costs of batch-invariant computation: Batch-invariant kernels can sacrifice substantial kernel performance because they omit optimizations such as split-K, shape-aware tiling, and hardware-specific features.The approach also requires maintaining a parallel kernel stack for deterministic execution.
End-to-end cost: 56% throughput collapse occurs when one deterministic request forces an 11-request batch onto slower batch-invariant kernels, reducing throughput from about 931 to about 415 tokens/s.With 10 non-deterministic requests, throughput is 845 tokens/s; adding a non-deterministic request instead raises it to 931 tokens/s.
End-to-end cost: Batch-invariant execution imposes a fixed performance cost on every request and creates engineering and maintenance burdens for real-world serving systems.The paper argues that these costs make the approach difficult to sustain in practice.

3 Observations

The paper identifies token-level consistency, shape-consistent GPU reductions, and selective determinism as the observations motivating LLM-42. These observations explain why determinism can be enforced without requiring universal batch-invariant execution.

Token consistency: If a sequence remains consistent, its next token is usually consistent under dynamic batching, but one divergence can progressively amplify during autoregressive decoding.An experiment compares 350 reference requests with dynamically batched executions at 6 queries per second and fixed output length 512.
Token consistency: Hundreds of initial tokens commonly match across runs, while the second consistent span is near zero for most requests after the first divergence.Some requests match all 512 tokens in the first consistent span.
Kernel invariance: Most GPU kernels use uniform, shape-consistent reductions whose strategy remains fixed across batches with the same shape.This behavior is described as applying one reduction strategy to all elements within a batch and across same-shaped batches.
Kernel invariance: Position-invariance means an input element produces the same output regardless of its batch position when total batch size is fixed.GEMM kernels provide the paper’s simplest example of this property.
Selective determinism: For deterministic inference, each token position needs the same reduction strategy across runs, while different positions may use different strategies.This is less restrictive than requiring one universal reduction strategy for every token.
Selective determinism: Many workloads do not require bit-level reproducibility, whereas evaluation, safety audits, and regression testing do.Controlled stochasticity may benefit output diversity and creativity, making all-request determinism excessive.

4 LLM-42

LLM-42 uses a speculative-decoding-inspired decode–verify–rollback protocol to enforce determinism while retaining fast dynamic-batching execution. Fixed-size verification provides a consistent reference, and grouped verification balances verification against recomputation cost.

Overall Design: LLM-42 decodes candidate tokens on a fast path, then verifies a fixed-size window before releasing approved tokens.The verifier replays tokens under a fixed input shape, producing a consistent reduction order.
Decode–Verify–Rollback: Verification failures truncate the sequence to the last matching token, repair the KV cache, and resume decoding from the consistent state.Verifier-generated output immediately after the last match is accepted, while later candidate tokens are recomputed.
Decode–Verify–Rollback: Each verification pass produces at least one new consistent token, guaranteeing forward progress even if every optimistically decoded token triggers rollback.The paper reports no such worst-case scenario in its experiments.
Grouped Verification: Verification windows trade higher overhead and lower recomputation at small sizes against lower overhead and longer rollbacks at large sizes.Grouped verification addresses this trade-off by verifying smaller windows from multiple requests together.
Implementation: LLM-42 reuses GEMM, RMSNorm, and FusedMoE kernels, while requiring careful attention-kernel configuration and an appropriate AllReduce implementation.The sampling module requires a one-time new implementation.

5 Evaluation

LLM-42 is evaluated against deterministic and non-deterministic SGLang across offline and online workloads, traffic mixes, and grouped-verification settings. It generally preserves high throughput and lowers latency relative to deterministic execution, while verification configuration exposes a latency–recomputation trade-off.

Offline Inference: Deterministic SGLang reduces throughput by 24% to 36%, while LLM-42 outperforms it in all but one fully deterministic workload.On ShareGPT, LLM-42 is 6% slower in the worst case.
Offline Inference: At 10% deterministic traffic, LLM-42 is 33% faster than deterministic SGLang on ShareGPT and up to 48% faster on other workloads.On ArXiv, its throughput is within 2% of non-deterministic SGLang at 10% deterministic traffic.
Offline Inference: LLM-42 throughput improves monotonically as the fraction of deterministic requests decreases because non-deterministic requests incur no determinism overhead.The evaluation includes offline traces and configurations with varying input and output lengths.
Online Inference: At 12 QPS, deterministic SGLang has 4.64-second median latency and 28-second P99 latency on ShareGPT.The online evaluation reports end-to-end latency across increasing load.
Online Inference: At QPS 18, fully deterministic LLM-42 has 101.2-millisecond P90 TTFT versus 171.6 milliseconds for deterministic SGLang.TTFT increases with deterministic traffic, with modest overhead at 2–10% ratios.
Ablation Study: Offline recomputation is typically below 2%, whereas online recomputation is typically above 6% because online batch sizes vary more.The paper links higher online recomputation to fluctuating load and request arrivals and departures.

Discussion

The prototype has two main scope boundaries: verification adds latency to all requests, and differing prefill and decode reduction strategies prevent prefill-decode invariance. The evaluation reports performance results only for Llama-3.1-8B-Instruct, while correctness was tested on additional models and GPU counts.

Limitations: The prototype’s verification pass adds latency to all requests, even when determinism is required selectively.Suggested mitigations include using a subset of GPU SMs or deferring verification batches.
Limitations: Different reduction strategies for prefill and decode make LLM-42 non–prefill-decode invariant.The passage identifies this as a current prototype limitation.
Evaluation Scope: Performance results are reported only for Llama-3.1-8B-Instruct, although correctness was evaluated on additional models and across 1–4 GPUs.The setup’s multimem/NVLS and limited NVLink support prevent a fair multi-GPU performance evaluation.

6 Related Works

Prior LLM-serving systems primarily optimize throughput, latency, and resource utilization through mechanisms such as continuous batching and KV-cache management. Related determinism work highlights reproducibility and invariant-kernel approaches, while LLM-42 instead explores a scheduling-based alternative.

Serving Systems: Continuous batching and PagedAttention improve serving efficiency through dynamic request scheduling and KV-cache reuse.These systems typically assume non-deterministic execution.
Deterministic Inference: Recent work connects deterministic inference with reproducible evaluation, traceability, compliance, and robustness to mixed-precision and fused-kernel inconsistencies.These motivations explain increasing interest in deterministic serving support.
Deterministic Inference: Tensor-parallel-invariant and batch-invariant kernels provide deterministic alternatives, but LLM-42 examines their performance and engineering costs through a different mechanism.The paper positions its approach as an alternative to batch-invariant computation.

7 Conclusion

LLM-42 offers a simpler alternative to batch-invariant computation for deterministic inference, minimizing new kernel development and limiting overhead to traffic requiring determinism.

LLM-42 repurposes speculative decoding to enable deterministic inference without requiring extensive new kernel implementations.
The approach supports selective determinism enforcement, so runtime overhead applies only to the fraction of traffic that requires it.
Batch-invariant kernels are cumbersome and suboptimal because they require rewriting kernels and prevent runtime adaptation of parallelism strategies.