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

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.