arXiv · Oct 1, 2026
SOLO: Certified-Recall Metric Similarity Search with Scan-Only Sampled Inverted Lists
By Édgar Chávez
In every fast nearest-neighbor index, recall is measured, never predicted: each operating point is tuned by serving it against ground truth. SOLO is an index whose recall is computed from the index itself, before any query is served. SOLO is an inverted file whose vocabulary is a random sample of the database. Each object's k_b nearest sample points are stored once, ranked; at serve time an object is posted under the first b ≤ k_b of them, and a query scans the lists of its k_s nearest sample points exhaustively, with the true distance. Recall depends on the product b · k_s (an equal-work law), so the search-side k_s compensates for a small b with no rebuild. There is no beam, vote or pruning bound, so a true neighbor is missed only if it shares no sample point with the query – a membership event decided by stored integers, not by a search. Recall is therefore a count: one ground-truth pass over a sample of the operator's queries certifies every (b, k_s) at once, with nothing served. The certificate matches served recall to four decimals from 10⁶ to 10⁹ objects, including 768-dimensional text embeddings under inner product with shifted queries. No graph index has an analogous object. The rest is the same rule applied recursively: a list that outgrows a bound is sampled and split like the database, and so is the vocabulary itself, which is what drives resident memory down. Deep-100M is served at recall 0.9977 from 1 GB of enforced resident memory, Deep-1B at 0.9925 from 96 MB. Inserts are one search, deletes are exact, and throughput reaches 1.8× a tuned HNSW at 10⁸. Every number is reported against HNSW, DiskANN, GRAFT, NAPP, misi, SPANN, ScaNN and RaBitQ on the same hardware and ground truth.