SOP-001: KV Cache Non-Determinism
Fresh Updated January 2026| Document Control | |
|---|---|
| SOP ID | SOP-001 |
| Version | 1.0 |
| Status | Active |
| Source | Thinking Machines Lab (2025), vLLM docs |
Overview
KV (Key-Value) Cache Non-Determinism refers to the phenomenon where identical prompts produce different outputs at temperature=0 due to how batched inference systems manage cached attention values.
Technical Explanation
Root Cause
- Batch invariance break: Cached KV is computed separately from current KV
- Different mask/reduction paths based on cache size
- FlashAttention + KV kernels lose per-sequence determinism when batched
Key Data Points
| Model | Unique Completions (N=30) | Notes |
|---|---|---|
| GPT-4 | 11.67 average | Sparse MoE architecture |
| GPT-3.5-turbo | 3.67 average | Presumably denser |
WARNING
API users report 38% variance even with deterministic sampling settings enabled.
Affected Systems
- All sparse MoE + batched systems
- OpenAI API
- Anthropic API
- Google Gemini API
- Any vLLM-based deployment
Mitigation Strategies
Option 1: Batch-Invariant Kernels (2025)
Implementation: vLLM and SGLang now support batch-invariant kernels.
Cost: ~2x slowdown (26s → 55s on 1000 sequences)
Option 2: Accept Variance
For many GEO/AEO use cases, variance is acceptable:
- Test outputs multiple times
- Use consensus across runs
- Design for variance in content pipelines
Option 3: Enterprise Tier
Higher-tier API access often provides:
- More stable batch composition
- Lower-churn inference queues
- More predictable outputs
Verification Checklist
- [ ] Understand that temperature=0 does NOT guarantee determinism
- [ ] Test critical prompts across multiple runs (recommend N=10)
- [ ] Document variance ranges for stakeholders
- [ ] Implement retry/consensus logic if determinism required
- [ ] Consider batch-invariant kernels for self-hosted deployments
Implications for GEO/AEO
- Content pipelines face instability - same prompt may yield different recommendations
- A/B testing is complicated - variance may mask real differences
- Caching strategies must account for variance - don't over-cache single responses
- Client expectations need management - explain variance is structural
See Also
- SOP-004: MoE Routing Variance
- SOP-007: Rate Limiting Effects
- Thinking Machines Lab (2025): "Defeating Nondeterminism in LLM Inference"
Citation
"Batch invariance break: Cached KV computed separately from current KV; different mask/reduction paths based on cache size" — Thinking Machines Lab (2025)