Binary Embeddings for Fast Search

Binary embeddings are the extreme end of quantization: one bit per dimension. A 768-d vector that took 3 KB at float32 shrinks to 96 bytes, and similarity becomes a bitwise operation a CPU runs in nanoseconds. The catch is recall — which is why binary search is almost never used alone.

Interactive Binary Quantization

The explorer is real: it sign-binarizes genuine GloVe vectors, ranks by Hamming distance, and measures recall@10 live — then re-ranks the candidates with float32 to recover what binary loses.

Sign binarization and Hamming distance

The simplest binarizer keeps the sign of each dimension — positive becomes 1, negative becomes 0:

Distance between two codes is then the Hamming distance — the number of bits that differ, computed as a XOR followed by a population count (a single instruction on modern CPUs):

def binarize(X):
    return (X >= 0).astype(np.uint8)        # 1 bit per dimension

def hamming(a, b):
    return np.unpackbits(a ^ b).sum()       # XOR + popcount

A d-dimensional code is d bits — d/8 bytes — so binary is exactly 32× smaller than float32, and a Hamming comparison is far cheaper than a dot product.

The price: recall

Discarding magnitude is lossy. On the GloVe vectors in the explorer, sign-binarized Hamming search recovers only ~60% of the true top-10 neighbors — fine for a coarse shortlist, not for final ranking.

Retrieve wide, re-rank exact

The standard fix is a two-stage pipeline: use binary to fetch a generous candidate set fast, then re-score just those candidates with full-precision vectors. Because the second stage touches only N documents, it is cheap — and it recovers almost all the lost recall:

def search(query, db_binary, db_float, n=50, k=10):
    # Stage 1 — Hamming over the binary index (fast, wide)
    qb = binarize(query)
    cand = np.argsort([hamming(qb, b) for b in db_binary])[:n]
    # Stage 2 — float32 cosine over the N candidates (exact, narrow)
    scored = sorted(cand, key=lambda i: -cosine(query, db_float[i]))
    return scored[:k]

Binary vs float32

Beyond sign binarization

Sign binarization wastes bits — it ignores that some directions matter more than others. Learned binarization improves the codes before taking the sign:

• ITQ (Iterative Quantization) rotates the space to minimize the gap between the real vectors and their nearest binary corner, so each sign carries more information.
• Random hyperplane LSH projects onto random directions before binarizing, with theoretical guarantees that Hamming distance approximates angular distance — covered in LSH search.

Either way the deployment pattern is the same: binary to shortlist, full precision to rank.

Best practices

1. Never rank on binary alone. Always re-rank the top candidates with float32 or int8.
2. Tune N against recall, not feel. Push N up until reranked recall plateaus, then stop.
3. Pack bits, use popcount. Store codes as uint64 words so Hamming is a handful of hardware instructions.
4. Consider ITQ when the recall budget is tight — the rotation is a one-time training cost.

References

• Charikar "Similarity Estimation Techniques from Rounding Algorithms" (SimHash)
• Gong & Lazebnik "Iterative Quantization: A Procrustean Approach to Learning Binary Codes"
• Shakir et al. "Binary and Scalar Embedding Quantization for Significantly Faster & Cheaper Retrieval"

Related concepts