Spec 0013 — Graph-Based ANN (Vamana / DiskANN family)

Status: Normative (v0.1). The reference implementation includes batch Vamana, compressed ADC with exact-source reranking (§4.4.1), exact-bound federation routing (§6), and explicit raw Fresh Vamana append/consolidation (0016 §4). 0009 §8.5.3 and dreamdb-conformance/vectors/0013/ pin the static graph format and scalar-canonical 10,000-node build/search artifacts. Those artifacts do not imply independent-implementation agreement for every later capability; portable incremental-build evidence remains OQ-70. No background scheduler or compressed Fresh writer is claimed. Depends on: spec/0001, spec/0002, spec/0004, spec/0007, spec/0010, spec/0012. Motivation: Graph traversal offers a different candidate-selection strategy from partition-based ANN. This document defines the static graph format and Vamana behavior, with the cross-shard routing contract resolving OQ-51. It does not establish a universal recall/cost advantage over IVF/PQ at a particular corpus size; comparisons require a pinned 0023 workload and report.

1. Purpose

DreamDB's spec/0004 partition algorithms answer "which cells does this query touch?" Graph algorithms answer a different question: "starting from a known entry point, which sequence of greedy local steps converges to the nearest neighbors?" The two are independently optimal — partition for selectivity-first, graph for recall-floor-first.

By the end of this document the following are concrete:

The graph-based SpatialIndex contract: an extension of spec/0004 §2 covering the entry-point + adjacency-list data model.
The GraphIndex Object: immutable, content-addressed CBOR Object that distributes the graph's metadata (R, alpha, entry point, page layout, seed).
The GraphPage Object kind: new on-disk format that holds a fixed-size batch of (node, vector, adjacency-list) tuples, page-aligned for I/O efficiency.
The Vamana algorithm (dreamdb.vamana-cosine): deterministic build + greedy search, suitable for 10B-scale.
The streaming-vs-batch build policy: how the graph is materialized at compaction time and (optionally) maintained incrementally.
The cross-shard routing layer: an exact-bound router GraphIndex over shards (§6), resolving OQ-51 in 0012.
The compression interop: supported 0010 compressors provide ADC candidates and direct exact-source reranking (§4.4.1); QINCo remains reserved.

What stays defined elsewhere:

SpatialIndex Object format / registry — spec/0004 §3.
Bucket-internal vector compression — spec/0010.
Federation Manifest format — spec/0012 §3.
HTTP backend contract — spec/0005.

What this document does NOT define:

Learned graph algorithms (NGT/PANNG, learned-edge-prune networks). Defer to v0.X+1 after Vamana ships.
Hybrid graph+partition (HNSW-style hierarchical graphs). Vamana is a single-layer R-regular graph; hierarchy is a future addition.
Per-query graph mutation (online graph update as a side-effect of queries). DreamDB's content layer is strictly immutable; graph updates produce new GraphPage Objects (§5).

2. Graph-SpatialIndex contract (extends spec/0004 §2)

A graph-based SpatialIndex differs from a partition-based one in that it does NOT produce a deterministic spatial key. Instead it produces a search trajectory: a sequence of (node-id, partial-distance) tuples that the SDK consumes as it walks the graph.

GraphSpatialIndex.search(query, k) →
  Stream<(node_id, vector_bytes, score)>     ;; yielded in approximate score order

The contract:

Determinism (§2.1 of spec/0004): for the same query, the same GraphIndex Object, the same fetched GraphPage bytes, two implementations MUST yield the same trajectory in the same order.
Distributability (§2.2 of spec/0004): the SDK MUST be able to reproduce the search from the GraphIndex Object + the GraphPage Objects alone.
Locality: greedy local steps MUST converge toward the global nearest neighbors. Vamana's α-pruning property gives a provable convergence bound (Subramanya et al. 2019, Thm 1); we restate the practical implication in §4.

Partition-based and graph-based algorithms register under the same algorithm registry (spec/0004 §3.4). A modality declares one or the other in its registry entry; the SDK dispatches accordingly.

3. The GraphIndex Object

Address path:

graph-index/<multihash-of-canonical-CBOR-bytes>

(New top-level namespace, parallel to spatial-index/, scalar-index/, vector-compressor/, federation-manifests/.)

3.1 CBOR encoding

{
  "algorithm":     "<algorithm-id>",            ;; "dreamdb.vamana-cosine"
  "dim":           <unsigned int>,              ;; vector dimensionality
  "metric":        "<metric-id>",               ;; "cosine"
  "embedding_spec_id": <multihash | omitted>,  ;; spec/0024; omitted only for legacy indexes
  "params":        <algorithm-specific>,        ;; §4 for Vamana; version is the form boundary
  "graph_layout": {
    "R":                  <unsigned int>,       ;; max out-degree (typical 32–64)
    "page_node_count":    <unsigned int>,       ;; nodes per GraphPage Object
    "page_bytes_target":  <unsigned int>,       ;; informational; ~64 KiB target
    "entry_point":        <unsigned int>,       ;; node-id of the search starting point
    "node_count":         <unsigned int>,       ;; total nodes in graph
    "vector_layout": {                          ;; how vectors appear inside GraphPages
      "compressor_hash":  <multihash | null>,   ;; null ⇒ raw f32; non-null ⇒ spec/0010 compressor
      "record_bytes":     <unsigned int>,       ;; per-node vector record size
    },
  },
  "shard_routing": <sub-Object>,                ;; present exactly in the v5 router profile (§6)
}

For Vamana, params.version = 1 is the legacy unidentified form and MUST omit embedding_spec_id; params.version = 2 is the identified form and MUST carry it. Every other combination is malformed. This version change is the critical- extension boundary required by 0002 §3.1.0: a pre-identity reader rejects version 2 before graph traversal instead of ignoring the new map key and silently searching vectors from an unknown embedding space.

Versions 3 and 4 are compressed successor profiles. Both require a non-null compressor_hash; embedding_spec_id may be present or absent, but MUST agree with the Schema and registry as in §3.4. Version 3 selects ADC-only ranking (Schema.rerank = false); version 4 selects exact-pool reranking (Schema.rerank = true, §4.4.1). Versions 1/2 retain their existing encoding and do not imply exact-source availability. Unsupported versions MUST be rejected before traversal. No new optional reference-bearing map key is added.

3.2 Reference from the Manifest registry

A modality using graph-based ANN declares it in the registry, parallel to spec/0004 §3.3:

"registry": {
  "embedding.f32.dim=768.graph.r=64": {
    "kind":              "continuous",
    "object_kind":       "graph-page",                    ;; NEW (this spec)
    "algorithm":         "dreamdb.vamana-cosine",
    "graph_index":       <multihash-GraphIndex-Object>,   ;; replaces spatial_index for graph-based
    "vector_compressor": <multihash-VC-Object | null>,    ;; optional, per spec/0010
  }
}

graph_index and spatial_index (spec/0004) are mutually exclusive in a single registry entry. A modality is partition-based OR graph-based, not both.

object_kind = "graph-page" is a distinct Track-index shape. Its inline and paged leaf entries are [page_hash] in page-index order. It MUST NOT be decoded as the unbucketed Item shape: an Unbucketed Item entry also carries a time anchor because its Object path is <timeline>/<modality>/<time-anchor>/<hash>, whereas a GraphPage lives at the literal graph-page/ path in §4.2. A time-range query against a GraphPage-list Track MUST refuse rather than return page hashes as if they were Items.

3.3 Modality-string parameterization

embedding.f32.dim=<D>[.spec=<spec_id>].graph.r=<R>

The .graph token replaces bucketed storage. The parameter key is lowercase r; the mathematical symbol and GraphIndex field remain R. Optional compression is bound by the registry/GraphIndex agreement in §3.4. The former .compress=<algo>:<param> proposal is withdrawn (0010 §4), not an alternative source of compressor identity or part of this valid tag example.

Example:

embedding.f32.dim=768.graph.r=64 — a 768-dimensional graph with maximum out-degree 64; consult its bound GraphIndex for vector storage.

3.4 Registry-vs-GraphIndex consistency (mandatory validation)

The SDK MUST validate at load time, parallel to spec/0004 §3.3.1 and spec/0010 §3.3:

Algorithm match: GraphIndex Object's algorithm equals registry algorithm.
Dimensionality / R consistency: GraphIndex Object's dim and graph_layout.R match modality parameters.
Vector layout: Schema compressor, registry vector_compressor, and GraphIndex vector_layout.compressor_hash MUST agree, including absence. The verified compressor MUST have the same dimension and cosine metric; record_bytes MUST equal its code_bytes (or 4 * dim without a compressor). page_node_count MUST be nonzero. GraphPage index, first node id, node count, record width, R and modality prefix MUST agree with the exact GraphIndex.
Entry-point validity: entry_point < node_count.
Embedding identity: an identified modality's spec parameter, registry embed_spec, and GraphIndex embedding_spec_id MUST agree. All three are absent for a legacy unidentified graph.

Mismatch ⇒ reject Manifest as malformed (ManifestCorrupted).

4. `dreamdb.vamana-cosine`

The flagship graph algorithm. Vamana (Subramanya et al. 2019) is a directed R-regular graph with α-pruned edge selection: starting from a random graph, two passes refine edges so that greedy search converges quickly.

4.1 Params (CBOR)

{
  "version":       1,
  "alpha":         <f32-as-bytes>,              ;; α-pruning factor (default 1.2)
  "build_seed":    <32 bytes>,                  ;; RNG seed for deterministic build
  "L_build":       <uint>,                      ;; search-list size during build (typical 100)
  "L_search":      <uint>,                      ;; default search-list size at query time (typical 100)
  "build_passes":  <uint>,                      ;; typically 2; 1 produces lower-quality graphs
}

4.2 GraphPage Object format

Each GraphPage holds page_node_count nodes. Layout:

┌──────────────────────────────────────────────────────────┐
│ GraphPage Header (192 bytes, fixed)                      │
│   magic:               4 bytes  = 0x47504755 ("GPGU")    │
│   version:             u32      = 1                       │
│   page_index:          u32      = 0-based page number     │
│   node_count_in_page:  u32      = nodes in this page      │
│   first_node_id:       u64      = first node-id in page   │
│   R:                   u32      = max out-degree (echo)   │
│   vector_record_bytes: u32      = per-node vector bytes   │
│   graph_index_hash:    33 bytes (multihash of the batch   │
│                         GraphIndex, or the lineage root   │
│                         for a Fresh snapshot — §4.2.1)    │
│   modality:            32-byte ASCII (zero-padded prefix) │
│   reserved:            remaining bytes = 0                │
├──────────────────────────────────────────────────────────┤
│ Node 0  (variable size; see below)                        │
│   time_anchor:    u64                                     │
│   vector_record:  vector_record_bytes bytes               │
│   adj_count:      u32                                     │
│   adj_list:       adj_count × u64 (node-ids)              │
├──────────────────────────────────────────────────────────┤
│ Node 1                                                    │
│ ...                                                       │
└──────────────────────────────────────────────────────────┘

Variable-size records (adj_count may vary per node) preclude pure positional indexing. The header's node_count_in_page plus a per-page offset table (appended after the last node) MAY be added in a follow-up if measurement shows it's needed; v0.X reads pages whole.

Address path:

<timeline>/<modality>/graph-page/<page-content-hash>

4.2.1 Page binding and Fresh lineage

For dreamdb.vamana-cosine, graph_index_hash retains its v1 meaning: it MUST equal the hash of the exact GraphIndex Object through which the page is being assembled. A mismatch is malformed and MUST NOT be ignored.

dreamdb.fresh-vamana-cosine uses the same field as a stable lineage-root binding, under that algorithm's recognisable parameter discriminant (0016 §4.1.1). Its root is an immutable batch dreamdb.vamana-cosine GraphIndex. The root's existing pages already carry that GraphIndex hash, so an incremental snapshot can reuse an unchanged page byte-for-byte. Every new or rewritten page in the Fresh lineage MUST put the same root hash in graph_index_hash.

This is not permission to accept an arbitrary old page. Before assembling a Fresh snapshot, a reader MUST validate the current GraphIndex against the root and the invariant family fields in 0016 §4.2.1, then require every selected page's graph_index_hash to equal that one validated root. Page indices, node ranges, and Track membership remain properties of the current snapshot. A page from another graph with identical algorithm parameters has a different root and is rejected.

The field remains reference-bearing. A semantic copier or collector that traverses GraphPages MUST treat it as a reference to the batch GraphIndex it names. The Fresh GraphIndex root reference adds closure and therefore lives behind the Fresh algorithm/parameter version boundary rather than an unknown-key compatibility hatch (0002 §3.1.0 and §3.1.4).

A node-id maps to (page-index, in-page-offset). The SDK consults the GraphIndex Object's graph_layout.page_node_count to compute the page-index for any node-id; the in-page-offset is found by scanning the page header forward (cheap — pages are typically 64 KiB).

4.3 Build algorithm (compaction-time)

Vamana is built during a special compaction phase (per spec/0006 §7.3's compaction verb). The build is deterministic given:

The set of input vectors (their content-addressed identity).
The GraphIndex Object's build_seed, L_build, alpha, build_passes.

Procedure:

Random init: every node has R out-edges to randomly chosen other nodes. Initialize ChaCha20 with build_seed as its 32-byte key, an all-zero 12-byte nonce and counter 0. Consume one continuous stream in ascending node-id order. Each candidate draw is the next 8 stream bytes interpreted as a little-endian u64, reduced modulo the node count; discard self ids and duplicates without rewinding the stream.
Pass 1 (alpha=1.0): for each node v in deterministic order (sorted by node-id): a. Greedy-search from entry_point (or current pass's entry point) toward v with search-list size L_build. b. The visited set V_v becomes the candidate edge set. c. α-prune: starting from the nearest candidate, add edges greedily; for each candidate c, accept iff no already-accepted edge c' satisfies dist(c, c') × α < dist(v, c). (At α=1.0 this is standard nearest-neighbor pruning.) d. Cap at R out-edges; if diversity pruning accepted fewer than R, fill in ascending (distance, node-id) order from the remaining candidates, including candidates rejected by the diversity test, until R or the candidate set is exhausted.
Pass 2 (alpha=user-supplied, default 1.2): repeat the pass with the user-supplied α. The diversity-boosting effect of α > 1 gives better recall at high L_search.
Materialize GraphPages: assign node-ids to pages in node-id order; emit each GraphPage Object.

Determinism notes:

entry_point MUST be deterministic. The convention: pick the medoid of the first 10,000 vectors (or all vectors if fewer); ties broken by smallest node-id. Approximate medoid (cheap to compute) suffices; full medoid is too expensive at 10B.
All inner-loop floating-point operations follow spec/0004 §5.4.1 discipline (scalar reference path, no FMA, no -ffast-math).
The build is single-threaded by spec. Parallel build is permitted ONLY if it produces bit-identical results (typically requires careful work-stealing with deterministic seed-propagation). Implementations that can't guarantee bit-identical parallel build MUST fall back to single-thread for conformance test vectors.

4.4 Search algorithm

At query time, given query vector q and target k:

visited = {entry_point}
candidates = MinHeap[(dist(q, entry_point), entry_point)]
results = MaxHeap[max-size=L_search][(dist(q, entry_point), entry_point)]
while candidates not empty:
  (d, v) = candidates.pop_min()
  if d > results.max_value() and len(results) == L_search: break
  v_page = fetch GraphPage covering v          ;; cached; spec/0005 §3.3
  for adj_node in v_page.adj_list_for(v):
    if adj_node in visited: continue
    visited.add(adj_node)
    adj_dist = dist(q, vector_for(adj_node))   ;; uses ADC (spec/0010 §5.1) if compressed
    candidates.push((adj_dist, adj_node))
    results.push_if_better((adj_dist, adj_node))
return results.top_k()

The entry point is both the initial frontier node and the first result candidate. Discovery is not a prerequisite for result membership: in a valid one-node graph with no edges, the loop discovers no neighbor and MUST still return the entry point for k >= 1. Implementations MUST NOT initialize results empty while putting the entry point only in candidates/visited; that shape incorrectly returns an empty result for the one-node case.

Per spec/0010 interop: when the GraphIndex references a vector_compressor, dist(q, vector_for(adj_node)) is computed via the ADC lookup table built once at query start.

Latency profile (1B-scale, R=64, compressed with QINCo M=8, L_search=100):

~150–300 hops per query (Vamana on 1B-scale; varies with α).
Each hop fetches one GraphPage (~64 KiB) — most are warm-cache after the first ~50 hops cover the relevant graph region.
Cold-start: ~50 cold GETs × ~50 ms over WAN = unacceptably slow.
Warm-cache: ~250 hops × ~50 µs of local memory access + ~50 µs ADC scoring = ~25 ms per query.

These are illustrative cache assumptions, not measured or mandatory latency bounds. An implementation may prefetch the entry-point region within its cache budget; neither a pinned K-hop neighborhood nor this latency target is a protocol conformance requirement. Query results must remain correct on a cold cache.

4.4.1 Exact reranking and compressed successors (OQ-56)

Dataset::compress_graph_index transforms an existing raw batch graph without changing node ids or adjacency. It publishes all encoded pages, the compressor, GraphIndex, Track, Schema and registry change under one optimistic Ref update. Its ordinary lineage edge names the exact raw predecessor binding, which remains in lineage, not query-active. The predecessor registry entry is retained. Recompression of a compressed predecessor is not supported.

For version 4, the immediate predecessor MUST be a raw version-1/2 GraphIndex of the same logical field, dimension, embedding identity, node count and page partition. It is the exact source, addressed by node id, not by time-anchor uniqueness. The source node's anchor MUST agree with the compressed node, and encoding its normalized vector with the bound compressor MUST reproduce that node's codes. Missing sources or contradictions MUST refuse; never return an approximate fallback under rerank = true.

Traversal uses a single query LUT and ADC for all compressed nodes. The retained beam has width max(L_search, top_k); tombstones remove ineligible result nodes before exact reads. The remaining beam is the rerank pool. Every pool member is rescored by deterministic cosine against the corresponding raw GraphPage record, then sorted descending with node-id tie breaks and truncated to top-k. No outside-pool candidate can return. This is a direct exact-vector read, not a second graph search, and makes no global exact-nearest-neighbor guarantee. Version 3 returns ADC ranking with approximate reconstructed vectors.

GC MUST retain registry GraphIndex roots as well as Track-listed GraphPages, for both active and lineage bindings. A GraphPage list does not itself mark its GraphIndex root. Collectors lacking this walk are unsafe even for raw graphs and MUST be upgraded before collecting a graph-containing retained root. No rerank_storage registry field is defined for graphs. Partition-based VS references remain per SpatialBucketEntry (0010), not per graph registry.

The first implementation trades storage for compatibility: retaining raw GraphPages retains their adjacency bytes too. Compression reduces vector bytes read during traversal, not total retained storage; selected exact pages are additional I/O. A compact exact-only sidecar would require its own future format and closure contract. audit_graph_index checks every node/page and, for version 4, its exact-source correspondence; ordinary traversal reads only visited and selected exact pages.

Rust, Python and WASM expose raw construction, compression, reopen/query and audit_graph_index / auditGraphIndex. The scored query path shares traversal and reranking with the batch path. Compound graph predicates, partition trace requests and IVF nprobe are explicitly unsupported; they MUST NOT be ignored or reported as an executed partition pre-filter plan.

4.5 Storage cost

For 1B nodes, R=64, dim=768 with QINCo M=8 compression:

Per node: 8 (anchor) + 8 (compressed vector) + 4 (adj_count) + 64×8 (adj_list) = 532 bytes.
Per page (256 nodes): 256 × 532 = ~133 KB raw, ~64 KiB after typical compression (zstd at REST is operator-layer).
Total storage: 1B × 532 B = 532 GB.

This is assumed payload arithmetic, not a measured codec ratio, recall result or deployment recommendation. 0010 §10's code-only total excludes anchors, indexes and retained exact sources, so comparing it with graph records is not a complete storage comparison. Graph-versus-partition choices and their recall must be measured under the same workload and environment (0023); QINCo remains a proposal, not an available baseline guaranteed by this specification.

5. Incremental updates (explicit raw Fresh Vamana)

DreamDB's content layer is strictly immutable. A streaming-update FreshDiskANN-style mechanism produces new GraphPage Objects per insertion, rewriting affected pages and reusing unaffected pages under §4.2.1's stable lineage-root binding. This is expensive (~kB-MB write amplification per insertion) but does not require rewriting the whole graph merely to refresh a snapshot hash.

The reference Dataset provides caller-driven raw Fresh append and id-preserving consolidation under 0016 §4 (#318). These operations publish new immutable snapshots; they do not install a background scheduler or promise out-of-core construction. Operators may still build a separate batch graph, but an auxiliary GraphIndex is not a Track and must use its field-qualified registry binding.

The storage binding for dreamdb.fresh-vamana-cosine is fixed by §4.2.1 and 0016 §4. Compressed Fresh construction remains a separate follow-up; an implementation that does not implement the Fresh algorithm MUST reject it rather than interpreting its pages with the batch current-snapshot rule.

6. Cross-shard routing (resolves OQ-51)

This section defines the federation-level routing mechanism implemented by the reference coordinator (#319). Static single-graph conformance alone does not establish this capability or independent-implementation agreement.

The scatter-gather model in spec/0012 §6.2 incurs O(N_shards × per-shard-query) work. For vector queries at extreme scale (10B+ across 100+ shards), this dominates. A graph-based router resolves it.

6.1 The router GraphIndex

A router uses dreamdb.vamana-cosine params version 5, with the CLOSED payload below. It is not a Dataset GraphPage index. Old decoders MUST reject the unknown version; shard_routing MUST NOT be added to an older profile. Every nested map of this profile is CLOSED. The outer map has exactly the five ordinary keys (algorithm, dim, metric, params, graph_layout), shard_routing, and optionally embedding_spec_id.

"shard_routing": {
  "field": <nonempty text>,
  "schema": <Federation shared Schema multihash>,
  "fanout": <u32>,
  "shards": [
    {
      "id": <logical shard id>,
      "manifest": <exact Dataset Manifest multihash>,
      "vector": <dim * 4 bytes, f32le>,
      "neighbors": [<u32 node id>, ...]
    },
    …
  ]
}

There is exactly one node per shard, in the Federation's canonical shard-id order; its ordinal is its node id. Every (id, manifest) and the schema commitment MUST match that exact Federation snapshot. Missing, foreign, duplicate or stale entries are malformed, even if the router's own hash is correct. No moving Ref participates in routing identity.

Vectors are finite unit representatives (squared binary64 norm within 1e-5 of 1); zero/nonfinite inputs are refused. Build normalizes finite input using a dimension-order binary64 sum and square root, then casts each quotient to f32. Representative quality is an operator assertion, not a certified centroid or a global recall guarantee. Neighbor ids are strictly increasing, in range, exclude self, and number at most R. fanout is in quorum..=len(shards).

Layout node_count == page_node_count == len(shards), page_bytes_target=0, entry point is in range, R is positive, and vector layout has exactly record_bytes=4*dim, with no compressor hash. All vectors and adjacency live inline in this GraphIndex: there are no router GraphPage objects. Params retain the six Vamana keys; alpha is finite and at least 1, build passes and L_build are positive, and L_search is at least fanout. This first profile is for small coordinator-resident graphs, not out-of-core routing.

Federation version 2 adds the required router multihash to its CLOSED map (0012 §3.1.1). It is a coordinator-local GC edge. The shard Manifest addresses repeat the Federation's remote bindings, not coordinator-local roots. Ordinary Dataset readers MUST reject the router profile.

6.2 Router-driven query path

1. Check field and embedding identity against the router; normalize finite q.
2. Greedy-search the inline Vamana graph with L_search and node-id tie breaks.
3. Select exactly fanout shards; refuse if traversal cannot supply that many.
4. Scatter queries to those selected shards ONLY (not all N).
5. Gather and merge per spec/0012 §6.1, without lowering quorum.

The public result MUST distinguish selected and intentionally pruned shard ids from selected shards whose replicas failed. partial continues to mean selected-shard unavailability, not global exact recall. A successful routed result is complete only over its declared selected scope. No-router vector queries still scatter to all shards; time-range queries retain scope routing. An identity mismatch or malformed router MUST NOT silently fall back to all shards or to another embedding space.

6.3 Router build and refresh

The coordinator builds from one supplied representative per shard using §4.3. It validates the exact snapshot binding before writing, makes the router durable, and publishes the Federation by its ordinary Ref CAS. A changed shard Manifest requires a new router binding and Federation snapshot, even if the representative stays identical. There is no time-based freshness exemption. Readers independently verify router bytes and binding at open; collectors retain routers for every retained Federation ancestor and refuse an incomplete closure before sweep. Router pages, automatic representative extraction, background refresh and compressed routing vectors are outside this profile.

7. Determinism conformance

The combination of f32 left-fold + scalar-reference (spec/0004 §5.4.1) + neural-MLP determinism (spec/0010 §7.3.1) covers most of what Vamana needs. Additional graph-specific requirements:

Build node order: ascending node-id. No exceptions; even parallel implementations process completion in this order.
Tiebreak in greedy search: when two candidates have identical distance, the smaller node-id wins. Ties at scale are rare but must be deterministic.
Random tiebreak in α-pruning: when α-prune evaluation has identical results for two candidates, the smaller node-id wins. (Not a random tiebreak — deterministic.)

The conformance suite (spec/0009 §8.5.3) ships a canonical reference corpus and complete graph (dim=64, 10,000 nodes, R=8), plus three search trajectories. The corpus is raw row-major f32le; the graph is fixed-width row-major u32le adjacency. Their vector record pins content hashes, dimensions, build parameters, entry point, final ordered search results and every expanded (node-id, cosine-score-bits) pair. This lets an independent implementation consume the inputs and expected outputs without linking the implementation that generated them.

8. Storage and latency at 10B-scale

Worked example. 10 backends, 1B vectors each, dim=768, QINCo M=8 + Vamana R=64.

Per-backend graph storage: 532 GB (per §4.5).
Total federation storage: 5.32 TB.
Cross-shard router: 10⁴ nodes × ~500 B = ~5 MB. Negligible.

Latency:

Cold-start at scale: ~30 ms for router-graph greedy (10⁴ nodes, all warm if router is pinned) + ~30 ms × K_router shards scatter (parallel) + ~30 ms gather/rerank = ~90 ms p50.
Warm-cache: ~25 ms total — the router fan-out reduction means we only contact 4–8 shards instead of 10.

Compared to spec/0012 §6.4 scatter-gather without router: ~40–100 ms p50 single-backend × N=10 = bounded by slowest shard, but p99 grows linearly with N. The router reduces effective N to K_router, dropping p99 proportionally.

9. Out of scope

HNSW (hierarchical small-world graphs). Vamana is single-layer; HNSW's multi-layer hierarchy is a different storage/latency tradeoff. Defer to v0.X+1.
Learned-edge graphs (NSG/SSG with learned pruning policies). Vamana's α-pruning is closed-form; learned variants require a training pipeline. Defer.
Graph-aware deletion. Vamana under v0.X is append-and-rebuild. Tombstone-based deletion is theoretically tractable; defer.
Concurrent build. v0.X is single-thread for conformance. A deterministic-parallel build is an open research question; defer.

10. Open questions

OQ-53 (→ this spec): GraphPage offset tables. The current variable-size record format requires scanning to find a specific node within a page. Add a per-page positional index? Defer until benchmarks show scan cost dominates.
OQ-54 (→ 0016): Streaming graph updates. Resolved: 0016 §4 defines dreamdb.fresh-vamana-cosine; the Dataset runtime provides raw-root incremental append, caller-driven consolidation, tombstone filtering and page-lineage reuse. Its initial writer is in-memory, not an out-of-core implementation. Compressed Fresh graphs and mid-iteration learned-graph approaches remain separate work.
OQ-55 (→ spec/0009): Resolved. dreamdb-conformance/vectors/0013/graph-build/002-* fixes the dim-64, 10,000-node, R=8 corpus, full adjacency and three complete build/search trajectories. Companion hashes and generation provenance are pinned in the JSON vector; an independent implementation needs only the documented raw f32le/u32le files.
OQ-56 (→ spec/0010): Resolved. §4.4.1 specifies direct exact-source reads for the selected candidate pool, not another graph search. The first graph implementation retains raw GraphPages through lineage; it does not introduce a graph-level VS reference or alter partition sidecars.

Next: spec/0014 — streaming/CMAF extensions for video at scale (or revisit chunking spec).