SimHash (reviewed on the previous page) stores the sign bits sign(si·x) for m random Gaussian vectors s1, …, sm (the rows of a matrix S). Comparing the bits of two vectors estimates the angle between them: they disagree on a bit with probability θ/π. That needs both vectors quantized.
In a KV cache the keys x are stored, but each query y arrives later at full precision. The quantized Johnson–Lindenstrauss (QJL) trick stores the same SimHash bits for x, plus the single number ‖x‖, and multiplies them by the unquantized projections of y:
⟨y, x⟩ ≈ ‖x‖ · √(π/2) · (1/m) Σi (si·y) sign(si·x) = ⟨y, x̃⟩, where x̃ = ‖x‖ √(π/2) (1/m) ST sign(Sx).
This is unbiased. Write y = αx̂ + y⊥ with x̂ = x/‖x‖. The Gaussian s·y⊥ is independent of s·x̂ and has mean zero, so it averages away; what is left is α E|s·x̂| = α√(2/π). Hence E[(s·y) sign(s·x)] = √(2/π) ⟨y, x̂⟩, and the √(π/2) cancels it. Equivalently, x̃ is an unbiased estimate of x itself.
Drag the tips of x (the stored key) and y (the query). Each random si defines a SimHash hyperplane (a line here, perpendicular to si); the bit says which side x is on. The reconstruction x̃ adds up ±si, pointing each one toward x's side of its hyperplane.