acceptodds
Under review as a conference paper at ICLR 2027

AC-FDE: Towards Accurate and Compact Fixed-Dimensional Encodings for Multi-Vector Retrieval

Abstract

Multi-Vector Retrieval (MVR) improves retrieval accuracy but incurs high computational cost due to MaxSim. Fixed-Dimensional Encoding (FDE) enables single-vector search by approximating MaxSim through repeated random bucketing and aggregation. Increasing the number of repetitions can improve retrieval accuracy, but produces high-dimensional vectors that reduce efficiency. We propose AC-FDE to improve this efficiency–accuracy trade-off through query-independent repetition selection and sampled blockwise PCA. A distortion bound guides repetition selection, while blockwise PCA compresses the resulting vectors with projections learned from a random document subset. Our analysis characterizes stable rank, blockwise reconstruction error, and sampled-subspace stability under stated assumptions. AC-FDE-hybrid further combines compressed FDE vectors with high-dimensional single-vector embeddings for complementary retrieval signals. Experiments across four retrieval benchmarks demonstrate improved accuracy-efficiency trade-offs, with small additional offline costs relative to MUVERA.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Multi-vector Retrieval

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_QMRTOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes AC-FDE, a method that advances multi-vector approaches such as MUVERA. MUVERA works by turning multi-vector representations into single fixed-dimensional encodings (FDEs) by repeated random SimHash bucketing and aggregation. AC-FDE targets MUVERA's efficiency-accuracy trade-off: a good MaxSim approximation needs many repetitions, which makes the FDE vectors very high-dimensional. With AC-FDE, the authors propose adding two offline steps, both of which are fitted to a small random sample of documents (10% by default). First, it selects repetitions without considering queries. Second, it compresses the encodings with PCA run separately on each repetition. At query time, the stored repetitions and projections are applied to the query FDE, followed by HNSW search and MaxSim reranking. Experiments on MS MARCO, SciDocs, FiQA, and NQ report up to 4.3x speedup over MUVERA, LEMUR, and multi-vector indexing baselines at equal recall, better pre-reranking candidate recall than LEMUR, and small offline overhead over MUVERA.

Critical strengths
  1. Interesting idea that addresses a real practical problem.
  2. AC-FDE is a simple and cheap method.
Critical weaknesses

The paper proposes an interesting idea. However, several problems affect the current submission, which is IMHO not ready for publication in its current shape. Here are some detailed points

  1. The experimental evaluation can be significantly improved. Several points on this: 1) Table 1 reports only the comparison between AC-FDE and LEMUR. Why not add MUVERA too? You added it as an evaluated method in Section 8.1. 2) The use of 1-Recall@N, although the authors provide a pointer to prior work, is not explained. Why is this metric used in this kind of evaluation? 3) Ground truth is not defined in the main text. 4) Table 1 uses HNSW (efSearch=500). The analysis mixes encoding error with approximate-search error. 5) MUVERA is run with PQ, and the multi-vector index baselines (PLAID, EMVB, IGP, WARP) appear with only a few operating points in Fig. 2. It is not clear how they were tuned to their own Pareto frontiers. Please describe how the multi-vector index baselines (PLAID, EMVB, IGP, WARP, DESSERT, GEM) are configured and tuned. 6) A recent SOTA multi-vector index is not tested nor discussed [1]. I suggest authors to add and compare to it.

  2. In terms of writing and presentation, the main paper (first nine pages) is too dense and difficult to read. Six theorems are packed into Sections 2-5, with little intuition provided. Figures 2-4 are hard to read at their printed size.

In its current form, the paper is not ready for publication. I suggest that the authors move the key evidence for repetition selection into the main text, shorten the theory in favor of intuition, fully specify the experimental setup, and add the missing comparisons (especially MUVERA).

Minor things:

  1. Algorithm 1: "Equation equation 6"
  2. "Validataion", end of page 33

[1] Martinico et al. Efficient Multivector Retrieval with Token-Aware Clustering and Hierarchical Indexing. ACM SIGIR 2026.

Questions for authors

see my weaknesses

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

AC-FDE aims to improve the accuracy–efficiency trade-off of MUVERA's fixed-dimensional encoding. The authors combine three components to improve MUVERA. Adaptive repetition selection uses document-side bucket occupancy to select repetitions with small approximation distortion. Blockwise PCA performs dimensionality reduction per repetition, and document subsampling reduces the offline cost of PCA fitting and repetition selection. AC-FDE-hybrid further combines the compressed FDE representation with a single-vector embedding to exploit complementary retrieval signals. Experiments on MS MARCO, SciDocs, FiQA, and NQ show up to 4.3× speedup at equivalent recall.

Critical strengths
  1. The high FDE dimension of MUVERA is an important issue for ANN index construction and query processing in practice. AC-FDE addresses this practical limitation without requiring modifications to the underlying multi-vector retriever.

  2. The authors provide theoretical analyses of the query-independent distortion bound, stable rank, blockwise PCA reconstruction error, and sampled-subspace stability. These analyses provide useful justification for the proposed design choices.

  3. An interesting contribution is the query-independent repetition selection criterion based on document-side bucket occupancy. Unlike MUVERA's random repetitions, AC-FDE selects repetitions according to a theoretically motivated distortion score, enabling more effective encoding under the same repetition budget.

  4. The combination of blockwise PCA and document subsampling provides a practical way to reduce the dimensionality and offline computation of FDE representations while maintaining retrieval accuracy.

Critical weaknesses
  1. While PCA and sampling are established techniques, the main novelty lies in the query-independent repetition selection criterion. The paper could better clarify how this criterion differs from simpler document-side statistics or alternative repetition selection heuristics.

  2. The relative contributions of repetition selection and blockwise PCA could be discussed more clearly in the main text, rather than relying primarily on the ablation results in Appendix M.1.

  3. Although the hybrid experiments include several controlled fusion baselines, it remains unclear which query characteristics benefit most from combining AC-FDE with SVR embeddings. A more detailed analysis of their complementary retrieval signals would strengthen the interpretation of the hybrid results.

Questions for authors
  • Appendix M.3 reports a positive correlation between the occupancy score and the MaxSim approximation error. Could the authors clarify whether this relationship remains consistent across different datasets and encoding configurations?

  • Which types of queries benefit most from AC-FDE-hybrid? For example, does the improvement primarily come from queries requiring fine-grained lexical matching or broader semantic matching?

2 comments

Thank you for the thorough rebuttal and additional experiments. I keep my original rating.

Thank you for your response and for reviewing our rebuttal. We have updated the revised PDF to include all the additional experiments and analyses. We sincerely appreciate your time and valuable feedback.

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

This paper introduces AC-FDE, an efficient fixed-dimensional encoding framework for multi-vector retrieval. Building upon MUVERA, the authors aim to improve the accuracy-efficiency trade-off through three main components: (1) adaptive repetition selection, (2) blockwise PCA, and (3) document sampling. Experiments demonstrate that AC-FDE achieves favorable accuracy-efficiency trade-offs compared with baseline methods.

Critical strengths

(1) Good motivation with effective and practical method design. (2) Comprehensive theoretical and experimental analysis.

Critical weaknesses

(1) The evaluation is restricted to four datasets (MS MARCO, FiQA, NQ, and SciDocs), which predominantly feature relatively short and QA-style queries. It remains unclear whether AC-FDE generalizes to more diverse query characteristics, such as long, complex, or domain-specific queries.

(2) AC-FDE introduces several hyperparameters, including the number of candidate repetitions, the number of selected repetitions, the number of buckets, the projection dimensions, and the sampling rate. However, their effects are not sufficiently investigated, making it difficult to assess the robustness of the method and identify suitable configurations in practice.

(3) Although the author compare blockwise PCA with full PCA, it lacks comparisons with other efficient dimensionality reduction techniques, such as randomized PCA or learned MLP-based projections.

Questions for authors

(1) How well does AC-FDE generalize to queries with different lengths, difficulties, or domain-specific queries? Please evaluate on more scenarios. (2) How sensitive is AC-FDE to its key hyperparameters? (3) How does blockwise PCA compare with other efficient dimensionality reduction approaches (under comparable computational and dimensionality budgets)? (4) How does AC-FDE behave when the assumptions underlying its theoretical analysis are weakened or violated, particularly for long, semantically heterogeneous documents?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.