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
}

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).

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.3 — 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.

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:

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, sampled i.i.d. from 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 (Charikar 2002)

For two unit vectors v_a, v_b with angle θ ∈ [0, π]:

P[ b_i(v_a) == b_i(v_b) ]  =  1 - θ/π

For independent hyperplanes, the joint probability that all N bits agree is (1 - θ/π)^N. The expected prefix length for two queries v_a, v_b with angle θ is approximately 1 / (θ/π) bits (geometric distribution of the position of the first differing bit).

Practical implication for billion-scale recall (see §8 for a sizing table):

• At θ = 5° (highly similar pairs): P[bit-collision] ≈ 0.972. Expected prefix length ≈ 36 bits.
• At θ = 10°: P ≈ 0.944. Expected prefix length ≈ 18 bits.
• At θ = 30°: P ≈ 0.833. Expected prefix length ≈ 6 bits.

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 whose distribution is roughly uniform on the unit sphere after normalization — sufficient for the cosine LSH locality property without requiring a Box-Muller transform (which would add f32 precision concerns). 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 binary32 distribution from ChaCha20 keystream is not literally Gaussian, but the L2-normalization step projects to the unit sphere, which is what locality requires. (The strict-Gaussian distribution would require a Box-Muller transform, which adds f32 precision concerns; the projected uniform-on-sphere is locality-equivalent for cosine-metric use.)

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. Charikar's locality bound is closed-form. Sizing decisions can be made from a calculator, not from running benchmarks.
• 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.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.

6. Recall-Widening Strategies

Single-table LSH-cosine has limited recall at meaningful angular separations: at θ = 30° (medium similarity), (1 − 30/180)^18 ≈ 4% — single-bucket lookups miss 96% of these candidates. 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.

Recall as a function of M for a candidate at angle θ: (1 − θ/π)^M.

Prefix truncation alone is insufficient for production recall at θ ≥ 20°. It is the right lever for high-similarity (θ < 10°) lookups and as a fallback for the other levers.

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.

Recall improves as 1 − (1 − p)^L where p is single-table recall. At θ=30°, M=14, p≈8%:

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 — 7% storage premium for ~3.5× recall improvement.

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):

At equivalent per-query work, single-table with max_hamming=2 strictly dominates multi-table on recall, latency, and storage. Multi-table becomes attractive only at very high recall targets (recall@10 > 0.95) where read-time probing saturates.

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. Estimate angular threshold θ_max for the target recall.
5. Compute the smallest M (prefix truncation, Lever 1) such that combined recall ≥ ρ given L, k, probe_count, max_hamming, θ_max. (Closed-form per §6.2; SDKs may also pre-tabulate.)
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 recall ≥ 90%, 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).

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 (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

8.1 The 100 ms target requires smaller buckets

§7.3's example fetches ~192 MB across 16 buckets to hit 90% recall at θ_max = 10°. That's 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.

The second lever is what production billion-scale retrieval actually does (FAISS-IVF-PQ, ScaNN). v0's dreamdb.lsh-cosine does not include PQ compression. A v0.1 algorithm dreamdb.lsh-pq that combines LSH bucketing with PQ compression inside buckets would pin this down.

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 is cosine-only; L2 metric needs a different algorithm. Future v0.1 spec adds dreamdb.lsh-l2 (random projection LSH with bucket-width parameter).
• 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): Bucket-splitting rule. Resolved: split when a Bucket Object would exceed bucket-max-bytes (default 100 MiB); new Bucket has same spatial key, new content hash, new index entry per 0002 §7.3.1's allowance for duplicate spatial_key_i.
• OQ-25 (→ v0.1 spec): A dreamdb.pq-ivf algorithm — closer to FAISS-IVF-PQ — for production-grade recall at billion scale. v0 ships LSH-cosine as default with multi-table (§6.2) for production-grade recall; PQ-IVF is the v0.1 addition that closes the recall gap further at the cost of a training step.
• OQ-26 (→ v0.1 spec): A dreamdb.lsh-l2 algorithm for L2-metric modalities. v0 cosine-only.
• 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): Adaptive recall widening + speculative preloading. Resolved as implementation-defined: SDKs MAY widen prefix-truncation depth M against cached index; SDKs MAY speculatively preload on cold-start paths but MUST cancel via RST_STREAM on consumer abandonment.
• OQ-29 (→ 0005 §6): HTTP/2 connection requirement. Resolved: HTTP/2 mandatory for Connectors; HTTP/1.1 fallback only with logged warning; HTTP/3 permitted as upgrade.

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.