Command Palette

Search for a command to run...

Hectal
Phase 3Intermediate4 of 14 in RAG and Vector Search

Vector Search: Exact, IVF, HNSW and Smaller Vectors

Search a million vectors fast: exact search first, then IVF and HNSW built by hand, smaller vectors, recall measured honestly, and filters.

Phase 2 turned text into vectors. This phase answers the next question: how do you find the closest vectors quickly? You start with the honest, exact answer (compare the question with every vector) and count what it costs. Then you build the two ideas that real vector databases use to avoid that cost, IVF (search only the nearest clusters) and HNSW (walk a graph of neighbours), at a size where every number can be followed by hand.

Both ideas are approximate: they sometimes miss a true neighbour. So the phase teaches the skill that matters most in practice, measuring recall against the exact answer, and turning one knob at a time (nprobe, efSearch, efConstruction, M) while reading the curve. You also shrink vectors with quantisation, and meet the awkward case of searching only one user's documents.

Every algorithm is written by hand in Python, Java and JavaScript on small seeded data, so all three languages print the same numbers. The build topic puts a vector index behind AskDocs, and the playbook gives you a benchmark harness and a test for the question beginners skip: do I even need an index?

0/9 · 0%
9 topics ~4 h 21 code blocks & diagrams
Start with the first topic
1
3.1

Exact Nearest-Neighbour Search

The simplest correct vector search compares the question with every stored vector and keeps the best k. It costs vectors times dimensions multiplications per question, which is fine for a surprisingly large collection and is the ground truth every faster method is judged against.

27 min 3 code practice

2
3.2

Why Search Becomes Approximate

Sorting and tree structures that make ordinary database lookups fast stop helping when vectors have hundreds of numbers. Vector indexes therefore trade a little accuracy for a lot of speed, and the accuracy is measured as recall against the exact answer.

27 min 3 code practice

3
3.3

IVF by Hand

IVF (inverted file) groups the vectors into clusters with k-means, then answers a question by searching only the few clusters whose centres are closest to it. The number of clusters (nlist) and the number searched (nprobe) set the speed against recall.

27 min 2 code practice

4
3.4

HNSW by Hand

HNSW links every vector to a few near neighbours and finds the nearest vectors by walking that graph: greedy hops, a small beam (efSearch) and sparse upper layers that act as express lanes. M, efConstruction and efSearch set memory, build quality and recall.

31 min 5 code practice

5
3.5

Making Vectors Smaller

Quantisation stores each number of a vector with fewer bits, which shrinks memory and speeds up comparisons while the ranking barely changes. Re-scoring a small shortlist with the full vectors wins back most of the accuracy that heavy compression loses.

25 min 2 code practice

6
3.6

Tuning Recall Against Speed

A faster index is only better if you know what it gave up. A trustworthy benchmark uses exact search as ground truth, real questions, a hardware-independent cost such as distances computed, and one knob turned at a time, then reads the curve for the cheapest setting that meets a recall target.

24 min 1 code practice

7
3.7

Filters Meet Vectors

Real searches say "only this user's documents" or "only the 2025 version". Filtering after an approximate search leaves too few results when the filter is selective, filtering before it can be slow or break a graph, and the practical answer depends on how many vectors pass the filter.

23 min 1 code practice

8
3.8

Build: A Vector Index for AskDocs

AskDocs version 3: an Embedder turns passages and questions into vectors, an exact index and an IVF index sit behind the same add and search interface, retrieval keeps only hits above a similarity bar, and recall against the exact index is measured. The login question is finally answered correctly.

29 min 1 code practice

9
3.9

Playbook: Picking and Tuning an Index

Recipes to copy into any vector search project: test whether you need an index at all, start from documented parameters, benchmark against exact search, shrink and re-score, choose a filter strategy, and keep recall from silently dropping.

25 min 3 code practice

Practise this phase

Hands-on exercises: write the code, run it, and press Check to have it tested automatically.

1

Exact top-k search

Write dot(a, b) that returns the dot product of two equal-length lists of numbers.

Beginner
2

Recall at k, and its average

Write recall_at_k(found, truth, k): look only at the first k ids of each list, and return the fraction of truth[:k] that also appears in found[:k]. Order does not matter. If truth[:k] is empty, return 1.0 (there was nothing to find).

Beginner
3

One round of k-means

points and centroids are lists of (x, y) pairs. Write assign(points, centroids) that returns, for each point, the index of the nearest centroid by squared distance. If two centroids are equally near, use the lower index.

Intermediate
4

Search an IVF index

centroids are the cluster centres, lists[c] holds the ids of the points in cluster c, and points[i] is point i (all 2-D (x, y) pairs). dist2(a, b) is given.

Intermediate
5

Scalar quantisation and memory

Write quantise(vec, levels) that maps each number from the range -1 to 1 onto a whole number from 0 to levels: floor((x + 1) / 2 * levels + 0.5) (import math for floor).

Intermediate
6

Filtering after the search

Write fetch_needed(k, matching, total) that returns how many results to fetch before filtering so that about k of them pass, rounded up: ceil(k * total / matching) with integer arithmetic only.

Intermediate