ADR-002 — DiskANN as cor's billion-scale index option

Status: Decided 2026-05-28. Implementation queued across three coordinated sessions for cor 3.0.0 + brainy 8.0.0.

Supersedes: Original DiskANN spike task (#35), retired 2026-05-28 in favour of the three-session plan captured here.

Related:

  • ADR-001 — native column store, shipped 2.3.0

  • brainy 7.28.0 SQ4 (4-bit) quantization — paves the PQ path for DiskANN's compressed in-RAM distance

  • Cortex 2.4.0 storage foundations (#23–#26) — stable IDs, mmap vector layer, graph compression — all transfer directly to DiskANN

Context

Brainy ships a TypeScript HNSW index that works excellently up to roughly 10M vectors per node on commodity hardware. Cortex 2.3.0 added a Rust-native HNSW variant via the hnsw provider hook — same algorithm, ~3–10× the throughput on hot paths thanks to SIMD distance and a tighter graph layout. The 2.4.0 storage foundations (vector mmap store, graph link compression, stable entity IDs) push HNSW further into the disk-resident regime.

But HNSW's design assumes the graph fits comfortably in memory. Past ~10M vectors, two costs compound:

  1. Memory pressure — the graph alone (M × node_count neighbour pointers + level metadata) plus the vector store (dim × 4 × node_count bytes for float32) blows past the RAM budget of normal nodes. At 100M vectors of 384-dim embeddings: ~150 GB of vectors + ~13 GB of graph = ~163 GB RAM minimum. At 1B vectors: ~1.6 TB RAM — out of reach on single boxes.

  2. Disk-locality on cold caches — even with vectors offloaded to mmap, HNSW's traversal order has no correlation with insertion order on disk. Each search hop typically faults a new page, costing ~10 μs per hop on NVMe SSD. A 100-hop search burns ~1 ms of disk wait that proper locality would have served from a single 10 μs read.

DiskANN (Microsoft, 2019) was designed for exactly this regime. Its Vamana graph construction uses α-pruning to choose neighbours that produce disk-locality natively: nodes visited together during search end up adjacent on disk. Combined with product quantization (PQ) in RAM for approximate distance, and full vectors on disk for re-ranking the final candidate set, DiskANN holds single-machine billion-scale search at a fraction of HNSW's RAM cost.

For cor specifically, DiskANN is the natural billion-scale upgrade path because:

  • The 2.4.0 foundations (stable IDs, mmap vector layer, graph link compression) transfer to it without rework

  • The 2.5.0 #30 SQ4 quantization work primes the PQ codec path

  • Cor's positioning has always been "billion-scale via Rust acceleration" — DiskANN fits the message

  • We control the rest of the stack (storage adapters, idMapper, HNSW provider), so the integration is in friendly territory

We considered ScaNN (Google, Apache 2.0) as an alternative. It posts SOTA recall/QPS numbers at moderate scale with anisotropic vector quantization. We declined: ScaNN is IVF-based (inverted file with partition centroids), which doesn't align with brainy's graph-native architecture. Switching to IVF would mean losing the structural symmetry between brainy's verb graph and its vector index, plus introducing periodic clustering retraining (an operational concern brainy doesn't currently have).

Decisions

Decision 1 — DiskANN as the billion-scale upgrade path (not a replacement for HNSW)

HNSW stays the brainy default forever. Every existing user, including those without cor, continues to get the TS HNSWIndex they ship with today. DiskANN is added as an alternative provider that engages when its constraints are met.

This preserves three properties we don't want to give up:

  • Zero-friction onboarding for new brainy users (no cor required, no config tuning to pick an algorithm).

  • Backward compatibility for every existing brainy install (no surprise migrations on upgrade).

  • The "cor makes brainy faster" story (not "cor makes brainy different").

Decision 2 — 100% pure Rust, no C++ FFI

We will port DiskANN's Vamana algorithm to Rust from the published paper (Subramanya et al., NeurIPS 2019; Singh et al., 2021) rather than wrap Microsoft's C++ reference implementation via FFI. The Vamana algorithm is straightforward: greedy graph construction with an α-pruning step that controls graph density. The published pseudocode plus the reference implementation's behaviour give us everything we need to validate correctness.

PQ codec: we will either compose a battle-tested Rust crate (e.g., qdrant-quantization, Apache 2.0) or implement PQ training + encode/decode in cor directly, depending on parity test outcomes. Either way, no C++.

Why not FFI: cross-platform C++ builds for Node native modules are operationally expensive (Linux/macOS/Windows × x64/arm64 binaries, headers, link-time gotchas), Microsoft's reference impl has its own build dependencies that would propagate, and we'd inherit any patent grant ambiguities at the binary level. Pure Rust gives us napi-rs's mature cross-platform binary distribution and a license posture we fully control.

Why not adopt an existing Rust crate wholesale: no mature Rust port of Vamana exists at our knowledge cutoff. We will track this and pivot if a high-quality one emerges; for now we're building it.

Decision 3 — Filesystem-only deployment in the first release

DiskANN is local-SSD-by-design. The whole point of the architecture is that disk reads are cheap (NVMe-cheap, ~10 μs) and predictable, so the search algorithm can lean on the OS page cache + the on-disk layout's locality.

Cloud object storage (S3, R2, GCS) breaks that assumption: range reads of large objects cost ~100 ms of round-trip latency, and the locality model has to account for HTTP/2 framing instead of OS pages. Supporting cloud storage for DiskANN would require either:

  • A persistent "DiskANN file lives on a local cache disk that we sync from cloud" model (operationally heavy), or

  • A fundamentally different search algorithm with batched range reads (no longer DiskANN, really).

For the first DiskANN release, the activation conditions explicitly require storage.adapter === 'filesystem'. Cloud-storage users continue to use HNSW. We may revisit cloud support if there's demand and an approach that doesn't compromise the algorithm's strengths.

Decision 4 — Auto-engagement, zero configuration

When all of these conditions hold at brainy init, DiskANN replaces HNSW as the active index without any user config:

  1. Cor is loaded as a plugin (the index:diskann provider is registered)

  2. The storage adapter is FileSystemStorage (local SSD)

  3. The metadata index exposes a stable idMapper (the 2.4.0 #23 foundation)

This mirrors the existing MmapVectorBackend wiring pattern from 2.4.0 #24: the heavy machinery activates when its preconditions are met, and otherwise silently falls back. Users who don't want it can opt out via config.index.type = 'hnsw'.

Why auto-engage instead of opt-in by config:

  • Matches cor's "loading cor makes brainy faster" value proposition (no extra knob to turn)

  • The constraints (cor + filesystem) are exactly the deployment shape DiskANN targets, so the conditions ARE the signal

  • Opt-in-only would leave most filesystem-using cor installs on HNSW out of caution — defeating the point

Why not unconditional default:

  • Cloud-storage users have no DiskANN-compatible path; we can't break their existing HNSW workflows

  • Cor-less users (the brainy-only crowd) never see DiskANN regardless — preserves the "brainy works the same with or without cor" property

Decision 5 — Explicit migration API for existing installs

Existing brainy installs with an HNSW index on disk do not auto-migrate to DiskANN on upgrade. The on-disk HNSW state is detected at init; if config.index.type is unset, brainy logs:

[brainy] Existing HNSW index detected at <path>. The new cor default for filesystem storage is DiskANN. Continue using HNSW (set config.index.type='hnsw' to silence this message) or run brain.migrateToDiskAnn() to convert.

The migration API:

// Convert an existing HNSW index to DiskANN.
// Builds the DiskANN index in parallel (separate files), verifies recall
// parity at the configured threshold, then atomically swaps the active
// index. Reversible via brain.migrateToHnsw().
await brain.migrateToDiskAnn({
  recallTarget?: number,    // default 0.95 — verification target before swap
  paddingFactor?: number,   // default 1.2 — slack for re-ranking candidate set
  parallel?: boolean        // default true — build new index alongside live old
})

Reversibility (brain.migrateToHnsw()) is a contract, not a courtesy. Users need to be able to roll back if recall regression or any other issue surfaces in production.

Architecture

Brainy provider contract

Cor registers two new providers (mirrors the existing hnsw provider shape):

// brainy: src/plugin.ts
export interface DiskAnnProvider {
  create(config: DiskAnnConfig, distance: DistanceFunction, options: DiskAnnOptions): DiskAnnInstance
  openExisting(path: string, distance: DistanceFunction): DiskAnnInstance
}

export interface DiskAnnInstance extends HnswProvider {
  // Implements the same interface HNSWIndex/HnswProvider exposes, so the rest
  // of brainy doesn't care which index is active. Adds one DiskANN-specific
  // method for the migration API:
  rebuildPQCodebook(): Promise<void>  // Re-trains PQ from current vectors
}

The instance implementing HnswProvider is the load-bearing decision. brainy's search/find/get code paths call into the provider through this surface; an HNSWIndex and a NativeDiskANN are interchangeable from brainy's POV. No control-flow plumbing changes in brainy beyond the choice of which provider to instantiate.

Cor Rust modules

cor/native/src/diskann/
├── mod.rs        — napi exports + the NativeDiskANN class
├── vamana.rs     — α-pruning greedy graph construction (~500 LOC)
├── pq.rs         — Product Quantization codebook training + encode/decode
├── format.rs     — On-disk file format (header + PQ codebook + graph + vectors)
└── search.rs     — Greedy graph search with PQ-approximate distance + re-rank

On-disk file format

Single contiguous file <dataDir>/_diskann/main.bin (path mirrors _vectors/main.bin from #24):

+--------------------------------------------------------------+
| Header (4 KB, aligned)                                       |
|   magic: u32         "DKAN"                                  |
|   version: u32       layout revision                         |
|   dim: u32           vector dimensionality                   |
|   node_count: u32    total vectors                           |
|   pq_subspaces: u8   PQ M parameter (typically 8 or 16)      |
|   pq_bits: u8        bits per subspace (typically 8)         |
|   max_degree: u8     Vamana R parameter (typically 64-96)    |
|   entry_point: u32   slot id of the entry node               |
|   ... reserved bytes for forward compatibility ...           |
+--------------------------------------------------------------+
| PQ codebook (M × 256 × subvec_dim × f32)                     |
+--------------------------------------------------------------+
| PQ codes (node_count × M bytes)                              |
| — one PQ code per node, M bytes each, in slot order          |
+--------------------------------------------------------------+
| Vamana graph (node_count × max_degree × u32)                 |
| — flat CSR-like array of neighbour slot ids                  |
| — fixed degree per node for predictable offset math          |
+--------------------------------------------------------------+
| Full vectors (node_count × dim × f32)                        |
| — only touched for re-ranking the final candidate set        |
+--------------------------------------------------------------+

The fixed-degree Vamana graph trades a small density loss for O(1) neighbour-offset arithmetic. PQ codes pack tightly in RAM (M bytes per vector — at M=16 that's 16 bytes/vector regardless of dim, so 1B vectors fit in ~16 GB RAM for the PQ-resident layer).

Search algorithm

async function search(query: Vector, k: number): Promise<Result[]> {
  // 1. PQ-encode the query into M sub-vector codes
  const queryPq = pqEncode(query, codebook)

  // 2. Greedy graph walk using PQ-approximate distance
  const visited = new Set<u32>()
  const candidates = new BoundedHeap(maxLen = k * paddingFactor)
  let current = entryPoint

  while (improving(candidates)) {
    const neighbours = graph[current]
    for (const n of neighbours) {
      if (visited.has(n)) continue
      visited.add(n)
      const approxDist = pqDistance(queryPq, codes[n])
      candidates.insert(n, approxDist)
    }
    current = candidates.bestUnvisited()
  }

  // 3. Re-rank the top-(k * paddingFactor) candidates with full vectors
  const topCandidates = candidates.topN(k * paddingFactor)
  return topCandidates
    .map(n => ({ id: idMapper.getUuid(n), distance: trueDistance(query, vectors[n]) }))
    .sort()
    .slice(0, k)
}

The paddingFactor (default 1.2 = 20% over-fetch) controls the recall/cost tradeoff. PQ approximate distance is fast but lossy; re-ranking on the over-fetched candidate set with full-precision vectors recovers recall at a small cost (typically a few hundred extra full-vector reads per query, which is fine on SSD).

Implementation plan

Session 35a — Vamana + PQ in pure Rust (cor)

Scope (~3–5 hrs focused):

  • cor/native/src/diskann/vamana.rs — Vamana graph construction with α-pruning, ~500 LOC. Inputs: vector buffer, dim, R (max degree), α (density parameter, typically 1.2–1.4). Output: CSR adjacency.

  • cor/native/src/diskann/pq.rs — PQ codebook training (k-means on subvector partitions) + encode/decode. M subspaces × 256 centroids each, configurable.

  • cor/native/src/diskann/format.rs — On-disk file format struct + read/write primitives.

  • Rust unit tests: graph connectivity invariants, PQ recall on small synthetic dataset, format round-trip.

Exit criteria: Vamana graph build over 10k random vectors produces a connected graph with degree ≤ R, search recall ≥ 95% at k=10 on synthetic dataset.

Session 35b — Search + napi bindings (cor)

Scope (~3–5 hrs focused):

  • cor/native/src/diskann/search.rs — Greedy search with PQ-approximate distance and full-vector re-ranking on the candidate set.

  • cor/native/src/diskann/mod.rs — #[napi] exports of NativeDiskANN class with create / openExisting / addItem / search / rebuildPQCodebook methods.

  • cor/native/index.d.ts regeneration.

  • Recall validation against published DiskANN benchmark numbers (sanity check, not full BIGANN — that's a separate effort).

Exit criteria: Search recall ≥ 95% at k=10 over a 100k-vector dataset matches the published DiskANN paper's numbers within 2 percentage points.

Session 35c — Brainy hookup + cor 3.0.0 + brainy 8.0.0 release

Scope (~3–5 hrs focused):

  • brainy/src/hnsw/diskAnnIndex.ts — TS wrapper class implementing brainy's HnswProvider contract over NativeDiskANN. Same surface as HNSWIndex so the rest of brainy is agnostic.

  • brainy/src/brainy.ts — wireDiskAnn() private method that runs after wireMmapVectorBackend() during init. Auto-engagement conditions; opt-out via config.index.type = 'hnsw'.

  • brainy/src/plugin.ts — DiskAnnProvider and DiskAnnInstance interfaces (mirrors the VectorStoreMmapProvider pattern from 2.4.0 #24).

  • brain.migrateToDiskAnn() and brain.migrateToHnsw() explicit migration APIs.

  • Tests: provider hookup, auto-engagement conditions, opt-out, recall parity at 10k–100k vectors, migration round-trip integrity.

  • Coordinated release: cor 3.0.0 + brainy 8.0.0. Major bumps because the default index type changes for filesystem+cor users (semver discipline matters).

Exit criteria: Recall parity between brainy 8.0.0 + cor 3.0.0 DiskANN path and brainy 7.x + cortex 2.x HNSW path is within 1% at standard k values (1, 10, 50). Migration round-trip preserves index integrity.

Consequences

Positive

  • Single-machine billion-scale becomes a supported workload. At 100M to 1B vectors, RAM cost drops by ~16–20× compared to HNSW. NVMe disk locality replaces RAM pressure as the bottleneck.

  • Cor's "billion-scale via Rust acceleration" positioning becomes literal, not aspirational.

  • Zero impact to non-cor users. brainy keeps shipping its TS HNSWIndex; no API change, no behaviour change for them.

  • Foundations carry forward. The 2.4.0 storage work (stable IDs, mmap layer, graph compression) and 2.5.0 #30 (SQ4 quantization, the PQ precursor) all transfer.

  • License posture is clean. Pure Rust port from a published algorithm + permissive (MIT/Apache 2.0) Rust deps. No C++ FFI license entanglement.

  • Future-utility carry. The cor Rust compaction primitives (compute_bfs_order, compute_hnsw_traversal_order) stay in the codebase; if HNSW's disk locality ever becomes interesting again, the math is already there.

Negative / Tradeoffs

  • Build cost. DiskANN graph construction is slower than HNSW because Vamana's α-pruning requires examining more candidate neighbours per node. On 100M vectors this is hours, not minutes. Acceptable for once-per-deployment cost.

  • PQ recall ceiling. Product Quantization is lossy. Recall maxes out around 95–98% on typical embedding workloads; HNSW with full precision can reach 99%+. The re-ranking step recovers most of the gap. Users with extreme recall requirements (e.g., legal-discovery search) may want to stay on HNSW.

  • Filesystem-only constraint. Cloud-storage users get no benefit from DiskANN in the first release. We've accepted this; cloud DiskANN is a future investigation, not a commitment.

  • Major version bump. Auto-engagement changing the default index type for filesystem+cor users is a semver-major event. brainy 8.0.0 and cor 3.0.0 must coordinate. Some communication overhead at release time.

Risks

  • Correctness drift from the reference implementation. Vamana has subtle algorithmic choices (the α-pruning order, the entry-point selection strategy) that affect recall by small but real amounts. Mitigation: explicit recall validation against the published numbers + reference implementations in 35a and 35b's exit criteria.

  • Brainy provider contract surface mismatch. The HnswProvider interface was designed for HNSW; DiskANN may surface operations (codebook retraining, segment-level compaction) that don't fit cleanly. Mitigation: keep DiskAnnInstance as an extension of HnswProvider plus DiskANN-specific methods; never narrow the parent interface.

  • Migration API regressions. migrateToDiskAnn runs over potentially billions of vectors. A bug here could mean hours of wasted compute or, worse, an inconsistent index. Mitigation: parallel build (the old HNSW stays serving until the new DiskANN is validated), explicit recall verification before the atomic swap, fully reversible via migrateToHnsw.

  • Long-running PQ codebook drift. As vectors are added over time, the original PQ codebook can drift away from the data distribution, eroding recall. Mitigation: expose rebuildPQCodebook() for explicit retrains; document the operational guideline (retrain after the dataset doubles, or after a measurable recall regression).

Open questions

  1. PQ codebook strategy at scale. Do we train PQ once on a sample of the data, or use online/streaming PQ updates? Tradeoff: simpler vs. better recall over time. Lean toward sample-once-with-explicit-retrain to keep the operational model simple.

  2. Vamana parameters as runtime config vs. baked into the file format. R (max degree), α (density), the search candidate set padding factor — how much do we expose to users? Lean toward fixed-good-defaults in 3.0.0, expose later if a workload demands it.

  3. Filtered search support. brainy's find({ where, ... }) interacts with HNSW via a filter callback. DiskANN's PQ-distance loop needs different filter integration. Plan to defer — initial release supports unfiltered top-K search; filtered search is a follow-up.

  4. Multi-shard / single-node-of-cluster deployments. Cor isn't a cluster engine, but some users run multiple cor+brainy nodes behind a load balancer. Does each node need its own DiskANN file, or can they share one? Plan to defer — start with per-node files.

References

  • Subramanya et al., DiskANN: Fast Accurate Billion-Point Nearest Neighbor Search on a Single Node, NeurIPS 2019. arXiv:1907.07574

  • Singh et al., FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search, 2021. arXiv:2105.09613

  • Microsoft DiskANN open-source reference implementation: github.com/microsoft/DiskANN (MIT licensed)

  • ADR-001 — Native column store with raw mmap segments (the same architectural pattern of "cor registers a provider, brainy consumes when present")

  • Brainy 7.28.0 SQ4 quantization (the PQ precursor — scalar quantization scoped to a single vector; PQ extends the same idea to subvector partitions with learned codebooks)

  • Cortex 2.4.0 storage foundations: stable EntityIdMapper (#23), mmap vector backend (#24), graph link compression (#25), column-store interchange (#26)