acceptodds
Under review as a conference paper at ICLR 2027

VENICE: UNIVERSAL SPECTRAL RATE-DISTORTION QUANTIZATION FRAMEWORK FOR VECTOR SEARCH

Abstract

High-dimensional vector embeddings impose severe memory and latency constraints in large-scale maximum inner product search. Vector quantization has emerged as the standard compression paradigm, where existing state-of-the-art methods perform effectively under classical assumptions of uncorrelated dimensions and isotropic energy distributions. Most real-world embeddings, however, exhibit a different geometry characterized by coordinate cross-correlations and anisotropic spectral decay, which we prove randomized Hadamard transforms redistribute rather than remove. To harness the benefits of non-uniform bit budgets, remove these cross-correlations, and correct inner product distortion, we present VENICE, a universal spectral framework that wraps arbitrary base quantizers as plug-and-play black boxes. Grounded in Shannon rate-distortion theory, VENICE transforms anisotropic embeddings into decoupled sub-vectors of uniform sensitivity through closed-form spectral decorrelation, water-filling rate allocation, and sensitivity equalization. This establishes the geometry downstream codecs were designed for, while norm restoration corrects the shrinkage of their output. We not only mathematically prove the foundational properties of VENICE, but also empirically validate its benefits across five benchmarks, wrapping six codecs of diverse nature. Across 4-, 2-, and 1-bit regimes, VENICE consistently improves both training-free and learned codecs on anisotropic spectra, cutting recall loss by up to 93% and rescuing ultra-low-bit quantizers from performance collapse.

Primary area:
optimization
Keywords:
vector search, quantization, venice, embeddings, shannon, adaptive

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_2UQWOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes VENICE, a geometry-preprocessing framework for retrieval-aware vector quantization. It formulates MIPS quantization error as an H-weighted quadratic form and introduces spectral decorrelation, reverse water-filling bit allocation, sensitivity equalization with local rotations, and norm restoration. The method is designed to work with different base quantizers without additional training. Experiments on multiple datasets and quantizers demonstrate improvements in retrieval quality, supported by ablation studies.

Critical strengths
  1. The paper identifies a clear and practically relevant mismatch between standard reconstruction error and retrieval quality. The query-aware distortion derived from the query second-moment matrix provides a principled motivation for the proposed design.
  2. Separating geometry preprocessing from the base quantizer is an interesting idea. The four components form a coherent pipeline and can be applied to both learned and training-free quantizers without additional learned parameters.
  3. The experimental evaluation is broad, covering multiple datasets, quantizers, and bit rates, with useful ablation studies. The limited gains on near-isotropic GloVe data are also consistent with the paper's motivation and provide a useful check of the proposed approach.
Critical weaknesses
  1. The mapping from coordinate-wise bit allocation to practical quantizer configurations (especially PQ and CAQ) is insufficiently explained, and the total storage cost including side information is not clearly accounted for.
  2. The reverse water-filling relies on a high-resolution approximation that may be inaccurate at 1–2 bits. Comparisons with allocation based on actual quantizer distortion are missing.
  3. The link between H-weighted distortion and ranking/top-k recall is not fully established. Robustness to query distribution shift and sensitivity to norm precision are also under-explored.
Questions for authors
  1. How is the coordinate-wise bit allocation translated into concrete configurations for PQ, CAQ, and similar quantizers? How is the total storage cost calculated?
  2. How does reverse water-filling compare with allocation strategies based on the actual distortion of the base quantizer at low bit rates?
  3. Can the authors better connect the H-weighted distortion to ranking errors, and evaluate robustness under query distribution shift?
  4. Do the gains hold under matched storage budgets and realistic latency? How sensitive is performance to the norm precision f?
3 comments

We thank the reviewer for the thorough feedback. We expanded the paper with explicit tier-mapping and byte-accounting specifications (Section 5.1, Appendix E), an empirical allocation study using true codec distortion (Appendix F), a theoretical and empirical link from $ e^T He $ to top-k ranking under query shift (Section 5.2, Appendix H), and end-to-end latency benchmarks (Appendix I).

  1. Tier mapping & total storage accounting (W.1, Q.1 — Section 5.1; Appendix E, Eq. 69, Table 1):
    • What we did: Documented how coordinates sharing $ b \in B_+ $ form at most T≤3T \le 3 sub-vectors (pruning b=0), each quantized by an unmodified uniform b-bit instance of the base codec (for PQ, 8/b-dim sub-vectors with 256-centroid codebooks; for CAQ and others, uniform b-bit tier encoding with native metadata m), and reported exact per-vector byte formulas and tables across all six codecs.
    • Conclusion: VENICE adds only 2+(T-1)m fixed bytes per vector (small relative overhead for d≥960d \ge 960 ) while substantially reducing recall loss across almost all settings.
  1. Closed-form $ 2^{-2b} $ water-filling vs. actual quantizer distortion (W.2, Q.2 — Appendix F, Figure 8):
    • What we did: For all 90 codec–dataset–rate settings (1, 2 and 4 bits), we measured the actual distortion of each base quantizer at every bit-width. We then re-ran VENICE's allocation with these measured curves instead of $ 2^{-2b} $ using the same solver and the same storage, with everything else unchanged.
    • Conclusion: Knowing the true distortion of the codec barely changes VENICE's recall. The differences are within noise at 1 and 4 bits, and small at 2 bits compared with VENICE's own gain. So the high-resolution approximation has negligible practical cost. The reason is that, for any decreasing distortion curve, the optimal allocation still gives more bits to the most important coordinates and prunes the least important ones; a more accurate curve only shifts the tier boundaries slightly (Remarks 5–6). VENICE therefore keeps its closed form, which is training-free and codec-agnostic, whereas the alternative would need every codec to be calibrated at every bit-width on each dataset.
  1. Connecting eTHee^T He to ranking & query distribution shift (W.3, Q.3 — Section 3.1, Section 5.2; Appendix H, Eq. 70, Table 2, Figure 10):
    • What we did: Linked per-vector RMS score perturbation eTHee^T He to top-k rank swaps via the parameter-free score-noise-to-margin ratio across 360 runs, and tested real out-of-distribution test queries (Hq≠Hx)(H_q \neq H_x) against an in-distribution document-query control (Hq=HxH_q=H_x).
    • Conclusion: All 360 evaluations collapse onto a single parameter-free monotonic curve linking eTHee^T He directly to top-k recall, and VENICE's recall gains remain invariant to natural query–database distribution shift.
  1. Matched storage budgets (Appendix E, Figure 7):

Plotting Recall@10@10 loss against exact total bytes per vector (all metadata included) shows VENICE lies strictly below standalone codecs and SAQ across the entire storage–accuracy Pareto frontier (Figure 7)—for instance, VENICE at 2 bits routinely outperforms standalone codecs at 4 bits (~2 fewer total bytes).

    • Realistic end-to-end latency (Appendix I, Figures 11–12):

Fusing projection onto the m≤dm \le d surviving coordinates with tier rotations into a single int8 SIMD matrix vector product reduces query overhead to O(md). On high-dimensional scans (d≥1536d\ge 1536 , N=106N=10^6), scan savings from coordinate pruning and lower bit-rates outweigh preprocessing, making VENICE faster end-to-end at matched recall than both FWHT-based RaBitQ and SAQ. Conversely, for short candidate rescoring (N=104N=10^4) and low-d BigANN (d=128), VENICE is ∼ 2 × slower at equal bit-rate because reference SIMD kernels optimize multiples of 64 dimensions, whereas VENICE's unrestricted tiers have arbitrary lengths (e.g., 8, 104, 16 at 4 bits)—highlighting a clean accuracy-vs.-SIMD-alignment tradeoff at small d.

    • Sensitivity to norm precision f (Section 5.1):

Storing the active-coordinate norm in f=16 bits matches 32-bit fp32 recall at half the metadata cost. As demonstrated in recent studies on norm-corrected codecs (https://arxiv.org/abs/2608.30384 section 3.3.1), 16-bit floating-point formats with sufficient mantissa precision (fp16 / UE7M9, 9–10 mantissa bits) are indistinguishable from fp32 for MIPS ranking, whereas 7-mantissa-bit bf16 degrades top-k recall.

Dear reviewer, thanks for your questions and suggestions. As the discussion period ends tomorrow, we would be grateful if you could take a look at our updates and let us know if there is something missing we could still help to clarify. Thanks a lot!

Thank you for the detailed response. My concerns have been adequately addressed, and I am happy to raise my score.

Reviewer_ScY9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors propose VENICE, a codec-agnostic framework for maximum inner product search that leverages spectral decorrelation, water-filling rate allocation, sensitivity equalization, and norm restoration. The authors provide theoretical guarantees for the component transformations. Empirically, VENICE improves the recall of six codecs on five datasets.

Critical strengths
  1. Composability VENICE is a universal framework that wraps existing codecs without modification. Figures 1 and 3 show improvements across both training-free and learned codecs using a single configuration, indicating that it's broadly applicable.
  2. Strong empirical performance VENICE outperforms SAQ on average when using the same base quantizer (CAQ), as shown in Figure 2.
Critical weaknesses
  1. Computational cost VENICE applies a orthogonal matrix to the query, which is a dense matvec that takes O(d2)O(d^2) compared to the O(dlog⁡(d))O(d \log(d)) of RHT, although SAQ also requires this. The experiments don't report query latency or throughput.
  2. Unclear ablation VENICE looks very similar to SAQ, as both have PCA, adaptive bit allocation, and within-segment rotation. Consider the standard setting where queries and datapoints (i) have zero mean, and (ii) share the same second-moment structure. In this case, we have λk=σk2\lambda_k=\sigma_k^2, so VENICE uses ∑kλkσk22−2bk=∑kσk42−2bk\sum_k \lambda_k\sigma_k^2 2^{-2b_k} = \sum_k \sigma_k^4 2^{-2b_k}, which has the same optimal bit allocation as SAQ's ∑kσk22−bk\sum_k \sigma_k^2 2^{-b_k} if we allow the rates to be (i) continuous and (ii) per-coordinate rather than per-segment. There are also some differences in segmentation/grouping, but in this setting VENICE's groups are also contiguous, although it allows unrestricted boundary locations, as opposed to SAQ's required alignment to 64 dimensions. There are many differences between VENICE and SAQ, but no ablation study to see how each of them contributes to the improvement over SAQ (Figures 5 and 6 are about PQ and RaBitQ rather than SAQ, the closest competitor).
Questions for authors
  1. What's the difference between VENICE and SAQ when queries and datapoints have zero mean and the same second moment? Can you run ablation under this setting to see how much each change improves the performance over SAQ when both use CAQ?
  2. What's recall versus end-to-end query latency against a baseline using RHT, e.g., RsLM versus VENICE+RsLM? Note that you should take the O(d2)O(d^2) query preprocessing time into consideration. I want to see the tradeoff between recall improvement and the additional preprocessing cost.
    1. It would be nice to have SAQ in the comparison as well, because its 64-dimension alignment requirement has a system benefit, but RsLM versus VENICE+RsLM is the most important one, so I would prioritize that if you don't have time to run all experiments.
2 comments

We thank the reviewer for the suggestion of deeper mathematical comparison with SAQ and practical system questions. We added a controlled crossover ablation between VENICE and SAQ around CAQ (Appendix J, Table 3) and end-to-end query latency benchmarks including preprocessing (Section 5.2; Appendix I, Figures 11–12).

  1. Differences & controlled ablation vs. SAQ (W.2, Q.1 — Section 5.2; Appendix J, Table 3; Figures 2, 5):
    • Analysis under μ=0\mu=0, H=ΣH=\Sigma: In your suggested setting, your derivation is correct: with continuous per-coordinate rates, VENICE's ∑kσk42−2bk\sum_k\sigma_k^4 2^{-2b_k} (Proposition 2) and SAQ's ∑kσk22−bk\sum_k\sigma_k^2 2^{-b_k} (SAQ, Eq. 17) share the KKT conditions σk22−bk⋆=θ~\sigma_k^2 2^{-b_k^\star}=\tilde\theta if bk⋆>0b_k^\star>0, σk2≤θ~\sigma_k^2\le\tilde\theta otherwise, hence the same allocation with contiguous tiers. (Zero mean does not hold on evaluated real datasets (μ≠0\mu\neq0, so λk=σk2+νk2\lambda_k=\sigma_k^2+\nu_k^2; Section 4.1), and SAQ is a standalone codec built around CAQ, whereas VENICE is a framework that wraps any base quantizer unchanged.) Three structural differences nevertheless remain: (i) global norm restoration vs. CAQ's per-segment scales, which inflate each segment's norm and leave 0-bit drops uncompensated (Section 4.4); (ii) unrestricted tier boundaries vs. 64-dim alignment, whose common per-segment rate costs up to a factor AM(wS)/GM(wS)\mathrm{AM}(w_S)/\mathrm{GM}(w_S) over the optimum (Proposition 1); (iii) sensitivity equalization before rotation, which keeps each tier block isotropic, whereas rotating an unscaled segment creates cross-talk (Proposition 3). When μ≠0\mu\neq0, VENICE also diagonalizes H rather than Σ\Sigma (Remark 14).
    • What we did: On the five benchmarks, we ran a pillar-by-pillar leave-one-out ablation of SAQ and CAQ+VENICE with the CAQ base codec fixed, pairing each SAQ component with its VENICE counterpart, together with a crossover (SAQ + Glob. Norm).
    • Conclusion: CAQ+VENICE beats SAQ in 13 of 15 settings. Global norm restoration (Pillar IV), which SAQ lacks, is the primary contributor: removing it causes the largest drops in VENICE, and adding it to SAQ recovers most of the gap on BigANN and OpenAI. Per-coordinate allocation (Pillar II) accounts for the additional gain where SAQ's 64-dim segmentation binds (low dimension, 1–2 bits), where VENICE stays ahead even after SAQ receives norm restoration. Removing Pillar III barely affects CAQ, which already rotates internally, but substantially hurts the non-rotating PQ (Figure 5).
  1. End-to-end query latency vs. RHT baselines & SAQ (W.1, Q.2 — Section 5.2; Appendix I, Figures 11–12):
    • What we did: Measured end-to-end query latency—explicitly including all query preprocessing—comparing VENICE against official C++/AVX2 SAQ/CAQ and a fast O(d log d) FWHT + SIMD FastScan baseline (RaBitQ-Library, which shares RSLM's fast Hadamard-scan architecture) at N=106N=10^6 and N=104N=10^4. We picked RabitQ for reproducibility (instead of RSLM) as it has available optimized open-source code.
    • Conclusion: Fusing projection onto the m≤dm \le d surviving coordinates with tier rotations into a single int8 SIMD matrix vector product reduces query overhead to O(md). On high-dimensional scans (d≥1536,N=106d\ge1536, N=10^6), scan savings from coordinate pruning and lower bit-rates outweigh preprocessing, making VENICE faster end-to-end at matched recall than both FWHT-based RaBitQ and SAQ. Conversely, for short candidate rescoring ( N=104N=10^4 ) and low-d BigANN (d=128), VENICE is ∼ 2 × slower at equal bit-rate because reference SIMD kernels optimize multiples of 64 dimensions, whereas VENICE's unrestricted tiers have arbitrary lengths (e.g., 8, 104, 16 at 4 bits)—highlighting a clean accuracy-vs.-SIMD-alignment tradeoff at small d.

Dear reviewer, thanks for your questions and suggestions. As the discussion period ends tomorrow, we would be grateful if you could take a look at our updates and let us know if there is something missing we could still help to clarify. Thanks a lot!

Reviewer_jNCVOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposed VENICE technique which is a general framework that improves embedding compression on the existing quantization methods for maximum inner product search. VENICE is based on four different foundations of spectral transformation, query-aware bit allocation, sensitivity equalization, and vector norm reconstruction. VENICE aims to assign different amount of precision to the different directions in the embedding space. The method is experimented over five different datasets (from vision to text), six different codecs, and over different bit budgets.

Critical strengths
  1. The paper conveyed the idea properly through text and provided formulas.
  2. Covering quite broad experiments over five datasets (from vision and text data), six different codecs, and various bit budgets.
Critical weaknesses

MAJOR

  1. storage accounting needs clarification; The bit rates presented in the paper reflect only the bits assigned to quantization codes, and do not account for the total storage requiremnts. In contrast to standard PQ that stores only the quantized codes, VENICE introduces an additional 16-bit value to represent each vector’s norm. This increases the storage cost of VENICE method while this additional storage cost is dependent on the dataset. In addition, according to Algorithm1, different quantization methods require different normalization or scaling parameters for each input. It is not clear in the paper that how these tier-specific parameters are handled, how they can are stored or reconstructed while maintaining compatibility with the original quantizers and introducing only a single additional scalar per vector. I think a fair comparison entails that the authors to report the actual storage cost in bytes per vector, accounting for all additional parametrs and metadata required for retreival.

  2. Search efficiency and throughput; Memory efficiency and computational speed are two key elemtns in measuring the efficincy of the quantization method. However, the experimental evaluation does not provide sufficient experiments to show how much is the query latency and encoding time. Since there is an accuracy–latency tradeoff here, I am interested to see comparison of the retrieval latency or query processing throughput versus accuracy.

  3. The query-distribution assumption cannot hold for all cases; The porposd retrieval etric in VENICE is dependent on Hq=Eq[qqT]H_q=\mathbb{E}_q[qq^T]. This is based on the assumption taht queries and databse vectors have the same/similar second moment structure. However, I think this assumption does not hold always true. So, it is recommedned that authors provide some experiments to evaluate the distribution mismatch between query and databse. Also, asses how much sensitive is the VENICE to the calibration sample size.

Questions for authors

Please refer to the Weaknesses section.

3 comments

We thank the reviewer for the constructive feedback. In the revised manuscript, we added full byte-level storage accounting and Pareto curves (Section 5.1, Appendix E), end-to-end latency and encoding-time benchmarks (Section 5.2, Appendix I), query–database distribution shift evaluations (Section 5.2, Appendix H), and calibration sample-size ablations (Section 5.1, Appendix G).

  1. Storage accounting needs clarification (W.1)

We agree, and now report total bytes per vector including all metadata, for all six codecs (Appendix E, Table 1). Net effect under matched storage: Across all experiments, VENICE lowers recall loss in 86 of 90 settings (the sole exceptions are three codecs on nearly isotropic GloVe at 4 bits) and remains strictly Pareto-optimal with wide-margin on the accuracy-vs.-total-bytes frontier across datasets (Figure 7).

  1. Search efficiency throughput (W.2)

We added end-to-end query latency (including query preprocessing) and offline encoding benchmarks using the official C++/SIMD libraries for RaBitQ (FWHT query rotation + FastScan) and CAQ/SAQ on a single thread (AMD Rome AVX2) at N=106N=10^6 exhaustive scan and N=104N=10^4 candidate-list rescoring (Section 5.2; Appendix I, Figures 11–12):

  • Query preprocessing & throughput–accuracy tradeoff: Fusing VENICE's active-coordinate projection and tier rotations into one cache-resident int8 SIMD matvec (O(md)) keeps preprocessing small, while pruning 0-bit tail dimensions and halving the bit-rate needed for a target recall makes VENICE faster end-to-end at matched recall on high-dimensional scans (d≥1536,N=106)(d\ge1536,N=10^6) and competitive or faster at index encoding. Only on short candidate lists (N=104N=10^4) or unaligned low-d tiers (d=128) does fixed projection or 64-dim SIMD alignment favor standalone baselines.

  • Calibration & index encoding time: One-time calibration on N=104N=10^4 vectors (estimating H, eigendecomposition, and water-filling) takes 4–6 s. Encoding 10610^6 vectors with VENICE+CAQ takes 8–23 s on GIST-960 and OpenAI—comparable to CAQ (13–26 s) and SAQ (12–22 s)—and 15–31 s on Wiki, which is 2.5–5.8x faster than CAQ/SAQ (71–99 s) because pruned dimensions are never encoded.

  1. The query-distribution assumption (W.3) All evaluation in the paper already contained results with real queries. Now we evaluated distribution mismatch across all 90 codec–dataset–rate pairs (Section 5.2; Appendix H, Table 2, Figure 10a) by comparing the effect on results if we replaced real queries distribution by using documents as queries:
    • What we did: Quantified the natural mean and spectral shift already present between standard test queries and database vectors (Hq≠Hx)(H_q \neq H_x), and compared VENICE's gains on these real out-of-distribution queries against a held-out in-distribution document-query control (Hq=Hx)(H_q=H_x) across all 90 settings.
    • Conclusion: Real benchmark queries already deviate substantially from DxD_x, yet VENICE achieves nearly identical relative recall-loss reductions under shifted and matched queries, confirming that calibrating H on database vectors generalizes robustly without query logs.

Calibration sample size (W.3):

We swept $N \in $ { 500,1k,2k,5k,10k,20k500,1k,2k,5k,10k,20k } across all five datasets, averaging Recall@10@10 loss over all six codecs and three bit budgets (Section 5.1; Appendix G, Figure 9): Conclusion: Recall loss plateaus rapidly around N=2,000 on every dataset; our default N=10,000 lies well inside this plateau and takes only a few seconds offline, with larger samples offering no further benefit.

Dear reviewer, thanks for your questions and suggestions. As the discussion period ends tomorrow, we would be grateful if you could take a look at our updates and let us know if there is something missing we could still help to clarify. Thanks a lot!

Reviewer_jNCVOpenReview ↗

Final Evaluation

I thank authors for the new experiments they have done, new discussions they added and new plots they provided. The authors directly addressed most of the points I raised, and my concerns regarding those evaluations are addressed now. So, I am happy to raise my score.

Comments on the paper

1 comment

Dear Area Chairs and Reviewers,

As the discussion window concludes, we thank all three reviewers for their feedback—and especially Reviewer 2UQW for confirming that our revisions resolved their concerns and updating their assessment positively.

For easy navigation of the revised PDF: while our initial submission established VENICE's closed-form rate-distortion theory and formal guarantees (Sections 3–4), we extended the practical and systems evaluations suggested across the reviews to complement those theoretical foundations:

  • Byte-Exact Storage Accounting (App. E, Table 1, Fig. 7): Full metadata accounting showing VENICE lies on the accuracy-vs.-bytes Pareto frontier (lowering recall loss in 86/90 settings).
  • End-to-End AVX2 Latency & Encoding Time (Sec. 5.2; App. I, Figs. 11–12): Faster end-to-end than C++/SIMD RaBitQ and SAQ at matched recall on high-d scans, including query preprocessing.
  • Controlled Crossover Ablation vs. SAQ (Sec. 5.2; App. J, Table 3): Isolates global norm restoration and per-coordinate allocation around fixed CAQ (ahead of SAQ in 13/15 settings).
  • Query Shift, Calibration Size & Codec Distortion (App. F–H, Table 2, Figs. 8–10): Confirms robustness under real out-of-distribution queries (N=2,000 calibration plateau) and measured low-bit codec distortion.

Thank you again for your time and constructive suggestions; we remain available for any final questions before the window closes.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.