DreamDB Specification — 0004: Spatial Indexing

Status: Draft. Builds on 0000-overview.md, 0001-data-model.md, 0002-content-addressing.md, and 0003-time-encoding.md. This document defines the spatial-key derivation algorithm — how a feature vector becomes the bit string that occupies the <spatial-key> slot in an address (0002 §6.3). It resolves 0000 OQ-2.

1. Purpose

0000 Principle 3 says: retrieval is probabilistic localization, not scanning. 0002 defined the address slot for the spatial key (<spatial-key> segment, base2-encoded, N bits long). This document fills in the missing piece — the function that maps a feature vector to those N bits — and quantifies the locality property that makes the billion-scale benchmark feasible.

By the end of this document, the following are concrete:

• The SpatialIndex contract: signature and required properties of any function that computes spatial keys for a DreamDB modality.
• The SpatialIndex Object: the immutable, content-addressed byte format that distributes the function across writers and readers, so they all hash queries identically.
• The v0 default algorithm: LSH-cosine (random-hyperplane signature), specified precisely enough that two independent implementations produce bit-identical keys.
• The extensibility path: how future algorithms (PQ-IVF, learned hashing, etc.) plug in without breaking the address grammar or backend contract.
• The recall-widening strategy: prefix truncation as the v0 mechanism for trading bytes-fetched against recall.
• Quantified locality: collision probabilities and recall-vs-cost curves usable for sizing.

What stays as defined elsewhere:

• The <spatial-key> slot in the address grammar — 0002 §6.3.
• The base2 encoding of N-bit strings — 0002 §6.3.2.
• The Spatial-Bucket Object kind — 0001 §3.1, 0002 §7.4.2.
• Bucket sizing and the billion-scale target — 0000 §1, project_billion_scale_time.md.

What this document does not fix:

• The byte format inside Spatial Bucket Objects (packed-array layout, headers, per-vector encoding) — 0007.
• The per-modality Object index format (paged vs. inline, index page CBOR shape) — already in 0002 §7.3.
• Vector encoding standards beyond what the modality tag declares (embedding.f32.dim=N); the spec is agnostic to which model produced the vectors.

2. The SpatialIndex Contract

A SpatialIndex is a deterministic, distributable function that maps an input vector to an N-bit string:

SpatialIndex : Vector_D → BitString_N

where D is the input dimensionality (declared by the modality tag, e.g. dim=768) and N is the spatial-bucket-bit-length (declared by the modality tag, e.g. spatial_bits=18).

Every SpatialIndex MUST satisfy three properties:

2.1 Determinism

SpatialIndex(v) == SpatialIndex(v')   whenever v == v' bit-for-bit

Two implementations of the same SpatialIndex Object MUST produce bit-identical outputs for identical inputs. No tolerance for f32-vs-f64 drift, library-version differences, or platform-specific math. The conformance test suite (0009) MUST include a battery of input-output vectors that any conformant SpatialIndex implementation reproduces exactly.

This is a hard requirement, not a recommendation. A spatial-index implementation that "almost always agrees" is broken — addresses derived from disagreeing functions silently route to different buckets, and the protocol's content-addressed equality breaks.

2.2 Distributability

A SpatialIndex's full behavior MUST be reproducible from a small (typically KB to low-MB) immutable Object — the SpatialIndex Object (§3). No hidden state, no model registries, no environment variables. Hand the Object to any conformant SDK, and it can hash queries the same way the writer did.

2.3 Locality

Vectors that are "close" under the modality's similarity metric MUST be more likely to share a bit-prefix than vectors that are "far":

∀ v_a, v_b : sim(v_a, v_b) > sim(v_a, v_c)
              ⇒  E[ prefix-len(SpatialIndex(v_a), SpatialIndex(v_b)) ]
                 ≥ E[ prefix-len(SpatialIndex(v_a), SpatialIndex(v_c)) ]

(In words: for the metric appropriate to the modality, more-similar pairs are more likely to share longer prefixes than less-similar pairs.)

Concrete locality guarantees are algorithm-specific — see §5 for the v0 default's quantified bound. The contract just says one must be provided.

3. The SpatialIndex Object

A SpatialIndex Object is the immutable, content-addressed Object that distributes a SpatialIndex's full behavior. It is treated like any other DreamDB content-layer Object: deterministic CBOR, BLAKE3-256 hash, idempotent put-by-hash to the backend.

3.1 CBOR encoding

{
   "algorithm": "<algorithm-id>",                ;; e.g. "dreamdb.lsh-cosine"
   "dim":       <unsigned int>,                  ;; input dimensionality D
   "bits":      <unsigned int>,                  ;; output bit-length N
   "metric":    "<metric-id>",                   ;; e.g. "cosine", "l2"
   "params":    <algorithm-specific sub-Object>, ;; see §5 for v0 default
   "parents":   [<multihash>, ...],              ;; OPTIONAL; see §3.5
   "embedding_spec_id": <bstr(33)>,              ;; OPTIONAL; spec/0024
}

algorithm, dim, bits, metric, params are required. params shape depends on algorithm; readers MUST reject Objects whose params don't match the expected shape for the named algorithm.

parents is OPTIONAL and OMITTED-WHEN-EMPTY: an encoder MUST NOT emit the key when the parents list is empty. This preserves byte-identical encoding for SpatialIndex Objects created before this revision — their content hashes are unchanged. Decoders treat a missing parents field as the empty list, which means the SI has no ancestors (it stands alone, with strict lineage matching per 0007 §6.1.2).

embedding_spec_id is OPTIONAL for wire compatibility and MUST be omitted for a legacy embedding modality with no spec= identity. For an identified embedding modality it is REQUIRED and MUST equal the modality's spec_id (0024 §6.4). Index evolution, including Ada-IVF, MUST copy this identity to every descendant index; changing it is a new embedding modality and requires re-encoding the vectors, not an index-only update. Omission preserves the canonical bytes and content addresses of pre-0024 SpatialIndex Objects.

For each built-in algorithm, params version = 1 is the legacy unidentified form and MUST omit embedding_spec_id; 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 hashing a query instead of ignoring the new map key and searching an unknown embedding space.

3.2 Address

A SpatialIndex Object lives at the backend key:

spatial-index/<multihash-of-CBOR-bytes>

(In its own top-level namespace — like manifests/... in 0002 §7.2.4 — because a single SpatialIndex Object may be referenced by multiple Tracks across multiple Timelines.)

3.3 Reference from a Manifest

A modality that uses spatial bucketing (the embedding.* family with bucketed parameter) MUST declare its SpatialIndex Object hash(es) and the algorithm name in the Manifest's registry field (0002 §7.2 / §5.4):

"registry": {
   "embedding.f32.dim=768.bucketed.spatial_bits=18": {
      "kind":            "continuous",
      "object_kind":     "spatial-bucket",
      "algorithm":       "dreamdb.lsh-cosine",                         ;; algorithm name; MUST match every referenced SpatialIndex Object's algorithm field
      "spatial_index":   [<multihash-of-SpatialIndex-Object-0>, ...], ;; array; length = L (the `tables=L` modality parameter)
      "replicate_probes": <unsigned int>,                              ;; k; default 0 (no write-time replication)
   },
   ...
}

For single-table modalities (tables=1 or absent), spatial_index is a one-element array. For multi-table (§6.2), it carries L distinct SpatialIndex Object hashes — different seeds, otherwise identical parameters.

3.3.1 Registry-vs-SpatialIndex consistency (mandatory validation)

When the SDK fetches the SpatialIndex Object(s) for a modality, it MUST validate that:

1. Algorithm match: every fetched SpatialIndex Object's algorithm field equals the registry entry's algorithm value. Mismatch → reject Manifest as malformed (ManifestCorrupted error).
2. Multi-table parameter consistency (when L > 1): all L SpatialIndex Objects MUST agree on:
   • algorithm (same string)
   • dim (same input dimensionality)
   • bits (same output bit-length)
   • metric (same metric) They MAY differ only in params (typically the seed field that distinguishes tables). Any mismatch → reject Manifest as malformed.
3. Modality-tag-vs-spec-fields consistency: the modality's parameters (dim=N, spatial_bits=M, etc.) MUST match the SpatialIndex Object's dim and bits fields. A modality declaring dim=768 referencing a SpatialIndex with dim=512 is malformed.
4. Embedding identity consistency: a modality with spec=S MUST reference only SpatialIndex Objects whose embedding_spec_id is exactly S; a legacy modality without spec MUST reference only Objects that omit the field. Missing, unexpected or mismatching identity is malformed.

These checks are mandatory; an SDK that silently accepts inconsistent registries produces silent under-recall (vectors hashed by the wrong projection land in the wrong buckets and are never matched). The spatial_index_hash field in Bucket headers (per 0007 §6.1.1) provides a redundant per-Bucket check; the registry-level check above catches the same class of bug at Manifest-load time, which is earlier and clearer.

The reader, on encountering a Bucket Object address with a given modality, consults the Manifest's registry to find the SpatialIndex Object hashes, fetches the SpatialIndex Objects (L small GETs, cached for the session), validates per the rules above, and uses them to hash queries identically to how the writer hashed Items.

3.4 Algorithm identifier grammar

algorithm-id  := simple-id  |  namespaced-id
simple-id     := "dreamdb." <lower-alpha-snake>
namespaced-id := <reverse-dns> "." <lower-alpha-snake>

Built-in algorithms are reserved under the dreamdb. prefix. v0 defines:

Namespace back-compatibility. Built-in identifiers were historically written under the dreamdb. prefix (e.g. dreamdb.lsh-cosine). Writers now emit the canonical dreamdb. prefix, but readers MUST dual-accept the legacy dreamdb. prefix for any built-in identifier — the suffix after the first . is authoritative. Existing dreamdb.*-namespaced data therefore keeps reading correctly, and a Manifest MAY mix a legacy vortex.* registry binding with a freshly-written dreamdb.* index object.

dreamdb.lsh-cosine is the v0 default and the only algorithm v0 implementations are REQUIRED to support. dreamdb.ivf-cosine is OPTIONAL but RECOMMENDED for deployments with real-embedding data at ≤10⁵ effective cells. dreamdb.imi-cosine is the RECOMMENDED choice when the effective cell count would otherwise exceed ~10⁵ (typically beyond ~10⁸ vectors at constant cell size) — see §5.7 for the cost-vs-recall tradeoffs.

User-defined algorithms use reverse-DNS (com.example.myco.learned-hash) and MUST be declared in the Manifest's registry with sufficient detail for a reader to either dispatch to a known implementation or reject the Manifest as unsupported.

3.5 SpatialIndex lineage chain

parents declares the SpatialIndex Object(s) that the current SI evolved from. The dreamdb-cli ada-ivf-step and dreamdb-cli rebuild-ivf verbs SHOULD set parents = [<old-si-hash>] on every SI they publish.

parents is informational at the SpatialIndex level — it doesn't change spatial-key derivation — but it carries operational weight at the Bucket level: when an SI is published with non-empty parents, Bucket Objects placed under any ancestor SI MAY be reused under the new SI without rewriting, provided the bucket's centroid position is preserved between the ancestor and the descendant (see 0007 §6.1.2 for the lineage check rules).

3.5.1 Lineage Chain Semantics

A SpatialIndex's "lineage chain" is the transitive closure of parents walked depth-first. Each SI Object in the chain is one historical version of the index.

SI_3 (parents = [SI_2])
   └─► SI_2 (parents = [SI_1])
          └─► SI_1 (parents = [])     ;; root

In this chain, a Bucket Object whose header records spatial_index_hash = SI_1 (the root) is "lineage-valid" under SI_3 IF AND ONLY IF the centroid position it occupies in SI_1 has been preserved (unchanged centroid vector) through SI_2 and SI_3. The chain walk is the necessary condition; the per-cell centroid-preservation check is the sufficient condition.

3.5.2 Chain Length Cap

Implementations SHOULD cap chain walks at 100 ancestors to bound the lineage check cost on long-lived datasets. Beyond the cap, the chain is treated as truncated and strict equality applies (any older Bucket must be rewritten).

3.5.3 Multi-Parent SIs

parents is an array, not a single hash, so an SI MAY descend from multiple ancestors. This is the foundation for future multi-parent merge of feature branches (per 0008). v0 sets the array to a single element; multi-parent semantics are not defined for v0 readers, who MUST treat such SIs as having only their first parent as the chain (forward-compatible with future merge support).

4. The Spatial-Key Derivation Pipeline

For a writer hashing an item or a reader hashing a query:

                ┌──────────────────────────────┐
                │  Input vector v ∈ R^D        │
                └──────────────┬───────────────┘
                               │
      ┌────────────────────────▼──────────────────────────┐
      │   1. Pre-normalize v as required by the metric    │
      │      (e.g. for cosine: L2-normalize to unit ball) │
      └────────────────────────┬──────────────────────────┘
                               │
      ┌────────────────────────▼──────────────────────────┐
      │   2. Apply the algorithm's bit-derivation         │
      │      function with the SpatialIndex Object's     │
      │      params → produce N bits                      │
      └────────────────────────┬──────────────────────────┘
                               │
      ┌────────────────────────▼──────────────────────────┐
      │   3. Encode bits as base2 string per `0002` §6.3 │
      └────────────────────────┬──────────────────────────┘
                               │
      ┌────────────────────────▼──────────────────────────┐
      │   <spatial-key> ∈ {'0','1'}^N                     │
      └───────────────────────────────────────────────────┘

The pre-normalization step is metric-dependent: cosine metric requires unit-vector input; L2 metric does not. The algorithm-id implies the metric.

5. v0 Default Algorithm: dreamdb.lsh-cosine

dreamdb.lsh-cosine is the DreamDB v0 default and the only algorithm v0 implementations are required to support.

5.1 Mathematical definition

Given:

• An input vector v ∈ R^D, L2-normalized so ||v|| = 1.
• N hyperplanes, each a unit vector h_i ∈ R^D, generated by the deterministic normalized-cube procedure in §5.3. This distribution is part of the algorithm identity; it is not the uniform distribution on the unit sphere.

For each i ∈ {0, 1, ..., N-1}:

b_i = sign( <v, h_i> )      ;; 1 if dot product ≥ 0, else 0

(Convention: ties at <v, h_i> = 0 resolve to 1, making the function a total function on R^D.)

The output bit string is b_0 b_1 ... b_{N-1}, encoded as a base2 string in big-endian bit order — b_0 is the leftmost character of the spatial key.

5.2 Locality property and probability boundary

For a rotationally uniform random hyperplane, Charikar's result gives P[b_i(v_a) == b_i(v_b)] = 1 - θ/π. That result does not apply to dreamdb.lsh-cosine: §5.3 draws each coordinate uniformly from a bounded integer cube and then normalizes. Normalization changes length, not direction, so the resulting directions are not rotationally uniform.

A two-dimensional counterexample makes the distinction observable. Let v = (1, 0) and w = (√3/2, 1/2), whose angle is 30 degrees. For a continuous uniform draw from [-1, 1]^2, normalizing the draw leaves the signs of both dot products unchanged, and direct area calculation gives P[same sign] = 1 - tan(30°)/4 ≈ 0.855662. The spherical formula gives 5/6 ≈ 0.833333. The specified i32-to-f32 draw is discrete rather than continuous, but that does not turn the cube distribution into a rotationally uniform one.

The algorithm still provides deterministic hyperplane partitioning and nearby vectors will ordinarily share more bits than distant vectors. This revision does not assign an exact angle-only collision probability, expected prefix length, or recall guarantee to that heuristic. Deployments MUST size prefix, table, and probe parameters from measurements made with this exact generator and their representative data. Changing to a rotationally uniform generator would require a new algorithm identity and a migration; implementations MUST NOT change the existing seed-to-hyperplane mapping in place.

5.3 Hyperplane generation from a seed

The params sub-Object is:

{
   "version": 1,                              ;; format version
   "seed":    h'<32 bytes>',                  ;; 256-bit seed
}

Hyperplanes are not stored directly — they are regenerated deterministically from the seed by every implementation. Storing 18 hyperplanes of dim 768 would be ~55 KB (small but unnecessary); storing the seed is ~32 bytes.

The deterministic generation procedure is fixed:

1. Initialize a ChaCha20 stream cipher with the 32-byte seed as key, all-zero 12-byte nonce, counter 0. (ChaCha20 chosen because it is fast, has a clear specification, and is widely available across language runtimes — Rust's chacha20, Go's crypto/chacha20, Python's cryptography.)
2. For each hyperplane index i ∈ {0, ..., N-1}: a. Generate D × 4 bytes of keystream from ChaCha20 (each hyperplane consumes D × 4 bytes regardless of byte order; deterministic continuation). b. Interpret each consecutive 4 bytes as a little-endian signed 32-bit integer n, then convert to a bounded f32 via n_as_f32 = (n as f32) / 2147483648.0 (= 2³¹). This gives each element a finite f32 in approximately [-1.0, 1.0]. The vector g_i ∈ R^D is the D such values. Rationale: interpreting raw bytes as IEEE 754 binary32 directly admits NaN, infinity, and astronomically-large finite values that overflow the L2-norm sum-of-squares for typical D. The integer-then-scale path produces bounded, always-finite f32 values. It deliberately preserves the published generator; it does not claim spherical uniformity. c. Compute h_i = g_i / ||g_i|| (L2-normalize). If ||g_i|| = 0 (only possible if D consecutive 4-byte windows all happen to be 0x00000000, which ChaCha20 doesn't produce in practice), advance the keystream by D × 4 more bytes and retry.

The normalized vector lies on the unit sphere, but its direction is the projection of a cube distribution and is not uniform on that sphere. A Gaussian-coordinate generator would be rotationally uniform, but replacing the published generator would change spatial keys and therefore requires a new algorithm identity rather than an in-place correction.

Implementations MUST use this exact procedure. Conformance test vectors (0009) include known-seed → known-hyperplanes round-trips.

5.4 Floating-point determinism

LSH-cosine involves f32 arithmetic. Implementations MUST treat this carefully:

• Vectors are encoded as binary32 (IEEE 754 single-precision, little-endian) per the modality tag (embedding.f32.*).
• Inner products <v, h_i> MUST be computed via a deterministic order — naïve left-fold over the dimensions, accumulating in f32. Higher-precision intermediate (f64) accumulators are FORBIDDEN, since they introduce platform-dependent rounding.
• The ChaCha20 keystream is bit-deterministic; the byte-to-f32 conversion is bit-deterministic. The only platform-specific step is the L2-norm and the subsequent dot-product fold; the spec pins f32 left-fold to remove ambiguity.

This is a tighter constraint than 0003 §4.1's no-f64-on-time-axis rule, because here we deliberately use f32 for vector math (it's how embeddings are sized for storage). The discipline is: f32 in, f32 out, deterministic accumulation order, no f64 widening.

5.4.1 Compiler-flag discipline (mandatory)

f32 left-fold determinism is necessary but not sufficient on its own. Compilers and CPUs have several subtle re-orderings that can produce divergent bits even on the "same" left-fold instruction stream:

• Floating-point contraction (a × b + c fused to a single fma instruction): produces a different result than separate multiply + add because fma rounds once instead of twice. LLVM's contraction is enabled by default on some platforms.
• Implicit FMA under -O2 / -O3: even without -ffast-math, some compilers fuse multiply-adds opportunistically.
• -ffast-math and equivalents: enable algebraic re-association (a + b + c → c + b + a) that breaks left-fold semantics. MUST be disabled.
• CPU microarchitecture variation: same instruction stream can produce different bits across Skylake AVX-2 vs. Zen-3 AVX-2 in extreme corners (rare but observable).

Conformant implementations MUST:

1. Disable floating-point contraction on every f32 path in the spatial-index pipeline. In Rust: #[no_implicit_fma] (when stabilized) or compile with -C llvm-args=-fp-contract=off. In C/C++: #pragma STDC FP_CONTRACT OFF or -ffp-contract=off. In Python: use a soft-float library; never trust NumPy's f32 path for canonical reference.
2. Forbid -ffast-math, --unsafe-fp-math, and equivalents on any code path producing a DreamDB spatial key.
3. Implement the canonical scalar path explicitly — no SIMD intrinsics, no auto-vectorization. This path is the bit-exact reference per 0009 §5.3.1.
4. Test against the canonical path on every supported architecture (x86-64 AVX-512/AVX2/scalar; ARM64 NEON/scalar) — see 0009 §5.3.1 for the conformance battery.

For the canonical scalar reference: implementations SHOULD use a soft-float library (e.g. softfloat-rs, MPFR with binary32 precision) to produce vectors that are bit-exact regardless of host CPU. Hardware-f32 paths verify against the soft-float reference.

Without this discipline, two implementations on different hosts will produce different bits for some vectors and silently route them to different Spatial Buckets. The class of bugs is exactly what content-addressing's strong-consistency story exists to prevent — but only if implementations honor it on the f32 side.

Conformance test vectors include cases sensitive to f32 rounding-order to verify implementations match.

5.5 Why LSH-cosine for v0 and not something stronger

LSH-cosine is not the highest-recall spatial-index algorithm. PQ-IVF (FAISS-style) and learned hashing both achieve significantly better recall per byte fetched at billion-scale. Why is dreamdb.lsh-cosine the v0 default?

• No training data required. A writer publishing the first track on a Timeline cannot run k-means over 1B vectors that don't yet exist. LSH parameters are seeded; no fitting step.
• Algorithmic clarity. The seed-to-hyperplane mapping and sign partition are small and deterministic. Unlike rotationally uniform hyperplane LSH, this generator has no angle-only closed-form sizing rule; deployments use the measured profiles required by §5.2.
• Implementation simplicity. A conformant LSH-cosine implementation is ~200 lines of Rust. PQ-IVF requires a quantizer, a residual-quantizer training pipeline, an asymmetric distance computation, and a much larger params blob.
• Forward compatibility. The algorithm registry in §3.4 makes PQ-IVF, learned hashing, etc. plug-in additions to the spec without breaking the address grammar or backend contract. Future spec versions ship them under dreamdb.pq-ivf, dreamdb.learned-mlp-v1, etc.

The billion-scale benchmark with dreamdb.lsh-cosine will not match FAISS-IVF-PQ on recall — but it will match within a factor of 2-3× and is the right choice to ship a clean, reference-quality v0. Production deployments wanting higher recall can use a v0.1+ algorithm without changing anything about the data model or address grammar.

5.6 Extension Algorithm: dreamdb.ivf-cosine

dreamdb.ivf-cosine is an OPTIONAL extension that partitions the vector space via k-means centroids rather than random hyperplanes. It is the highest-recall algorithm v0 implementations are documented to support and is RECOMMENDED for deployments with real-embedding data (where natural cluster structure exists).

On SIFT-1M with k=1024, dreamdb.ivf-cosine at nprobe=32 reaches recall@10 = 0.97 versus dreamdb.lsh-cosine's 0.88 at the same probe budget — a 9-percentage-point lift, matching the faiss IndexIVFFlat reference within 0.001.

5.6.1 Params (CBOR)

{
  "version":   1,                    ;; format version, fixed at 1 for v0
  "k":         <uint>,               ;; centroid count (≥ 2)
  "centroids": <byte-string>,        ;; k × dim LE-f32 bytes, row-major
}

The SpatialIndex Object's outer bits field MUST equal ceil(log2(k)) — this is the spatial-key width needed to encode every centroid id. Decoders reject mismatches with BitsTooNarrow.

Centroids on the wire are not required to be unit-norm; decoders MUST L2-renormalize on load (defense-in-depth — a malformed producer cannot break the cosine semantics for downstream readers).

5.6.2 Mathematical definition

Given:

• An input vector v ∈ R^D, L2-normalized so ||v|| = 1.
• A trained centroid set C = {c_0, c_1, …, c_{k-1}}, each L2-renormalized to unit length on load.

The spatial key is the id of the nearest centroid by cosine similarity:

id     = argmax_{i ∈ [0,k)} <v, c_i>
        (ties: smaller id wins)

bits   = id_to_msb_bits(id, ceil(log2(k)))
         ;; bit 0 = MSB of id; bit (bits-1) = LSB of id

For unit vectors, argmax dot product equals argmin angular distance equals argmin L2 distance — the algorithm is exact-equivalent to nearest-centroid in any of those metrics.

5.6.3 Multi-probe

Multi-probe IVF returns the top nprobe centroids by descending dot product (not Hamming-distance flips, which are an LSH-specific concept). The max_hamming_distance parameter accepted by the verb layer is documented as ignored by dreamdb.ivf-cosine implementations — accepted for API parity with dreamdb.lsh-cosine only.

Probe ordering: descending by <v, c_i>, ties broken by ascending id. Returns are deduplicated by spatial key (which can't collide given each centroid maps to a distinct id).

5.6.4 Floating-point determinism

dreamdb.ivf-cosine implementations MUST honor the same f32 discipline as dreamdb.lsh-cosine (§5.4):

• Left-fold accumulator for dot products.
• No FMA / fp-contract.
• Bit-identical scalar reference per architecture; SIMD paths MUST verify against the scalar reference on every supported architecture.

The hot path is k × D multiplies per query (versus bits × D for LSH) — meaningfully more arithmetic, but identical in its determinism requirements.

5.6.5 Training and the centroid-publication contract

Unlike dreamdb.lsh-cosine (where hyperplanes derive from a seed and need no training data), dreamdb.ivf-cosine requires a centroid set. This raises a coordination problem for multi-writer timelines: writers MUST agree on the centroid set, or their writes go into incompatible spatial keys.

The protocol resolves this via SpatialIndex-Object immutability:

1. One writer trains and publishes the SpatialIndexObject (Genesis-time or first-write). The SI Object's address — its content hash — is the algorithm's identity on this timeline.
2. Subsequent writers fetch and consume. Reading the Manifest yields the spatial_index_hash; fetching that Object yields the centroids; the local algorithm instance is then trivially consistent with the publishing writer's hashes.
3. No re-training mid-Track. A second-generation centroid set (e.g. trained after data drift) MUST go into a new SpatialIndex Object referenced from a new Track — see spec/0008 on Track layering. Mutating an existing SI Object is FORBIDDEN.

For the training step, implementations are RECOMMENDED to use spherical k-means with k-means++ initialization, with the following determinism guarantees:

• A canonical sample-selection rule (the obvious one: the first pca_sample_size vectors of the dataset) plus a fixed RNG seed plus fixed iteration count MUST produce byte-identical centroids across implementations and architectures.
• The scalar reference is the bit-exact source of truth; vectorized training paths MUST verify against it.

This deterministic-training contract is what makes "two writers train independently and arrive at the same SI Object" tractable. Multi-writer ceremonies that don't want to rely on this can instead designate one bootstrapper and have subsequent writers fetch — the protocol allows either pattern.

5.6.6 Sizing guidance

• k: O(sqrt(N)) is the standard k-means rule of thumb. k=1024 for N=1M; scale up to k=32K for N=1B.
• nprobe: trade recall for cost. nprobe=k/32 ≈ 0.95 recall@10 on typical embedding data; nprobe=k/16 ≈ 0.97; nprobe=k/8 ≈ 0.99.
• sample size for training: 100K vectors covers dim ≤ 1024 adequately. More samples don't materially change centroids on real-embedding data (the population already plateaus the covariance).
• iterations: 20 Lloyd iterations suffice for real-embedding data; SIFT-1M centroids stabilize by iteration 10.

5.6.1 Independent IVF + PQ composition (OQ-25)

No combined dreamdb.pq-ivf discriminator is needed for the implemented global-vector cosine PQ contract. Bind a dreamdb.ivf-cosine SpatialIndex and a dreamdb.pq-cosine VectorCompressor independently through Schema's spatial_index and compressor references. Both objects must have the field's dimension and cosine metric; the existing registry/header lineage binds their content addresses. A different partitioner or compressor is a different published binding, not an in-place reinterpretation of existing codes.

The IVF partitioner routes the original vector to a centroid; the PQ compressor encodes that same vector's contiguous subspaces. No IVF centroid is subtracted. Training samples are unit-normalized global vectors, and PQ training is not per-IVF-cell residual training. Probe selection uses IVF query/centroid scores; candidate ranking uses PQ's query lookup/ADC rules (0010 §11.1), with optional whole-pool exact reranking through the existing raw exact sources (0010 §5). This must not be described as residual IVF-PQ or as equivalent to a named FAISS configuration. Such a variant would require a separate concrete contract.

The public create/append/reopen/query test ivf_pq_composition.rs trains both objects, persists both references, probes all four cells and compares a fully admitted exact pool against brute force. It proves composition is usable, not an ANN recall/speed improvement. The bundled reference trainers provide small deterministic test codebooks; production training quality remains operator policy.

5.7 Extension Algorithm: dreamdb.imi-cosine

dreamdb.imi-cosine (Inverted Multi-Index, Babenko & Lempitsky 2012) is the algorithm of choice when the effective cell count k_total would otherwise exceed ~10⁵. It maps onto the same DreamDB primitives as dreamdb.ivf-cosine (one Spatial Bucket per cell, content-addressed VS Object for vector data) but factors the partitioning into two independent half-codebooks of size k_sub, giving k_sub² effective cells.

The structural problem IMI solves: at billion-scale with linear-k sizing (one cell per ~1000 vectors), pure IVF needs k_total ≈ 10⁶ centroids. Per-query argmax over 10⁶ centroids is ~30 ms scalar — it BECOMES the dominant query latency, breaking the scale-independent-latency promise. IMI's cost reduces to O(2·k_sub) = O(2·√k_total): the same 10⁶-effective-cell index needs only 2 × 1000 = 2000 centroid distances per query, on the order of 60 µs.

The same factorization applies to per-vector ingest hashing (the dominant cost during write). At billion scale, the O(N) ingest improvement compounds into days saved.

5.7.1 Params (CBOR)

{
  "version":         1,                       ;; format version, fixed at 1 for v0
  "k_sub":           <uint>,                  ;; per-half centroid count (≥ 2)
  "centroids_high":  <byte-string>,           ;; k_sub × (dim/2) LE-f32 bytes, row-major
  "centroids_low":   <byte-string>,           ;; k_sub × (dim/2) LE-f32 bytes, row-major
}

The SpatialIndex Object's outer bits field MUST equal 2 × ceil(log2(k_sub)) — the spatial-key width needed to encode the combined (id_high, id_low) cell id. The outer dim field MUST be even (the half-split convention requires it).

5.7.2 Mathematical definition

Given:

• An input vector v ∈ R^D, L2-normalized so ||v|| = 1.
• Two half-codebooks C_high = {c_h_0, …, c_h_{k_sub-1}} and C_low = {c_l_0, …, c_l_{k_sub-1}}, each unit-renormalized on load.

Split v into v_high = v[0..D/2] and v_low = v[D/2..D]. Note that v_high and v_low are NOT individually unit-norm — they're literal slices of the unit-normalized full vector. This matters: the asymmetric distance computation

score(v, cell(i,j))  =  <v_high, c_h_i> + <v_low, c_l_j>
                     =  <v, [c_h_i, c_l_j]>

holds exactly because dot products distribute over concatenation. The cell selected is

(id_high, id_low)  =  ( argmax_i <v_high, c_h_i>,
                        argmax_j <v_low,  c_l_j> )

cell_id            =  id_high · k_sub + id_low

bits               =  id_to_msb_bits(cell_id, 2 · ceil(log2(k_sub)))

5.7.3 Multi-probe via the multi-sequence algorithm

Naïve "enumerate all k_sub² cells and sort" is too expensive at large k_sub (e.g. 10⁶ enumerations at k_sub = 1000). The standard solution (Babenko & Lempitsky §4) is the multi-sequence algorithm:

1. Sort the per-half dot products independently — k_sub log k_sub cost per half.
2. Maintain a min-heap of grid coordinates (h, l) ordered by dots_high_sorted[h] + dots_low_sorted[l] descending.
3. Pop the top, emit its cell, then push (h+1, l) and (h, l+1) if not yet visited.
4. Repeat nprobe times.

This yields the top-nprobe cells in O(nprobe · log nprobe) time without enumerating all k_sub² pairs. The reference implementation in dreamdb-protocol/src/imi_cosine.rs follows this scheme exactly.

5.7.4 Floating-point determinism

Identical to dreamdb.lsh-cosine and dreamdb.ivf-cosine (§5.4): left-fold dot product, no FMA, scalar reference path. SIMD paths MUST verify against the scalar reference per-architecture. Tiebreak rules: argmax breaks ties to the smaller centroid id; the multi-sequence heap breaks score ties by ascending (h_grid, l_grid). Both are bit-deterministic.

5.7.5 Training and the centroid-publication contract

Same as dreamdb.ivf-cosine (§5.6.5) — a single writer trains, publishes the SI Object, others fetch and consume. The training procedure is two independent spherical-k-means runs, one per half:

1. Sample N vectors and split each into half-vectors (v_high, v_low).
2. Run k-means independently on the two halves with derived seeds (seed, seed ^ HALF_MIX) so the two passes don't share RNG state.
3. Each half-pass is byte-deterministic given fixed inputs (sample, seed, iteration count) — multi-writer reproducibility is preserved.

5.7.6 When IMI vs IVF

The decision is governed by per-query and per-vector hash cost, not recall (both algorithms hit similar recall on real-embedding data at matched effective cell counts):

There is no recall reason to prefer IMI at small k. The centroid factorization introduces a small (~1-3 percentage point) recall cost vs full IVF at matched k_total because half-codebooks can't model joint correlations between the two halves of the input. For deployments where every recall point matters, stick with IVF as long as the cell budget is small enough to make centroid-scan latency acceptable.

5.8 L2 projection LSH (dreamdb.lsh-l2)

This optional algorithm preserves vector magnitude. Its metric is l2, its SpatialKey width is exactly 64, and its params are a CLOSED map of exactly version: uint, seed: bstr(32), bucket_width_f64le: bstr(8). Width is an IEEE-754 binary64 little-endian bit pattern, finite and strictly positive. Version 1 has no embedding_spec_id; version 2 requires it, following §3's identity-bearing index contract. Other versions, metric/algorithm mismatches, wrong key width, zero dimension and malformed params MUST be rejected. These are new algorithm-discriminated bytes, not a reinterpretation of any cosine index. Unsupported implementations MUST refuse them.

Seeded projection. Initialize ChaCha20 with the 32-byte seed and zero 12-byte nonce. Consume dim successive little-endian signed i32 values, widen each to binary64 and divide by 2^31. Sum their squares in dimension order, take the square root, and divide each component by that norm. If all components are zero, consume another dim values and repeat. Consume the next little-endian u32, divide by 2^32, then multiply by bucket width to obtain the offset. This is one seeded unit projection, not a claim of Gaussian or isotropic projections, nor a production recall guarantee.

Hashing. Input components are finite binary32 values of exactly dim. Do NOT normalize the input. Compute the projection dot product in ascending dimension order, widen each input to binary64, add the offset, and divide by width. Refuse nonfinite results or a position outside [-2^63, 2^63); floor the position to signed i64. Encode its two's-complement u64 bits XOR 2^63 as an MSB-first 64-bit SpatialKey. Thus key order is signed-bin order.

Probes. Emit the primary bin first. Let f = position - floor(position). The next left/right interval distances start at f / 1-f. Emit the side with smaller distance, ties to the smaller signed bin; advance that side by one checked bin and increase its distance by one. Never wrap at i64 limits. Stop after the requested number of probes. Hamming-distance options have no meaning for this algorithm and do not constrain its interval probes.

Arithmetic. Every projection, norm, division and distance step uses binary64 round-to-nearest-ties-to-even, dimension-order scalar left folds, no FMA, reassociation, extended precision or fast-math. SIMD implementations must agree with that scalar sequence. Candidate score is negative squared Euclidean distance: sum (q[d] - v[d])^2 in binary64, round once to binary32, then negate. Reject a nonfinite input or a squared distance not representable as finite binary32; do not replace it by negative infinity. Equal scores are ordered by ascending anchor. These scores are exact for the retrieved raw candidate vectors up to the specified rounding, not global exact NN search.

Binding and SDK profile. L2 fields use algorithm dreamdb.lsh-l2 and embedding.f32.dim=D.metric=l2[.spec=ID].bucketed with the existing capacity and version suffixes. Schema, registry and every SpatialIndex table MUST agree on algorithm, metric and dimension. Mixing cosine and L2 tables is malformed and MUST fail before ranking. Joint filters with multiple Vector clauses remain unsupported, including mixed-metric ones; no cross-metric score fusion is implied. Cosine modalities retain their exact old spelling.

The Dataset/Python/WASM raw-only profile builds a default width-1 index when the Schema algorithm is dreamdb.lsh-l2; an explicit, verified SpatialIndex hash can supply a different width. lsh_bits is absent or 64. Compression, cosine rerank sidecars and compressed embedding-layer APIs are unsupported for this profile and MUST refuse, not normalize silently. Ordinary append, reopen, query and compaction preserve raw vectors and the index binding. The SDK defaults rerank to false for L2. Multi-table routing may only combine matching L2 profiles; global recall, out-of-core building and cell occupancy bounds are not claims of this first single-projection profile.

6. Recall-Widening Strategies

Single-table LSH-cosine can have limited recall at meaningful angular separations. Its exact recall is data- and orientation-dependent under the normalized-cube generator (§5.2), so it MUST be measured rather than derived from the spherical-hyperplane formula. v0 supports four independent recall-widening levers that compose; modalities choose which to enable via parameters.

Lever priority — correction 2026-05 (added after empirical sweep at dreamdb-bench/reports/sweep-*.json): the 2026 spec elevated read-time multi-probe (Lever 4, §6.4) from "implementation-defined query-side technique" to a first-class lever. Empirically, at fixed per-query work (~16 cells fetched), tables=1 + max_hamming=2 + probe_count=16 strictly Pareto-dominates tables=4 + max_hamming=1 + probe_count=4 on recall, latency, AND storage. The new default ordering is: tune max_hamming and probe_count first; reach for tables>1 only when read-time probing is insufficient.

6.1 Lever 1: Prefix truncation (always available)

The SDK truncates the query's spatial key to M < N bits and issues a list-prefix (or, on the hot path, scans the cached object_index for matching prefixes — see §7.3):

list-prefix( <timeline> / <modality> / <first-M-chars-of-spatial-key> )

returns all bucket Objects whose spatial keys begin with the M-char prefix — up to 2^(N-M) buckets. Fetch all of them, run exact comparison locally on the union.

The number of buckets selected by an M-bit prefix is structural and exact; the recall is not:

Only M=0 has a distribution-independent 100% candidate-recall guarantee. All other prefix choices require empirical calibration with the specified generator and the deployment's data.

6.2 Lever 2: Multi-table LSH (tables=L modality parameter)

A modality declares tables=L (e.g. embedding.f32.dim=768.bucketed.spatial_bits=18.tables=4) to opt into multi-table LSH. Writers hash each Item with L independent SpatialIndex Objects (different seeds) and place L bucket-index entries per Item. Readers query each table at the same M and union the candidate sets.

If an empirical calibration establishes independent per-table hit probability p for a fixed workload, the union probability is 1 - (1 - p)^L. This is a conditional composition rule, not an angle-only value supplied by this spec; p MUST NOT be substituted from 1 - θ/π for this generator.

Crucial point on storage cost: vector bytes are content-addressed and stored once. Bucket Objects in multi-table mode use byte-range references (per 0007's decoupled storage layout; OQ-23) rather than inlining the vector bytes — so additional tables only multiply the index entries (~50 B per entry), not the underlying ~3 KB vector bytes.

For a 1B-vector track with dim=768 and L=4:

• Vector byte storage: 1B × 3 KB = 3 TB (single-copy)
• Bucket index entries: 1B × 4 × ~50 B = ~200 GB (4× the single-table index)
• Total ~3.2 TB vs. 3.0 TB single-table — about 7% ingest-time storage premium; recall improvement must be measured.

The reader's L SpatialIndex Objects are listed in the modality's registry entry as an array. Each table is a separate tables_id ∈ {0, …, L-1} dimension in the address grammar (per 0002 §7.3.1 spatial-bucket index entries).

6.2.1 Storage caveat: the 7% premium is the un-compacted figure

The "1B × 4 × 50 B = ~200 GB" calculation above describes the storage at ingest time, when reference-mode buckets carry references into a single shared per-Track Vector-Storage Object (per 0007 §6.2). It does NOT describe the storage after compaction (per 0006 §7.3).

Compaction rewrites each (table_id, spatial_key) cell into its own per-cell Vector-Storage Object so query bytes are contiguous. With L>1, each vector is in L cells (one per table) and therefore lands in L separate per-cell VS Objects after compaction → post-compact storage is L× the raw vector bytes, eliminating the dedup advantage that motivated reference mode in the first place.

Empirically (dreamdb-bench/reports/realistic-postcompact-final.json, 20M dim=192 tables=4): 19.4 GB ingest-time storage → 84.8 GB post-compact storage (4.4× growth, of which 4× is the inevitable per-table replication and the rest is metadata churn).

Implications:

• Reference mode at L=1 after compaction: storage stays at 1× raw + small refs. Cheapest production layout for latency-sensitive workloads.
• Reference mode at L>1 after compaction: storage is L× raw — equivalent to inline mode. The "75% storage savings" headline is recovered ONLY if you skip compaction (and accept slow scattered-read queries).
• Inline mode at L>1: same L× storage, simpler operations (no compaction, no writer/compactor coordination).

Updated guidance, 2026-05: at L>1 you now choose between (a) inline mode + always-L× storage + simple operations, or (b) reference mode + L× storage post-compact + writer/compactor coordination cost (per 0008 §7.4). The "free dedup" framing of the 2026-04 draft was wrong for latency-sensitive ANN — surface to operators as such.

6.2.2 When multi-table is still warranted

Multi-table earns its cost only when read-time multi-probe alone (§6.4) is insufficient to reach the target recall. Sweep results at 2M dim=128 bits=14 (dreamdb-bench/reports/sweep-*.json):

The comparison is workload-dependent, not strict dominance for all corpora or equal-cost operating points. Read-time probing avoids write replication, while independent tables change candidate selection. Choose using measured recall, bytes and latency for a pinned workload; 0.95 is not a universal crossover.

6.3 Lever 3: Write-time multi-probe (replicate_probes=k modality parameter)

A modality declares replicate_probes=k (e.g. ... .replicate_probes=4) to opt into write-time replication. At write time, the writer computes the Item's natural spatial key plus k bit-flip neighbors (typically the k bits with smallest |<v, h_i>| — the bits closest to the decision boundary, most likely to flip under perturbation). The Item's bucket-index entry is replicated across all k+1 spatial keys.

At read time, the SDK fetches only the natural-key bucket; the candidate set is automatically widened because each bucket already contains nearby boundary-case vectors from neighboring buckets.

Storage cost: k+1 bucket-index entries per Item (still ~50 B each via byte-range references); same ~7% premium per probe at billion-scale. Recall at fixed read cost approaches that of multi-probe READ-time LSH (which is a query-side technique outside the protocol).

replicate_probes=k and tables=L compose: ... .tables=4.replicate_probes=2 gives 4 × 3 = 12 index entries per Item, very high recall.

6.4 Lever 4: Read-time multi-probe (probe_count and max_hamming query parameters)

New first-class lever, 2026-05. The 2026-04 draft mentioned read-time multi-probe in §6.3 as a query-side technique "outside the protocol." Empirical evidence has elevated it to a load-bearing lever — see §6 preamble and §6.2.1.

Read-time multi-probe widens the candidate cell set at QUERY TIME instead of write time. The query verb (per 0006 §6.6) takes two parameters:

• probe_count — the maximum number of cells the query inspects per table. Cap is the candidate-pool size at the chosen max_hamming.
• max_hamming — the radius (in bits) within which to consider candidate cells.

Given the query's primary spatial key (the deterministic LSH output for the query vector), the candidate pool is:

Candidates are ranked by ascending sum of |projection magnitudes| for the flipped bits — the bits closest to the LSH decision boundary, where the query's classification was least confident. Multi-probe probe_count=K fetches the top K of this ranked pool.

This is a strictly stronger ordering than write-time multi-probe (§6.3): write-time replication picks bit-flip candidates for each Item (independent of any future query), whereas read-time multi-probe picks them for the specific query vector using its actual projection magnitudes. The latter has more information to work with, so per-cell hits are more useful.

6.4.1 Why max_hamming is the underused dial

At bits=N=14, max_hamming=1 caps the candidate pool at 15 cells. Setting probe_count > 15 with max_hamming=1 is a no-op — the cap binds. Operators who set probe_count=64 thinking "more probes = more recall" but leave max_hamming=1 get exactly the same result as probe_count=15. This footgun is silent.

At max_hamming=2, the candidate pool grows to 15 + C(14, 2) = 106 cells. probe_count=16 now selects the 16 best-ranked candidates from a pool of 106 — far more useful than from a pool of 15. Empirically this lifts recall@1 from 0.40 to 0.70 at zero storage cost (dreamdb-bench/reports/sweep-A.json vs sweep-C.json).

Recommended defaults:

• max_hamming = 2 (universal default — minor compute cost, large recall lift)
• probe_count = 16-32 (tune against target recall)
• tables = 1 unless §6.2.2 sweep data shows tables > 1 is required for the recall target

max_hamming = 3 is permitted but produces a candidate pool of 1 + N + N(N−1)/2 + N(N−1)(N−2)/6 (e.g. 470 cells at N=14) — typically more cells than the SDK can afford to fetch, and the marginal recall gain is small. SDKs MAY support it for high-recall workloads.

6.5 SDK-side recall-widening procedure (combined)

A query for k-nearest-neighbors with target recall ρ on a modality with tables=L and replicate_probes=k, using read-time multi-probe (probe_count, max_hamming):

1. Look up the modality's registry → get the L SpatialIndex Object hashes. Fetch and cache the SpatialIndex Objects (L small GETs, once per session).
2. Compute the query's spatial key under each of the L SpatialIndex functions → L primary query-keys.
3. Expand each primary key into probe_count candidates within max_hamming bits (Lever 4) — ranked by ascending |projection magnitude| for flipped bits.
4. Select a calibration profile measured with the exact §5.3 generator and representative data for the requested recall target.
5. Choose M (prefix truncation, Lever 1) from that profile for the configured L, k, probe_count, and max_hamming. No closed-form angle-only sizing rule is defined for dreamdb.lsh-cosine.
6. For each of the L × probe_count candidate keys: locate matching buckets via the cached object_index (hot path) or list-prefix (cold start); collect bucket addresses.
7. Issue parallel ranged GETs against the union of bucket addresses.
8. Exact-compare query against all candidates; return top-k.

The SDK MAY iteratively widen M, probe_count, or max_hamming if the result set is too small (adaptive recall widening); the policy is implementation-defined. Recommended escalation order: probe_count → max_hamming → M → L. (Cheapest to most expensive.)

7. Worked Example: 768-dim, 18-bit, 1B Vectors

The benchmark target. End-to-end mechanics:

7.1 Setup

Modality: embedding.f32.dim=768.bucketed.spatial_bits=18.

SpatialIndex Object (CBOR):

{
   "algorithm": "dreamdb.lsh-cosine",
   "dim":       768,
   "bits":      18,
   "metric":    "cosine",
   "params":    { "version": 1, "seed": h'a3b9... (32 bytes)' },
}

Object size: ~80 bytes. Address: spatial-index/<33-byte-multihash>.

The Manifest's registry declares the modality → SpatialIndex Object mapping. Readers fetch this once per session, cached.

7.2 Ingestion

For each input vector v ∈ R^768:

1. L2-normalize v to unit length.
2. Generate the 18 hyperplanes from the seed (computed once at module load, cached).
3. Compute b_i = sign(<v, h_i>) for i ∈ {0,...,17} → an 18-bit string.
4. Encode the bit string as 18 base2 chars → the spatial-key segment.
5. Append v to the Spatial Bucket Object at <timeline>/<modality>/<spatial-key>/<bucket-hash>. (The bucket hash is determined when the bucket is finalized — per 0002 §7.4.2.)

At 1B vectors with N=18 (~262K buckets), each bucket holds ~3,800 vectors on average → ~12 MB per bucket Object at 3 KB/vector. Sweet spot for backend GET cost.

7.3 Query — hot path vs. cold start

For a query vector q seeking the 10 nearest neighbors at an operator-calibrated recall target, the SDK's path differs sharply between hot path (Track Object cached) and cold start (Track Object not yet fetched). The protocol-level behavior for production is the hot path; cold-start is the bootstrap mechanism.

Hot path — Track Object's object_index already cached from a prior query:

1. Look up modality → SpatialIndex Object hashes via cached Manifest registry. (No backend call.)
2. L2-normalize q. Compute q's spatial keys for each of the L tables (cached hyperplanes).
3. Locate matching buckets in the cached object_index (in-memory prefix scan, microseconds). For paged-form indexes (per 0002 §7.3.2), traverse the cached B-tree.
4. Issue parallel ranged GETs against the matching bucket addresses, multiplexed over an HTTP/2 (or HTTP/3) connection (per 0005). No list-prefix backend call required — bucket addresses are known from the cached index.
5. Decode each bucket's packed-array vectors (per 0007), exact-compare against q, accumulate top-10.
6. Return the top-10 with byte-range URIs (0002 §6.5).

Normative — Manifest Supremacy (0005 §5.3.1). The steady-state (warm) read path MUST NOT issue a list-prefix request: every bucket address is resolved from the cached, Manifest-anchored object_index. list-prefix is permitted ONLY as the cold-start bootstrap when no Track Object is cached (see below). This is a conformance criterion (0009 §7, verb.query.no-list-prefix) and holds independently of the latency budget that follows.

Cold start — Track Object not yet cached:

1. Locate the Track Object via the Manifest's tracks field; fetch it (one GET; for paged-form Track Objects, fetch the root Index Page and the relevant subtree — typically 2–4 small GETs).
2. Cache the object_index for the session.
3. Proceed as the hot path from step 2.

Latency budget at billion-scale (informative — a performance profile, not a conformance requirement; see 0009 §4.4 and 0023-performance-profiles.md) (single-table tables=1, N=18, hot path, prefix-truncated to M=14 → ~16 buckets):

• Steps 1–3: ~1 ms (purely local, in-memory).
• Step 4: 16 parallel HTTP/2 GETs of ~12 MB each. At commodity 10 Gbps with HTTP/2 multiplexing, total wall-clock ~50–100 ms.
• Step 5: local exact-KNN over ~60K candidates at dim=768 → ~10–30 ms (CPU-bound).
• Total p50 hot-path latency: ~100–150 ms. Within reach of the sub-100 ms benchmark target with PQ compression in 0007 (which shrinks bucket bytes by ~30×) or with smaller buckets at N=22.

For multi-table (tables=4), step 4 fans out to 4× more buckets but each table's recall lever is independent: M can be larger per table for the same union recall, partially offsetting the GET-count increase.

The cold-start path adds 1 round trip (~30–80 ms) for the Track Object fetch. This is paid once per Track per session — irrelevant at production query rates, where the cache is always warm. The list-prefix backend call appears nowhere on the hot path; it is only the cold-start bootstrap mechanism for SDKs without any cached Track Object at all.

8. Billion-Scale Considerations

(Informative.) This section is performance guidance — bucket sizing and latency budgets for a billion-scale workload — not normative conformance. Its latency/throughput/recall targets are performance-profile material (0023-performance-profiles.md); the normative invariants the budgets rely on (the §7 read path and Manifest Supremacy, 0005 §5.3.1) are stated there, not here. Per 0009 §4.4, an implementation that satisfies the protocol but misses these targets is conformant — it simply does not claim this profile.

8.1 The 100 ms target requires smaller buckets

§7.3's example fetches ~192 MB across 16 buckets. Whether that candidate set meets a particular recall target is an empirical property (§5.2); independently of recall, that byte volume is far over the 100 ms p95 target.

Two levers:

• Smaller buckets. Increasing N from 18 to 22 → 4M buckets, ~250 vectors each → ~750 KB per bucket. With M=8 prefix-truncation (16 buckets), total bytes fetched ~12 MB, achievable in ~50 ms warm cache. But more buckets means more backend Objects to manage.
• Compressed vectors. Storing PQ-compressed vectors inside Bucket Objects (not full f32) — e.g. 8 sub-quantizers of 256 centroids each, 8 bytes per vector instead of 3 KB. 1B vectors → 8 GB total. Each bucket: ~250 × 8 bytes = 2 KB. Recall is then a re-rank step: fetch candidates' approximate distances, identify top-K candidates, fetch their full f32 vectors via byte-range URIs for exact distance.

Compression and partitioning are independently bound (0010); a combined algorithm name is not required to use the second lever. §5.6.1 specifies the implemented IVF + global-vector PQ case. The arithmetic above does not establish recall, latency or equivalence with FAISS-IVF-PQ or ScaNN.

8.2 Spatial-bits sizing

N = spatial_bits controls bucket count and per-bucket density. The right N depends on item count and target recall:

Rule of thumb: target ~250–4000 items per bucket. Below 250, prefix truncation has too few buckets to widen across; above 4000, exact KNN within a bucket dominates query cost.

8.3 SpatialIndex Object caching

Each SDK session loads the SpatialIndex Object (small) and the regenerated hyperplanes (~55 KB at dim=768, N=18). One-time cost per modality per session — irrelevant at billion-scale.

8.4 Hyperplane regeneration cost

ChaCha20 → 768 × 4 bytes per hyperplane × 18 hyperplanes = ~55 KB of keystream. ChaCha20 throughput is ~1 GB/s on commodity hardware → regeneration takes ~50 µs. Cached after first use.

9. Out of Scope for this Document

• Per-modality vector encoding beyond what the modality tag specifies. embedding.f32.dim=768 says "f32, 768-dim"; how the application produced the f32 values (which embedding model, whose normalization convention) is a DreamDB non-goal per 0000 §8.
• Inside-bucket layout (packed-array headers, vector compression formats) — 0007.
• Query routing across multiple Tracks of the same modality (e.g. the same embedding model layered over many videos) — that's a 0006 query-operation concern.
• Algorithm fitness for non-cosine metrics. dreamdb.lsh-cosine remains cosine-only; dreamdb.lsh-l2 (§5.8) preserves magnitude using a distinct metric and algorithm binding.
• Multi-table LSH. Mentioned in §6.3 as a future extension; v0 ships single-table only.

10. Open Questions Surfaced by This Document

• OQ-23 (→ 0007 §6): Bucket-internal vector encoding and storage layout. Resolved: inline-mode (default for tables=1, fixed-size records); reference-mode (default for tables>1, byte-range refs into per-Track Vector-Storage Objects). Pure f32 in v0; PQ-compressed deferred to v0.1 (OQ-38).
• OQ-24 (→ 0007 §6.4): RESOLVED. bucket_max_bytes bounds record payload, excluding the header; default 100 MiB, with the range and canonical decimal spelling fixed there. Splits retain cell identity and produce separate content hashes and index entries.
• OQ-25: Resolved. §5.6.1 chooses independently bound IVF + global-vector cosine PQ, demonstrated through public create/write/reopen/query. No combined algorithm identity or wire change; residual IVF-PQ and performance claims are not implied.
• OQ-26 — Resolved (#321): §5.8 defines the versioned L2 projection, width, signed-bin identity, probe order and raw distance arithmetic. Existing cosine encodings are unchanged.
• OQ-27 (→ 0009 §5.3): Conformance test vectors for dreamdb.lsh-cosine. Resolved: full battery in 0009 §5.3.1 — multi-architecture coverage (x86 AVX-512/AVX2/scalar, ARM NEON/scalar), known-seed → known-hyperplanes, f32-rounding-boundary cases.
• OQ-28 (→ 0006 §6.4 / §6.5): RESOLVED as implementation-defined. SDKs may widen prefix depth and speculatively preload under those sections' bounds. Cancellation uses the negotiated transport's mechanism; HTTP/2 RST_STREAM is not a requirement on an HTTP/1.1 connector.
• OQ-29 (→ 0005 §6): HTTP/2 connection requirement. Resolved: transport-agnostic — Connectors MUST implement the HTTP semantics over HTTP/1.1 or later and are conformant on any version; HTTP/2 (or HTTP/3) is a SHOULD-negotiate performance upgrade and a performance-profile attribute (0023), not a conformance requirement.

Next: 0005-backend-interface.md — pins the HTTP semantic contract between the Storage Connector and the Cloud Object Store: which verbs, which status codes, which conditional headers, which consistency guarantees. Resolves OQ-3, OQ-22, and the ContentStore/RefStore tier definitions referenced throughout.