Research map / Learning theory and algorithms / Clustering
Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Optimist, a router for clustering-based maximum inner product search that scores each shard by an optimistic upper estimate of its max inner product, built from the first two moments (with a rank-t masked covariance sketch).
Problem
Routing (selecting which shards to probe) in clustering-based approximate maximum inner product search has received little attention; existing routers like mean or normalized mean are ad hoc and mis-estimate shard maxima, especially when vector norms vary.
Approach
Apply the optimism-in-the-face-of-uncertainty principle to routing: score each shard by a one-sided Chebyshev upper bound on its inner-product quantile, mean plus a variance term, and sketch the covariance with a masked rank-t approximation so the router stores only t+2 vectors per shard.
Key results
- On Music, Optimist reaches 95% top-100 recall probing 6,666 points versus 14,463 for NormalizedMean (54% fewer).
- Optimist probes up to 50% fewer points than state-of-the-art routers at the same recall on benchmark datasets, with savings of 22% on Text2Image and 5.5% on GloVe at 95% recall.
- On DeepImage, Optimist probes about 10% more points than NormalizedMean at 95% recall, which the authors attribute to dataset construction.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Optimist routing instead of NormalizedMean | Clustering-based MIPS · Text2Image, 95% recall | relative points probed: -22% | Helped |
| Use Optimist routing instead of NormalizedMean | Clustering-based MIPS · Music, 95% recall | relative points probed: -54% | Helped |
| Use Optimist routing instead of NormalizedMean | Clustering-based MIPS · DeepImage, 95% recall | relative points probed: +10% | Hurt |
| Use Optimist routing instead of NormalizedMean | Clustering-based MIPS · GloVe, 95% recall | relative points probed: -5.5% | Helped |
| Use Optimist routing instead of NormalizedMean | Clustering-based MIPS · MsMarco-MiniLM, 95% recall | relative points probed: -7.7% | Helped |
| Use Optimist routing instead of NormalizedMean | Clustering-based MIPS · Nq-Ada2, 95% recall | relative points probed: -20% | Helped |
| Use a rank-t Masked Sketch instead of the full covariance matrix (ablation) | Optimist · ANN benchmark datasets, larger k | recall | Hurt |
Surprising findings
- On DeepImage, the proposed router scans more points than the NormalizedMean baseline.
- The normalized-mean router's advantage over the plain mean router is explained by variance-dependent over-estimation of inner products.
Limitations
- Chebyshev-based bound is loose and assumption-free; the gap to the optimal threshold is not characterized.
- Router requires more compute and storage than the mean router (t+2 vectors per shard vs one), e.g., 300 MB vs 9.4 MB on Nq-Ada2.
- Latency gains depend on hardware and storage type; benefits shrink with abundant bandwidth.
Experimental setup
Datasets: Text2Image Music DeepImage GloVe MsMarco-MiniLM Nq-Ada2
Benchmarks: Text2Image Music DeepImage GloVe MsMarco-MiniLM Nq-Ada2
Metrics: top-100 recall vs number of points probed latency (ms) router size (MB) prediction error E_l
Baselines: Mean router NormalizedMean router ScaNN router SubPartition (kRt)
Builds on: spherical KMeans ScaNN Eckart-Young-Mirsky low-rank approximation kRt
Closest papers by meaning
- Sort Before You Prune: Improved Worst-Case Guarantees of the DiskANN Family of Graphs (ICML 2025 · similarity 0.86)
- Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search (ICML 2024 · similarity 0.86)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.86)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.85)
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.85)
- Query-Efficient Correlation Clustering with Noisy Oracle (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.