# Rate-Distortion Limits for Multimodal Retrieval: Theory, Optimal Codes, and Finite-Sample Guarantees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 42 references that are in the map.
- First posted on arXiv 14 Sep 2025.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Scaling Up Visual and Vision-Language Representation Learning With Noisy Text Supervision](https://mlsanity.com/paper/2102.05918/) (2021)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Deep Visual-Semantic Alignments for Generating Image Descriptions](https://mlsanity.com/paper/1412.2306/) (2014)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Debiased Contrastive Learning](https://mlsanity.com/paper/2007.00224/) (2020)
- [Emergence of Invariance and Disentanglement in Deep Representations](https://mlsanity.com/paper/1706.01350/) (2017)
- [Towards the Generalization of Contrastive Self-Supervised Learning](https://mlsanity.com/paper/2111.00743/) (2021)
- [What to align in multimodal contrastive learning?](https://mlsanity.com/paper/2409.07402/) (2024)
- [On the Generalization of Multi-modal Contrastive Learning](https://mlsanity.com/paper/2306.04272/) (2023)
- [Explaining and Mitigating the Modality Gap in Contrastive Multimodal Learning](https://mlsanity.com/paper/2412.07909/) (2024)
- [Generalization Analysis for Contrastive Representation Learning](https://mlsanity.com/paper/2302.12383/) (2023)
- [Turbo your multi-modal classification with contrastive learning](https://mlsanity.com/paper/2409.09282/) (2024)

## Abstract (arXiv)

We establish the first information-theoretic limits for multimodal retrieval. Casting ranking as lossy source coding, we derive a single-letter rate-distortion function R(D) for reciprocal-rank distortion and prove a converse bound that splits into a modality-balanced term plus a skew penalty kappa,Delta H capturing entropy imbalance and cross-modal redundancy. We then construct an explicit entropy-weighted stochastic quantizer with an adaptive, per-modality temperature decoder; a Blahut-Arimoto argument shows this scheme achieves distortion within O(n-1) of R(D) using n training triples. A VC-type analysis yields the first finite-sample excess-risk bound whose complexity scales sub-linearly in both the number of modalities and the entropy gap. Experiments on controlled Gaussian mixtures and Flickr30k confirm that our adaptive codes sit within two percentage points of the theoretical frontier, while fixed-temperature and naive CLIP baselines lag significantly. Taken together, our results give a principled answer to "how many bits per query are necessary" for high-quality multimodal retrieval and provide design guidance for entropy-aware contrastive objectives, continual-learning retrievers, and retrieval-augmented generators.