# Runtime-Certified Bounded-Error Quantized Attention

arXiv: https://arxiv.org/abs/2605.20868 · HTML: https://mlsanity.com/paper/2605.20868/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in KV cache quantization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 22 of its 37 references that are in the map.
- First posted on arXiv 20 May 2026.

## Placed in

- Efficient LLM inference and serving / [KV cache quantization](https://mlsanity.com/inference/kv-cache-quantization/)

## Builds on (most cited first, 22 of 22)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache](https://mlsanity.com/paper/2402.02750/) (2024)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [FlashInfer: Efficient and Customizable Attention Engine for LLM Inference Serving](https://mlsanity.com/paper/2501.01005/) (2025)
- [Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference](https://mlsanity.com/paper/2407.11550/) (2024)
- [QServe: W4A8KV4 Quantization and System Co-design for Efficient LLM Serving](https://mlsanity.com/paper/2405.04532/) (2024)
- [TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate](https://mlsanity.com/paper/2504.19874/) (2025)
- [vAttention: Dynamic Memory Management for Serving LLMs without PagedAttention](https://mlsanity.com/paper/2405.04437/) (2024)
- [PQCache: Product Quantization-based KVCache for Long Context LLM Inference](https://mlsanity.com/paper/2407.12820/) (2024)
- [QJL: 1-Bit Quantized JL Transform for KV Cache Quantization with Zero Overhead](https://mlsanity.com/paper/2406.03482/) (2024)
- [Twilight: Adaptive Attention Sparsity with Hierarchical Top-p Pruning](https://mlsanity.com/paper/2502.02770/) (2025)
- [BLASST: Dynamic BLocked Attention Sparsity via Softmax Thresholding](https://mlsanity.com/paper/2512.12087/) (2025)
- [HACK: Homomorphic Acceleration via Compression of the Key-Value Cache for Disaggregated LLM Inference](https://mlsanity.com/paper/2502.03589/) (2025)
- [Don't Waste Bits! Adaptive KV-Cache Quantization for Lightweight On-Device LLMs](https://mlsanity.com/paper/2604.04722/) (2026)
- [Cocktail: Chunk-Adaptive Mixed-Precision Quantization for Long-Context LLM Inference](https://mlsanity.com/paper/2503.23294/) (2025)
- [VecInfer: Efficient LLM Inference with Low-Bit KV Cache via Outlier-Suppressed Vector Quantization](https://mlsanity.com/paper/2510.06175/) (2025)
- [A Mathematical Theory of Top-k Sparse Attention via Total Variation Distance](https://mlsanity.com/paper/2512.07647/) (2025)
- [TaDA: Training-free recipe for Decoding with Adaptive KV Cache Compression and Mean-centering](https://mlsanity.com/paper/2506.04642/) (2025)
- [InnerQ: Hardware-Aware Tuning-Free Quantization of KV Cache for Large Language Models](https://mlsanity.com/paper/2602.23200/) (2026)
- [PackInfer: Compute- and I/O-Efficient Attention for Batched LLM Inference](https://mlsanity.com/paper/2602.06072/) (2026)

## Built on by (most cited first, 4 of 4)

- [WitCert: Sound Runtime Risk Observability and Gating for KV-Cache Quantization](https://mlsanity.com/paper/2607.28699/) (2026)
- [LOCKS: Page-Local Compact Key Summaries for Efficient Long-Context Decoding](https://mlsanity.com/paper/2607.24555/) (2026)
- [KV Cache Compression Through the Lens of Transform Coding](https://mlsanity.com/paper/2608.14191/) (2026)
- [Pricing the Risk of Runtime Compression: Anytime-Valid Admission and a Served-Output Law for Compressed Serving State](https://mlsanity.com/paper/2608.15810/) (2026)

## Abstract (arXiv)

KV cache quantization reduces the memory cost of long-context LLM inference, but introduces approximation error that is typically validated only empirically. Existing systems rely on average-case robustness, with no mechanism to detect or recover from failures at runtime. We present a tiered KV cache architecture that enables runtime-certified attention: INT8 keys and INT4 values are stored in GPU memory, while FP16 originals are retained in system RAM for deterministic fallback. A two-term error decomposition yields per-head, per-step bounds on (i) attention distribution distortion from key quantization and (ii) value reconstruction error. These bounds are computed online and used to drive adaptive precision selection and a multi-stage fallback ladder, which guarantees recovery to the exact dense attention output when required. Across PG-19, NIAH, and RULER benchmarks on LLaMA~3.1-8B with contexts up to 128K, the system matches dense FP16 KV quality within noise for language modelling and retrieval tasks, while recovering catastrophic failures observed in naive INT8/INT4 baselines. Value-sensitive tasks at short context expose a controlled trade-off between compression and fidelity, which can be eliminated via tighter value tolerances or FP16-value fallback. The certification is local (per-head, per-step) and does not guarantee end-to-end model correctness, but ensures that each attention computation is either bounded relative to an FP16 reference or exactly recovered via fallback. This reframes KV cache quantization as a runtime-verified computation rather than a fixed approximation. The goal is not raw speedups, but enabling safe deployment of aggressive KV compression under strict quality constraints.