Turning a gentle slope into a cliff

1AND: make buckets selective

Concatenate $k$ independent bits into one bucket key. Two points share a bucket only if they agree on all $k$ :

\Pr[\text{same bucket}] \;=\; p^{\,k}

Strangers are filtered out exponentially fast: $\kres{p_2}^k$ . With $p_2 = 0.52$ and $k = 12$ , a random point lands in the query’s bucket once in about 2,492.

Unfortunately neighbours are filtered too: $\kdec{p_1}^{k}$ with $p_1 = 0.61$ and $k = 12$ is about 0.003. One table almost never contains the neighbour.

2OR: give neighbours more chances

Build $L$ independent tables, each with its own $k$ bits. A point is a candidate if it shares a bucket with the query in any table:

\Pr[\text{candidate}] \;=\; 1 - \big(1 - p^{\,k}\big)^{L}

This is the AND-OR construction, or amplification. As a function of similarity it is an S-curve: near zero for dissimilar points, near one for similar points, with a transition that sharpens as $k$ and $L$ grow together.

Fig 5.2.1The LSH S-curve

Set k and L The faint dotted line is a single bit. The dashed markers are a true 10th neighbour and a random pair on Marginalia’s data. Where a marker meets the curve is, roughly, your recall (green) and the share of the database you will have to scan (red). When your settings match a measured configuration, the measurement appears below.

3How to choose k and L

Let $N$ be the size of the database. The classical recipe (Indyk and Motwani):

Choose $k$ so that strangers are rare. Set $p_2^{\,k} = 1/N$ , which gives about one stranger per table: $k = \dfrac{\ln N}{\ln(1/p_2)}$ .
Choose $L$ so that a neighbour is found. A neighbour is in a given table with probability $p_1^{\,k}$ , so you need about $L = 1/p_1^{\,k}$ tables.
Substitute. $p_1^{\,k} = N^{-\rho}$ where

\kcode{\rho} \;=\; \frac{\ln(1/\kdec{p_1})}{\ln(1/\kres{p_2})} \qquad\Longrightarrow\qquad L \approx N^{\rho}, \qquad \text{query work} \approx N^{\rho}, \qquad \text{memory} \approx N^{1+\rho}

The exponent ρ is always below 1 because $p_1 > p_2$ . That is the sense in which LSH is provably sublinear.

4The memory bill

Every table stores a pointer for every vector. $L$ tables cost $L \times N \times 4$ bytes before you store a single vector: at $L = 64$ that is 256 bytes per vector of index overhead, as much as an HNSW graph and far more than an IVF index, which stores each vector once.