# Polysemous codes

arXiv: https://arxiv.org/abs/1609.01882 · HTML: https://mlsanity.com/paper/1609.01882/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2016.

## Built on by (most cited first, 8 of 8)

- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Residual Quantization with Implicit Neural Codebooks](https://mlsanity.com/paper/2401.14732/) (2024)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [PDX: A Data Layout for Vector Similarity Search](https://mlsanity.com/paper/2503.04422/) (2025)
- [Large-Scale Visual Search with Binary Distributed Graph at Alibaba](https://mlsanity.com/paper/2102.04656/) (2021)
- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [Givens Coordinate Descent Methods for Rotation Matrix Learning in Trainable Embedding Indexes](https://mlsanity.com/paper/2203.05082/) (2022)
- [Adaptive Prefiltering for High-Dimensional Similarity Search: A Frequency-Aware Approach](https://mlsanity.com/paper/2602.22214/) (2025)

## Abstract (arXiv)

This paper considers the problem of approximate nearest neighbor search in the compressed domain. We introduce polysemous codes, which offer both the distance estimation quality of product quantization and the efficient comparison of binary codes with Hamming distance. Their design is inspired by algorithms introduced in the 90's to construct channel-optimized vector quantizers. At search time, this dual interpretation accelerates the search. Most of the indexed vectors are filtered out with Hamming distance, letting only a fraction of the vectors to be ranked with an asymmetric distance estimator. The method is complementary with a coarse partitioning of the feature space such as the inverted multi-index. This is shown by our experiments performed on several public benchmarks such as the BIGANN dataset comprising one billion vectors, for which we report state-of-the-art results for query times below 0.3,millisecond per core. Last but not least, our approach allows the approximate computation of the k-NN graph associated with the Yahoo Flickr Creative Commons 100M, described by CNN image descriptors, in less than 8 hours on a single machine.