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

Namyoon Lee, Yongjune Kim · 2026

Read FibQuant: Universal Vector Quantization for Random-Access KV-Cache Compression by Namyoon Lee, Yongjune Kim (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11478.txt.

Introduction

Namyoon Lee and Yongjune Kim introduce FibQuant, a universal fixed-rate vector quantizer for random-access key-value cache compression. Serving long contexts strains memory traffic. Rotation-based scalar codecs store a norm, rotate and quantize coordinate by coordinate, but discard the geometry created by normalization. After a Haar rotation, a block of coordinates forms a spherical-Beta source, not a product source. FibQuant keeps the same normalize-rotate-store interface with a shared radial-angular codebook, beating its scalar specialization at matched rate.

Catalog record

CREATORNamyoon Lee, Yongjune Kim
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46962
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.11478

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

FibQuant: Universal Vector Quantization for Random-Access KV-Cache Compression Namyoon Lee, Yongjune Kim Abstract Long-context inference is increasingly a memory-traffic problem. The culprit is the key–value (KV) cache: it grows with context length, batch size, layers, and heads, and it is read at every decoding step. A useful cache codec is therefore not merely a quantizer. It is also a data structure: every cached key and value must occupy a fixed address and be reconstructed independently, so decompression can be fused with attention. Rotation-based scalar codecs meet this systems constraint by storing a norm, applying a shared random rotation, and quantizing one coordinate at a time. They are universal and random-access, but they discard the geometry created by the normalization step. After a Haar rotation, a block of k k consecutive coordinates is not a product source; it is a spherical-Beta source on the unit ball. We introduce FibQuant , a universal fixed-rate vector quantizer that keeps the same normalize–rotate–store interface while replacing scalar tables by a shared radial–angular codebook matched to this canonical source. The codebook combines Beta-quantile radii, Fibonacci / Roberts–Kronecker quasi-uniform directions, and multi-restart Lloyd–Max refinement. We prove that the resulting vector code strictly improves on its scalar product specialization at matched rate, with a high-rate gain that separates into a cell-shaping factor and a density-matching factor. The same construction gives a dense rate axis, including fractional-bit and sub-one-bit operating points, without calibration or variable-length addresses. On GPT-2 small KV caches, FibQuant traces a memory–fidelity frontier from 5 × 5\times compression at 0.99 0.99 attention cosine similarity to 34 × 34\times at 0.95 0.95 . End-to-end on TinyLlama-1.1B, it is within 0.10 0.10 perplexity of fp16 at 4 × 4\times compression and has 3.6 × 3.6\times lower perplexity than scalar TurboQuant at b = 2 b=2 ( 8 × 8\times compression), where scalar random-access quantization begins to fail. 1 Introduction The key–value (KV) cache is the state carried by an autoregressive transformer. Its size grows linearly with context length, batch size, layer count, and head count; its contents are accessed at every decoding step. In long-context serving, the cache is therefore not an auxiliary buffer. It is often the object that determines memory bandwidth, batch size, and latency, and in extreme regimes it can exceed the model weights itself [ 1 ] . This pressure has led to two-bit and lower-precision cache quantization methods such as KIVI and KVQuant [ 2 , 3 ] . The cache, however, imposes a constraint that is absent from ordinary source coding. A deployable cache codec must be random-access : the representation of token t must live at a fixed address, and the corresponding key or value must be decoded independently by simple address arithmetic. Otherwise decompression cannot be fused with the attention kernel [ 1 ] . This single constraint explains why fixed-rate quantizers dominate the source-coding layer of KV-cache compression [ 2 , 3 , 6 , 7 ] . It rules out many statistically attractive variable-length or context-dependent representations before one even asks about distortion. The cleanest representative of this random-access family is TurboQuant [ 6 ] . It stores the vector norm, applies a shared random orthogonal rotation, and quantizes each rotated coordinate with the same scalar Lloyd–Max table. This is the right interface : source-agnostic, fixed-rate, and easy to fuse. But it is the wrong geometry . Once a vector has been normalized and Haar-rotated, a block of k consecutive coordinates lies on the unit ball with a specific radial law and a uniform angular component. The coordinates are not an independent product of shifted-Beta marginals. A scalar code sees one coordinate at a time; the source seen by the cache is intrinsically vectorial. The sub-one-bit gap. In production, the admissible cache rate is not chosen by an elegant integer-bit quantizer. It is set by VRAM, latency, context length, and batch size. When this budget falls below roughly one bit per coordinate, current universal, calibration-free, random-access codecs cease to operate: TurboQuant bottoms out at one bit, RaBitQ [ 7 ] is a one-bit signed code, and KIVI / KVQuant primarily target two bits or above. The remaining alternatives either rely on calibration, as in low-rank projection methods such as Palu [ 13 ] , or alter the sequence itself through eviction or retention policies such as StreamingLLM and H2O [ 10 , 9 ] . The missing object is a fixed-rate, calibration-free, random-access codec with a continuously tunable rate axis below one bit per coordinate. Contribution. We ask a simple question: what is the canonical source induced by the random-access normalize–rotate interface? The answer is the spherical-Beta law f_{d,k} on the unit ball \mathbb{B}^{k} . Once this law is identified, the rest of the codec is classical. The radius is matched by Bennett–Gersho companding, the direction by quasi-uniform spherical point sets, and the finite-rate codebook by Lloyd–Max refinement. The result is FibQuant : a vector quantizer that keeps the serving interface of scalar rotation codes but recovers the shaping and density-matching gains that scalar products leave on the table. Our contributions are as follows. • Canonical source. We prove that norm-then-Haar-rotation maps every nonzero input distribution to the same k -block marginal f_{d,k} on \mathbb{B}^{k} (Theorem 1 ). Thus one shared offline codebook is the correct universal object for layers, heads, prompts, and models. • Vector advantage. We show that the best k -vector code strictly dominates the scalar product specialization at matched rate, and that the high-rate gain factors into a cell-shaping term and a density-matching term (Theorem 2 ). • Dense rate axis. Because the rate is b=(\log_{2}N)/k , FibQuant realizes fractional-bit and sub-one-bit operating points while preserving fixed addresses and independent decoding (Figure 3 ). • KV-cache evidence. On GPT-2 small, FibQuant reaches 34.1\times compression at 0.946 attention-output cosine similarity, the only universal random-access method in our comparison beyond 10\times compression (Figure 4 ). On TinyLlama-1.1B, it strictly dominates per-token Int and scalar TurboQuant at matched integer rates on WikiText-103 perplexity and HellaSwag accuracy (Sec. 5.3 ). 2 Background and Related Work FibQuant is a source-coding layer for a specific systems interface: fixed-rate random access to cached keys and values. It is therefore complementary to eviction, low-rank projection, and fused-kernel systems work. We separate the related work according to this role. KV-cache compression. Existing approaches reduce the KV cache along different axes. Quantizers reduce precision, from outlier-aware matrix quantization such as LLM.int8() [ 14 ] to cache-specific methods such as KIVI , KVQuant , Gear , and Qjl [ 2 , 3 , 4 , 5 ] . Token-selection methods reduce the sequence dimension by keeping attention sinks or heavy hitters [ 10 , 9 , 11 , 12 ] . Low-rank methods such as Palu exploit calibrated head-specific subspaces [ 13 ] . System frameworks such as KVComp focus on making compression compatible with the memory hierarchy and the attention kernel [ 1 ] . These methods attack different bottlenecks. Our question is narrower and more primitive: given a random-access fixed-rate cache slot, what source code should occupy it? Rotation-then-quantize codes. The closest prior art is the family of source-agnostic rotation codes. TurboQuant stores a norm, applies a shared random rotation, and quantizes

Read the complete text