Topic 3.1
Exact Nearest-Neighbour Search
In one line
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.
Think of it like this
Finding the three tallest children in a school hall. You walk past every child once, and you carry a card with the three tallest so far. If the next child is shorter than the shortest name on your card, you ignore them. If not, they replace someone. When you reach the end, the card is exactly right. It took one look at each child, and no cleverness.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Nearest neighbour
- The stored vector most similar to the question's vector. The k nearest neighbours (k-NN) are the best k.
- Exact / brute-force / flat search
- Comparing the question with every stored vector. Slow for huge collections, never wrong.
- Top k
- The k best-scoring results, best first.
- Multiply-add
- One multiplication plus one addition: the unit in which a similarity's cost is counted.
- Heap
- A structure that always keeps its smallest (or largest) item at the front. It keeps the top k cheaply.
- Ground truth
- The known-correct answer a fast method is compared with. For vector search, the exact top k.
- Latency
- How long one question takes from start to answer.
Step by step
01Step 1: twelve passages, four numbers each
To see every number, the first example gives each handbook passage a hand-made vector with four toy "meaning" directions: money, time, account and safety. A real embedding model has hundreds of directions that nobody named (Topic 2.1), but the search code does not care.
02Step 2: one similarity
Cosine similarity is the dot product divided by the two lengths. The loop adds x * y for the dot and x * x, y * y for the lengths. That is the whole inner loop of vector search, and it runs n times per question.
def cosine(a, b):
dot = norm_a = norm_b = 0.0
for x, y in zip(a, b):
dot += x * y
norm_a += x * x
norm_b += y * y
return dot / (math.sqrt(norm_a) * math.sqrt(norm_b))03Step 3: score everything, sort, take k
The simplest top-k: score all twelve, sort best first, keep the first three. A stable sort keeps equal scores in handbook order, which is the tie-break. For the toy question "how much is a late return?" the winners are Late returns (0.985), Refunds (0.957) and Monthly pass (0.895).
04Step 4: keep only a short list
With millions of vectors, sorting everything is wasted work. The second example scans 2,000 random vectors and holds just the best 3, inserting a vector only when it beats the weakest one on the list. The list changed 20 times. Library code uses a real heap for this; Python's heapq is the same idea:
import heapq
best = [] # a min-heap of (score, id): the weakest of the current top k is at best[0]
for doc_id, vector in items:
score = dot(query, vector)
if len(best) < k:
heapq.heappush(best, (score, doc_id))
elif score > best[0][0]:
heapq.heapreplace(best, (score, doc_id))05Step 5: count the cost at real sizes
Multiply vectors by dimensions, then by 4 bytes for memory. The table at the end of the second example shows why a million 384-number vectors are 384 million multiply-adds and 1.5 GB, while a hundred million 1,024-number vectors would need 400 GB just to sit in memory.
06Step 6: see it with a real model
The lab below runs a real embedding model in your browser over the twelve handbook passages. For the question about bringing a bike back late, the late-returns passage scores about 0.60, the damage passage about 0.54 and the refunds passage about 0.54, with a gap of only about 0.004 between the last two. That ranking, best cosine first, is exact search. A near-tie like that one is where an approximate index may swap two results. Remember it: from Topic 3.2 on, "correct" means "the same top k as this".
Try it yourself
- 1
Predict, then search
In the first example change the query to
[0.0, 0.1, 0.9, 0.2](mostly "account"). Predict the top result before you run. Then change it to[0.1, 0.0, 0.1, 0.9](mostly "safety"). Which passages move? - 2
Change k
Set k to 1, then to 12. With k = 12 the "top k" is the whole sorted list. What is the lowest cosine in the handbook for this question?
- 3
Watch the list stop changing
In the second example raise the number of vectors from 2,000 to 20,000. Predict how many times the top-3 list changes (hint: not ten times more). Then run and compare with the formula in the lesson.
- 4
Compare languages
Run both examples in all three tabs. The outputs are identical, including the last digit of every score. Why is that guaranteed here, and why would it not be for results from a GPU? (Hint: the order in which numbers are added.)
Code & diagrams
The vectors are a toy: four directions chosen by hand so you can check the scores in your head. A real embedding model has hundreds of learned directions.
Expected output
compared with 12 vectors of 4 numbers
0.985 D6 Late returns
0.957 D1 Refunds
0.895 D8 Monthly passThe 2,000 vectors are random numbers from the course's seeded generator. The cost table assumes one billion multiply-adds per second per core: a round number to reason with, not a benchmark.
Expected output
scanned 2000 vectors, the top-3 list changed 20 times
id 651 squared distance 0.1382
id 1134 squared distance 0.1503
id 1162 squared distance 0.1515
cost of one exact query (1 billion multiply-adds per second is an assumed round number)
10000 vectors x 384: 3 million multiply-adds, about 3 ms, 15 MB of vectors
1000000 vectors x 384: 384 million multiply-adds, about 384 ms, 1536 MB of vectors
100000000 vectors x 1024: 102400 million multiply-adds, about 102400 ms, 409600 MB of vectorsTry: Press Search and read the Cosine column: this ranking, best first, is exact search over the handbook. Check that the late-returns passage is first (about 0.60) and that the next two scores are very close (about 0.54 each). Then change k and the question (try "Can I get my money back if I cancel?") and see which passages enter and leave the top 3.
Goals
- The late-returns passage is the best match
- The opening-hours passage stays out of the top 3
Press Search. Then change one thing (a word in the question, a passage, the ranker) and compare the scores.
Break it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Sort the wrong way round
In the Python tab of the first example, remove the minus sign in scored.sort(key=lambda s: -s[0]) so the key is s[0].
Break #2
Use the dot product on vectors that are not unit length
In the Python tab of the first example, change the last line of cosine to return dot.
Myth vs fact
Myth
Exact search is too slow to use.
Fact
For tens of thousands of vectors it answers in milliseconds and has no tuning and no missed results. Many production systems should stay on exact search. Topic 3.9 shows how to decide.
Myth
An approximate index is just a faster version of the same search.
Fact
It is a different trade: it may return a different top k. Only by comparing with exact search can you say how different (Topic 3.2).
Myth
The cost of search depends mainly on k.
Fact
Almost not at all. Every vector must be compared whatever k is. The cost is vectors times dimensions.
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
Exact search is embarrassingly parallel and cache-friendly: it is one big matrix-vector product. Batched queries become a matrix-matrix product, which reads each stored vector once for many questions and which libraries run far faster than a naive loop (memory bandwidth, not arithmetic, is then the limit). So measure on your own machine before you assume you need an index.
- ▸
Memory, not time, is usually the first wall. Float32 vectors for 10 million chunks of 1,536 numbers are about 61 GB. Topic 3.5 shrinks that 4 times with 8-bit codes, and Topic 5.7 prices the rest.
- ▸
Keep the exact path alive even after you add an index. It is your test oracle, your fallback when an index is being rebuilt, and the right answer for tiny filtered subsets (Topic 3.7).
Remember this
- 1
Why this comes first. After Phase 2 every passage is a list of numbers, a vector, and so is the question. "Search" now means: find the stored vectors closest to the question's vector. The simplest way is also correct every time, which makes it the baseline for everything else in this phase: a fast method is only good if you can show how often it agrees with this one. (LLM Engineering Phase 8 already searches this way in a few lines. Here we count what it costs.)
- 2
The method. For each stored vector, compute its similarity to the question's vector (cosine, or the dot product when vectors have length 1, Topic 2.2), and keep the top k. This is called exact nearest-neighbour search, brute force or a flat index. It has no tuning knobs and cannot miss: if a better vector exists, it is found.
- 3
The cost, counted by hand. One similarity between two vectors of
dnumbers takesdmultiplications anddadditions (a multiply-add). Fornstored vectors, one question costsn × dmultiply-adds. The handbook has 12 vectors of 4 numbers in the first example: 48. A help centre of 50,000 chunks with 384 numbers each: 19.2 million. One million chunks: 384 million. Also count memory: each number is usually a 32-bit float (4 bytes), so a million 384-number vectors take1,000,000 × 384 × 4= 1,536 MB. - 4
Keeping the top k without sorting everything. Sorting all
nscores wastes work when you only want 3. Keep a short list of the best k so far, and compare each new score only with the weakest entry on the list. A heap (a priority queue whose smallest element is always at the front) does that inlog ksteps per vector. In the example the list changed only 20 times while scanning 2,000 vectors: for data in random order, a new vector enters the top k aboutk × (1 + ln(n / k))times in total, here about 22. Almost every vector is looked at and then ignored. - 5
How far brute force really goes. Take, as a round assumption, one billion multiply-adds per second on one core (real code with SIMD instructions, a matrix library or a GPU is many times faster, and your machine will differ: measure it). Then 50,000 vectors of 384 numbers cost about 19 ms per question, a million cost about 384 ms, and a hundred million of 1,024 numbers cost over a minute. So exact search is a fine answer up to tens or even hundreds of thousands of vectors, and the real limit is often memory before time. Topic 3.9 turns this into a test you can run.
- 6
Ties and exactness. Two vectors can have the same score. Decide the tie-break once (here: the one stored first wins) so that results are repeatable, because repeatable results are what let you compare an index against the exact answer. The exact answer is also your ground truth: Topic 3.2 measures how often an approximate index agrees with it.
Explain it without notes
What does exact nearest-neighbour search do, and what does one query cost in terms of n (vectors) and d (dimensions)?
Why keep only a short list of the best k instead of sorting every score? Roughly how often does that list change?
A team has 80,000 chunks of 768 numbers and about 3 questions per second. Is exact search enough? Show your reasoning.
Why does exact search matter even if you will use an approximate index in production?
Practice
Write top_k(query, vectors, k) that returns the ids (positions) of the k vectors with the highest dot product, ties broken by lower id. Print the top 2 for the query [1, 1] and the top 3 for [1, 0] over the vectors [1, 0], [0, 1], [0.6, 0.8], [0.8, 0.6].
A collection has 50,000 vectors of 768 numbers. Print the number of multiply-adds one exact query needs and the memory the float32 vectors take in megabytes (1 MB = 1,000,000 bytes).
Trade-offs
- ↔
Exact search: never wrong and nothing to tune, but cost grows in step with the collection.
- ↔
Cosine on stored vectors: robust to vectors of any length, with extra work per comparison. A dot product on pre-normalised vectors is cheaper and gives the same ranking.
- ↔
A heap or short list: tiny memory and fast, with slightly more code than sorting everything.
Done when you can
Done when you can write exact top-k search with a tie-break from memory.
Done when you can compute the multiply-adds and the memory of a collection from n and d.
Done when you can explain why a bounded top-k list beats sorting everything.
Done when you can say when exact search is enough and why it is still needed with an index.