Two destinations for the same primitive. UMAP uses nearest neighbors to build a skeleton of local structure for dimensionality reduction. Semantic search uses them to retrieve answers at query time.
Part 5 of Approximate Nearest Neighbors
The last four articles built up a single primitive. Given a query vector and a large collection of database vectors, find the ones that are closest. The algorithms got clever (partition, compress, design for hardware), but the question never changed.
This article is about what people do with that primitive once it works. Two destinations sit downstream of nearest-neighbor search, and they optimize for very different things. One wants structure to look at. The other wants answers to return.
Both methods need "what is near this vector?" to be fast enough and good enough. What they demand beyond that is where the two disciplines diverge. Thinking about them side by side is the clearest way to see that the three-idea stack is not one recipe but a set of dials tuned for the job at hand.
UMAP is an algorithm for projecting high-dimensional data down to two or three dimensions so that a person can look at it. Its first step, before any layout work, is to build a k-nearest-neighbor graph over the input vectors. Each point connects to its k closest neighbors in the original space.
That graph is UMAP's model of the data. It encodes the local topology of the manifold: who is near whom. The rest of the algorithm is an optimizer that embeds the graph into 2D while trying to preserve those connections. If two points are graph-neighbors in high dimensions, the optimizer pulls them together in the plane. If they are not, it pushes them apart.
The crucial observation for our purposes: the graph does not have to be perfect. UMAP does not need the true nearest neighbors. It needs a graph that roughly captures local structure. A few mistakes are smoothed out by the optimization. This is why UMAP implementations are built on approximate nearest-neighbor libraries, not exact search.
Think about the cost profile. Building the k-NN graph over a million points is a one-time job. It might take minutes. The layout step that follows is also one-time, also offline. Once the projection is produced, UMAP is done. There is no "query" in the sense that semantic search has one. You do not run UMAP in response to a user action.
This reshapes every decision about the index. Build-time cost dominates, so a memory-heavy structure like HNSW that takes a while to build but has great recall for graph construction is perfectly fine. Query-time cost is irrelevant because there are no online queries. Reranking, the step where you refine approximate matches using exact distances, is pointless: the output is a layout, not a candidate list. The graph's statistical shape is the answer.
Recall of 90% for the k-NN graph is usually indistinguishable from 100% in the final layout. The optimizer pulls the picture back toward the manifold's true shape either way.
Semantic search is the opposite side of the same primitive. A user types a sentence. An embedding model turns it into a vector. The index answers "which documents are closest?" and the top few are handed back to an application, usually as context for a language model or as direct results for the person doing the searching.
Every keystroke can trigger a query. Every user triggers many queries. The index is built once, often from millions or billions of documents, then hit constantly for the rest of its life.
Query latency dominates. A semantic search backend needs to answer in something like 50ms at the 99th percentile, and it needs to do that while the disk is busy and the network is noisy and other queries are running. The index is allowed to be expensive to build because you amortize that cost across the billions of queries it will serve.
This flips the set of reasonable choices. IVF-PQ with on-disk partitions, the combination that sits at the heart of systems like lancedb, is a sweet spot: cheap enough to keep hot shards in RAM, compressed enough to fit the long tail on SSD, fast enough to return the top-k in a few milliseconds. Reranking matters here; approximate codes get you the candidates, exact distances decide the final order. Recall@10 of 95% is typically "good enough" because a language model downstream can filter out the miss and the user rarely notices.
The three ideas from this series, partition, compress, and hardware, appear in both systems. What differs is how hard each dial is turned, and why.
The two disciplines spend their compute budget in opposite shapes. UMAP pours almost everything into a single up-front build; nothing happens afterward. Semantic search builds once and then pays a small cost on every user interaction, forever.
Approximate nearest-neighbor search is infrastructure. You rarely talk to it directly, the way you rarely talk to a database query planner or a network stack. It sits below the products we actually use: the search bar that understands what you meant, the recommender that knows what you will want next, the 2D projection that makes a million-row dataset legible in a single glance.
The fact that this works at all comes down to the three ideas in this series, stacked and tuned for the job. Partition the space so you are not looking everywhere. Compress the vectors so comparisons are cheap and the data fits. Design for the hardware you are running on. Each idea is simple in isolation. Together, they make it possible to visualize a million embeddings, retrieve from a billion documents, and power a recommender over tens of billions of users, with the same primitive.
Thanks for reading. If you want to go deeper, the series index has all five parts in one place.