Day 14 · Vector Search

Day 13 left one box unopened: “find the top-k passages most similar to the question.” Today you open it. Similarity between two pieces of text becomes similarity between two vectors, “most similar” becomes a number you compute, and the whole retriever turns out to be a few dozen lines of arithmetic over &[f32] — no database, no linear-algebra crate, no magic.

From text to geometry

An embedder maps text to a fixed-length vector of f32. The trick that makes retrieval work: similar text lands at similar vectors, so “which passage is most relevant?” becomes “which vector points in nearly the same direction as the question’s vector?” The standard measure of “same direction” is cosine similarity — the cosine of the angle between two vectors:

                 a · b                Σ aᵢbᵢ
   cos(a, b) = ───────────  =  ──────────────────────
               ‖a‖ · ‖b‖       √(Σ aᵢ²) · √(Σ bᵢ²)

It ranges from +1 (same direction — very similar) through 0 (orthogonal — unrelated) to -1 (opposite). Crucially it ignores magnitude and compares only direction, so a long passage and a short one are judged on what they’re about, not how many words they have.

The hot loop, by hand

askr implements it directly over slices — no dependency, total (never panics), and honest about the edge cases:

pub fn cosine_similarity(a: &[f32], b: &[f32]) -> f32 {
    if a.len() != b.len() {
        return 0.0;                 // mismatched dims: caller bug, but stay total
    }
    let mut dot = 0.0f32;
    let mut norm_a = 0.0f32;
    let mut norm_b = 0.0f32;
    for i in 0..a.len() {
        dot += a[i] * b[i];
        norm_a += a[i] * a[i];
        norm_b += b[i] * b[i];
    }
    if norm_a == 0.0 || norm_b == 0.0 {
        return 0.0;                 // zero vector: angle undefined → 0
    }
    dot / (norm_a.sqrt() * norm_b.sqrt())
}

Both degenerate cases — different lengths, an all-zero vector — return 0.0 instead of producing NaN or panicking. That keeps the function usable in the middle of a sort without a special case at every call site.

The store and top-k

The store is the least clever data structure that works: a Vec of (Chunk, Vec<f32>). To answer a query, score every entry and keep the best k:

pub fn top_k(&self, query: &[f32], k: usize) -> Vec<Scored<'_>> {
    let mut scored: Vec<Scored> = self.entries.iter()
        .map(|(chunk, emb)| Scored { score: cosine_similarity(query, emb), chunk })
        .collect();
    scored.sort_by(|a, b| {
        b.score.partial_cmp(&a.score).unwrap_or(std::cmp::Ordering::Equal)
    });
    scored.truncate(k);
    scored
}

Two Rust details worth pausing on:

• Scored<'a> borrows the chunk. top_k returns Vec<Scored<'_>>, where each Scored holds a &Chunk into the store rather than a clone. The borrow checker ties the results’ lifetime to &self, so they cannot outlive the store they point into — you get zero-copy retrieval with a compile-time guarantee that you’ll never read a dangling chunk. That is the recurring thread in one line: the compiler is protecting you from a use-after-free, and the cost is just writing '_.
• partial_cmp, not cmp. f32 is PartialOrd but not Ord, because NaN is unordered. sort_by with partial_cmp().unwrap_or(Equal) makes the float ordering explicit and panic-proof.

The f32 ordering footgun

A tempting one-liner is scored.sort_by(|a, b| b.score.partial_cmp(&a.score).unwrap()). It works… until a NaN sneaks in (a divide-by-zero upstream, a malformed embedding), at which point partial_cmp returns None, the unwrap() panics, and your retriever crashes mid-query. Because f32 deliberately does not implement Ord, Rust forces you to decide what an unordered comparison means — here we treat it as Equal and keep going. The language turning “I forgot about NaN” into a decision you must make is the borrow checker’s philosophy applied to numbers.

By the numbers — when is brute force fine?

Scoring every vector is O(N · D): one multiply-add per dimension, per stored chunk.

   N = 10,000 chunks
   D = 1,024 dimensions
   work ≈ N · D = 10,000 × 1,024 ≈ 10.2 million multiply-adds per query

Ten million flops over contiguous f32 slices is on the order of a few milliseconds on one modern core — well inside “instant” for a CLI. Brute-force exact search stays fine into the tens of thousands of chunks. You only need an approximate index once N reaches the millions and that linear scan stops being free.

Under the hood — exact vs. approximate nearest neighbor

askr does exact search: it really compares against every vector, so the top-k is always correct. That’s the right call at this scale and it’s trivially testable. Production systems with millions or billions of vectors switch to approximate nearest neighbor (ANN) indexes, which trade a little recall for a huge speedup by not scanning everything:

• FAISS (Meta AI, 2017 — Johnson, Douze & Jégou, “Billion-scale similarity search with GPUs”) popularized fast similarity search at scale.
• HNSW (Malkov & Yashunin, 2016/2018) builds a layered “navigable small-world” graph and walks it to find near neighbors in roughly logarithmic time instead of linear.

The interface barely changes — still “give me the top-k for this vector” — which is exactly why hiding the store behind a small API (as askr does) lets you upgrade the index later without touching the RAG code above it.

Why Rust is a good home for this loop

This is a tight numeric loop over contiguous memory, run once per dimension per chunk on every query — precisely the shape you saw guard the hot path back in the kvlite and apilite work. Rust suits it for the same reasons throughout this playbook: a Vec<f32> is a flat, cache-friendly buffer (no pointer-chase per element), the loop compiles to tight machine code the optimizer can vectorize, there are no GC pauses to stutter a query, and there is no hidden allocation per comparison — top_k allocates one results Vec and borrows everything else. You get C-level throughput on the hot path with the borrow checker still guaranteeing none of those borrowed chunks dangle.

Testing it without an embedder

The retriever is fully tested offline using the deterministic MockEmbedder (one vector component per keyword), so the assertions are obvious to read:

#[tokio::test]
async fn retrieve_surfaces_the_relevant_chunk_first() {
    let embedder = MockEmbedder::new(vec!["rust", "ocean", "coffee"]);
    // three chunks about rust / ocean / coffee, embedded and stored...
    let hits = retrieve(&store, &embedder, "tell me about rust", 1).await.unwrap();
    assert_eq!(hits[0].chunk.source, "rust.txt");
}

Plus unit tests pinning the math itself: identical vectors score 1.0, orthogonal 0.0, opposite -1.0, and the zero/mismatched-length cases return 0.0. That’s the payoff of hand-writing the similarity — it’s a pure function you can nail down with a handful of asserts, no network and no model in sight.

Build it

1. Implement cosine_similarity(a: &[f32], b: &[f32]) -> f32 with the zero/length guards.
2. Build VectorStore (a Vec of (Chunk, Vec<f32>)) with add and top_k returning Scored<'_>.
3. Write the math tests (identity, orthogonal, opposite, degenerate) and a retrieval test with MockEmbedder.
4. cargo test — the whole retriever is green, offline.

Tomorrow: production hardening — config, errors, a CI pipeline — and a bridge into Phase 2.

Check your understanding

1. What does cosine similarity measure, and why is it a good fit for comparing text embeddings even when passages differ a lot in length?
2. cosine_similarity returns 0.0 in two guard cases instead of computing a ratio. What are they, and why return 0.0 rather than panic or produce NaN?
3. top_k returns Vec<Scored<'_>> where Scored holds a &Chunk. What does the lifetime buy you, and what does the compiler guarantee about those references?
4. Why does the sort use partial_cmp(...).unwrap_or(Equal) instead of cmp? What language fact forces this?
5. At roughly what scale does askr’s brute-force exact search stop being “free,” and what kind of index do production systems switch to then?

Show answers

1. It measures the cosine of the angle between two vectors — i.e. how aligned their directions are, independent of magnitude. Because it ignores length, a long passage and a short one are compared on what they’re about rather than on word count, which is exactly what you want for text relevance.
2. (a) The vectors have different lengths (a caller bug, but the function stays total), and (b) either vector is all zeros (the angle is undefined). Returning 0.0 keeps the function usable inside a sort without crashing or injecting NaN into the rankings.
3. The lifetime 'a ties each Scored to the store it was produced from, giving zero-copy retrieval (no cloning chunk text per query). The compiler guarantees the returned references cannot outlive the store, so you can never read a dangling/freed chunk — a use-after-free is impossible to write.
4. f32 is PartialOrd but not Ord, because NaN is unordered — so cmp isn’t available. partial_cmp returns an Option, and unwrap_or(Equal) decides that incomparable values sort as equal, keeping the sort total and panic-proof.
5. Brute force stays fine into the tens of thousands of chunks (a linear scan is a few milliseconds there). Once N reaches the millions, systems switch to an approximate nearest neighbor (ANN) index — e.g. FAISS or an HNSW graph — trading a little recall for sub-linear search.

---

Prev: Day 13 · Streaming and RAG · Next: Day 15 · Hardening and the Phase 2 Bridge →