nordisk/znippy-zoomies

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

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.)
• 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).
• 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 ("40× faster than binary search"), MIT, copyright retained in the crate LICENSE. Full design in stree-design.md, benchmarks in 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.