BitDecoding-FP4: Algorithm-System Co-Design for Native FP4 KV Cache Decoding

The KV Cache Bottleneck in Long-Context LLM Serving

In long-context LLM serving, the key-value (KV) cache dominates both memory capacity and bandwidth. As context lengths continue to grow, KV cache size scales linearly, becoming the core bottleneck that constrains inference efficiency. The emergence of 4-bit microscaling formats (such as NVFP4 and MXFP4) makes KV cache compression and FP4 tensor-core-based attention computation possible, theoretically enabling substantial reductions in memory footprint and improvements in throughput.

However, a significant gap remains between algorithmic-level quantization and system-level acceleration: existing FP4 KV systems use naive quantization, causing severe accuracy degradation, while accuracy-oriented 4-bit algorithms rely on vector codebooks, whose lookup overhead actually drags down decoding throughput. BitDecoding-FP4 is proposed precisely to bridge this gap through an algorithm-system co-design approach, aiming to achieve both accurate and efficient native FP4 KV decoding.

KV cache refers to the intermediate tensors cached during autoregressive inference to avoid recomputing the keys (Key) and values (Value) of historical tokens. Its size is approximately 2 × layers × heads × head dimension × sequence length × bytes per element, growing linearly with context length. For a 70B-class model with a 32K context, the KV cache can reach tens of GB, far exceeding the memory budget beyond model parameters and directly limiting batch size and throughput. Microscaling (MX) is a class of block floating-point formats: tensors are grouped into fixed block sizes (e.g., 32 elements), each group sharing a scaling factor (e.g., E8M0), with the elements themselves represented in low bit-width (e.g., FP4's E2M1). NVFP4 and MXFP4 are two 4-bit microscaling variants promoted by NVIDIA and OCP, differing mainly in block size and scaling factor format. They enable KV caches to be stored in 4 bits and allow attention matrix multiplication to be performed directly on FP4 tensor cores, but quantization error and dequantization overhead are the main obstacles to deployment.

Three Error Sources and Algorithmic Innovations

BitDecoding-FP4 suppresses the errors introduced by FP4 quantization from three dimensions, each targeting a specific error source.

Dual-Residual Query Quantization

Quantization error in the query directly propagates to the attention logits. Research found that naive FP4 quantization can cause query logit errors as high as 60%. BitDecoding-FP4 splits the query into two FP4 tensors, preserving more information through a dual-residual approach that dramatically reduces logit error from 60% to 1%. This splitting strategy significantly improves query representation accuracy without adding extra storage overhead.

Underflow-Aware Probability Scaling

In long-context scenarios, attention probability distributions are often very sparse, with large numbers of extremely small probability values. When using E4M3-format scaling factors, these long-context probabilities are easily rounded to zero, causing information loss. BitDecoding-FP4 introduces an underflow-aware probability scaling mechanism that prevents probability values from underflowing to zero during quantization, thereby preserving critical attention signals in long contexts.

Outlier-Aware Key Quantization

Outliers in the keys (Key) disrupt the effectiveness of per-token scaling quantization. BitDecoding-FP4 combines three techniques—static smoothing, Hadamard rotation, and scale search—to effectively suppress the impact of key outliers. Hadamard rotation disperses outliers across multiple dimensions, while scale search further optimizes quantization parameters, ensuring quantization robustness under token-level scaling.

Hadamard rotation is an orthogonal transform that multiplies a vector by a Hadamard matrix (or its fast variant) to spread energy evenly across all dimensions. In quantization, it can "flatten" the few outliers with extremely large values that dominate the dynamic range, making per-token or per-block scaling factors more representative of the overall distribution and thereby reducing quantization error. The transform is invertible with O(d log d) computation; after applying it to keys in attention, a corresponding transform must be applied on the query side to keep the dot product unchanged. Static smoothing estimates per-channel scaling coefficients during a calibration phase and rescales keys per channel to level out variance differences across channels. Both work in concert with scale search, which searches among candidate scaling factors for the value that minimizes quantization error, jointly improving robustness under token-level scaling.

System-Level Optimization: Eliminating the Softmax Bottleneck

Algorithmic accuracy improvements require system-level coordination to translate into actual throughput. BitDecoding-FP4 performs deep system-level optimizations targeting the paged KV cache.

In conventional attention computation, the softmax operation often becomes the bottleneck in the decoding phase. BitDecoding-FP4 adopts a transposed softmax that fuses probability quantization with softmax, reducing the write-back overhead of intermediate results. Meanwhile, it stacks query MMA (matrix multiply-add) operations on the paged KV cache, improving tensor core utilization. These system-level optimizations and algorithmic improvements form a closed loop that jointly supports end-to-end high throughput.

Paged KV cache borrows the paging concept from operating system virtual memory, partitioning the KV cache into fixed-size blocks that are mapped to non-contiguous physical GPU memory via a block table. It eliminates the waste of reserving the maximum contiguous length for each sequence and supports dynamic batching and sequence sharing, making it a core mechanism of inference systems such as vLLM. However, its indirect addressing makes memory access patterns irregular in attention kernels, especially under FP4 where additional dequantization and scaling factor loads are required. Transposed softmax means aligning the normalization direction of softmax with the accumulation direction of matrix multiplication in block-wise attention computation, so that probability quantization can be fused in-place into the softmax reduction process, avoiding writing the full probability matrix back to GPU memory and reading it out again. Query MMA stacking refers to issuing matrix multiply-add instructions for multiple query blocks consecutively to fill the tensor core pipeline and hide the latency of paged memory access and dequantization.

Accuracy and Performance Results

BitDecoding-FP4 validated its accuracy preservation capabilities across multiple model architectures. On dense models and MoE models, covering both GQA and MLA attention mechanisms, with NVFP4, BitDecoding-FP4 maintains an accuracy gap within 0.5 percentage points compared to BF16 KV; with MXFP4, the gap is 1 percentage point. Additionally, in reinforcement learning training rollouts, BitDecoding-FP4 also tracks the accuracy performance of BF16 KV.

In end-to-end serving tests on NVIDIA B300 using Qwen3-4B and Qwen3-30B-A3B models, BitDecoding-FP4 achieved 2.4 to 3.0 times peak serving throughput improvement compared to BF16 KV. This result demonstrates that algorithm-system co-design can translate the theoretical advantages of FP4 into practical serving efficiency.

Open Source and Outlook

The BitDecoding-FP4 implementation is open-sourced on GitHub (https://github.com/OpenBitSys/BitDecoding-FP4), providing researchers and engineers with a reproducible FP4 KV decoding solution. Its core philosophy—designing algorithms for specific error sources and eliminating the additional overhead introduced by quantization at the system level—offers a paradigm worth emulating for future lower-bit KV cache acceleration. As long-context applications become increasingly widespread, such co-design approaches are expected to become an important component of LLM serving infrastructure.

One-line Summary

BitDecoding-FP4 achieves accurate and efficient native FP4 KV decoding through algorithm-system co-design.

Paragraph Summary

In long-context LLM serving, KV caches grow linearly with context length, becoming the core bottleneck for memory and bandwidth. 4-bit microscaling formats (NVFP4, MXFP4) can theoretically greatly compress KV caches and enable FP4 tensor-core attention, but existing FP4 KV systems use naive quantization causing severe accuracy degradation, while high-accuracy 4-bit algorithms rely on vector codebook lookups that drag down decoding throughput. BitDecoding-FP4 proposes an algorithm-system co-design solution: algorithmically, dual-residual query quantization reduces logit error from 60% to 1%, underflow-aware probability scaling prevents long-context probabilities from being rounded to zero, and static smoothing, Hadamard rotation, and scale search suppress key outliers; at the system level, transposed softmax fuses probability quantization and query MMA is stacked on paged KV caches to eliminate the softmax bottleneck. On NVIDIA B300, it achieves 2.4 to 3.0 times peak throughput improvement over BF16 KV, with accuracy gaps within 0.5 percentage points under NVFP4.