TL;DR
SIMQ (Single Graph Index for Multi-vector Query) is a new framework that makes high-performance multi-vector retrieval (like ColBERT) significantly faster and more accessible by running efficiently on CPUs. By replacing expensive "interaction matrices" and GPU-heavy clustering with a single graph index and data-aware sampling, SIMQ achieves state-of-the-art retrieval speed and accuracy without specialized hardware.
What Problem Does This Paper Address?
Modern search engines are moving toward multi-vector retrieval (e.g., ColBERT), where a document isn't just one embedding, but a collection of embeddings—one for every token. This captures rich semantic nuances but introduces a massive computational headache: the MaxSim scoring mechanism.
To score a document, you have to find the maximum similarity between each query token and all document tokens, then sum them up. At scale, this is prohibitively slow. Existing solutions like PLAID attempt to solve this using a "centroid interaction matrix," but this creates a new bottleneck: you either have too few clusters (hurting accuracy) or too many (making the matrix calculation too slow). Furthermore, these methods often require expensive GPUs to perform the initial clustering of hundreds of millions of vectors.
Methods
SIMQ bridges the gap between traditional single-vector graph indices and complex multi-vector retrieval through three main innovations:
- Data-Aware Sampling-Based Partitioning: Instead of running iterative $k$-means clustering (which is slow on CPUs), SIMQ uses a strategy derived from Point Aggregation Graphs. It samples initial centroids directly from the data and uses graph-guided assignment to form clusters. Oversized clusters are split locally, ensuring the process remains "data-aware" (adapting to the actual distribution of vectors) without the heavy compute cost.
- Per-Token Graph Navigation: Rather than building a massive matrix of all query-centroid interactions, SIMQ builds a single graph index (like HNSW) over the centroids. At query time, each query token independently navigates this graph to find its most relevant clusters. This bypasses the interaction matrix bottleneck entirely.
- SIMQ+ Enhancements: The authors introduced an upgraded version, SIMQ+, which uses count-based scoring. Instead of relying on precise inner-product values—which can be noisy in fine-grained clusters—it ranks documents based on how many distinct query tokens "hit" them. It also uses a dynamic candidate set to prevent arbitrary document truncation at the scoring boundary.
Datasets
The authors evaluated SIMQ on five diverse benchmarks from the BEIR and ColBERTv2 suites:
- Quora: Duplicate question retrieval.
- SciDocs: Scientific paper retrieval.
- NQ (Natural Questions): Large-scale Wikipedia-based QA.
- HotpotQA: Multi-hop reasoning across documents.
- LoTTE-pooled: An out-of-domain benchmark covering five different forum topics.
Key Insights and Ideas
- The "Interaction Matrix" is the Enemy: The primary contribution is the realization that we don't need to materialize the full query-centroid matrix. By treating centroids as searchable nodes in a graph, we can navigate directly to the "good" parts of the vector space.
- Data-Awareness Matters: The authors provide a theoretical proof that data-aware partitioning (like SIMQ’s) has a lower expected approximation error than data-oblivious methods (like Locality Sensitive Hashing used in MUVERA). LSH often mixes semantically distinct tokens into the same bucket, whereas SIMQ keeps them coherent.
- Simplicity Scales: By avoiding GPU-dependent $k$-means, SIMQ makes it possible to build and run high-quality multi-vector indices on standard commodity CPU hardware.
Key Results
SIMQ consistently outperformed state-of-the-art baselines like PLAID, MUVERA, and IGP across all datasets in terms of the trade-off between throughput (Queries Per Second) and Recall.
- Speed: On the Quora dataset, SIMQ's index construction took only 68 seconds on a CPU, compared to over 4,200 seconds for PLAID.
- Efficiency: As shown in the Pareto frontiers below, SIMQ (red lines) maintains higher QPS even as recall requirements increase, effectively shifting the performance curve upward and to the right.
- Robustness: SIMQ+ proved particularly effective at handling "ranking reversals"—cases where a relevant document might be underestimated by a single proxy centroid but is correctly identified when looking at the aggregate "hits" across all query tokens.
Limitations and Future Work
While SIMQ significantly reduces the computational bottleneck, the paper notes that multi-vector models still require substantial storage space to keep all token-level embeddings (or their compressed residuals). While SIMQ is integrated into the VSAG library, future work could explore tighter integration with advanced compression techniques to reduce the memory footprint further without sacrificing the speed gains achieved by the graph-based navigation.
Summary updated