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

arXiv:2605.30120 · cs.IR, cs.AI, cs.LG · Submitted 2026-05-28 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "No More K-means".

Jane: Single-stage Sparse Retrieval (SSR) proposes a paradigm shift from dense approximation to efficient sparse coding, replacing expensive clustering with sparse autoencoding to achieve high-throughput retrieval while retaining fine-grained semantic information.

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So we've covered the main points of "No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval," focusing on how sparse coding replaces dense methods, the role of hybrid training, and the speed gains from neuron-level indexing.

Jane: We've also discussed how this method addresses the trade-off between precision and efficiency by using coarse-to-fine pruning and theoretical guarantees to ensure accuracy remains high during acceleration.

Lu: The overall message is that we can achieve high performance in multi-vector retrieval by leveraging sparse autoencoding to create an efficient, neuron-level interaction structure instead of relying on expensive vector clustering.

Meng: It really gives us a new direction for optimizing the engineering side of this kind of system; focusing on building efficient sparse autoencoders that can handle these high-dimensional embeddings is the next big challenge for practical implementation.

Lalam: For me, this research means we can build AI that is not just powerful in knowledge, but also incredibly nimble and efficient when it needs to retrieve and utilize that knowledge quickly across vast amounts of data.

Tom: We've covered the main points of "No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval," focusing on how sparse coding replaces dense methods, the role of hybrid training, and the speed gains from neuron-level indexing.

Jane: We've also discussed how this method addresses the trade-off between precision and efficiency by using coarse-to-fine pruning and theoretical guarantees to ensure accuracy remains high during acceleration.

Lu: The overall message is that we can achieve high performance in multi-vector retrieval by leveraging sparse autoencoding to create an efficient, neuron-level interaction structure instead of relying on expensive vector clustering.

Meng: It really gives us a new direction for optimizing the engineering side of this kind of system; focusing on building efficient sparse autoencoders that can handle these high-dimensional embeddings is the next big challenge for practical implementation.

Lalam: For me, this research means we can build AI that is not just powerful in knowledge, but also incredibly nimble and efficient when it needs to retrieve and utilize that knowledge quickly across vast amounts of data.

Conclusion: Tom: So we've really been talking about how this paper, "No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval," completely changes the game for how we search across huge collections of data.

Jane: That's right, Tom; essentially, the authors took dense vector methods that were getting too slow and replaced them with a clever sparse coding technique to find relevant information much more efficiently.

Lu: I think what’s really striking is how they manage to preserve the high level of semantic detail in this new sparse format while achieving this massive speed improvement we've been discussing.

Meng: From my side, I'm still wrestling with the practicalities of deploying these sparse structures on actual hardware; we need to see if this theoretical efficiency translates into a system that runs smoothly in a production environment.

Lalam: For me, the real impact is seeing AI systems become incredibly nimble when it needs to pull specific pieces of knowledge out of massive datasets without getting bogged down in slow searches.

Tom: Exactly, Lalam; the authors are showing us that by focusing on these sparse interactions rather than checking every single vector, we can build retrieval systems that are both way more accurate and drastically faster.

Jane: It’s a big step because it shows a clear path for scaling up multi-vector search capabilities without hitting those old computational walls we used to face with dense representations.

Lu: The paper also lays out some very solid mathematical proof, which gives us confidence that this sparse approximation actually stays close enough to the original, more complex interaction score.

Meng: That theoretical backing is important for engineering; it tells us the limits of what we can expect in terms of distortion when we trade speed for sparsity.

Lalam: And if we get this right, it suggests a future where AI systems don't just store massive vectors, but learn the most essential semantic pathways directly into their structure for extremely fast access.

Tom: So, to wrap up this part of our conversation, the main takeaway is that single-stage sparse coding offers a powerful way to make multi-vector retrieval both more accurate and much faster than traditional dense methods.

Stony Brook University

cs.IR, cs.AI, cs.LG

Submitted: 2026-05-28

Updated: 2026-09-28

Comments: Accepted by ICML2026

Code: https://github.com/Y-Research-SBU/SSR

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 91/100

The gist: Single-stage Sparse Retrieval (SSR) proposes a paradigm shift from dense approximation to efficient sparse coding, replacing expensive clustering with sparse autoencoding to achieve high-throughput

Key concepts

Sparse Autoencoder (SAE)
This is a neural network trained to compress complex, high-dimensional token embeddings into a much smaller, highly sparse vector representation. Instead of storing every possible feature, it learns only the most important 'active' neurons for each token.
Neuron-Level Inverted Indexing
Instead of comparing full vectors (which is slow), SSR uses an inverted index based on individual neurons. This index stores which documents activate specific neurons, allowing the system to quickly find relevant documents by looking only at the activated features.
MaxSim Operator Interaction
The similarity score calculation is modified so that interactions only happen between neurons that are 'activated' (i.e., important). This focuses the search on a small subset of relevant features, making the final sparse interaction score much faster to compute than dense methods.

Terminology

Summary

Single-stage Sparse Retrieval (SSR) proposes a paradigm shift from dense approximation to efficient sparse coding, replacing expensive clustering with sparse autoencoding to achieve high-throughput retrieval while retaining fine-grained semantic information.

The gist

SSR projects token embeddings into a high-dimensional but highly sparse feature space via Sparse Autoencoder (SAE), enabling direct and efficient semantic retrieval by leveraging neuron-level inverted indexing instead of relying on vector clustering.

How it works

The core mechanism involves transforming dense token embeddings into sparse vectors using a learned SAE. The process is defined as follows:

  1. Each token embedding is mapped into a sparse vector, resulting in query vectors Q' and document vectors D'.

  2. The fine-grained similarity score S(Q, D) is calculated using the MaxSim operator, but crucially, this interaction only occurs between activated neurons: the interaction only occurs between activated neurons.

  3. The sparse late-interaction score is computed as:

z⊤qi zdj = X u∈AK(zqi)∩AK(zdj) z(u) qi z(u) dj.

Hybrid Training of Sparse Projectors

To ensure the learned sparse features are both reconstructive and discriminative, a hybrid training objective is employed. This objective combines unsupervised and supervised losses:

  1. Unsupervised TopK Sparse Autoencoding minimizes reconstruction error under sparsity constraints using the loss: Lrecon(k) = ∥x − xˆ∥2 / 2 under sparsity k.

  2. The overall loss function is formulated as LSSR = Lunsup + γLCE, where Lunsup combines reconstruction losses with auxiliary and sparse contrastive losses (Laux and Lcl).

  3. Supervised Contrastive Learning (LCE) is incorporated to help the SAE capture semantic differences between positive and negative documents, using a similarity score sim for positive/negative pairs.

Sparsity-Enabled Efficient Indexing and Retrieval

Leveraging the high sparsity (K ≪ h) of sparse features, SSR circumvents the expensive cluster-based scanning of dense MVR by utilizing neuron-level inverted indexing:

  1. A posting list Iu is constructed for each neuron dimension u, storing the maximum impact: µD,u = max t∈D z(u)t.

  2. To facilitate retrieval, each list Iu is partitioned into fixed-size blocks where an upper-bound score UB = max D∈B µd,u is stored. This block organization enables early pruning during posting-list traversal.

  3. The retrieval process involves traversing the union of posting lists corresponding to the top-K activated neurons, which is significantly faster than scanning dense vector clusters.

SSR++: Accelerated Retrieval with Pruning

To further reduce latency, an accelerated variant, SSR++, employs a coarse-to-fine pruning strategy:

  1. Step 1 (Coarse Scoring): For each query token qi, only the principal active neurons AKcoarse(qi) are extracted (with Kcoarse < K), and an approximate upper-bound score Sˆ coarse is computed using block upper-bounds UB to rapidly produce a small candidate set C1.

  2. Step 2 (Exact Refinement): For the refined subset C1, the system reverts to the full set of activated neurons AK(qi) to compute the precise late-interaction score defined in Equation (4).

Theoretical Guarantees and Performance

The paper provides a theoretical characterization of SSR's effectiveness. Theorem A proves that SSR is a bounded-distortion approximation to dense interaction, showing that the dense similarity differs from the sparse inner product by at most O(Bϵ + ϵ2 + δC2). Theorem B extends this to the full MaxSim late-interaction score, stating that Sdense(Q, D) − SSSR(Q, D) ≤ Nη, where η is a bounded distortion term. Empirical results demonstrate SSR achieves state-of-the-art retrieval performance with halved retrieval latency compared to competitive baselines and a 15x reduction in indexing time by eliminating the clustering bottleneck. Furthermore, SSR shows robustness across various benchmarks, achieving the best results on 9 of 13 BEIR datasets.

Empirical Validation

Experiments confirm that SSR simultaneously optimizes accuracy, speed, and scalability. SSR-CLS achieved the highest average performance (53.4) and maintained sub-20ms retrieval latency. When tested on modern Large Language Model backbones like Llama-embed-nemotron-8b, SSR achieves a best average score of 67.1 for SSR-CLS, outperforming strong baselines such as Qwen3-Embedding-8B.

Improvements for AI systems

As a fastidious and diligent researcher, I have analyzed No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval. The core innovation lies in replacing computationally expensive clustering (like K-means) with Sparse Autoencoders (SAE) to project token embeddings into high-dimensional sparse spaces.

Here are the specific improvements I can implement in AI systems based on this paper, and what the resulting system can achieve:

)Specific Improvements for AI Systems:

  1. Organize Retrieval Indexing via Neuron-Level Inverted Indexing:

  2. Implement Coarse-to-Fine Pruning (SSR++):

  3. Employ Hybrid Training Objectives for Sparse Projectors (LSSR):

  4. Utilize Adaptive Sparsity Control based on Query Length:

)What the Improved AI System Can Do (Specific Capabilities):

)Specific System Capabilities Achieved by these Improvements:

)Detailed Specific Outcomes of the Improved AI System:

  1. Organize Retrieval Indexing via Neuron-Level Inverted Indexing:

  2. Implement Coarse-to-Fine Pruning (SSR++):

  3. Employ Hybrid Training Objectives for Sparse Projectors (LSSR):

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.

Sources

Related papers