Locality-Sensitive Hashing: Collision Probability and the ρ Exponent

Overview & motivation

Two ANN families so far have avoided scanning every vector by learning the data. IVF read the cloud’s density with k-means and cut it into Voronoi cells you probe; the navigable-graph topics built a structure from the insertion order and walked it. Both look at the points before they answer. Locality-sensitive hashing is the third family, and it makes the opposite bet: fix the partition before seeing a single vector, using randomness alone, and lean on a theorem to make it work.

The theorem is the whole design. A hash function is locality-sensitive if near points are more likely to land in the same bucket than far ones — collision probability is a decreasing function of distance. If you have such a family, retrieval is almost trivial: hash every database vector into a table, hash the query, and scan only the bucket it lands in. The near neighbors are probably there because near points probably collide. Everything hard is in turning “probably” into a guarantee with a tunable knob, and in paying honestly for the fact that the hash never looked at your data.

angle θ / π = 0.30

exact collision 1 − θ/π

0.70

angle θ

54°

One bit per random hyperplane. A plane separates x and y exactly when its normal lands in the wedge between them — angular measure θ/π — so the two collide with probability 1 − θ/π. The measured points sit on the line because the law is exact, not fitted.

The first panel is the exact angular law on the unit circle — random-hyperplane normals colored by whether they separate two vectors, with the collision probability falling linearly in the angle. The second is amplification: the S-curve that the AND/OR construction bends into a sharp threshold. The third is the payoff and the price — the sublinear exponent ρ on the left, and a cross-index head-to-head on the right where, told honestly, the data-aware indexes win.

Movement 1 — the family and its collision probability

We need a concrete locality-sensitive family, and the cleanest one is the one already half-built in the prerequisite. Random projection multiplies a vector by a random matrix; SimHash keeps only the sign of each coordinate of that projection. One random Gaussian vector $\mathbf{h}$ defines one bit, $b(\mathbf{x}) = \mathbf{1}[\langle \mathbf{x}, \mathbf{h}\rangle \ge 0]$ — which side of the hyperplane through the origin with normal $\mathbf{h}$ the point falls on. A $k$ -bit signature is $k$ such bits. Because only the sign matters, the $1/\sqrt{k}$ scaling that Johnson–Lindenstrauss applies is irrelevant here: the random hyperplanes are the projection rows, reused verbatim.

Definition 1 (A locality-sensitive hash family).

A family $\mathcal{H}$ of hash functions is $(r_1, r_2, p_1, p_2)$ -sensitive for a distance $d$ if, for $h$ drawn uniformly from $\mathcal{H}$ ,

d(\mathbf{x}, \mathbf{y}) \le r_1 \;\Rightarrow\; \Pr[h(\mathbf{x}) = h(\mathbf{y})] \ge p_1, \qquad d(\mathbf{x}, \mathbf{y}) \ge r_2 \;\Rightarrow\; \Pr[h(\mathbf{x}) = h(\mathbf{y})] \le p_2.

The family is useful when $r_1 < r_2$ and $p_1 > p_2$ : near points (within $r_1$ ) collide at least as often as $p_1$ , far points (beyond $r_2$ ) at most as often as $p_2$ , and the gap between $p_1$ and $p_2$ is what amplification will widen into a usable filter.

For SimHash the relevant distance is the angle, and the collision probability is not an inequality to be estimated but an exact closed form.

Theorem 1 (The SimHash collision law).

Let $\mathbf{x}, \mathbf{y}$ have angle $\theta = \angle(\mathbf{x}, \mathbf{y}) \in [0, \pi]$ , and let $h$ be a single random-hyperplane bit with normal $\mathbf{h}$ drawn from a spherically symmetric distribution. Then

\Pr[h(\mathbf{x}) = h(\mathbf{y})] = 1 - \frac{\theta}{\pi}.

The hyperplane separates $\mathbf{x}$ and $\mathbf{y}$ — assigns them opposite bits — exactly when its normal falls in the wedge spanned between them, whose angular measure, relative to the full circle of directions, is $\theta/\pi$ . So they collide with the complementary probability $1 - \theta/\pi$ . The law is linear in the angle, exact for any dimension, and depends on nothing but $\theta$ .

The companion code drives the law directly: it builds pairs of unit vectors at a controlled angle $\theta = \tfrac{\theta}{\pi}\cdot\pi$ and measures the fraction of thousands of random hyperplanes that fail to separate them. At $\theta/\pi = (0.1,\,0.3,\,0.5,\,0.7,\,0.9)$ the measured collision rates are $(0.9009,\,0.7025,\,0.5019,\,0.3029,\,0.1066)$ against the predicted $1 - \theta/\pi = (0.9,\,0.7,\,0.5,\,0.3,\,0.1)$ . The points land on the line because the law is exact, not fitted — this is the number the whole index is built on.

Movement 2 — amplification: AND/OR and the S-curve

A single bit collides with probability $1 - \theta/\pi$ , which for any interesting angle is far too gradual to separate near from far: at $\theta = \pi/4$ the collision is $0.75$ , at $\theta = \pi/2$ still $0.5$ . A useful index needs the collision probability to be near one for true neighbors and near zero for everything else — a step, not a ramp. Amplification builds that step out of the gradual base law with two compositions.

Theorem 2 (The AND/OR S-curve).

Let $p = 1 - \theta/\pi$ be the base collision probability of a single bit. Concatenate $k$ independent bits into one table key (an AND: the keys match only if all $k$ bits agree, probability $p^k$ ), and maintain $L$ independent such tables (an OR: two points are candidates if they collide in any table). The probability that $\mathbf{x}$ and $\mathbf{y}$ become candidates is

g(p) = 1 - \left(1 - p^{\,k}\right)^{L}.

As a function of $p$ this is an S-curve: $k$ slides the threshold rightward and steepens it (a stricter AND), $L$ raises the whole curve (a more forgiving OR). At $k = L = 1$ it collapses to the identity $g(p) = p$ — the bare hash, the byte-for-byte anchor the code checks.

The two knobs pull in opposite directions, and reading the verified S-curves shows it. At a base $p = 0.85$ (an angle $\theta = 0.15\pi$ , the kind of small gap a true neighbor sits at), the $(k=16,\,L=4)$ family collides with probability only $0.2655$ — sixteen bits is a demanding AND — while $(k=8,\,L=8)$ collides at $0.9215$ , because eight tables is a forgiving OR. Tuning $(k,L)$ places the steep part of the curve right between the near angle you want to keep and the far angle you want to drop. That is the engineering of an LSH index: choose $k$ to push the threshold past the far radius, then choose $L$ to pull the near radius back above it. The price of a larger $L$ is a larger candidate set — every table contributes its bucket to the union you must then rank exactly.

Movement 3 — the ρ exponent and sublinear query time

Amplification gives recall; the reason to use LSH at all is what it costs. The headline result of Indyk and Motwani is that the AND/OR knobs can be set so the query touches a sublinear number of points, and the exponent that controls it is a clean ratio of the two collision probabilities.

Theorem 3 (The ρ exponent and the query-time bound).

For an $(r_1, r_2, p_1, p_2)$ -sensitive family, set $k = \log_{1/p_2} n$ and $L = n^{\rho}$ with

\rho = \frac{\ln(1/p_1)}{\ln(1/p_2)}.

Then the $(c, r)$ -approximate near-neighbor problem (with $c = r_2/r_1$ ) is solved with query time $O(n^{\rho})$ and space $O(n^{1+\rho})$ , and $\rho < 1$ whenever $p_1 > p_2$ . The choice of $k$ makes a random far point’s expected collisions $O(1)$ per table; the choice of $L$ makes a near point collide in some table with constant probability. Query time is sublinear, by a family that never examined the data.

The exponent rewards a wider gap. Fixing the near angle at $\theta_1 = 0.15\pi$ (so $p_1 = 0.85$ ) and widening the far angle by an approximation factor $c$ , the verified $\rho$ falls from $0.7827$ at $c = 1.25$ to $0.4556$ at $c = 2$ to $0.1774$ at $c = 4$ : a search willing to accept a four-times-looser “near” is an easy problem, $\rho$ near a fifth, query time close to $n^{1/5}$ . An easier approximation is a cheaper search, made quantitative.

What the exponent does not say is that LSH wins in practice, and the honest way to see this is to run it against the indexes that learn the data.

Proposition 1 (The head-to-head, on one normalized cloud).

Build LSH, IVF, flat-NSW, and HNSW on the same cloud and score them against the same ground truth, by distance computations per query. To compare angular SimHash against the Euclidean indexes fairly, L2-normalize the cloud: for unit vectors $\lVert \mathbf{x} - \mathbf{y}\rVert^2 = 2 - 2\cos\theta$ , so the Euclidean top- $k$ ranking is the angular ranking and the ground truth is shared by construction. Count LSH’s cost honestly — the $L\cdot k$ hyperplane projections that hash the query (the analogue of IVF’s coarse centroid comparisons) plus one exact distance per candidate.

On this low-rank cloud the data-aware indexes dominate. To reach recall $0.9$ , HNSW spends $82$ distance computations per query, IVF spends $113$ , and LSH spends $486$ — and past a few dozen tables LSH does more work than a brute-force scan of all $500$ vectors. This is a verdict on this cloud, not a universal ranking.

The proposition reads like a defeat for LSH, and on this data it is — but the reason is instructive. LSH’s candidate work is small: at recall $0.94$ its buckets surface only about $38$ vectors to rank exactly, fewer than HNSW touches. What sinks it is the hashing overhead — to get recall on a tightly clustered, low-dimensional cloud the oblivious hash needs many tables, and $L\cdot k$ projections at $n = 500$ is nearly a full scan on its own. That overhead amortizes only as $n$ grows, and the dominance of the structure-aware indexes is exactly what you should expect when the data has structure to learn. LSH’s case is the opposite regime: very high dimension where graphs and inverted files degrade, adversarial or shifting data where no learned partition can be trusted, and the distribution-free worst-case guarantee that $\rho < 1$ provides no matter what the data does.

§ Finance case study text

A production retrieval system over financial filings embeds each chunk into a normalized vector where cosine similarity is the native metric — and cosine similarity is exactly angular distance, the regime where SimHash’s $1 - \theta/\pi$ law is exact. That makes random-hyperplane LSH the natural data-oblivious baseline: bit-pack each filing’s embedding into a $k$ -bit signature, bucket by signature, and answer a query by Hamming-near buckets. Its appeal is not raw recall — the head-to-head shows a learned index beats it on a structured corpus — but three operational properties the learned indexes lack. The signatures are tiny (a few bytes per document), so a first-stage filter over tens of millions of chunks fits in memory where the full vectors would not; the hash is update-free, so a streaming feed of new filings needs no re-training of a quantizer or re-linking of a graph; and the collision guarantee is distribution-free, so a sudden regime shift in the embedding distribution — a new asset class, a new document modality — cannot silently degrade it the way a stale k-means partition would. LSH earns its place as the cheap, robust coarse filter beneath a structure-aware reranker, not as the reranker itself.

Honest accounting

⚠ Rigor flag

The collision law $1 - \theta/\pi$ is exact, but exact only for the random-hyperplane family — the p-stable family for Euclidean distance obeys a different law, and quoting the angular law for an L2 index is the wrong-family error. The $O(n^{\rho})$ guarantee is worst-case for the approximate-near-neighbor decision problem under a data-independent family, so realized recall on real data is not what the exponent promises, and SimHash’s $\rho$ is not optimal: data-dependent and cross-polytope hashing achieve a smaller exponent for the same gap. Amplification’s recall is probabilistic over the random tables, so any single index can miss a true neighbor that no table happened to bucket with the query. And the head-to-head is one verdict on one synthetic normalized cloud, where a data-aware index that learns the cloud’s structure is expected to dominate the oblivious hash at equal cost — on that low-rank cloud LSH never wins, and the place to reach for it is the opposite regime: very high dimension, streaming or adversarial data, and the distribution-free guarantee no learned partition can match.

LSH completes the partition-family side of the ANN story: IVF’s learned Voronoi cells and LSH’s random buckets are the two ways to slice the space without scanning it, one data-dependent and one data-oblivious, and the graph indexes are the third way that abandons a partition for a walk. What remains on the ANN thread is the other axis of richness — when a document is not one vector but many, and a query must be scored against the best match among them, the index must change shape again. Multi-vector and late-interaction indexing, where the pruning of that many-to-many match at scale is its own problem, is where the thread continues.