SIMQ: A Single Graph-based Index for Multi-Vector Query

Yifan Lu, Jiabao Jin, Xiaoyao Zhong, Peng Cheng, Xiangyu Wang, Haotian Li, Hua Chen, Junqing Chen, Wei Xi, Heng Tao ShenarXiv 2026 · arXiv

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:

  1. 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.
  2. 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.
  3. 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.
The SIMQ framework pipeline: from sampling centroids to per-token graph navigation and final reranking.

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.
QPS vs. Recall Pareto frontiers across five datasets. SIMQ and SIMQ+ consistently outperform baselines.

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

Abstract

Multi-vector retrieval models such as ColBERT achieve state-of-the-art effectiveness by representing documents as sets of token-level vectors and scoring via MaxSim, but their high computational cost limits scalability to large corpora. Existing approximate methods face fundamental bottlenecks: centroid interaction matrix approaches require computing a full matrix at every query and rely on GPU-accelerated clustering, while data-oblivious compression methods yield unstable recall that requires repeated compensation. We propose SIMQ (Single graph Index for Multi-vector Query), a framework that bridges single-vector graph indices and multi-vector retrieval through data-aware sampling-based clustering and per-token graph navigation, simultaneously bypassing all aforementioned bottlenecks. SIMQ organizes all token vectors into fine-grained clusters via data-aware sampling, builds a single graph index over cluster centroids independently of PLAID's residual representation, and approximates the MaxSim score through per-token graph search without materializing any interaction matrix or relying on GPU acceleration. We provide theoretical analysis showing that, under a manifold assumption and successful cell retrieval, data-aware partitioning has a smaller expected approximation error than a data-oblivious partition. Building on this foundation, SIMQ+ further introduces count-based scoring and a dynamic candidate set to improve robustness across varying query conditions. Experiments on five benchmarks compare recall, throughput, and construction time against several baselines, primarily on CPU; large-scale PLAID k-means centroids are built on a separate GPU machine. SIMQ has been integrated into VSAG, an Ant Group's open-source vector search library.
BibTeX
@misc{lu2026simq,
  author = {Yifan Lu and Jiabao Jin and Xiaoyao Zhong and Peng Cheng and Xiangyu Wang and Haotian Li and Hua Chen and Junqing Chen and Wei Xi and Heng Tao Shen},
  title = {{SIMQ: A Single Graph-based Index for Multi-Vector Query}},
  year = {2026},
  eprint = {2611.22079},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22079},
}
Figure