Tracking: Vector search is ~50× slower than Qdrant at 21M scale (wiki_dpr_e5 disk-rescore benchmark)

[idas0]

Vector search is ~50× slower than Qdrant at 21M scale (wiki_dpr_e5 disk-rescore benchmark)

Labels: benchmark, performance, engine, investigation
Component: engine / TurboVec serving path

Summary

On the wiki_dpr_e5 workload from the Elastic-DiskBBQ-vs-Qdrant benchmark exchange
(21,015,300 × 768d, recall@100, closed-loop concurrency 4), LodeDB is projected to be
~50× lower throughput than Qdrant at 21M vectors, at lower recall (0.94 vs 0.96).
The gap is structural, not a tuning miss:

• The serving path is an exact O(N) SIMD scan — throughput scales as 1/N, while
  Qdrant's HNSW is ~flat in N. At 1M we're within ~2.5×; at 21M the gap is ~50×.
• There is no fp32 rescore (codes-only storage), so recall caps at ~0.94 at 4-bit.
• The opt-in cluster-prune ANN cannot close it: it masks the blocked layout at
  32-vector granularity over an insertion-ordered layout, so speedup ≈ 1/(32·f)
  where f = candidate fraction. Reaching 0.96 recall needs f ≈ 20% → block-skip
  saves ~nothing → ANN ≈ slower than exact.

This issue is a tracking / decision record, not a request to fix serving latency.
The recommendation is to not publish this benchmark as a head-to-head and to reframe
on LodeDB's actual strengths (footprint, zero-infra, sub-2M scale). Filed so the analysis
and repro are preserved.

Environment

• Host: Apple M5 (10-core), 32 GB, macOS (Darwin 25.4.0) — local spike, in-process.
  Numbers are generous vs the benchmark's Graviton + network-client setup.
• LodeDB 1.3.1, native core built from source (uv sync), numpy 2.4.
• Harness: benchmarks/wiki_dpr_disk_rescore/ (branch feat/wiki-dpr-disk-rescore-benchmark).

Reproduce

Data prep (streams shards into an on-disk float32 memmap, samples self-retrieval
queries, computes exact fp32 top-100 ground truth):

# 1. Fetch dataset shards (~80 GB) — e.g. huggingface_hub snapshot_download
#    kenhktsui/wiki_dpr_e5, allow_patterns=["data/*.parquet"] into <shards>/data
# 2. Prepare a working scale (1M validates the trend; O(N) makes 21M an ÷21 extrapolation)
python benchmarks/wiki_dpr_disk_rescore/data_prep.py \
    --shards-dir <shards>/data --out <data>/spike_1m \
    --target-rows 1000000 --n-queries 1000

Exact 4-bit baseline (ingest + recall@100 + sequential + closed-loop-4):

python benchmarks/wiki_dpr_disk_rescore/lodedb_bench.py \
    --data <data>/spike_1m --store <data>/store_1m_bw4 --bit-width 4 --loop-seconds 20

ANN cluster-prune operating point (constructor-time; each nprobe = its own store):

python benchmarks/wiki_dpr_disk_rescore/lodedb_bench.py \
    --data <data>/spike_1m --store <data>/store_1m_ann16 --bit-width 4 \
    --ann-clusters 1000 --ann-nprobe 16 --loop-seconds 20

Full 21M / serving-node-parity (4 vCPU / 16 GB) run via Modal — written, not yet run:

modal run benchmarks/wiki_dpr_disk_rescore/modal_bench.py::download
modal run benchmarks/wiki_dpr_disk_rescore/modal_bench.py::prepare
modal run benchmarks/wiki_dpr_disk_rescore/modal_bench.py::main

Measured results (Apple M5, in-process)

Scale / config	recall@100	seq latency	closed-loop-4 QPS	batch QPS
1M, 4-bit exact	0.9401	22 ms	45.9	329
1M, ANN 1000cl/nprobe16	0.877	12.5 ms	76.9	—
500k, 4-bit exact	0.9453	5.7 ms	—	—

ANN recall/speedup frontier (100k, 1000 clusters), tracing the curve:

nprobe	candidate frac	recall@100	speedup vs exact
3	0.3%	0.6559	1.25×
15	1.5%	0.8679	1.02×
60	6%	0.9348	0.68× (slower)
200	20%	0.9510	0.38× (slower)

Reference (published, not rerun here): Qdrant two-stage 111.9 QPS / 35.7 ms @ 0.9596
(3×4vCPU/16GB); Elastic DiskBBQ 32.4 QPS / 122.6 ms @ 0.96 (3×7vCPU/26GB).

Analysis

• O(N) scan, cores already saturated. The TurboVec scan is rayon-parallel
  (into_par_iter, third_party/turbovec/turbovec/src/search.rs), so one query uses all
  cores and closed-loop concurrency ≈ single-thread throughput (GIL is not the lever —
  shared / per-thread / per-process closed-loop modes all land near single-thread). 1M→21M
  throughput ÷21 ⇒ ~2 QPS closed-loop vs Qdrant's ~flat 112.
• 500k→1M is super-linear (5.7→22 ms): memory-bandwidth-bound at scale, so 21M is
  likely worse than the linear ÷21 estimate.
• ANN is a bitmask over the blocked layout. A 32-vector block is skipped only if all
  32 slots miss (block_has_allowed, search.rs:1314); the layout is insertion-ordered so
  candidates scatter. Blocks-scanned ≈ 1 − e^(−32f) ⇒ speedup ≈ 1/(32·f). Validated:
  predicts 1.95× at the 1M nprobe=16 point vs 1.8× measured. Cluster count only sets the
  granularity of f (capped at 4096, crates/lodedb-core/src/engine/mod.rs:5065); it does
  not change the speedup-at-fixed-recall curve. Reaching 0.96 recall ⇒ f ≈ 20% ⇒ ANN
  ≈ slower than exact.
• No fp32 rescore (codes-only) ⇒ recall caps ~0.94 at 4-bit; no lever to reach 0.96.

Options (for discussion — none scoped here)

1. Don't publish head-to-head; reframe on footprint (~8 GB 4-bit codes vs 60 GB fp32
   kept for rescore), zero-infra embedded deployment, and ≤2M scale where exact scan wins.
   (Recommended.)
2. Cluster-contiguous blocked layout (reorder codes by cluster so inverted lists are
   contiguous) — would let block-skipping actually prune; decouples f from scatter.
3. A real sublinear index (HNSW / DiskANN-style) — closes the gap but is a major engine
   project and a philosophical shift from the exact-scan core.
4. fp32 rescore tier — needed to exceed the ~0.94 recall ceiling; contradicts codes-only
   storage.

Open item

Not measured: whether finer clusters improve recall-per-candidate enough to matter (the
4096-cluster run was cut for time). The 1/(32·f) speedup curve is scatter-bound regardless,
so even optimistically this is break-even-with-exact at 0.96 recall, not a fix. The finished
4096-cluster sweep (~25 min, k-means build dominated) would close this out.

[Davidobot]

Results from the two-stage implementation (#84, merged) measured with the reconstructed harness (#85, merged); every serve below is 4 vCPU at 1M rows, closed-loop concurrency 4, recall@100 against exact fp32 ground truth.

This issue's central claims, re-measured:

Claim	Verdict
Block-skip over the insertion-ordered layout prunes at ~1/(32f)	Confirmed on stores built by the released engine, and fixed: the cluster-contiguous layout serves 1.7-2.9x faster at bit-identical recall (same store parameters, same clustering, only physical row order differs)
At recall-grade nprobe, ANN is slower than the exact scan	Reproduced on the old layout (np128: 73.5 ms vs exact 53.3 ms) and gone on the new one (43.2 ms)
Recall caps at ~0.94 at 4-bit with no lever	Removed: exact + fp16 rescore reaches 0.9994 (fp32: 1.0000) at ~7% throughput cost
Reaching 0.96 recall needs f~20%, making ANN pointless	Refuted: ann4096 + fp16 rescore serves 0.9701 recall@100 at 27.8 QPS with f=3.1%, 1.5x the exact scan's throughput (Qdrant's published point: 0.9596)
Open item: do finer clusters improve recall-per-candidate?	Yes: ann4096 0.9249 vs ann1000 0.9098 at matched f~3.1%

Selected operating points (full 22-config sweep committed under benchmarks/wiki_dpr_disk_rescore/results/rows_1000000/):

config	recall@100	p50	CL-4 QPS
exact 4-bit (baseline)	0.9408	53.3 ms	18.3
ann1000 np16 (new layout)	0.8759	8.2 ms	90.4
ann4096 + fp16 rescore, np128/ov2	0.9701	35.1 ms	27.8
ann4096 + fp16 rescore, np256/ov4	0.9863	57.8 ms	16.4
exact + fp32 rescore	1.0000	60.0 ms	16.5

21M status. The full corpus, exact fp32 ground truth, and Modal pipeline are staged and reproducible (one command per stage). A 21M exact store was built once: ingest 82 min at 4,270 rows/s, persist 102 min, 13.7 GB on disk. The head-to-head serve was not completed; the campaign surfaced three scale problems that are their own issues: the reopen RAM floor (#88), persist duration at 21M (#89), and long native calls starving host Python threads (fixed: GIL released in #84's follow-up #87). Projection to be validated when the 21M serve runs: the measured 1M exact throughput scales to roughly 1 QPS at 21M (the issue's ~2 QPS estimate was optimistic), and the 0.97-recall two-stage point scans 3.1% of the corpus, projecting an order of magnitude over exact at equal-or-better recall than the published Qdrant point; per-node parity comparison remains projection until measured.

The recommendation in this issue's summary (do not publish the old numbers as a head-to-head) stands for the pre-#84 engine; the measured 1M results above are per-node-honest and committed.