Technical Summary: FibQuant: Universal Vector Quantization for Random-Access KV-Cache Compression

1. Problem Statement

Long-context inference in autoregressive transformers is increasingly constrained by memory bandwidth and capacity, primarily due to the Key-Value (KV) cache. The cache size scales linearly with context length, batch size, layer count, and head count, and it must be accessed at every decoding step.

Existing compression methods face a critical systems constraint: random access. A deployable cache codec must store representations at fixed addresses so that any token's key or value can be decoded independently via simple address arithmetic. This constraint rules out variable-length coding and context-dependent representations, forcing the use of fixed-rate quantizers.

Current state-of-the-art random-access codecs, such as TURBOQUANT, employ a "normalize–rotate–quantize" approach:

1. Store the vector norm.
2. Apply a shared random orthogonal (Haar) rotation.
3. Quantize each rotated coordinate independently using a scalar Lloyd–Max table.

While this interface is universal and random-access, the paper argues it is geometrically suboptimal. Once a vector is normalized and Haar-rotated, a block of $k$ consecutive coordinates does not form an independent product of scalar marginals. Instead, it forms a spherical-Beta source on the unit ball. Scalar codecs treat coordinates as independent, discarding the geometric structure (radial and angular correlations) inherent in the rotated block. Furthermore, scalar methods struggle to operate effectively below one bit per coordinate, creating a "sub-one-bit gap" where current universal, calibration-free codecs fail.

2. Methodology: FibQuant

FibQuant proposes a universal fixed-rate vector quantizer that maintains the same "normalize–rotate" interface as scalar methods but replaces the scalar coordinate tables with a shared radial–angular vector codebook.

2.1 The Canonical Source

The authors prove that the normalize–rotate interface induces a universal source distribution regardless of the original KV data distribution.

• Normalization: Removes scale.
• Haar Rotation: Removes orientation.
• Result: The rotated unit vector is Haar-uniform on the sphere $S^{d-1}$. Consequently, any block of $k$ consecutive coordinates follows a specific spherical-Beta density $f_{d,k}$ on the unit ball $B^k$.
• Implication: A single offline codebook can serve all layers, heads, prompts, and models, as the source distribution is invariant to the specific input.

2.2 Codebook Construction

The FibQuant codebook is constructed to match the spherical-Beta source, combining three components:

1. Radii ($r_n$): Matched to the radial density of the spherical-Beta source using Bennett–Gersho companding rules. For $k=2$, this yields a closed-form solution involving Beta-quantile radii.
2. Directions ($u_n$): Approximated using quasi-uniform spherical point sets to ensure uniform angular packing:
   • $k=2$: Planar Fibonacci spiral (Golden Quantizer).
   • $k=3$: Fibonacci sphere.
   • $k \ge 4$: Roberts–Kronecker low-discrepancy sequences.
3. Refinement: A multi-restart Lloyd–Max algorithm refines the deterministic initialization to minimize Mean Squared Error (MSE) for the specific finite codebook size $N$.

2.3 Encoding and Decoding

• Encoder: Computes the norm $\nu = \|x\|_2$, rotates the unit vector $\Pi x / \nu$, splits it into $d/k$ blocks of size $k$, and performs a nearest-codeword lookup against the shared codebook.
• Decoder: Retrieves the codeword, reconstructs the block, concatenates blocks, applies the inverse rotation, and scales by the norm.
• Rate: The bit rate is $b = (\log_2 N) / k$ bits per coordinate. By varying $N$ and $k$, FibQuant achieves a dense rate axis, enabling fractional-bit and sub-one-bit operating points without variable-length addressing.

3. Key Contributions

3.1 Canonical Source Identification

The paper proves (Theorem 1) that the norm-then-Haar-rotation interface maps any nonzero input distribution to the same spherical-Beta marginal $f_{d,k}$. This establishes that a shared offline codebook is the theoretically correct universal object for KV-cache compression.

3.2 Vector Advantage over Scalar Specialization

The authors prove (Theorem 2) that the optimal $k$-vector code strictly dominates the scalar product specialization (where $k=1$) at matched rates. The high-rate gain is factored into two components:

1. Cell-Shaping Factor ($\gamma_{cell}$): Vector quantization cells (e.g., hexagonal in 2D) are more efficient than rectangular scalar cells.
2. Density-Matching Factor ($\gamma_{dens}$): Matching the joint spherical-Beta density is superior to matching only the scalar marginals.

3.3 Dense Rate Axis

Unlike scalar Lloyd–Max tables which are limited to integer-bit rates, FibQuant realizes a dense set of rates $b \in (0, \infty)$. This allows operation in the sub-one-bit regime (e.g., $b \approx 0.19$), a regime where current universal random-access codecs cease to function.

4. Experimental Results

4.1 Source Coding Performance

On the canonical spherical-Beta source, FibQuant demonstrates strict dominance over scalar TURBOQUANT at all integer rates. It also fills the gaps between integer rates, providing operating points that scalar methods cannot reach.

4.2 KV-Cache Compression (GPT-2 Small)

Evaluated on GPT-2 small KV caches with attention-output cosine similarity as the metric:

• FibQuant traces a memory–fidelity frontier from 5× compression (at 0.99 similarity) to 34.1× compression (at 0.946 similarity).
• At high compression ratios (>10×), FibQuant is the only universal, calibration-free method that maintains fidelity, outperforming low-rank projection methods that require per-layer calibration.
• The paper notes that full-vector codes ($k=d$) perform better at extreme compression than half-vector codes ($k=d/2$) because they spend all bits on angular packing, which directly correlates with attention inner products.

4.3 End-to-End Language Model Performance (TinyLlama-1.1B)

Evaluated on WikiText-103 perplexity and HellaSwag accuracy:

• At $b=4$ (4× compression): FibQuant is within 0.10 perplexity of the fp16 baseline and outperforms scalar TURBOQUANT.
• At $b=2$ (8× compression): FibQuant achieves 15.88 perplexity, significantly outperforming scalar TURBOQUANT (56.72) and per-token INT quantization (which collapses to 4450.5).
• Fractional Rates: FibQuant provides intermediate operating points (e.g., $b=2.5, 3.5$) unavailable to scalar codecs, allowing the cache budget to be chosen first and the codec tuned to fit.

5. Significance and Claims

The paper claims that the random-access constraint, often viewed as an engineering limitation, has a profound mathematical consequence: it forces the data into a specific spherical-Beta geometry. By recognizing this canonical source, FibQuant recovers the "shaping and density-matching gains" that scalar quantization leaves on the table.

The significance lies in:

1. Universality: A single codebook works across all model configurations without calibration.
2. Sub-One-Bit Operation: It enables high-fidelity compression in regimes where scalar methods fail, effectively expanding the usable memory budget for long-context inference.
3. System Compatibility: It retains the fixed-address, random-access interface required for fusing decompression with attention kernels, making it immediately deployable in existing serving frameworks.

The authors conclude that random access does not preclude good source coding; rather, it dictates exactly which source must be coded.