mlsanityData to 14 Oct 2026

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

arXiv 2606.11780 ↗First posted 10 Jun 2026cs.IR cs.AI cs.ITcited by 4

Not on the map. Why?

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.

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

15 of 30 references.

References · 15

  1. 2017Billion-scale similarity search with GPUscited by 2,497
  2. 2022GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformerscited by 1,919
  3. 2017Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inferencecited by 1,593
  4. 2020MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformerscited by 1,463
  5. 2022LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scalecited by 906
  6. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 861
  7. 2022One Embedder, Any Task: Instruction-Finetuned Text Embeddingscited by 333
  8. 2023Improving Text Embeddings with Large Language Modelscited by 303
  9. 2022FP8 Formats for Deep Learningcited by 196
  10. 2025On the Theoretical Limitations of Embedding-Based Retrievalcited by 104
  11. 2025ReasonIR: Training Retrievers for Reasoning Taskscited by 77
  12. 2023LLM-FP4: 4-Bit Floating-Point Quantized Transformerscited by 69
3 more
  1. 2021Efficient Passage Retrieval with Hashing for Open-domain Question Answeringcited by 53
  2. 2020The Curse of Dense Low-Dimensional Information Retrieval for Large Index Sizescited by 48
  3. 2018On the Dimensionality of Word Embeddingcited by 46

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Non-negative Elastic Net Decoding for Information Retrievalcited by 1
  2. 2026There is No Theoretical Curse of Multilinguality For Embedding Space Structurecited by 0
  3. 2026Where Post-Training Quantization Breaks Text Embedders: A Measured Map Across Four Embedder Familiescited by 0
  4. 2026Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026The Undetected Damage of Quantization on Retrieval and How to Fix It
  2. 20254bit-Quantization in Vector-Embedding for RAG
  3. 2025Dimension vs. Precision: A Comparative Analysis of Autoencoders and Quantization for Efficient Vector Retrieval on BEIR SciFact
  4. 2024Quantization of Large Language Models with an Overdetermined Basis
  5. 2026Top-K Is Not a Budget for Hybrid Retrieval ↗
  6. 2026ColBERTSaR: Sparsified ColBERT Index via Product Quantization
  7. 2026Matryoshka Hash Representations for Model-Aware Compact Semantic Retrieval
  8. 2026Quantize by Drift: Label-Free Mixed-Precision Post-Training Quantization for Text Embedders