Random Hyperplane LSH and the Arithmetic of Banding

Locality-sensitive hashing is the oldest family of approximate nearest-neighbor methods still in wide use, and its mathematics is unusually clean: a hash family whose collision probability is a known function of the similarity score, plus a combinatorial trick that reshapes that function into whatever recall curve the application needs. The first half is geometry; the second half is counting. Most of the practical difficulty lives in the second half, because the curve produced by banding is steep and unforgiving near its threshold.

One random plane, one bit, one probability

Take two unit vectors $u$ and $v$ in $\mathbb{R}^d$ with angle $\theta$ between them. Choose a random hyperplane through the origin by drawing a vector $r$ from a spherically symmetric distribution, for instance the standard normal in every coordinate. Hash each vector by the sign of its projection:

$$h_r(x) = \begin{cases} 1 & r \cdot x \ge 0 \ 0 & r \cdot x < 0 \end{cases}$$

The two vectors collide when $r$ falls on the same side relative to both, which happens exactly when $r$ does not lie in the wedge between them. That wedge subtends angle $\theta$ out of the full circle of directions perpendicular to the plane spanned by $u$ and $v$, so

$$P[h_r(u) = h_r(v)] = 1 - \frac{\theta}{\pi}$$

This is Charikar’s result for the sign of a random projection. It gives an LSH family for cosine similarity with the collision probability decreasing linearly in the angle and therefore, since $\theta = \arccos(u \cdot v)$, monotonically decreasing in the cosine score. For a cosine of $0.9$, the angle is about $25.8°$, so the collision probability is roughly $1 - 25.8/180 \approx 0.857$. For a cosine of $0.7$, the angle is about $45.6°$ and the probability is roughly $0.747$. For orthogonal vectors the probability is one half, the value any pair of random signs would produce anyway.

One bit distinguishes almost nothing. 0.857 against 0.747 is a difference of one collision in nine, and drawing a single hash bit per record partitions a million items into two buckets of half a million each, where both relevant and irrelevant items are present in abundance. The signal has to be amplified, and amplification is where the parameters come from.

Amplification by concatenation and by repetition

Two independent operations act on the collision probability $p$.

Concatenating $r$ bits into a single key replaces $p$ with $p^r$. The key is now long, so buckets are small, but the collision probability for even a fairly similar pair drops fast: with $p = 0.857$ and $r = 20$, the probability is $0.857^{20} \approx 0.045$. Similar items rarely share a key.

Repeating the whole arrangement $b$ times and taking the union of all buckets that match in any repetition replaces $p$ with $1 - (1 - p^r)^b$. Twenty rows with $b = 20$ bands gives $1 - (1 - 0.045)^{20} \approx 1 - 0.955^{20} \approx 0.60$. Recall recovers at the cost of twenty tables, each storing one key per record.

The composed function is the workhorse:

$$P_{\text{hit}}(p) = 1 - \left(1 - p^{r}\right)^{b}$$

Its shape is what makes LSH tunable. At small $p$ the inner term $p^r$ is tiny, so the expression is roughly $b,p^{r}$, growing as a power of $r$ and therefore nearly flat and near zero. At large $p$ the inner term approaches one from below, and $1 - p^r$ is small, so the expression approaches $1 - (1-p^r)^b$, saturating at one. Between the two regimes the curve rises over a narrow interval of $p$, and the position of that rise is set by the ratio of $b$ to $r$.

The threshold is conventionally defined as the value $p^\ast$ at which the hit probability equals one half:

$$1 - \left(1 - (p^\ast)^{r}\right)^{b} = \tfrac{1}{2} \implies (p^\ast)^{r} = 1 - 2^{-1/b}$$

For large $b$ the right side approaches $\ln 2 / b$, giving $p^\ast \approx (\ln 2 / b)^{1/r}$. With $b = 100$ and $r = 10$, that is roughly $(0.00693)^{0.1} \approx 0.60$. Pairs with collision probability above 0.60 are found with probability greater than one half; pairs below are usually missed. A collection where the interesting pairs have $p$ around 0.5 will be missed by a wide margin with these parameters, and no amount of table repetition fixes it, because repetition only raises the floor toward one for pairs that already pass the per-band test.

Reading the table: what a lookup actually costs

Storage is $b$ tables each holding $n$ keys of $r$ bits, plus the original vectors if candidates are to be rescored. At $r = 10$ bits and $n = 10^6$ records, the keys themselves are 10 megabits, a little over a megabyte, negligible against the gigabytes of vector data. The hash table structure that maps keys to posting lists is the real cost: a dictionary with $b$ entries per record and a posting list per occupied bucket. If buckets average a few records, the posting lists dominate and the overhead is comparable to a small multiple of the key size.

The query cost is the sum of the posting list lengths over the $b$ buckets the query lands in. A bucket of average size $s$ contributes $s$ candidates, so a query inspects roughly $b \cdot s$ candidates before deduplication. With $b = 100$ and average bucket size 4, that is 400 candidates, and each must be rescored exactly: 400 exact distance computations against 768-dimensional vectors is a small fraction of a full scan of a million, so the amplification pays for itself.

Bucket size is not uniform, and the imbalance is the operational problem. A cluster of near-duplicate records all land in the same bucket and that bucket’s posting list grows without bound. For a collection with heavy duplication, the longest posting list can be orders of magnitude longer than the mean, and queries that land in it become as expensive as the full scan they were meant to avoid. The standard mitigations are to cap posting list length and fall back to a sample, or to deduplicate the collection before indexing. Both change recall in ways that are easy to overlook, and a capped list drops the records that were added last.

Choosing r and b against a target

The parameters are chosen from two constraints: a target recall at a given similarity level, and a budget on tables.

Let $p_1$ be the collision probability of a pair that should be found, and $p_2$ the probability of a pair that need not be. The classical formulation asks for $P_{\text{hit}}(p_1) \ge 1 - \delta$ and $P_{\text{hit}}(p_2) \le \delta$, which can be satisfied by choosing $r$ so that $p_1^r / p_2^r = (p_1/p_2)^r$ is large, then $b$ large enough to lift the $p_1$ case. Since the ratio condition depends only on $r$, and the recall condition only on $b$ once $r$ is fixed, the two parameters separate cleanly.

import math

def hit_probability(p: float, r: int, b: int) -> float:
    return 1.0 - (1.0 - p ** r) ** b

def choose_params(p_target: float, recall: float, max_b: int = 256) -> tuple[int, int]:
    """Rows and bands for a target hit probability at p_target.

    r is derived from the largest allowed band count, then the smallest b that
    meets the target is chosen. If no b within max_b meets it, max_b is returned
    and the achievable probability is below the target.
    """
    delta = 1.0 - recall
    # p^r must exceed 1 - delta^(1/b); solving for r at the largest allowed b
    # gives the fewest rows that can still reach the target.
    r = max(1, math.ceil(math.log(1.0 - delta ** (1.0 / max_b)) / math.log(p_target)))
    for b in range(1, max_b + 1):
        if hit_probability(p_target, r, b) >= recall:
            return r, b
    return r, max_b

For a target of 0.9 recall at $p = 0.55$, the search finds $r = 8$ rows and needs a band count above 250, reaching the cap; the achievable hit probability at the cap is about 0.88, so the target sits just out of reach. The product $r \cdot b$ is the number of independent hash bits per record, and it is the quantity that actually costs memory and build time: 2000 bits per record, 250 bytes, against 3072 bytes for the float vector itself at 768 dimensions. A recall target that looks modest can therefore demand more memory for keys than for the data they index.

The steepness also means that the effective recall is extremely sensitive to where the true similarity distribution sits relative to $p^\ast$. If most relevant pairs score well above the threshold, measured recall will exceed the calculation, since the formula only guarantees the behavior at exactly $p^\ast$. If relevant pairs are spread across the threshold, measured recall will land close to the prediction, and the variance across queries will be large: some queries find nearly everything, others find nothing.

Implementation details that decide accuracy

Three details separate a working implementation from a slow one.

The random projection matrix should be generated once and stored, or regenerated from a fixed seed. Drawing $r$ vectors of $d$ components per record at query time is $r \cdot d$ random numbers per query, which is not negligible; a fixed matrix makes the query projection a matrix-vector product and lets the same code vectorize over batches. Dense Gaussian projections cost $r \cdot d$ multiply-accumulates. Sparse projections, where each row has a small constant number of nonzero entries, reduce this to $r \cdot c$ and are the standard choice when $d$ is large, at the cost of slightly worse randomness and therefore slightly different collision behavior.

Sign bits should be packed. $r = 32$ fits exactly in a machine word, and $r = 64$ in a 64-bit word, which makes the hash key an integer comparison instead of a byte-wise comparison of keys. Padding $r$ up to a multiple of the word size costs a few wasted bits and saves a memory comparison in every table lookup.

Banding must use independent bits across bands. Reusing the same rows in different bands correlates the failures, so a pair that misses in one band misses in the correlated ones too, and the union bound $1 - (1 - p^r)^b$ no longer applies. Generating $r \cdot b$ independent bits and slicing them into $b$ chunks of $r$ is the correct construction.

For a collection whose total bits per record would run to hundreds, a two-level scheme is common: a coarse LSH pass over a short key retrieves a candidate set, and exact or quantized rescoring refines it. The candidate set is where recall is lost or preserved, which is why the over-fetch and rerank structure described in Over-Fetch and Exact Reranking in Two-Stage Vector Retrieval applies to LSH as much as to any other index.

The remaining limitation is structural. LSH guarantees are probabilistic per pair and give no bound on the number of candidates examined, so latency has a heavy tail driven by bucket imbalance. It also requires the similarity function to admit a known collision family; cosine and Jaccard do, and Euclidean distance admits one through a quantization of the projection, but an arbitrary learned distance does not. Indexes that adapt their partitioning to the data, examined in Coarse Quantization with Inverted Files and the nprobe Setting, trade the clean probability model for better behavior on skewed collections.