No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval
Lixuan Guo, Yifei Wang, Tiansheng Wen, Aosong Feng, Stefanie Jegelka, Chenyu You · 2026
Read No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval by Lixuan Guo, Yifei Wang, Tiansheng Wen, Aosong Feng, Stefanie Jegelka, Chenyu You (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30120.txt.
Introduction
Lixuan Guo and five colleagues replace clustering with sparse coding in costly multi-vector retrieval. Leading systems tame billion-scale token vectors with dimension reduction and K-means, paying in indexing delay and lost meaning. Their Single-stage Sparse Retrieval method projects token embeddings through a sparse autoencoder into a highly sparse code, then uses inverted indexing with no clustering step. On BEIR it cuts indexing time fifteenfold against ColBERTv2 and halves retrieval latency, while improving retrieval quality.
Catalog record
| CREATOR | Lixuan Guo, Yifei Wang, Tiansheng Wen, Aosong Feng, Stefanie Jegelka, Chenyu You |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73098 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.30120
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval Lixuan Guo, Yifei Wang, Tiansheng Wen, Aosong Feng, Stefanie Jegelka, Chenyu You 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. † † affiliationnotice: Equal contribution Figure 1 : Single-stage Sparse Retrieval (SSR). (a) Paradigm Comparison. Unlike dense MVR, which compresses embeddings into low-dimensional vectors and requires exhaustive token-pair computations, our sparse MVR projects features into a high-dimensional sparse space via Sparse Autoencoders (SAE). This enables efficient interaction calculation solely on overlapping activated neurons. (b) Trade-off Analysis. Single Vector Retrieval offers high efficiency but suffers from semantic compression loss. Dense MVR preserves token-level details but incurs heavy computational overheads due to clustering and multi-stage pruning (inefficient indexing). SSR bridges this gap, accelerating retrieval via natural inverted indexing while retaining fine-grained semantic information. (c) Performance vs. Efficiency. SSR achieves state-of-the-art retrieval performance with halved retrieval latency compared to competitive baselines. Notably, it delivers a 15x reduction in indexing time (indicated by bubble size) by eliminating the clustering bottleneck. 1 Introduction Neural information retrieval has long faced a fundamental trade-off between precision and efficiency ( 22 ; 6 ; 69 ; 44 ) . While Single-Vector Retrieval (SVR) enables high-throughput search via simple dot products, it often struggles to capture the intricate semantic nuances of complex queries. In contrast, Multi-Vector Retrieval (MVR) paradigms, pioneered by ColBERT ( 22 ) , have established a new standard for effective retrieval. By preserving documents as sequences of token-level embeddings and employing late interaction (e.g., MaxSim) mechanisms, MVR achieves fine-grained semantic alignment that SVR typically misses. However, such precision imposes substantial storage and computational overheads. Representing documents as bags of vectors causes the index size to explode by orders of magnitude compared to single-vector baselines. To make deployment feasible, state-of-the-art systems like PLAID ( 44 ) rely on aggressive approximation strategies, such as Vector Quantization (VQ) and large-scale clustering (e.g., K-means). While these engineering optimizations mitigate retrieval latency, they leave two critical issues unresolved. First, compressing rich token embeddings into short codes or centroids inevitably incurs information loss, sacrificing the very semantic details MVR aims to preserve. Second, the indexing process remains prohibitively complex: performing clustering on billion-scale token datasets is computationally expensive, creating a severe bottleneck for index construction and real-time updates. This leads us to a pivotal question: Can we retain the token-level granularity of MVR while achieving similar retrieval speed of lexical search, without the heavy burden of clustering? In this paper, we propose a paradigm shift from dense approximation to S ingle-stage S parse R etrieval ( SSR ). As shown in Figure 1 (Left) , instead of compressing token embeddings into lower-dimensional dense embeddings, we project them into a significantly higher-dimensional but highly sparse feature space using Sparse Autoencoder (SAE) ( 17 ; 27 ) . This transformation disentangles complex token semantics into sparse vectors with few active neurons (e.g., 32). Crucially, this sparsity unlocks a structural advantage that dense methods lack: it enables us to discard K-means entirely and utilize the inverted index, allowing each active dimension to function as a ”pseudo token”, which is the same efficient data structure powering traditional keyword search (e.g., BM25 ( 42 ) ). We present two implementations: SSR-tok, which only focuses on token-level interactions, and SSR-CLS, which incorporates global semantics by integrating [CLS] embedding similarities. We empirically validate SSR on the MS MARCO ( 37 ) (in-domain) and BEIR ( 49 ) (out-of-domain) benchmarks. Our results demonstrate that SSR simultaneously optimizes accuracy, speed, and scalability: it matches or exceeds the performance of state-of-the-art retrievers (achieving an average 2.2% improvement over the strongest baseline) while nearly halving retrieval latency and reducing index construction time by over 15 \times (by eliminating the clustering overhead). Furthermore, we demonstrate the scalability of our approach by applying it to modern Large Language Model backbones (Llama-Embed-8B ( 1 ) ), achieving performance competitive with the latest single-vector embedding models. We discuss in detail the evolution of single-vector retrieval and multi-vector retrieval techniques in Appendix B , highlighting the correlations and limitations of existing methods that motivate SSR. Our code is released at https://github.com/Y-Research-SBU/SSR . Our contributions are as follows: • We propose Single-stage Sparse Retrieval , a framework for efficient and effective multi-vector sparse coding, enabling direct use of inverted indices for single-stage semantic retrieval. • We introduce a hybrid training objective that combines reconstruction loss with a multi-vector contrastive loss, ensuring that the learned sparse features are discriminative for ranking tasks. • Extensive in-domain and out-of-domain evaluations confirm that SSR effectively improves the efficiency-effectiveness trade-off frontier, delivering sub-20ms retrieval latency and state-of-the-art indexing speed without compromising retrieval quality. Figure 2 : Conceptual comparison between standard retrieval paradigms (e.g., PLAID ( 45 ) ) and our proposed SSR. 2 Background 2.1 Problem Formulation The objective of a retrieval task is to get a ranked list of documents from a large-scale corpus \mathcal{D}=\{D_{1},\dots,D_{|\mathcal{D}|}\} that are semantically relevant to a user query Q . Both the query Q=(q_{1},\dots,q_{|Q|}) and the document D=(d_{1},\dots,d_{|D|}) are typically represented as sequences of tokens. The core challenge is to learn a parameterized scoring function s_{\theta}(Q,D)\in\mathbb{R} that quantifies the relevance between the query-document pair. Ideally, for a relevant document D^{+} and a non-relevant document D^{-} , the model should satisfy s_{\theta}(Q,D^{+})>s_{\theta}(Q,D^{-}) . 2.2 Existing Multi-Vector Retrieval Paradigm Despite architectural variations in recent literature, the inference process of modern Multi-Vector Retrieval (MVR) models generally converges to a three-stage filter-and-refine paradigm, as illustrated in Figure 2 . Formally, given a query Q=\{q_{1},\dots,q_{N}\} and a document corpus \mathcal{D} , the goal is to efficiently identify top- k documents that maximize the late interaction score S(Q,D) . Stage I: Indexing & Candidate Generation. Handling billion-scale token vectors necessitates an efficient pre-filtering mechanism. Specifically, document tokens are mapped to a codebook of centroids \mathcal{C}=\{\mathbf{c}_{1},\dots,\mathbf{c}_{K}\} via clustering engines such as FAISS ( 13 ) in the indexing stage. During retrieval, for each query token q_{i} , the system identifies a set of nearest centroids \mathcal{C}_{i}\subset\mathcal{C} and retrieves the associated document list. The initial candidate set \mathcal{D}_{\text{cand}} is the union of documents hit by these active centroids: \mathcal{D}_{\text{cand}}=\bigcup_{q_{i}\in Q}\bigcup_{\mathbf{c}\in\mathcal{C}_{i}}\phi(\mathbf{c}) (1) where \phi(\mathbf{c}) represents the set of documents that include tokens in the centroid \mathbf{c} . This stage typically