You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Tracking epic for HNSW/vector-index research and roadmap items: semantic hierarchy (centrality-biased levels, RAPTOR-style summary trees), and related retrieval-capability research. See the design review posted on #1244.
Filed by Claude (Opus 4.8), issue-backlog triage & grouping pass.
Scaling data for 10M+ node graphs, and where the next bottlenecks are
Follow-up to #2069 → #2125 → #2180 → #2181. Posting the measured curves and the cost
decomposition here, because they change what the roadmap for this epic should contain.
Method: benchmarks/hnsw-scale.js, 768-dim, int8, calibrated hard synthetic corpus
(d(nn)/d(rand) ≈ 0.65–0.8), single-query, in-memory harness, main with #2125 and #2181.
5M latencies carry memory-pressure noise (27.6 GB RSS on a 30 GB box). The scaling write-up
is in DESIGN.md under "efConstruction and the search-ef ceiling both auto-scale with the graph".
Measured
N
ef
p50
p95
p99
recall@10 raw/set
visited
ms/insert
1M (efC 200)
512
7.2 ms
12.0
12.2
0.985 / 0.997
3,110
6.6
2M (auto efC 283)
512
10.4 ms
22.3
28.1
0.950 / 0.955
4,248
6.6
2M
1024
30.4 ms
39.8
42.5
0.983 / 0.988
—
—
5M (auto efC 447)
512
22.2 ms
41.4
45.4
0.920 / 0.935
5,107
13.9
5M
1024
45.1 ms
70.8
160.2
— / 0.985
—
—
Shape: visits grow ~N^0.20 (log N plus a small polynomial correction), wall-clock ~N^0.36
(the extra factor is memory hierarchy, not algorithm). Constant-recall latency is ~Θ(√N) —
that's the curve the auto-scale now spends by design. Build is Θ(N^1.5) under recall-preserving
construction. Average layer-0 degree holds at ~37 across all sizes.
Per-visit cost decomposition
Measured on a representative node (768-d int8 vector, 40 layer-0 edges):
Component
Cost
Share of a warm visit
Total per visited node (5M, ef 512)
4.34 µs
100%
768-d int8 asymmetric cosine, JS
0.43 µs
10%
Neighbour iteration + visited-set ops
0.21 µs
5%
msgpackr decode of one node (VT-cache miss)
5.57 µs
+128% when cold
~85% of a warm visit is JS object bookkeeping — candidate heap, visited set, property access,
allocation, GC. A native distance kernel is not the lever: at 0.43 µs it would lose to its
own NAPI boundary crossing. A native traversal loop over a native data layout is (SIMD int8 dot
~50 ns + streaming 768 contiguous bytes ~150 ns + primitive heap/bitset ops ~50 ns ≈ 0.25–0.4
µs/visit, i.e. an estimated ~10–15×, one boundary crossing per query).
Resident-size measurement
A node encodes to 1,425 bytes with shared-structure encoding (768 B vector + ~40 × {id,
distance} + scale/invMag/pk). Projected per graph:
Not in the current shape. Traversal is pointer-chasing — you must read a node to learn its
neighbours — so misses serialise and cannot be prefetched. At ~5K visits/query and ~100 µs per
NVMe read: 1% miss = +5 ms, 5% = +25 ms, 20% = +100 ms, cold = +460 ms. Tolerance is roughly ≤2% miss on visited nodes, and visit counts grow with N. Upper layers self-protect (6.3% of
nodes but only 5.5% of visits at 5M, hit every query, so they stay hot); the ~95% of visits in
layer 0 track query locality, which a long-tail corpus does not supply.
Index slicing within a table. √N constant-recall latency and N^1.5 build make one very
large graph strictly worse than 8–32 medium ones on both curves. DESIGN.md already states
the ef ceilings are finite on purpose and that sharding is the tool past tens of millions —
but there's no supported way to do it inside a table today. This looks like the highest-value
missing capability for 10M+ tables.
A compressed resident traversal plane + rescore. Binary codes (or PQ) for traversal, full
int8 on disk for rescoring a bounded candidate set. 26 GB vs 143 GB at 100M nodes, and it is
simultaneously what makes a native loop fast (contiguous, decode-free, SIMD-able) and what
makes the working set fit.
Native traversal loop, per the decomposition — most valuable as a capacity/QPS lever.
1, 3 and 4 are effectively a single project — a native compact resident traversal plane with
async batched rescore from disk, i.e. roughly DiskANN implemented against RocksDB — and none of
them delivers much alone. Worth scoping as one thing.
Activity
kriszyp commentedon Aug 28, 2026
Scaling data for 10M+ node graphs, and where the next bottlenecks are
Follow-up to #2069 → #2125 → #2180 → #2181. Posting the measured curves and the cost
decomposition here, because they change what the roadmap for this epic should contain.
Method:
benchmarks/hnsw-scale.js, 768-dim, int8, calibrated hard synthetic corpus(d(nn)/d(rand) ≈ 0.65–0.8), single-query, in-memory harness,
mainwith #2125 and #2181.5M latencies carry memory-pressure noise (27.6 GB RSS on a 30 GB box). The scaling write-up
is in
DESIGN.mdunder "efConstruction and the search-ef ceiling both auto-scale with the graph".Measured
Shape: visits grow ~N^0.20 (log N plus a small polynomial correction), wall-clock ~N^0.36
(the extra factor is memory hierarchy, not algorithm). Constant-recall latency is ~Θ(√N) —
that's the curve the auto-scale now spends by design. Build is Θ(N^1.5) under recall-preserving
construction. Average layer-0 degree holds at ~37 across all sizes.
Per-visit cost decomposition
Measured on a representative node (768-d int8 vector, 40 layer-0 edges):
~85% of a warm visit is JS object bookkeeping — candidate heap, visited set, property access,
allocation, GC. A native distance kernel is not the lever: at 0.43 µs it would lose to its
own NAPI boundary crossing. A native traversal loop over a native data layout is (SIMD int8 dot
~50 ns + streaming 768 contiguous bytes ~150 ns + primitive heap/bitset ops ~50 ns ≈ 0.25–0.4
µs/visit, i.e. an estimated ~10–15×, one boundary crossing per query).
Resident-size measurement
A node encodes to 1,425 bytes with shared-structure encoding (768 B vector + ~40 × {id,
distance} + scale/invMag/pk). Projected per graph:
Can the graph exceed RAM?
Not in the current shape. Traversal is pointer-chasing — you must read a node to learn its
neighbours — so misses serialise and cannot be prefetched. At ~5K visits/query and ~100 µs per
NVMe read: 1% miss = +5 ms, 5% = +25 ms, 20% = +100 ms, cold = +460 ms. Tolerance is roughly
≤2% miss on visited nodes, and visit counts grow with N. Upper layers self-protect (6.3% of
nodes but only 5.5% of visits at 5M, hit every query, so they stay hot); the ~95% of visits in
layer 0 track query locality, which a long-tail corpus does not supply.
What this implies for the roadmap
one query use many cores, and enables batched parallel reads — which is the only way an
out-of-memory graph works, per the miss-rate arithmetic above.
large graph strictly worse than 8–32 medium ones on both curves.
DESIGN.mdalready statesthe ef ceilings are finite on purpose and that sharding is the tool past tens of millions —
but there's no supported way to do it inside a table today. This looks like the highest-value
missing capability for 10M+ tables.
int8 on disk for rescoring a bounded candidate set. 26 GB vs 143 GB at 100M nodes, and it is
simultaneously what makes a native loop fast (contiguous, decode-free, SIMD-able) and what
makes the working set fit.
severity suggests for any delete-and-reinsert-heavy ingest pattern.
1, 3 and 4 are effectively a single project — a native compact resident traversal plane with
async batched rescore from disk, i.e. roughly DiskANN implemented against RocksDB — and none of
them delivers much alone. Worth scoping as one thing.
Raw benchmark JSON available on request.