Beyond Hamming: Query-Aware Decoding of Binary Cosine Sketches

Cosine similarity estimation is a core primitive in coarse-to-fine retrieval pipelines, where early-stage candidate selection relies on approximate similarity estimates whose errors are amplified downstream. Widely used sign-based sketches arising from extreme quantization of random projections exhibit a structural variance peak near $\theta$ $\approx$ 90$^\circ$, the near-background region where candidate selection is most difficult. We propose QA-Cos, a query-aware decoder-side estimator that departs from the Hamming-agreement paradigm, treating sign bits as probabilistic observations rather than deterministic votes. Across simulations and BEIR benchmarks, QA-Cos reduces estimation error by up to $\sim$15--20\% in the near-orthogonal region and translates these gains into improved candidate selection in two-stage ANN pipelines, improving Hit@K by up to $\sim$30 percentage points at fixed budgets and reducing candidates by up to $\sim$45--50\% at fixed recall. In a native hnswlib scorer-replacement experiment, the same decoder improves the quality of the final HNSW frontier, and in a focused storage-aware setting a practical gated variant reduces end-to-end wall-clock latency at matched recall.

Many search and recommendation systems first make a quick guess about which items are worth checking, then spend more time scoring only those candidates. To keep this first step fast, systems often store each database item as a tiny yes/no fingerprint rather than the full vector. This is efficient, but the usual way of comparing fingerprints is least reliable for items that are neither clearly similar nor clearly different from the query. Our work asks whether we can use a fact available at search time: the query itself is still kept in full detail. We propose QA-Cos, a decoding method that keeps stored fingerprints unchanged but reads their bits more carefully using the query. Instead of treating every bit as an equally reliable vote, QA-Cos gives more weight to bits that are more informative for the current query. On standard retrieval benchmarks, this improves candidate selection: difficult queries recover more relevant items under the same budget, and the same recall can often be reached with fewer candidates. This can make retrieval faster or cheaper without retraining the model or rebuilding the database index. Overall, the work shows that reading compact representations better can matter as much as storing them differently.