Skip to content

AdaCode: Adaptive Lossless Compression for BFloat16 KV Cache

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/lichangshiwhu/Adacode
Area: Model Compression
Keywords: KV cache compression, lossless compression, BFloat16, adaptive coding, GPU memory efficiency

TL;DR

Addressing the severe memory bottleneck of KV caches in long-context generation without suffering from the approximation errors of lossy quantization, this paper reveals that BFloat16 exponent values are inherently concentrated and proposes AdaCode, a bit-exact lossless compression framework that encodes frequent exponents into short fixed-length codes while retaining outliers explicitly, achieving an average 71.78% compression ratio across diverse LLMs and 70.26% on vision-language models with zero accuracy loss.

Background & Motivation

The memory footprint of the Key-Value (KV) cache has become a critical bottleneck hindering the deployment of large language models (LLMs) during autoregressive generation, particularly for long-context inference. Because the KV cache grows linearly with both sequence length and batch size, real-world applications often face strict limits on practical context lengths or must rely on expensive offloading techniques. While quantization methods (such as INT8, INT4, and extreme 2-bit formats like KIVI, HQQ, and CommVQ) have been widely adopted to reduce the KV cache footprint, they inevitably introduce approximation errors into the attention computation. In mission-critical domains such as formal mathematical reasoning, code execution, and tasks demanding bit-exact reproducibility, even minor numerical perturbations can trigger trajectory divergence, compounding errors, and degraded generation quality.

However, existing lossless compression strategies have seen very limited application to dynamic KV caches. Classical entropy coding (e.g., Huffman coding) and recent lossless techniques developed for LLMs (such as ZipNN, DFloat11, and Neuzip) primarily target static model parameters or checkpoint weights. These methods assume an offline compression regime where only decompression occurs during inference. They lack the lightweight, ultra-low-latency, and highly parallel compression and decompression routines required for the dynamic, step-by-step token generation executed on modern GPUs.

To bridge this gap, the authors analyze the numerical representation of BFloat16 KV caches, which consist of 1 sign bit, 8 exponent bits, and 7 mantissa bits. Both empirical statistics and theoretical derivations reveal that the exponent values are sharply concentrated within a narrow contiguous interval, whereas the sign and mantissa bits exhibit near-uniform, low-redundancy distributions. Core idea: exploit the intrinsic concentration of BFloat16 exponents by encoding dominant contiguous exponent ranges into short fixed-length codes and storing rare outliers explicitly, coupled with minimal-cost parameter optimization, GPU-friendly byte-aligned packing, offline calibration, and an asynchronous CPU adjuster to realize bit-exact, high-throughput lossless KV cache compression.

Method

Overall Architecture

AdaCode provides an end-to-end lossless compression and on-the-fly decompression pipeline tailored for iterative autoregressive generation on GPUs. The system operates on blocks of 8 BFloat16 elements. First, the 1-bit sign and 7-bit mantissa of each float are packed into a single uint8 byte without transformation. Second, the 8-bit exponent field is encoded using a per-layer short code length \(L\) (typically 2, 3, or 4 bits) optimized via a minimal-cost objective. Exponents within the contiguous high-frequency range are stored as relative offsets from a base value, while outliers outside this range are assigned a reserved zero marker and stored explicitly in full precision. To eliminate GPU runtime overhead during prefill, parameters are initialized via offline calibration on a representative dataset (C4). During decode, a lightweight asynchronous adjuster periodically recomputes the optimal coding parameters on the CPU to mitigate distribution shifts.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input: Block of 8 BFloat16 KV Cache Elements<br/>(1-bit sign + 8-bit exponent + 7-bit mantissa)"] --> B["Sign & Mantissa Packing<br/>Pack 1-bit sign + 7-bit mantissa into 1 uint8 per element"]
    A --> C["Exponent Minimal-Cost Optimization<br/>Determine optimal short-code length L and offset"]
    C --> D["Short-Code Mapping & Outlier Handling<br/>Map frequent range to (e - offset)<br/>Assign zero marker to outliers and record 8-bit raw values"]
    B --> E["GPU-Friendly Byte-Aligned Packing<br/>2-bit (4/byte), 3-bit (8/3-bytes), 4-bit (2/byte)"]
    D --> E
    E --> F["Output: Bit-Exact Lossless Compressed Cache<br/>(Zero accuracy drop, fast parallel decompression)"]
    F -.Periodic monitoring every N steps.-> G["Lightweight Online Adjuster<br/>CPU asynchronous solving to track distribution shifts"]
    G -.Update parameters.-> C

Key Designs

1. Exponent Concentration Theory and Minimal-Cost Optimization: Adaptive Bitwidth Selection

Conventional entropy coding schemes produce variable-length bitstreams that incur heavy serialization and branch divergence on parallel GPU architectures. AdaCode instead adopts a fixed-length short code for the frequent exponent range combined with explicit full-precision outlier storage. The authors theoretically prove that when Transformer activations follow a symmetric \(\alpha\)-stable distribution \(S(\alpha, 0, \gamma, 0)\) with \(\alpha \in (0, 2]\), the exponent probability mass function \(P(e) = 2[F(r s) - F(s)]\) (where \(s = 2^{e-127}\) and \(r = 2 - 2^{-7}\)) attains its maximum at \(e^* = 127 + \log_2(\gamma t^*)\). For exponents above \(e^*\), the probability exhibits a sharp power-law decay \(P(e) \simeq C 2^{-\alpha e}\), while for exponents below \(e^*\) it collapses exponentially towards zero, leaving subnormal exponents (\(e=0\)) virtually nonexistent.

Because exponents in the high-frequency bracket form a contiguous interval, AdaCode avoids complex lookup tables. To select the optimal short code length \(L\), the storage overhead is formulated as a trade-off: a larger \(L\) increases base storage but captures more exponents, while a smaller \(L\) reduces base bits at the expense of more full-precision outliers. To ensure predictable parallel memory layouts on streaming multiprocessors (SMs), every element occupies an \(L\)-bit slot in base storage, with outliers additionally requiring their full \(E=8\) bits. The optimal \(L\) is obtained by minimizing: $\(L^* = \arg\min_{L} \Big( L|W| + E \cdot \big(|W| - |\text{Top}_{2^L - 1}(\text{Freq}(W))|\big) \Big)\)$ Searching over candidate bitwidths \(L \in \{2, 3, 4\}\) yields the optimal configuration \((L^*, \text{offset}^*)\). Values within the frequent interval \((\text{offset}, \text{offset} + 2^L - 1]\) are encoded as the relative integer \(e - \text{offset}\), while the code 0 is reserved as an outlier sentinel.

2. GPU-Friendly Byte-Aligned Packing Format: Accelerating On-The-Fly Decompression

Irregular memory transactions and unaligned bit manipulations severely degrade GPU memory bandwidth. AdaCode divides the 16-bit BFloat16 word into two decoupled, byte-aligned data streams: - Sign & Mantissa Stream: Each BFloat16 value provides exactly 1 sign bit and 7 mantissa bits. Concatenating them forms an 8-bit unsigned integer (uint8), naturally aligning with standard GPU byte boundaries without requiring bit-shifting arithmetic. - Exponent Short-Code Stream: The variable short codes are aligned into regular uint8 units based on the chosen \(L\): - For \(L=2\): 4 codes fit cleanly into 1 uint8. - For \(L=4\): 2 codes fit cleanly into 1 uint8. - For \(L=3\) (the optimal bitwidth for \(>98\%\) of layers): 8 codes fit precisely into 3 contiguous uint8 bytes (24 bits total).

The custom Triton decompression kernel loads blocks of 8 elements in parallel. Threads unpack the exponent codes from registers, add the scalar offset (or pull raw 8-bit values from the outlier pool when the zero marker is encountered), and fuse the reconstructed exponent with the sign and mantissa bytes, recovering the pristine BFloat16 tensor with zero numerical discrepancy.

3. Offline Calibration and Asynchronous CPU Adjuster: Mitigating Distribution Shifts with Zero Overhead

Computing optimal compression parameters dynamically at every inference step would introduce prohibitive latency into the prefill and decoding phases. However, the authors observe that the exponent distribution of a given LLM remains remarkably consistent across different datasets and inference stages, with only minor shifts.

AdaCode addresses this through a dual-track strategy. First, during offline initialization, the optimal parameters \((L, \text{offset})\) are precomputed per layer using a general calibration corpus (C4) and cached. During online prefill, the model applies these parameters immediately, bypassing runtime optimization and preserving low Time-To-First-Token (TTFT). Second, to counter gradual distribution drift during long-sequence decoding, an adjuster runs asynchronously on the host CPU every \(N=128\) generation steps. When activated, it evaluates the recent exponent distribution and recomputes \((L_{\text{new}}, o_{\text{new}})\). If a shift is detected, a background recompression is scheduled. Because this occurs off the GPU critical execution path, it guarantees near-optimal compression ratios throughout generation without compromising token-generation latency.

A Worked Example

Consider a block of 8 consecutive BFloat16 values arriving from attention computation: 1. Separation: The 8 floats are split into 8 pairs of (1-bit sign, 7-bit mantissa) and 8 corresponding raw exponent bytes: \([126, 127, 128, 127, 129, 127, 130, 145]\). 2. Sign/Mantissa Packing: The 8 sign/mantissa pairs are packed directly into an array of 8 uint8 bytes. 3. Exponent Encoding: For this layer, calibration selected \(L=3\) (representing values \(1 \sim 7\), with \(0\) reserved as the outlier sentinel) and \(\text{offset}=125\). - Exponent 126 is encoded as \(126 - 125 = 1\) (001 in binary). - Exponent 127 is encoded as \(127 - 125 = 2\) (010). - Exponent 128 is encoded as \(3\) (011). - Exponent 129 is encoded as \(4\) (100). - Exponent 130 is encoded as \(5\) (101). - Exponent 145 falls outside the valid range \([126, 132]\). It is flagged as an outlier, encoded with the sentinel code \(0\) (000), and its raw 8-bit representation (10010001) is appended to the layer's outlier buffer. 4. Byte Packaging: The 8 3-bit codes are packed sequentially into 3 uint8 bytes (\(8 \times 3 = 24\) bits). During inference decompression, the kernel reads the 3 bytes, extracts the 8 3-bit values, resolves the sentinel to fetch 145 from the outlier buffer, adds 125 to the remaining codes, and rejoins the exponents with the sign and mantissa bytes to reconstruct the exact original BFloat16 floats.

Key Experimental Results

Main Results

The primary evaluation spans four LLMs—two dense models (Qwen3-4B, Mistral-7B-Instruct-v0.3) and two MoE architectures (Qwen1.5-MoE-A2.7B-Chat, Huihui-MoE-1.2B-A0.6B)—across 22 benchmark datasets spanning LongBench (16 tasks), LCB, MBPP, AIME24, AIME25, RiddleBench, and SimpleMath. Compression ratio is defined as Compressed Memory / Original Memory \(\times 100\%\) (lower is better). In all cases, AdaCode achieves bit-exact identical recovery with zero accuracy loss.

Model Original Memory (GB) Compressed Memory (GB) Avg. Ratio (%) Min Ratio / Task (%) Max Ratio / Task (%)
Qwen3-4B 1.07 ± 0.05 0.77 ± 0.03 71.83 71.37 (qmsum) 73.52 (AIME25)
Mistral-7B-Instruct-v0.3 1.05 ± 0.04 0.75 ± 0.03 71.22 70.76 (musique) 72.75 (AIME24 / R.B.)
Qwen1.5-MoE-A2.7B-Chat 1.43 ± 0.06 1.02 ± 0.04 71.85 70.96 (musique) 74.82 (RiddleBench)
Huihui-MoE-1.2B-A0.6B 0.83 ± 0.04 0.60 ± 0.03 72.21 71.77 (qmsum) 73.91 (AIME25)
DeepSeek-V2-Lite (MLA) 2.10 ± 0.09 1.50 ± 0.07 71.94 71.48 (passage_count) 73.58 (RiddleBench)
Qwen3-VL-8B-Instruct (VLM) 0.65 ± 0.08 0.46 ± 0.06 70.26 70.21 (Art) 70.31 (Public_Health)

To demonstrate the vulnerability of lossy quantization in error-sensitive tasks, the authors benchmarked AdaCode against KIVI and HQQ on precise text reproduction (Copy task), complex puzzle reasoning (RiddleBench), and arithmetic computation (SimpleMath):

Task Qwen3-4B (KIVI / HQQ / Ours) Mistral-7B (KIVI / HQQ / Ours) Qwen1.5-MoE (KIVI / HQQ / Ours) Huihui-MoE (KIVI / HQQ / Ours)
Copy Task (%) 57.00 / 62.00 / 77.00 57.00 / 53.00 / 58.00 22.00 / 13.00 / 24.00 0.00 / 19.00 / 80.00
RiddleBench (%) 11.69 / 12.55 / 13.41 5.24 / 5.24 / 5.30 6.04 / 6.68 / 6.74 1.61 / 2.70 / 3.97
SimpleMath (%) 38.70 / 42.50 / 47.30 43.40 / 42.40 / 45.70 4.60 / 4.50 / 4.70 0.70 / 0.90 / 1.90
Average Accuracy (%) 35.80 / 39.02 / 45.90 35.21 / 33.55 / 36.33 10.88 / 8.06 / 11.81 0.77 / 7.53 / 28.62

Ablation Study & Component Analysis

Configuration / Dimension Quantitative Metric & Result Takeaway & Mechanism
Offline Calibration Impact on TTFT (multi_news) TTFT reduced: Qwen3-4B (0.87s → 0.83s, -4.21%), Mistral-7B (0.99s → 0.86s, -14.56%), Qwen1.5-MoE (0.71s → 0.65s, -8.41%), Huihui-MoE (0.63s → 0.61s, -3.96%) Precomputing parameters on C4 eliminates runtime search overhead during prefill, significantly improving TTFT.
Adjuster Interval \(N\) Sensitivity (SimpleMath / MBPP) Compression ratio stabilizes as \(N\) decreases, converging at \(N=128\); omitting adjuster (W/O) degrades ratio by up to 3% on Qwen1.5-MoE SimpleMath Confirms that dynamic tracking is essential for datasets with distribution drift; \(N=128\) achieves optimal memory-throughput balance.
Optimal Short-Code Length Distribution (C4) Qwen3-4B: 3-bit (100%); Mistral-7B: 2-bit (1.6%), 3-bit (98.4%); Huihui-MoE: 3-bit (98.2%), 4-bit (1.8%) 3-bit codes dominate across almost all transformer layers, validating the hardware-aligned 3-byte packing design.
Outlier Frequency Distribution (LongBench) Outlier proportions range between 3% and 8% across all 4 LLMs, with median values strictly below 6% Demonstrates that the non-concentrated exponent tail is sparse, incurring minimal auxiliary storage overhead.
Generalization to Other Formats (C4 dataset) BF16 (72.67%~73.71%), FP16 (91.48%~92.82%), FP8 E5M2 (78.97%~81.20%), FP8 E4M3 (90.51%~93.42%) Shows universality; BF16 benefits most because exponent bits account for 50% of total bitwidth (8/16 bits).

Key Findings

  • 3-bit short code is the empirical sweet spot for BFloat16: Across diverse models and layers, over 98% of configurations converged to \(L=3\), which compresses 8 8-bit exponents into 24 bits (3 bytes), reducing exponent storage by over 60%.
  • Outliers are exceptionally sparse: Even across long-sequence generation, outlier rates remain below 6%, confirming that dedicating a small overflow buffer to preserve bit-exact precision introduces negligible storage cost.
  • Superior throughput-per-memory: On Mistral-7B, AdaCode achieves 2762 tokens/s/GB, outperforming uncompressed execution (2468 tokens/s/GB) by ~11%, while running at roughly \(8.5\times\) the throughput of CPU Offloading (323 tokens/s/GB) and significantly exceeding Neuzip (1861 tokens/s/GB).
  • Orthogonal compatibility with MLA and VLMs: AdaCode seamlessly layers on top of DeepSeek-V2-Lite's Multi-Head Latent Attention (MLA), compressing the already-compact latent and RoPE cache down to 71.94% of baseline memory. Similarly, on Qwen3-VL-8B-Instruct, it achieves an average compression ratio of 70.26% across 30 MMMU academic subjects.

Highlights & Insights

  • Leveraging statistical distribution physics over heavy algorithms: Instead of applying heavy variable-length entropy trees that stall GPU execution, AdaCode identifies the mathematical concentration of exponents in BFloat16 activations, replacing complex decoding pipelines with an ultra-lightweight relative offset mapping.
  • Asymmetric software-hardware co-design: By offloading parameter search and drift monitoring to an asynchronous CPU thread while keeping the GPU execution path fully deterministic, memory-aligned, and branchless, AdaCode eliminates runtime overhead during token generation.
  • Bit-exact preservation for mission-critical tasks: While conventional wisdom assumes KV cache reduction requires lossy quantization, AdaCode demonstrates that ~30% of memory can be reclaimed strictly losslessly, providing a reliable foundation for strict mathematical reasoning and code generation.

Limitations & Future Work

  • Format specificity: The high compression gains are closely tied to the bit allocation of BFloat16 (8 exponent bits). Formats with smaller exponent fields, such as FP16 (5 exponent bits, 10 mantissa bits) or FP8 E4M3, exhibit lower compression ratios (~91% to 92%).
  • Hardware kernel dependencies: The current implementation is optimized in Triton for NVIDIA GPUs. Deploying AdaCode on other accelerators (such as TPUs, Apple Silicon, or AMD GPUs) will require platform-specific kernel adaptations for optimal bit-packing throughput.
  • Opportunities for hybrid schemes: Combining AdaCode's lossless exponent coding with conservative mantissa prediction or block-sparse attention masks could push KV cache reduction further without sacrificing model determinism.
  • vs KIVI / HQQ (Quantization-based KV Cache): Quantization achieves high compression (e.g., 2-bit to 4-bit) at the cost of non-negligible numerical errors that severely degrade sensitive reasoning tasks; AdaCode guarantees 100% bit-exact recovery identical to uncompressed BFloat16 while maintaining a stable ~71% compression ratio.
  • vs ZipNN / Neuzip (Neural Network Lossless Compression): Existing lossless techniques focus on static model checkpoints and weights, where decompression is executed once or offline; AdaCode is the first framework purpose-built for the dynamic, step-by-step token append and read patterns of autoregressive KV cache inference.

Rating

  • Novelty: ⭐⭐⭐⭐☆ [Pioneers lossless KV cache compression by proving exponent concentration and proposing hardware-aligned fixed-width offset coding]
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Extensive evaluations across 6 model architectures, 22 long-context and reasoning datasets, multimodal VLMs, and MLA structures]
  • Writing Quality: ⭐⭐⭐⭐⭐ [Clear structural organization, rigorous mathematical formulation, and informative empirical visualizations]
  • Value: ⭐⭐⭐⭐⭐ [Provides an immediately practical, drop-in memory reduction technique for high-reliability LLM serving systems]