The City of Ten Thousand Wells wakes to smell.

The city hangs between two ridges. Ninety-nine thousand four hundred households, one well apiece, one water apiece. The water differs, so the scent differs: the north slope’s well water carries iron and the scents it distills sit low and heavy; the south slope’s water is soft and its scents float up to the rafters; the well beneath the old locust tree at the west end is said to make cassia smell like rain just fallen.

There is a scent market in the city, and in the scent market there is a trade: scent finding.

A customer hands you a small phial holding a smell of unclear origin — the bottom of a dowry chest thirty years gone, or lacquer scraped off the planks of a sunken ship. You hold it under your nose, breathe once, and then tell them: which household in this city smells most like this.

For years the work was done on your knees.

The Pavilion of Scent Records kept a great ledger, one page per household, each page recording that household’s scent recipe: thirty-six base notes in exact qian and li, with firing times. When a customer came, old master Shen Jiu opened the ledger at page one and read to page ninety-nine thousand four hundred, comparing, page by page, for three days. Then he pointed at the closest page.

It was accurate. But the city kept growing. More than a thousand new courtyards rose each year, the ledger thickened by a sheaf each year, and every reading took longer. By the year A-Tang came to the pavilion, one reading took five days.

A-Tang could barely read. She swept the floors.

But she ran the city all day — carrying samples for Shen Jiu, fetching well water, buying charcoal. What she remembered was not pages. It was roads.

That winter she said to him: Master, stop reading the ledger. String ropes between the courtyards instead.

Shen Jiu asked: ropes for what?

A-Tang said: walk into any household, smell once, then step to whichever household it is roped to that smells closer. Keep walking. Stop at a household whose neighbors include nothing that smells closer to the customer’s phial than it does itself. That household is your answer.

Shen Jiu worked at it all night and said: fine. But how do you decide which ropes to string?

The first version went like this: every household strings sixteen ropes, each to the sixteen households whose scent is closest to its own.

They tried it in the east quarter for three months.

After three months, A-Tang untied every rope.

The trouble was not the ropes. It was the reach. Ninety-nine thousand four hundred households, sixteen ropes apiece; the city was too wide, and the ropes were too short. Starting from a doorway you had never seen, you would take a thousand shuffling half-steps — slightly closer, slightly closer — just to graze the district where the customer’s scent lived.

Worse, you got lost. There was a narrow lane in the east quarter, seventeen households, their scents so alike that all seventeen had roped themselves to each other and not one rope went out. A-Tang walked to the mouth of that lane, stepped in, and never came out again. She circled inside for forty-odd steps. Every household was closer than the last. None of them was right.

The ropes were too short because they only tied kin.

That night she sat on the well curb and watched the city’s lamps.

The city climbs a hillside. Looking up from the foot, the lights are dense below and thin above: at the base, row upon row, a single sheet of brightness; halfway up, scattered points; at the summit, three lamps.

And she understood one thing: the city needed floors.

At the bottom, everyone — ninety-nine thousand four hundred households, short ropes, one household at a time. One floor up, only a few hundred remained, and their ropes were long: one strand could cross half the city. Another floor up, a few dozen, ropes longer still. At the very top, three.

One small step at the top is ten li on the ground.

But then came the trouble: who gets a second floor?

New courtyards raise their beams every day. A-Tang could not survey the whole city first and then decide who goes upstairs — the courtyards appeared one at a time, and the shape of the city was only knowable once the city was finished. That was the fatal flaw in the whole notion.

Her answer was: draw lots.

On the day a household raises its beam, it throws a die on the threshold.

Most households land on “ground” and stay at street level their whole lives, stringing short ropes. A few land on “second” — they keep one set of ropes on the ground and another set on the second floor, where they are roped to the few hundred households that also drew a second floor. Fewer still land on “third.” Very rarely, a fourth.

The die is weighted: with every floor up, better than half of the remaining households drop out. The third and fourth floors together hold a few dozen households in the whole city, then a handful.

The floor you draw is fixed on beam-raising day and never changes. The courtyard cannot know what the city will become, but as long as the die is weighted, the floors grow themselves into a shape that is dense below and sparse above.

And none of it needs a coordinator. A new household in the east quarter knows nobody in the west quarter; it throws its die and strings its ropes. Ninety thousand households each doing only that, and the floors come out the same shape.

So scent finding became a descent.

The customer hands over the phial. A-Tang climbs to one of the three households at the summit — that is the entrance. On the top floor she does exactly one thing: look at the three neighbors, step to whichever smells closer to the customer’s phial, then again from that one. The top floor is nearly empty; a few steps and you are done. Then she takes that household’s own staircase down one floor. On the next floor, the same walk — only toward what smells closer. More households here, shorter ropes, smaller steps. Down again. The last floor is the ground, all ninety-nine thousand four hundred, and there she walks the final few dozen steps.

That day she took nine steps and knocked on the door of a dried-tangerine-peel household in the south of the city.

Shen Jiu turned the ledger to that page, checked it, looked up at her, and said nothing for a long while.

—

But the second version still failed once.

It failed on a single word: kin.

In the second version, when a household strung its ropes, it strung them to “the sixteen households that smell most like me.” That sounds self-evident and is in fact a trap.

On a single floor, if every household ropes only to its closest neighbors, then a group of households with similar scents ropes itself into a knot: you to me, me to you, every rope inside the ring, nothing out. The knot becomes an island. Someone arriving from outside can only circle within it; the closer answer outside is not reachable by a single rope.

A-Tang saw one on the dyers’ street in the north quarter: twenty-nine households, more than four hundred ropes among them, and exactly two going out.

So the rule changed: do not string to “the one most like me.” String to “the one only I can reach.”

Concretely: a household is allowed sixteen ropes. A new neighbor asks to be roped. Do not simply agree. Look at the direction that rope would point — is a rope already pointing there? If the newcomer is closer to me than the one already roped, yet farther from that already-roped one than it is from me — in other words, if it points somewhere no rope yet points — then tie it.

Sometimes this means cutting a nearer rope and keeping a farther one.

It looks like a loss. It is how you dismantle an island.

A farther rope is often exactly the door into the next district.

—

The last problem was the basket on A-Tang’s arm.

At first she remembered only one thing: the household that currently smelled closest. Walk there, then look for something closer. That walk is decisive, and it stops on false summits — a household whose every neighbor smells worse, so you halt, when one household to the side, one tolerated step of “worse,” leads on to the true district.

So you carry a basket.

The basket holds sixteen households — the sixteen closest she has met so far on the whole walk. At every step she takes the closest household in the basket whose door she has not yet knocked on; knocks; drops the new households she meets into the basket; and evicts the ones that smell least like the customer’s phial. When does she stop? When nothing left in the basket can beat the household at the bottom of it.

A big basket walks accurately and slowly. A small basket walks fast and may miss.

A-Tang settled on sixteen. Good enough, she said.

—

The city never burned the great ledger. It stayed in the Pavilion of Scent Records, opened once a year, to check whether the new method had drifted.

At the city gate A-Tang raised a wooden board, carved with the only two lines she ever wrote:

This is a map made of guesses. It does not promise the household that smells most like yours. It promises that, nearly every time, it finds one of the few that do.

Shen Jiu studied it for a while and said: you left out a line.

Which one? she asked.

He said: A guess is only worth anything if it is fast.

— —

By now you’ve probably recognized it: this is HNSW.

What it is

HNSW — Hierarchical Navigable Small World — is one of the most widely deployed approximate nearest neighbor (ANN) indexes. The problem it solves: given a query vector, find the k most similar vectors among hundreds of millions, without computing the distance to every single one.

Its structure is several proximity graphs stacked in layers:

• Layer 0 holds every vector. Each node keeps at most M_max0 = 2M edges, and edges only go to nearby points.
• Layers 1 and up hold a subset of points, sparser the higher you go, and each node keeps at most M_max = M edges. Levels are assigned with exponential decay.

Which layers a point occupies is decided at insertion time, randomly: l = floor(-ln(U) * mL), with U ~ Uniform(0,1) and mL = 1/ln(M). Roughly 1/M of points reach layer 1, 1/M² reach layer 2 — no global knowledge required, and no re-layout after the fact. A new point simply throws its die and strings its ropes, and the whole structure naturally grows dense below and sparse above.

Search happens in two phases. The upper layers are not there to find the answer; they are there to find the entry point. Starting from the entry node at the top layer, each layer runs a greedy descent (ef = 1): step only to a neighbor closer to the query, until you hit a local minimum, then drop through the same node to the next layer down. At layer 0 the search switches to a best-first candidate heap: maintain a candidate set of size ef (efSearch), always expand the closest unexpanded candidate, push its neighbors back into the set, evict the worst; stop when the best remaining candidate is no better than the worst result already collected, and return the top k.

Insertion reuses the search: greedy descent from the top to find the entry at each layer, then from the new point’s assigned top level downward, run an efConstruction-sized candidate search at each layer to find M neighbors, add bidirectional edges, and prune the excess with the paper’s heuristic neighbor selection (Algorithm 4).

That heuristic is precisely the rule A-Tang changed: keep candidate neighbor e only if e is closer to the new point than it is to any already-selected neighbor. In plain words — keep this edge only if it points somewhere no existing edge points. The rule permits cutting a nearer, redundant-direction neighbor to keep a farther one that opens a new direction. Without it, the graph degenerates into dense, mutually disconnected clumps, and greedy search walks in and never walks out.

Query and insert both cost O(log N). The price is memory: each point stores M_max0 + M × (levels - 1) edges, roughly 4 bytes per edge.

Why it matters

Embeddings are now the common interface for semantic search, RAG retrieval, recommendation recall, image deduplication, and anomaly detection. But at production scale, brute force collapses: ten million 768-dimensional vectors is 7.68 billion floating-point multiply-adds per query — hundreds of milliseconds to seconds each, which caps QPS and inflates cost.

ANN indexes trade a little recall for orders of magnitude in latency. HNSW has long occupied the sweet spot in that trade: in-memory, low-latency, high-recall, without IVF’s cluster-then-probe-buckets structure or PQ’s compressed-codebook distance approximation. Faiss, hnswlib, Qdrant, Weaviate, Milvus, pgvector, and Elasticsearch’s vector search all ship it as the default or primary index.

That importance is also where the sharp edges are:

• It is approximate, and that approximation is a product decision, not a bug. The metric is recall@k — how many of the true top k you actually returned. Turning efSearch up slides along the latency/recall curve; most production systems accept 0.95 rather than 0.999, because the last few points cost another multiple of the query time.
• The parameters are not mysticism, but there is no universal setting. M sets graph connectivity and memory; efConstruction sets build quality (it affects indexing only, never query time); efSearch is the runtime dial. Too small an M and the graph fragments into islands; too large and memory and build time rise linearly while recall saturates almost immediately.
• Greedy search gets trapped in local optima. That is exactly why the upper layers must be sparse: long edges in sparse layers provide the cross-region jumps that let the descent go coarse-to-fine. This is the “small world” part — a handful of long-range links collapse the graph’s diameter.
• Deletion is awkward. A graph does not let you cleanly remove a node, because other nodes’ edges point at it. In practice you tombstone it or periodically rebuild the whole index. In write-heavy, delete-heavy workloads, maintenance cost matters more than query cost.
• Filtered search is the real hard problem. “Nearest neighbors where tenant_id = 42 and created_at > ...” — filter first and the subgraph may be disconnected; search first and you miss. This is why vector databases with metadata filtering are consistently slower and lower-recall than the unfiltered case.
• It is a graph, so it shards badly. Graphs have no natural hash boundary: cross-shard edges either get cut (recall drops) or duplicated (memory grows). Large-scale vector search systems therefore keep re-litigating “shard + independent HNSW per shard + merge results” versus “one big box with a lot of RAM.”

Metaphor mapping

• Ninety-nine thousand four hundred households → every vector in the store (N points)
• A household’s scent → a vector (embedding)
• How alike two scents are → distance or similarity between vectors (cosine, inner product, L2)
• The customer’s phial → the query vector
• Finding the few households that smell most alike → k-nearest-neighbor search
• The great ledger, read page by page → brute-force / flat search, O(N·d)
• Five days per reading, and the city still growing → scan cost rising linearly with corpus size
• Ropes strung between courtyards → edges of a proximity graph
• At most sixteen ropes per household → maximum out-degree M (2M at layer 0)
• Start anywhere, step only toward a closer-smelling neighbor → greedy search on the graph
• Walking into the narrow lane and never getting out → local optimum / disconnected graph
• Lights dense at the base, three lamps at the summit → layered structure, exponentially fewer points per layer
• One die throw on beam-raising day → random level assignment at insertion, l = floor(-ln(U) · mL)
• Better than half the households lost per floor up → geometric distribution, about 1/M reach the next layer
• Weighted die, no coordinator → local randomness producing a global layered shape
• Taking that household’s own staircase down → descending from the current node to the next layer
• A few top-floor steps crossing half the city → long edges in sparse layers enabling cross-region jumps
• The last few dozen steps on the ground → fine-grained ef search at layer 0
• Stepping only toward what smells closer → greedy descent with ef = 1
• Similar households roped into a knot with nothing pointing out → nearest-neighbor-only graphs degenerating into dense islands
• Roping to “the ones most like me” → naive k-nearest-neighbor edge selection
• Roping to “the one only I can reach” → heuristic neighbor selection keeping only new-direction edges
• Cutting a nearer rope for a farther one → sacrificing distance for diversity and navigability
• A basket holding sixteen households → candidate set size efSearch
• Tolerating one step that smells worse → ef > 1 escaping local optima
• A big basket is accurate and slow → the efSearch recall/latency tradeoff
• Stopping when nothing in the basket can do better → termination condition when the candidate set is exhausted
• Nine steps to the right door → O(log N)-scale query complexity
• “This is a map made of guesses” → HNSW is approximate, with no exactness guarantee
• “Not the closest, but one of the closest few” → recall@k as the metric of record
• Opening the ledger once a year to check for drift → offline exact search used to calibrate ANN recall
• “A guess is only worth anything if it is fast” → the entire value of ANN is trading bounded recall loss for order-of-magnitude latency wins
• A new household needs no knowledge of the far city → insertion is purely local, with no global coordination
• The two outward ropes that dismantle an island → a small number of long-range edges determine whether the graph is navigable at all