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

• URL: http://arxiv.org/abs/2605.11478v1
• Date: Tue, 12 May 2026 03:45:53 GMT
• Title: FibQuant: Universal Vector Quantization for Random-Access KV-Cache Compression
• Abstract summary: We introduce textscFibQuant, a universal fixed-rate vector quantizer.<n>The codebook combines Beta-quantile radii, Fibonacci,/,Roberts--Kronecker quasi-Max refinement.<n>On GPT-2 small KV caches, textscFibQuant traces a memory--fidelity frontier.
• Score: 35.73320708128261
• License: http://creativecommons.org/licenses/by/4.0/
• 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. 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$ consecutive coordinates is not a product source; it is a spherical-Beta source on the unit ball. We introduce \textsc{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, \textsc{FibQuant} traces a memory--fidelity frontier from $5\times$ compression at $0.99$ attention cosine similarity to $34\times$ at $0.95$. End-to-end on TinyLlama-1.1B, it is within $0.10$ perplexity of fp16 at $4\times$ compression and has $3.6\times$ lower perplexity than scalar \textsc{TurboQuant} at $b = 2$ ($8\times$ compression), where scalar random-access quantization begins to fail.

Related papers

• A Single Fixed Shallow Circuit for Classical Shadows of Arbitrary n-Qubit States [2.5735476569508995]
  We construct a single fixed shallow quantum analyzer whose Born outcomes replace externally sampled settings as labels for reusable shadow snapshots.<n>The analyzer combines a freshly prepared $n$-qubit fiducial register $A$ with parallel Bell readout of $A$ and the unknown system $S$, producing one $2n$-bit record per copy.
  arXiv  Detail & Related papers  (2026-09-07T04:36:39Z)
• No Free Compression in Quantum Relaxations for Optimization [0.0]
  Qubit-efficient quantum relaxations compress classical decision variables into expectation values on substantially fewer qubits.<n>We show that compression can shift cost into restricted expectation value geometry, smaller expectation value magnitudes, or more demanding information recovery rather than eliminate it.
  arXiv  Detail & Related papers  (2026-08-25T20:57:14Z)
• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) is a framework that combines overcomplete equal-width tight frames, coordinate subsampling, and privacy-aware quantization.<n>SSTQ achieves mean squared error scaling while using only $lceil log N il + b$ bits per client, where $N = (d)$ is the frame size.<n>We also derive a surrogate privacy-aware codebook objective that reduces the codebook-dependent MSE scaling from $O(4b)$ to $O(2b)$.
  arXiv  Detail & Related papers  (2026-08-05T17:51:25Z)
• A JoLT for the KV Cache: Near-Lossless KV Cache Compression via Joint Tucker and JL-Residual Allocation for LLMs [0.0]
  Key-value (KV) cache has become the dominant memory cost of transformer inference.<n>Low-rank methods factor two-dimensional slices of the cache, or per-head matrices or cross-layer feature blocks, and quantization methods lower the bit-width of every entry.<n>Our method, JoLT, applies a partial Tucker decomposition that compresses only the token and feature axes while leaving the head and layer axes intact.<n>A randomized-SVD variant, FlashJoLT, delivers a 5-13x compression-time speedup at 1024-token context and matched quality.
  arXiv  Detail & Related papers  (2026-07-14T09:23:20Z)
• OCTOPUS: Optimized KV Cache for Transformers via Octahedral Parametrization Under optimal Squared error quantization [13.284869342523095]
  Key-value (KV) dominates memory bandwidth and footprint in autoregressive inference.<n>Recent rotation-preconditioned codecs (TurboQuant, PolarQuant) show that a structured random rotation followed by a per-coordinate quantizer matched to an analytically tractable marginal is a near-optimal recipe for KV compression.<n>OCTOPUS advances this paradigm through joint quantization of rotated coordinate triplets.
  arXiv  Detail & Related papers  (2026-05-20T14:19:51Z)
• Provable Quantization with Randomized Hadamard Transform [20.865915882313775]
  We show that a dithered version of TurboQuant achieves mean squared error $bigl(sqrt3/2 + obigr) cdot 4-b$ at $b$ bits per coordinate.<n>We prove that a dithered version of TurboQuant achieves mean squared error $bigl(sqrt3/2 + obigr) cdot 4-b$ at $b$ bits per coordinate.
  arXiv  Detail & Related papers  (2026-05-13T17:38:18Z)
• Stochastic Sparse Attention for Memory-Bound Inference [19.301894658575502]
  We present Additive No-mulT Attention (SANTA), a method that sparsifies value-cache access by sampling $S ll n_k$ indices from the post-softmax distribution.<n>We also propose Bernoulli $qKmathsfT$ sampling as a complementary technique to sparsify the score stage.
  arXiv  Detail & Related papers  (2026-05-03T14:44:14Z)
• Scaling Federated Linear Contextual Bandits via Sketching [49.12000877146222]
  This paper proposes Federated Sketch Contextual Linear Bandits (FSCLB)<n>Experiments on both synthetic and real-world datasets show that FSCLB significantly reduces computational and communication costs by over 90 %.
  arXiv  Detail & Related papers  (2026-05-01T08:22:06Z)
• IsoQuant: Hardware-Aligned SO(4) Isoclinic Rotations for LLM KV Cache Compression [0.4496256885343706]
  We propose a blockwise rotation framework based on quaternion algebra and the isoclinic decomposition of $SO(4)$.<n>IsoQuant achieves mean kernel-level speedups of $4.5times$--$4.7times$ over RotorQuant with peak speedups above $6times$.
  arXiv  Detail & Related papers  (2026-03-30T13:37:45Z)
• Robust Layerwise Scaling Rules by Proper Weight Decay Tuning [50.11170157029911]
  In modern scale-invariant architectures, training quickly enters an degrading-governed steady state.<n>We introduce a weight-decay scaling rule for AdamW that preserves sublayer gain across widths.<n>Our results extend $mu$P beyond the near-init regime by explicitly controlling the steady-state scales set by parameters.
  arXiv  Detail & Related papers  (2025-10-17T02:58:35Z)
• An Improved Quantum Algorithm for 3-Tuple Lattice Sieving [1.5327973773729056]
  Shortest Vector Problem is one of the cornerstones of post-quantum cryptography.<n>The fastest known attacks on SVP are via so-called sieving methods.<n>In this paper we improve the quantum time complexity of 3-tuple sieving from $20.3098 d$ to $20.2846 d$.
  arXiv  Detail & Related papers  (2025-10-09T17:13:07Z)
• Programmable Quantum Matter: Heralding Large Cluster States in Driven Inhomogeneous Spin Ensembles [0.0]
  Atom-like emitters in solids are promising platforms for quantum sensing and information processing.<n>We present a framework that leverages this diversity to reduce the resources for generating optically heralded spin cluster states.<n>An optimized pulse sequence simultaneously corrects pulse-length and detuning errors, achieving single-qubit gate fidelities exceeding $99.99%$ for errors.
  arXiv  Detail & Related papers  (2025-09-03T03:59:22Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  We consider a centralized distributed learning setup where all workers jointly find an unbiased bound LDeltaepsilon2,$ better poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution.
  arXiv  Detail & Related papers  (2025-06-30T13:27:39Z)
• Exact results on finite size corrections for surface codes tailored to biased noise [0.0]
  We study the XY and XZZX surface codes under phase-biased noise. We find exact solutions at a special disordered point. We show that calculating thresholds based not only on the total logical failure rate, but also independently on the phase- and bit-flip logical failure rates, gives a more confident estimate.
  arXiv  Detail & Related papers  (2024-01-08T16:38:56Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Deep Learning Meets Projective Clustering [66.726500395069]
  A common approach for compressing NLP networks is to encode the embedding layer as a matrix $AinmathbbRntimes d$. Inspired by emphprojective clustering from computational geometry, we suggest replacing this subspace by a set of $k$ subspaces.
  arXiv  Detail & Related papers  (2020-10-08T22:47:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.