No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval

• URL: http://arxiv.org/abs/2605.30120v3
• Date: Wed, 03 Jun 2026 08:02:09 GMT
• Title: No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval
• Abstract summary: Single-stage Sparse Retrieval (SSR) is a paradigm shift that replaces expensive clustering with efficient sparse coding.<n>It reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance.
• Score: 51.43543998583709
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-vector retrieval (MVR) models, exemplified by ColBERT, have established new benchmarks in retrieval accuracy by preserving fine-grained token-level interactions. However, this granularity imposes prohibitive storage and retrieval efficiency bottlenecks: to manage the immense memory footprint and computational overhead of billion-scale token vectors, state-of-the-art systems are forced to rely on aggressive dimension reduction and complex clustering (e.g., K-means). This compromise introduces two critical limitations: excessive indexing latency of clustering large-scale corpora and semantic information loss inherent to compression. In this paper, we propose Single-stage Sparse Retrieval (SSR}, a paradigm shift that replaces expensive clustering with efficient sparse coding. Instead of compressing features into low-dimensional dense vectors, we utilize Sparse Autoencoder (SAE) to project token embeddings into a high-dimensional but highly sparse representation. This transformation enables us to bypass vector clustering entirely and leverage inverted indexing for precise, high-throughput retrieval. Extensive experiments on the BEIR benchmark demonstrate that SSR achieves a "trifecta" of improvements: it reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance over leading baselines.

Related papers

• Efficient Multivector Retrieval with Token-Aware Clustering and Hierarchical Indexing [11.098422338598454]
  TACHIOM is a multivector retrieval system that exploits token-level structure to significantly accelerate both clustering and retrieval.<n>By accounting for tokens' distribution during centroid allocation, TACHIOM easily scales to millions of centroids, enabling highly accurate document scoring using only centroids.
  arXiv  Detail & Related papers  (2026-04-30T17:30:15Z)
• Auto-FlexSwitch: Efficient Dynamic Model Merging via Learnable Task Vector Compression [54.12624130407679]
  We propose T-Switch, which decomposes task vectors into three compact components.<n>We then introduce Auto-Switch, a training-free merging scheme that automatically composes task vectors.<n>We present Auto-FlexSwitch, a dynamic model merging approach that supports highly efficient task vector compression.
  arXiv  Detail & Related papers  (2026-04-30T16:58:05Z)
• Towards Practical Lossless Neural Compression for LiDAR Point Clouds [84.36825469211375]
  extreme sparsity of high-precision geometric details hinders efficient context modeling.<n>Our framework comprises two lightweight modules.<n>Experiments demonstrate competitive compression performance at real-time speed.
  arXiv  Detail & Related papers  (2026-03-26T10:02:07Z)
• Multi-Vector Index Compression in Any Modality [73.7330345057813]
  Late interaction has emerged as a dominant paradigm for information retrieval in text, images, visual documents, and videos.<n>We introduce four approaches for index compression: sequence resizing, memory tokens, hierarchical pooling, and a novel attention-guided clustering (AGC)<n>AGC uses an attention-guided mechanism to identify the most semantically salient regions of a document as cluster centroids and to weight token aggregation.
  arXiv  Detail & Related papers  (2026-02-24T18:57:33Z)
• Multivector Reranking in the Era of Strong First-Stage Retrievers [11.098422338598454]
  We reproduce several state-of-the-art multivector retrieval methods on two publicly available datasets.<n>We show that replacing the token-level gather phase with a single-vector document retriever produces a smaller and more semantically coherent candidate set.<n>Our two-stage approach achieves over $24times$ speedup over the state-of-the-art multivector retrieval systems, while maintaining comparable or superior retrieval quality.
  arXiv  Detail & Related papers  (2026-01-08T18:22:18Z)
• From HNSW to Information-Theoretic Binarization: Rethinking the Architecture of Scalable Vector Search [0.7804710977378487]
  This paper analyzes the architectural limitations of the dominant "HNSW + float32 + cosine similarity" stack.<n>We introduce and empirically evaluate an alternative information-theoretic architecture based on maximally informative binarization (MIB)<n>Results demonstrate retrieval quality comparable to full-precision systems, while achieving substantially lower latency and maintaining constant throughput at high request rates.
  arXiv  Detail & Related papers  (2025-12-16T23:24:37Z)
• Re-Densification Meets Cross-Scale Propagation: Real-Time Neural Compression of LiDAR Point Clouds [83.39320394656855]
  LiDAR point clouds are fundamental to various applications, yet high-precision scans incur substantial storage and transmission overhead.<n>Existing methods typically convert unordered points into hierarchical octree or voxel structures for dense-to-sparse predictive coding.<n>Our framework comprises two lightweight modules. First, the Geometry Re-Densification Module re-densifies encoded sparse geometry, extracts features at denser scale, and then re-sparsifies the features for predictive coding.
  arXiv  Detail & Related papers  (2025-08-28T06:36:10Z)
• CRISP: Clustering Multi-Vector Representations for Denoising and Pruning [7.580000668015255]
  Multi-vector models such as ColBERT deliver state-of-the-art performance by representing queries and documents by contextualized token-level embeddings.<n>A common approach to mitigate this overhead is to cluster the model's frozen vectors, but this strategy's effectiveness is limited by the intrinsic clusterability of these embeddings.<n>We introduce CRISP, a novel multi-vector training method which learns inherently clusterable representations directly within the end-to-end training process.
  arXiv  Detail & Related papers  (2025-05-16T17:26:16Z)
• Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
  We propose a tile-based strategy that partitions the contrastive loss calculation into arbitrary small blocks. We also introduce a multi-level tiling strategy to leverage the hierarchical structure of distributed systems. Compared to SOTA memory-efficient solutions, it achieves a two-order-of-magnitude reduction in memory while maintaining comparable speed.
  arXiv  Detail & Related papers  (2024-10-22T17:59:30Z)
• CITADEL: Conditional Token Interaction via Dynamic Lexical Routing for Efficient and Effective Multi-Vector Retrieval [72.90850213615427]
  Multi-vector retrieval methods combine the merits of sparse (e.g. BM25) and dense (e.g. DPR) retrievers. These methods are orders of magnitude slower and need much more space to store their indices compared to their single-vector counterparts. We propose conditional token interaction via dynamic lexical routing, namely CITADEL, for efficient and effective multi-vector retrieval.
  arXiv  Detail & Related papers  (2022-11-18T18:27:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.