Vector Search at Scale

Anchored in rag_pipeline.py → class VectorStore · vector_search

Right now your search code does this:

results = table.search(query_vector).metric("cosine").limit(top_k).to_list()

That's exact k-NN: for every query, LanceDB compares your query vector against every single chunk vector, sorts them, and returns the top 5. For 83 chunks, that's fine. For 83,000 — or 8.3 million — it's not. This lesson is about what "not" means in concrete numbers, and the two algorithm families that fix it.

1. The problem with exact search

Cosine similarity between two 384-dimensional vectors is ~1,540 floating-point operations (multiplies, adds, one square root at the end). Call it C. To find the top 5 out of N chunks, you do N comparisons and a sort:

cost_exact = N · C

For our current index, that's 83 × 1,540 ≈ 128,000 FLOPs per query. On a modern CPU at ~10 GFLOPS, this takes microseconds. The end-to-end latency in `DAY1_NOTES.md` was 60–90 ms, and most of that was the embedding model, not the search.

But scale the dataset up. Here's the same math for the same query:

At 1M chunks the per-query cost is starting to hurt. At 10M your single search takes longer than your embedding model took. And you also pay a memory cost: 1M × 384 floats × 4 bytes = 1.5 GB just for the vectors, and LanceDB's table format adds overhead on top.

2. ANN: the contract

ANN — Approximate Nearest Neighbor — is a family of algorithms that trade a small, controlled amount of accuracy for a large, controlled speedup. The contract is:

• Recall@10 ≈ 0.95 instead of 1.0 — we accept that 5% of the time the true top-1 isn't in our top-10.
• Query time drops from O(N) to roughly O(log N) — milliseconds even at 10M rows.
• Build time goes up: you pay a one-time tax when you create the index.

The "approximate" matters because search quality downstream — RAG answer quality — is the product of two things: the retrieval recall and the LLM's ability to ignore noise. If recall drops from 1.0 to 0.95, your RAG will occasionally miss a great answer. You tune the index to keep this in the noise floor. Pinecone's PQ guide explains the "magic triangle" of recall/speed/memory.

3. Family 1: HNSW — graph-based

HNSW stands for Hierarchical Navigable Small World. Despite the imposing name, the data structure is just a graph. Each chunk is a node. Edges connect "close" chunks. There are multiple layers — the top layers have few nodes, the bottom layer has all of them.

Searching for the nearest neighbor to a query is like navigating a social network:

1. Start at the top layer at a pre-defined entry node.
2. Look at your neighbors. If any is closer to the query than you, jump to it. Repeat until no neighbor is closer. (You've hit a "local minimum.")
3. Drop down to the next layer, at the same node. Repeat the greedy descent.
4. When you hit the bottom layer, you've explored the densest region of the graph and have a high-quality top-k.

It's the same idea as a B-tree — expressways on top, local streets at the bottom — applied to a graph instead of a sorted array. The search is O(log N) because the top layers act as a long-jump scaffold.

Three knobs you'll see in the LanceDB config:

The official paper is Malkov & Yashunin, 2016. Pinecone's HNSW page has a good interactive walkthrough.

4. Family 2: IVF — partition-based

IVF stands for Inverted File Index. The mental model is a database index: partition the space into clusters and only search the partitions that could plausibly contain the answer.

Build time: run k-means clustering over all the vectors. You choose nlist centroids. Each chunk is assigned to its nearest centroid.

Query time: find the nprobe centroids closest to the query, then only compare against the vectors in those clusters.

Two knobs:

The intuition: if you have 1M vectors and nlist=1000, each cluster has ~1,000 vectors. With nprobe=10, you only scan ~10,000 vectors per query — a 100x reduction.

5. PQ — compression (the secret weapon)

Product Quantization solves a different problem: memory. At 1M vectors × 384 dims × 4 bytes, you're holding 1.5 GB of floats in RAM. PQ compresses each vector to ~50–100 bytes — a 30–60× reduction — by splitting the vector into sub-vectors, clustering each sub-vector separately, and replacing every sub-vector with the ID of its nearest centroid.

You don't compare raw vectors at query time; you compare compressed representations via a precomputed lookup table. There's a small accuracy hit, but memory drops to a fraction, and more vectors fit in cache, so the system is often faster despite the quantization step.

Most production systems combine: IVF + PQ for memory-bounded scale, or IVF + HNSW for latency-bounded scale. The first gives you "billion-scale, slower per query"; the second gives you "fastest possible per query, more memory."

6. How LanceDB exposes all of this

Our current code doesn't create an index. LanceDB defaults to exact k-NN when there's no index. For 83 rows, that's the right call — building an index would be slower than running the brute-force scan, and the index itself would use more memory than the raw data.

To add an index, you call create_index on the table. The current LanceDB API (v0.33) takes a typed config object:

rag_pipeline.py · VectorStore._create_table (extended)

from lancedb.pydantic import IvfPq, IvfHnswSq

# 1) IVF + PQ — best when memory is the constraint
table.create_index(
    "vector",
    config=IvfPq(
        num_partitions=256,        # ≈ rows // 4096
        num_sub_vectors=96,        # ≈ dim // 8 (for 384-d)
        metric="cosine",
    ),
)

# 2) IVF + HNSW + SQ — best latency/recall balance
table.create_index(
    "vector",
    config=IvfHnswSq(
        num_partitions=256,        # ≈ rows // 4,096
        m=16,                      # HNSW degree
        ef_construction=150,
        metric="l2",               # SQ builds on L2, then we project
    ),
)

The full set of supported indexes in LanceDB today: IvfFlat, IvfPq, IvfRq, IvfSq, IvfHnswFlat, IvfHnswPq, IvfHnswSq. The naming convention is IVF_[HNSW_]? + a quantizer (Flat = no compression, PQ = product quantization, SQ = scalar quantization, RQ = RaBitQ). Full reference →

7. The recall benchmark you should always run

When you adopt an ANN index, the first thing to do is measure how often the ANN top-k matches the exact top-k. This is "recall@k" against the brute-force ground truth.

The pattern:

import numpy as np
import lancedb

db = lancedb.connect("data/lancedb")
table = db.open_table("rag_chunks")

# 1) Ground truth via exact k-NN
gt = (
    table.search(query_vec)
    .metric("cosine")
    .limit(10)
    .to_list()
)
gt_ids = {row["id"] for row in gt}

# 2) Approximate results (after create_index on the vector column)
ann = table.search(query_vec).limit(10).to_list()
ann_ids = {row["id"] for row in ann}

# 3) Recall @ 10
recall = len(gt_ids & ann_ids) / len(gt_ids)
print(f"recall@10 = {recall:.2f}")

Run this on 50–100 real queries. recall@10 ≥ 0.95 is the typical bar. Below 0.9, your RAG answers will start degrading visibly. You also need to compare against your old exact k-NN behavior — if 0.95 of the time the answer is the same chunk, no user will notice. If it's 0.70, your whole search will feel flaky.

8. Hands-on exercise

"""Lesson 0002 — benchmark exact vs ANN vector search at scale."""
import time
import numpy as np
import lancedb
from rag_pipeline import Embedder

print("Loading model...")
embedder = Embedder()
DIM = embedder.dimension

# ----- 1) Synthesize a scalable dataset by chunking Wikipedia text -----
# (We don't have 83k real blog chunks; we fake the count by duplicating
# the existing index with random perturbations of the vectors.)
print("Connecting to existing index...")
db = lancedb.connect("data/lancedb")
existing = db.open_table("rag_chunks")
real_chunks = existing.to_pandas()
print(f"  real rows: {len(real_chunks)}")

# Helper: build a "scaled" table with N rows
def build_scaled_table(n: int) -> lancedb.table.Table:
    """Create a fresh table with `n` rows of random unit vectors."""
    name = f"scaled_{n}"
    try:
        db.drop_table(name)
    except Exception:
        pass
    rng = np.random.default_rng(seed=42)
    vecs = rng.normal(size=(n, DIM)).astype("float32")
    vecs /= np.linalg.norm(vecs, axis=1, keepdims=True)
    schema = None  # schema inferred from the data dicts below
    table = db.create_table(
        name,
        data=[
            {
                "id": f"fake-{i}",
                "doc_id": "fake",
                "title": f"fake {i}",
                "content": f"fake content {i}",
                "source_url": "",
                "category": "TIL",
                "chunk_index": i,
                "total_chunks": n,
                "vector": vecs[i].tolist(),
            }
            for i in range(n)
        ],
    )
    return table


# ----- 2) Benchmark a single query against different sizes -----
QUERIES = 20
for n in (1_000, 10_000, 100_000):
    print(f"\n--- n = {n:,} rows ---")
    tbl = build_scaled_table(n)

    query_vec = embedder.embed_one("how to configure neovim folding")

    # Warm-up (first call may pay file-open cost)
    tbl.search(query_vec).metric("cosine").limit(10).to_list()

    # Exact k-NN
    t0 = time.perf_counter()
    for _ in range(QUERIES):
        tbl.search(query_vec).metric("cosine").limit(10).to_list()
    exact_ms = (time.perf_counter() - t0) / QUERIES * 1000
    print(f"  exact k-NN:   {exact_ms:7.2f} ms/query")

    # Build an index, then re-benchmark
    print("  building IVF_HNSW_SQ index...")
    from lancedb.pydantic import IvfHnswSq
    tbl.create_index(
        "vector",
        config=IvfHnswSq(
            num_partitions=max(8, n // 4096),
            m=16,
            ef_construction=100,
        ),
    )
    t0 = time.perf_counter()
    for _ in range(QUERIES):
        tbl.search(query_vec).limit(10).to_list()
    ann_ms = (time.perf_counter() - t0) / QUERIES * 1000
    print(f"  IVF_HNSW_SQ:   {ann_ms:7.2f} ms/query  (speedup: {exact_ms / ann_ms:.1f}x)")

    db.drop_table(tbl.name)

9. What you now know

• ✅ Exact k-NN is the default in LanceDB and is O(N) per query. Fine for our 83 chunks. Painful at 10M.
• ✅ ANN trades a small recall loss for a large speedup. The recall loss is what you measure, not assume.
• ✅ HNSW is a graph-based index: O(log N) search, more memory, fast to query, slow to build.
• ✅ IVF is a partition-based index: cluster first, then search only the relevant clusters. Two knobs (nlist, nprobe) control the build/query speed/recall tradeoff.
• ✅ PQ compresses vectors ~30–60×, enabling billion-scale in memory. Often combined with IVF.
• ✅ LanceDB's create_index(... config=IvfHnswSq(...)) is the practical API. Under 100k rows, exact k-NN is usually the right choice.

10. What you don't know yet (next lessons)

• Why keyword search still matters when you have a perfect vector index (Lesson 0003: BM25).
• How to fuse vector and keyword rankings (Lesson 0004: RRF).
• How to add metadata filters without breaking the vector index (filtering with LanceDB where clauses).

Citations & further reading

1. LanceDB Vector Index documentation — the canonical reference for index types and config objects.
2. Malkov & Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (2016) — the HNSW paper.
3. Pinecone, HNSW explained — interactive walkthrough of the graph algorithm.
4. Pinecone, Product Quantization explained — the "magic triangle" framing for recall/speed/memory.
5. FAISS wiki, Getting started — the reference implementation; great for understanding operational constraints.
6. Milvus, IVF_PQ documentation — implementation-level parameter guidance.