# Static tree vs. static ANN — `stree` and `vann` are the same idea, twice
> **Class:** `reasoning` · **Functions:** `stree` + `vann`. Why they share DNA, why
> they stay two structures, and why the generic `STree<T>` and the IVF layer were both
> rejected. The chosen shapes are in [`stree-design.md`](stree-design.md) and
> [`vann-design.md`](vann-design.md).
> ⛔ **SUPERSEDED (2026-07-02, same day).** The **`vann::RagnarsEmbIndex` IVF was
> removed** hours after this note was written — nornir requires exact (100%-recall)
> search, and IVF is approximate (it skips `nprobe` cells and can miss the true
> nearest). `vann` today is the **exact flat `VectorIndex` oracle + a
> provably-lossless int8/VNNI prefilter → f32 rerank** (byte-identical to flat).
> **`stree32` is untouched and still shipping** — it is an exact-key search tree,
> not a vector index. Everything below about IVF / `nprobe` / k-means / posting
> lists / "recall knob" describes **deleted code** and is retained only as design
> history. The one durable, still-true point is the **shared batch-prefetch SIMD
> DNA**: `stree32`'s branchless `count_lt` and `vann`'s `vpdpbusd` int8 dot both
> turn a latency-bound scan into a throughput-bound one via precomputed layout +
> prefetch. The int8 kernel lives on in the *exact* rerank path.
>
> Original note (2026-07-02) for the two **static, cache-aware search structures**
> in `znippy-zoomies`: the exact-key **S+tree** (`stree` / `stree32`, Ragnar Groot
> Koerkamp's design) and the (now-removed) approximate-NN **IVF vector index**
> (`vann::RagnarsEmbIndex`). Built from the *same* Ragnar DNA.
## TL;DR
| | `stree32` (S+tree) | `vann` (RagnarsEmb IVF) |
|---|---|---|
| **Question** | "where is key `q`?" | "which vectors are nearest `q`?" |
| **Domain** | 1-D **ordered** keys (`u32`/`i64`) | high-D vectors (768-D `f32` → `i8`) |
| **Answer** | exact index, or `None` | approximate top-`k` `(id, score)` |
| **Structure** | implicit S(+)-tree (pointer-free) | k-means centroids + CSR posting lists |
| **Traversal** | `log_{B+1}(N)` dependent hops | 2 hops: scan centroids → scan `nprobe` postings |
| **Inner loop** | branchless `count_lt` SIMD compare | `vpdpbusd` int8 dot (VNNI) |
| **Exactness** | 100% (recall = 1) | tunable via `nprobe` (recall knob) |
| **Speedup vs naive** | up to ~40× vs binary search | ~60–1000× vs flat scan (data-dependent) |
| **Static?** | yes — rebuilt only every ≥1024 commits | yes — rebuilt on re-embed |
They are two points on one design axis: **precompute a memory layout that mirrors
the traversal order, then let SIMD + prefetch turn a latency-bound scan into a
throughput-bound one.**
---
## The similarities — one Ragnar DNA
Both structures win the *same* way, and it is not "a cleverer algorithm" — it is
**respecting the memory hierarchy**. Three shared traits (the rail at the bottom
of the diagram above):
### 1. Contiguous memory in traversal order (no pointer chasing)
- **`stree`**: the classic Eytzinger/S+tree trick — the tree is an *implicit*
array. A node's children are found by **arithmetic** (`child = k·(B+1)+i`), never
a stored pointer. Each node is exactly one **64-byte cache line** holding `B`
keys (`B=16` for `u32`, `B=8` for `i64`). One line fetched = one whole node
compared.
- **`vann`**: vectors are stored in **cluster (CSR) order**, so a posting list is
one contiguous run of `i8` rows. Scanning a probed cluster is a single
sequential stream — the same "the bytes you need next are the bytes right here"
property, just over rows instead of tree nodes.
Neither structure ever dereferences a pointer into cold memory on the hot path.
### 2. A branchless SIMD inner loop
- **`stree`**: `count_lt` compares the query against all `B` keys in a node with
one `_mm256_cmpgt_epi32` (8×`u32` lanes) and a `popcount(movemask)/4` — **no
branch**, so no mispredict, so the pipeline never stalls on data. (u32 adds the
`i32::MIN` bias trick to borrow AVX2's *signed* compare; see [`stree-design.md`](stree-design.md).)
- **`vann`**: `score_i8_batch` scores a row with `vpdpbusd` — **64 int8
multiply-accumulates per instruction** — also branch-free. (int8 borrows VNNI's
*unsigned×signed* form via a `+128` query bias and a per-row `Σr` correction;
see `src/vector/mod.rs` G2 notes.)
Same shape: fold many elements per instruction, keep the branch predictor out of
it. The specific intrinsic differs because the *elements* differ (ordered keys vs
quantized vector lanes) — that difference is the whole reason they stay two
concrete implementations rather than one generic (mirroring the deliberate
`STree64`/`STree32` split).
### 3. A software-pipelined batch that hides the miss (MLP)
This is the sharpest shared idea, and it has its own diagram:
A single query is **latency-bound**: every hop (down a tree level, or to the next
posting run) is a cache miss the core would otherwise sit idle through. Ragnar's
fix is to run **`P` queries in flight**: each query issues a `prefetch` for its
*next* hop and then yields; another query's compute fills the gap. The wall clock
collapses from "sum of the misses" to "the compute, with the misses overlapped."
- **`stree`** exposes it as `batch_stream::<P>` / `batch_prefetch::<P>` — `const P`
is the *pipeline depth* (the one parameter kept generic; `P=16` pegs every core
at 100%).
- **`vann`** exposes it as `search_batch(queries, k, nprobe)` — the same
prefetch-next-posting-rows-while-scoring-the-current overlap, and its result is
**byte-identical** to looping single-query `search` (a tested invariant).
Same driver, two payloads (the bottom rail of the pipeline diagram): a `stree` hop
is *prefetch child → `count_lt` → descend*; a `vann` hop is *prefetch posting rows
→ `score_i8_batch` → merge top-k*.
Both also share the **"static" contract**: build is comparatively expensive
(sorting keys / k-means), queries are cheap and read-only, and the structure is
frozen between rebuilds — the reason the diagram dresses both in ice.
---
## The differences — why they are still two structures
### Ordered vs. unordered domain (the root difference)
`stree` exists because its keys are **totally ordered**: `count_lt` is meaningful,
so the tree can route with exact arithmetic and land on *the* answer. Embedding
vectors have **no total order** — "nearest in 768-D" is not a position in a sorted
array — so `vann` cannot route; it must **partition** (k-means) and **scan
candidates**. That is the line between an exact index and an approximate one.
### Exact vs. approximate (and the knob)
- `stree.find_exact` is exact: recall is 1.0 by construction.
- `vann.search` is approximate: it only scans `nprobe` of `nlist` clusters, so a
true neighbour in an unprobed cluster is missed. `nprobe` trades recall for
speed. On well-separated synthetic data `nprobe=1` already gives ~0.99 recall
(~1000× at 1M); on real overlapping embeddings you pay more probes for the same
recall — the honest number lives in nornir's `.nornir/vector-ragnar-reuse.md`.
### Depth vs. breadth of traversal
- `stree` does `log_{B+1}(N)` **dependent** hops — each level's load address
depends on the previous compare. `B=16` keeps the tree shallow (`log₁₇`), so
there are few dependent misses; that is the whole point of restoring the 32-bit
width (fewer levels than the i64 tree — see [`stree-design.md`](stree-design.md)).
- `vann` does a fixed **2 levels** regardless of `N`: one pass over `nlist`
centroids, then a scan of the probed postings. The cost scales with `nprobe` and
cluster size, not with tree depth.
### Build cost & determinism
- `stree` build = sort + pack the implicit layout: cheap, fully deterministic.
- `vann` build = **k-means** (seeded Lloyd iterations): heavier (≈97 s at 1M,
single-threaded today) and only deterministic under a fixed seed. Empty clusters
keep their prior centroid. This is the honest cost of an *unordered* domain.
### Quantization
`vann` additionally quantizes `f32`→`i8` (the vectors are L2-normalized, so
components live in `[-1,1]` and quantize to ~1e-2 cosine error) to quarter the
bytes the scan streams. `stree` keys are exact integers — no quantization, no
recall loss from it. int8 is a `vann`-only lever (and its recall ceiling on dense
data is a documented seam, cured by an optional f32 re-rank of the candidate set).
---
## Where they meet — the hybrid (why co-locating them pays off)
The two are not just neighbours by heritage; they **compose** in a retrieval
stack. `vann` finds the fuzzy vector neighbours; an exact-key structure resolves
the crisp parts:
- **`id → row` term dictionary.** After `vann` returns `(id, score)` pairs, an
exact `id → payload` lookup is precisely a `stree`/`stree32` `find_exact` over a
sorted id column (or the existing `STree32Mmap`, whose on-disk column *is* the
leaf layer). No hash map, no pointer chase.
- **Hybrid lexical + vector search.** A lexical term-dict (sorted terms →
postings, a `stree` job) fused with `vann`'s vector candidates is the standard
"BM25 + ANN" hybrid. Ragnar's IVF doc explicitly parks the stree *here* — **not**
inside pure IVF (a CSR posting index already gives O(1) there), but as the exact
half of a hybrid.
That is the architectural payoff of putting the ANN engine in `znippy-zoomies`
beside `stree`/`gatling`/`psort`: the exact-key tree, the fuzzy-vector index, the
no-barrier batch driver (`gatling`), and the parallel sort (`psort`) that k-means
and top-k both want are **one toolbox**, reusable by `skade`, `nornir`, and any
other consumer without pulling a whole application repo.
---
## Provenance & cross-repo notes
- `stree`/`stree32`: Ragnar Groot Koerkamp's [`static-search-tree`](https://github.com/RagnarGrootKoerkamp/static-search-tree)
("40× faster than binary search"), MIT, copyright retained in the crate `LICENSE`.
Full design in [`stree-design.md`](stree-design.md), benchmarks in [`benchmarks.md`](benchmarks.md).
- `vann::RagnarsEmb`: extracted from nornir `src/vector` (the flat int8 oracle +
the IVF layer). The reuse rationale, the flat→batched→IVF→mmap progression, and
the real-vs-synthetic recall numbers live in nornir's
`.nornir/vector-ragnar-reuse.md`; the heavy warehouse bench harness (`xtask`)
runs from the **consumer (nornir) repo**, as with the stree32 512 MB gate.
- Both structures are **static**: rebuilt on a coarse cadence (≥1024 commits for
the skade snapshot tree; on re-embed for `vann`) and read-only in between.