Searching Fast: ANN, Skip Lists & Small Worlds

Part of the free Generative AI course on LogicWiz, module: Finding the Needle: Hybrid Search & Retrieval.

Episode 40: Searching Fast — ANN, Skip Lists & Small Worlds

Arjun's semantic search worked beautifully on 500 products. At 500,000 it took nine seconds per query. "Correct," Anjali said, "is not the same as usable."

Finding a Face in a Stadium

Imagine you're looking for the one friend who looks most like the photo on your phone — and they're somewhere in a stadium of 100,000 people.

The guaranteed way is to walk up to every single person, hold up the photo, and compare. You'll definitely find the best match… after 100,000 comparisons. Fine for a small room. Hopeless for a stadium — and completely hopeless for a product catalogue with millions of items, where this happens on every search.

That's the exact problem dense (semantic) search runs into, and this episode is about the clever shortcut that fixes it.

Why the Obvious Way Doesn't Scale

Remember: dense search turns everything into a vector (a list of numbers that captures meaning), and "most similar" means "closest vector." The obvious way to find the closest is to measure the distance from your query to every stored vector and keep the nearest ones.

That's called k-NN — k-nearest-neighbours. The k is just how many results you want back: k=5 means "give me the 5 closest."

It's perfectly accurate, and that's the trap. It's the stadium again: for 100 million products, every query does 100 million distance calculations. This is the brute-force wall — correct, but far too slow to ship.

See the wall for yourself — scan the catalogue one item at a time, then scale it up and watch the number of checks explode:

The Shortcut: Approximate Nearest Neighbour (ANN)

Here's the key insight. Do you really need the mathematically perfect closest match — or just an excellent one, instantly?

For search, "excellent and instant" wins every time. That's ANN — Approximate Nearest Neighbour search. Instead of comparing against everything, you build a smart index ahead of time that lets you jump almost straight to the best matches, checking only a tiny slice of the data.

Here's where the speed actually comes from — and it's not from looking at fewer results. It's from not having to examine everything to find them. A smart index lets you skip past almost the entire catalogue and still land on the best matches, so the work per query drops from "millions of checks" to "a few dozen" — milliseconds instead of minutes, no matter how big the dataset gets.

The word approximate is the small price for that shortcut:

Because you skipped most of the catalogue instead of scanning all of it, a genuinely close match can once in a while sit down a path the search never explored. So when you ask for, say, the 10 closest matches, it returns the true 10 almost every time — and just occasionally hands back 9 of them with a near-miss slipping in for the tenth. That tiny accuracy cost is the side-effect of the shortcut; the massive speed-up is its payoff. At scale, it's a trade worth making every time.

You'll bump into a few ANN methods by name in the real world — HNSW, IVF, DiskANN. Don't memorise them. We'll focus on just one, HNSW, because it's the default in almost every vector database you'll touch. And the nice part: HNSW is really just two simple, older ideas stacked together. Let's meet them one at a time — no HNSW required yet.

Idea One: Skip Lists — Add Express Lanes

Picture a train line where you must stop at every station to reach your destination. Slow. Now add an express line on top that stops only at major stations: ride the express to get close fast, then drop to the local line for the final stops.

A skip list is exactly that, for a list of numbers kept in sorted order — smallest on the left, largest on the right:

The bottom lane holds every value (the local train — all stops).
Each lane above keeps only some of the values below it, so the higher you go, the fewer stops and the bigger the leaps (the express).
To search: start on the top express lane and move right while the next stop is still below your target. The moment you'd overshoot, drop down one lane and keep going. You leap past most of the list instead of crawling through it.

That sorted order is the whole trick: because the values run small-to-large, "move right" always means "go bigger," so at every stop you know exactly which direction heads toward your target.

Step through a real search and watch how few stops it actually visits:

💡 Which values get "promoted" to the express lanes? It's decided randomly (a coin flip per value). That sounds odd, but it means the lanes stay evenly sparse on their own as data is added or removed — no one has to hand-tune them.

Idea Two: Navigable Small Worlds — Follow "Getting Warmer"

The second idea borrows from "six degrees of separation" — the famous notion that any two people are just a handful of "who-knows-who" introductions apart. You don't know a celebrity directly, but a friend of a friend of a friend might.

A Navigable Small World (NSW) applies that to your data. Turn every vector into a dot, and draw a line between dots that are similar. Now searching becomes a simple game of "getting warmer":

Drop in at any dot and see how close it is to your query.
Glance at that dot's neighbours and hop to whichever one is closest to the query.
Repeat — each hop lands you warmer — and stop when no neighbour is closer than where you're standing.

Because the graph mixes lots of short local links with a few long-range ones (just like real friendships), you reach the right neighbourhood in a few hops instead of checking everything.

Watch the walk find its target while touching only a handful of dots:

⚠️ The honest catch: "always hop to the warmest neighbour" can occasionally settle on a spot that's pretty close while a slightly better one sits down a path you never took. That small risk is exactly what the Approximate in ANN means — and it's a bargain we happily accept for the speed.

Two Ideas, One Index

Keep both pictures in your head:

Skip list → express lanes: sparse on top for big leaps, dense at the bottom for precision.
NSW → a graph you cross by always hopping toward "warmer."

Stack these two together — small-world graphs arranged in express-lane layers — and you get HNSW, the index behind fast dense search almost everywhere. That combination is the whole of the next episode.

What Nova Learns Next

Nova can now picture both ingredients of fast vector search: leap with express lanes, navigate by getting warmer. This episode was all about building that intuition, so there's no lab here — you'll get hands-on in Episode 41, where we snap the two ideas together into HNSW (the hierarchical graph that powers dense search in nearly every production vector database) and you'll code the layered search yourself.