PaperlayerView exact revision on arXiv

Source-linked AI summary

SOLO: Certified-Recall Metric Similarity Search with Scan-Only Sampled Inverted Lists

Édgar Chávez

arXiv:2610.02387v2cs.DBcs.IR

TL;DR

Fast nearest-neighbor indexes typically measure recall by serving each operating point against ground truth, while SOLO computes recall from stored signatures before serving. Its scan-only inverted file certifies the operating surface, and the certificate matches served recall to four decimals across 10^6 to 10^9 objects.

  • Problem

    Fast nearest-neighbor indexes measure recall only after serving against ground truth, one operating point at a time.

    Source: §1 · p. 2

  • Method

    SOLO stores ranked signatures over a random sample and uses scan-only list intersections to compute recall coverage for operating points before serving.

    Source: §2 · p. 3, §2.1 · p. 5, §2.2 · p. 8

  • Results

    Four-decimal certificate agreement holds from 10^6 to 10^9 objects, including the corpus where SOLO performs worst.

    Source: §10 · p. 30

  • Takeaways & Limitations

    At scale, the paper argues that a better bill of what must be examined may be a more useful primitive than a better navigator.

    Source: §10 · p. 30

    The paper does not measure filtered-search outcomes or compare them with filtered-DiskANN and ACORN, especially at selectivities of 10^-2 and below.

    Source: §9.1 · p. 29

Abstract

from arXiv · show

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 \le 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 \cdot 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^6$ to $10^9$ 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\times$ a tuned HNSW at $10^8$. Every number is reported against HNSW, DiskANN, GRAFT, NAPP, misi, SPANN, ScaNN and RaBitQ on the same hardware and ground truth.

1 Introduction

SOLO replaces post-hoc recall tuning with an inverted-file design whose stored ranked signatures make recall certifiable before serving. Its introduction presents equal-work tuning and recursive splitting as routes to bounded lists and lower resident memory.

1 Introduction

  • Graph recall is known only after serving against ground truth, and exhaustively tuned HNSW on Deep-100M stops at recall@10 0.9989 at ef=4000.DiskANN needs 12 GB for Deep-100M on the reported hardware and fails below 9.6 GB.Source: §1 · p. 2
  • The certificate matches served recall to four decimals from 10^6 to 10^9 objects, with a per-query provision fitted on seven corpora and thirteen query sets.One ground-truth pass certifies every operating point before any is served.Source: §1 · pp. 2–3
  • 0.9925 recall from 96 MB at depth 3 for Deep-1B, while Deep-100M reaches 0.9977 recall from 1 GB; inserts are one search and deletes are exact.The in-RAM comparison reaches 1.8× a tuned HNSW at 10^8 objects.Source: §1 · p. 2
  • Coverage depends mainly on touched posting mass b · ks rather than its factorization, so ks can compensate for smaller b without rebuilding.At fixed recall, evaluations grow as n^0.4–0.6 over four measured decades.Source: §1 · p. 3
  • Recursive sampling and splitting bounds oversized lists without clustering; against per-list graphs, it wins on recall and throughput with a 25× cheaper build.The comparison is an ablation attaching a small graph index to each oversized list.Source: §1 · p. 3
  • The paper does not claim efficiency per gigabyte against DiskANN, filtered-search performance, or generalize its throughput comparison beyond one machine.The representation was introduced by misi [6], which served it by voting; SOLO keeps the representation and replaces the serving theory.Source: §1 · p. 3

2 The SOLO index

This section presents SOLO’s sampled-vocabulary inverted index, covering ranked assignments, scan-based serving, and pre-serving recall computation from query–neighbor term overlap. It also describes ranked codes’ uses and limits, exact updates, and sequential layouts for memory- and disk-capped search.

2.1 Vocabulary and assignment

  • A uniform 2% sample forms the vocabulary; each object stores a ranked signature of its 64 nearest sample points, and truncating it at serve time selects replication b.One build serves every b, and construction uses independent searches without iterative refinement.Source: §2.1 · p. 5

2.2 Scan-only serving and the recall identity

  • SOLO recall@k equals the fraction of true query-neighbor pairs whose query-routed and neighbor-posted term sets intersect, up to ties at rank k.A true neighbor is returned if and only if the sets intersect: every candidate is evaluated with the true distance and the top-k selection over candidates is exact.Source: §2.2 · p. 6
  • The certificate estimates expected served recall for the sampled workload, not a bound; another workload requires its own certification pass.One brute-force ground-truth pass supports prefix-intersection calculations across the operating surface, and the certificate’s uncertainty is measured by clustered bootstrap over queries.Source: §2.2 · pp. 7–8
  • At 10^8, the stored-signature certificate matched served recall to 0.0001 at all six MS MARCO operating points, including a best served recall of 0.8987.The queries were 768-dimensional text embeddings under inner product, drawn from a different distribution than the passages.Source: §2.2 · p. 9

2.3 One rule: recursive decomposition

  • Inside oversized GloVe lists, local coverage was 0.9969 at (b′=8, k′s=32) and 0.9994 at k′s=64; the depth-2 index matched its composed prediction to 2 × 10^-4.Lists above a bound are sampled and decomposed by the same rule, while leaves are scanned in full.Source: §2.3 · p. 9

2.4 Quantized leaves

  • Across three datasets from 10^6 to 10^8, SQ8 with R=40 reproduced full-precision results exactly; SQ4 needed R=200 on GloVe, while SIFT was unchanged at R=100.The screen keeps distinct candidates and re-ranks them at full precision; quantization accelerates verification rather than defining the final score.Source: §2.4 · p. 9
  • On Deep-100M, SPANN scored with the same Int8 grid reached 0.9561, four points below its own float build, while using the grid as a screen with exact refinement was lossless.The comparison used float ground truth and the same machine; the passage concludes that quantization must screen, not score.Source: §2.4 · p. 10

2.5 Serving kernels and the memory model

  • A touched-clearing per-thread bitmap costs 12.5 MB and is faster than epoch-stamped visited arrays, while list-major code streams avoid random gathers during scanning.At 10^6 objects, streaming costs about 1.7 ns per record on one core versus 9–25 ns per gathered record; deduplication before the R-heap prevents recall loss from duplicate candidates. A tapered frontier achieves 0.9991 recall from 54% of the records of the (16, 128) rectangle on SIFT-1M.Source: §2.5 · p. 10
  • The mmap-able router loads in 43–90 µs at every measured scale, versus seconds to minutes for reconstruction, with bitwise-identical search.Under a memory cap, the mapped router is file-backed and reclaimable, unlike a rebuilt anonymous-memory router.Source: §2.5 · p. 10
  • At (b, ks) = (16, 256), disk-mode search reads 37 MB sequentially and 0.4 MB randomly per query using posting-ordered leaf blocks and bounded per-thread buffers.The same passage reports that mmap-faulting vector reads under a 4 GB cap causes about 85× amplification.Source: §2.5 · p. 10

2.6 The codes as a proximity sketch

  • At b=64, mean code overlap falls from 38.8 shared terms at neighbor rank 1 to 23.4 at rank 100 and 16.3 at rank 1000, versus a 0.35 random-pair floor.The overlap is monotone across three decades of rank; at b=16, a ≥1-shared-term test captures 95% of rank-100 pairs at a 1.8% false-pair rate.Source: §2.6 · p. 10
  • Code overlap supports disk-regime result-set operations, similarity self-joins, and standing queries, but encoding a fresh query still requires a search.For standing queries, arriving objects’ codes are computed during their inserts; code comparison cannot accelerate the search that produces a fresh query’s encoding.Source: §2.6 · pp. 10–11

2.7 Updates and determinism

  • Inserts require one router search and b list appends, while deletes remove entries exactly without tombstones, graph repair, or rebalancing.Builds and queries are bitwise deterministic for a fixed seed across thread counts, and recall is machine-independent.Source: §2.7 · p. 11

3 Measured laws

Across datasets and scales, SOLO’s measured behavior follows three regularities: coverage tracks touched posting mass, fixed-recall work grows sublinearly, and replicated appearances make downstream losses more forgiving. These measurements also show that assignment rank outperforms distance-ratio closure.

3 Measured laws

  • Coverage depends on touched posting mass, fixed-recall work grows sublinearly with database size, and covered neighbors often appear in multiple touched lists.The multiple appearances make each lossy step downstream of routing forgiving.Source: §3 · p. 11

3.1 The equal-work law and the regime spectrum

  • At about 140k scanned candidates, four GloVe factorizations cover 0.9126–0.9332; SIFT reaches 0.99 coverage near b · ks = 512, while GloVe needs at least 8k.Figure 3 shows each dataset’s measured pairs following one curve, so the factorization is free within a contour.Source: §3.1 · p. 11, Figure 3 · p. 12

3.2 Scale

  • At target recall 0.998, interpolated work rises from 30,603 to 696,138 evaluations across 10^6–10^9 objects (exponents 0.40, 0.39, 0.57), while scanned fraction falls from 3.060% to 0.070%.The 10^9 point at recall 0.998 is certified; served points there reach recall 0.9925.Source: §3.2 · p. 11

3.3 Replication is insurance

  • Among covered GloVe neighbors at ks=64, the median number of touched lists containing a neighbor is about 13, while only 2.5% appear in one list.A neighbor is lost only if all its appearances are missed; the same replication structure recurs inside decomposed lists.Source: §3.3 · p. 12

3.4 Choosing the assignment rule

  • At equal mean replication, rank-b assignment covers more than distance-ratio closure on both SIFT and GloVe.At ks=128, SIFT coverage is 0.9996 for rank-8 versus 0.9960 for closure; at GloVe, it is 0.9902 for rank-32 versus 0.9788 for closure.Source: §3.4 · p. 12

4 The certificate out of sample

The certificate measures expected recall on its calibration query distribution, while queries from a shifted distribution need a per-query provision. SOLO uses routed-distance order statistics to stratify query hardness and estimate coverage, but cross-modal shifts can fall outside that calibration’s scope.

4 The certificate out of sample

  • The certificate is an expectation for its calibration query distribution, so production query drift calls for a per-query provision.The provision uses routed distances as an unbiased probe of the query’s neighborhood and estimates local intrinsic dimension as a query-hardness statistic.Source: §4 · pp. 12–13
  • On shifted text-embedding queries, the provision predicts recall to within 0.0009 at (b, ks) = (8, 64), versus 0.0033 error for the unconditioned certificate.Choosing ks per query meets the 0.99 target on shifted queries with 26–34% fewer misses than a fixed ks at the same posting mass.Source: §4 · p. 13
  • Across corpora, coverage-rate curves have corpus-specific offsets, and the cross-modal T2I text queries fall outside the image-query calibration for most of the set.The text queries exceed the image-query estimate’s 99th percentile for 86% of ℓ2 queries and 66% of inner-product queries; they are served uncertified.Source: §4 · p. 13, Figure 4 · p. 14

5 Evaluation

The evaluation reports operating points and enforced-memory serving under a same-machine, same-query, same-ground-truth protocol. Recursive routing lets depth 2 serve Deep-100M at 1 GB where the flat router collapses.

5 Evaluation

  • Comparisons use interleaved repetitions, medians, fixed seeds, and baselines swept to saturation against exact recall@10 ground truth.The evaluation spans SIFT-1M, GloVe-1.2M, Deep-10M, and Deep-100M; Deep-100M rows are single-seed.Source: §5 · pp. 14–15

5.1 Operating surface

  • Table 5’s measured SOLO operating points are monotone in recall and agree with the Proposition 1 certificate.Deep rows use SQ8 screening at R=100; their recalls are bit-identical to full-precision scans of the same configuration.Source: §5.1 · p. 15, Table 5 · p. 16

5.2 Serving Deep-100M at 1 GB resident, and below

  • At 1 GB, depth 2 serves Deep-100M at recall 0.9977 and 8.7 qps, where depth 1 collapses.The depth-2 route costs 18.4 ms per query; its resident footprint is 10.7 bytes per object. Table 6 reports the capped comparison.Source: §5.2 · p. 15, Table 6 · p. 17
  • At 512 MB and 8 threads, depth 2 serves 12.8 qps at recall 0.9964; at 256 MB and 2 threads, it serves recall 0.9977 at 2.9 qps.The memory floor below 1 GB shifts to per-thread scratch and buffers, rather than the router.Source: §5.2 · p. 16

5.3 The same cap, six other systems

The capped-memory comparison separates systems that fit within a resident-memory limit from those that stop, and also shows that a small index may still have a low recall ceiling or a severe throughput loss under tighter caps.

5.3 The same cap, six other systems

  • SPANN serves recall 0.9911 at 185 qps under an 8 GB cap, versus 186 qps uncapped, while several graph and cluster indexes stop below their memory floors.Table 8 compares systems under enforced cgroup caps, with OOM kills marked as such.Source: §5.3 · p. 18
  • At 1 GB, IVF-PQ runs at 4.5 qps and recall saturates at 0.8747; at 8 GB, the same configuration runs at 182 qps.The passage attributes its recall ceiling to PQ distances being the final score, and the throughput drop to random reads from probed lists.Source: §5.3 · p. 18
  • ScaNN’s codes-only form saturates at 0.4281, while re-ranking reaches 0.9937 at depth 5,000 but requires 32 GB to serve.The bfloat16 dataset copy accounts for 192 of its 244.2 bytes per object.Source: §5.3 · p. 18
  • RaBitQ saturates at 0.3450 with 1-bit codes and 0.8715 with 4-bit codes; exact-vector re-ranking reaches 0.9987 with 4-bit codes but runs at 48 GB.The re-ranked index materializes a flat copy on load.Source: §5.3 · p. 18

5.4 Comparison with prior indexes

The comparisons show that SOLO’s throughput depends on its serving kernel and that its matched-recall performance varies by corpus. On 768-dimensional MS MARCO, its best measured recall is 0.8987, while its certificate still matches served recall to four decimals.

5.4 Comparison with prior indexes

  • At hnswlib’s ceiling on SIFT-1M, SOLO serves recall 0.9992 at 8,836 qps against 0.9991 at 4,166 qps; on GloVe, it serves 0.9881 at 808 qps against 0.9863 at 268 qps.With four socket-local replicas, the matched-recall ratio on Deep-100M is 1.2–2.2×; recall is bit-identical between the two serving protocols.Source: §5.4 · pp. 18–19
  • DiskANN serves Deep-100M at recall 0.9984 and 568 qps from 12 GB, but does not run below 9.6 GB.The paper frames this as a capability comparison, not an efficiency-per-gigabyte claim.Source: §5.4 · p. 19
  • At matched recall, SOLO serves 2–4.6× SPANN’s throughput on Deep-10M and 5–7× on Deep-100M.SPANN reaches 0.9996 at 24 qps on Deep-100M, while SOLO serves 0.9988 at 320 qps against SPANN’s 0.9989 at 47 qps.Source: §5.4 · p. 19
  • At Deep-100M, the list-major 4-bit stream is 1.1–1.8× faster than hnswlib above recall 0.9974 and reaches 0.9990 beyond the graph’s ceiling.Figure 5 shows the in-RAM frontier; the gather-kernel version is slower than graphs wherever they operate.Source: §5.4 · p. 18, Figure 5 · p. 20, Table 9 · p. 21

5.5 MS MARCO Web Search at 108: where the architecture is weakest

  • The MS MARCO screen uses one grid step per coded dimension and carries the augmented coordinate as a per-record bias rather than coding it.With both corrections, recall is flat across R=100, 500, and 2000 and tracks coverage.Source: §5.5 · p. 20
  • On MS MARCO Web Search, SOLO’s best measured point is recall 0.8987 at 235 qps, while tuned graph indexes operate near 0.99.At b=16 and ks=256, coverage falls from 0.9539 to 0.8987 with scale, a 0.055 drop per decade, versus 0.0012 on Deep over the same step.Source: §5.5 · pp. 20–21, Table 10 · p. 22

5.6 Deep-1B: the surface certified before it is served, then served

At Deep-1B, the paper computes the operating surface from signatures before building and serving the stream, then recursively indexes the router to reduce resident state. The served depth-2 design reaches 0.9925 recall at 512 MB.

5.6 Deep-1B: the surface certified before it is served, then served

  • The billion-object operating surface was read from signatures before the stream was built and served.The setup uses a uniform 2% vocabulary and one signature per object; the signatures occupy 60 GiB at kb=16.Source: §5.6 · p. 22
  • The certificate shows recall 0.9960 at 19.3 MB of scan per query and 0.9986 at 37.5 MB; the 20-million-point GRAFT router’s coverage matches exact routing within 0.0002.The flat router requires 9,882 MiB, so the paper identifies depth 2 as necessary for a deployed billion-scale index.Source: §5.6 · p. 22
  • At 16 GB, depth 2 serves 30.15 qps against depth 1’s 25.44 qps; at 8 GB, it serves 63× depth 1’s throughput.The resident router falls from 9,882 to 189 MiB, and depth 2 serves 19.59 qps at 4 GB.Source: §5.6 · p. 23, Table 12 · p. 23
  • Deep-1B serves recall@10 0.9925 from a 512 MB cap at 8 threads and 6.93 qps.This is 0.54 resident bytes per object; the paper reports 10× fewer resident bytes per object than Deep-100M at the same cap and thread count.Source: §5.6 · p. 23
  • At 96 MB, depth 3 serves Deep-1B at recall 0.9925 and 1.6 qps; depth 2 is killed at 128 MB with 4 threads.At 16 GB, the third hop adds 4.2 MB of counted IO and returns coverage and recall unchanged to four decimals.Source: Table 12 · p. 23, §5.6 · p. 24
  • At 96 MB, the 8-bit depth-2 router serves recall 0.9925 at 1.9 qps, with a 78.9 MiB image versus 188.7 MiB for float.The paired router results retain identical coverage and recall to four decimals; 64 MB is killed at either depth.Source: §5.6 · p. 24, Table 13 · p. 24

5.7 Build and asset ledger

SOLO’s build and asset ledger separates construction costs from the data structures retained for serving. The accompanying table identifies a Deep-1B comparison of depth-2 and depth-3 routers against a same-day depth-2 float control.

5.7 Build and asset ledger

  • 5 s for SIFT-1M and about 5 minutes for Deep-10M are the reported build times; assignment for every b is then free.The builds use one router build plus n independent searches; Deep-10M uses 64 threads.Source: §5.7 · p. 24
  • At Deep-100M with b=16, postings occupy 6.4 GB, SQ8 codes 9.6 GB, optional disk leaf blocks 160 GB, and the router image 1.0 GB.The reported SQ8 coding and optional sequential leaf-block build take 158 s and 830 s, respectively.Source: §5.7 · p. 24
  • Table 14 compares a depth-2 router rebuilt over 8-bit points and a depth-3 router with a same-day depth-2 float control at matched cap, threads, and query count.The caption specifies Deep-1B stage 4, b=8, and ks=512; it does not provide the table’s outcome values.Source: Table 14 · p. 25
  • The listed serving setup uses s=128 and R=2000, with explicit pread at every level; rows with different thread or query counts are not compared.Coverage is computed on the served queries from stored signatures.Source: §5.7 · p. 25

5.8 Ablation: recursion vs. per-list graphs

The recursion-based design outperforms attaching small graph indexes to oversized lists at the matched GloVe operating points. Its throughput comparison at ks=64 has a session-related caveat, while recall comparisons are stable across reruns.

5.8 Ablation: recursion vs. per-list graphs

  • 0.9899 at 124 qps and 0.9978 at 52 qps are the recursion results, versus 0.9890 at 72 qps and 0.9976 at 35 qps for per-list graphs.The matched settings are ks=64 and ks=128, respectively; the recall comparison is stable to 10^-4 across reruns.Source: §5.8 · p. 25
  • Recursion replaces 58 minutes of graph construction and 4.2 GB of graphs with 2 minutes of GEMM assignments and postings.The comparison is against the natural alternative of attaching a small graph index to every oversized list.Source: §5.8 · p. 25
  • The ks=64 throughput pair came from different sessions on the same laptop, so its ratio includes thermal drift; the ks=128 pair was interleaved.The passage states that the recall comparison is unaffected at both settings.Source: §5.8 · p. 25

6 The resident-memory law

SOLO’s resident-memory law accounts for router state, per-thread scratch, and the page cache of list reads. Recursing on the router reduces its resident term by a factor of 1/α per level, while scratch still grows with the operating point needed to hold recall fixed.

6 The resident-memory law

  • Resident serving memory comprises the router over α^L n points, per-thread scratch, and the page cache of list reads.The scratch is a per-thread dedupe set; other listed structures are mapped or read explicitly and reclaimable page by page.Source: §6 · p. 25
  • At α=2% and d=96, the depth-1 router term is 8.96 B/object and gives a 1.2 × 10^8 flat ceiling at M=1 GB.The measured flat-router floor at 10^8 is 16–21 B/object once scratch and reads in flight are counted, so the Deep-100M deployment at that cap uses depth 2.Source: §6 · p. 26
  • Each recursion level divides the router term by 1/α; at α=2%, that multiplies the ceiling by 50 when scratch is small against M.The router is itself indexed, with its posting lists moved into a code stream on storage.Source: §6 · p. 26
  • At 10^9, the measured floor is 512 MB at recall 0.9925, and depth 3 serves from 96 MB; at 10^8, two-hop routing uses 50× less resident routing state for 0.0009 less recall.The depth-2 certificate predicts served recall to 0.0008; its throughput cost at 10^8 depends on whether the flat router fits in RAM.Source: §6 · p. 26
  • At fixed operating point scratch is independent of n, but holding recall fixed does not fix the operating point: candidates grow as n^0.4–0.6 over the measured range.The passage states the implementation was measured through depth 3 at 10^9 and does not claim beyond that point; 10^10 would face 32-bit identifiers, RAM sorting of n·b IDs, and about 7.6 TiB of stream and base.Source: §6 · p. 26
  • At ks=32, an 8-bit router has paired coverage cost 0.0000 on all four corpora, with no more than ±0.0008 bootstrap interval.The routed pool changed for 0 of 2,000 wiki-1024 queries, 5 Deep-96, 4 SIFT-128, and 49 GloVe queries.Source: §6 · p. 27
  • An 8-bit router multiplies the depth-1 ceiling by 2.8× at d=96 and 3.8× at d=1024; at d=1024 a 2-bit router gives 13.0× the float ceiling.The 2-bit router is worth another 3.4× at embedding dimensions for about 20% more scanned data; the measured 8-bit image shrinks from 188.7 to 78.9 MiB.Source: §6 · p. 27, Table 15 · p. 27
  • With a depth-2 router at 10^9, 8-bit copies route to the same coverage and recall to four decimals as the float control, in the same 9.1 ms.The end-to-end substitution was confirmed on the same queries.Source: §6 · p. 27

7 Where SOLO sits

SOLO reaches high recall under tight resident-memory caps where the measured alternatives do not, and its scan-based access pattern supports explicit, sequential counted I/O. Recursion and vertical decomposition extend this memory and deployment behavior, while the paper reports no claims beyond its last measured scale.

7 Where SOLO sits

  • 0.9977 recall on Deep-100M at 1 GB is the SOLO result; under the identical protocol, other systems either fail below their stated memory caps or saturate at lower recall.SPANN, DiskANN, and vote-served misi are killed below 8, 12, and 6 GB; ScaNN and RaBitQ reranking indexes are killed below 32 and 48 GB.Source: §7 · p. 27
  • At Deep-100M, SOLO retains 0.9977 recall from 1 GB, while the tested low-memory scoring alternatives saturate at 0.8747, 0.4281, 0.3450, and 0.8715 recall.The passage identifies the high-recall/tight-budget conjunction as the region no other tested system reaches.Source: §7 · p. 27
  • Under a cap, IVF-PQ throughput falls 40× from 8 to 1 GB, while SOLO falls 12% from 2 to 1 GB.The passage attributes the difference to probed-list random reads versus scans with known access order.Source: §7 · p. 28
  • Per-level candidate interfaces let SOLO decompose vertically; its depth-2 recall matches the composed prediction to 2 × 10^-4, and distributed answers match the single-process index.The two-tier GloVe prototype uses a 19.5 MiB routing tier and 1312 bytes per query on the wire; its synchronous-hop throughput cost is 12–33%.Source: §7 · p. 28
  • Four socket-local replicas raise throughput 2.2× for SOLO and 1.6× for hnswlib on the same machine and queries.The passage describes scans as bandwidth-bound and graph walks as latency-bound.Source: §7 · p. 28
  • At 10^9, depth 2 serves from 512 MB and is faster than the flat router; depth 3 serves from 96 MB, with the paper claiming nothing past the last measured point.The arithmetic places the resident-memory ceiling at 5.6 × 10^9 for depth 2 and 10^11–10^12 for depth 3 at M=1 GB; work per query grows sublinearly over the four measured decades.Source: §7 · p. 28

8 Related work

SOLO is positioned against clustered-routing, permutation/pivot, and navigable-graph indexes, combining a random vocabulary and rank-based assignment with scan-only serving, recursion, and a certificate.

8 Related work

  • SOLO shares IVF and SPANN’s scan-based serving silhouette but uses a random vocabulary, rank-b assignment, serve-time replication, recursion, exact scans, and a certificate.The passage contrasts its exact scan with lossy IVFPQ scoring and says rank-b assignment was measured to dominate closure.Source: §8 · p. 28
  • Unlike constant-size pivot indexes, SOLO uses a linear-size sampled vocabulary, retaining misi’s representation while replacing vote-then-verify with scan-only serving and recursion.The passage says NAPP’s resolution cannot grow with n, while SOLO keeps misi’s representation and replaces its serving theory.Source: §8 · p. 28
  • HNSW, DiskANN, and GRAFT are described as throughput-frontier graph systems whose recall is emergent, updates are hard, and disk versions pin navigation state.The comparison is deliberately against the strongest of each system type.Source: §8 · p. 28

9 Limitations and future work

The section derives filtered-search costs and conditional coverage from the scan-only identity, while noting that key high-selectivity outcomes and several implementation and evaluation questions remain unresolved.

9.1 Filtered search: what the identity gives, and what it still owes

  • Filtered queries intersect touched lists with the predicate bitmap and scan survivors, returning the exact top-k among those scanned survivors.Proposition 1 applies with quantities conditioned on the surviving set.Source: §9.1 · p. 29
  • A planner can price filtered queries from touched-list bitmap popcounts and extend b until surviving scanned mass reaches its target.Coverage can be certified over surviving objects without serving the filter, provided the ground-truth sample is drawn under that filter.Source: §9.1 · p. 29
  • At selectivities of 10^-2 and below, the affordable level of conditional coverage and comparison with filtered-DiskANN and ACORN remain untested.Geometry-correlated predicates can remove neighbors and vocabulary mass unevenly, making surviving mass fall faster than b · ks can be raised.Source: §9.1 · p. 29

9.2 Other limitations

  • The throughput comparison uses one four-socket Haswell machine, and the relative performance on current hardware remains to be measured.The memory system bounds a streaming kernel more than a latency-bound graph walk; the same kernel runs ten times faster per core on the laptop.Source: §9.2 · p. 29
  • Query-batched scanning is unimplemented; the reported Deep-100M rows use a single seed, and out-of-sample calibration transfer across corpora is untested.The out-of-sample provision uses one random split, two in-domain shifts, and one cross-modal shift; the table is per corpus.Source: §9.2 · p. 29
  • The paper reports no measurements beyond 10^9 objects and leaves per-object adaptive b as future work.The engineering blockers at 10^10 are listed elsewhere in the paper.Source: §9.2 · p. 29

10 Conclusion

The conclusion presents SOLO’s scan-based serving path as making recall an index property that can be certified before serving, and describes recursion, updates, and same-condition comparisons as part of its scale story.

10 Conclusion

  • One ground-truth pass certifies every operating point before serving, and the certificate held to four decimals from 10^6 to 10^9 objects.The conclusion says this held on the corpus where the index performs worst as well as those where it performs best.Source: §10 · pp. 29–30
  • Recursion and related design choices serve a hundred million vectors from a quarter gigabyte and a billion from under a hundred megabytes.The conclusion characterizes replication as insurance, quantization as lossless acceleration, skew as recursion, and the router as another database to index.Source: §10 · p. 30
  • The reported comparisons use the strongest systems the authors could run on the same machine, queries, and ground truth, with versioned manifests recording each run’s configuration.The implementation, experiment drivers, and manifests are available in the artifact repository.Source: §10 · p. 30
Loading 2610.02387v2…