Lune

ICML2026Top-tier venue

Beyond Hamming: Query-Aware Decoding of Binary Cosine Sketches

DaeHun Nyang

Abstract

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 ∼\sim15--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 ∼\sim30 percentage points at fixed budgets and reducing candidates by up to ∼\sim45--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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on3

  1. A Simple Framework for Contrastive Learning of Visual RepresentationsTing Chen, Simon Kornblith, Mohammad Norouzi, Geoffrey E. HintonICML 2020 · 24,064 citations
  2. Accelerating Large-Scale Inference with Anisotropic Vector QuantizationRuiqi Guo, Philip Sun, Erik Lindgren, Quan Geng et al.ICML 2020 · 539 citations
  3. Dense Passage Retrieval for Open-Domain Question AnsweringVladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis et al.EMNLP 2020 · 142 citations

Related papers

  1. Probabilistic Kernel Function for Fast Angle TestingKejing Lu, Chuan Xiao, Yoshiharu IshikawaICLR 2026 · 2 citations
  2. Distilling Large Embeddings via Hyperspherical Householder QuantizationYihang Wang, Bin Wu, Yueyang Su, Tianfu Zhang et al.ACL 2026
  3. SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor SearchYutong Gou, Jianyang Gao, Yuexuan Xu, Cheng LongSIGMOD 2025 · 21 citations
  4. Recall-Aware Early Termination in Approximate Nearest Neighbor SearchShuang Hao, Xinxin Li, Wei ZhangKDD 2026
  5. Angular Distance-Guided Neighbor Selection for Graph-Based Approximate Nearest Neighbor SearchSungjun Jung, Yongsang Park, Haeun Lee, Young H. Oh et al.WWW 2025 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines