# What Limits Does Quantization Place on Dense Top-k Retrieval? A Theoretical Study

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 10 Jun 2026.

## Builds on (most cited first, 15 of 15)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference](https://mlsanity.com/paper/1712.05877/) (2017)
- [MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers](https://mlsanity.com/paper/2002.10957/) (2020)
- [LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale](https://mlsanity.com/paper/2208.07339/) (2022)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [One Embedder, Any Task: Instruction-Finetuned Text Embeddings](https://mlsanity.com/paper/2212.09741/) (2022)
- [Improving Text Embeddings with Large Language Models](https://mlsanity.com/paper/2401.00368/) (2023)
- [FP8 Formats for Deep Learning](https://mlsanity.com/paper/2209.05433/) (2022)
- [On the Theoretical Limitations of Embedding-Based Retrieval](https://mlsanity.com/paper/2508.21038/) (2025)
- [ReasonIR: Training Retrievers for Reasoning Tasks](https://mlsanity.com/paper/2504.20595/) (2025)
- [LLM-FP4: 4-Bit Floating-Point Quantized Transformers](https://mlsanity.com/paper/2310.16836/) (2023)
- [Efficient Passage Retrieval with Hashing for Open-domain Question Answering](https://mlsanity.com/paper/2106.00882/) (2021)
- [The Curse of Dense Low-Dimensional Information Retrieval for Large Index Sizes](https://mlsanity.com/paper/2012.14210/) (2020)
- [On the Dimensionality of Word Embedding](https://mlsanity.com/paper/1812.04224/) (2018)

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

- [Non-negative Elastic Net Decoding for Information Retrieval](https://mlsanity.com/paper/2606.17910/) (2026)
- [There is No Theoretical Curse of Multilinguality For Embedding Space Structure](https://mlsanity.com/paper/2608.17088/) (2026)
- [Where Post-Training Quantization Breaks Text Embedders: A Measured Map Across Four Embedder Families](https://mlsanity.com/paper/2609.16391/) (2026)
- [Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy](https://mlsanity.com/paper/2610.02749/) (2026)

## Abstract (arXiv)

We establish conditions for embedding a corpus of N documents as d-dimensional vectors such that every k-subset S subseteq [N] is realizable as a result of top-k retrieval by some query vector. Recent work shows that d = O(k) suffices for such embeddings to exist in ℝd, independently of N. We theoretically prove that this corpus-independent bound is specific to infinite precision. With B bits per coordinate, perfect top-k retrieval requires Bd = Omega(k ln N); thus, at any fixed precision, the dimension must grow at least logarithmically with N. Specializing to a ℓ2-normalized B-bit uniform scalar quantization model, we also identify a threshold on the precision B* = O(ln ln N) below which no dimension suffices, together with two further regimes that bound the feasible (B, d) pairs. Our result implies that in practical vector databases and dense retrieval systems where quantization is standard, the embedding dimension and possibly the precision must grow with the corpus size.