big-ann-benchmarks streaming track (NeurIPS'23)¶

The streaming track replays a runbook of inserts, deletes and searches from an empty index (neurips23/runbooks/delete_runbook.yaml on msturing-10M-clustered: 100-d float32, L2, at most 6M live rows, 33 search checkpoints of 10,000 public queries) and scores the mean recall@10 over the checkpoints, under 8 GiB of DRAM and one hour. HMS enters it with UpdatableIndex (src/python/vector_index.rs over core::qgraph::UpdatableVGraph): a memory-mapped base graph, an in-memory delta graph of the rows inserted since the last consolidation, and a rebuild of the base over the live rows when the delta or the deleted share passes the adapter's thresholds (delta 1.0x the base, 30% deleted, 100k rows minimum).

Every number below traces to benchmarks/results/bigann_streaming_delete_runbook_v1.json or, from "Operating point" on, benchmarks/results/bigann_streaming_delete_runbook_v2.json; both record the HMS commit, the harness commit (89a3aba), the machine and the parameters.

Where the recall went¶

The recall deficit at the ef the leaderboard entries use (64-128) was diagnosed on the first 1M rows of the dataset (float64 brute-force ground truth over the live rows, 1,000 public queries) and on the first 12 steps of the official runbook against the harness ground truth, with per-search-step recall recorded. The hypotheses that deletes or the delta were the loss are falsified by that record: recall is low at the first checkpoint, before any delete, and stays flat across deletes and consolidations (at ef 1024 the 33 official checkpoints sit in 0.91-0.98 with no trend). Two settings of the build explain the gap to the static VectorIndex on the same rows and the gap to the track baseline:

• alpha, the pruning parameter of the second construction pass, defaulted to 1.2 in UpdatableIndex.create (and in the track adapter) while VectorIndex and BuildParams::default() use 1.0. At degree 32 the alpha-1.2 prune keeps nearer, shorter edges and loses 7-9 points of recall@10 at ef 64-128 on both the base and the delta. With alpha 1.0 the consolidated base reproduces the static index exactly (the regression test consolidated_base_matches_static_build_at_equal_params pins that equality). The default is now 1.0.
• The remaining distance to the DiskANN baseline (R64, Ls 100: 0.924) is the degree: R64 L128 gains another 12 points at ef 64 and 10 at ef 128 on the prefix, at 2x the build time per consolidation and about 128 more bytes per live row; R32 peaked at 7.47 GiB (sampled summed RSS, Modal, ef 1024) and at 4.85 GiB (GNU time, writerslogic-02, ef 64 and 128), and the official R64 L64 run at ef 256 peaked at 5.57 GiB on Modal (see the official runs table).
• Candidate retention (reservoir) changes nothing at any ef (0.7161 at 0, 256 and 512), so neither quantized estimates nor pool eviction is a loss mechanism here; the queries are simply far from the clustered rows (in-distribution queries reach 0.973 at ef 64 on the same graph).

Per search step of the official runbook (harness ground truth, same wheel, R32 L64 T8):

Official runs (delete runbook, run.py --nodocker, 8 CPUs, 8 GiB)¶

The baseline the track README quotes is DiskANN at R64 L50 Ls100: 0.924 in about 23 minutes on the competition VM (Azure D8lds v5). The writerslogic-02 runs are recall runs at nice 19 on a shared host (Core Ultra 9 185H, 8 of 22 threads, 8 GiB cgroup cap); their wall time is an upper bound, not a timing claim.

The Modal runs at 082766e each replay the runbook once (one round per row), the R32 ones in four containers started together, under /usr/bin/time -v around run.py, with an 8 GiB hard memory limit and non-preemptible scheduling. cpu=8.0 gives eight schedulable CPUs; Modal bills cpu in physical cores and hides the topology inside the container, so whether these are eight cores or eight hyperthreads is not known, and the compute is not matched to the competition VM's 8 vCPU (D8lds v5). Wall time spread between the containers is host noise as much as ef: the ef 512 replay finished before the ef 384 one, and the runbook-step sums differ by 33% in the direction opposite to the search work. The runbook-step sum is the harness's own per-step time; the wall includes start-up and the dataset range reads.

Operating point¶

At R32 L64 alpha 1.0, ef 512 scores 0.9371 against the track baseline's 0.924, at a 4.84 GiB peak, in a 15:41 replay (941 s of runbook steps); ef 384 falls just short (0.9226). Every one of the five Modal replays finished in 13:32-20:51 against the baseline's 23 minutes, one round each and on different hardware from the baseline's, so that is an observation, not a matched timing comparison. The ef 64 and ef 128 rows reproduce the Core Ultra 9 numbers of the 791749b runs (alpha 1.0 passed explicitly) to the fourth digit, and main without the 3-byte ids scores the same 0.7623 on Modal, so the change leaves the results unchanged.

The choice came from full-runbook replays on a shared Intel Core Ultra 9 185H (8 threads per replay, nice 19, load average 11-25; replay.py: the official runbook through UpdatableIndex with the adapter's policy, recall@10 against the harness ground truth at every checkpoint, several ef per pass). Mean recall@10 over the checkpoints each replay reached (rows marked partial were stopped early; their means cover the early checkpoints, which score higher than the late ones, so they are not comparable with full means):

Each complete replay reproduced the official score to the fourth digit (R32 ef 384 0.9226, ef 512 0.9371; R64 ef 256 0.9353), so a full replay is the official score without the harness.

Degree 64 reaches the same recall at half the ef: R64 L64 at ef 256 scores 0.9353 (0.0018 below R32 L64 at ef 512) at 0.73 GiB more memory, and its 908 s of runbook steps are indistinguishable from R32's 941 s given the spread between containers. R32 ef 512 is the configured point. In both, the inserts and deletes, which run the four rebuilds of 1.9M to 3.8M live rows, are 80-87% of the step time. The R64 L128 and R64 L48 replays were stopped early.

Memory¶

Peak RSS at R32 is 4.84-4.87 GiB for the benchmark process (4.97 GiB sampled with the Modal parent), reached near the end of the runbook, when the live count (5.2M) and the mapped base pages searches touch are largest; at R64 it is 5.57 GiB. The anonymous peak comes earlier, in the step-49 rebuild of 3.8M rows (old delta, new adjacency, Python): 2.1 GiB at R32 and 2.7 GiB at R64 in the replays. The 8 GiB limit is not binding at either point. The earlier 7.47-7.78 GB peaks were measured at ff70f3e and cc5dede, before #205 moved consolidation onto a mapped scratch matrix and a bounded encoder instead of an owned row copy plus a full owned graph and encoding; the drop is consistent with that change, which this one does not touch.

This change narrows the consolidated base's neighbour ids from 4 to 3 bytes whenever the generation has fewer than 2^24 - 1 rows (4-byte ids above that; variable-width encodings are untouched), as the static VectorIndex already does: the base vertex file shrinks from 380 to 348 bytes per row at R32 (508 to 444 at R64), about 166 MB at 5.2M rows. Measured on Modal at ef 64, one round each, run one after the other: main (c80aa52) peaks at 5,350,993,920 bytes (4.98 GiB) for the benchmark process and 5,572,100,096 sampled with the parent; this change at 5,212,020,736 (4.85 GiB) and 5,432,266,752, 139 MB lower (2.6%), with the same score (0.7623).

On the Core Ultra 9 host (no reclaim pressure, 12 GiB scope), the replays' RSS peaks split into anonymous memory (delta graph, build adjacency, Python) and mapped files (base, scratch rows, and the replay's own numpy.memmap of the source, which the official adapter does not hold): R32 L64 peaks at 4.55 GiB VmRSS (2.0 GiB anonymous, 2.5 GiB mapped) at step 73 with 5.2M live rows; R64 L64 at 6.04 GiB (2.0 anonymous, 4.1 mapped) at step 68 with 4.8M live rows.

Final runbook (msturing-30M-clustered): loss¶

One run at the same setting (R32 L64 alpha 1.0, ef 512, 082766e, Modal cpu 8.0, 8 GiB) did not finish: the runner stopped run.py at its 3,600 s limit after 541 of 1,280 steps (4.3M live rows at that point), so no recall was recorded. Measured over those steps: 270 searches at 3.88 s each (1,049 s), 143 insert steps 1,089 s, 128 delete steps 1,461 s (deletes include the tombstone-triggered rebuilds); peak RSS 6.02 GiB for the benchmark process, 6.22 GiB summed with the parent, so memory was not the limit. Projection, not measured: the 640 searches alone need about 2,480 s at ef 512, so this runbook needs a lower ef and fewer or cheaper rebuilds to fit the hour.

Merged consolidation (development measurements)¶

UpdatableIndex.consolidate(merge=True) keeps the previous base graph instead of rebuilding it: it splices deleted rows out of the lists that pointed at them, links the delta in with the build's first insertion pass, and runs the build's second pass over the delta, the base rows it links to and the rows that lost a deleted neighbour (docs/file-format/VECTOR-UPDATES.md). The fork adapter turns it on with "merge": true. Each Modal row below is one round (run.py --nodocker, harness 89a3aba, cpu=8.0, 8 GiB, non-preemptible, R32 L64 alpha 1.0 T8, ef 512, HMS 9b26418, which is c1ec45d before its rebase onto main); the control is the same image without merging, run in the same hour, since step sums vary by about a third between containers.

A merge searches again for about four to six rows per changed row, so it beats a rebuild only while the churn per consolidation is a fraction of the live set: merging at a quarter of the base spends more on inserts than rebuilding at doubling. The configured point merges at the rebuild thresholds (1.0 / 0.3): by construction a delta-triggered consolidation there usually falls back to a rebuild (the delta is then at least as large as the surviving base), so the merges replace the tombstone-triggered rebuilds.

Final runbook (msturing-30M-clustered), ef 256: no recall was recorded. With the image of 9b26418 at ef 256, merging at the rebuild thresholds (1.0 / 0.3) reached step 672 of 1,280 in 1,926 s of runbook steps (searches averaged about 1.0 s; the #238 run at ef 512 needed 3,599 s for its first 541 steps), then the launcher's 8 GiB guard on the summed benchmark and parent RSS stopped it at 8.60 GB during the step-673 consolidation (a merge after deletes, 8.42M live rows; the same step at which earlier rebuild-based candidates ran out of time or memory). Merging at 0.25 / 0.15 reached step 638 in 2,838 s before the same guard (8.61 GB). The ef 512 run at 0.25 / 0.15 was stopped at step 214 (1,461 s of steps against the #238 run's 976 s for the same steps) once it could not finish. The merge read the previous base's adjacency back into memory and kept those pages through the insertion passes; 50017d4 drops them as soon as the last list is read.

Replacement entry memory (development measurement)¶

When consolidation deletes the previous entry vertex, it now selects the surviving row nearest the mean directly from the prepared rows. Previously it copied all surviving vectors and norms first. Accumulation order and ties remain identical; stored formats and search parameters are unchanged.

A locked, interleaved three-pair kernel experiment on Intel Core Ultra 9 185H, eight threads pinned to CPUs 0–7, load average 1.18–1.20, used 1M synthetic 100-dimensional rows with 800k survivors. Median process peak RSS fell from 718,436 to 403,012 KiB; median selection time fell from 182.64 to 38.79 ms. All six runs selected row 830166. Raw values and source hashes are in benchmarks/results/streaming_entry_memory_v1.json. These are development measurements, not streaming standings or full-consolidation costs.

To reproduce the parent arm, check out the recorded parent commit and apply benchmarks/results/streaming_entry_memory_v1/baseline.patch from this revision. Build both arms separately with cargo test --release --lib replacement_entry_large_live_set --no-run. Under one flock ~/hms-timing.lock, run their test executables in A/B, B/A, A/B order with RAYON_NUM_THREADS=8 /usr/bin/time -v taskset -c 0-7 <test-executable> replacement_entry_large_live_set --ignored --nocapture --test-threads=1.

Whether step 673 deletes the previous entry, total consolidation RSS, and final-runbook recall/completion remain unmeasured. After the standings freeze is lifted, pin the adapter to the tested revision with R32/L64/alpha 1.0/T8, merge enabled, delta/deleted ratios 1.0/0.3 and ef256, then run in the harness checkout with its dataset and ground truth:

flock ~/hms-timing.lock systemd-run --user --scope -q \
  -p MemoryMax=8G -p MemorySwapMax=0 taskset -c 0-7 \
  /usr/bin/time -v timeout 3600 uv run python run.py --nodocker \
  --neurips23track streaming --algorithm hms --dataset msturing-30M-clustered \
  --runbook_path neurips23/runbooks/final_runbook.yaml

Record all 1,280 steps, mean recall across all 640 searches and peak RSS. A kernel improvement does not establish that the one-hour/8-GiB limits or a leaderboard target have been met.

Earlier graph-page release (development measurement)¶

Consolidation now marks rows that lose deleted neighbours while repairing their adjacency, then releases the old graph pages before inserting delta rows. This removes a second scan of the old adjacency. The encoded generation remains byte-identical.

Three locked interleaved pairs on Intel Core Ultra 9 185H, eight threads pinned to CPUs 0–7, used a 500k-row 100D base, degree32/build-ef64, every seventh row deleted except the entry, and 100k inserted rows. At the end of the insertion phase, RSS was 441,480–444,072 KiB on the parent versus 381,084–381,300 KiB with earlier release. All six encoded generations had CRC32 434904111. Whole-process peak RSS stayed approximately 516–518 MiB (528,836–530,216 KiB); that high-water mark includes fixture construction. Consolidation times varied 19.86–27.29 s versus 19.79–22.32 s; no reliable speedup is established.

benchmarks/results/streaming_page_release_v1.json records each pair and load average. Apply its sibling directory's baseline.patch to the recorded parent to add the same fixture and generation test. Build both test executables with cargo test --release --lib consolidation_live_set_peak --no-run. Hold the timing lock, set RAYON_NUM_THREADS=8 HMS_CONSOLIDATION_ROWS=500000, and run A/B, B/A, A/B with /usr/bin/time -v taskset -c 0-7 <test-executable> consolidation_live_set_peak --ignored --nocapture --test-threads=1. Phase instrumentation is enabled identically in both arms.

An isolated consolidation peak, an 8-GiB constrained scaled replay, and final-runbook completion/recall remain unmeasured. After the standings freeze is lifted, pin the adapter to this revision with R32/L64/alpha1.0/T8, merge enabled, delta/deleted ratios 1.0/0.3, ef256, and run in the prepared harness checkout:

flock ~/hms-timing.lock systemd-run --user --scope -q \
  -p MemoryMax=8G -p MemorySwapMax=0 taskset -c 0-7 \
  /usr/bin/time -v timeout 3600 uv run python run.py --nodocker \
  --neurips23track streaming --algorithm hms --dataset msturing-30M-clustered \
  --runbook_path neurips23/runbooks/final_runbook.yaml

Require all 1,280 steps, recall averaged over all 640 searches, and memory below 8 GiB. The phase-RSS reduction alone does not establish that outcome.

Delta-row spill (development evidence; incremental comparison pending)¶

Consolidation moves committed delta rows into a private unlinked read-only mapping before building the next generation. Copying rows releases mapped pages in batches. The writer serializes mutations; scratch I/O occurs outside the state lock. Failed consolidation can still accept subsequent inserts by detaching the mapped backing. Persisted bytes are unchanged.

The completed development comparisons use older parent e3bb3648, so they combine entry selection, earlier graph-page release and delta spilling. They do not isolate this PR's benefit over its parent 0880ccda. On Intel Core Ultra 9 185H, eight threads on CPUs 0–7 under the timing lock, one 3M-base/600k-insert pair within an 8-GiB cgroup reduced isolated consolidation peak RSS from 2,581,784 to 2,348,628 KiB (9.0%). Consolidation took 185.401 versus 185.642 seconds; both generations had CRC32 2824448824. Linux clear_refs=5 reset the high-water mark before consolidation. Load averages and smaller three-pair results are in benchmarks/results/streaming_delta_spill_v1.json.

The cached-slice implementation's single-thread query check gave paired median ratios 0.9939, 1.0263 and 0.9942, with identical result fingerprints; no consistent speed change was established. A discarded per-neighbour backing lookup was 0.6–1.0% slower.

Local formatting, clippy, tests, byte-output and interrupted-consolidation recovery checks passed. The master session owns the incremental comparison against the current PR parent. Build both arms with cargo test --release --lib --no-run, adding the candidate's ignored measurement fixtures to the parent without its production changes. Under the timing lock, run A/B, B/A, A/B with RAYON_NUM_THREADS=8 HMS_CONSOLIDATION_ROWS=500000, an 8-GiB cgroup and taskset -c 0-7 <test-executable> consolidation_live_set_peak --ignored --nocapture --test-threads=1; also run delta_search_live_set in both arms.

Scaled official-data replay, eight-thread search throughput and final-runbook completion and recall remain unmeasured. After the freeze is lifted, pin the tested revision and use the R32/L64/alpha1.0/T8 merge configuration, ratios1.0/0.3, ef256:

flock ~/hms-timing.lock systemd-run --user --scope -q \
  -p MemoryMax=8G -p MemorySwapMax=0 taskset -c 0-7 \
  /usr/bin/time -v timeout 3600 uv run python run.py --nodocker \
  --neurips23track streaming --algorithm hms --dataset msturing-30M-clustered \
  --runbook_path neurips23/runbooks/final_runbook.yaml

Require all 1,280 steps within one hour and 8 GiB, and report recall over all 640 searches. These development measurements establish no leaderboard standing.

The delta frontier now rejects a noncompetitive scored neighbour before searching for its insertion position. Three alternating development pairs on an Intel Core Ultra 9 185H (CPUs 0–7, timing lock, five measured batches per arm) compared 7db61aa0 with 5c8e8ec. On the first 1M official clustered rows and 256 official queries, median query-time ratios were 0.704/0.737 with one thread and 0.809/0.828 with eight threads at ef256/512; every pair improved. The synthetic 100k-row control ratios were 0.828/0.834 and 0.879/0.830. One-minute load averages ranged 2.16–7.45 on official data and 1.80–3.13 on synthetic data. All full-frontier score bits and IDs matched across arms, pairs and thread counts. The sort-based oracle also preserves traversal visit counts, including tied scores and deleted routing vertices. Per-arm timings, fingerprints and commands are in streaming_frontier_v1.json. This measures live delta queries; total streaming throughput and the final-runbook recall still require the post-freeze command above.