Semantic Search

Learning Objectives

By the end of this project, you will be able to:

• Explain why a brute-force cosine scan (Project 02) does not scale, and what a vector database adds on top of raw embeddings.
• Build a semantic search index with Chroma: create a collection, add documents (id + embedding + document + metadata), and query it.
• Explain approximate nearest neighbor (ANN) search and how HNSW achieves ~O(log N) query time instead of O(N) — and why it is approximate.
• Convert correctly between distance and similarity and avoid the silent ranking-inversion bug (Chroma returns distances; lower = closer).
• Choose and justify a distance space (cosine vs l2 vs ip) for text embeddings.
• Compare ANN results against the exact brute-force baseline and measure recall, not just eyeball it.
• Explain the retrieve-then-rerank pattern (bi-encoder retrieves, cross-encoder re-ranks) and when it is worth the cost.

1. Motivation

Why This Exists

In Project 02 you ranked a corpus by computing cosine against every document — an exact O(N) scan. Fine for 6 sentences, hopeless for 6 million. Real semantic search needs two things the brute-force loop lacks: speed at scale and persistence (build the index once, query it forever). A vector database provides both.

What Breaks Without It

Get the distance-vs-similarity direction wrong and your "most relevant" result is actually your least relevant — a silent bug with no error. Pick the wrong distance space and rankings degrade quietly. Misunderstand ANN and you'll be surprised when the "nearest" neighbor is occasionally missed.

Real-World Stakes

Every production search, RAG pipeline, recommendation engine, and "find related" feature runs on a vector DB under the hood. The judgment built here (index design, metric choice, recall measurement, when to re-rank) is what separates a search box that feels magic from one that feels broken.

2. Mental Model

Explain Like I'm 12

In Project 02 you found the closest word by checking every single house in the city, one by one. That works for a small town. Now imagine the whole country. Instead of visiting every house, you use a map with zoom levels: zoom out, jump to the right region, zoom in, jump to the right city, zoom in again, until you're on the right street. You visited a handful of places, not the whole country — but you almost always land on the right house. That zoom-map is HNSW, and the filing cabinet that holds all the addresses is the vector database.

Explain Like I'm a Software Engineer

• A vector database is an index + storage + query API over embeddings. In Chroma a collection holds (id, embedding, document, metadata) records; collection.query(query_embeddings=..., n_results=k) returns the k nearest by distance.
• The index is HNSW: a hierarchical set of proximity graphs searched by greedy routing from the top layer down — ~O(log N) instead of the O(N) brute-force scan. It is approximate: it can occasionally miss the true nearest neighbor, trading a little recall for a lot of speed.
• Chroma returns distances, not similarities — lower distance = more similar. With space="cosine", cosine distance ≈ 1 − cosine_similarity.

Real-World Analogy

How It Works (Diagram)

 Build (once):
   docs ──embed──► [v1 v2 ... vN] ──add──► Chroma collection ──► HNSW index on disk

 Query (per request):
   "monetary policy"
        │ embed
        ▼
     q-vector ──► HNSW greedy routing (top layer → bottom) ──► top-k ids + DISTANCES
                                                                  (lower = closer)
   compare to brute-force exact scan ──► measure recall (did ANN find the true top-k?)

3. Technical Explanation

Formal Definition

Vector search: given a query vector q and a set {v_1..v_N}, return the k vectors minimizing a distance d(q, v_i) (or maximizing similarity). Exact search evaluates all N (O(N)); approximate (ANN) search uses an index to evaluate far fewer.

HNSW builds a "multi-layer structure consisting from hierarchical set of proximity graphs (layers) for nested subsets of the stored elements," with layer membership drawn from "an exponentially decaying probability distribution," searched greedily from the top layer down — yielding "logarithmic complexity scaling."

How It Works Step by Step

1. Build the index. Embed each document once, then collection.add(ids=, embeddings=, documents=, metadatas=). Chroma inserts each vector into the HNSW graph (max_neighbors/M = links per node; ef_construction = build-time breadth).
2. Query. collection.query(query_embeddings=[q], n_results=k) runs greedy routing (ef_search = candidates explored; higher = better recall, slower) and returns ids, documents, distances, metadatas.
3. Distance ↔ similarity. For space="cosine", similarity = 1 − distance. Reporting raw distance as a "higher = better" score is the classic inversion bug.

Costs: brute-force exact search is O(N·d) per query; HNSW is ~O(d·log N) — the whole point. Cosine distance d_cos = 1 − (a·b)/(‖a‖‖b‖) ∈ [0, 2], so similarity = 1 − d ∈ [−1, 1].

Key Concepts

4. Guided Examples

The lab stack: chromadb (vector DB / HNSW), litellm (embeddings via config.py, default local ollama/nomic-embed-text, 768-dim), numpy (the brute-force baseline).

Example 1: Simplest Case — build and query a collection

import chromadb
from embedding_helpers import embed_many   # wraps litellm; returns list[list[float]]

docs = [
    "The central bank raised interest rates this quarter.",
    "A young wizard attends a school of magic.",
    "Photosynthesis converts sunlight into energy in plants.",
]
client = chromadb.Client()                                  # in-memory for the demo
col = client.create_collection("demo", metadata={"hnsw:space": "cosine"})  # text -> cosine
col.add(ids=["d0", "d1", "d2"], embeddings=embed_many(docs), documents=docs)

q = embed_many(["monetary policy and the economy"])[0]      # query is lexically unlike doc 0
res = col.query(query_embeddings=[q], n_results=2)
print(res["documents"][0])     # most similar first
print(res["distances"][0])     # LOWER distance = MORE similar  (not a similarity!)

Example 2: Real-World Case — distance → similarity, done right

def to_similarity(distance: float) -> float:
    # Chroma space="cosine" returns cosine DISTANCE in [0, 2]; similarity = 1 - distance.
    return 1.0 - distance

for doc, dist in zip(res["documents"][0], res["distances"][0]):
    print(f"{to_similarity(dist):+.3f}   {doc}")   # +higher = more relevant, human-readable

Example 3: When It Fails — ANN is approximate; measure it

import numpy as np
def cosine(a, b): return float(a @ b / (np.linalg.norm(a) * np.linalg.norm(b)))

# Exact brute-force ranking (Project 02 style) over the same vectors:
qv = np.array(q)
vecs = [np.array(v) for v in embed_many(docs)]
exact_order = [i for i, _ in sorted(enumerate(vecs), key=lambda t: -cosine(qv, t[1]))]

# recall@k = |ANN top-k ∩ exact top-k| / k  (map Chroma ids back to indices)
ann_idx = [int(i[1:]) for i in res["ids"][0]]
k = len(ann_idx)
recall = len(set(ann_idx) & set(exact_order[:k])) / k
print("recall@%d = %.2f" % (k, recall))

5. Reflection Before Building

After filling in UNDERSTANDING.md, use the AI mentor pattern in docs/meta/learning-flow.md to get feedback. Record the feedback in UNDERSTANDING_FEEDBACK.md.

6. Project Assignment

See PROJECT.md for the full project specification including file structure and extended requirements.

Core Requirement

Build a semantic search engine in code/ over a provided corpus:

• indexer.py — embed a corpus and build a persistent Chroma collection (space="cosine") with text + metadata. Idempotent: re-running does not duplicate records.
• semantic_search.py — embed a query, run collection.query, return ranked (document, similarity, metadata) with distance correctly converted to similarity.
• baseline.py — exact brute-force cosine ranking (reuse Project 02's cosine) to validate the vector DB, plus a recall_at_k helper.
• evaluate.py — run queries through both paths and report recall@k of the ANN index vs. the exact baseline.

Extended: add cross-encoder re-ranking (rerank.py); compare space="cosine" vs l2; sweep ef_search and record recall vs. latency.

7. Project Milestones

Work through these in order. Each milestone should produce runnable code before moving on.

8. Self-Evaluation

After building, honestly evaluate your implementation against these criteria. Record your answers in EVALUATION.md.

9. Common Mistakes

10. Connections

Builds On

Project 02 produced embeddings and ranked them by cosine by hand over a tiny corpus. Project 03 keeps the exact same embeddings and cosine intuition but moves storage and search into a vector database so it scales and persists. Your Project 02 cosine_similarity becomes the exact baseline you validate the database against.

Enables

This is the retrieval engine of Project 04 (RAG / PDF assistant) — RAG = this search step feeding retrieved chunks to an LLM. Project 05 (memory) stores and recalls past items by the same vector-DB lookup. The re-ranking pattern reappears wherever first-stage retrieval isn't precise enough.

Production Patterns

The standard architecture is two-stage retrieval: a bi-encoder + ANN index retrieves a broad candidate set fast; a cross-encoder re-ranks the top-k precisely. Add metadata filtering (where) for hard constraints, and persist the index so it survives restarts.

StarcallOS Relevance

Sources

See source/resources.md for the complete annotated source list.