Source-linked AI summary
misi: a Metric Inverted Sample Index
Edgar Chavez
TL;DR
Approximate nearest-neighbor indexes must balance recall and query speed against construction cost, determinism, and memory constraints. misi addresses this with a linear-size sampled vocabulary, weighted shared-neighbor voting, and exact verification, achieving strong structural and deployment properties while remaining slower at query time and limited by unmeasured components.
Problem
The paper examines how to scale NAPP’s fixed reference vocabulary with database size while preserving usable posting lists and supporting metric spaces and constrained deployments.
Method
misi samples m = αn database points, builds a pluggable high-recall inner index, represents objects by kb nearest sample points, and retrieves candidates through idf-weighted voting followed by exact verification.
Results
misi constructs deterministically 3.7× faster than the strongest matched-recall graph build, streams under 3 GiB, and serves within 8 GB where the SSD-graph baseline does not run.
Takeaways & Limitations
The design suits frequently rebuilt corpora, batch similarity workloads, constrained-memory serving, and black-box metrics when construction and footprint outweigh peak throughput.
Takeaways & Limitations
The update path is unimplemented and unbenchmarked, non-vector metrics are unevaluated, and the paper lacks a controlled SPANN comparison.
Abstract
from arXiv · showhide
We present misi, an inverted index for approximate nearest-neighbor search over general metric spaces whose vocabulary is a random sample of the database, of size proportional to $n$. Each object is represented by its $k_b$ nearest sample points, found by a pluggable inner index over the sample; queries are answered by an idf-weighted shared-neighbor vote followed by exact verification of $C$ candidates. The construction generalizes the NAPP index from a constant number of pivots to a linear-size vocabulary, which keeps posting lists at constant expected length $ρ= k_b/α$ as $n$ grows and turns the index into a combinator: any high-recall index on $αn$ points yields an index on $n$ points, for any metric. A probabilistic model gives a recall guarantee -- $k_b$ logarithmic in $n$ over the overlap gap suffices, with a verification budget the index itself estimates -- and a matching limit: the vote cannot resolve overlap differences below order $1/\sqrt{k_b}$. The design's strengths are structural: construction is $n$ independent searches -- embarrassingly parallel, deterministic, $5{,}250$ s for $10^8$ vectors on 64 cores, $3.7\times$ faster than a matched-recall graph build -- it streams under an enforced 3 GiB cap, and the portable artifact serves $10^8$ vectors from NVMe within an enforced 8 GB budget, below the working floor of the SSD-graph baseline. Its cost is query-time work: saturated graph baselines answer $6$-$16\times$ faster in RAM, and the verification budget for 0.99 recall grows as $n^{0.30}$. All results carry seeds, saturation sweeps and full configurations, are generated from run manifests, and include measured negative results. The intended applications weight construction cost, determinism, memory footprint, or black-box metrics over peak throughput: frequently rebuilt corpora, batch similarity workloads, constrained-memory serving.
1 Introduction
misi replaces NAPP’s fixed reference vocabulary with a linear-size random database sample, yielding constant expected posting-list length and a composable metric index. Its measured advantages are deterministic, memory-conscious construction and portable serving, traded against slower query throughput and unmeasured extensions.
- Contribution: misi uses a sample of size m = αn as its vocabulary, turning any high-recall index on αn points into an index on n points for any metric.The core consumes only neighbor identities, so reference search is delegated to a pluggable inner index.
- Contribution: At fixed dials, mean posting-list length is ρ = kb/α rather than growing linearly with the database.The linear vocabulary is the structural reason list lengths remain constant as n grows.
- Trade-offs: 6–16× slower matched-recall query throughput than saturated graph baselines is misi’s principal measured cost in RAM.Each query streams postings through an accumulator and verifies candidates exactly.
- Measured results: Coverage-driven vocabulary resampling gains 0.037 recall at C=500 on SIFT, but the gain shrinks with C and reverses on GloVe at large C.The paper reports the conditions under which this heuristic helps or hurts.
- Measured properties: 3.7× faster construction than the strongest matched-recall graph build accompanies deterministic parallelism, streaming under 3 GiB, and serving within 8 GB where the SSD-graph baseline does not run.The reported systems properties target construction cost, memory footprint, and artifact portability rather than peak query throughput.
- Limitations: Unmeasured future work includes resident product-quantization screening and recursive construction using the same method for the inner index.These compositions are motivated by the analysis but are not evaluated.
2 Related work
misi extends reference-based inverted indexing by scaling the vocabulary with the database and replacing simple shared-reference counts with weighted voting and budgeted verification. It differs architecturally from graph, partitioned-inverted, and shared-neighbor approaches while leaving controlled SPANN comparison as an important gap.
- Reference-based indexing: NAPP, misi’s direct ancestor, stores each object’s K nearest pivots from a fixed vocabulary and retrieves candidates by shared-pivot count before verification.misi changes the vocabulary scale, pivot search, and candidate rule.
- Reference-based indexing: misi uses a Θ(n) vocabulary, a pluggable ANN pivot search, and an idf-weighted vote with verification budget C instead of NAPP’s constant vocabulary, exhaustive search, and threshold count.The comparison identifies the three principal architectural changes from NAPP.
- Graph indexes: Graph indexes such as HNSW, DiskANN, and GRAFT provide baseline or inner-index functionality, with graph construction described as deterministic and embarrassingly parallel.Navigable graphs also natively support incremental insertion, unlike misi’s unmeasured update path.
- Partitioned inverted designs: SPANN is the closest architectural system, but misi samples data points instead of clustering, uses kb = 64 assignments instead of ≤8, and applies idf-weighted voting instead of union-and-rerank.The paper identifies a controlled SPANN comparison as its most important missing experiment.
- Shared neighbors: misi uses shared-nearest-neighbor similarity as the retrieval signal itself and connects its merge problem to approximate string-join methods.This distinguishes retrieval use from the clustering origins of shared-neighbor similarity.
3 The index
misi builds signatures from each object’s nearest points in a frozen sample, inverts those signatures into rank-sorted postings, and answers queries by weighted voting followed by exact verification. Its constant expected list length and memory-mapped serving design are balanced by an update path that remains designed but unmeasured.
- Construction: misi samples S ⊆ D with |S| = m = αn, builds a high-recall inner index over S, and freezes it for signature construction.Each object is searched for its kb nearest sample points, whose identities and build ranks form its signature.
- Construction: Each posting list contains objects sharing a sample point, is sorted by rank and id, and has mean length exactly ρ = kb/α independent of n.There are kbn postings distributed across αn lists.
- Query: Queries search the inner index for ks sample points, merge their postings with an idf-weighted shared-neighbor score, and exactly verify the top C candidates.ks controls lists read, while C controls true-distance evaluations.
- Residency: Serving keeps sample vectors, the inner index, and offsets in RAM while memory-mapping postings and database vectors from disk.The merge uses an O(ksρ)-transient accumulator rather than a dense scoreboard.
- Updates: Updates are only a design claim: insertion requires one inner search and kb posting appends, while deletion uses exact removal through the forward file.The rank-sorted layout conflicts with cheap appends, so updates are neither implemented nor benchmarked.
4 A model of the vote
The model treats misi’s shared-neighbor vote as a metric-free estimator whose confidence depends on k_b and whose resolution depends on the overlap gap. It proves a vote-then-verify guarantee, identifies an order-1/√k_b resolution limit, and scopes empirical refinement results to tested methods and datasets.
- Model and guarantee: misi uses resolution ρ = k_b/α and confidence k_b, ranking candidates by shared-neighbor vote before exact verification.The analysis conditions on neighborhood sets, so the geometry may be arbitrary; only the random sample is probabilistic.
- Model and guarantee: k_b = O(log(k n/δ)/∆^2) separates candidates whose overlaps differ by ∆, under the vote-separation model.Bernstein’s inequality bounds the probability that the lower-overlap candidate outranks the higher-overlap candidate.
- Model and guarantee: The sampled intersection X/k_b is an unbiased estimator of neighborhood overlap ω, making the index’s query difficulty observable.This supports estimating the confusable-set size that determines verification work.
- Model and guarantee: With true neighbors above threshold ω− + ∆, verifying C = |K(q, ω−)| + k candidates returns the exact k nearest neighbors with probability at least 1 − δ.The budget covers the confusable set plus the target neighbors, and its size varies by query.
- Resolution limit: Under generic overlap, the vote cannot reliably resolve an overlap advantage of order 1/√k_b, so the raw vote resolves gaps above Θ(1/√k_b) but not below.The expected rank of the true neighbor inside this unresolved band can force verification to cover a constant fraction of the band.
- Scope of evidence: The empirical claim that no tested query-time refinement improves vote-then-verify is limited to statistical re-weighting, implicit-graph navigation, and triangle-inequality bounds on SIFT, GloVe, and Deep.Learned re-ranking and distance estimation remain untested, while the proved barrier concerns the vote itself.
5 What query-time processing does not add
Five query-time refinement families did not improve the static (ks, C) recall/cost frontier on the evaluated datasets. Navigation contributed marginally, while geometric bounds and adaptive stopping were ineffective or costly under the tested conditions.
- Five query-time refinement families failed to improve the static (ks, C) recall/cost frontier on SIFT1M, GloVe-200, and Deep prefixes.The tested scope excludes learned re-ranking and distance estimation from personal pivots.
- Navigation: 5.1% of final top-10 entries on GloVe came from best-first expansion, but 1 candidate in 102 was unreachable through merge ranking and equal-cost recall did not improve.The implicit graph is real but its measured contribution was marginal.
- Geometric bounds: 0–3% of verifications were pruned by quantized-distance triangle bounds, while vote-ordered verification reached 0.98 recall versus 0.47 for upper-bound ordering on SIFT at equal budget.The one-byte personal-radius variant pruned 0.8% on SIFT and 0.06% on GloVe.
- Adaptive stopping: Every simulated adaptive-stopping variant landed on or below the static (ks, C) frontier, although an oracle stop showed 1.8–2.2× headroom.A calibrated sequential test on the vote gap remains untested.
- Evidence placement: At equal postings read, native truncation dominated random posting subsampling: thinned-32 lost to native-16 while reading twice the postings.The native dial keeps the nearest evidence rather than thinning across the full radius.
6 Vocabulary selection
Vocabulary re-sampling changes posting-list imbalance without changing mean list length. Seeded measurements show that coverage re-sampling helps when verification is constrained, but can become neutral or harmful when the budget is generous.
- Re-sampling changes the posting-list distribution on hub-heavy data, while the mean list length ρ remains fixed.The heuristic retires heavily loaded samples and promotes members of idle lists.
- Seeded evaluation: +0.037 recall at C=500 on SIFT exceeded seed noise of ±0.002 across five sample seeds.The gain decayed to nothing at C=20,000.
- Seeded evaluation: About −0.004 recall at C=50,000 on GloVe shows that the re-sampling effect can reverse at large verification budgets.At small C, the GloVe gain was under two points.
- Interpretation: Coverage re-sampling helps when verification budget is binding, is neutral-to-harmful when the budget is generous, and costs two extra builds.Single-run measurements overstate the effect because seeds reveal the sign reversal.
7 The merge
The merge is the principal query-time cost: candidates from selected posting lists are accumulated with idf-weighted shared-neighbor scores, and exact top-C verification follows. Uniform rank-major lists require reading every posting in the selected lists, while batching can reduce posting-read traffic per query.
- The merge scores candidates from ks posting lists using a dense per-thread scoreboard or an O(ksρ) radix-partitioned accumulator.Five implementations read the same posting volume within constant factors; locality differentiates them.
- Read cost: Exact top-C merging must read every posting in selected rank-major, id-unordered lists with uniform weights; skipping cannot be certified from the available evidence.Skipping algorithms remain applicable in principle to id-sorted layouts.
- Accounting: W = h ksρ postings are streamed per query, with h = 1.72–1.75 measured on SIFT across α = 1–4%.At fixed dials, W is independent of n; halving residency doubles the stream.
- Batching: For batches of B queries, posting-read traffic per query falls as kbn/B beyond B∗ because the posting matrix can be streamed once and accumulated as a tiled sparse product.The conserved quantity is operations rather than bytes, and implementation measurement is future work.
- Query cost: 75–93% of query time is the accumulate loop, while list selection takes ≤4% and verification is bounded by C.The accumulate loop is compute-bound through 10^7 and cache-bound at 10^8 on the measured 4-socket machine.
8 Experiments
Experiments compare misi with NAPP and graph baselines across recall, scale, saturation, memory, construction, portability, streaming, and metric robustness. misi’s structural advantages are clearest in construction and constrained serving, while graph indexes retain substantial in-RAM throughput advantages.
- One million objects: At 0.99 recall on SIFT1M, hnswlib reaches 15,751 QPS versus misi’s 2,637 QPS, while their saturated ceilings match.On GloVe, the systems interleave, and NAPP reaches 0.9917 recall at low QPS.
- One million objects: misi improves on NAPP by about 2.2× at matched recall on SIFT, although the advantage is modest at this scale.The experiments describe the linear vocabulary’s main advantage as asymptotic rather than constant-factor.
- Scaling: C0.99 ∝ n^0.30 over nested Deep prefixes from 10^6 to 10^8, while the verified fraction falls by approximately 5× per decade.At fixed resolution, the reported model account is that the confusable count grows with n.
- Saturated ceilings: At 10^8, GRAFT, HNSW, and DiskANN reach 0.9992, 0.9989, and 0.9984 maximum recall, versus misi’s 0.9967.All four converge within half a point of exact at low throughput under saturation sweeps.
- Memory-limited serving: Within an enforced 8 GB budget, misi serves 10^8 vectors at 8–30 QPS, whereas DiskANN does not run at 8 GB and reaches 1,983 QPS at 12 GB.misi’s measured serving floor is 4–8 GB because the inner index is rebuilt over the 2·10^6-point sample at load time.
- Construction, portability, streaming: misi builds 10^8 vectors in 5,250 s versus 19,675 s for a matched-recall graph configuration, and its Deep-10M artifact transfers across machines.The Deep-10M artifact loaded in 15.7 s and served at 862 QPS at 0.9911 recall; streaming under 3 GiB completed in 462 s with an 8% penalty.
- Metric robustness: Under adversarial MIPS, global hubs produce posting skew 535 and recall 0.28, while the Neyshabur–Srebro reduction restores 0.9907 recall with skew 37.Direct dot-product indexing on Deep-5M otherwise reaches 0.9930 recall@10.
9 Position
The paper positions misi as an architectural alternative whose value lies in construction, residency, determinism, and portability rather than peak query throughput or recall ceilings. Its comparison depends on deployment constraints and explicitly measured resource boundaries.
- Deployment position: The intended position favors frequently rebuilt corpora, batch similarity workloads, and constrained-memory serving over peak throughput.The comparison treats construction cost, residency, updates, and portability as decision-relevant axes.
- Against its ancestor: misi removes NAPP’s scale walls by using a linear vocabulary, yielding mean posting length ρ = 3,200 instead of NAPP’s 10^5 at 10^8.NAPP with 32,000 pivots would require 3.2·10^12 brute-force pivot distances at build.
- Against in-RAM graphs: Against in-RAM graphs, misi loses matched-recall throughput by 6–16× at 10^6 and has no measured recall-ceiling advantage.It instead wins on construction time, determinism, and artifact portability.
- Against the SSD graph: Against the SSD graph, misi serves in a measured 4–8 GB window where DiskANN cannot, but loses throughput by two orders of magnitude at DiskANN’s native budget.The paper identifies verification I/O—C ≈ 10^4 versus approximately 10^2 reads per query—as the central gap and leaves a resident PQ screen unimplemented.
10 Limitations and future work
The paper identifies open limitations in updates, metric coverage, comparisons, reproducibility scope, memory residency, and query-time optimization. Several proposed improvements remain designs or untested directions rather than demonstrated results.
- Scope and evaluation: The update path is designed but not implemented, non-vector metrics are unevaluated, the SPANN comparison is absent, and all 10^8 misi rows use a single seed.These boundaries restrict how broadly the current measurements can be interpreted.
- Memory and scale: The current 4–8 GB serving floor is caused by rebuilding the inner index at load time, and at 10^12 the sample itself outgrows RAM.Recursive construction is proposed as the design’s answer, conditional on inner-index recall and future implementation choices.
- Future work: A resident PQ verification screen, calibrated stopping, skipping, learned within-list methods, tiled batching, and bandwidth-rich substrates remain open work.The paper identifies the PQ screen as the change most likely to alter memory-limited serving, while several other directions lack mapped recall costs.
- Future work: Coverage re-sampling needs a selection principle, and its measured benefit can reverse sign across datasets and verification budgets.The paper frames the per-query confusable count as a natural target for calibrated stopping.