Tiny Towns

Every real corpus has towns. Embed 7 years of iMessage history and every “lol” you ever sent lands on the same vector. Same text in, same point out. Every single time. So the map ends up dotted with what I’ll call zero-acreage towns: hundreds or thousands of residents, all standing on one point, with literally no space between them.

The folklore says duplicates are just untidy. Dedup them, save some memory, move on. The author of HNSW himself warned in a GitHub comment that big duplicate clusters can cost the graph its connectivity. But nobody ever measured what they actually do.

Turns out the folklore undersold it. And pointed it in the wrong direction.

The towns are real

The wild half of this study runs on my own iMessage history: 369,040 messages across 7 years, embedded with MiniLM (same encoder family as the companion study). The census: 9,115 towns with 2 or more residents, holding 18.7% of the corpus. 44 towns have over 100 residents.

And the biggest town is invisible. It’s the attachment placeholder character that iMessage quietly inserts for every photo + video. 14,082 residents on one point. 3.8% of the entire corpus.

Finding 1: the zero-acreage law

Here’s the clean experiment. Take a healthy 29k-document corpus (real chat chunks, baseline serving cost ef* = 54) and inject one synthetic town. Vary two things independently: the town’s population s (100 up to 10,000 copies), and its acreage ε (the diameter of the little ball the residents get scattered in, from exactly 0 up to 0.1). 3 index builds per cell. And a control arm adds the same number of points as jittered copies of s different documents, to separate “concentrated mass” from “duplicate mass.”

That indicator function is the whole law. 10,000 residents with ε = 0.003 of elbow room: harmless, 3 builds out of 3. The same 10,000 on a single point: every build damaged, one of them at triple the baseline cost. Somewhere between 3,000 and 10,000 residents (10 to 25% of this corpus) the trap arms itself. Below that, it sleeps.

And concentration alone is innocent. The spread control proves the mass has to be coincident, not just close together.

Where exactly is “zero”? The micro-sweep

A fair objection (raised by a sharp reviewer): showing harm at 0 and health at 0.003 proves a sharp transition somewhere below 0.003, not a wall at exactly zero. So we walked the ladder: ε from 1e-8 up to 3e-3, 3 builds per rung, on both libraries.

First surprise: at ε = 1e-8, every one of the 10,000 residents is already bitwise unique (float32 spreads the jitter unevenly across coordinates, so each vector picks up at least one distinct bit). And the index is exactly as sick as at ε = 0. The trap is NOT about identical bits. You can make every vector distinct and change nothing.

The transition tracks something better than bits: what the distance function can resolve. Float32 distances near 1.0 quantize at about 1.2e-7. Below that spacing, every islander presents identical computed distances to every candidate, all the neighbor-selection comparisons are exact ties, and the harm is total. Right at 1e-7 the curve breaks. And the small residual tail clears near 3.5e-4, which is exactly where islander-to-islander distances (r²/2 in cosine space) stop rounding to 0.0. Two knees, both sitting on float32 resolution boundaries, same shape in both libraries.

Why does that break the graph? HNSW picks neighbors with a diversity rule: keep a candidate only if it’s closer to the new point than to any neighbor you already kept. Inside a town the math can’t resolve, every one of those comparisons is a tie. The wiring that falls out of thousands of tie-broken comparisons is broken wiring. Give the residents spacing the math can SEE and the comparisons mean something again. (We went after the mechanism directly. See the nulls for what the obvious explanation turned out NOT to be.)

So the honest version of the law: acreage only counts if the distance math can see it. Invisible acreage is zero acreage. And that’s why the practical dose (0.003) works everywhere... it sits comfortably above every resolution scale in the pipeline.

Finding 2: amputation, not a tax

“Costs more ef” undersells what the hot cells do. Push the search budget to ef = 600, eleven times the healthy baseline, and watch what it buys:

Two verification passes stand behind that figure, because the obvious objection is scoring. With 10,000 identical vectors, exact ground truth is full of tied distances, and ties could fake a recall drop with zero real damage. So we checked. Only 1 of 1,000 queries even has town residents in its true top-10, and re-scoring with the whole town collapsed into one result moves the curves by one part in ten thousand.

The damage is real.

And here’s the part folklore got backwards. Every prior mention of duplicate trouble (including from the HNSW author) frames it locally: the copies themselves get hard to find, or search gets stuck near the pile. We tagged every dead query, here and across the whole replication battery. Out of 2,831 dead queries, not one had a duplicate in its true answers. On this corpus the victims scatter across the entire space. On others they cluster in the pile’s general region. Either way, their correct results have nothing to do with the town.

A zero-acreage town doesn’t hurt its own residents. It takes bystanders.

Finding 3: the build lottery

Same vectors, same parameters, 3 builds of the hot cell: ef* of 80, 80, 180. The unlucky build costs 3.3x baseline and kills 7.5% of queries. Its siblings pay 1.5x and lose 3%. On the clean corpus, those same 3 builds land within one rung of each other. Zero-acreage towns turn index construction into a lottery. And since multithreaded insertion makes every build unique regardless of seed, every rebuild is a fresh ticket.

The lottery has a tail. While chasing an old anomaly in this corpus’s research logs, we found a build from an earlier study (same data, same parameters) that couldn’t return k = 100 results at all. insufficient_results at ef = 400. The whole lane dead. We rebuilt it twice: 0 failures in 6,000 attempts. That build was a rare catastrophic ticket... a graph so fragmented by the towns that 100 connected candidates couldn’t be gathered. Rare enough to miss in 3 builds. Real enough that it burned us once already.

So if your index has big zero-acreage towns, CI passing on THIS build says pretty much nothing about the next one.

Finding 4: the cure in the wild

Everything above is a synthetic town injected into a small corpus. The real test: the full 369k-message corpus with its 9,115 natural towns, 600 real queries, 3 builds per variant, and two fixes. Dedup keeps one resident per town (310,918 vectors). Jitter keeps every vector but gives each duplicate copy ε = 0.003 of acreage. That’s a nudge of about 0.3% of typical document spacing. Way below any semantic difference.

Three things worth staring at here.

The mystery this solves: this corpus’s recall ceiling had been measured at ~0.95 in an earlier study and nobody knew why.

It’s the towns.

The lottery dies too: 36/36/80 becomes 24/24/24. Three builds, indistinguishable. And the economics flip. Curing the towns doesn’t cost performance, it refunds it: a third off the serving bill, because search no longer wades through walls of coincident points.

One difference from the lab: on the real corpus the dead queries ARE town-adjacent (their true neighborhoods carry 21 to 28x more big-town mass than average). The lab’s single monster town (26% of its corpus) hurt far-field. The wild’s many mid-size towns hurt near-field. Same law, dose-dependent blast radius: as the pile grows past everything else in the space, the damage goes global.

Finding 5: it replicates everywhere we looked

One corpus + one library is an observation. So we ran the same 5-condition signature (baseline, 25% pile at ε=0, same pile jittered, spread control, 10% pile) on 4 more corpora + a second library. Different content types, different encoders, different dimensions, and one corpus that isn’t even cosine (SIFT is raw image features under L2 distance). The jitter dose scales with each corpus’s vector norms (0.003 relative).

Same signature every time. Only ε=0 detonates. The jitter rescues. The spread control is innocent everywhere. And the lottery shows up on every corpus: arXiv’s three builds of the identical hot cell came out 24, 36, and 700. MS MARCO’s came out 120, 700, 700 with the worst build silently dropping a quarter of all queries. If you benchmark the lucky build, you ship the trap.

Two honest wrinkles. faiss takes roughly 3x more damage than hnswlib from the same pile (a 10% pile that hnswlib mostly shrugs off kills up to 12% of faiss queries). And SIFT is the one place the jitter cure is partial: 8 to 32 dead queries remain against a baseline of 0, so L2’s critical diameter may sit above our relative dose there. Dedup remains the sure cure.

Finding 6: it happens in the wild, without help

Everything so far either injected a synthetic town or used my own iMessage history. Fair question: does this happen naturally, on data anyone can check? So we went hunting for raw public corpora... and found that the popular benchmarks couldn’t answer the question, because their creators dedup’d them (one Reddit dataset literally filters out [deleted], the biggest town Reddit has). The disease lives in RAW data. So we got some: the Enron email archive, a 1M-tweet customer-support corpus, and 1M lines of Ubuntu IRC chat. Indexed each one exactly as it ships. No injections. Queries are 1,000 substantive texts that appear exactly once in the corpus, so no query is ever a town resident.

Four raw corpora tested, four natural victims. The towns doing the damage are exactly what you’d guess: Enron’s empty bodies (×6,325), a legal-department signature block (×1,321), and “Best, Jeff” (×1,117). The support corpus’s canned brand replies (×874, ×725, ×557). IRC’s “thank” (×12,366). And the attribution holds in the wild: on Enron and Twitter the dead queries’ true neighborhoods carry 30 to 108x more town mass than average (near-field bystanders), while on Ubuntu the dead queries carry ZERO town mass... the far-field geometry from the lab, occurring naturally. Both blast shapes are real.

The playbook

What didn’t survive contact with the data

Three plausible stories died on the way to this page. The corpses are informative:

The upper-layer story. The obvious mechanism (the town’s thousands of copies get promoted into HNSW’s sparse upper routing layers and wreck navigation from above) is testably wrong. Or at least it’s not the dose. We parsed the built graphs, and the town owns almost exactly its population share of every layer in every build, detonating and benign alike. Level assignment is pure RNG. It never looks at geometry. The damage variance lives in the wiring the degenerate pruning emits, not in who gets promoted.

The off-grid statistic. We tried to build a cheap predictor of ceiling damage: the share of the population more than 3 hops off the kNN graph’s hub core. It turned out to be anti-correlated with health. The hot lab cell scores as the most connected corpus we measured, because a 10k-resident town is a mega-hub, maximally ON grid. HNSW’s failure is about search dynamics over pruned wiring, not raw kNN connectivity. (Which also means the damage is invisible to standard geometry probes. Including q_plateau, which goes literally undefined on town-heavy corpora: a query that IS a duplicated text has its 10th and 50th neighbors both at distance zero, and 0/0 isn’t a contrast ratio. Guard your denominators.)

The ef-paradox. The archive briefly suggested a build that failed at high ef but passed at low ef. Genuinely spooky. Then we re-read the logs: the low-ef success never existed. The build had simply failed everything it was asked. The spooky version dissolved into the catastrophic-ticket story in Finding 3. Always re-read the logs.

Prior art: the prophecy in the issue tracker

The mechanism was suspected. Qualitatively, in GitHub comments, most notably by HNSW’s own author. What we couldn’t find anywhere: measurements, the zero-diameter criticality, the far-field damage, the catastrophic build lottery, or the jitter cure. The published advice is uniformly “dedup.” And nobody seems to have noticed that curing the towns makes serving cheaper.

Methods & caveats

Setup. hnswlib, cosine space, M=16, efConstruction=200, 3 builds per condition. ef* is the smallest rung on a fixed ladder (10 to 600) reaching mean recall@10 of 0.90 or better against exact search on the same corpus. Lab corpus: 28,932 chat-session chunks, MiniLM-L6 (384d), 1,000 real held-out queries (300 for the k=100 serviceability lanes). Wild corpus: 369,040 iMessages, same encoder, 600 real reply-recovery queries. Ground truth per variant is exact search on that variant’s own vectors. Towns are exact string-duplicate groups. Jitter: for each duplicate copy beyond the first, add a uniform-in-ball perturbation of radius 0.003 and renormalize. Dead query = per-query recall@10 below 0.5 at ef=600. Level censuses parse the hnswlib binary directly.

Replication battery. Same 5-condition x 3-build signature on: chat chunks 29k under faiss 1.15 (IndexHNSWFlat, M=16, efConstruction=200, 3 insertion-order shuffles as builds), SIFT-1M (L2, 10k standard test queries, first 1,000), GloVe-1.18M angular (standard test queries), MS MARCO passages x Qwen-0.6B 500k prefix (1,000 real Bing dev queries), and 399k arXiv abstracts (1,000 held-out abstracts as queries; a weaker query set, but the injection differential is measured against the same queries in both conditions). Jitter dose per corpus = 0.003 x median vector norm.

Caveats, honestly held. Two libraries now (hnswlib + faiss), but other graph indexes (DiskANN, NSG, Vamana) still untested. SIFT’s jitter rescue is partial (8 to 32 residual dead queries), so the transition under L2 may sit at a different relative scale... dedup is the sure cure. The population threshold for a single town is relative to corpus size and was mapped at 29k; the wild corpus shows many smaller towns produce a milder, near-field version. The ε micro-sweep (1e-8 to 3e-3, both libraries, flagship cell) pins the transition to float32 distance-resolution boundaries: full harm through 1e-7 with all vectors bitwise unique, knee at 1e-6, near-cure by 1e-5, total by 3e-3, residual tail clearing where within-island distances stop rounding to 0.0 (about 3.5e-4). The resolution story makes a testable prediction we haven’t run: a float64 distance pipeline should shift the knee about 9 decades left.

The experiment scripts (islandtrap_a/a2/b/b2/r/eps/n, islandtrap_mech, tinytowns_c) run on consumer Apple-silicon hardware in about 2 hours total, for a compute cost of roughly nothing. The companion study (how to price your vector search before building anything) lives at ann.itsnick.co.

Small worlds, tiny towns. The graph is a map of places, and search is just trying to get home. The map only fails when too many people claim to live on a single point of it. Give everyone even a hair of space to stand apart... and every road works again.