TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
Authors: Amir Zandieh
Majid Daliri
Majid Hadian
Vahab Mirrokni
Venue: ICLR 2026 Poster (2026)
Keywords: Vector Quantization
KV Cache Compression
Nearest Neighbor Search
Similarity Search Acceleration
Online Compression Algorithms
Primary area: optimization

Abstract: Vector quantization, a problem rooted in Shannon's source coding theory, aims to quantize high-dimensional Euclidean vectors while minimizing distortion in their geometric structure. We propose TurboQuant to address both mean-squared error (MSE) and inner product distortion, overcoming limitations of existing methods that fail to achieve optimal distortion rates. Our data-oblivious algorithms, suitable for online applications, achieve near-optimal distortion rates (within a small constant factor) across all bit-widths and dimensions. TurboQuant achieves this by randomly rotating input vectors, inducing a concentrated Beta distribution on coordinates, and leveraging the near-independence property of distinct coordinates in high dimensions to simply apply optimal scalar quantizers per each coordinate. Recognizing that MSE-optimal quantizers introduce bias in inner product estimation, we propose a two-stage approach: applying an MSE quantizer followed by a 1-bit Quantized JL (QJL) transform on the residual, resulting in an unbiased inner product quantizer. We also provide a formal proof of the information-theoretic lower bounds on best achievable distortion rate by any vector quantizer, demonstrating that TurboQuant closely matches these bounds, differing only by a small constant ($\approx 2.7$) factor. Experimental results validate our theoretical findings, showing that for KV cache quantization, we achieve absolute quality neutrality with 3.5 bits per channel and marginal quality degradation with 2.5 bits per channel. Furthermore, in nearest neighbor search tasks, our method outperforms existing product quantization techniques in recall while reducing indexing time to virtually zero.

Published as a conference paper at ICLR 2026
TURBOQUANT: ONLINE VECTOR QUANTIZATION WITH NEAR-OPTIMA DISTORTION RATE
Amir Zandieh
Majid Daliri New York University
Majid Hadian Google DeepMind ji com
Google Research zand f wech@goooll..oom
dalirí ma 1 jid@nyu.ede edu
Vahab Mirrokni
Google Research
mi www.oiiioooggl...ooooro com
ABSTRACT
Vector quantization, problem rooted in Shannon's ' source coding, aims to quan- tize high-dimensional Euclidean vectors while minimizing distortion in their geo- metric structure. We propose TURBOQUANT to address both mean-squared error (MSE) and inner product distortion, overcoming limitations of existing methods that fail to achieve optimal distortion rates. Our data-oblivious algorithms, suit- able for online applications, achieve near-optimal distortion rates (within small constant factor) across all bit-widths and dimensions. TURBOQUANT achieves this by randomly rotating input vectors, inducing concentrated Beta distribution on coordinates, and leveraging the near-independence of distinct coordinates in high dimensions to simply apply optimal scalar quantizers per each coordinate. Recognizing that MSE-optimal quantizers introduce bias in inner product estima- tion, we propose a two-stage approach: applying an MSE quantizer followed by a 1-bit Quantized JL (QJL) transform on the residual, resulting in unbiased inner product quantizer. We also provide a formal proof of the information terioon-tteeeticcc lower bounds on best achievable distortion rate by any vector quantizer, demon- strating that TURBOQUANT closely matches these bounds, differing only by a small constant (= 2.7) factor. Experimental results validate our theoretical find- ings, showing that for KV cache quantization, we achieve absolute quality neu- trality with 3.5 bits per channel and marginal quality degradation with 2.5 bits per channel. Furthermore, in nearest neighbor search tasks, our method outperforms existing product quantization techniques in recall while reducing indexing time virtually zero
Vector quantization (VQ) in Euclidean space is crucial for efficiently handling high- dighesimensi vectors across a spectrum of computational domains, from training and deploying large-scale AI and deep learning models powering vector databases for search/retrieval. The core objective is to compress high-dimensional vectors by quamtizing them-converting floating- point coordinate values low-bitwidth i minimizing distortion, quantified by metrics such as mean-squared error (MSE) or inner product errors. By preserving these properties, inner product queries can be answered rapidly, with minimal latency, and using reduced computational and communication resources.
This problem traces back to Shannon's seminal work on source coding [Shannon (1488; : Shannon al. (1959), which established that the minimum distortion achievable by block source codes now known as vector quantizers-ba characterized by the distortion-rate function, determined by the source statistics and the chosen distortion measure (c.g., MSE). Today, vector quantization plays central role in modern computational domains, including AI, deep learning, and large-scale search systems.
A key application of VQ is in deployment of Al models, including LLMs Achiam et al. (202);; Dubey et al. y Anthropic 2 Team et al. (2024). As LLM capabilities depend heavily their model size and context length Kaplan et al. (2020). serving them requires substantial memory demands and increased inference latency. This latency is primarily attributed communication bot-

---

Published as a conference paper at ICLR 2026
tlenecks between HBM and SRAM accelerators, or across distributed clusters. By compressing or quantizing model weights and activations, we can effectively mitigate these bottlenecks, resulting in significant reductions in inference costs. Inner product operations between activations and weights is at the core of deep learning models. Thus, model quantization schemes strive to compress weights and/or activation vectors while accurately preserving these inner products.
Decoder based transformer models Vaswani et al. (2017) present another compelling use case. These models must store key/value (KV) embeddings from previously generated tokens in the KV cache, the size of which scales with both model size (number of layers and attention heads) and context length. This scaling is a significant bottleneck in terms of memory usage and computational speed, especially for long context models. Therefore. reducing the KV cache size without compromising accuracy is essential. In this context, the preservation of the Fuclidean structure of these embed- ding vectors-their inner products and distances-is crucial for maintaining model performance. VQ emerges as the most suitable framework for addressing this challenge, offering a robust approach to compressing high-dimensional embeddings while preserving their essential geometric properties.
Additionally, nearest neighbor (NN) search in high-dimensional spaces with inner product or cosine
similarity ela 2025); Guo et al. (2020) is cornerstone of vector databases pin (2025); gdr (2025)
pgy (2025). ). These databases are fundamental for retrieval -uugeetee generation Gao et al. (203))
Edge et al. 2024) and information retrieval Khattab & Zaharia (2200; Santhanam et al. (2021). ). VQ,
a.k.a. product quantization (PQ), plays a critical role by enabling efficient compression of database
vectors, optimizes memory usage, and facilitates low-latency, accurate estimations of inner products
with query vectors, thereby enabling fast and precise nearest neighbor searches.
Existing VQ algorithms present trade-off: either they lack accelerator (vectorization) compatibility and exhibit slow computation, making them unsuitable for real-time Al applications like KV cache quantization, or they suffer from suboptimal distortion bounds relative bit-width. Our objective is to introduce an algorithm that addresses these limitations. Specifically, we design TURBOQUANT: a lightweight, capable of online application (crucial for scenarios like KV cache quantization), and highly accelerator-friee friendll- a critical attribute for modern AI workloads.
The core of TURBOQUANT is a two-stage process. First, we develop quantizer with optimal distortion rate in terms of mean-squared error (MSE). Subsequently, we apply 1-bit quantizer to the residual, resulting in an unbiased and low-distortion inner product quantizer. We demonstrate that quantizers optimized for MSE do not produce unbiased estimators for inner products, and our two- stage solution effectively bridges this gap. Our quantizer starts by randomly rotating d-dimensional input vectors. Observing the key fact that each coordinate in the rotated vectors follows Beta distribution, we design optimal Lloyd-Max quantizer| Lloyd| 1982); Max (960)) for each coordinate by solving a continuous k-means problem. This method gives optimal MSE distortion bound and minimizes the L2 norm of the residual. To obtain an unbiased and low-distortion quantizer for inner products, we compose our quantizer with the recently developed Quantized (QJL) transform Zandieh et al. (2024a), which quantizes each coordinate of the residual vector to a single bit. Our algorithm offers provably optimal distortion bounds for both MSE and inner products, achieving an exponential improvement over existing methods in terms of bit-width dependence.
0.1 PROBLEM DEFINITION
Formally, our goal is to design a quantization map, denoted as Q : Rd + 13. that transforms d-dimensional vectors to B-bit binary strings. If we set b- d for some b 2 0, this quantizer is said to have a bit-width of b, representing the average number of bits used to encode each coordinate of Rdd. Crucially, we require an inverse map, Q- (0, 1) - Rd that performs dequantization, approximately reconstructing original vectors from their quantized representations. Of course, this transformation is inherently lossy, as Q is not a bijection. So, our primary objective is to minimize distortion, with specific focus on mean-squared error (MSE) and inner product distortion.
We make no distributional assumptions on the input vectors, treating them in the worst-case setting. We let the quantizer Q(-) to be randomized, leading to stochastic outputs. Considering random- ized quantizers, it is more appropriate to define the expected distortion over the randomness of the quantizer's 's output. Thus, aim to design quantizers that for any desired bit-width b minimize the
2

---

Published as a conference paper at ICLR 2026
following expected distortion measures for any (worst-case) vectors a, y E R
(MSE) Duse := R -1--0-
(1)
(inner-prod error)
Dprod
[(v (y. Q (
(2)
The expectations above are taken with respect to the randomness of the quantizer Q(-). Furthermore, for inner-product quantizers, we require unbiasedness of the inner product estimator, a desirable property for numerous applications. More precisely, we require:
(unbiased inner-prod)
E
Kyy Q (Q(x)))) = (y. x).
We aim to design computationally efficient quantizers Qusa and Qprod, that achieve optimal bounds for the distortion measures defined above, for any given bit-width b. Additionally, we aim for Qprod to provide unbiased inner product estimates. In particular, assume that we are given n real-valued Rd. We design the following primitives:
vectors æ1, 22
In
QUANT: efficiently quantizes the dataset and computes
Qz..) DEQUANT: efficiently reconstructs original vectors by computing Q (Q(x))) for i e [n].
0.2 RELATED WORK
Online (data-oblivious) quantization methods apply instantly without needing data-specific tuning or calibrations Dettmers et al. (2022); Asskbboss et al. (2024): Liu et al. (2024b); [S2abb et al. (2024); Han et al. 2025a). In contrast, offline (data-dependent) methods require heavy preprocessing and learning to adapt the quantization map to the data, making them unsuitable for dynamic data sce- narios Kim et al. (2023). For instance, methods such as those presented in Frantar et al. (2022): Lin iet al.] (2024): Xiao et al. (2023a); Chee et al. (2023) use second-order (Hessian) information to tune the quantization map which requires heavy preprocessing and even in some cases post processing as well.
Due to space constraints, we include a more detailed discussion of related work in Appendix
0.3 OVERVIEW OF TECHNIQUES AND CONTRIBUTIONS
MSE Optimized TURBOQUANT. Our first VQ algorithm is designed to minimize MSE distor- tion defined in Eq. (T) To achieve this, we apply a random rotation to the input vectors, thereby inducing Beta distribution each coordinate, irrespective of the input vectors themselves. In high dimensions d, the distribution of each coordinate converges to a Normal distribution due to concen- tration of measure and the central limit theorem. Furthermore, any nearly uncorrelated and, more importantly. almost independent (a deeper result that goes beyond just correlation). This near-independdece It allows us to quantize each coordinate using optimal scalar quantization, disregarding interactions or correlations between different coordinates, while still achieving near-optimal distortion.
distinct coordinates become
crucial aspect that simplifies our quantization design.
We find optimal scalar quantizers for random variables with Beta distributions by solving contin- uous 1-d k-means problem using the Max-Lloyd algorithm. We precompute and store these optimal codebooks for a range of practically useful bit- widths, to enable efficient subsequent invocations of our TURBOQUANT algorithm. In Theorem | we prove that the b-bit MSE optimized TURBO- QUANT Quae Rd > {0, 1 achieves the following distortion for any worst-case vector RRd with | = 1, without any assumption on the distribution of x::
Dase (Quse) = E ||
Qui (Quee (x))
332 + for any 2 0.
For small bit-widths the above distortion upper bound can be further refined. Specifically, for b = 1, 2, 3, 4 we have Drae (uua) 0.36, 0.117, 0.03, 0.009, respectively.
Note that the unit norm assumption, ||=||, = 1. is standard and not restrictive and can compute and store the 7.2 norms in floating-point precision and rescale the dequantized points.
3

---

Published as a conference paper at ICLR 2026
Inner Product TURBOQUANT. We show that the MSE optimized quantizers biased for inner product estimation, and thus a different VQ scheme is needed to get an unbiased inner product quantizer. Our solution is two-stage algorithm that first applies the above-mentioned Quse with a bit-width one less than our target budget and then applies a QJI. Zandieh et al.] (2024a) on the residual error. This is proven to be unbiased and also has nearly optimal inner product error rate. In Theorem we prove that the b-bit inner product optimized TURBOQUANT Qprod E² + {0, 1 achieves the following distortion for any vectors 2, y E IR with || = 1, without any assumption on the distribution of y:
2
E (y,, Qprod (x)ra(())) = = x)
Dproa (Qprod)
E
(y, x)) (y, Qpeoa (Qproa
v3x² v3++-1113
-ill 2
for any b 0.
For small bit-widths the above distortion upper bound can be further refined. Specifically, for = 1, 2, 3, 4 we have Dprod (Qroaa) R3 1.57 0.56 0.18
0.047 respectively.
Lower Bound. As shown in Theorem 3 in the appendix, we leverage Shannon's 's lower bound and Yao's minimax principle prove that for any randomized quantization algorithm Q IR - {0, 1) with bit-width 6, there exist hard input instances æ, y E IRd with | = 1 such that the following lower bounds hold:
Daaa((Q) = E ||0 - [1 QQ
. Dproa (Q) = E [K, x) (y. Q (Q(=)))
As demonstrated by our lower bounds, TURBOQUANT'S MSE distortion is provably within factor of at most 2 this factor significantly decreases. For instance, bit-width of b TURBOQUANT achieves distortion that is only a factor of approximately 1.45 away from the optimal which also confirmed by our experimental results, indicating its efficiency in low-bit-width scenarios.
v x 2.7 of the
cormmationnthooretiie lower bound. Notably, for smaller bit-widths,
we empirically validate our theoretical distortion bounds, demonstrating that TURBOQUANT'S observed distortions closely align with our predictions across various real-world datasets, approaching the established lower bounds. Furthermore, in Section 2.2
Experimental Results. In Section 2.1
and Section 2.3] we showcase TURBOQUANT'S efficacy online KV cache quantization. Specili- cally, achieve perfect long-context retrieval in needle-in-a-haysee haysttakk tasks well other long- context tasks, while compressing the KV cache by a factor exceeding 5x. Finally in Section 2.4 apply TURBOQUANT various high-dimensional near neighbor search tasks. TURBOQUANT consistently outperforms data-dependent product quantization, while reducing the indexing time to near zero.
We use boldface lowercase letters, such and y. denote vectors, and boldface uppercase letters, like M, to denote matrices. To denote a slice of a vector æ between the coordinate indices i and j inclusive of the endpoints, denote its i-th vector. We use the notation 1d1-1 to denote the hypersphere in Rd of radius 1.
Notations.
Dej- For matrix M, simply write M; to
TURBOQUANT: HIGH PERFORMANCE QUANTIZATION
We developed two VQ algorithms, each tailored to a specific objective. The first algorithm is de- signed to minimize the MSE between the original and reconstructed vectors after quantization. The second algorithm is optimized for unbiased inner product estimation, addressing the bias inherent in MSE-optimal quantizers. These algorithms are detailed in the following subsections.
Furthermore, in Appendix C.3 we establish information-theoretie lower bounds on the best achiev- able distortion rates for any vector quantizer. This analysis demonstrates that TURBOQUANT achieve optimaltt,,, differing from the lower bound by only a small constant factor across all bit-widths.
4

---

Published as a conference paper at ICLR 2026
Algorithm TURBOQUANT optimized for MSE
1: input: dimension d and bit-width b
2: Generate a random rotation matrix E Rdxd
3: Construct codebook by finding centroids c1, 22..... O2t [-,,,1] 1] that minimize MSE cost in
Eq. (3)
4: Procedure 250
5: y II-
6: idx; f- arg min y/ Ck for every E {idxy's are b-bit integers)
7: output: idx
8: Procedure DEQUANT (1dx) (1dxx)
9: fj Cidx; for every E [d]
10: σ II II"-
11: output: ē
1.1 MSE OPTIMAL TURBOQUANT
Let æ E gd-1 be a (worst-case) vector on the unit sphere in dimension d. We aim to quantize to b bits per coordinate while minimizing the reconstruction MSE defined in Eq. ( We start by randomizing this vector by multiplying it with random rotation matrix II E R axd We can generate by applying QR decomposition on a random matrix with i.i.d Normal entries.
The resulting rotated vector, II x. is uniformly distributed on the unit sphere Sd-1, As shown in Lemma D. each coordinate of II x follows Beta distribution, which converges to normal distribution in high dimensions. Furthermore, in high dimensions, distinct coordinates of II æ become nearly independent Vershynin (2018), allowing us to apply optimal scalar quantizers to each coordinate independently. Therefore, by Lemma our task reduces to designing scalar quantizer
for random variables with the distribution fx (2) -F-T((d- 1)/2) (1 (1-x² x:2) (d 3)/2 for E (-1,1]
r(d/2)
The optimal scalar quantization problem, given known probability distribution, can be framed as a continuous k-means problem in dimension one. Specifically, we aim partition the interval [-1, 1] into 2 clusters/buckets. The optimal solution adheres Voronoi tessellation meaning interval boundaries are the midpoints between consecutive centroids, when arranged in sorted order. Therefore, with c;'s denoting the centroids in ascending order, scalar quantization as the following k-means optimization problem:
1982).
formulate the
2
C(fx,b) = -1Se
min
x c.l2.. fx(2) dx.
Note that C(fx, b) in Eq. (3) denotes the optimal MSE cost function for bit-width b, quantity we will bound to prove the upper bound on the end-to-end MSE of TURBOQUANT. The problem in Eq. 3 can be solved using iterative numerical methods to achieve any desired precision. We solve Eq. for range of practically relevant bit-widths once, and store the results for future uses by the quantizer. For example, in moderately high dimensions d, where the distribution fx(x) closely approximates normal distribution, the optimal quantization centroids for bit-widths b 1,2 are
2/ and Vd
0.453 + Vd
151
respectively.
vdl
Therefore the quantizer Quae Rd + {0, 1 first computes II x and then computes and stores the indices of the nearest centroids to each coordinate of this vector. The dequantization map Q 1)
ad reconstructs the vector by retrieving the centroids corresponding to the stored indices and then rotating the result back to the original basis through multiplication with II pseudocode for these procedures given Algorithm
We are now ready to prove our main theorem for TURBOQUANT mso. the proof is in Appendix
Theorem (Performance Guarantee: TURBOQUANT ). For any bit-width > and any vector 8d-1, the procedure QUANT nee (x)) in Algorithm louppts index vector idx E [20]d. When
5

---

Published as a conference paper at ICLR 2026
Algorithm 2 TURBOQUANT optimized for inner product
input: dimension and bit-width b
2: Instantiate
with bit-width 6 per Algorithm
3: Generate a random projection matrix S E _add with iid. entries St, ~ NO)
4: Procedure QUANT prod (
5: idx < QUANT nee (z) DEQUANT (idx)
6:
(residual vector) (OJI on residual vector)
7: qjl < sign (S
8: output: (idx, qj], rll1))
9: Procedure DEQUANT proa (idx, q)
Fase DEQUANT use (idx)
11: æajz f 1212 S qjp
output: Tase + fa11
this index vector is passed to the primitive DEQUANT (idxx) it produces a reconstructed vector I R. that satisfies the following distortion bounds:
MSE defined Dase := E=
/33 = is bounded by Daze S S/ 45 for any b 2 0.
For small bit-widths, specifically b 1,2,3, 3, the MSE exhibits finer-grained distortion values: Dase R 0.36, 0.117, 0.03, 0.009, respectively.
1.2 INNER-PRODUCT OPTIMAL TURBOQUANT
For important applications like nearest neighbor search, having an unbiased inner product esti- mator is essential. However, TURBOQUANT presented in Section [.] does not provide unbi- ased inner product estimates with query vectors. To illustrate this, consider the case with a bit- width of b 1. In this scenario, the optimal codebooks that solve the optimization problem in Eq. 3. for sufficiently large d, are /=v2/md)) This implies that the quantization map for TURBOQUANT, nse Qusa(ar) = sign [II. .x) for any æ E Id, and the dequantization map is Qual 22/rd IIT z for any = E (1)+ Therefore, for large enough d, according to Lemma 4 we have E. [[y. Quil (x)a 2 (y,z), which has multiplicative bias of 2/T. This bias diminishes with increasing bit-widths b, as we empirically demonstrate Section
To address this bias, we propose solution that combines TURBOQUANT with an instance of QJI. ZZndieh et al.) (2024a). Specifically, let Quse be the quantization map corresponding to TURBOQUANT with a bit-width of
For any E gd-1 the residual vector, defined as Q=i (Quee (x=). has small L2 norm, i.e., expectation E[ VC(fx, ( (per Eq. 3 ). We can then apply the QJL quantization map Qajı on this residual vector, resulting in an overall bit-width of b and providing the following unbiased inner product estimator:
yy, Q=1 (Qnee(x))) + ||||| -y, Qail (Qqz(r))).
More formally, the quantization map Qprod 4d-1 [20-1]d (-1, 1)dd defined as:
Qproa (x) = [Qaeo (z), Qaji (x Q=1 (Qnea (x))) || Qui (Qnee
pseudocode for this procedure is given in Algorithm
We prove the main result for TURBOQUANT prod in the following theorem and prove it in Ap- pendix C
Theorem (Performance Guarantee: TURBOQUANT prog). For any bit-width b 2 and any vector E gd-1, 1, the procedure QUANT (x) in Algorithm 2 outputs index vector idx [2"-114 along with a sign vector qil {-1,1}d and positive number ?/ 0. When these vectors and the scalar value are passed to the primitive DEQUANT (idx, qjl,7), it produces a reconstructed
vector i R&d that for any vector y Red satisfies the following properties:

---

Published as a conference paper at ICLR 2026
Expected inner-product Ea Ky. Φ}] (y.z)
Inner-product distortion defined as Dprod = Ea Ky x.) - (y. 83pp]
is bounded by
Dprea I Va
1 for any b 2 O.
2
For small bis-widths, specifically b 1,2,3, 4, Dprod exhibits finer-grained distortion val-
ues: Dprod s 1.57 0.56 0.18 0.047 respectively.
2
EXPERIMENTS
All experiments are performed using single NVIDIA A100 GPU. The first set of experiments em- pirically validates the theoretical results, and the second evaluates the performance of our methods downstream tasks, specifically KV cache quantization and nearest neighbor vector search.
2.1
EMPIRICAL VALIDATION
(a) TURBOQUANT, prod
Bitwidth
Bitwidth
Bitwidth 3
Bitwidth
1.5
1.5
1.5
1.5
Frequency
1.0
Frequency
2.0
Frequency
L.-
Frequency
7.0
0.55
0.5
0.0
0.1
0.01
0.1
0.0
0.1
0.1
0.0
0.1
0.1
Product Distortion
Inner Product Distortion
Inner Product Distortion
Inner Product Distortion
(b) TURBOQUANT,
x10
Bitwidth
x10
Bitwidth =
x1
Bitwidth
X
Bilwidth 4
1.5
Frequency
Frequency
Frequency
Frequency
1.0-
0.5
0.0
0.1
11.0
0.1
0.0
0.11
0.0
6.0
0.1
Inner Product Distortion
Inner Product Distortion
Inner Product Distortion
Inner Product Distortion
Figure 1: Distribution of Inner Product error for TURBOQUANT prod and TURBOQUANT
In this section, we validate the theoretical results using experiments on the DBpedia Entities dataset, which is embedded in 1536-dimensional space via OpenA13 embeddings. We randomly sample 100,000 points as the training set and extract 1,000 distinct entries as the query set.
We compare two quantization methods: TURBOQUANT, prod. optimized for unbiased inner product estimation, and TURBOQUANT ase which minimizes mean squared eтror (MSE) between quantized and original vectors. Both methods are applied to estimate inner products by quantizing the train- ing set and analyzing distortion across varying bit widths. As shown in Fig. [ increasing the bit widths reduces variance both methods. However, TURBOQUANT introduces bias inner product estimation, which diminishes and converges to zero with higher bit widths. In contrast, TURBOQUANT proa remains unbiased across all bit widths, confirming the theoretical guarantees.
In addition to histograms, we also plot in Fig. the average inner product emror and MSE between the original and quantized vectors for different bit-widths. These plots are drawn against the up- per and lower bounds established in theoretical analysis and confirm that the results align with the theoretical predictions. Specifically, for inner product estimation, the TURBOQUANTprO ap- proach performs better at lower bit ratios. However, the bit count increases, TURBOQUANTmSe reduces bias and ultimately achieves superior performance in inner product estimation.

---

Published as a conference paper at ICLR 2026
(a) Inner Product Error
(b) MSE
(c) Speedup
Inner Product Error (Drra)
Mean squarod orror (Dwn)
Turteiquar....
Turhafjuent 1-htt
Baund
Lover Bound:
Upper Bound:: Cap
Speedup over einsum
Turboouunnt
TurboDuent 2eb6
Upper Bound Agp
20
Bitwidth (6)
Bitwidth (b)
425 611
Sequence
length
Mois 10x 18
Figure 2: (a) Inner-product error, (b) mean squared error (MSE) versus theoretical bounds, and (c)
speedup factors for QK" computation in the KV-cache at different bit-wid Speedup is measured
relative to the PyTorch einsum baseline.
2.2
NEEDLE-IN-AN MIEDLE-I---HAASTTAE
SnapKV Score: 0.858
PyramidKV
KIVI Score: 0.981
Score: 0.895
Dapt Percent
075
Depth Parcemt
22
0.75
075
68
44
0.50
66
0.50
0.0
87
89
1046
0.00
0.00
100
0.00
Taken Limit
Taken Limit
Taken Limit
PolarQuant Score: 0.995
Full-Precision Score: 0.997
TURBOQUANT Score: 0.997
Dapth Portent
Dapth Persent
Persent
475
075
33
88
84
0.50 g
66
64
0.50
450
78
0.25
78
0.25
0225
88
0
108
Takan Limit
Takan Limit
Takan Limit
Figure 3: Evaluation of L.lam-33 1-st--T-tttt- ruct on the Sheedle-n-A-Haystaed test, where a model must retrieve a hidden sentence from long-context sequences. While some methods struggle with recall, TURBOQUANT, despite being more than 4x quantized, achieves the same exact perfor- mance as the uncompressed baseline.
The Beeedle-InA--Hyyttae Test" Kamradi (2023) evaluates a model's ability to retrieve a unique sentence (the "needle") embedded within long document (the "haystack"). Following Fu et al. (2024), we perform this test using the Llama-3.. 1--B-IInstruee model across varying document lengths from 4k to 104k tokens. Performance is measured using the recall score, which reflects the accuracy of retrieving the hidden sentence.
We compare our method to state-of-the memory-efficient approaches, including PolarQuant Han et al. (025a)), SnapKV Li et al. (2024), PyramidKV V Cai al. (2024), and KIVI Liu al. 20244)). all evaluated under a memory compression ratio of 0.25 (i.e., using only 25% of the full K cache). As shown in Fig. 3 quantization methods with theoretical guarantees such PolarQuan and TURBOQUANT outperform token-level compression (SnapKV, PyramidKV V) and scalar quantiza- tion methods without formal guarantees (KIVI). Remarkably, TURBOQUANT matches the perfor- mance of the full-precision model even at 4x compression, highlighting its robustness for long- context tasks.
8

---

Published as a conference paper at ICLR 2026
Method
KV Size
SingleQA
MultiQA
Summarization Few shot
Synthetic
Code
Average
Llama-3.
3.t.....1....... ----Instuuct
Full Cache
16
45.29
46.
26.55
68.38
59.54
46.28
50.06
KIVI
3
43.38
37.99
27.16
68.38
59.50
44.68
48.50
KIVI
5
45.04
45.70
26.47
08.57
59.55
46.41
50.16
PolarQuant
3.9
45.18
44.48
26.23
68.25
60.07
45.24
49.78
TURBOQUANT (ours)
2.5
44.88
44.01
26.75
68.39
59.07
46.03
49.74
TURBOQUANT (ours)
3.5
45.01
45.31
26.00
68.63
59.95
46.17
50.06
Ministral
Cache
47.53
49.06
26.09
66.83
53.50
47.90
49.89
TURBOQUANT (ours)
2.5
48.38
49.22
24.91
66.69
53.17
46.83
49.62
Table I: LongBench-Vi v1 Bai et al. (2023) results of various KV cache compression methods on Llama-3.1-8B- Instrruct.
2.3 END-TO-END GENERATION ON LONGBENCH
We evaluated TURBOQUANT on the LongBench dataset Bai et al. (2023), using the more uni- formly distributed LongBench-E subset ensure fair comparison across context lengths. Our method is compared to previous approaches in Section using both Ll L1ama-3.1-88 L--B-Insttucct and Ministral-7B-Instruue
Unlike KIVI and PolarQuant, which skip quantization for generated tokens, TURBOQUANT applies quantization throughout the streaming process.
As shown in Table [] TURBOQUANT consistently outperforms other methods, achieving strong results even under low-precision settings-specificalll 2.5-bit and 3.5-bit quantization. These non- integer precisions arise from Iwo-tier channel-wise quantization strategy: outlier channels allocated more bits (e.g., 32 channels at bits, 96 at bits for 2.5-bit precision), inspired by prior work Zandich al.] (2024a); (Su al. (2025). Despite operating lower bitwidths, TURBOQUANT matches the performance of unquantized baselines while achieving over 4.5x compression.
2.4 NEAR NEIGHIBOUR SEARCH EXPERIMENTS
In this section, we demonstrate the effectiveness of TURBOQUANT in near-neighbor search tasks. Experiments are conducted on the DBpedia Entities dataset(Takkun el. (202T), encoded using Ope- nAI3 embeddings in 1536- and 3072-dimensional spaces.... T well as a lower-dimensional
dataset using standard GloVe embeddings Pennington et al. 2014)).
We sample 100,000 points as the training set and 1,000 distinct entries the query set, except for GloVe, which uses a pre-existing 10,000-query set. We compare TURBOQUANT against two base- lines: Product Quantization Douze et al. (2224) and RabitQ Gao et al. (2024). based on recall @ k, which measures how often the true top inner product is captured within the top-k approximated re- sults.
Product Quantization (PQ) Douze et al. 2024) uses k-means to construct codebooks, incurring AVX2-based
exponential growth in storage bit-width increases. For efficient querying. implementations with LUT256 (256 codewords), grouping 4 coordinates for 2-bit and 2 coordinates for 4-bit quantization. Although PQ benefits from using the same data for training and evaluation, still suffers from quality degradation at low-bit LUTI6 configurations.
Rabit Gao al. (2024) lacks vectorized implementation and GPU support, leading significantly slower CPU performance. Furthermore, its actual bit usage is higher than reported due to hidden computational overheads, which are not included the bit ratio accounting.
Despite these advantages favoring the baselines, TURBOQUANT consistently achieves higher call@k across datasets and bit-widths, confirming its robustness and superiority high- dimensional, guantization-bart based search tasks.
at http:///tttttteeeee///eeeeeeeeee

---

Published as a conference paper at ICLR 2026
(a) Glo d=200
(b) OpenA13 d=1536
(c) OpenA13 dd3072
0 mm
Racall 1@k
Pecall 1@k
TurbeQuart TurbeQvant bite
Recall 1@k
TurboQuart
Turborquant
0.3
PQ2 bits
0.500
PQ bits
FO 4 Biz
PG 4 bis btt
0:27
TurboCuam 2 bit
Tudb-Cuant 4 Lita
0.0
0.500
HobiQ
Habrt bit
64
32
16
Top-k
Top-k
Top-k
Figure 4: Recall comparison on different datasets with different embedding dimensions.
REFERENCES
Elastic search.,
2025.
https://ww.ellsticcco//eetrrreee searchh
vector- search
Qdrant vectore search., 2025.
https://gdrant.tecch
Pgvector search., 2025. htttes////thhb..ccoo///eeetrrrrr
Pinecone vectore database., 2025, https::/ww.piincoom
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprint arXiv:2303.0877 087744 2023.
Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh. Oblivious sketching of high-degree polynomial kernels. In Pro- ceedings of the Fourleenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 141-160. SIAM, 2020.
Joshua Ainslie, James Lee-Thorp, Michiel de Jong, Yury Zemlyanskiy, Federico Lebron, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head check- points. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Pro- cessing, pp. 4895-4901, 2023.
Anthropic. Claude, 2024. https: brtps://www.r /www.
claue 3 fami ly
Saleh Ashkboos, Amirkeivan Mohtashami, Maximilian Croci, Bo Li, Pashmina Cameron, Martin Jaggi, Dan Alistarh, Torsten Hoefler, and James Hensman. Quarot: Outlier-free 4-bit inference in rotated 1lms. arXiv preprint arXiv:2404. 00456, 2024.
Artem Babenko and Victor Lempitsky. Additive quantization for extreme vector compression. In Proceedings of the IEEE Conference Computer Vision and Paltern Recognition, pp. 931-938, 2014.
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308. 14508, 2023.
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint a a5x5v:2004.05150 2020.
Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Baobao Chang, Junjie Hu, et al. Pyramidkv: Dynamic kv cache compression based on pyramidal information funneling. arXiv preprint arXiv:24066 020690 2024.
Jerry Chee, Yaohui Cai, Volodymyr Kuleshov, and Christopher M De Sa. Quip: 2-bit quantization of large language models with guarantees. Advances in Neural Information Processing Systems, 36:4396 4429, 2023.
10

---

Published as a conference paper at ICLR 2026
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Damai Dai, Chengqi Deng, Chenggang Zhao, RX Xu, Huazuo Gao, Deli Chen, Jiashi Li, Wangding Zeng, Xingkai Yu, Y Wu, et al. Deepseekmoe: Towards ultimate expert specialization in mixture- of-experts language models. arXiv preprint arXiv:2401 100006666. 2024.
Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. Gpt3, int8 O: 8-bit matrix multiplication for transformers scale. Advances in Neural Information Processing Systems, 35: 30318-3000 -00322, 2022.
Shichen Dong, Wen Cheng, Jiayu Qin, and Wei Wang. Qaq: Quality adaptive quantization for Ilm kv cache. arXiv preprint arXiv:2403.0460 2024.
Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre- Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library. 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.
Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, and Jonathan Larson. From local to global: graph rag approach to query-focused summariza- tion. arXiv preprint arXivv2404. 16130, 2024.
Elias Frantar, Salch Ashkboos, Torsten Hoefler, and Dan Alistarh. Gptq: Accurate post-training quantization for generative pre-trained transformers. arXiv preprint arXiv:2210.173225 2022.
Yao Fu, Rameswar Panda, Xinyao Niu, Xiang Yue, Hannaneh Hajishirzi, Yoon Kim, and Hao Peng. Data engineering for scaling language models to 128k context. arXiv preprint arXiv:240..10171, 2024. URL
Long- Context Data Engineering
Jianyang Gao, Yutong Gou, Yuexuan Xu, Yongyi Yang, Cheng Long, and Raymond Chi-Wing Wong, Practical and asymptotically optimal quantization of high-dimensional vectors in euclidean space for approximate nearest neighbor search. arXiv preprint arXiv:2409.000 09913, 2024.
Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, Haofen Wang, and Haofen Wang. Setrieval-augmente generation for large language models: A survey. arXiv preprint arXiv:2312. 10997, 2, 2023.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approximate nearest neighbor search. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.
2013.
Allen Gersho. Asymptotiallly optimal block quantization. IEEE Transactions on information the- ory, (5()))373-388 1979.
Allen Gersho. On the structure of vector quantizers. IEEE Transactions Information Theory, 28
(2):157-166, 1982.
Han Guo, William Brandon, Radostin Cholakov, Jonathan Ragan-Kelley, Eric P Xing, and Yoon Kim. Fast matrix multiplications for lookup table-quantized 1lm.. arXiv preprint arXiv:2407. 10960, 2024.
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Ku- mar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pp. 3887-3896. PMLR, 2020.
Insu Han, Praneeth Kacham, Amin Karbasi, Vahab Mirrokni, and Amir Zandich. Polarquant: Quan- tizing kv caches with polar transformation. arXiv preprint arXiv:2502.02617. 2025a.
Insu Han, Michael Kapralov, Ekaterina Kochetkova, Kshiteej Sheth, and Amir Zandich. Balancekv: Kv cache compression through discrepancy theory. arXiv preprint arXiv:2502.0788. 07861, 2025b.
11

---

Published as a conference paper at ICLR 2026
Coleman Hooper, Schoon Kim, Hiva Mohammadzadeh, Michael W Mahoney, Yakun Sophia Shao, Kurt Keutzer, and Amir Gholami. Kvquant: Towards 10 million context length Ilm inference with kv cache quantization. arXiv preprint ar arXiv:2401.18079, 2024.
Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33 2010.
Greg Kamradt, Needle haystack - pressure testing llms., 2023. https::/github.com com/
Dikamrat/LLMIee Needle e InAHaystack
Hao Kang, Qingru Zhang, Souvik Kundu, Geonhwa Jeong, Zaoxing Liu, Tushar Krishna, and Tuo Zhao. Gear: An efficient kv cache compression recipefor near-lossless generative inference of Ilm. arXiv preprint arXiv:2403.05527, 2024.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Omar Khattab and Matei Zaharia. Colbert:
Efficient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference research and development in Information Retrieval, pp. 39-48, 2020.
Junhyuck Kim, Jongho Park, Jaewoong Cho, and Dimitris Papailiopoulos. treme ky cache compression via sparse coding over universal dictionaries. arXiv preprint arXiv:2412.08890, 2024.
Lexico: Ex-
Schoon Kim, Coleman Hooper, Amir Gholami, Zhen Dong Xiuyu Li, Sheng Shen, Michael W Mahoney, and Kurt Keutzer. Squeezellm: Dense-and-sparse quantization. arXiv preprint arXiv:2306.07629, 2023.
Yuhong Li, Yingbing Huang, Bowen Yang. Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Llm knows what you are looking for before generation. arXiv preprint 2404 14469, 2024.
Lin, Jiaming Tang, Haotian Tang, Shang Yang, Wei-Ming Chen, Wei-Chen Wang. Guangxuan Xiao, Xingyu Dang, Chuang Gan, and Song Han. Awq: Activation-aware weight quantization for on-device IIm compression and acceleration. Proceedings of Machine Learning and Systems, 6: 87-100, 2024.
Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. Scissorhands: Exploiting the persistence of importance hypothesis for I1m kv cache compression at test time, Advances in Neural Information Processing Systems, 36, 2024a.
Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu. Kivi: A funing-free asymmetric 2bit quantization for kv cache. arXiv preprint arXiv:2402.02755, 2024b.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions information theory, 28(2): 129-137, 1982.
Joel Max. Quantizing for minimum distortion. IRE Transactions Information Theory, 6(1):7-12, 1960.
PF Panter and Wu Dite. Quantization distortion in pulse-count modulation with nonuniform spacing of levels. Proceedings of the IRE, 39(1):44 48, 1951.
Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word representation. In Alessandro Moschitti, Bo Pang. and Walter Daelemans (eds.), Proceedings of the 2014 Conference Empirical Methods in Natural Language Processing (EMNLP). pp.
1543, Doha. Qatar, October 2014. Association for Computational Linguistics. doi: 10. 1/154111D14-116 URL utl/:/teee///eaaanttooooooyyyygp
12

---

Published as a conference paper at ICLR 2026
Keshav Santhanam, Omar Khattab, Jon Saad-Falcon, Christopher Potts, and Matei Zaharia. Colbertv2: Effective and efficient retrieval via lightweight late interaction. arXiv preprint arXiv:2112.01488, 2021.
Jay Shah, Ganesh Bikshandi, Ying Zhang. Vijay Thakkar, Pradeep Ramani, and Tri Dao. Flashattention-3: Fast and accurate attention with asynchrony and low-precision. arXiv preprint arXiv:2407.08608, 2024.
Claude E Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-44 423, 1948.
Claude Shannon et al. Coding theorems for a discrete source with a fidelity criterion. IRE Nat. Conv. Rec, (14421633),, 1959.
Noam Shazeer. Fast transformer decoding: One write-head is all you need. arXiv preprint 1rXiv:1911.02150, 2019.
Zunhai Su, Zhe Chen, Wang Shen, Hanyu Wei, Linge Li, Huangqi Yu, and Kchong Yuan. Rotatekv: Accurate and robust 2-bit ky cache quantization for Ilms via outlier-aware adaptive rotations, 2025. URL/pttps::/axxxvvcoo
Gemini Team, Petko Georgiev. Ving Ian Lei, Ryan Burnell, Libin Bai, Anmol Gulati, Garrett Tanzer, Damien Vincent, Zhufeng Pan, Shibo Wang, et al. Gemini 1.5: Unlocking multimodal under- standing across millions of tokens of context. arXiv preprint arXiv:2403.05534 2024.
Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. BEIR: A heterogeneous benchmark for zero-shot evaluation of information retrieval models. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. http:ttts///opeeeeeeeee
net htt://oommmmam weeee/oormmidd-Cauut WCu6T5X jeJ
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. NewrlPS, 2017.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
Jingdong Wang, Ting Zhang, Nicu Sebe, Heng Tao Shen, et al. A survey learning hash. IEEE transactions on pattern analysis and machine intelligence, 40(4))769-790, 2017.
Xiang Wu, Ruiqi Guo, David Simcha, Dave Dopson, and Sanjiv Kumar. Efficient inner product approximation in hybrid spaces. arXiv preprint urXiv:/903: 1903006600 2019.
Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. Smoothquant: Accurate and efficient post-training quantization for large language models. In International Conference on Machine Learning, pp. 38087-38099. PMLR, 2023a.
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming
language models with attention sinks. arXiv preprint 2rXiv:2309.17453 2023b.
June Yong Yang. Byeongwook Kim, Jeongin Bae, Bcomseok Kwon, Gunho Park, Eunho Yang, Se Jung Kwon, and Dongsoo Lee. No token left behind: Reliable kv cache compression via importance-awan aware mixed precision quantization. arXiv preprint arXiv:2402. 20..24422//099 /8096, 2024.
Yuxuan Yue, Zhihang Yuan, Haojie Duanmu, Sifan Zhou, Jianlong Wu, and Liqiang Nie. Wkvquant: Quantizing weight and key/value cache for large language models gains more. arXiv preprint arXiv:2402. 12065, 2024.
Paul Laszlo Zador. Development and evaluation of procedures for quantizing multivariate distribu- tions. Stanford University, 1964.
Amir Zandieh, Majid Daliri, and Insu Han. Qjl: 1-bit quantized transform tion with zero overhead, 2024a.
transfrmm for kv cache quantiza-
03482
Amir Zandich, Insu Han, Vahab Mirrokni, and Amin Karbasi. Subgen: Token generation in sublin- time and memory. arXiv preprint 20X6022402.06082, 2024b.
13

---

Published as a conference paper at ICLR 2026
Tianyi Zhang. Jonah Yi, Zhaozhuo Xu, and Anshumali Shrivastava. Kv cache is 1 bit per channel: Efficient large language model inference with coupled quantization. arXiv preprint arXiv:2405.03917. 2024a.
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H2o: Heavy-hitter oracle for efficient gen- erative inference of large language models, Advances Neural Information Processing Systems, 36, 2024b.
14

---

Published as a conference paper at ICLR 2026
A EXTENDED RELATED WORK
Beginnings of VQ. The vector quantization theory started by Shannon's 's seminal work Shannon (1948); [Shannon et al. (1959) on achievable distortion-rate functions. In 1963, Zador Zador (1964) made significant advances by employing high-resolution methods to derive the limiting operational distortion-rate function for fixed-rate quantization high rates that closely matches Shannon's distortion-rate function. However, Zador did not specifically consider implementable algorithms. Gersho's influential paper [Gersho (1979), further advanced the vector quantization by populariz- ing high-resolution theory, simplifying Zador's results, introducing lattice vector quantization, and proposing a key conjecture that shaped the field. Despite these theoretical advancements, the prac- tical applicability of vector quantization remained unclear in early years. The most straightforward encoding method, brute-force nearest neighbor search, was computationally expensive, hindering the adoption of VQ in practice.
Online KV Cache Compression. Several approaches have been proposed to compress the KV cache. These include architectural modifications [Shazeer (2019); Ainslie et al. (2023); Dai et al.
(2024) which restructure the transformer to minimize the number of stored key-value pairs. Addi- tionally, pruning or evicting redundant or less critical tokens has emerged as another approach Belt- agy et al. (2020) Zhang et al. (2024b); [Li et al. (2024a); Xiao et al. (2023b); Zandich et al. (2024b);
Li al. 2024); Han et al. (2025b).
simple yet effective approach to reducing KV cache size is quantizing the KV cache. Several quantization techniques have been developed specifically for this purpose Yue et al. (2024); Yang
cet al. [on4) et al. (2024): Kang et al. (2024); /Zhang et al. (2024a); Liu et al. (2024b): Hooper
al. (022)) Kim al. (2024) Han al. (2025a). Recently, new quantization called QII.. Zandieh
et al. 2024a) introduced an efficient, data-oblivious 1-bit quantization approach based on sketching
techniques, which provides unbiased estimates for inner product queries. This method does not
require tuning or adaptation to the input data and we make use of this technology in our quantizer optimized for inner product distortion.
Product Quantization (PQ). In Near Neighbor (NN) search problem with Euclidean datasets, the index size poses a significant memory bottleneck, often mitigated by quantization techniques, com- monly referred to as Product Quantization (PQ) in the NN literature. Many of these algorithms rely on constructing a quantization codebook using variations of k-means during the indexing phase Je- gou et al. (010); BBabenko & Lempitsky (2014); Ge et al. (2013); Wang et al.] (2017); Guo et al. (2020). Therefore, these methods are ill-suited for online settings due to their requirement for ex- tensive preprocessing.
Recently, a grid-based PQ method was introduced Gao et al. (2024), eliminating the need for pre- processing. This approach operates by projecting uniform grid onto the unit sphere and conducting a search to identify the nearest projection to the data points. While the paper's theoretical guaran- tees are suboptimal, likely due to loose analysis- as practical performance surpasses theoretical bounds- the grid projection and binary search algorithm is also computationally slow and particu- larly inefficient accelerators like GPU because of their algorithm's inherent lack of vectorization, which prevents parallel processing.
B MATHEMATICAL PRELIMINARIES
For random variable æ we denote its differential entropy h(x)) For random variables and y, the mutual information between them is denoted as [(x; v) = h(x) - h(zlg).
Given that TURBOQUANT employs random rotation mitigate worst-case input scenarios, under-
standing the statistical properties of random points on a hypersphere is essential. The following lemma outlines one such property that we will need for analysis and design purposes:
Lemma 1 (coordinate distribution of random point on hypersphere). For any positive integer d if
gd-1 is random variable uniformly distributed over the unit hypersphere, then for any j E [d] the coordinate x, follows the following (sialed/shifted) Beta distribution:
T(d/2) 23 fx(x)= == VT [[(d - (()2)))/2 (1 (1- x2) ---22--)3)) (d-3)/2
15

---

Published as a conference paper at ICLR 2026
In high dimensions this beta distribtion converges the normal distribution fx(+) -V
Proof. (x)x) equals the ratio of the area of a sphere with radius v1 x² in dimension d - 1 to the volume of a unit sphere in dimension scaled down by 1/v1 x² (by Pythagorean theorem). Therefore,
fx(x)=
(1-12 T((d-1)/2
(1 (1-22)(d-2)) 22222222/2 2)/2
1/V1-222 x²
VF. 11/2) (1- 1-=2)ld-3)/
r(d/2)
2/4/2
T(d/2)
B. SHANNON LOWER BOUND ON DISTORTION
The Shannon Lower Bound (SLB) is powerful tool, derived from Shannon's lossy source coding theorem Shannon et al. 1959), that provides a universal lower bound on the optimal achievable distortion rate for any lossy compression scheme. Specifically, the mean-squared error (MSE) distortion measure applied to general d-dimensional sources.
version of SLB tailored for
Lemma 2 (SLB). Let E I& be random vector with arbitrary probability distribution px and finite differential entropy h()). Define the MSE distortion-rate function D(B) for total bit
complexity 2 0 as:
D(px, B) :0)=inff inf
21 [x; S BB.
where the infimum is taken over all joint distributions of x and reconstruction random vector E RRd such that the mutual information y(:;y) is at most B and E || y is the expected MSE distortion, calculated with respect to the joint distribution of x and y. Then, for any bit
complexity B 2 0, the following Shannon Lower Bound holds:
D(px B) - 212200((M)))
d
2Te
This is classic result proved using backward Gaussian test channel (for proof see Cover 1999 Our lower bound result uses corollary of SLB that corresponds to the uniformly distributed random points on the unit hyeprsphere. We present this in the following lemma:
Lemma (SLB for random point on hypersphere). Let gd-1 be a random variable uniformly distributed over the unit hypersphere and define the MSE distortion-rate function D(B) for total bit complexity as per Lemma Then, for any bit complexity 2 the following distortion lower bound holds:
D(B) 2 2B/d
Proof. If we let As denote the area of the hypersphere Sa-1, the entropy of uniform distribution over hypersphere is h(x)) = log2 Aq. Plugging this into the SLB from Lemma 2 we get D(B) >
d
-A22/d 2/d 2 2-2B/d, Using Stirling's approximation formula for Gamma function we have A =
2ne
2n 4/2
((1d)). By substituting this into the inequality obtained from 2 we get the desired lower bound.
2xe d/2 V d
T(d/2)
Lemma
B.2 QJL: 1-BIT INNER PRODUCT QUANTIZATION
As previously stated, we design two VQ algorithms: one optimized for minimizing MSE and the other for minimizing inner product error. We show that MSE-optimal quantizers do not neces- sarily provide unbiased inner product estimates, particularly exhibiting significant bias lower bit-widths. Our solution for inner product quantization is two-stage algorithm. First, we apply the MSE-optimal quantizer using one less bit than the desired bit-width budget, thus minimizing the L2 norm of the residuals. Next we apply unbiased and optimal single-bit quantizer to the residual. For the single-bit inner product quantizer, we utilize the recently proposed Quantized Sabnson-Lindenstrauss (QJL) algorithm Zandich et al. (2024a). which is optimal inner product quantizer with a bit-width one. Here, we present the QJL algorithm and its essential theoretical guarantees.
16

---

Published as a conference paper at ICLR 2026
Definition (QJL), For any positive integer the QJL map Quii R > f-1, +13
1 is defined as:
Qan (x) = sign x) for any a E R
where S E Rdddd is random matrix with iid. entries sampled from the normal distribution N(0,1) 1) and the sign function is applied entry-wise to its vector input. The inverse/dequantization map Qui +-1,+1} + R is defined as:
1 Qaji(z)
S
for any 2 E (-1,
d
In the next lemma we restate the results from Zandieh al. 2024a) that show the QJL is unbiased and also has small inner product distortion:
Lemma 4 (performance guarantee: QJL). Lel Qap and Quji be defined as per Definition For any vector E St-1 and any y Idd we have the following:
Unbiased: E (v. Qui (Qaz(()))) = (y,
Variance Bound: Var ((y. Qqji (x)))) -/2
1
Proof. The unbiasedness immediately follows from Lemma 3.2 of Zandich et al. (2024a). To show the variance bound let 81, 82,... 8m denote the rows of the random matrix in Definition [ We have:
Qun (Qnn = à Σ
4/2-80 sign(s, æ))
Since 8,'s are i.i.d. the above is indeed the average i.idd random samples defined as 2; == /T/2 s, ssig(s, x) for [d]. Let us now upper bound the variance of single 2 using Fact 3.4 from Zandich et al. (202a))
Var (z+) 7/2 Var (s, sign(s, (s) x)) $ T/2 (s] ( 7/2- 11y11.
(4)
where the last equality above follows because 8, y is a Gaussian random variable with mean zero and variance | 2. Now the variance of the average of d i..d. random samples 21, 22.... ... 2d is:
Var (api (Qun (3))))
Σ Var(z)
2d |1y1|2.
d
iE(d
C PROOFS AND TECHNICAL REMARKS
In this section, we provide detailed proofs for each of the main theoretical results presented in the paper, including those for TURBOQUANT TURBOQUANT prod. and the information-theorees lower bound.
C.I TURBOQUANT
Remark (Entropy-Encoding Codebook Pointers). TURBOQUANT'S efficiency can be further in- creased by applying entropy encoding to the indices that point the closest codebook elements. Specifically, the probability of each codeword index appearing in the quantized vectors can be com-
+
puted as Pt S fx(x) dz. Optimally coding the indices. reduces the average bit-width
to nearly the entropy of the distribution {ps (ps)ietss) This lossless compression does not affect the distortion and provides bit-width reduction at no cost. The most significant reduction occurs for b 4, 4, where the entropy of {ps Trejo is approximately 3.8. Detailed calculations for optimal prefix codes reveal that the average widtw can be reduced by 5%. However, given the limited gain, we have chosen not to incorporate this technique into TURROQUANT maintain simplicity and speed.
17

---

Published as a conference paper at ICLR 2026
Theorem (Performance Guarantee: TURBOQUANT For any bit-width 2 and any vector a E gd-1, , the procedure QUANT use (x) in Algorithm 1 outputs an index vector idx E [2"]á. When this index vector is passed to the primitive DEQUANT (idx), it produces a reconstructed vector E IRd that satisfies the following distortion bounds:
MSE defined Dase = E=ll =1|21 is bounded by Duse S V3n for any b 2 0.
2"
For small bit-widths, specifically b 1,2,3. the MSE exhibits finer-grained distortion values:
Duse 2 0.36, 0.117, 0.03, 0.009, respectively.
Proof. We start the proof by showing that Dasa = d. C(Jx, b), where C(Jx, b) the optimal MSE
cost for scalar quantizer defined in Eq. (3). Let ý be defined as per line on Algorithm Since II
a rotation matrix we can write: | - x 2 |II x U|ا.. Using the notation y = II æ as per
line of Algorithm and plugging this into the definition of Dece we can write:
Dase
Ellly
Σ jEld
E
|1y
Σ jE(d
E [1y; Cidxy [2]
|1y1 Cidzi 11
=d-
min
|or |0- -x(()x((x)) do
-Ise ScaS Segh
=d-C(fx,
The third equality above follows from the definition of ÿ in line of Algorithm and the fourth line above follows because all y have identical distribution of yj (+) shown in Lemma | The last two lines above follows because Cidx, is chosen to be the nearest centroid to each coordinate in line 6
Now we must bound the optimal k-means cost C(fx: b). For moderate values of d, fx (0, 1/d). By numerically solving the optimization problem in Eq. (3) for values b = 1,2,3, we get that C) x -
0.36 0.1 0.03 0.009 respectively. For larger bit-widths > 4, we can
d.
apply the Panter-Dite Panter & Dite (195T) high-resolution formula for the distortion of fixed-rate scalar quantizer, yielding the following bound:
(fixlo)us dx)
3
V3T 1
C(Jx, 12
2d 45'
This completes the proof.
C.2 TURBOQUANT, prod
Theorem (Performance Guarantee: TURBOQUANT proa). For any bit-width b and any vector E gd-1, the procedure QUANT (x) in Algorithm 2 outputs an index vector idx E [2'-1]d 0. When these vectors and the scalar value are passed to the primitive DEQUANT proal (idx, (ixxx qj1,7), produces a reconstructed vector t E Rd that for any vector Rd satisfies the following properties:
along with sign vector qjl 1-1, and positive number
Expected inner-product Ea [[y, a>)
(z)
Inner-product distortion defined as Dprod == Ed
(2. x3) is bounded by (y. x))
vex $ for any b 2 0.
Dproa
For small bit-widths, specifically b 1,2,3, 4, Dproa exhibits finer-grained distortion val- ues: Dprod Rd 1.57 0.56 0.18 0.047 respectively.
18

---

Published as a conference paper at ICLR 2026
Proof. First we compute the conditional expectation of the inner product estimate (y. .) condi-
tioned on Tase as follows:
E [y, 3)) [insa]
= E
[(2,, Tinna + Tag1) [nase]
(y, Fnna) + E
(y, Inaa) + (,,rr)
(,, x),
where the first equality follows from the definition of x in line 12 of the algorithm. The third equality above follows from Lemma 4 and last line follows from definition of the residual vector -nae in line 6 Now can computed the unconditional expectation using the law of
total expectation: Es Ky, x) = Ea [ [yy, ( [naa]] = Ey a)] = (y, æ),, which proves the first
claim of the theorem.
We apply the same conditioning on Tnees when computing the distortion, and then compute the resulting conditional distortion:
Ky. x) (y,, x)
Duse
E
(yy, x)) (y, Tase + Ø
Tnse
[(y. r)) - (y,, mggiil
E
Tnse
Var
( ألحام @nso)
| 1
2d
where the second equality above follows from the definitions of and Enee in lines and 10 of Algorithm 2 The third line above follows because [1 @qn1)] (y. r). by Lemma The last line follows from the variance bound of QJI. estimator shown Lemma and using the fact that Zq in line II is re-scaled by ||
Now by law of total expectation along with the fact that r = x Unse we can bound the inner product distortion follows:
prod
E Zone
(1,, x)) (y), x3) Fuse
||
[E[| 2c
Basa
2d
| Duse.
2d
The theorem follows by invoking the MSE bounds from Theorem with bit-width b 1.
C.3 LOWER BOUNDS
We show that TURBOQUANT achieves optimal distortion rate, up to small constant factor, for any bit-w by proving lower bounds on the best achievable distortion for any compression algorithm. Our lower bound proof leverages Yao's minimax principle. This principle allows to relate the lower bound for randomized algorithms with worst-case deterministic input vectors to the lower bound for deterministic algorithms with randomized input vectors. Subsequently, we derive a lower bound on the achievable distortion rate for the latter using Shannon's 's lower bound (SLB) presented in Appendix [.. Formally, we prove the following theorem.
Theorem 3 (Lower Bound on Best Achievable Compression Distortion). For any randomized guantization algorithm Q gd-1 - {0, 1]bd with bit-width b and any reconstruction map Q-1: {0, [0,1)*b 1]bd + Rd, there exist hard input instance x E Sd-1 such that:
1
Duso (Q)
E -
40
Furthermore, there exists y E gd-1 such that:
D pproa (Q) = E
(y, x) - (y, Q (Q(x))))
2
>
1
d 4b
19

---

Published as a conference paper at ICLR 2026
We note that comparable lower bound for the worst-case distortion in vector quantization be derived using "sphere packing" arguments (indeed, with larger constants as this a harder prob- robust and relevant lower bound for analysis. This because it establishes a lower bound on the expected distortion, rather than the worst-case error, and aligns seamlessly with upper bounds presented in Theorem [ and Theo- rem
lem) Gersho (1982). However, Theorem B offerss
Proof. By Yao's minimax principle the expected MSE of the optimal randomized compression al- gorithm for worst-case inputs (Dnee) is equal to the expected MSE of the optimal deterministic compression algorithm when applied to inputs drawn from maximally difficult randomized distri- bution. By definition, the MSE of the latter scenario is lower-bounded by the best achievable MSE for inputs uniformly distributed on the unit hypersphere.
The best achievable MSE for compression algorithm with bit-width b, operating uniformly distributed inputs from the sphere Sd-1, is lower bounded in Lemma Therefore, by invoking
Lemma 3 we conclude that Dase 45-
Furthermore, from Dace and using the definition of Dase conclude that:
Duse
Σ
110- (Q(()))))
j=1
Σ
[(ee, - (-
1
>
46"
By pigeonhole principle there exist index j E [d] such that E [(ee, (e(,)=((((x))))
qn. which completes the proof.
D ADDITIONAL EXPERIMENT
As observed in Fig. 5 when quantizing to 2 bits, the variance remains constant regardless of the inner product of the original vector in the TURBoQUANTprod approach. However, the same plot indicates that the bias in the TURBOQUANTISS approach is dependent on the average inner product. As the average inner product increases, the bias also increases.
To compare the efficiency of quantization time, we measure the time required to quantize the training (100,000 vectors) using each method, with results shown in Table 2 TURBOQUANT is signifi- cantly faster-by several orders of magnitude-than both Product Quantization Douze et al. (2024) and RabitQ Gao et al. 2024). This efficiency stems from TURBOQUANT'S fully vectorizable design, which allows seamless GPU acceleration. In contrast, RabitQ lacks a GPU implementation and can- not be vectorized, resulting substantially slower runtimes. Product Quantization also incurs high latency due to its reliance on iterative k-means training, which is inherently slow and sequential.
Approach
d=200
d=1536
d=3072
Product Quantization
37.04
239.75
494.42
RabitQ TURBOQUANT
597.25
2267.59
3957.19
0.0007
0.0013
0.0021
Table 2: Quantization time (in seconds) for different approaches across various dimensions using 4-bit quantization.
E IMPLEMENTATION
The TURBOQUANT algorithm, as detailed Algorithm [ (for MSE-optimal quantization) and Al- gorithm (for inner product quantization), incorporates random rotation matrices applied to the
20

---

Published as a conference paper at ICLR 2026
(a) TURBOQUANT prod
x IPf
IP
x10"
Avg 0.06
xIf Avg 0.10
X Avg 0.17
Frequency
Frequency,
Frequency
Frequency.
13
3.00
0.05
-0.05
0.015
0.05
0,00
0.05
0.00
0.15
Inner Product Distortion
Inner Product Distortion
Inner Product Distortion
Inner Product Distortion
(b) TURBOQUANT ...
XI0 Avg IP 0.01
Avg IP 0.06
xII Avg 0.10
X10
IP 0.17
Frequency
Frequency
Frequancy
Prequeney
50
0000
-0.15
0.I15
0.15
Inner Product Distortion
Inner Product Distortion
Inner Product Distortion
Inner Product Distortion
Figure 5: The variance of Inner-product error remains constant for TURBOQUANT TURBOQUANT increases with the average inner product. Bit-width is =
prod while in
input embedding vectors during both quantization and dequantization stages. This transformation crucial for the algorithm's performance. In practice, the rotation matrices implemented as structured matrices, specifically yandomized Hadamard transforms Ahle et al. (202)). This involves randomly flipping the signs of the embedding vector coordinates, followed by the fast Hadamard transform (FHT), enabling matrix-vector multiplication in (d log d) time, significant improve- ment over the naive (dd) complexity. This efficient transformation beneficial for both CPU and GPU architectures.
The overall quantization process Qproa with bit-width b be conceptualized in stages. First, TURBOQUANT (Quse) with bit-width b 1 is applied to the input vector æ. Second, the resid- ual error of this stage, r, is then quantized using a 1-bit Quantized transform, denoted as qr](r). The final quantized representation 전 stores the necessary information from both (m)) and qrl(
(QJL)
Vector Search. For efficient search vector dataset æ1.... Fy E Rd., vectors are quantized using TURBOQUANT to yield . ..n. Given a query E IRd, we want to estimate the inner products (g, 2;)) through computing (g. Q (x:))- By dequant primitives in Algorithm and Algorithm 2 we have (q. ( [[qji(r:)) (Sq. qr](r:)) (IIq, CQm, where ey
the centroids that minimize the objective in Eq. (3) and Sq and II are randomized Hadamard
transforms applied on which can be computed very quickly.
Computing the first inner product reduces to accumulating the coordinates of Sq with signs given in the quantized vector qjl(r.). The second inner product, (IIq, (xx)()))) can also be computed with high efficiency. This computation involves summing contributions from quantized components of æ., To accelerate this, for each query we precompute small lookup tables (LUTss. For
the k-th component, its LUT, (k), would store values L k-th coordinate of the transformed query. This can be implemented efficiently using the "LUT16" AVX2 in-register lookup technique described by Wu et al. (2019); Ge et al. (2013) for any bit-width b at most 5. This results in (at most) 16-entry tables for each component, and the PSHUFB instruction can then perform multiple such lookups in parallel. This involves quantizing the LUT entries themselves (e.g., 8-bit values) fully leverage the SIMD capabilities.
(IIq)x Cy. where (Iqq)x is the
21

---

Published as a conference paper at ICLR 2026
KV Cache. In LLMs the Key and Value caches K, V R (where n is the sequence length, and is the embedding dimension) can be compressed by quantizing their row vectors using TURBOQUANT prod yielding K and V. During autoregressive decoding, to compute the attention output for a query vector E RR, we first need to calculate attention scores, typically involving Qprod [ These scores, forming a vector E F= (after softmax), are then used to retrieve values via a Oproa
Instead of explicit dequantization of K and V back to full precision in HBM, more efficient approach is use fused GPU kernel. This kernel performs on-the-fly dequantization and mixed- precision matrix multiplication concurrently. It loads the quantized key value data from HBM into on-chip shared memory and registers. The dequantization then performed based on Algorithm 2 (the codebook stored LUT), and the resulting values immediately used in the matrix multiplication (e.g.. GEMM operations with M=1), thereby minimizing costly data transactions with HBM.
Indeed, fast and efficient mixed-precision fused kernels for this type of non-uniform LUT-based quantizers were recently developed in the FLUTE paper Guo al. (2024), initially for the static weights of LLMs. FLUTTESs implementation uses optimized workload distribution (e.g.. Stream- K) techniques to maximize efficiency. Our implementation of TurboQuant mixed-precision matrix multiplication for KV cache compression builds upon their publicly available code, with modifi- cations to the dequantization module. Our findings indicate that this mixed-pre peeeddp-eeiiion fused kernel implementation for KV cache operations is 2-4x faster than conventional floating-pont point GEMM kernels.
Guo
22


Reviews:
[{"review_id": "yG1r6xI5FA", "reviewer": "Reviewer_X81d", "summary": "This paper introduces TurboQuant, an online vector quantization algorithm designed to speed up nearest-neighbor retrieval and vector search by continuously updating codebooks as new data arrives. The core idea is to maintain good quantization quality in a streaming setting by using lightweight updates rather than full re-training. The method provides theoretical guarantees on quantization error and memory usage and is evaluated on several ANN benchmarks to show improved trade-offs between accuracy, latency, and memory.", "questions": "NA", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "S1 Addresses a relevant and timely problem: efficient vector quantization in streaming/online settings, which is important for large-scale retrieval systems.\n\nS2 Includes theoretical analysis that supports the stability and bounded error of the online updates.\n\nS3 Empirical results show clear improvements over static or periodically-retrained quantization baselines in both speed and accuracy.\n\nS4 Paper is generally well-written, and motivations for online updates vs. periodic retraining are clearly explained.", "weaknesses": "The paper is in general quite solid. My question is that the paper seems missing comparisons with stronger or more recent quantization methods, such as those using residual or product quantization variants with adaptive codebook updates, or learned quantizers from recent literature. It’s not entirely clear how TurboQuant performs relative to the current state of the art. Can you provide more literature review and comparisons?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sNp6ee9fzN", "reviewer": "Reviewer_WFrV", "summary": "This paper proposes TurboQuant as method for low-distortion vector quantization. To minimize MSE, TurboQuant first randomly rotates the input vector and then uses k-means generated codebook for each dimension. For an unbiased estimation of inner product, TurboQuant combines the random rotation method for MSE with an unbiased 1-bit quantization method via a residual quantization approach. Theoretical results show that the quantization errors of TurboQuant are close to the optimization. Empirical results show that TurboQuant provides good performance for both KV cache compression and nearest neighbor search.", "questions": "NA", "limitations": "", "rating": 10, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Thank you for the interesting paper! I think this paper is among the best vector papers I have read in this year, and I learned a lot from the paper.\n\nS1: A comprehensive discussion for the applications of vector quantization is provided in the introduction.\n\nS2: TurboQuant has a low quantization complexity and yet strong performance.\n\nS3: The theoretical analysis is in-depth, and the theoretical results are strong.\n\nS4: Combing different vector quantization methods via a residual quantization like approach, despite straightforward, is interesting and makes sense.\n\nS5: The experiment results are strong and cover both KV cache compression and nearest neighbor search.\n\nS6: The presentation is fluent. Although the paper is heavy on math, the author makes it easy to read even for readers that may not be familiar with this area.", "weaknesses": "The paper can be enhanced with more detailed discussions and experiments to compare TurboQuant with RaBitQ and variants (e.g., [1]). Note that I do not think RaBitQ affects the novelty of TurboQuant since the theorical results of TurboQuant are much stronger.\n\nD1: RaBitQ is discussed in the appendix but the discussions are far from insufficient. The original RaBitQ quantization is slow due to the joint search for the optimal quantized bits over dimensions but a recent work [1] solves the problem. Moreover, [1] also uses PCA to significantly reduce the quantization error of RaBitQ. RaBitQ and variants are similar to TurboQuant in that they all use random projection; but they are also different in crucial aspects, (1) they search for quantized bits while TurboQuant uses k-means generated codebook independently for each dimension; (2) they use a re-normalization trick for unbiased inner product estimations while TurboQuant combines random rotation with another vector quantization method. A crucial question is that which design is better for the two purposes, and giving clear answers will be valuable for this area. Some ablation experiments can be added for these design choices, e.g., check the quantization error by using different design combinations. It will even better if some theorical analysis can be conducted.     \n\n[1] SAQ: Pushing the Limits of Vector Quantization through Code Adjustment and Dimension Segmentation", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "46LMgJSN4w", "reviewer": "Reviewer_Autm", "summary": "TurboQuant is proposed to minimize both mean-squared error and inner product distortion in vector quantization by using random rotation and optimal scalar quantizers, achieving near-optimal distortion rates across all bit-widths and dimensions, with a two-stage approach for unbiased inner product estimation, and experimental results validate its superiority over existing methods.", "questions": "Besides the two major concerns mentioned above, I have the following questions:\n\n1) Line 210: Why is multiplication with a random rotation matrix employed? Is the purpose to achieve a beta distribution? Additionally, is this approach originally introduced in this paper?\n\n2) The experiments are insufficient, as comparisons are made with only two quantization methods, and only a few bit-width cases are examined. \n\n3) The “online” property claimed in the title is not explicitly demonstrated in either the theoretical analysis or experimental results.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "As detailed below, I suspect there may be issues with the  two major innovations regarding mean-squared error and inner product distortion.", "weaknesses": "The two major contributions claimed in the paper appear theoretically and logically untenable.\n\n1) **$Q_{mse}$:** This paper does not impose restrictions on the distribution of vector x, nor does it specify whether the elements of x are independent. If the elements are not independent (commonly seen in natural data), then multiplying x by a random rotation matrix cannot guarantee mutual independence among the resulting vector's elements (contrary to the statement in Line 215), rendering simple scalar quantization methods (which quantize elements individually) inapplicable. Consequently, the paper's claimed optimal mse quantization would not hold.\n\n2) **Unbiased $Q_{prod}$:** The multiplicative bias of $2/\\pi$  (derived in Line 296) for the inner product $⟨x,y⟩$ is a constant and does not affect comparisons between different inner products. Therefore, I question the necessity of eliminating this bias by introducing complex quantization schemes for the residual vectors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9YkPjGeRbr", "reviewer": "Reviewer_k6Lz", "summary": "The author introduce a new method for online vector quantization, which does not assume data-specific tuning, which is especially useful for applications such as KV cache compression in LLMs. Their method consist of applying a random rotation to map the (unit-normalized) distribution to a representation with near-independent coordinates whose distribution converges to a known distribution in high dimensions. This allows them to pre-compute per-coordinate $b$-bits codebooks optimized for this distribution, that are suitable for online usage. They further combine this method with QJL to provide unbiased inner product, which is important for KV cache compression.", "questions": "The method is interesting, and its simplicity is a strong argument for applying it. I would ask the authors to clarify their results and clearly justify the quality of the quantization in either KV compression or ANN settings.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 1, "presentation": 3, "contribution": 2, "strengths": "- The proposed method is clearly explain and simple to use.\n- The proposed method is online, making it easily applicable to KV cache compression.\n- The authors provide theoretical justifications and bounds.\n- The proposed method has potential for broad application on LLM inference", "weaknesses": "While the presented method has undeniable strengths, they are undermined by weak experimental validations.\n- For KV compression, all compared methods use a different number of bits, making comparison of the accuracy-compression ratio harder to read. Better analysis of where this method takes place on this trade-off is needed.\n- KL compression is compared to only two other comparison methods, ignoring some other methods, including RotateKV which is cited by the authors. Comprehensive comparison is needed.\n- Authors propose “TurboQuant”, which revolves around the random matrix multiplication followed by per-bit quantization. The QJL and two-tier channel-wise quantization strategy parts come from other work and are generally applicable to some other methods, but are used in the comparison. Analysis of the individual component introduce by the paper would make results more convincing.\n- This method is only compared to existing ones on a single benchmark, and single model.\n\nThe near neighbor search experiments are the least convincing:\n- The method is only compared to PQ, and another method that barely surpasses PQ. For this kind of data-dependant method already surpass these baselines, including codebook-based methods (such as OPQ, RQ, LSQ++) or neural-network based (such as QINCo2 or UNQ).\n- An argument is made about the time needed to quantize the training set, but this has very limited impact. Real-world ANN settings are usually constrained mostly by the search speed and accuracy on CPU, and the limited memory, more than the 1-time quantization. This part lacks justification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)