Matryoshka Hash Representations for Model-Aware Compact Semantic Retrieval

Summary

Matryoshka Hash Representations (MHR) compress each document to a short binary code for semantic search and retrieval-augmented generation (RAG). Dense retrieval stores one learned vector per document, and that storage dominates index cost at scale. MHR learns codes of 8, 16, and 32 bytes that are nested, so one stored code serves every length and a system can change its storage budget without re-encoding the corpus. At 32 bytes, a 96-fold reduction from a 3,072-byte float vector, MHR reaches 0.556 NDCG@10 on seven BEIR datasets against 0.524 for the best same-budget baseline.

Key numbers

• 0.556 vs 0.524NDCG@10 at 32 bytes per document for MHR and the best same-budget baseline, averaged over seven BEIR datasets
• 96×Payload reduction from a 3,072-byte float vector to a 32-byte code, which retains 87.3% of the float model's NDCG@10
• 99.6–100%Share of unpruned NDCG@10 that MHR preserves in LEANN graph search at 25% retention, with 66.6–68.6% fewer exact distance evaluations

Method

Dense retrieval embeds queries and documents as vectors and answers a query with its nearest neighbors ^[1]. Quantization replaces each vector with a short code. Standard quantizers such as product quantization (PQ), which splits a vector into parts and stores each part as an index into a small codebook, choose the code that reconstructs the original vector best. Reconstruction is a proxy for ranking, so MHR trains the code directly on the retriever's ranking signal, which makes it a model-aware code.

Training every prefix of a code under one objective forces the early bits to compromise across budgets. MHR separates the work into two stages. It first trains a full-width binary code on MS MARCO ^[2] with LoRA, compressing a 768-dimensional float vector 96-fold. It then freezes that model and trains zero-initialized residual code adaptors that organize the code into 8-, 16-, and 32-byte prefixes, each directly searchable. Documents are stored at one bit per coordinate, and queries keep continuous logits, as in PQ, for more expressive scoring. Search runs through FAISS FastScan ^[3], a SIMD (single instruction, multiple data) routine for scoring short codes.

Evaluation

The model is trained on MS MARCO only and tested without further training on seven datasets from BEIR ^[4], a benchmark for zero-shot retrieval. Quality is measured by NDCG@10, the ranking quality of the top 10 results with graded relevance, and Recall@100, the share of relevant documents found in the top 100. At 32 bytes MHR reaches 0.5561 NDCG@10 and 0.6535 Recall@100, against 0.5239 and 0.6426 for JPQ ^[5], the best same-budget baseline, which trains its codes jointly with the query encoder. At 16 bytes MHR scores 0.502 against 0.404 for JPQ, and at 8 bytes 0.376 against 0.217. The 16-byte comparison holds on all seven datasets in both metrics. All MHR points come from one prefix-closed code, while the baselines at 8 and 16 bytes truncate a 32-byte model or train separate codes.

The same code helps two common pipelines. In coarse-to-fine reranking, an 8-byte filter followed by full-precision scoring of a short candidate list recovers near-float quality. In LEANN ^[6], a low-storage graph index that recomputes embeddings only for selected nodes, replacing the 8-byte PQ code with an 8-byte MHR prefix at 25% retention preserves 99.6 to 100% of unpruned NDCG@10 and 97.4 to 99.8% of Recall@100. Exact distance evaluations fall by 66.6 to 68.6%. On NQ, MHR reaches 0.529 NDCG@10 against 0.444 for PQ fitted to the target corpus.

Limitations

MHR remains 12.7% below the float BGE model in macro NDCG@10 at 32 bytes. At 32 bytes it is the best method on five of the seven datasets in NDCG, so the margin is not uniform. Longer codes can buy quality at higher storage cost, and the paper leaves that trade-off to future work.

The study measures in-memory CPU search. FAISS-style GPU kernels and disk-resident graph indexes such as DiskANN are not tested. Training uses one source corpus, and all other results are zero-shot transfers across the seven BEIR datasets.

Citation

@article{hua2026matryoshka,
      title={Matryoshka Hash Representations for Model-Aware Compact Semantic Retrieval}, 
      author={Peichun Hua and Yunming Xiao},
      journal={CoRR},
      volume={abs/2609.07276},
      year={2026},
      url={https://arxiv.org/abs/2609.07276},
      doi={10.48550/arXiv.2609.07276},
      eprinttype={arXiv},
      eprint={2609.07276},
      primaryClass={cs.IR}
}

References

1. Vladimir Karpukhin et al. Dense Passage Retrieval for Open-Domain Question Answering. EMNLP, 2020. arxiv.org/abs/2004.04906
2. Payal Bajaj et al. MS MARCO: A Human Generated MAchine Reading COmprehension Dataset. arXiv, 2016. arxiv.org/abs/1611.09268
3. Matthijs Douze et al. The Faiss library. arXiv, 2024. arxiv.org/abs/2401.08281
4. Nandan Thakur et al. BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models. NeurIPS Datasets and Benchmarks, 2021. arxiv.org/abs/2104.08663
5. Jingtao Zhan et al. Jointly Optimizing Query Encoder and Product Quantization to Improve Retrieval Performance. CIKM, 2021. arxiv.org/abs/2108.00644
6. Yichuan Wang et al. LEANN: A Low-Storage Vector Index. arXiv, 2025. arxiv.org/abs/2506.08276