Lesson 4.3

Nearest-neighbor lookup

How a semantic cache actually finds the closest past question: nearest-neighbor search in vector space.

concepts intuition 9 min read

Every question is a point on a map.

Last lesson placed each question as a point whose location captures its meaning. Questions that mean similar things sit close together; unrelated ones sit far apart. A semantic cache is built on that map. The cached questions are dots already on it. A new query is a new dot you drop down.

So "do we have a cached answer?" becomes a geometry question: which existing dot is closest to the new one, and is it close enough to count? Drag the query dot below. The line snaps to whichever cached question is nearest, and the dashed circle is the threshold: inside it is a hit, outside is a miss.

Drag the query point. The nearest cached question lights up.

nearest = Q3 distance = 0.07 radius = 0.10 → HIT

Finding a cache hit is finding the closest point. The query lands on the map, and the nearest cached question is the only candidate worth checking.

Nearest neighbor: the single closest point.

The closest stored point to your query is called its nearest neighbor. Finding it is nearest-neighbor search, and it is the engine inside every semantic cache. You take the new query's point and ask: of all the cached points, which one is least far away?

"Least far away" needs a way to measure far, a distance. Two common ones are Euclidean distance (straight-line distance, the length of the line you would draw between two dots) and cosine distance (based on the angle between the two points' directions). Either way, a smaller number means closer in meaning. The demo above uses plain straight-line distance so you can see it.

This same nearest-neighbor search is the heart of vector search, the engine behind similar-item lookup, retrieval for RAG, and recommendation. It is its own deep topic (and a later project on the monkway roadmap). Here we only need the one move: find the closest stored point to the query.

The threshold is a radius around the query.

Finding the nearest point is only half the job. The nearest stored question might still be about something totally different, just the least-different thing on file. So the threshold from last lesson becomes a radius: a circle of "close enough" drawn around the query.

Nearest point falls inside the radius: hit. Reuse its stored answer.
Nearest point falls outside the radius: miss. Even the closest match is too far, so go to the provider.

Drag the query far from every cached dot in the demo and watch the verdict flip to MISS: there is still a nearest neighbor, but it sits outside the radius, so it does not count. The closest past question wins only if it is inside the threshold.

A hit, worked by hand.

A new query lands on the map. The cache measures the distance to each stored point and keeps the smallest. Say point P (a stored question) is the closest, at distance 0.07, and the threshold radius is 0.10:

nearest stored point = P

distance(query, P) = 0.07

threshold radius = 0.10

0.07 ≤ 0.10 → inside the radius → HIT

P is the nearest neighbor and it sits inside the radius, so the gateway returns P's stored answer and skips the provider. Now nudge the query until the nearest distance grows to 0.14. It is still the same nearest neighbor, but 0.14 is outside the 0.10 radius, so the verdict is a miss and the request goes to the provider.

A semantic cache is nearest-neighbor search plus a radius. The closest past question wins only if it falls inside the threshold; otherwise it is a miss.

Work it out

Three cached points sit at distances 0.22, 0.11, and 0.09 from a new query. The threshold radius is 0.10. Which point is the nearest neighbor, and is the result a hit or a miss? Now the threshold is loosened to 0.15. Same answer? (Answers: the nearest neighbor is the one at 0.09, a hit under both thresholds. At radius 0.15 the 0.11 point would also fall inside, but nearest-neighbor search still picks the single closest, 0.09.)

Key takeaways

Embeddings place each question as a point, so finding a cache hit becomes finding the nearest stored point to the query (nearest-neighbor search).

A distance measures how far apart two points are; the threshold is a radius, and only a nearest neighbor inside it counts as a hit.

This nearest-neighbor search is the core of vector search, and it is what turns the semantic cache from an idea into something the gateway can run.