# Learning Discrete Representations via Constrained Clustering for Effective and Efficient Dense Retrieval

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2021.

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

- [ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction](https://mlsanity.com/paper/2112.01488/) (2021)
- [Learning Vector-Quantized Item Representation for Transferable Sequential Recommenders](https://mlsanity.com/paper/2210.12316/) (2022)
- [A Survey on Knowledge-Oriented Retrieval-Augmented Generation](https://mlsanity.com/paper/2503.10677/) (2025)
- [Fine-Grained Distillation for Long Document Retrieval](https://mlsanity.com/paper/2212.10423/) (2022)
- [UnifieR: A Unified Retriever for Large-Scale Retrieval](https://mlsanity.com/paper/2205.11194/) (2022)
- [Distill-VQ: Learning Retrieval Oriented Vector Quantization By Distilling Knowledge from Dense Embeddings](https://mlsanity.com/paper/2204.00185/) (2022)
- [Constructing Tree-based Index for Efficient and Effective Dense Retrieval](https://mlsanity.com/paper/2304.11943/) (2023)
- [Taxonomy-guided Semantic Indexing for Academic Paper Search](https://mlsanity.com/paper/2410.19218/) (2024)
- [Boosted Dense Retriever](https://mlsanity.com/paper/2112.07771/) (2021)
- [Hybrid Contrastive Quantization for Efficient Cross-View Video Retrieval](https://mlsanity.com/paper/2202.03384/) (2022)
- [ESPN: Memory-Efficient Multi-Vector Information Retrieval](https://mlsanity.com/paper/2312.05417/) (2023)
- [Trinity: Syncretizing Multi-/Long-tail/Long-term Interests All in One](https://mlsanity.com/paper/2402.02842/) (2024)
- [Self-Calibrated Listwise Reranking with Large Language Models](https://mlsanity.com/paper/2411.04602/) (2024)
- [Injecting Domain Adaptation with Learning-to-hash for Effective and Efficient Zero-shot Dense Retrieval](https://mlsanity.com/paper/2205.11498/) (2022)
- [Disentangled Modeling of Domain and Relevance for Adaptable Dense Retrieval](https://mlsanity.com/paper/2208.05753/) (2022)
- [REIS: A High-Performance and Energy-Efficient Retrieval System with In-Storage Processing](https://mlsanity.com/paper/2506.16444/) (2025)
- [HAKES: Scalable Vector Database for Embedding Search Service](https://mlsanity.com/paper/2505.12524/) (2025)
- [Learned Accelerator Framework for Angular-Distance-Based High-Dimensional DBSCAN](https://mlsanity.com/paper/2302.03136/) (2023)
- [Foundations of GenIR](https://mlsanity.com/paper/2501.02842/) (2025)
- [Matryoshka Hash Representations for Model-Aware Compact Semantic Retrieval](https://mlsanity.com/paper/2609.07276/) (2026)
- [A Bibliographic View on Constrained Clustering](https://mlsanity.com/paper/2209.11125/) (2022)
- [Enhanced vectors for top-k document retrieval in Question Answering](https://mlsanity.com/paper/2210.10584/) (2022)
- [Online Distillation for Pseudo-Relevance Feedback](https://mlsanity.com/paper/2306.09657/) (2023)
- [FecTek: Enhancing Term Weight in Lexicon-Based Retrieval with Feature Context and Term-level Knowledge](https://mlsanity.com/paper/2404.12152/) (2024)
- [A Simple and Effective Framework for Symmetric Consistent Indexing in Large-Scale Dense Retrieval](https://mlsanity.com/paper/2512.13074/) (2025)
- [NeuRoute: Logit-Guided Neural Routing for Billion-Scale Vector Search with Sub-Hour Index Construction](https://mlsanity.com/paper/2608.15438/) (2026)
- [Where Post-Training Quantization Breaks Text Embedders: A Measured Map Across Four Embedder Families](https://mlsanity.com/paper/2609.16391/) (2026)

## Abstract (arXiv)

Dense Retrieval (DR) has achieved state-of-the-art first-stage ranking effectiveness. However, the efficiency of most existing DR models is limited by the large memory cost of storing dense vectors and the time-consuming nearest neighbor search (NNS) in vector space. Therefore, we present RepCONC, a novel retrieval model that learns discrete Representations via CONstrained Clustering. RepCONC jointly trains dual-encoders and the Product Quantization (PQ) method to learn discrete document representations and enables fast approximate NNS with compact indexes. It models quantization as a constrained clustering process, which requires the document embeddings to be uniformly clustered around the quantization centroids and supports end-to-end optimization of the quantization method and dual-encoders. We theoretically demonstrate the importance of the uniform clustering constraint in RepCONC and derive an efficient approximate solution for constrained clustering by reducing it to an instance of the optimal transport problem. Besides constrained clustering, RepCONC further adopts a vector-based inverted file system (IVF) to support highly efficient vector search on CPUs. Extensive experiments on two popular ad-hoc retrieval benchmarks show that RepCONC achieves better ranking effectiveness than competitive vector quantization baselines under different compression ratio settings. It also substantially outperforms a wide range of existing retrieval models in terms of retrieval effectiveness, memory efficiency, and time efficiency.