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

Thomas Y. Chen · 2025

Read Rate–Distortion Limits for Multimodal Retrieval: Theory, Optimal Codes, and Finite-Sample Guarantees by Thomas Y. Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-11054.txt.

Introduction

Thomas Y. Chen is the sole author of this 2025 information theory paper. It asks a basic question about search systems that mix text and images. How much information must each query carry for retrieval to stay accurate?

Chen treats ranking as a form of lossy compression. He derives a rate-distortion limit for a ranking-based error measure. He then proves that no system can beat that limit. The bound splits into two parts. One part is balanced across data types. The other is a penalty for lopsided information. He also builds a coding scheme that nearly reaches the limit. Tests on image-caption data keep it close to the best possible result. Common baselines fall well behind.

Catalog record

CREATORThomas Y. Chen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-11054

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Rate–Distortion Limits for Multimodal Retrieval: Theory, Optimal Codes, and Finite-Sample Guarantees Thomas Y. Chen Abstract 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 ) R(D) for reciprocal-rank distortion and prove a converse bound that splits into a modality–balanced term plus a skew penalty κ ​ Δ ​ H \kappa\,\Delta H capturing entropy imbalance and cross-modal redundancy. We then construct an explicit entropy-weighted stochastic quantiser with an adaptive, per-modality temperature decoder; a Blahut–Arimoto argument shows this scheme achieves distortion within O ⁡ ( n − 1 ) O(n^{-1}) of R ⁡ ( D ) R(D) using n 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 naïve 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. 1 Introduction Contrastive vision–language pre-training has proved remarkably effective for aligning images and text in a common embedding space, enabling zero-shot recognition and cross-modal retrieval at unprecedented scale [ 30 , 8 ] . Yet today’s systems still treat retrieval largely as an empirical engineering problem: pick an embedding dimensionality, optimise a temperature-scaled InfoNCE loss, and hope that the resulting codes suffice for ranking. What is missing is a principled answer to a basic question: given a fixed number of bits per query, what is the minimum ranking error we can ever hope to achieve when both queries and documents are themselves multimodal objects? Classical rate–distortion theory [ 5 , 12 ] gives tight limits for lossy compression under additive distortions such as mean-squared error. Unfortunately, ranking error is inherently order-dependent and non-additive ; it depends on the entire permutation a retrieval engine produces, not on a per-sample distance. Consequently, the celebrated single-letter formulas of Shannon and Berger do not directly apply. Recent information-bottleneck analyses of representation learning [ 1 ] illuminate why noise-injected encoders can trade accuracy for compression, but they do not quantify the specific price paid in retrieval metrics such as mean reciprocal rank. Early visual-semantic embedding work [ 16 ] focused on bimodal ( image, text ) pairs, leaving open how additional modalities and their entropy imbalance affect fundamental limits. This paper closes that gap. We recast multimodal retrieval as a two-way lossy source–channel coding problem and derive, for the first time, a single-letter rate–distortion function R(D) that lower-bounds the achievable expected ranking distortion at embedding rate R . The analysis reveals a new modality-skew coefficient that quantifies how entropy imbalance and cross-modal redundancy inflate the rate required for a given distortion. A converse theorem shows that standard temperature-scaled contrastive objectives hit the bound only when this coefficient equals one; otherwise they are information-theoretically sub-optimal. An achievability construction based on entropy-weighted stochastic quantisation, together with an adaptive temperature schedule, attains distortion within O(n^{-1/2}) of the bound in finite samples, establishing near-optimality in both asymptotic and practical regimes. Beyond filling a theoretical vacuum, our results have immediate design implications. They provide guidance on how many bits per query are necessary before engineering effort can meaningfully improve retrieval quality, and they justify entropy-adaptive temperature tuning rules now gaining empirical traction. Section 2 formalises notation and links our setting to classical coding theory; Section 3 states the rate–distortion optimisation; Sections 4 – 5 develop the converse and achievability proofs; Section 6 extends the theory to finite data; and Section 7 illustrates the constants on synthetic mixtures and Flickr30k. We conclude with open directions such as continual multimodal retrieval and graph-aware corpora. 2 Background and Notation Multimodal retrieval model. Let \mathcal{X}=\mathcal{X}_{1}\times\!\dots\times\!\mathcal{X}_{M} and \mathcal{Y}=\mathcal{Y}_{1}\times\!\dots\times\!\mathcal{Y}_{M} denote query- and document-spaces whose factors correspond to M distinct modalities (e.g. image, text, audio). A corpus \mathcal{D}=\{Y^{(1)},\dots,Y^{(N)}\}\subset\mathcal{Y} is fixed and public. A user issues a multimodal query X\!\sim\!P_{X} ; relevance is encoded by a latent joint law P_{XY} on \mathcal{X}\!\times\!\mathcal{Y} . Following Shannon’s source-coding paradigm [ 33 ] , an encoder f:\mathcal{X}\!\to\!\mathcal{C} compresses X into a codeword C=f(X) selected from a finite codebook \mathcal{C} of size |\mathcal{C}|=2^{R} (thereby using R bits per query). A decoder g:\mathcal{C}\times\mathcal{D}\!\to\!\mathfrak{S}_{N} maps C and the corpus to a permutation g(C) over indices \{1,\dots,N\} , where \mathfrak{S}_{N} is the symmetric group. Ranking distortion. To evaluate quality we adopt a position-sensitive distortion d\!\bigl((X,Y),\pi\bigr)\;=\;1-\mathrm{RR}\bigl(\pi;Y\bigr), (1) where \pi\in\mathfrak{S}_{N} and \mathrm{RR}(\pi;Y)=1/\mathrm{rank}_{\pi}(Y) is reciprocal rank [ 10 ] . The expectation \mathbb{E}[d] equals 1\!-\!\mathrm{MRR} , so minimising average distortion is equivalent to maximising mean-reciprocal-rank, a standard retrieval metric [ 22 ] . Crucially, the mapping \pi\mapsto d is non-additive : d depends on the entire permutation, not a sum of per-item penalties. This violates the separability assumptions underlying classical rate–distortion derivations [ 5 , 12 ] , motivating our bespoke analysis. Rate–distortion objective. For a target distortion level D\in[0,1] , the fundamental limit is R(D)\;=\;\min_{\,f,g:\,\mathbb{E}[d]\leq D}\;I(X;C), (2) where I(\cdot;\cdot) is mutual information under P_{X} and the encoder distribution induced by f . Because codewords are deterministic functions of X , I(X;C)=H(C) ; nevertheless we keep the information-theoretic form to facilitate the converse proof in Sec. 4 . Existence of minimisers follows from lower semi-continuity of I and compactness of the probability simplex (support-lemma argument [ 13 , Ch. 3] ). Section 3 elaborates ( 2 ) and derives its properties. Entropy imbalance and redundancy. Write H_{m}=H(X_{m}) for the marginal entropy of the m^{\text{th}} modality and I_{\text{cross}}=\sum_{m\neq m^{\prime}}I(X_{m};X_{m^{\prime}}) for total cross-modal redundancy. These quantities will feature in the modality-skew coefficient introduced in Sec. 4 , which governs the gap between achievable distortion and the bound ( 2 ). All subsequent expectations are taken with respect to P_{XY} unless stated otherwise. 3 Problem Formulation We now cast multimodal retrieval as a lossy source–coding problem and establish foundational properties of the resulting rate–distortion function. Throughout, the probability space (\Omega,\mathcal{F},P_{XY}) defined in Sec. 2 is fixed. Encoders and decoders. An (randomised) encoder is a stochastic map f:\mathcal{X}\!\to\!\mathcal{P}(\mathcal{C}) , where \mathcal{P}(\mathcal{C}) denotes the set of probability measures over a finite codebook \mathcal{C}=\{1,\dots,2^{R}\} . We write C\sim f(\,\cdot\mid X) and require I(X;C)\leq R bits. The corresponding decoder g:\mathcal{C}\!\times\!\mathcal{D}\!\to\!\mathfrak{S}_{N} outputs a permutation g(C) over the corpus indices. Together (f,g) induce a joint law P_{XCY} ; expectations \mathbb{E} henceforth refer to this law. Distortion measure revisited. Let d\bigl((X,Y),g(C)\bigr) be the non-additive ranking distortion from ( 1 ). We emphasise that d fails the separability condition d((x,y_{1}),(x^{\prime},y_{2}))=d_{1}(x,x^{\prime})+d_{2}(y_{1},y_{2}) exploited in the classical proof of Shannon’s direct coding theorem [ 33 ] ; novel arguments will therefore be required in Secs. 4 – 5 . Rate–distortion function. For any admissible distortion level D\in[0,1] define R(D)\;=\;\inf_{\begin{subarray}{c}f,g\\ \mathbb{E}[\,d\,]\;\leq\;D\end{subarray}}I(X;C), (3) where the infimum is taken over all encoder–decoder pairs with finite codebooks. Because I(X;C)=H(C) for deterministic encoders we allow randomisation explicitly; randomised codes are necessary for convexity (Lemma 3.1 ). Lemma 3.1 (Monotonicity and convexity) . R(D) is non-increasing and convex in D . Proof. Monotonicity holds since enlarging the feasible set by relaxing the constraint \mathbb{E}[d]\!\leq\!D cannot increase

Read the complete text