Conceptio › Archive › arXiv CS

arXiv CSopen access

Block-Sphere Vector Quantization

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Block-Sphere Vector Quantization Heesang Ann∗

[email protected]

Seoul National University

Joongkyu Lee∗

[email protected]

Seoul National University

Min-hwan Oh

[email protected]

arXiv:2605.19972v1 [cs.LG] 19 May 2026

Seoul National University

Abstract Vector quantization is a fundamental primitive for scalable machine learning systems, enabling memory-efficient storage, fast retrieval, and compressed inference. Recent rotationbased quantizers such as EDEN, RabitQ, and TurboQuant have introduced strong guarantees and empirical performance, but the surrounding comparisons have been difficult to interpret because they rely on different distortion criteria, probability regimes, and implementation assumptions. As our first contribution, we provide a unified theoretical comparison of these methods and show that their relative advantages are criterion-dependent rather than absolute: EDEN and TurboQuant are favorable for MSE distortion, EDEN is also effective for expected inner-product distortion, and RabitQ provides strong high-probability control. This comparison further clarifies that EDEN provides particularly strong guarantees for expected distortion measures. As our second contribution, we introduce Block-Sphere Quantization (BlockQuant), a new rotation-based block quantization algorithm designed around the spherical geometry of randomly rotated vectors. Unlike coordinate-wise quantizers, BlockQuant quantizes blocks on the sphere, preserving the geometry of rotated embeddings more faithfully. We prove that this block-spherical design theoretically improves over the baselines considered in this paper for both reconstruction MSE and expected inner-product distortion. Our experiments on real embedding datasets and long-context LLM inference tasks show practical gains that are consistent with our theoretical improvements.

1 Introduction Vector quantization addresses a central bottleneck in large-scale machine learning systems: storing, transmitting, and comparing massive collections of high-dimensional vectors. These vectors appear as embeddings for retrieval, gradients in distributed and federated learning, and key–value cache states in long-context LLM inference. In these settings, quantization reduces storage cost and memory traffic while enabling efficient similarity computation. It has long been a core tool for billion-scale similarity search and is becoming increasingly important in LLM inference, where KV-cache memory grows with batch size and context length and can become a major bottleneck (Johnson et al., 2019; Liu et al., 2024). Recent quantizers using random rotation have attracted significant attention, showing strong performance even in the low-bit regime. TurboQuant explicitly targets both reconstruction MSE and inner-product distortion, and reports strong performance in simple LLM and nearest-neighbor tasks (Zandieh et al., 2025a). RabitQ and its extensions are also rotationbased quantizers, but use a different spherical approximation based on normalized rotated ∗. Equal contribution.

Block-Sphere Vector Quantization

Table 1: Comparison of rotation-based quantizers. The suffixes BSM and UB denote the best-scalar MSE variant and the unbiased inner-product variant, respectively; MSE and PROD follow the original TurboQuant notation. The entries for b = 1, 2, 3, 4 report high-dimensional approximate values. The large-b column reports the high-rate asymptotic upper bounds of the form C · 4−b . All values are computed in this work except † , reported in Zandieh et al. (2025a).

MSE distortion

Quantizer for reconstruction EDENBSM RabitQBSM TurboQuantMSE BlockQuantBSM (p = 2)(ours) BlockQuantBSM (p = 3)(ours)

b=1

b=2

b=3

b=4

Large b

0.363 0.363 0.36† 0.363 0.357

0.117 0.119 0.117† 0.108 0.101

0.0345 0.0374 0.03† 0.0297 0.0271

0.0095 0.0115 0.009† 0.0078 0.0071

2.721 · 4−b – 2.721 · 4−b † 2.015 · 4−b 1.770 · 4−b

Inner product distortion

Quantizer for inner product EDENUB RabitQUB TurboQuantPROD BlockQuantUB (p = 2) (ours) BlockQuantUB (p = 3) (ours)

b=1

b=2

b=3

b=4

Large b

0.571 d−1 0.571 d−1 1.57 † d 0.571 d−1 0.553 d−1

0.133 d−1 0.135 d−1 0.56 † d 0.120 d−1 0.113 d−1

0.0358 d−1 0.0389 d−1 0.18 † d 0.0306 d−1 0.0279 d−1

0.0096 d−1 0.0117 d−1 0.047 † d 0.0078 d−1 0.071 d−1

2.721 −b d−1 · 4

– 17.09 −b † d ·4 2.015 −b d−1 · 4 1.770 −b d−1 · 4

grids; they have recently been explored for both approximate nearest-neighbor search and LLM quantization (Gao and Long, 2024; Gao et al., 2025; Yang et al., 2025; Gao et al., 2026). In parallel, EDEN, which also uses random rotation and coordinate-wise marginal distributions, has been revisited in relation to TurboQuant (Vargaftik et al., 2021; 2022; Ben-Basat et al., 2026b). A major strength of these methods is that they come with theoretical guarantees. However, these guarantees are stated under different criteria: TurboQuant and EDEN are primarily analyzed through expected distortion measures, whereas RabitQ is analyzed through high-probability bit-complexity guarantees. This makes a direct theoretical comparison difficult. Moreover, some recently discussed variants, such as inner-product variants of EDEN and reconstruction variants of RabitQ, have mostly been compared empirically (Ben-Basat et al., 2026a; Gao et al., 2026). In this paper, we close this gap by placing EDEN, RabitQ, and TurboQuant under a unified theoretical framework. We compare these methods under three criteria: reconstruction MSE, expected inner-product distortion, and high-probability bit complexity. This comparison reveals that no existing method dominates across all criteria. Rather, each algorithm reflects a different design principle: EDEN and TurboQuant are strong for reconstruction MSE, EDEN is effective for expected inner-product distortion, and RabitQ provides the strongest highprobability control. This unified view separates the role of the quantization codebook from that of the dequantization rule. 2

Block-Sphere Vector Quantization

Motivated by these findings, we propose Block-Sphere Quantization (BlockQuant), a rotation-based block quantizer designed to improve expected distortion. Whereas EDEN and TurboQuant use coordinate-wise marginal distributions after random rotation, BlockQuant groups coordinates into small blocks and uses the exact block marginal distribution induced by the unit sphere to construct its centroids. This direction is related in spirit to product quantization (Jégou et al., 2011; Ge et al., 2013), but differs in a crucial way: unlike product quantization methods, the codebook of BlockQuant is not learned from data, but is derived from the known spherical distribution induced by random rotation. As a result, BlockQuant achieves the best reconstruction MSE and expected inner-product error among the rotationbased methods. Our lower-bound analysis further shows that increasing the block size moves this framework toward the ideal spherical quantization limit, and our empirical validation supports the theoretical findings. Our main contributions are summarized as follows: • A unified comparison of EDEN, RabitQ, and TurboQuant. We provide a unified theoretical comparison of EDEN, RabitQ, and TurboQuant under three criteria: reconstruction MSE, expected inner-product distortion, and high-probability bit-complexity guarantees. Our analysis shows that the relative strengths of these methods depend on the criterion: EDEN yields strong guarantees for expectation-based distortion criteria, while RabitQ provides stronger high-probability guarantees. • Block-Sphere Quantization. We propose Block-Sphere Quantization (BlockQuant), a rotation-based block quantizer that exploits the spherical geometry of randomly rotated unit vectors. Unlike coordinate-wise quantizers, BlockQuant quantizes lowdimensional blocks using the exact block marginal distribution induced by the unit sphere. We prove that BlockQuant improve both the MSE distortion and the expected inner-product distortion over the baselines considered in this paper, respectively (see Table 1). Our analysis covers both the derivation of approximate constants for small bit-widths and the high-rate asymptotic regime. • A sharper lower bound. We revisit the Shannon lower bound for the MSE distortion, and we obtain a corrected lower bound for our problem setting. We further show that the idealized version of BlockQuant with block size p = d has an MSE upper bound that closely matches this lower bound, both in order and in the leading constant. This indicates that incorporating block-spherical structure is a principled route toward near-optimal MSE distortion. • Empirical validation. We show that BlockQuant achieves lower reconstruction and inner-product distortion than EDEN, RabitQ, and TurboQuant on real embedding data, while maintaining comparable runtime via efficient approximate nearest-centroid search. We further demonstrate that BlockQuant yields practical gains for KV-cache quantization in long-context LLM inference, supporting our theoretical findings.

2 Preliminaries Notations. We denote the unit sphere and the unit ball in Rd by Sd−1 and Bd , respectively. We denote the beta function by Beta and the gamma and digamma functions by Γ and d ψ(t) := dt log Γ(t) = Γ′ (t)/Γ(t), respectively. 3

Block-Sphere Vector Quantization

2.1

Problem Settings

We consider a randomized quantizer Q, with quantization map Q : Rd → {0, 1}b·d , which maps a d-dimensional vector to a b · d-bit string. We denote the corresponding dequantization map by Q−1 : {0, 1}b·d → Rd . The randomness of Q may arise, for example, from random rotations or random projection matrices. Since vector norms can be stored separately, we focus on the quantization of unit vectors x ∈ Sd−1 . Expected distortion metrics. For a randomized quantizer Q, the worst-case MSE of the reconstructed vector is defined as h i 2 DMSE (Q) := max EQ x − Q−1 (Q(x)) 2 . x∈Sd−1

While MSE distortion captures reconstruction quality, inner products are the fundamental quantities in similarity search and retrieval. Thus, we also define the worst-case mean squared error of inner-product estimation as h i 2 DIP (Q) := max max EQ ⟨y, Q−1 (Q(x))⟩ − ⟨y, x⟩ . x∈Sd−1 y∈Sd−1

Rotation-based quantizer. We focus on quantizers that employ a random rotation, including EDEN, RabitQ, and TurboQuant. Let x ∈ Sd−1 be a unit vector and let R be a Haar-distributed orthogonal matrix. Then the rotated vector Rx is uniformly distributed on Sd−1 . Rotation-based quantizers exploit this fact by first applying the random rotation and then encoding the rotated vector using a fixed codebook C. More formally, let Pcode denote the nearest-codeword map associated with C, and let Pdecode denote the corresponding decoder. A rotation-based quantizer encodes x through Pcode (Rx). The raw reconstruction in the original coordinate system is x̄ = R⊤ Pdecode Pcode (Rx) where R⊤ = R−1 . The final dequantized output need not be exactly x̄; depending on the target objective, it may apply an additional rescaling or correction to x̄. All EDEN, RabitQ, and TurboQuant fit into this rotation-based framework, with different choices of the codebook and dequantization rule. Our first goal is to compare the expected distortion metrics DMSE and DIP for EDEN, RabitQ, and TurboQuant within a common framework. For rotation-based quantizers, the expectation EQ appearing in these metrics is taken with respect to the random rotation matrix R. Beyond these expectation-based criteria, we also compare their high-probability guarantees for quantization error (Gao et al., 2026). Motivated by this comparison, we then design efficient quantizers that improve both DMSE and DIP . 2.2

Existing Quantizers for Comparison

EDEN (Vargaftik et al., 2021; 2022). For a unit input vector x, EDEN first applies a random rotation R and rescales the rotated vector by a factor ηq , so that a dimensionindependent scalar codebook can be used. Each coordinate of the rescaled vector is then quantized to its nearest centroid. During dequantization, each code is replaced by the corresponding centroid, the inverse rotation is applied, and the result is rescaled by a scalar ηdq . The choice of ηdq depends on the target objective. A key component of EDEN is the Lloyd–Max scalar codebook CEDEN , constructed for the standard normal distribution (Vargaftik et al., 2022). This choice is motivated by the 4

Block-Sphere Vector Quantization

distribution of randomly rotated vectors: if x ∈ Sd−1 and R is√a random rotation, then each coordinate of Rx tends to follow N (0, d1 ). Thus, choosing ηq = d makes the standard-normal Lloyd–Max codebook well matched to the rotated coordinates. The same quantization rule can be expressed equivalently by scaling the codebook rather (scaled) than the rotated vector Rx. If we define CEDEN = √1d CEDEN , then the output of EDEN can be

written as ηR⊤ (Pdecode (Pcode (Rx))) = ηx̄ for some η ∈ R, where Pcode and Pdecode denote (scaled) the encoding and decoding maps with respect to CEDEN . Then, EDENBSM uses η = ⟨x,x̄⟩ , ∥x̄∥22 which is the best scalar for minimizing the expected squared reconstruction error, and EDENUB 1 uses η = ⟨x,x̄⟩ for unbiased inner-product estimation. These two variants correspond to EDEN-biased and EDEN-unbiased in Ben-Basat et al. (2026a), respectively. For presentation clarity and consistency across methods, we rename them EDENBSM and EDENUB , where the suffixes indicate the reconstruction-oriented and unbiased inner-product variants, respectively. RabitQ (Gao et al., 2025; 2026). RabitQ is a rotation-based quantizer whose practical encoder quantizes the rotated vector using a uniform grid. Although RabitQ is implemented through this grid quantization procedure, it can be equivalently viewed as using a fixed spherical codebook CRabitQ in the rotated domain (Gao et al., 2025). The elements of CRabitQ are obtained by projecting the grid codewords onto Sd−1 . Thus, after applying a random rotation R, RabitQ selects a spherical codeword for Rx, and the raw reconstruction x̄ is obtained by applying the inverse rotation to the decoded codeword. RabitQ applies a scalar correction to the raw reconstruction for reconstruction or innerproduct estimation, like EDEN. For notational consistency with EDEN and TurboQuant, we absorb the scalar correction into the dequantized output. Specifically, throughout this paper, x̄ we regard ⟨x,x̄⟩ as the dequantized output of RabitQUB for unbiased inner-product estimation. This convention is equivalent to the estimator in Gao et al. (2025), where the correction factor is treated as part of the estimation procedure rather than as part of the dequantization output. x̄ = ⟨x, x̄⟩x̄, For reconstruction, the best scalar multiple of x̄ for approximating x is ⟨x,x̄⟩ ∥x̄∥22 since RabitQ uses a spherical codebook. We therefore regard ⟨x, x̄⟩x̄ as the dequantized output of RabitQBSM . Here, RabitQUB corresponds to the original RabitQ in Gao et al. (2025), while RabitQBSM corresponds to RabitQMSE in Gao et al. (2026). Following the same naming convention as above, we use the suffixes to distinguish the unbiased inner-product variant from the reconstruction-oriented variant. TurboQuant (Zandieh et al., 2025a). TurboQuant is a randomized rotation-based quantization method based on coordinate-wise scalar quantization, similar to EDEN. Unlike EDEN, which designs its scalar codebook using a Gaussian approximation to the marginal distribution of randomly rotated coordinates, TurboQuant constructs a Lloyd–Max codebook for the exact coordinate marginal of a uniformly random point on Sd−1 . In this sense, TurboQuantMSE can be viewed as an EDEN-type coordinate-wise Lloyd–Max quantizer that replaces the high-dimensional Gaussian approximation with the exact spherical marginal and uses the scaling convention ηq = 1 (Ben-Basat et al., 2026a). TurboQuant also provides a variant for inner product estimation, denoted by TurboQuantPROD . A b-bit TurboQuantPROD first applies a (b − 1)-bit TurboQuantMSE quantizer to obtain a raw reconstruction x̄, and then allocates the remaining one bit to a QJL-based correction for the residual x − x̄ (Zandieh et al., 2025b). The final estimator combines the inner product 5

Block-Sphere Vector Quantization

with the raw reconstruction and an unbiased one-bit estimate of the residual contribution. This residual correction makes the resulting inner-product estimator unbiased.

3 New Theoretical Guarantees for Comparing Existing Quantizers In this section, we compare the theoretical guarantees of EDEN, RabitQ, and TurboQuant from several perspectives. These algorithms report performance under different criteria; the existing guarantees are summarized in Appendix B. Specifically, Vargaftik et al. (2022) provides an DMSE bound for EDENUB , but does not report guarantees for DIP or highprobability behavior. RabitQ proves a bit-complexity guarantee based on high-probability analysis (Gao et al., 2025), but does not provide expected-distortion guarantees such as DMSE or DIP . TurboQuant provides bounds for both DMSE and DIP , but does not analyze high-probability behavior. We fill these gaps and thereby enable a unified comparison of existing methods under each criterion. Overall, no single quantizer dominates across all measures, in particular, in high dimension, EDENBSM and TurboQuantMSE show the better DMSE approximates than RabitQ, whereas EDENUB performs best for DIP . Based on this observation, in Section 4, we propose quantizers that strictly improve upon existing methods under both criteria. 3.1

MSE Comparison

To compare reconstruction performance, we report either numerical approximations or upper bounds for the DMSE of EDENBSM , RabitQBSM , and TurboQuantMSE . We begin with EDENBSM : for small bit-widths b ∈ {1, 2, 3, 4}, we report numerical approximations, whereas for the large-b regime we use a high-rate upper bound. Proposition 1 (MSE of EDENBSM ). In high dimensions, the MSE of EDENBSM is approximately DMSE (EDENBSM ) ≈ 0.363, 0.117, 0.0345, 0.0095 for b = 1, 2, 3, 4, respectively. Moreover, for large b, EDENBSM satisfies DMSE (EDENBSM ) ≤ 2.721 · 41b . Proposition 2 (MSE of RabitQ √ BSM ). Let z = (z1 , . . . , zd ) be randomly rotated vector of input unit vector and Rj := d zj be the rescaled coordinates of z for j = 1, . . . , d. Define the function Qb (u) = sgn(u) min ⌊|u|⌋ + 12 , 2b−1 − 12 , where the value at u = 0 is irrelevant for continuous distributions. Then the MSE of RabitQBSM is   d X 1 (Rj − αQb (Rj /α))2  . DMSE (RabitQBSM ) = E min α>0 d j=1

Moreover, for large d, if we apply the gaussian approximations, the MSE bound is approximately DMSE (RabitQBSM ) ≈ 0.363, 0.119, 0.037, 0.0115 for b = 1, 2, 3, 4. Remark 1 (MSE of TurboQuantMSE ). For TurboQuant, Zandieh et al. (2025a) report approximate MSE values for b = 1, 2, 3, 4. Since the reported numerical precision differs from the one used in our comparison, we recompute the constants under our notation : For large d, the MSE of TurboQuant is approximately DMSE (TurboQuantMSE ) ≈ 0.363, 0.117, 0.0345, 0.0095 for b = 1, 2, 3, 4, respectively. 6

Block-Sphere Vector Quantization

Discussion on MSE guarantees. From Propositions 1 and 2, together with Remark 1, in high dimensions, both EDENBSM and TurboQuantMSE achieve smaller approximate MSE values than RabitQ across b = 1, 2, 3, 4. The approximated MSE values of RabitQBSM are also comparable, but become slightly larger than those of TurboQuantMSE and EDENBSM as b increases. Moreover, in the high-rate regime, EDENBSM admits an MSE upper bound with the same leading constant as that of TurboQuantMSE . Overall, these results suggest that the Lloyd–Max centroids used in TurboQuant and EDEN, which are optimized for coordinate-wise MSE distortion, are effective in reducing DMSE . The proofs of Proposition 1, Proposition 2 and explanation of Remark 1 are deferred to Appendix D.1, D.2, and D.3, respectively. 3.2

Inner Product Distortion Comparison

In this section, we derive expected inner product estimation error for EDENUB and RabitQUB , then compare the bound with that of TurboQuantPROD . Different from TurboQuantPROD which uses additional QJL algorithm for unbiased estimation, EDENUB and RabitQUB apply 1 scalar multiplication to raw reconstruction, i.e. multiplying ⟨x,x̄⟩ to x̄. In this paper, we call this type of quantizer by (rotation-based) ratio quantizer for inner product. The below theorem shows the general bound on inner product distortion of ratio quantizers. Theorem 1 (General bound on rotation-based ratio quantizer). Let x, y ∈ DSd−1 and E x̄ η := ⟨x, y⟩. Then, the inner product estimation from the ratio quantizers ηbratio := ⟨x̄,x⟩ ,y , the squared error of ηbratio can be expressed by 1 − η2 ∥x̄∥22 − ⟨x̄, x⟩2 2 E . E[(b ηratio − η) ] = d−1 ⟨x̄, x⟩2 Then, we can get the inner product distortion guarantee of EDEN and RabitQ. Corollary 1 (Expected inner product error of EDENUB ). In high dimension, the inner0.133 0.0358 0.0096 product error of EDENUB is approximately DIP (EDENUB ) ≤ 0.571 d−1 , d−1 , d−1 , d−1 , for b = 1, 2, 3, 4, respectively. Moreover, for large b, EDENUB satisfies 2.721 −b 4 (1 + o(1)). d−1 Corollary 2 (Expected inner product error of RabitQ). In high dimension, the inner product 0.135 0.0389 0.0117 error of RabitQUB is approximately DIP (RabitQUB ) ≈ 0.571 for d−1 , d−1 , d−1 , d−1 b = 1, 2, 3, 4, respectively. DIP (EDENUB ) ≤

Discussion on inner product error guarantees. For inner-product estimation, EDENUB gives the strongest guarantee among the methods compared here, closely followed by that of RabitQUB . For b = 2, 3, 4, its expected inner-product distortion is roughly four times smaller than that of TurboQuantPROD , whose distortion is approximately DIP (TurboQuantPROD ) ≈ 1.57 0.56 0.18 0.047 respectively, as stated in Proposition B.4. This comparison suggests d , d , d , d that the rescaling step used in EDENUB and RabitQUB are more effective for reducing expected inner product distortion than the QJL-based correction used in TurboQuantPROD . The reason is that TurboQuantPROD sacrifices one bit for the QJL-based bias correction, rather than using all bits for reconstruction. This bit allocation appears to incur an approximately constant-factor loss, which is visible as the roughly fourfold gap. The proofs of Theorem 1 and Corollaries 1, 2 are deferred to Appendix E. 7

Block-Sphere Vector Quantization

3.3

High Probability Bit Complexity Comparison

Unlike the other two methods, RabitQ analyzes the high-probability behavior of the innerproduct error and derives the corresponding bit-complexity guarantee. As pointed out by Gao et al. (2026), applying Chebyshev’s inequality only to the variance bound for TurboQuantPROD in Proposition B.4 is not sufficient to recover the optimal bit complexity of Alon and Klartag (2017) stated in Lemma J.2. We show, however, that a sharper highprobability guarantee for TurboQuantPROD can be obtained by combining the high-probability guarantee of TurboQuantMSE with that of QJL. In particular, this refined analysis shows that TurboQuantPROD attains the optimal bit complexity in a certain low-accuracy regime. The similar bit-complexity guarantee also holds for EDENUB . Theorem 2 (Bit complexity of EDENUB and TurboQuant PROD (informal)). Let d be the 1 input dimension and let ϵ, δ ∈ (0, 1). Suppose that 1ϵ log δ ≲ d. Then, for both EDENUB and 1 1 TurboQuantPROD , it suffices to use b = Θ log dϵ2 log δ bits per dimension to ensure that the inner-product estimation error is at most ϵ with failure probability at most δ. Discussion on bit complexity. The above theorem shows that EDENUB and TurboQuant PROD achieves the optimal bit complexity of Alon and Klartag (2017) when 1ϵ log 1δ ≲ d. This guarantee is weaker than that of RabitQ in Lemma B.2, since RabitQ achieves the same optimal bit complexity in the high-accuracy regime d ≤ ϵ12 log 1δ , which is the regime considered by Alon and Klartag (2017). This limitation comes from the MSE-oriented construction of EDEN and TurboQuant: although it effectively reduces expected reconstruction error, it does not directly provide sharp high-probability control of the residual distribution. The proof is deferred to Appendix F.

4 Proposed Method Motivated by the comparison in Section 3, we propose a new quantization scheme that improves both DMSE and DIP . Our method follows the spirit of product quantization by grouping multiple coordinates into blocks, and extends the coordinate-wise approaches used in EDEN and TurboQuant to a block-spherical quantization scheme. This allows the quantizer to incorporate the spherical structure of the input vectors more directly, leading to improved distortion guarantees. 4.1

Block-Sphere Quantization (BlockQuant)

The coordinate-wise MSE-optimized centroids used in EDEN and TurboQuant lead to low MSE distortion, but they do not fully exploit the spherical structure of unit input vectors. Since quantization is performed independently across coordinates, many possible combinations of scalar centroids can lie far from the sphere. This suggests that part of the 2bd code space is spent on codewords that are not well aligned with the geometry of the input domain. If the quantizer incorporates the spherical structure more directly, the bit budget can be used more efficiently, potentially leading to improved MSE and inner-product performance. We propose Block-Sphere Quantization (BlockQuant), which addresses this limitation by constructing centroids that capture richer spherical information at the block level (Figure 1). After rotating input vectors, instead of quantizing each coordinate separately, we group the 8

Block-Sphere Vector Quantization

Coordinate-wise MSE-optimized centroids

Projected-grid spherical codewords

Block-spherical MSE-optimized centroids

EDEN, TurboQuant

RabitQ

BlockQunat

<latexit sha1_base64="6ngiWcPxKIg8jkXNxU280tUuBlQ=">AAAC7HicjVHLLgRBFD3a+z1Y2nRMhI1JzyywlEwkNhLCIEGku7pQ0d3VqaomTHyCnZ3Y+gFbvkP8AX/hVmmJR4TqdPepc+85VffeKE+ENkHw3OF1dnX39Pb1DwwODY+MVsbGt7QsFOMtJhOpdqJQ80RkvGWESfhOrniYRgnfjk6aNr59ypUWMts05znfT8OjTBwKFhqiDiozTSlVLLLQ8Lkzobm/urE8J3MjUnHBY5/xzCgpYn1QqQa1wC3/J6iXoIpyrcnKE/YQQ4KhQAqODIZwghCanl3UESAnbh9t4hQh4eIclxggbUFZnDJCYk/oe0S73ZLNaG89tVMzOiWhV5HSxzRpJOUpwvY038UL52zZ37zbztPe7Zz+UemVEmtwTOxfuo/M/+psLQaHWHQ1CKopd4ytjpUuheuKvbn/qSpDDjlxFscUV4SZU3702Xca7Wq3vQ1d/MVlWtbuWZlb4NXekgZc/z7On2CrUavP1+bXG9WlhXLUfZjEFGZpngtYwgrW0CLvK9zjAY9e5l17N97te6rXUWom8GV5d2/tcJ+P</latexit>

<latexit sha1_base64="wCrecMfjY7zudy8uVl9WQxPvbA4=">AAAC53icjVG7TsMwFD2EV3kXGFkiKiQWqpShMCKxMBaJPqSCUOKYYkjjyHZACLGzsSFWfoAV/gTxB/AXXJtU4iEEjpIcn3vPse+9UZYIbYLgZcgbHhkdGy9NTE5Nz8zOlecXWlrmivEmk4lUnSjUPBEpbxphEt7JFA/7UcLb0em2jbfPuNJCpnvmIuMH/bCXiiPBQkPUYXm5oeQJZ4bHaz0lYl9nx1xRNPGZjPm5VLE+LFeCauCW/xPUClBBsRqy/Ix9xJBgyNEHRwpDOEEITU8XNQTIiDvAJXGKkHBxjitMkjanLE4ZIbGn9O3RrluwKe2tp3ZqRqck9CpS+lghjaQ8Rdie5rt47pwt+5v3pfO0d7ugf1R49Yk1OCb2L90g8786W4vBETZdDYJqyhxjq2OFS+66Ym/uf6rKkENGnMUxxRVh5pSDPvtOo13ttrehi7+6TMvaPStyc7zZW9KAa9/H+RO01qu1erW+u17Z2ihGXcISlrFK89zAFnbQQJO8r/GARzx5wrvxbr27j1RvqNAs4svy7t8BAwKdtg==</latexit>

<latexit sha1_base64="YeRAMYY7fM2HhteCXeuy9bEbuL0=">AAAC53icjVHLSsNAFD3Gd31VXboJLYILKYlIdSk+wJVYaFWoUpI4rYN5MZmIUrp3507c+gNu9U/EP9C/8M44BR+ITkhy7rn3nJk7109DnknHeRmwBoeGR0bHxgsTk1PTM8XZuYMsyUXAGkESJuLI9zIW8pg1JJchO0oF8yI/ZIf++ZbKH14wkfEkrsurlJ1EXifmbR54kqhWsXQs2aWUsruzvbPXW7b7YT0XflLLvVj2WsWyU3H0sn8C14AyzNpPis84xikSBMgRgSGGJBzCQ0ZPEy4cpMSdoEucIMR1nqGHAmlzqmJU4RF7Tt8ORU3DxhQrz0yrA9olpFeQ0sYiaRKqE4TVbrbO59pZsb95d7WnOtsV/X3jFRErcUbsX7p+5X91qheJNtZ1D5x6SjWjuguMS65vRZ3c/tSVJIeUOIVPKS8IB1rZv2dbazLdu7pbT+dfdaViVRyY2hxv6pQ0YPf7OH+Cg5WKW61Ua6vljU0z6jEsoIQlmucaNrCLfTTI+xoPeMSTxa0b69a6+yi1BoxmHl+Wdf8OsdueCg==</latexit>

<latexit sha1_base64="XwSlhuuUtyB+rqAOtWU//jo4O1U=">AAAC7HicjVHLLgRBFD3a+z1Y2nRMhI1JjwWWQiQ2EsIgQaS7plCZ6q5OVbUE8Ql2dmLrB2z5DvEH/IVbpSUeEarT3afOvedU3XuTXApjo+i5LWjv6Ozq7unt6x8YHBqujIxuG1VoxhtMSaV3k9hwKTLesMJKvptrHqeJ5DtJa9nFd065NkJlW/Ys5wdpfJyJI8FiS9RhZWpJKtaaMfkJ10TKcG1zZUblVqTinDdDxjOrlWiaw0o1qkV+hT9BvQRVlGtdVZ6wjyYUGAqk4MhgCUvEMPTsoY4IOXEHuCBOExI+znGJPtIWlMUpIya2Rd9j2u2VbEZ752m8mtEpkl5NyhCTpFGUpwm700IfL7yzY3/zvvCe7m5n9E9Kr5RYixNi/9J9ZP5X52qxOMKCr0FQTblnXHWsdCl8V9zNw09VWXLIiXO4SXFNmHnlR59DrzG+dtfb2MdffKZj3Z6VuQVe3S1pwPXv4/wJtmdr9bna3MZsdXG+HHUPxjGBaZrnPBaxinU0yPsK93jAY5AF18FNcPueGrSVmjF8WcHdG6uln3U=</latexit>

<latexit sha1_base64="N0jrKZ94sAdAazyT4tA1iOVp3ag=">AAAC1HicjVHLTsJAFD3UF+KDqks3jcTEFWmNQZdENy7ByCMBQtoy4ITSNu3USJCVcesPuNVvMv6B/oV3xpKoxOg0bc+ce86dufc6ocdjYZqvGW1hcWl5JbuaW1vf2MzrW9v1OEgil9XcwAuipmPHzOM+qwkuPNYMI2aPHI81nOGZjDeuWRTzwL8U45B1RvbA533u2oKorp5vC3YjhJhc2A4X1WlXL5hFUy1jHlgpKCBdlUB/QRs9BHCRYAQGH4KwBxsxPS1YMBES18GEuIgQV3GGKXLkTUjFSGETO6TvgHatlPVpL3PGyu3SKR69ETkN7JMnIF1EWJ5mqHiiMkv2t9wTlVPebUx/J801Ilbgiti/fDPlf32yFoE+TlQNnGoKFSOrc9MsieqKvLnxpSpBGULiJO5RPCLsKuesz4byxKp22Vtbxd+UUrJy76baBO/yljRg6+c450H9sGiViqXqUaF8mo46i13s4YDmeYwyzlFBTc38EU941urarXan3X9KtUzq2cG3pT18AAPylhE=</latexit>

<latexit sha1_base64="SszByuzPGEdJ29ab+t+u5dOsPHA=">AAAC2XicjVHLSsNAFD2Nr1pf8bFzEyyCq5KIVJelbly2YB/QSkmm0xqaJiGZiLV04U7c+gNu9YfEP9C/8M6YglpEJyQ5c+49Z+be64SeGwvTfM1oc/MLi0vZ5dzK6tr6hr65VY+DJGK8xgIviJqOHXPP9XlNuMLjzTDi9tDxeMMZnMp444pHsRv452IU8ouh3ffdnstsQVRH32kLfi2EGJe9gA2qiW+L3KSj582CqZYxC6wU5JGuSqC/oI0uAjAkGILDhyDswUZMTwsWTITEXWBMXETIVXGOCXKkTSiLU4ZN7IC+fdq1UtanvfSMlZrRKR69ESkN7JMmoLyIsDzNUPFEOUv2N++x8pR3G9HfSb2GxApcEvuXbpr5X52sRaCHE1WDSzWFipHVsdQlUV2RNze+VCXIISRO4i7FI8JMKad9NpQmVrXL3toq/qYyJSv3LM1N8C5vSQO2fo5zFtQPC1axUKwe5UvldNRZ7GIPBzTPY5Rwhgpq5H2DRzzhWWtpt9qddv+ZqmVSzTa+Le3hAwEVl/4=</latexit>

Figure 1: Conceptual comparison of codebooks used by rotation-based quantizers for b = 2 in a two-coordinate projection when d > 2. The shaded disk indicates the feasible region of the two displayed coordinates of a rotated unit vector. Left: EDEN and TurboQuant use a Cartesian-product codebook formed by coordinate-wise MSE-optimized scalar centroids. Middle: RabitQ uses spherical codewords obtained by projecting a 2b × 2b uniform grid onto Sd−1 . Right: BlockQuant with block size p = 2 optimizes 2bp = 16 centroids directly for the two-dimensional block distribution.

coordinates of rotated vectors z into blocks. Specifically, for a block size p that divides d, we decompose z = (z1 , . . . , zm ) where m = d/p and zj ∈ Bp for j ∈ [m]. Each block zj is then assigned to a centroid in a p-dimensional codebook. Each block zj is then assigned to a centroid in a p-dimensional codebook. In this way, the quantizer reduces to the coordinatewise schemes when p = 1, while larger block sizes allow the codebook to capture more of the spherical structure of the rotated unit vector. The following lemma characterizes the marginal distribution of each block zj in Bp . Lemma 1 (Block marginal distribution of a uniform spherical vector). Suppose d = mp and x ∼ Unif(Sd−1 ). Divide vector x into blocks x = [z1 , . . . , zm ] where zj ∈ Bp for j ∈ [m]. d−p−2 Γ(d/2) Then, each block zj has density on Bp : fp,d (zj ) = πp/2 Γ((d−p)/2) (1−∥zj ∥22 ) 2 . Equivalently, p−1 zj can decomposed as zj = rj θ j for rj ∈ [0, 1], θ j ∈ S , where rj ⊥ θ j and each component

follows the distributions: rj2 ∼ Beta

p d−p 2, 2

and θ j ∼ Unif(S p−1 ).

The proof of Lemma 1 is provided in Appendix G. Then, we can formulate the block quantization as the following K-means optimization problem: Z (Distortion cost) = min ∥z − oi ∥22 fp,d (z) dz. (1) Bp i∈[2bp ]

Notably, as in TurboQuant, the codebook is constructed only once before quantization and is reused throughout the online quantization procedure. For the dequantization step in Line 11 of Algorithm 1, we use objective-dependent rescaling rules for S, as in EDEN. Let x̄ denote the raw reconstruction before the final rescaling, and let ρ := ⟨x, x̄⟩. This alignment is computed in the rotated domain in Line 6 of Algorithm 1, since ⟨x, x̄⟩ = ⟨x, R⊤ z̄⟩ = ⟨Rx, z̄⟩ = ⟨z, z̄⟩. For BlockQuantBSM , the MSE-optimized variant with best scalar rescaling, we set S = ⟨x, x̄⟩/∥x̄∥22 = ρ/∥x̄∥22 . For BlockQuantUB , the unbiased-reconstruction variant, we set S = 1/ρ. When fast quantization and dequantization are preferred, we also consider the raw-reconstruction variant, denoted 9

Block-Sphere Vector Quantization

Algorithm 1 Block-Sphere Quantization (BlockQuant) Require: dimension d, block size p, bit-width b. // Global Parameters for Setting up BlockQuant. 1: Generate a random rotation matrix R ∈ Rd×d from Haar distribution. 2: Construct codebook by finding centroids o1 , o2 , . . . , o2bp ∈ Bp that minimize Equation 1. 3: procedure Quant(x) 4: 5: 6: 7:

z = (z1 , . . . , zm ) ← Rx, where m = d/p. idxj ← arg mini∈[2bp ] ∥zj − oi ∥ for every j ∈ [m]. Save the alignment ρ = ⟨z, z̄⟩, where z̄ aggregated vector of corresponding codewords. return idx = [idx1 , . . . , idxm ] ∈ {0, 1}b·d . ▷ idx’s are bp-bit integers

8: procedure DeQuant(idx) 9: 10: 11:

12:

z̄ = [z̄1 , . . . , z̄m ] where z̄j ← cidxj for every j ∈ [m]. x̄ ← R⊤ z̄. Set the rescaling parameter  ρ  , for minimizing MSE (i.e., BlockQuantBSM ),   ∥x̄∥22    S = 1, for unbiased reconstruction (i.e., BlockQuantUB ),  ρ      1, for raw reconstruction (i.e., BlockQuantMSE ). e. return S · x

by BlockQuantMSE following the notation of TurboQuantMSE . In this case, we set S = 1, so the value of ρ in Line 6 does not need to be stored. 4.2

Analysis of BlockQuant

The following theorem gives MSE bounds for the proposed algorithm with practical block sizes p = 2 and p = 3, as well as for the idealized case p = d, where the centroids lie on Sd−1 . In this case, fd,d in the cost function (Equation 1) is defined by the probability density function of Unif(Sd−1 ). Theorem 3 (MSE bounds for BlockQuantMSE and BlockQuant BSM ). In high dimension, for Q ∈ {BlockQuantMSE , BlockQuantBSM }, DMSE Q(p=2) ≈ 0.363, 0.108, 0.0297, 0.0078 and DMSE Q(p=3) ≈ 0.357, 0.101, 0.0271, 0.0071, for b = 1, 2, 3, 4, respectively. Moreover, for large b, 1 DMSE Q(p=2) ≤ 2.015 · b (1 + o(1)), 4 1 DMSE Q(p=3) ≤ 1.770 · b (1 + o(1)), 4 bd 1 d−1 DMSE Q(p=d) ≤ Cd · · (1 + o(1)), 4 10

Block-Sphere Vector Quantization

h √ i 2 d−1 2 where Cd := Γ 1 + d−1 2 π Γ((d+1)/2) ≈ 1.055, 1.008, 1.001 for d = 100, 1000, 10000, Γ(d/2) respectively. Discussion of Theorem 3. Since the MSE distortion of EDENBSM and TurboQuantMSE are approximately 0.363, 0.117, 0.0345, 0.0095 for b = 1, 2, 3, 4 (Proposition 1, Remark 1), the MSE guarantee of BlockQuant with block size ≥ 2 is better than, that of TurboQuantMSE (and other two methods) in both small and large bit regime. Moreover, the result for p = d closely matches the lower bound presented in Section 5, not only in order but also in the leading constant. This suggests that increasing the block size in BlockQuant moves the quantizer toward the optimal quantization limit. The proof of Theorem 3 is deferred to Appendix H.1. Combining the ratio-estimator bound in Theorem 1 with the MSE bound in Theorem 3, we obtain the bound on the inner-product error of Algorithm 1. Corollary 3 (Inner product error bound of Algorithm dimension, the BlockQuantUB 1). In high 0.120 0.0306 0.0078 , with block size p satisfies DIP BlockQuantUB(p=2) ≈ 0.571 d−1 d−1 , d−1 , d−1 for p = 2 0.553 0.113 0.0279 0.0071 and b = 1, 2, 3, 4, and DIP BlockQuantUB(p=3) ≈ d−1 , d−1 , d−1 , d−1 , for p = 3 and b = 1, 2, 3, 4, respectively. Moreover, for large b, 2.015 −b DIP BlockQuantUB(p=2) ≤ 4 (1 + o(1)), d−1 1.770 −b DIP BlockQuantUB(p=3) ≤ 4 (1 + o(1)). d−1 Discussion of Corollary 3. Since the MSE distortion of EDENUB is approximately 0.571 0.133 0.0358 0.0096 , , , and for b = 1, 2, 3, 4, respectively (Corollary 1), the expected d−1 d−1 d−1 d−1 inner-product error guarantee for BlockQuantUB with block size ≥ 2 is stronger than the corresponding bounds for other existing rotation-based quantizers. The proof of Corollary 3 is deferred to Appendix H.2.

5 Sharper Lower Bound on Distortion We derive a lower bound for our quantization problem using the Shannon lower bound. A similar quantization lower bound based on Shannon’s argument was considered in Zandieh et al. (2025a); however, the entropy term used there is not directly applicable to a unit vector. (Since Sd−1 has zero Lebesgue measure in Rd , the ambient differential entropy of x is not finite) We correct this by applying the Shannon lower bound to the first d − 1 coordinates of x, whose distribution is absolutely continuous on Bd−1 . Consequently, unlike the previous bd expression, the exponent involves (d−1) rather than b. This correction reflects the fact that, although the ambient dimension is d, the unit sphere Sd−1 has intrinsic dimension d − 1. Theorem 4 (Shannon distortion lower bound). Suppose x ∼ Unif(Sd−1 ). Then, for any b ≥ 0 and any fixed bd-bit quantization map Q, the MSE is lower bounded as Ex [∥x − Q

−1

(Q(x))∥22 ] ≥ cd 11

bd 1 d−1 , 4

Block-Sphere Vector Quantization

d/2 2/(d−1) ψ(1/2)−ψ(d/2) π where cd := d−1 exp ≈ 0.936, 0.991, 0.999 for d = 100, 1000, 2πe Γ(d/2) d−1 10000, respectively. Disscusion on Theorem 4. The resulting theorem can be interpreted as an DMSE lower bound for rotation-based quantizers. Indeed, after a random rotation, the rotated input vector can be viewed as z ∼ Unif(Sd−1 ), and nearest-centroid quantization with a fixed codebook can be regarded as a fixed quantization map on the sphere. Since the distance between two points on sphere is preserved under rotation, the left hand side is equal to DMSE . This lower bound shows the tightness of Theorem 3. Moreover, the comparison suggests that, as the block size p increases, BlockQuant moves closer to the optimal quantization limit. The proof of Theorem4 is provided in Appendix I.

6 Experiments To examine whether the distortion improvements predicted by our theory translate into practical gains, we evaluate BlockQuant on real embedding and LLM inference tasks. Specifically, we consider three settings: quantization accuracy on real embeddings, nearest-neighbor search using quantized inner-product estimates, and KV-cache quantization for long-context LLM inference. Unless stated otherwise, we use block size p = 3. We largely follow the experimental environments and settings of Zandieh et al. (2025b). Practical implementation. Since the exact nearest-centroid assignment for BlockQuant requires comparing each block against all K = 2bp centroids, its cost grows with both the block size and the bit-width. This cost becomes non-negligible even for small blocks; for instance, when p = 3 and b = 4, each block has 212 = 4096 candidate centroids. To keep the experiments practical, we use a simple lookup-table approximation: we partition the block domain into a Cartesian grid, precompute a small set of nearest candidate centroids for each grid cell, and search only within this candidate set at quantization time. This reduces the online assignment cost from a full codebook search to a small candidate search, while leaving the codebook construction, dequantization, and rescaling rules unchanged. Further details are provided in Appendix K.1. 6.1

Quantization Accuracy.

Reconstruction MSE. We first evaluate reconstruction accuracy on DBpedia Entities (Thakur et al., 2021) using 1, 536-dimensional embeddings. We sample 100, 000 database vectors and normalize them to unit norm, matching the setting of our theoretical analysis. For each database vector xi , we measure the squared reconstruction error ei = ∥b xi − xi ∥22 , bi denotes the reconstructed vector. where x Figure 2 shows the distribution of the squared reconstruction error. Both BlockQuantMSE and BlockQuantBSM with block size p = 3 achieve the smallest distortion among the compared methods, supporting the advantage of block-spherical centroids over coordinate-wise codebooks. We also observe no noticeable degradation from the approximate nearest-centroid search, suggesting that the approximation preserves the expected-distortion advantage of BlockQuant in practice. These results further indicate that BlockQuantBSM can serve as an effective reconstruction method in practical settings. 12

Frequency

Block-Sphere Vector Quantization

10000 7500 5000 2500

TurboQuantMSE , bits=1 mean = 2.37e-04 std = 5.65e-06 max = 2.65e-04

Frequency

0.00022

Frequency Frequency Frequency Frequency Frequency

0.00024

0.00023

0.00024

mean = 2.34e-04 std = 5.28e-06 max = 2.56e-04

0.00023

0.00024

0.00025

BlockQuantBSM (p=3), bits=1 mean = 2.34e-04 std = 5.27e-06 max = 2.56e-04

0.00023

0.00024

0.00025

7.5

8.0

6.5

7.0

7.5

8.0

6.5

7.0

7.5

8.0

6.5

7.0

7.5

8.0

mean = 6.58e-05 std = 2.13e-06 max = 7.60e-05

6.5

7.0

7.5

8.0

8.5 1e 5

BlockQuantBSM (p=3), bits=2 mean = 6.57e-05 std = 2.13e-06 max = 7.60e-05

6.0

6.5

7.0

7.5

8.0

8.5 1e 5

2.0

2.2

2.4

2.6

1.8

2.0

2.2

2.4

2.6

1.8

2.0

2.2

2.4

2.6

1.8

2.0

2.2

2.4

2.6

mean = 1.77e-05 std = 6.94e-07 max = 2.23e-05

1.8

2.0

2.2

2.4

2.6

2.8 1e 5

BlockQuantBSM (p=3), bits=3 mean = 1.77e-05 std = 6.93e-07 max = 2.23e-05

1.6

1.8

2.0

2.2

2.4

2.6

2.8 1e 5

9 1e 6

BlockQuantBSM (p=2), bits=4 mean = 5.06e-06 std = 2.78e-07 max = 7.68e-06

9 1e 6

BlockQuantMSE (p=3), bits=4 mean = 4.69e-06 std = 2.01e-07 max = 6.82e-06

4 10000 7500 5000 2500

mean = 5.07e-06 std = 2.78e-07 max = 7.70e-06

4 10000 7500 5000 2500

9 1e 6

BlockQuantMSE (p=2), bits=4 4

2.8 1e 5

BlockQuantMSE (p=3), bits=3

mean = 6.16e-06 std = 4.60e-07 max = 1.01e-05

10000 7500 5000 2500

EDENBSM , bits=4

10000 7500 5000 2500

2.8 1e 5

mean = 7.40e-06 std = 6.76e-07 max = 1.21e-05

10000 7500 5000 2500

RabitQBSM , bits=4

10000 7500 5000 2500

2.8 1e 5

mean = 1.93e-05 std = 8.77e-07 max = 2.51e-05

mean = 6.18e-06 std = 4.72e-07 max = 1.06e-05

2.8 1e 5

BlockQuantBSM (p=2), bits=3

1.6 10000 7500 5000 2500

1.8

TurboQuantMSE , bits=4

10000 7500 5000 2500

2.8 1e 5

mean = 1.93e-05 std = 8.78e-07 max = 2.53e-05

1.6 10000 7500 5000 2500

2.6

BlockQuantMSE (p=2), bits=3 1.6

8.5 1e 5

BlockQuantMSE (p=3), bits=2

2.4

mean = 2.24e-05 std = 1.23e-06 max = 3.04e-05

1.6

10000 7500 5000 2500

2.2

EDENBSM , bits=3

10000 7500 5000 2500

8.5 1e 5

2.0

mean = 2.42e-05 std = 1.47e-06 max = 3.04e-05

1.6

10000 7500 5000 2500

1.8

RabitQBSM , bits=3

10000 7500 5000 2500

8.5 1e 5

mean = 6.99e-05 std = 2.47e-06 max = 8.24e-05

mean = 2.25e-05 std = 1.25e-06 max = 2.98e-05

1.6

8.5 1e 5

BlockQuantBSM (p=2), bits=2

6.0 10000 7500 5000 2500

7.0

mean = 7.00e-05 std = 2.47e-06 max = 8.27e-05

6.0 10000 7500 5000 2500

6.5

TurboQuantMSE , bits=3

10000 7500 5000 2500

8.5 1e 5

BlockQuantMSE (p=2), bits=2 6.0

0.00025

BlockQuantMSE (p=3), bits=1

8.0

mean = 7.63e-05 std = 2.95e-06 max = 9.09e-05

6.0

10000 7500 5000 2500

7.5

EDENBSM , bits=2

10000 7500 5000 2500

0.00025

mean = 2.36e-04 std = 5.63e-06 max = 2.62e-04

0.00022

Frequency

0.00023

7.0

mean = 7.73e-05 std = 3.08e-06 max = 8.96e-05

6.0

10000 7500 5000 2500

6.5

RabitQBSM , bits=2

10000 7500 5000 2500

0.00025

BlockQuantBSM (p=2), bits=1

0.00022

9 1e 6

BlockQuantBSM (p=3), bits=4 mean = 4.68e-06 std = 2.00e-07 max = 6.80e-06

9 1e 6

BlockQuantMSE, approx (p=3), bits=1 10000 BlockQuantMSE, approx (p=3), bits=2 10000 BlockQuantMSE, approx (p=3), bits=3 10000 BlockQuantMSE, approx (p=3), bits=4 mean = 2.34e-04 std = 5.28e-06 max = 2.56e-04

0.00022

Frequency

0.00024

mean = 2.36e-04 std = 5.63e-06 max = 2.62e-04

0.00022

10000 7500 5000 2500

0.00023

mean = 7.64e-05 std = 2.97e-06 max = 9.36e-05

6.0

0.00025

BlockQuantMSE (p=2), bits=1 0.00022

10000 7500 5000 2500

0.00024

mean = 2.36e-04 std = 5.60e-06 max = 2.63e-04

0.00022

10000 7500 5000 2500

0.00023

EDENBSM , bits=1

10000 7500 5000 2500

0.00025

mean = 2.36e-04 std = 5.63e-06 max = 2.64e-04

0.00022

10000 7500 5000 2500

0.00024

RabitQBSM , bits=1

10000 7500 5000 2500

0.00023

TurboQuantMSE , bits=2

10000 7500 5000 2500

0.00023

0.00024

7500 5000 2500

0.00025

mean = 6.58e-05 std = 2.11e-06 max = 7.36e-05

6.0

6.5

7.0

7.5

8.0

7500 5000 2500

8.5 1e 5

mean = 1.77e-05 std = 6.90e-07 max = 2.16e-05

1.6

1.8

2.0

2.2

2.4

2.6

7500 5000 2500

2.8 1e 5

mean = 4.69e-06 std = 2.01e-07 max = 6.82e-06

9 1e 6

BlockQuantBSM, approx (p=3), bits=1 10000 BlockQuantBSM, approx (p=3), bits=2 10000 BlockQuantBSM, approx (p=3), bits=3 10000 BlockQuantBSM, approx (p=3), bits=4 mean = 2.34e-04 std = 5.27e-06 max = 2.56e-04

0.00022

0.00023

0.00024

0.00025

7500 5000 2500

mean = 6.57e-05 std = 2.13e-06 max = 7.60e-05

6.0

6.5

7.0

7.5

8.0

8.5 1e 5

7500 5000 2500

mean = 1.77e-05 std = 6.93e-07 max = 2.23e-05

1.6

1.8

2.0

2.2

2.4

2.6

2.8 1e 5

7500 5000 2500

mean = 4.68e-06 std = 2.00e-07 max = 6.80e-06

9 1e 6

Figure 2: Distribution of MSE.

Inner product error. We next evaluate inner-product estimation accuracy on DBpedia Entities (Thakur et al., 2021) using 1, 536-dimensional embeddings, with 100, 000 database vectors and 1, 000 query vectors. All vectors are normalized, and only the database vectors are quantized. For each pair (xi , yj ), we measure the inner-product estimation error eij = bi is the dequantized output of each algorithm. ⟨b xi , yj ⟩ − ⟨xi , yj ⟩, where x Figure 3 shows that the ratio-based estimators are centered near zero, confirming their empirical unbiasedness. Moreover, BlockQuantUB yields a more concentrated error distribution than the coordinate-wise baselines, especially at moderate bit-widths. This is consistent with Corollary 3, which predicts a smaller expected inner-product distortion for the block-spherical construction. 13

Frequency

Block-Sphere Vector Quantization

6000 4000 2000

TurboQuantPROD , bits=1 mean = -2.06e-03 std = 3.19e-02 max = 1.40e-01

6000 4000 2000

Frequency

0.075 0.050 0.025 0.000 0.025 0.050 0.075 6000 4000 2000

RabitQUB , bits=1 mean = 6.48e-05 std = 1.91e-02 max = 7.76e-02

Frequency Frequency

6000 4000 2000

EDENUB , bits=1 mean = -1.59e-04 std = 1.91e-02 max = 8.06e-02

Frequency Frequency

RabitQUB , bits=2 mean = -1.25e-05 std = 9.20e-03 max = 3.49e-02

EDENUB , bits=2 mean = -2.37e-05 std = 9.25e-03 max = 3.92e-02

TurboQuantPROD , bits=3 mean = -3.70e-04 std = 1.10e-02 max = 4.70e-02

RabitQUB , bits=3 mean = 1.74e-06 std = 4.96e-03 max = 1.88e-02

EDENUB , bits=3 mean = 4.45e-06 std = 4.80e-03 max = 2.19e-02

0.075 0.050 0.025 0.000 0.025 0.050 0.075

BlockQuantUB (p=2), bits=2

BlockQuantUB (p=2), bits=3

6000 4000 2000

BlockQuantUB (p=3), bits=1 mean = -2.31e-04 std = 1.90e-02 max = 7.78e-02

mean = 1.93e-04 std = 8.76e-03 max = 3.94e-02

6000 4000 2000

0.075 0.050 0.025 0.000 0.025 0.050 0.075 6000 4000 2000

BlockQuantUB (p=3), bits=2 mean = 1.46e-04 std = 8.46e-03 max = 3.37e-02

mean = -8.84e-06 std = 4.42e-03 max = 2.03e-02

0.075 0.050 0.025 0.000 0.025 0.050 0.075

BlockQuantUB (p=3), bits=3 mean = 3.63e-05 std = 4.19e-03 max = 1.55e-02

mean = -1.19e-04 std = 5.94e-03 max = 2.45e-02

RabitQUB , bits=4 mean = -9.53e-06 std = 2.72e-03 max = 1.31e-02

0.075 0.050 0.025 0.000 0.025 0.050 0.075 6000 4000 2000

EDENUB , bits=4 mean = 1.99e-05 std = 2.48e-03 max = 1.15e-02

0.075 0.050 0.025 0.000 0.025 0.050 0.075 6000 4000 2000

TurboQuantPROD , bits=4

0.075 0.050 0.025 0.000 0.025 0.050 0.075 6000 4000 2000

BlockQuantUB (p=2), bits=1 mean = -9.85e-05 std = 1.91e-02 max = 8.43e-02

6000 4000 2000

0.075 0.050 0.025 0.000 0.025 0.050 0.075 6000 4000 2000

0.075 0.050 0.025 0.000 0.025 0.050 0.075

0.075 0.050 0.025 0.000 0.025 0.050 0.075 6000 4000 2000

6000 4000 2000

0.075 0.050 0.025 0.000 0.025 0.050 0.075 6000 4000 2000

mean = -9.24e-04 std = 1.93e-02 max = 8.12e-02

0.075 0.050 0.025 0.000 0.025 0.050 0.075 6000 4000 2000

TurboQuantPROD , bits=2

BlockQuantUB (p=2), bits=4 mean = -1.33e-05 std = 2.26e-03 max = 8.51e-03

0.075 0.050 0.025 0.000 0.025 0.050 0.075 6000 4000 2000

0.075 0.050 0.025 0.000 0.025 0.050 0.075

BlockQuantUB (p=3), bits=4 mean = 5.52e-06 std = 2.17e-03 max = 9.06e-03

0.075 0.050 0.025 0.000 0.025 0.050 0.075

BlockQuantUB, approx (p=3), bits=1 6000 BlockQuantUB, approx (p=3), bits=2 6000 BlockQuantUB, approx (p=3), bits=3 6000 BlockQuantUB, approx (p=3), bits=4 mean = -2.31e-04 std = 1.90e-02 max = 7.78e-02

0.075 0.050 0.025 0.000 0.025 0.050 0.075

mean = 1.47e-04 std = 8.46e-03 max = 3.37e-02

4000 2000

0.075 0.050 0.025 0.000 0.025 0.050 0.075

mean = 3.65e-05 std = 4.19e-03 max = 1.55e-02

0.075 0.050 0.025 0.000 0.025 0.050 0.075

4000 2000

mean = 5.04e-06 std = 2.17e-03 max = 9.44e-03

0.075 0.050 0.025 0.000 0.025 0.050 0.075

Figure 3: Distribution of inner product error

6.2

Nearest-Neighbor Search.

We evaluate retrieval quality using Recall@1@k. For each query q, let g(q) denote the exact top-1 neighbor computed using full-precision inner products, and let Ak (q) denote the set of top-k candidates returned by a method using quantized inner-product estimates. We define Recall@1@k =

1 X 1{g(q) ∈ Ak (q)} , |Q| q∈Q

where Q is the query set. Thus, Recall@1@k measures whether quantization preserves the exact nearest neighbor within the top-k retrieved candidates, rather than only measuring average inner-product estimation error. Figure 4 compares the methods on GloVe (d = 200) and OpenAI3/DBpedia (d = 1536 and 3072) under 4-bit compression; the corresponding 2-bit results are provided in Figure 5. Across both datasets, the approximate version of BlockQuantUB achieves strong recall, with the largest gains in the low-k regime. This regime is especially sensitive to quantization error, since small perturbations in inner-product estimates can change the ordering of the top-ranked candidates. These results show that the smaller expected inner-product distortion of BlockQuantUB translates into improved nearest-neighbor retrieval under the same bit budget. In particular, the block-spherical construction improves not only pointwise estimation accuracy but also the ranking quality that is central to approximate nearest-neighbor search. 14

Block-Sphere Vector Quantization

TurboQuantPROD

BlockQuantUB, approx

OpenAI3, d=1536, 4bits

1.00

Recall@1@k

EDENUB

RabitQUB

GloVe, d=200, 4bits

OpenAI3, d=3072, 4bits 1.00

0.95

0.99

0.98

0.90

0.98 0.85

0.96

0.97

0.80

0.94

Top-k

0.96

Top-k

Figure 4: Recall comparison at 4 bits across different datasets. TurboQuantPROD

Recall@1@k

1.0

EDENUB

RabitQUB

GloVe, d=200, 2bits

BlockQuantUB, approx

OpenAI3, d=1536, 2bits

OpenAI3, d=3072, 2bits

1.00

1.000

0.9

0.975

0.95

0.8

0.950

0.7

0.90

0.925

0.6

0.900

0.85

0.5

0.875 1

Top-k

Figure 5: Recall comparison at 2 bits across different datasets. 6.3

KV Cache Quantization.

We further evaluate whether the improved distortion of BlockQuant translates into end-toend LLM performance under KV-cache quantization. We apply each quantizer to the KV cache of Llama-3.1-8B-Instruct while keeping the model weights unchanged. In the attention computation, the query states are kept in full precision and are not quantized. For the key cache, we follow the outlier-aware configuration used in the KV-cache quantization setup. For each attention head with head dimension dh = 128, the 32 key channels with the largest L2 norm are treated as outlier channels and quantized at a higher bit-width, while the remaining 96 channels are quantized at a lower bit-width. In our main 3.5-bit setting, the outlier channels use 4-bit quantization and the non-outlier channels use 3-bit quantization, together with two additional float16 scaling values for the two subvectors. This gives an effective key-cache bit-width of 32×4+96×3+2×16 = 3.5. For the value cache, 128 we quantize the full head dimension uniformly using a 2-bit approximation. All other components, including model weights, MLP layers, embeddings, and output projections, remain unquantized. We use the approximate nearest-centroid search for BlockQuant. We compare against RabitQ, TurboQuant, and EDEN under the same KV-cache bit budget, and report results on the Needle-In-A-Haystack (Kamradt, 2024) benchmark and LongBench-E (Bai et al., 2024). Since the randomness induced by sampled rotation matrices has a particularly noticeable effect on LLM inference, we repeat each experiment over five random seeds and report the mean performance with standard deviations. 15

Block-Sphere Vector Quantization

Full-Precision

RaBitQ

TurboQuant

Score: 0.944 (0.006)

EDEN

Score: 0.933 (0.011)

Score: 0.953 (0.004)

BlockQuant

Score: 0.962 (0.002)

1.00

Score

0.75 0.50 0.25

Token Limit

4k 11 k 18 k 25 k 33 k 40 k 47 k 54 k 61 k 68 k 75 k 83 k 90 k 97 10 k 4k

Token Limit

4k 11 k 18 k 25 k 33 k 40 k 47 k 54 k 61 k 68 k 75 k 83 k 90 k 97 10 k 4k

Token Limit

4k 11 k 18 k 25 k 33 k 40 k 47 k 54 k 61 k 68 k 75 k 83 k 90 k 97 10 k 4k

Token Limit

4k 11 k 18 k 25 k 33 k 40 k 47 k 54 k 61 k 68 k 75 k 83 k 90 k 97 10 k 4k

0.00

4k 11 k 18 k 25 k 33 k 40 k 47 k 54 k 61 k 68 k 75 k 83 k 90 k 97 10 k 4k

Depth Percent

Score: 0.965

0 11 22 33 44 56 67 78 89 100

Token Limit

Figure 6: Evaluation of Llama-3.1-8B-Instruct on the “Needle-In-A-Haystack” benchmark over five random seeds. Results are reported as mean, with standard deviations shown in parentheses.

Table 2: Evaluation of Llama 3.1 8B Instruct on the “LongBench-E” benchmark over five random seeds. Results are reported as mean, with standard deviations shown in parentheses. Method

SingleQA

MultiQA

Summ

Few-shot

Synthetic

Code

Average

RabitQ TurboQuant EDEN BlockQuant

19.12 (0.54) 18.60 (0.39) 19.02 (0.27) 19.55 (0.46)

15.88 (0.26) 15.79 (0.15) 16.30 (0.26) 16.31 (0.15)

29.40 (0.11) 29.11 (0.11) 29.42 (0.17) 29.72 (0.14)

68.23 (0.10) 68.19 (0.10) 68.46 (0.12) 68.49 (0.16)

55.75 (0.35) 55.31 (0.81) 56.29 (0.22) 56.48 (0.57)

60.35 (0.13) 59.72 (0.49) 61.41 (0.21) 61.42 (0.34)

43.52 (0.15) 43.20 (0.20) 43.87 (0.07) 44.03 (0.10)

19.53

16.54

30.28

68.41

56.41

61.60

44.15

Full Cache (16-bit)

Needle-In-A-Haystack. Figure 6 shows the Needle-In-A-Haystack results across different context lengths and needle depths. The full-precision cache obtains a score of 0.965. Among the quantized methods, BlockQuant achieves the highest score, 0.962, with a standard deviation of 0.002, nearly matching the full-precision cache. In comparison, EDEN, RabitQ, and TurboQuant obtain scores of 0.953, 0.944, and 0.933, respectively. This indicates that BlockQuant better preserves the attention-relevant information in the KV cache, especially in long-context settings where small quantization errors can accumulate across many tokens. LongBench-E. Table 2 reports the LongBench-E results.1 BlockQuant achieves the best average score among all quantized methods, with an average of 44.03, compared with 43.87 for EDEN, 43.52 for RabitQ, and 43.20 for TurboQuant. The score is also close to the full-cache result of 44.15, leaving only a small gap of 0.12. Moreover, BlockQuant obtains the best quantized performance in all six task groups, including SingleQA, MultiQA, summarization, few-shot tasks, synthetic tasks, and code. Overall, these results show that the block-spherical construction is effective not only for standalone embedding distortion and nearest-neighbor retrieval, but also for downstream LLM inference. Under the same memory budget, BlockQuant gives the closest performance to the full-precision KV cache and consistently improves over existing rotation-based quantizers.

7 Conclusion In this work, we provide a unified framework for rotation-based quantizers, including EDEN, RabitQ, and TurboQuant, and compare them from three complementary perspectives: reconstruction MSE, expected inner-product distortion, and high-probability bit complexity. 1. The original TurboQuant evaluation (Zandieh et al., 2025b) applies additional prediction post-processing, including truncation to the first generated line or token before scoring. To avoid potential evaluation artifacts caused by this truncation, we instead use the official LongBench-E result.json outputs.

Block-Sphere Vector Quantization

This comparison clarifies that existing methods have different strengths: EDEN is favorable for both expected distortion measures, while RabitQ provides stronger high-probability guarantees. Motivated by this observation, we propose BlockQuant, a block-spherical quantizer that better exploits the geometry of randomly rotated vectors by optimizing centroids at the block level. We prove that BlockQuant improves the distortion constants for both reconstruction MSE and expected inner-product distortion over existing coordinate-wise rotation-based quantizers. Our empirical results support the theoretical findings. On embedding retrieval tasks, BlockQuant achieves lower distortion and improved recall compared with existing baselines. We also evaluated KV-cache quantization for Llama-3.1-8B-Instruct, where BlockQuant improves benchmark accuracy over prior rotation-based quantizers. Overall, these results suggest that BlockQuant provides a promising step toward structure-aware vector quantization.

References Noga Alon and Bo’az Klartag. Optimal compression of approximate inner products and dimension reduction. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 639–650. IEEE, 2017. Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. Longbench: A bilingual, multitask benchmark for long context understanding. In Proceedings of the 62nd annual meeting of the association for computational linguistics (volume 1: Long papers), pages 3119–3137, 2024. Ran Ben-Basat, Yaniv Ben-Itzhak, Gal Mendelson, Michael Mitzenmacher, Amit Portnoy, and Shay Vargaftik. A note on turboquant and the earlier drive/eden line of work. arXiv preprint arXiv:2604.18555, 2026a. Ran Ben-Basat, Yaniv Ben-Itzhak, Gal Mendelson, Michael Mitzenmacher, Amit Portnoy, and Shay Vargaftik. A note on TurboQuant and the earlier DRIVE/EDEN line of work. arXiv preprint arXiv:2604.18555, 2026b. URL https://arxiv.org/abs/2604.18555. Sepehr Eghbali and Ladan Tahvildari. Deep spherical quantization for image search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 11682–11691, 2019. Jianyang Gao and Cheng Long. Rabitq: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 2(3):1–27, 2024. 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. Proceedings of the ACM on Management of Data, 3(3):1–26, 2025. Jianyang Gao, Yutong Gou, Yuexuan Xu, Jifan Shi, Yongyi Yang, Shuolin Li, Raymond Chi-Wing Wong, and Cheng Long. Revisiting rabitq and turboquant: A symmetric comparison of methods, theory, and experiments. arXiv preprint arXiv:2604.19528, 2026. 17

Block-Sphere Vector Quantization

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 (CVPR), pages 2946–2953, 2013. doi: 10.1109/CVPR. 2013.379. Allen Gersho. Asymptotically optimal block quantization. IEEE Transactions on Information Theory, 25(4):373–380, 1979. doi: 10.1109/TIT.1979.1056067. Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1): 117–128, 2011. doi: 10.1109/TPAMI.2010.57. Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE transactions on big data, 7(3):535–547, 2019. Gregory Kamradt. Needle in a haystack-pressure testing llms, 2023. URL https://github. com/gkamradt/LLMTest_NeedleInAHaystack, 2024. Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, and Xia Hu. Kivi: A tuning-free asymmetric 2bit quantization for kv cache. arXiv preprint arXiv:2402.02750, 2024. Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129–137, 1982. doi: 10.1109/TIT.1982.1056489. Joel Max. Quantizing for minimum distortion. IRE Transactions on Information Theory, 6 (1):7–12, 1960. doi: 10.1109/TIT.1960.1057548. Mohammad Norouzi and David J. Fleet. Cartesian k-means. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 3017–3024, 2013. doi: 10.1109/CVPR.2013.388. PF Panter and Wu Dite. Quantization distortion in pulse-count modulation with nonuniform spacing of levels. Proceedings of the IRE, 39(1):44–48, 2006. Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. Beir: A heterogenous benchmark for zero-shot evaluation of information retrieval models. arXiv preprint arXiv:2104.08663, 2021. Tycho F. A. van der Ouderaa, Maximilian L. Croci, Agrin Hilmkil, and James Hensman. Pyramid vector quantization for LLMs. arXiv preprint arXiv:2410.16926, 2024. URL https://arxiv.org/abs/2410.16926. Shay Vargaftik, Ran Ben-Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzenmacher. Drive: One-bit distributed mean estimation. Advances in Neural Information Processing Systems, 34:362–377, 2021. Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben Itzhak, and Michael Mitzenmacher. Eden: Communication-efficient and robust distributed mean estimation for federated learning. In International Conference on Machine Learning, pages 21984–22014. PMLR, 2022. 18

Block-Sphere Vector Quantization

Jianfeng Wang, Jingdong Wang, Jingkuan Song, Xin-Shun Xu, Heng Tao Shen, and Shipeng Li. Optimized cartesian k-means. IEEE Transactions on Knowledge and Data Engineering, 27(1):180–192, 2015. doi: 10.1109/TKDE.2014.2324592. Yongyi Yang, Jianyang Gao, and Wei Hu. Raana: A fast, flexible, and data-efficient post-training quantization algorithm. arXiv preprint arXiv:2504.03717, 2025. Paul L. Zador. Asymptotic quantization error of continuous signals and the quantization dimension. IEEE Transactions on Information Theory, 28(2):139–148, 1982. doi: 10.1109/ TIT.1982.1056490. Amir Zandieh, Majid Daliri, Majid Hadian, and Vahab Mirrokni. Turboquant: Online vector quantization with near-optimal distortion rate. arXiv preprint arXiv:2504.19874, 2025a. Amir Zandieh, Majid Daliri, and Insu Han. Qjl: 1-bit quantized jl transform for kv cache quantization with zero overhead. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 25805–25813, 2025b. Yue Zhao, Yuanjun Xiong, and Philipp Krähenbühl. Image and video tokenization with binary spherical quantization. In International Conference on Learning Representations (ICLR), 2025. URL https://openreview.net/forum?id=yGnsH3gQ6U.

Block-Sphere Vector Quantization

Appendix Table of Contents A Related Work

B Existing Guarantees on EDEN, RabitQ, and TurboQuant

C High-Resolution Formula

D MSE Analysis

D.1 Proof of Proposition 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.2 Proof of Proposition 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

D.3 Approximated MSE of TurboQuant . . . . . . . . . . . . . . . . . . . . . .

E Inner Product Distortion Analysis

E.1 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

E.2 Proof of Corollary 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

E.3 Proof of Corollary 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Bit Complexity Analysis (Proof of Theorem 2)

F.1 Bit Complexity of EDEN . . . . . . . . . . . . . . . . . . . . . . . . . . . .

F.2 Bit Complexity of TurboQuantPROD . . . . . . . . . . . . . . . . . . . . .

G Block Marginal Distribution of a Uniform Spherical Vector (Proof of Lemma 1) 33 H Expected Distortion Analysis of BlockQuant

H.1 Proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

H.2 Proof of Corollary 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Lower Bound Analysis (Proof of Theorem 4)

Auxiliary Lemmas

K Additional Experimental Details and Results

K.1 Approximate nearest-centroid assignment for BlockQuant . . . . . . . . .

K.2 Quantization Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . .

K.3 Computational Resources . . . . . . . . . . . . . . . . . . . . . . . . . . .

Block-Sphere Vector Quantization

A Related Work Classical vector quantization and high-rate theory. Vector quantization has a long history in source coding and signal compression. Classical scalar and vector quantizer design is built on the Lloyd–Max optimality conditions and the Linde–Buzo–Gray algorithm, which iteratively alternates nearest-codeword assignment and centroid updates (Max, 1960; Lloyd, 1982). High-rate quantization theory further characterizes the leading-order distortion of optimal vector quantizers through the Zador–Gersho formula (Gersho, 1979; Zador, 1982). Product and block quantization for nearest-neighbor search. Product quantization (PQ) and its variants are among the most widely used vector quantization methods for approximate nearest-neighbor search. PQ decomposes a high-dimensional vector into low-dimensional subspaces and quantizes each subvector using a separate sub-codebook (Jégou et al., 2011; Ge et al., 2013; Norouzi and Fleet, 2013; Wang et al., 2015). BlockSphere Quantization (BlockQuant) is related to this line of work in that it also quantizes low-dimensional blocks. The key difference is that our codebook is not learned from a dataset. BlockQuant constructs a universal block codebook for this spherical marginal distribution of randomly rotated input vectors in the same framework as EDEN, RabitQ, and TurboQuant. Spherical quantization. Several quantization methods exploit hyperspherical geometry by normalizing vectors and quantizing their directions. For example, deep spherical quantization uses unit-sphere embeddings for supervised image retrieval, while binary spherical quantization applies spherical normalization and binary codes for visual tokenization (Eghbali and Tahvildari, 2019; Zhao et al., 2025). Pyramid vector quantization and related lattice-based methods also use structured codebooks to represent directions on spherical or pyramidal domains, and have recently been revisited for neural and LLM compression (van der Ouderaa et al., 2024). Although these works demonstrate the usefulness of spherical geometry, the role of the sphere is different from ours. Existing spherical quantizers typically quantize a full normalized embedding, feature vector, or model-weight direction, often using a learned or structured spherical codebook. In contrast, BlockQuant does not construct a codebook on the full sphere. After a random rotation of x ∈ Sd−1 , BlockQuant partitions the rotated vector into low-dimensional blocks zj ∈ Bp and quantizes the Euclidean-ball marginal of each block. This marginal distribution is induced exactly by the unit-sphere geometry and is known in closed form. Thus, BlockQuant uses spherical geometry through the exact block marginals of randomly rotated unit vectors, rather than through a global spherical code or a learned hyperspherical embedding. Rotation-based quantizers and theoretical guarantees. Several recent quantizers use randomized rotations to make coordinated istributions more regular. DRIVE and EDEN apply randomized rotations and scalar quantization for distributed mean estimation and federated learning (Vargaftik et al., 2021; 2022). RabitQcombines randomized quantization with a ratio-based estimator and provides high-probability error guarantees for approximate nearest-neighbor search(Gao and Long, 2024; Gao et al., 2025). TurboQuant uses the exact coordinate marginal distribution induced by random rotation to design scalar quantizers for MSE, and then combines a reconstruction quantizer with a QJL residual correction to obtain unbiased inner-product estimation(Zandieh et al., 2025a;b). Recent notes have compared the EDEN/DRIVE, RabitQ, and TurboQuant lines of work, highlighting the need to evaluate 21

Block-Sphere Vector Quantization

these methods under a common set of criteria(Ben-Basat et al., 2026b; Gao et al., 2026). However, existing comparisons remain fragmented: they often focus on empirical performance or algorithmic structure, while the theoretical guarantees are stated under different objectives and are therefore difficult to compare directly. Our work follows this comparison-driven perspective by separating three criteria—reconstruction MSE, expected inner-product distortion, and high-probability bit complexity—and analyzing EDEN, RabitQ,and TurboQuant under a unified framework. The insights from this comparison then motivate BlockQuant, which exploits block-spherical structure to improve expected distortion.

B Existing Guarantees on EDEN, RabitQ, and TurboQuant The following proposition is performance guarantees of EDEN. Proposition B.1 (MSE bound of EDENUB , Theorem 2.3 of Vargaftik et al. (2022)). For all unit input x ∈ Rd , EDENUB satisfies: ! r 1 log d i −1+O DMSE (EDENUB ) ≤ h , d E (Q(z))2 where z ∼ N (0, 1) and Q is Lloyd-max quantizer for standard normal distribution. The following proposition is performance guarantees of RabitQ. Proposition B.2 (Bit complexity of RabitQ, Theorem 3.2 of Gao et al. (2025)). For ϵ, δ > 0, assume that ϵ12 log 1δ > d holds. Then, to ensure that the inner product error of the estimator is bounded by ϵ with the probability of at least 1 − δ, RabitQ requires b = Θ log dϵ12 log 1δ . The following propositions are performance guarantees of TurboQuant. Proposition B.3 (Expected distortion bound of TurboQuantMSE , Theorem 1 of Zandieh et al. (2025a)). The b-bit TurboQuantMSE achieves the following distortion rate: • DMSE (TurboQuantMSE ) ≲

√

3π 1 2 · 4b

• For b = 1, 2, 3, 4, DMSE (TurboQuantMSE ) ≈ 0.36, 0.117, 0.03, 0.009 Proposition B.4 (Expected distortion bound of TurboQuantPROD , Theorem 2 of Zandieh et al. (2025a)). The b-bit TurboQuantPROD achieves the following distortion rate: • DIP (TurboQuantPROD ) ≲

√

3π 2 1 d · 4b

0.56 0.18 0.047 • For b = 1, 2, 3, 4, DIP (TurboQuantPROD ) ≈ 1.57 d , d , d , d .

C High-Resolution Formula In this section we briefly state high-resolution formula of high-rate quantization analysis (Gersho, 1979; Zador, 1982). Let M be an m-dimensional smooth Riemannian manifold with volume measure dVM , and let µ be a probability measure on M with density f with respect to dVM . 22

Block-Sphere Vector Quantization

Definition C.1 (Zador–Gersho constant). R Let T ⊂ M be a bounded measurable subset of M with positive volume, and let x̄T := |T1 | T x dVM (x) be its centroid. Its normalized second moment is Z 1 ∥u − ūT ∥22 dVM (x). G(T ) := m |T |1+2/m T Then, the Zador–Gersho constant G⋆M is defined as the infimum of G(T ) over all tessellating m-dimensional cells: G⋆M := inf{G(T ) : T tiles M by translations}. Definition C.2 (Source factor). The source factor JM is defined as Z JM :=

f (x)

m+2 m

m m+2

dVM (x)

M ∗ Proposition C.1 (General high-rate Zador–Gersho formula). Let DMSE (K) be the optimal K-point quantization distortion for M, i.e. Z ∗ DMSE (K) := inf min ∥x − c∥22 f (x) dVM (x). C⊂Rd , |C|≤K

M c∈C

Then, the leading-order optimal distortion is ∗ (K) = (G∗M + o(1)) JM K −2/m , DMSE

K → ∞.

(C.1)

The Panter–Dite high-resolution formula (Panter and Dite, 2006) used for scalar fixed-rate quantization is the m = 1 specialization of eq. C.1. For a one-dimensional density f and a scalar quantizer with K levels, ∗ DMSE (K) =

1 + o(1) 12

1/3

f (x)

3 dx K −2 ,

K → ∞.

D MSE Analysis D.1

Proof of Proposition 1

Proof for Small b = 1, 2, 3, 4 √ Proof. Let z = Rx, let Rj := d zj , and set K = 2b . Let Qb : R → {q1 , . . . , qK } be the K-level Lloyd–Max scalar quantizer for Z ∼ N (0, 1). Thus there are thresholds −∞ = t0 < t1 < · · · < tK = ∞ such that Qb (r) = qi for r ∈ [ti−1 , ti ), qi = E[Z | Z ∈ [ti−1 , ti )], and ti = (qi + qi+1 )/2. Set z̄ := P d−1/2 (Qb (R1 ), . . . , Qb (Rd )) and x̄ := R⊤P z̄. Since R is orthogonal, d d −1 2 2 −1 2 ρd := ⟨x, x̄⟩ = ⟨z, z̄⟩ = d j=1 Rj Qb (Rj ) and ψd := ∥x̄∥2 = d j=1 Qb (Rj ) . The dequantized output of EDENBSM uses the reconstruction-optimal scalar α⋆ = ρd /ψd2 . Therefore, for each realization of the random rotation, D.1.1

∥x − α⋆ x̄∥22 = min ∥x − αx̄∥22 = 1 − α∈R

ρ2d . ψd2

(D.1)

Block-Sphere Vector Quantization

For fixed b, the empirical averages in ρd and ψd2 are approximated in high dimension by their Gaussian counterparts: ψd2 = E[Qb (Z)2 ] + od (1).

ρd = E[ZQb (Z)] + od (1), By the Lloyd–Max centroid condition,

E[ZQb (Z)] = E[Qb (Z)2 ] =: mb .

E[Z | Qb (Z)] = Qb (Z),

Substituting these approximations into (D.1) gives h i m2 ER ∥x − α⋆ x̄∥22 ≈ 1 − b = 1 − mb . mb Equivalently, if eb := E (Z − Qb (Z))2 , then the centroid condition also gives eb = 1 − mb , and hence the high-dimensional approximate MSE of EDEN pBSM is eb (which is also the approximate MSE of TurboQuantMSE ). For b = 1, Q1 (Z) = 2/π sgn(Z), so m1 = 2/π and e1 = 1 − 2/π ≈ 0.363380. For b = 2, 3, 4, solving the Lloyd–Max equations gives the following scalar distortions. b

K = 2b

mb = E[Qb (Z)2 ]

eb = 1 − m b

1 2 3 4

2 4 8 16

0.6366197724 0.8825181522 0.9654522392 0.9904989920

0.3633802276 0.1174818478 0.0345477608 0.0095010080

Thus, in high dimensions, DMSE (EDENBSM ) ≈ 0.363, 0.117, 0.0345, 0.0095 for b = 1, 2, 3, 4, respectively. D.1.2

Proof for Large Bit-Width

Proof. Since EDENBSM chooses the best scalar multiple of the raw reconstruction x̄, we have, for every realization of the random rotation, bEDENBSM ∥22 = min ∥x − αx̄∥22 ≤ ∥x − x̄∥22 . ∥x − x α∈R

In the high-dimensional approximation, the scaled rotated coordinates are asymptotically standard normal. Therefore, when d → ∞, DMSE (EDENBSM ) ≤ E[(Z − Qb (Z))2 ], where Z ∼ N (0, 1) and Qb is the b-bit Gaussian Lloyd–Max quantizer. By the Panter–Dite high-rate formula (Appendix C), √ π 3 −b 2 DMSE (EDENBSM ) ≤ E[(Z − Qb (Z)) ] ≤ 4 (1 + ob (1)), 2 24

Block-Sphere Vector Quantization

Hence, in high-demensional, EDENBSM and TurboQuantMSE has the same leading constant. We note that if high-rate analysis based on the exact spherical marginal density f1,d (s) = √

Γ(d/2) (1 − s2 )(d−3)/2 , π Γ((d − 1)/2)

−1 ≤ s ≤ 1,

πd Γ(d/2) is applied for EDENBSM , the coefficient of 4−b would be d+3 d+6 12 Γ((d−1)/2) √ converges to π 3/2 as d → ∞.

D.2

Γ((d+3)/6) Γ((d+6)/6)

, which

Proof of Proposition 2

Proof. Let x̄ be the selected RabitQ codeword with ∥x∥2 = 1 and set ρ := ⟨x, x̄⟩. The MSE-best scalar reconstruction along x̄ is x̂ := ρx̄, and since ∥x∥2 = ∥x̄∥2 = 1, ∥x − x̂∥22 = ∥x − ρx̄∥22 = 1 − ρ2 .

(D.2)

Let Gb := {−(2b − 1)/2 + u : u = 0, 1, . . . , 2b − 1}d . The unrotated RabitQ codebook is CRabitQ = {g/∥g∥2 : g ∈ Gb }, and the algorithm selects the codeword closest to z. Therefore the squared angular error is 1 − ρ2 =

min

t>0, g∈Gb

∥z − tg∥22 .

√ For α = t d, this objective becomes ∥z − tg∥22 =

d d X 1X 2 (Rj − αgj )2 . (zj − tgj ) = d j=1

j=1

For fixed α, the minimizing gj is the nearest grid point to Rj /α, namely gj = Qb (Rj /α). Combining this with (D.2) gives   d X 1 DMSE (RabitQBSM ) = E[1 − ρ2 ] = E min (Rj − αQb (Rj /α))2  . (D.3) α>0 d j=1

√ For large d, the rescaled coordinates Rj = d zj are approximately standard normal in the marginal sense, and empirical averages concentrate. Thus, for Z ∼ N (0, 1), the right-hand side of (D.3) is approximated by minα>0 ϕ(α), where ϕ(α) := E[(Z − αQb (Z/α))2 ]. If ζ denotes the standard normal density, symmetry gives 2b−1 X−2 Z (k+1)α

2 1 b−1 ϕ(α) = 2 ζ(r) dr+2 r−α 2 − ζ(r) dr. 2 kα (2b−1 −1)α k=0 (D.4) p For b = 1, Q1 (Z/α) = 12 sgn(Z), so ϕ(α) = 1 − α 2/π + α2 /4 and the minimum is p 1 − 2/π ≈ 0.363380 at α = 2 2/π. For b = 2, 3, 4, numerical minimization of (D.4) gives the following values.

1 r−α k+ 2

Z ∞

Block-Sphere Vector Quantization

minimizing α

minα>0 ϕ(α)

1 2 3 4

1.5957691216 0.9956867007 0.5860194285 0.3352006088

0.3633802276 0.1188460504 0.0374396594 0.0115428844

These are the stated Gaussian-approximation constants. D.3

Approximated MSE of TurboQuant

Let z √ = Rx be the randomly rotated input vector and define the rescaled coordinate Rj := d zj . TurboQuant applies coordinate-wise scalar quantization, where the 2b centroids are chosen to minimize the one-dimensional MSE distortion. In the high-dimensional regime, each Rj is well approximated by Z ∼ N (0, 1). Hence the b-bit scalar codebook can be computed from the Lloyd–Max problem 2 ATQ := arg min E min (Z − a) Z∼N (0,1) b A⊂R |A|=2b

a∈A

which is identical to the original codebook of EDEN (Vargaftik et al., 2022). If qb denotes the nearest-centroid map associated with ATQ b , then the dequantized vector is 1 x̄ ≈ R⊤ √ qb (R1 ), . . . , qb (Rd ) , d and concentration of empirical averages gives DMSE (TurboQuantMSE ) = E∥x − x̄∥22 ≈ EZ∼N (0,1) (Z − qb (Z))2 Solving this scalar Lloyd–Max problem gives DMSE (TurboQuantMSE ) ≈ 0.363380, 0.117482, 0.034548, 0.009501, for b = 1, 2, 3, 4, respectively.

E Inner Product Distortion Analysis E.1

Proof of Theorem 1

Proof. We first record the isotropy supplied by the random rotation. Fix x with ∥x∥2 = 1, and consider any orthogonal matrix U satisfying U x = x, i.e., any rotation in the stabilizer of d x. By Haar invariance, RU ⊤ = R. Moreover, since U ⊤ x = x, the rotated input is unchanged, (RU ⊤ )x = Rx, while the final inverse rotation gives x̄RU ⊤ = U x̄R . Consequently, ρ := ⟨x̄, x⟩ is unchanged, since ⟨U x̄R , x⟩ = ⟨x̄R , U ⊤ x⟩ = ⟨x̄R , x⟩, and ψ := ∥x̄∥2 is also unchanged. On the other hand, the residual component v := x̄ − ρx, which lies in x⊥ , is transformed as v 7→ U v. Thus, after conditioning on the scalar quantities (ρ, ψ), the only remaining randomness in v is its direction inside x⊥ . Since the stabilizer of x acts transitively on directions in x⊥ , the conditional distribution of v is directionally isotropic in x⊥ . 26

Block-Sphere Vector Quantization

Now decompose the reconstruction as x̄ = ρx + v, where v ⊥ x by the definition of ρ = ⟨x̄, x⟩. Since ∥x∥2 = 1, this decomposition gives ∥v∥22 = ∥x̄∥22 − ρ2 = ψ 2 − ρ2 . Let ϕ := ⟨x, y⟩ and assume ρ > 0. For the ratio estimator, we have ϕbratio = ⟨x̄, y⟩/ρ, and hence ϕbratio − ϕ = ⟨x̄, y⟩/ρ − ⟨x, y⟩ = ⟨v, y⟩/ρ. Writing y⊥ := y − ϕx, we have y⊥ ∈ x⊥ and ∥y⊥ ∥22 = 1 − ϕ2 . Moreover, since v ⊥ x, ⟨v, y⟩ = ⟨v, y⊥ ⟩. By the conditional isotropy of v in x⊥ , its conditional mean in every fixed direction of x⊥ is zero, and thus E[⟨v, y⊥ ⟩ | ρ, ψ] = 0. Therefore E[ϕbratio | ρ, ψ] = ϕ, so ϕbratio is unbiased. The same conditional isotropy implies that the squared length ∥v∥22 = ψ 2 − ρ2 is spread uniformly over the d − 1 dimensions of x⊥ , giving E[⟨v, y⊥ ⟩2 | ρ, ψ] = (ψ 2 − ρ2 )∥y⊥ ∥22 /(d − 1). Consequently, h i 1 − ϕ 2 ψ 2 − ρ2 2 b . E E (ϕratio − ϕ) = d−1 ρ2

E.2

Proof of Corollary 1

Proof for Small b = 1, 2, 3, 4 √ Proof. Let z = Rx, Rj := d zj , and let Qb be the 2b -level Lloyd–Max scalar quantizer for Z ∼ N (0, 1). As in the proof of P Proposition 1, set z̄ := d−1/2 (Qb (R1 ), .P . . , Qb (Rd )) and d d ⊤ −1 2 2 −1 2 x̄ := R z̄. Then ρd := ⟨x, x̄⟩ = d j=1 Rj Qb (Rj ) and ψd := ∥x̄∥2 = d j=1 Qb (Rj ) . The EDENUB estimator is ηbratio := ⟨x̄, y⟩/ρd . Applying Theorem 1 with ρ = ρd and ψ = ψd , for η = ⟨x, y⟩ we get E.2.1

E (b ηratio − η)

2 ψd 1 − η2 = E 2 −1 . d−1 ρd

Taking the supremum over y ∈ Sd−1 gives DIP (EDENUB ) ≤ (d − 1)−1 (E[ψd2 /ρ2d ] − 1) (= holds when used in Proposition 1 gives E[ψd2 /ρ2d ] ≤ p η = 0). The concentration argument −1 2 mb + O( log d/d), where mb := E[Qb (Z) ]. Hence 1 DIP (EDENUB ) ≤ d−1

1 −1+O mb

log d d

!! .

For Lloyd–Max centroids, E[Z | Qb (Z)] = Qb (Z), so E[ZQb (Z)] = mb . Thus, with eb := EDEN . From the proof E[(Z − Qb (Z))2 ], we have eb = 1 − mb and m−1 b − 1 = eb /(1 − eb ) =: Bb of Proposition 1, the constants are b

mb = 1 − e b

BbEDEN = eb /(1 − eb )

1 2 3 4

0.3633802276 0.1174818478 0.0345477608 0.0095010080

0.6366197724 0.8825181522 0.9654522392 0.9904989920

0.5707963268 0.1331211687 0.0357840185 0.0095921430

This proves the stated small-bit inner-product bounds for EDENUB . 27

Block-Sphere Vector Quantization

E.2.2

Proof for Large Bit-Width

Proof. Let x̄ be the unscaled coordinate-wise high-rate reconstruction used in the proof of Proposition 1. The EDENUB estimator is ηbEDENUB := ⟨x̄, y⟩/⟨x̄, x⟩. Write e := x̄−x, t := ⟨x, e⟩, and u := e − tx. Then u ⊥ x, x̄ = (1 + t)x + u, ρd := ⟨x̄, x⟩ = 1 + t, and ψd2 − ρ2d = ∥u∥22 . By Theorem 1, after taking the supremum over y ∈ Sd−1 , 2 ψ − ρ2 1 1 ∥u∥22 DIP (EDENUB ) = . E d 2 d = E d−1 d−1 (1 + t)2 ρd Thus the ratio correction removes the radial component from the numerator exactly, so the leading contribution comes only from ∥u∥22 . In the high-rate regime, E∥e∥22 = O(4−b ) and E∥e∥42 = O(4−2b ). Since |t| ≤ ∥e∥2 and ∥u∥2 ≤ ∥e∥2 , Hölder’s inequality gives E∥u∥22 |t| ≤ E∥e∥32 ≤ (E∥e∥42 )3/4 = o(4−b ). Hence the denominator (1 + t)2 only changes the expression by a lower-order term, and therefore E[∥u∥22 /(1 + t)2 ] = E∥u∥22 + o(4−b ). It remains to recall the tangential energy from the high-rate MSE proof. Let f1,d be the one-dimensional marginal density of a coordinate of a uniform vector on Sd−1 , and define R1 R 1 Ld := −1 f1,d (s)1/3 ds and Md := −1 s2 f1,d (s)1/3 ds. The Panter–Dite formula gives the leading coordinate-wise high-rate distortion, and the radial calculation applies the same local error expansion to the component along x. Thus, E[∥e∥22 ] =

d 3 −b L 4 (1 + o(1)), 12 d

E[t2 ] =

d 2 L Md 4−b (1 + o(1)). 12 d

Since e = tx + u with u ⊥ x, the tangential energy is obtained by subtracting the radial d 2 energy: E[∥u∥22 ] = E[∥e∥22 ] − E[t2 ] = 12 Ld (Ld − Md )4−b (1 + o(1)). Also, because f1,d (s)1/3 is proportional to (1 − s2 )(d−3)/6 , R1 2 2 (d−3)/6 ds Md B(3/2, (d + 3)/6) 3 −1 s (1 − s ) = = R1 = . (d−3)/6 2 Ld B(1/2, (d + 3)/6) d + 6 (1 − s ) ds −1

Γ(d/2) d+3 d 3 −b 3 Thus E[∥u∥22 ] = d+6 12 Ld 4 (1 + o(1)). Using Ld = π Γ((d−1)/2)

Γ((d+3)/6) Γ((d+6)/6)

, we obtain

Γ((d + 3)/6) 3 −b 1 d + 3 πd Γ(d/2) DIP (EDENUB ) ≤ 4 (1 + o(1)). d − 1 d + 6 12 Γ((d − 1)/2) Γ((d + 6)/6) a−b implies that the coefficient multiplying 4−b /(d − 1) Finally, Γ(x √ + a)/Γ(x + b) ∼ x converges to π 3/2 ≈ 2.721. This proves the high-rate inner-product bound for EDENUB .

E.3

Proof of Corollary 2

Proof. The factor inside the expectation in Theorem 1 is nonnegative and independent of y, so the worst case over y ∈ Sd−1 is attained when ϕ = 0. For a fixed x, ∥x̄∥22 − ⟨x̄, x⟩2 1 EQ , DIP (RabitQ) = d−1 ⟨x̄, x⟩2 and rotation invariance makes this quantity independent of the particular x ∈ Sd−1 . 28

Block-Sphere Vector Quantization

The codewords of RabitQ are normalized, so ∥x̄∥2 = 1. Let ρ := ⟨x̄, x⟩ and ∆ := 1 − ρ2 . As in the proof of Proposition 2, ∆ = ∥x − ρx̄∥22 is the reconstruction error of RabitQBSM . Hence 1 ∆ DIP (RabitQ) = . (E.1) EQ d−1 1−∆ √ Let z = Rx and Rj := d zj . For Qb (u) := sign(u) min(⌊|u|⌋ + 1/2, 2b−1 − 1/2), the same MSE proof gives d 1X ∆ = min (Rj − αQb (Rj /α))2 . (E.2) α>0 d j=1

We now use the same high-dimensional Gaussian approximation as in the proof of Proposition 2. Let Z ∼ N (0, 1) with density ζ. For fixed b, the Gaussian limit of the empirical objective in (E.2) is ϕ(α) := E (Z − αQb (Z/α))2 2 2 Z ∞ 2b−1 X−2 Z (k+1)α 1 1 b−1 =2 r−α k+ ζ(r) dr + 2 r−α 2 − ζ(r) dr, 2 2 kα (2b−1 −1)α k=0

(E.3)

where the summation term is empty when b = 1. Define ∆z := minα>0 ϕ(α) and κRQ := b ∆z /(1 − ∆z ). By concentration of the empirical averages, for fixed b and d → ∞, ∆ = ∆z + oP (1). Since ∆z < 1 for the bit-widths considered here and the denominator stays bounded away from zero with high probability, EQ [∆/(1 − ∆)] = κRQ b + o(1). Equation (E.1) therefore gives κRQ + o(1) DIP (RabitQ) = b . d−1 The minimization in (E.3), computed in Proposition 2, gives b 1 2 3 4

Optimal value of α 1.595769 0.995687 0.586019 0.335201

∆z 0.363380 0.118846 0.037440 0.011543

= ∆z /(1 − ∆z ) κRQ b 0.570796 0.134875 0.038896 0.011678

Thus, for b = 1, 2, 3, 4, the leading constants are 0.570796/(d − 1), 0.134875/(d − 1), 0.038896/(d − 1), and 0.011678/(d − 1), respectively.

F Bit Complexity Analysis (Proof of Theorem 2) We prove the bit-complexity guarantees for EDENUB and TurboQuantPROD separately in Sections F.1 and F.2. Each subsection contains the corresponding formal statement, namely Theorems F.1 and F.2, the high-probability residual bound, and the proof. 29

Block-Sphere Vector Quantization

F.1

Bit Complexity of EDEN

Theorem F.1 (Bit complexity of EDENUB (formal)). Let x, y ∈ Sd−1 and let 0 < ϵ, δ < 1. There exist universal constants C, c > 0 such that, if log(4/δ) ≤ cd, then for every bit-width b ≥ 1, " !# r log(4/δ) log(4/δ) (b) PQ IPEDEN (x, y) − ⟨x, y⟩ > C 2−b ≤ δ. + d d Consequently, whenever ϵ ≥ C log(4/δ)/d, to ensure h PQ

i (b) IPEDEN (x, y) − ⟨x, y⟩ > ϵ ≤ δ,

it is sufficient to take 1 C log(4/δ) b ≥ max 1, log2 2 dϵ2 bits per dimension. F.1.1

High probability residual bound

Lemma F.1 (High probability residual bound EDEN). Assume that the unscaled b-bit EDEN reconstruction satisfies max EQ ∥x − x̄∥22 ≤ Ced 4−b . x∈Sd−1

Let x, y ∈ Sd−1 be fixed, and let x̄ be the unscaled dequantized codeword produced by the b-bit EDEN quantizer. Then, for every 0 < δ < 1, " # r p log(4/δ) δ PQ ∥x − x̄∥2 > Ced 2−b + Clevy ≤ , (F.1) d 2 where Clevy > 0 is the universal constant from Lévy’s concentration. Proof. Fix b, d and x ∈ Sd−1 . Let R be the random rotation, write z = Rx, and let √ (b) CEDEN be the fixed rotated-coordinate product codebook after the 1/ d scaling. If z̄ ∈ arg mino ∈C (b) ∥z − oi ∥2 and x̄ = R⊤ z̄, then ∥x − x̄∥2 = ∥z − z̄∥2 by orthogonality of R. i

EDEN

(b)

Define f (z) := dist(z, CEDEN ) = mino ∈C (b) i

EDEN

∥z − oi ∥2 , so f (z) = ∥x − x̄∥2 .

The distance-to-a-set map is 1-Lipschitz: for any z, z′ ∈ Sd−1 , f (z) − f (z′ ) ≤ ∥z − oi⋆ (z′ ) ∥2 − ∥z′ − oi⋆ (z′ ) ∥2 ≤ ∥z − z′ ∥2 , and reversing z, z′ gives |f (z) − f (z′ )| ≤ ∥z − z′ ∥2 . Set L = log(4/δ). By Lévy’s concentration inequality, after increasing Clevy if necessary, " PQ

r # L δ f (z) > EQ f (z) + Clevy ≤ . d 2

Moreover, Jensen’s √ inequality and the assumed MSE bound give EQ f (z) ≤ (EQ f (z)2 )1/2 = 2 1/2 (EQ ∥x − x̄∥2 ) ≤ Ced 2−b . Combining the two estimates proves (F.1). 30

Block-Sphere Vector Quantization

F.1.2

Proof of Theorem F.1 (b)

bEDEN = x̄/ρ. Fix b ≥ 1. Let x̄ be the unscaled b-bit EDEN codeword, set ρ = ⟨x, x̄⟩, and define x (b) (b) The EDENUB estimator is IPEDEN (x, y) := ⟨b xEDEN , y⟩ = ⟨x̄, y⟩/ρ. Let η = ⟨x, y⟩, v = x̄ − ρx, and y⊥ = y − ηx. Then v ⊥ x, y⊥ ⊥ x, and (b)

IPEDEN (x, y) − ⟨x, y⟩ =

⟨v, y⟩ ⟨v, y⊥ ⟩ = . ρ ρ

We next record the isotropy supplied by the Haar rotation. Write the EDEN output as x̄R = R⊤ Q0 (Rx), where Q0 is the fixed rotated-coordinate scalar quantize–dequantize d

map. If U x = x, then RU ⊤ = R and x̄RU ⊤ = (RU ⊤ )⊤ Q0 (RU ⊤ x) = U x̄R . Hence ρ and ∥v∥2 are invariant, while v is transformed into U v. Therefore, conditional on ρ and ∥v∥2 , the direction of v is rotationally √ invariant in x⊥ . p Set L = log(4/δ) and αb := Ced 2−b + Clevy L/d. By Lemma F.1, with probability at least 1 − δ/2, ∥x − x̄∥2 ≤ αb . The EDEN MSE bound from the previous section gives a universal constant Ced < 4 for the unscaled reconstruction. Hence, by choosing the universal constant c small enough, L ≤ cd implies αb ≤ α0 for some fixed α0 < 1 and all b ≥ 1. On this residual event, ∥v∥2 ≤ ∥x̄ − x∥2 ≤ αb , and since ∥x̄ − x∥22 = ∥x̄∥22 + 1 − 2ρ with ∥x̄∥22 ≥ 0, we also have ρ ≥ (1 − αb2 )/2 ≥ (1 − α02 )/2 =: cρ > 0. Conditional on ρ and ∥v∥2 , write v = ∥v∥2 θ with θ uniform on the unit sphere in x⊥ . For fixed y⊥ , Lévy’s concentration on this (d − 2)-dimensional sphere gives universal constants Csph , csph > 0 such that, whenever L ≤ csph d, " # r L δ ρ, ∥v∥2 ≤ . PQ |⟨v, y⊥ ⟩| > Csph ∥v∥2 ∥y⊥ ∥2 d 2 Since ∥y⊥ ∥2 ≤ 1, a union bound yields, with probability at least 1 − δ, (b) IPEDEN (x, y) − ⟨x, y⟩

Csph ≤ αb cρ

L ≤C d

r 2−b

L L + d d

! .

This proves the high-probability bound after taking c ≤ csph and replacing L by log(4/δ). It remains to choose b for target accuracy ϵ. If ϵ ≥ C0 L/d with C0 ≥ 2C, then CL/d ≤ ϵ/2. If 1 C1 L b ≥ max 1, log2 , 2 dϵ2 p 2 ) > 1, this follows from then, after increasing C1 if necessary, C2−b L/d ≤ ϵ/2: if C1 L/(dϵ p √ 2 the lower bound on b, while if C1 L/(dϵ ) ≤ 1, it follows from L/d ≤ ϵ/ C1 and 2−b ≤ 1. Thus the error is at most ϵ with probability at least 1 − δ, and enlarging the theorem constant C to dominate C0 , C1 completes the proof. F.2

Bit Complexity of TurboQuantPROD

Theorem F.2 (Bit complexity of TurboQuantPROD (formal)). Let x, y ∈ Sd−1 and let 0 < ϵ, δ < 1. There exist universal constants C, c > 0 such that, if log(4/δ) ≤ cd, then for 31

Block-Sphere Vector Quantization

every bit-width b ≥ 1, " PQ

(b)

IPTQ (x, y) − ⟨x, y⟩ > C

2−(b−1)

log(4/δ) log(4/δ) + d d

!# ≤ δ.

Consequently, whenever ϵ ≥ C log(4/δ)/d, to ensure h PQ

i (b) IPTQ (x, y) − ⟨x, y⟩ > ϵ ≤ δ,

it is sufficient to take 1 C log(4/δ) b ≥ 1 + max 0, log2 2 dϵ2 bits per dimension. F.2.1

High probability residual bound

We first introduce a high-probability bound on the residual norm of TurboQuantMSE , obtained by applying Lévy’s concentration inequality. Lemma F.2 (High probability residual bound TurboQuantMSE ). Assume that the b-bit TurboQuantMSE reconstruction satisfies max EQ ∥x − x̄∥22 ≤ Cmse 4−b .

x∈Sd−1

Let x ∈ Sd−1 be fixed, and let x̄ be the corresponding dequantized codeword. Then, for every 0 < δ < 1, # " r p log(2/δ) PQ ∥x − x̄∥2 > Cmse 2−b + Clevy ≤ δ, (F.2) d where Clevy > 0 is a universal constant from Lévy’s concentration. (b)

Proof. Fix b, d and x ∈ Sd−1 . Let R be the random rotation, write z = Rx, and let CTQ be the fixed rotated-coordinate TurboQuantMSE codebook. If z̄ ∈ arg mino ∈C (b) ∥z − oi ∥2 and i

(b) x̄ = R⊤ z̄, then ∥x − x̄∥2 = ∥z − z̄∥2 . Define f (z) := dist(z, CTQ ) = mino ∈C (b) ∥z − oi ∥2 , so i

f (z) = ∥x − x̄∥2 . As above, f is 1-Lipschitz because f (z)−f (z′ ) ≤ ∥z−oi⋆ (z′ ) ∥2 −∥z′ −oi⋆ (z′ ) ∥2 ≤ ∥z−z′ ∥2 , and the reverse inequality follows by swapping z, z′ . Hence Lévy’s concentration gives p PQ [f (z) > EQ f (z) + t] ≤ 2 exp(−cdt2 ) for a universal c > 0. Taking t = Clevy log(2/δ)/d makes this probability at most δ. Jensen’s inequality √ and−bthe assumed MSE guarantee give 2 1/2 2 1/2 EQ f (z) ≤ (EQ f (z) ) = (EQ ∥x − x̄∥2 ) ≤ Cmse 2 . Combining the two estimates proves (F.2). 32

Block-Sphere Vector Quantization

F.2.2

Proof of Theorem F.2

Fix a total bit-width b ≥ 1. Let x̄ be the reconstruction produced by the (b − 1)-bit (b) TurboQuantMSE stage and set r = x − x̄. The TurboQuantPROD estimator is IPTQ (x, y) := ⟨y, x̄⟩ + IPQJL (y, r). Since ⟨y, x⟩ = ⟨y, x̄⟩ + ⟨y, r⟩, (b)

IPTQ (x, y) − ⟨x, y⟩ = IPQJL (y, r) − ⟨y, r⟩. Set L = log(4/δ). Applying Lemma F.2 to the (b − 1)-bit residual with failure probability δ/2 gives, with probability at least 1 − δ/2, r p ∥r∥2 ≤ Cmse 2−(b−1) + Clevy

L . d

Conditional on this residual, Lemma J.4 with η = δ/2 gives, since ∥y∥2 = 1 and L ≤ cqjl d, that with conditional probability at least 1 − δ/2, r |IPQJL (y, r) − ⟨y, r⟩| ≤ Cqjl ∥r∥2

L . d

A union bound gives both events with probability at least 1 − δ, and on their intersection ! r L L (b) IPTQ (x, y) − ⟨x, y⟩ ≤ C 2−(b−1) + , d d for a universal constant C > 0. This proves the first claim after replacing L by log(4/δ) and taking c ≤ cqjl . For the bit-width claim, if ϵ ≥ C0 L/d and C0 ≥ 2C, then CL/d ≤ ϵ/2. If 1 C1 L b ≥ 1 + max 0, , log2 2 dϵ2 then 2−(b−1) ≤ (C1 L/(dϵ2 ))−1/2 whenpC1 L/(dϵ2 ) > is trivial √ 1, while the same inequality 2 −(b−1) 2 when C1 L/(dϵ ) ≤ 1. Hence C2 L/d ≤ Cϵ/ C1 ≤ ϵ/2 for C1 ≥ 4C . Combining the two terms gives the desired probability bound, and enlarging the theorem constant C to dominate C0 , C1 completes the proof.

G Block Marginal Distribution of a Uniform Spherical Vector (Proof of Lemma 1) Proof. By symmetry, it suffices to prove the claim for the first block z1 . Let g = (g1 , . . . , gm ) ∼ N (0, Id ), where gj ∈ Rp are independent standard Gaussian blocks. The standard Gaussian d

g representation of the uniform distribution on the sphere gives x = ∥g∥ , and hence, 2

g1 d z1 = q . P 2 ∥g1 ∥22 + m ∥g ∥ k 2 k=2 33

Block-Sphere Vector Quantization

P 2 2 2 Define U = ∥g1 ∥22 and V = m k=2 ∥gk ∥2 . Then U ∼ χp and V ∼ χd−p , and U and V are independent. Moreover, the Gaussian direction θ 1 q := g1 /∥g1 ∥2 is uniform on Sp−1 and is d

U independent of U and V . Therefore, we have z1 = U +V θ 1 . It follows from the standard beta–chi-square relationship that U p d−p 2 , r1 := ∼ Beta , U +V 2 2

and r1 is independent of θ 1 . This proves the polar decomposition. It remains to derive the density with respect to Lebesgue measure on Bp . Let a = p/2 and b = (d − p)/2. Since r12 ∼ Beta(a, b), the density of r1 on [0, 1] is fr1 (r) =

d−p−2 2 rp−1 (1 − r2 ) 2 , B(a, b)

0 ≤ r ≤ 1.

Since θ 1 is uniform on Sp−1 and independent of r1 , the density fp,d of z1 = r1 θ 1 must be radial. Using the polar-coordinate identity dz = rp−1 dr dσ(θ), where dσ denotes surface-area measure on Sp−1 , we get fp,d (rθ) =

d−p−2 2 fr1 (r) = (1 − r2 ) 2 . p−1 p−1 p−1 |S |r B(a, b)|S |

Finally, using B(a, b) = Γ(a)Γ(b)/Γ(a + b) and |Sp−1 | = 2π p/2 /Γ(p/2), we obtain fp,d (z1 ) =

d−p−2 Γ(d/2) 2 2 1 − ∥z ∥ , 1 2 π p/2 Γ((d − p)/2)

z1 ∈ Bp .

H Expected Distortion Analysis of BlockQuant H.1

Proof of Theorem 3

H.1.1

Proof for Small b = 1, 2, 3, 4 (p)

Proof. Let p be the block size and let CBQ be the codebook minimizing the distortion cost in Equation 1. For d-dimensional b-bit compression, Z d DMSE (BlockQuant) = min ∥u − o∥22 fp,d (u) du . p Bp o∈C (p) BQ

Define Rj = Rj is hp,d (r) =

√

d zj and ai =

1 dp/2

fp,d

r √ d

√

d oi . Then ∥zj − oi ∥22 = d−1 ∥Rj − ai ∥22 , and the density of

Γ(d/2) = p/2 p/2 d π Γ((d − p)/2)

(d−p−2)/2 √ ∥r∥22 1− 1{∥r∥2 ≤ d} . d

After this rescaling, DMSE (BlockQuant) =

1 inf p A⊂√dBp , |A|≤2bp 34

Z √

min ∥r − a∥22 hp,d (r) dr.

dBp a∈A

Block-Sphere Vector Quantization

For fixed p, hp,d converges pointwise to the standard p-dimensional Gaussian density ζp (r) = (2π)−p/2 exp(−∥r∥22 /2). Hence the finite-rate MSE is approximated by DMSE (BlockQuant) = p−1 ϕ⋆p + od (1), where Z ϕ⋆p := inf min ∥r − a∥22 ζp (r) dr . A⊂Rp , |A|≤2bp

Rp a∈A

For a candidate rescaled codebook A = {a1 , . . . , a2bp }, let Vi (A) := {r : ∥r − ai ∥2 ≤ ∥r − ai′ ∥2 for all i′ }. Then the Gaussian objective is bp

ϕp (A) =

2 Z X

∥r − ai ∥22 ζp (r) dr .

Vi (A)

i=1

R If the cells are fixed, minimizing the i-th term gives 0 = 2 Vi (ai − r)ζp (r) dr, so each centroid R R must be the Gaussian conditional mean of its own Voronoi cell, i.e., ai = Vi rζp (r) dr/ Vi ζp (r) dr. Applying Lloyd optimization for N (0, Ip ) gives the following near-minimum values of ϕp . p

ϕp

ϕp /p

2 2 2 2

1 2 3 4

0.726760 0.214970 0.059433 0.015516

0.363380 0.107485 0.029716 0.007758

3 3 3 3

1 2 3 4

1.068772 0.303994 0.081462 0.021173

0.356257 0.101331 0.027154 0.007058

We next show that the same Gaussian-approximation value applies to BlockQuantBSM . Let QA (r) be the nearest-centroid map for the Gaussian codebook and define Z Z 1 1 Ap := ⟨r, QA (r)⟩ζp (r) dr, Mp := ∥QA (r)∥22 ζp (r) dr . p Rp p Rp The centroid condition implies Ap = Mp , since on each Voronoi cell Vi , Z Z Z ⟨r, ai ⟩ζp (r) dr = rζp (r) dr, ai = ∥ai ∥22 ζp (r) dr Vi

For the raw reconstruction x̄, the high-dimensional Gaussian approximation and the law of large numbers give ⟨x, x̄⟩ ≈ Ap and ∥x̄∥22 ≈ Mp . On the other hand, we have that Z ϕp 1 = ∥r − QA (r)∥22 ζp (r) dr = 1 − 2Ap + Mp = 1 − Mp . p p Therefore the best-scalar reconstruction satisfies DMSE (BlockQuantBSM ) ≈ 1 − 35

A2p ϕp = 1 − Mp = . Mp p

Block-Sphere Vector Quantization

Thus, BlockQuantMSE and BlockQuantBSM have the same finite-rate Gaussian-approximation value. Specifically, for Q ∈ {BlockQuantMSE , BlockQuantBSM } and b = 1, 2, 3, 4, DMSE (Q(p=2) ) ≈ 0.363380, 0.107485, 0.029716, 0.007758 DMSE (Q(p=3) ) ≈ 0.356257, 0.101331, 0.027154, 0.007058.

H.1.2

Proof for Large Bit-Width with p ̸= d

Let x̄ be the raw reconstruction used by BlockQuantMSE . BlockQuantBSM returns

Then, best-scalar variant

x,x̄ x̄, and for every rotation matrix R, we have ∥x̄∥22

x, x̄ x̄ x− ∥x̄∥22

= min ∥x − αx̄∥22 ≤ ∥x − x̄∥22 . 2

α∈R

That means, for every block size p, it holds that DMSE (BlockQuantBSM(p) ) ≤ DMSE (BlockQuantMSE(p) ), so any high-rate upper bound for BlockQuantMSE also applies to BlockQuantBSM . Thus, in this section (Section H.1.2) and the next section (Section H.1.3), we focus on bounding MSE of BlockQuantMSE . For a large number of centroids, we use the high-rate Zador–Gersho formula to derive the MSE bound of BlockQuantMSE . The following corollary is a restatement of Proposition C.1 in our setting. Corollary H.1 (MSE bound of Algorithm 1 for many centroids). Let d, m, and p be integers with d = mp. If Algorithm 1 is run with b-bit compression and m blocks, then for any x = [x1 , . . . , xm ] ∈ Sd−1 , DMSE (BlockQuant) ≲ d G⋆p Jp,d 4−b , where G⋆p := G⋆Bp and Jp,d :=

p/(p+2) dz Bp fp,d (z)

(p+2)/p

We now prove the large-bit bound for p ̸= d. Γ(d/2) Proof. Recall that each block zj has density fp,d (z) = πp/2 Γ((d−p)/2) (1 − ∥z∥22 )(d−p−2)/2 on p B . Set βp,d := p(d − p − 2)/(2(p + 2)). Then

p/(p+2)

fp,d (z) Bp

dz =

Γ(d/2) p/2 π Γ((d − p)/2)

p/(p+2) Z

(1 − ∥z∥2 )βp,d dz.

Using polar coordinates and the change of variables u = r2 , Z Z 1 Γ(βp,d + 1) π p/2 2 βp,d (1 − ∥z∥ ) dz = up/2−1 (1 − u)βp,d du = π p/2 . Γ(p/2) Γ(β p,d + 1 + p/2) Bp 0 36

Block-Sphere Vector Quantization

Substitution gives Γ(d/2) Jp,d = π Γ((d − p)/2)

Γ(βp,d + 1) Γ(βp,d + 1 + p/2)

(p+2)/p .

√ Case p = 2. Since G⋆2 = 5/(36 3) and J2,d = 8π(d − 2)/d2 , 10π DMSE (BlockQuantBSM (p = 2)) ≤ DMSE (BlockQuantMSE (p = 2)) ≤ √ 9 3

1−

2 d

4−b ≈ 2.015·4−b .

Γ(d/2) Case p = 3. Since G⋆3 ≤ G(A⋆3 ) = 19/(192 21/3 ) ≈ 0.0785432812 and J3,d = π Γ((d−3)/2)

Γ((3d−5)/10) Γ((3d+10)/10)

DMSE (BlockQuantBSM (p = 3)) ≤ DMSE (BlockQuantMSE (p = 3)) Γ((3d − 5)/10) 5/3 −b Γ(d/2) 4 ≤ 0.0785432812 πd Γ((d − 3)/2) Γ((3d + 10)/10) ≈ 1.770 · 4−b .

√ ⋆ Remark H.1. When p = 1 (TurboQuantMSE ), since 1/12 and J1,d ≈ 6 3π/d, the √ G1 = −b MSE distortion satisfies DMSE (TurboQuantMSE ) ≤ ( 3π/2)4 ≈ 2.721 · 4−b . H.1.3

Proof for p = d

Proof. When p = d, Algorithm 1 uses a single block. The block source is therefore not the full-dimensional density fp,d on Bp used above; for any fixed x ∈ Sd−1 , the rotated vector z := Rx is uniform on Sd−1 , so the intrinsic source dimension is n = d − 1. Let Ad−1 := Hd−1 (Sd−1 ) = 2π d/2 /Γ(d/2). With respect to surface measure dσ, the density of z is f (z) = A−1 d−1 . In the p = d case, = 2bd . For C ⊂ Rd with |C| ≤ K, R the total number2 of codewords is K ⋆ (K) := inf define Dsph (C) := Sd−1 mino∈C ∥z − o∥2 f (z) dσ(z) and Dsph |C|≤K Dsph (C). This is the single-block analogue of the objective above. Formally, the intrinsic n-dimensional Zador–Gersho formula gives ⋆ Dsph (K) ≤ nG⋆n

n/(n+2)

f (z)

(n+2)/n dσ(z) K −2/n (1 + o(1)).

Sd−1

Here curvature contributes only lower-order error, because on a cell of diameter r, squared R Euclidean and tangent-plane distances differ by O(r4 ). Since f is constant, Sd−1 f (z)n/(n+2) dσ(z) = 2/(n+2)

Ad−1

, so

⋆ Dsph (K) ≤ (d − 1)G⋆d−1

2π d/2 Γ(d/2)

!2/(d−1) K −2/(d−1) (1 + o(1)).

Since G⋆d−1 is not available in closed form, we use an explicit random-coding comparison. 37

i5/3

Block-Sphere Vector Quantization

Let Vn := π n/2 /Γ(1 + n/2) be the unit-ball volume in Rn , and draw Crand = {o1 , . . . , oK } i.i.d.

with oi ∼ Unif(Sd−1 ). Fix z ∈ Sd−1 and set Ti := ∥z − oi ∥22 , T(1) := mini Ti . For small t, the cap {o : ∥z − o∥22 ≤ t} has surface area Vn tn/2 (1 + o(1)), hence P(Ti ≤ t) = (Vn /Ad−1 )tn/2 (1 + o(1)). With t = K −2/n s, K Vn n/2 −2/n −2/n . s P(T(1) > K s) = 1 − P(Ti ≤ K s) → exp − Ad−1 R∞ Using ET(1) = 0 P(T(1) > t) dt and the change of variables u = (Vn /Ad−1 )sn/2 yields 2 Ad−1 2/n −2/n ECrand T(1) = Γ 1 + K (1 + o(1)). n Vn The ideal codebook cannot be worse than the random comparison. Substituting n = d − 1 and Vd−1 = π (d−1)/2 /Γ((d + 1)/2) gives √ Γ((d + 1)/2) 2/(d−1) 2 ⋆ −2/(d−1) Dsph (K) ≤ Cd K (1 + o(1)), Cd := Γ 1 + 2 π . d−1 Γ(d/2) Under the b-bit-per-coordinate convention, K = 2bd and K −2/(d−1) = (1/4)bd/(d−1) . It remains to translate the spherical source bound back to randomized MSE. For fixed x ∈ Sd−1 , let QC (z) := arg mino∈C ∥z − o∥22 and x̄ := R⊤ QC (Rx). Since rotations preserve distance and Rx ∼ Unif(Sd−1 ), Z ER ∥x − x̄∥22 = min ∥z − o∥22 f (z) dσ(z). Sd−1 o∈C

The right-hand side is independent of x. Choosing ideal spherical centroids gives bd/(d−1) 1 DMSE (BlockQuantBSM(p=d) ) = max ER ∥x − x̄∥22 ≤ Cd (1 + o(1)). 4 x∈Sd−1 Since BlockQuantBSM is the best scalar multiple of the same raw reconstruction x̄, bd/(d−1) 1 DMSE (BlockQuantBSM(p=d) ) ≤ DMSE (BlockQuantMSE(p=d) ) ≤ Cd (1 + o(1)). 4 The values C100 ≈ 1.055, C1000 ≈ 1.008, and C10000 ≈ 1.001 follow by evaluating the log-gamma expression, and Cd → 1 by the gamma-ratio asymptotic. H.2

Proof of Corollary 3

H.2.1

Proof for Small b = 1, 2, 3, 4

Proof. Let x̄p,b be the unscaled reconstruction produced by b-bit BlockQuantBSM(p) , and set ρp,b := ⟨x̄p,b , x⟩ and ψp,b := ∥x̄p,b ∥2 . The corresponding ratio estimator is ηbratio := ⟨x̄p,b , y⟩/⟨x̄p,b , x⟩. Since BlockQuantBSM(p) is obtained by a Haar random rotation, a fixed block quantizer, and the inverse rotation, Theorem 1 applies. Thus, with η = ⟨x, y⟩, " # 2 − ρ2 ψp,b 1 − η2 p,b 2 E[(b ηratio − η) ] = E . d−1 ρ2p,b 38

Block-Sphere Vector Quantization

2 − Taking the supremum over y ∈ Sd−1 gives DIP (BlockQuantUB(p) ) = (d − 1)−1 E[(ψp,b ρ2p,b )/ρ2p,b ]. It remains to evaluate the deterministic equivalent of the nonlinear factor. As in the √ small-bit proof of Theorem 3, write Rj = d zj and approximate its law by N (0, Ip ). Let Qp,b be the nearest-neighbor Gaussian block quantizer with 2bp centroids and define δp,b := p−1 E∥R − Qp,b (R)∥22 , where R ∼ N (0, Ip ). The centroid condition gives E[R | Qp,b (R)] = Qp,b (R), hence E⟨R, Qp,b (R)⟩ = E∥Qp,b (R)∥22 . If mp,b := p−1 E∥Qp,b (R)∥22 , then δp,b = 1 − mp,b . After rescaling back to the unit sphere, the empirical block averages satisfy ρp,b = 2 =m mp,b + od (1) and ψp,b p,b + od (1) under the high-dimensional Gaussian approximation. Therefore " # 2 − ρ2 ψp,b mp,b − m2p,b δp,b p,b E ≈ = . 2 2 1 − δp,b ρp,b mp,b

Substituting the small-bit MSE constants from Theorem 3 gives the following leading inner-product constants. p

δp,b

δp,b /(1 − δp,b )

2 2 2 2

1 2 3 4

0.363380 0.107485 0.029716 0.007758

0.570796 0.120429 0.030626 0.007819

3 3 3 3

1 2 3 4

0.356257 0.101331 0.027154 0.007058

0.553415 0.112757 0.027912 0.007108

p,b 1 Since DIP (BlockQuantUB(p) ) ≈ d−1 1−δp,b , dividing these coefficients by d − 1 proves the claimed constants for b = 1, 2, 3, 4.

H.2.2

Proof for Large Bit-Width

Proof. Let x̄p,b be the unscaled high-rate BlockQuantBSM(p) reconstruction of x, and set ρp,b := ⟨x̄p,b , x⟩ and ψp,b := ∥x̄p,b ∥2 . Write ep,b := x̄p,b − x, tp,b := ⟨x, ep,b ⟩, and up,b := 2 − ρ2 = ∥u ∥2 . ep,b − tp,b x. Then up,b ⊥ x, x̄p,b = (1 + tp,b )x + up,b , ρp,b = 1 + tp,b , and ψp,b p,b 2 p,b By Theorem 1, taking the worst case over y ∈ Sd−1 gives " # 2 − ρ2 ψp,b ∥up,b ∥22 1 1 p,b E = E . DIP (BlockQuantUB(p) ) = d−1 d−1 (1 + tp,b )2 ρ2p,b Thus only the tangential error enters the numerator, while the random denominator remains inside the expectation. Under the same high-rate regularity used in Corollary H.1, E[∥ep,b ∥22 ] = O(4−b ) and E[∥ep,b ∥42 ] = O(4−2b ). Since |tp,b | ≤ ∥ep,b ∥2 and ∥up,b ∥2 ≤ ∥ep,b ∥2 , the denominator does not 39

Block-Sphere Vector Quantization

change the leading order: ∥up,b ∥22 − E[∥up,b ∥22 ] ≤ C · E[∥up,b ∥22 |tp,b |] + o(4−b ) ≤ C · E∥ep,b ∥32 + o(4−b ) = o(4−b ), E (1 + tp,b )2 where E[∥ep,b ∥32 ] ≤ (E[∥ep,b ∥42 ])3/4 = O(2−3b ). Hence ∥up,b ∥22 = E[∥up,b ∥22 ] + o(4−b ) ≤ E[∥ep,b ∥22 ] + o(4−b ). E (1 + tp,b )2 This uses only the total high-rate MSE constant. By Theorem 3, equivalently Corollary H.1, E∥ep,b ∥22 ≤ dG⋆p Jp,d 4−b (1 + o(1)). Therefore DIP (BlockQuantUB(p) ) ≤

dG⋆p Jp,d −b · 4 (1 + o(1)). d−1

√ (1 − 2/d), so For p = 2, dG⋆2 J2,d = 910π 3

1 10π √ DIP (BlockQuantUB(p=2) ) ≤ d−19 3

2 1− d

4−b (1 + o(1)) ≤

2.015 −b 4 (1 + o(1)). d−1

For p = 3, dG⋆3 J3,d ≤ 0.0785432812 πd

Γ((3d − 5)/10) 5/3 Γ(d/2) , Γ((d − 3)/2) Γ((3d + 10)/10)

which gives 0.0785432812 πd Γ(d/2) Γ((3d − 5)/10) 5/3 −b DIP (BlockQuantUB(p=3) ) ≤ 4 (1 + o(1)) d−1 Γ((d − 3)/2) Γ((3d + 10)/10) 1.770 −b 4 (1 + o(1)). ≈ d−1 This proves the high-rate bounds in the corollary.

I Lower Bound Analysis (Proof of Theorem 4) Proof. Write x = (u, Xd ), where u ∈ Rd−1 denotes the first d − 1 coordinates of x. Also write b = Q−1 (Q(x)) and let u b be the first d − 1 coordinates of x b. Since coordinate projection x b∥22 ≥ ∥u − u b ∥22 . Moreover, u b is determined by the cannot increase Euclidean distance, ∥x − x b ) ≤ H(Q(x)) ≤ bd bits. Hence bd-bit message Q(x), so by data processing I(u; u Ex [∥x − Q−1 (Q(x))∥22 ] ≥ Du (bd),

Du (B) :=

inf

I(u;e u)≤B

e ∥22 , E∥u − u

where mutual information is measured in bits. It remains to lower bound the distortion-rate function of the projected spherical source u. We first record the law of u. The sphere p is the union, up to the equator of surface measure zero, of the two graphs u 7→ (u, ± 1 − ∥u∥22 ) over the open unit ball in Rd−1 . The 40

Block-Sphere Vector Quantization

surface element of either graph is (1 − ∥u∥22 )−1/2 du. Dividing the contribution of the two sheets by |Sd−1 | = 2π d/2 /Γ(d/2) gives the density fu (u) =

Γ(d/2) (1 − ∥u∥22 )−1/2 1{∥u∥2 < 1}. π d/2

Therefore, with he denoting differential entropy in nats, ! π d/2 1 he (u) = log + E log(1 − ∥u∥22 ). Γ(d/2) 2 The radial variable satisfies ∥u∥22 ∼ Beta((d − 1)/2, 1/2), and the beta identity E log(1 − U ) = ψ(β) − ψ(α + β) for U ∼ Beta(α, β) gives ! π d/2 1 he (u) = log + {ψ(1/2) − ψ(d/2)}. Γ(d/2) 2 e satisfying I(u; u e ) ≤ B, let D = E∥u − u e ∥22 Now set n = d − 1. For any reconstruction u e . Since conditioning cannot increase differential entropy and translation does and e = u − u e ) = h2 (u) − h2 (u | u e ) ≥ h2 (u) − h2 (e), where h2 = he / log 2. Among all not change it, I(u; u n-dimensional errors with second moment at most D, the isotropic Gaussian has the largest entropy, so h2 (e) ≤ n2 log2 (2πeD/n). Thus every B-bit reconstruction must satisfy 2he (u) n 2 (h2 (u)−B) n 2−2B/n . D≥ 2n exp = 2πe 2πe n Applying this with B = bd and substituting the entropy formula above yields d−1 Du (bd) ≥ 2πe

π d/2 Γ(d/2)

!2/(d−1)

ψ(1/2) − ψ(d/2) · exp d−1

2−2bd/(d−1) .

Since 2−2bd/(d−1) = ( 14 )bd/(d−1) , this is exactly the claimed lower bound. The numerical values of cd follow by direct evaluation of the displayed formula.

J Auxiliary Lemmas Lemma J.1 (Shannon’s lower bound on distortion, Lemma 2 in Zandieh et al. (2025a)). Let x ∈ Rd be a random vector with finite differential entropy h(x). Then, for any b ≥ 0, and any quantization map Q, the following Shannon Lower Bound holds: Ex [∥x − Q−1 (Q(x))∥22 ] ≥

2 d · 2 d (h(x)−bd) . 2πe

Lemma J.2 (High-probability error guarantees, Alon and Klartag (2017), Gao et al. (2025)). Let d be the dimension, and let ϵ, δ ∈ (0, 1). Suppose that an error bound ϵ with failure probability at most δ is required, and assume that ϵ12 log 1δ > d. Then the minimum number of bits required to achieve such a guarantee is Θ d log dϵ12 log 1δ . 41

Block-Sphere Vector Quantization

Lemma J.3 (High-probability angular error decay of RabitQ). Let x, and x̄ be a unit d-dimensional vector and its quantized vector by RabitQ, respectively. Then, for any L > 0, we have q c c1 L 0 2 2 <δ P 1 − ⟨x, x̄⟩ > b + √ · exp − L 2 2 δ where c0 and c1 are absolute constants. Lemma J.4 (High probability inner product distortion bound of QJL, Lemma 3.5 of Zandieh d−1 et al. (2025b)). Let S ∈ Rd×d have i.i.d. standard Gaussian rows. √ For fixed x, y ∈ S , π/2

define the inner product estimator IPQJL of QJL, i.e. IPQJL (y, x) := d ||x|| ⟨Sy, sign(Sx)⟩. Then, there exist universal constants cqjl , Cqjl > 0 such that, for all 0 < δ < 1 with log(2/δ) ≤ cqjl d, " # r log(2/δ) PS |IPQJL (y, x) − ⟨y, x⟩| > Cqjl x ≤δ d

K Additional Experimental Details and Results K.1

Approximate nearest-centroid assignment for BlockQuant

The exact encoding step of BlockQuant assigns each rotated block zj ∈ Rp to its nearest codebook centroid: idxj = arg min ∥zj − ci ∥22 , K = 2bp , i∈[K]

where b is the bit-width per coordinate and p is the block size. Since the number of blocks is m = d/p, the exact assignment costs O(mKp) distance evaluations per vector. This becomes expensive for larger b and p; for example, when p = 3 and b = 4, each block has K = 212 = 4096 candidate centroids. To reduce this cost, we use a lookup-table approximation that replaces the full nearestcentroid search by a small candidate search. The approximation changes only the encoding step; the codebook construction, dequantization, and ratio rescaling for inner-product estimation remain unchanged. Cartesian LUT construction. We partition the block domain into a Cartesian grid. Let each coordinate axis be divided into L bins, producing Lp grid cells. For a cell indexed by u ∈ [L]p , let Gu ⊂ Rp denote the cell and let gu be its center. For each grid center gu , we precompute the k closest codebook centroids: Ctopk (u) := arg topki∈[K] −∥gu − ci ∥22 . Equivalently, Ctopk (u) stores the indices of the k smallest values among {∥gu − ci ∥22 : i ∈ [K]}. This table is built once after the codebook is constructed and is reused for all input vectors. Approximate assignment. At quantization time, for each block zj , we first find the grid cell Gu(zj ) containing zj . Instead of comparing zj with all K centroids, we compare it only with the precomputed candidate set for that cell: f j = arg idx

min

i∈Ctopk (u(zj ))

∥zj − ci ∥22 .

Block-Sphere Vector Quantization

Thus the exact search space [K] is replaced by the much smaller candidate set Ctopk (u(zj )). The online assignment cost is reduced from O(mKp) to O(mkp), plus the negligible cost of locating the grid cell. After the approximate indices are obtained, dequantization proceeds in the same way as exact BlockQuant: ze′ = (cidx x e = Π⊤ ze′ . f 1 , . . . , cidx f m ), For inner-product estimation, we use the same ratio correction as in BlockQuantUB : x bapprox =

1 x e, ρe

ρe = ⟨z, ze′ ⟩.

Approximation error. The approximation is exact whenever the true nearest centroid belongs to the stored candidate set: idxj ∈ Ctopk (u(zj )). Even when this does not hold, the loss is controlled by the grid resolution. Let Di (z) := ∥z − ci ∥22 and let rL be the maximum distance between a point in a grid cell and its center: rL := max max ∥z − gu ∥2 . u∈[L]p z∈Gu

If all blocks, grid centers, and centroids lie in a bounded set with norm at most R, then for any z ∈ Gu , |Di (z) − Di (gu )| = ∥z − ci ∥22 − ∥gu − ci ∥22 ≤ 4RrL . Therefore, if ei(z) denotes the approximate index and i⋆ (z) denotes the exact nearest-centroid index, then Dei(z) (z) ≤ Di⋆ (z) (z) + 8RrL . Thus the additional per-block squared-distance error vanishes as the grid is refined. Increasing L decreases the discretization error, while increasing k increases the probability that the exact nearest centroid is included in the candidate set. Complexity. The LUT requires one-time preprocessing cost O(Lp Kp) to compute distances from all grid centers to all centroids, and memory O(Lp k) to store the candidate indices. Since we use small block sizes, in particular p = 3, this preprocessing is modest. The online assignment cost is O(mkp), which is substantially smaller than the exact cost O(mKp) when k ≪ K. In our experiments, this approximate assignment is used for BlockQuant unless otherwise specified. K.2

Quantization Efficiency

We compare GPU-based quantization runtime across bit-widths in Tables K.1 and K.2. Among baselines, EDEN variants are consistently the fastest and nearly constant across bit-widths, reflecting their coordinate-wise structure. RaBitQ incurs moderate overhead, while TurboQuant becomes slower at higher bit-widths due to additional correction steps. 43

Block-Sphere Vector Quantization

Table K.1: Runtime comparison for IP-based methods (seconds). Bitwidth

Method 1-bit

2-bit

3-bit

4-bit

TurboQuantPROD RabitQUB EDENUB

0.0225 0.0237 0.0220

0.0658 0.0391 0.0222

0.0627 0.0402 0.0221

0.0661 0.0392 0.0223

BlockQuantUB (p = 2) BlockQuantUB (p = 3) BlockQuantUB,approx (p = 3)

0.0238 0.0236 0.0251

0.0259 0.0318 0.0252

0.0372 0.1009 0.0254

0.0805 0.6573 0.0270

Table K.2: Runtime comparison for non-IP methods (seconds). Bitwidth

Method 1-bit

2-bit

3-bit

4-bit

TurboQuantMSE RabitQBSM EDENBSM

0.0219 0.0247 0.0220

0.0220 0.0392 0.0222

0.0218 0.0394 0.0221

0.0222 0.0402 0.0223

BlockQuantMSE (p = 2) BlockQuantMSE (p = 3) BlockQuantMSE,approx (p = 3)

0.0220 0.0218 0.0236

0.0242 0.0301 0.0237

0.0345 0.0961 0.0237

0.0778 0.6531 0.0265

BlockQuantMSE (p = 3) BlockQuantMSE,approx (p = 3)

0.0249 0.0273

0.0284 0.0273

0.0294 0.0277

0.0350 0.0340

For BlockQuant, the exact assignment cost grows rapidly with both block size and bit-width, especially for p = 3, where the runtime reaches 0.6573 seconds at 4 bits. In contrast, the approximate version removes this dependence on codebook size and remains nearly constant across bit-widths (e.g., 0.0251–0.0270 seconds for BlockQuantUB,approx ). A similar trend holds for MSE and UR variants in Table K.2. Overall, the LUT-based approximation reduces the complexity from full codebook search to a small candidate search, bringing BlockQuant to a runtime comparable with the fastest baselines while preserving its accuracy advantages. K.3

Computational Resources

Except for the KV-cache quantization experiments, all experiments are conducted on a GPU server with eight NVIDIA GeForce RTX 3090 GPUs, each with 24 GiB of VRAM, together with a dual-socket CPU server containing two Intel Xeon Gold 6226R processors, for a total of 32 cores and 32 threads. The KV-cache quantization experiments are conducted on a separate server with four NVIDIA H100 SXM5 GPUs, each with 80 GiB of VRAM, and two Intel Xeon Platinum 8592+ processors, totaling 128 cores and 128 threads.

Record · ID 204798 · SHA-256 1aa9a02e463ac518
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.