REVIEW 6 minor 30 references
Lossy Compression, Realism, and Coordination
T0 review · 0 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read This paper argues that lossy compression with realism constraints and distributed coordination are the same rate-limited distribution-matching problem, with the only substantive difference being whether the constraint applies to the…
desk verdict A clear, honest survey that codifies the RDP–channel synthesis parallel and proposes a promising open problem; the main weakness is that the new proposal is unproven conjecture, but the paper is accurate and deserves serious review. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is the constraint-substitution map $Y \leftrightarrow (X,Y)$: it converts the realism requirement $P^{(n)}_{Y^{1:n}} \approx p_X^{\otimes n}$ into the coordination requirement $P^{(n)}_{X^{1:n},Y^{1:n}} \approx q_{X,Y}^{\otimes n}$, and it converts each term of the achievable regions while preserving the Markov chain $X-V-Y$ and the lower bound $R \ge I(X;V)$. Around this map the paper organizes the shared proof technology: the soft covering lemma, which makes a random codebook induce approximately the target output distribution, and the likelihood encoder, which selects codewords with probability proportional to their likelihood under the source. The map also explains the role of common randomness: because the decoder must generate entropy that the rate-$R$ message cannot carry, the sum-rate $R+R_c$ is the bottleneck, and the minimum CR is given by the necessary conditional entropy $H(Y^{\dagger}|X)$, the minimal randomness the decoder needs beyond the message.
What would settle it
Compute the achievable $(R,R_c)$ region for batched-critic coordination with a binary source $X \sim \mathrm{Bern}(1/2)$, a target channel $q_{Y|X}$ with $H_q(Y|X)>0$, and batch size $B_n=2$, using critics that inspect the joint empirical distribution of $(X,Y)$. If a positive common-randomness rate is required at this small batch size, the claimed interpolation from the RDP problem does not transfer to coordination; if deterministic schemes achieve the optimum for every subexponential $B_n$, the transfer holds. Either outcome can be decided by a finite information-theoretic calculation.
Extended reading notes
Core claim
The central claim is that under strong distribution matching, the rate-distortion-perception problem and channel synthesis for distributed coordination are fundamentally the same problem, differing only by the substitution $Y \leftrightarrow (X,Y)$. In the RDP region, the reconstruction marginal must match the source, $p_Y = p_X$, and the CR-augmented rate obeys $R+R_c \ge I(Y;V)$; in channel synthesis, the input-output joint law must match a target, $p_{X,Y} = q_{X,Y}$, and the corresponding bound is $R+R_c \ge I(X,Y;V)$. The same pattern reappears in remote-source compression and in compression with side information, so the authors present the substitution as a systematic dictionary rather than a coincidence. The shared tools—random codebooks made to cover the target distribution by the soft covering lemma, and the likelihood encoder that picks codewords by conditional likelihood—explain why common randomness is indispensable in both problems: the decoder must inject entropy beyond what the rate-limited message can carry. The paper's forward-looking component is to use this dictionary to import batched critics and algorithmic realism into coordination, asking what happens to the need for common randomness when realism is evaluated on small batches rather than on the full distribution.
Load-bearing premise
The paper's forward-looking proposal assumes, without proof, that the batch-size interpolation result proven for the rate-distortion-perception problem (deterministic codes suffice for small batches, common randomness becomes necessary for large batches) carries over to coordination, where the encoder does not control the input $X$; if that transfer fails, the proposed batched-critic coordination problem may look quite different from what the interpolation predicts.
Editorial extensions
If this is right
- Under perfect strong realism, deterministic codes provably fail at rates below the source entropy, and the required common-randomness rate $R_c$ can far exceed the compression rate $R$, since $R_c \ge H(Y|X)$ in the typical case.
- Any achievable-region or converse technique proven for one problem transfers to the other by the $Y \to (X,Y)$ substitution; the paper documents this transfer for the role of common randomness and for the joint-realism side-information formulation.
- In the RDP problem, batched critics interpolate between single-sample and full-distributional realism: at batch size 1 deterministic codes suffice, while for sufficiently large batches the strong-realism region (14) is recovered and common randomness becomes necessary.
- If the same interpolation holds for the proposed coordination formulation, deterministic schemes with no common randomness would suffice for small batch sizes, and the open batched-critic coordination problem in Table I is the concrete next characterization to pursue.
Reading between the lines
- If the interpolation property transfers to coordination, multi-agent systems that check coordination on small batches of joint actions could avoid shared randomness altogether, with common-randomness needs emerging only as the batch size grows toward full distributional coordination.
- The equivalence suggests that generative-model decoders developed for neural compression could serve as channel synthesizers for coordination, treating the target joint distribution as the model's sampling law subject to a rate constraint; this is an application the paper does not spell out.
- A testable extension is to define batched-critic versions of remote channel synthesis and side-information coordination, producing regions analogous to (23)–(27) under realization-based constraints; the paper does not derive these regions.
- If the parallel is as tight as claimed, the algorithmic-realism result that deterministic schemes are optimal for subexponential batch sizes should have a coordination counterpart, which would determine whether common randomness is truly unavoidable for coordinated behavior in practical rate-limited settings.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper presents a survey-style unification of two information-theoretic problems: rate-distortion-perception (RDP) trade-offs with strong realism constraints, and channel synthesis (strong coordination) under rate-limited communication. The authors construct a unified problem formulation in Section II, compare the known achievable regions in Section III for the point-to-point, remote-source, and side-information settings, and argue that the regions differ only by the substitution Y→(X,Y), aside from the distortion constraint. They then survey batched critics and algorithmic realism in Section IV-A and propose, as an open problem, an analogous batched-critic formulation for coordination in Section IV-B. The paper carefully flags which statements are established results, which are conjectures, and which are open.
Significance. The paper's central claim—that strong-form RDP and channel synthesis are governed by nearly identical achievable regions—is supported by accurate reproductions of published characterizations, and the explicit caveat 'besides the distortion constraint' is stated in Section III-A3. The survey's value lies in its clear side-by-side presentation of (14)/(15), (23)/(24), and (25)/(27), which makes the structural parallel transparent and could stimulate transfer of techniques across the two areas. The open problem in Section IV-B is a concrete, falsifiable research direction. The paper does not claim new theorems, but it offers a useful reference and a testable proposal; the distinction between proven, conjectured, and open statements is handled carefully.
minor comments (6)
- [Figure 1 caption] The caption states that replacing Y with (X,Y) is 'the only substantive difference between the achievable regions,' but (14) also contains the distortion constraint λ1≥E[d(X,Y)], which is absent from (15). Please add the caveat 'besides the distortion constraint,' consistent with Section III-A3.
- [Section III-A, Eq. (18)] The display for Rc(λ1) is typeset in a way that makes 'I_p(X;Y)=R(λ1)' appear to be multiplied by H_p(Y†X). Please reformat so that Rc(λ1) is defined as the minimum of H_p(Y†X) over the stated constraints, with the identity I_p(X;Y)=R(λ1) explained in a separate sentence.
- [Section IV-A] The condition 'B_n does not grow exponentially fast with n' is ambiguous; please state the exact growth condition from [10] (e.g., B_n=2^{o(n)} or B_n=O(n^k)).
- [Section III-A5] The empirical observation that 'no existing neural codec has reported needing large amounts of shared randomness' is stated without a citation or a source; please either add a reference or soften the claim to reflect that it is based on the authors' knowledge.
- [Section IV-B] For the proposed batched-critic coordination problem, it would be helpful to make precise what 'large enough B_n' means (e.g., exponential in n) and to state a conjectured region as a function of B_n, rather than only an expected interpolation property.
- [Section II-C4] The heuristic equivalence between batched critics with B_n→∞ and distributional constraints is stated informally ('for certain choices of δ'). Since this interpolation underpins the open problem in Section IV-B, a pointer to the precise statements in [10] would help the reader.
Circularity Check
No significant circularity: the central comparison is between independently established regions, with open problems explicitly labeled as open.
full rationale
The paper is a survey and synthesis, not a derivation of new limits from its own assumptions. Its central claim, that strong-realism RDP and channel synthesis have nearly identical achievable regions, is supported by a direct comparison of Eq. (14), cited to [8] (Saldi et al.), and Eq. (15), cited to [7] (Cuff). The 'Y replaced by (X,Y)' observation is an expository reading of these two published regions, not a step that feeds back into its own inputs. Section III-A3 explicitly acknowledges the distortion constraint as an additional difference, so the slogan is qualified rather than stated as an exact equivalence. The side-information and remote-source regions in Section III-B are quoted from [9], [24], and [25]; although [9] and [24] are self-citations, they are published, parameter-free characterizations that can be checked independently, and the core point-to-point parallel does not depend on them. Section IV-B's batched-critic extension for coordination is explicitly framed as an open problem, with the interpolation property only 'expected' and the technical difficulty that X is not under the designer's control acknowledged; it is not asserted as a proven consequence. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no known result is merely relabeled as a new organization. Hence no circular step meets the evidentiary standard of this review.
Assumptions & free parameters
assumptions (3)
- domain assumption The source is modeled as an i.i.d. sequence across the entire paper.
- standard math Theorems from cited works stating achievable regions (14), (15), (23), (24), (25), and (27) are correct.
- standard math The soft covering lemma and the likelihood encoder are valid tools for the settings discussed.
Cite this review
Pith. "Pith review of Lossy Compression, Realism, and Coordination." pith.science (2026). https://pith.science/paper/HRXL7DWP
@misc{pith2026260812222,
author = {Pith},
title = {Pith review of: Lossy Compression, Realism, and Coordination},
year = {2026},
howpublished = {\url{https://pith.science/paper/HRXL7DWP}},
note = {Machine review of arXiv:2608.12222}
}
read the original abstract
Classical rate-distortion theory characterizes the fundamental limits of lossy compression under fidelity constraints, but minimizing distortion often yields perceptually unsatisfying reconstructions - blurry images, over-smoothed textures, and unnatural artifacts. This has motivated a growing body of work on compression with realism constraints, which require reconstructions to be statistically indistinguishable from natural signals, giving rise to the three-way rate-distortion-perception (RDP) trade-off. This paper provides an accessible overview of this emerging area and reveals deep connections to another fundamental problem: distributed coordination under rate-limited communication. Under strong distribution matching formulations, both problems lead to nearly identical information-theoretic characterizations, both require common randomness (CR) for optimal performance, and both rely on similar analytical tools such as the soft covering lemma. Beyond a unifying perspective, we survey recent developments in formalizing realism, including batched critics and algorithmic realism, and propose to transfer such paradigms to coordination - illustrating how the connection continues to generate new problems.
Figures
Reference graph
Works this paper leans on
-
[1]
Beyond Transmitting Bits: Context, Se- mantics, and Task-Oriented Communications,
D. Gündüzet al., “Beyond Transmitting Bits: Context, Se- mantics, and Task-Oriented Communications,”IEEE Journal on Selected Areas in Communications, vol. 41, no. 1, 2023
work page 2023
-
[2]
A. El Gamal and Y . Kim,Network Information Theory. Cam- bridge (UK): Cambridge University Press, 2011
work page 2011
-
[3]
On Distribution Preserving Quantization,
M. Liet al., “On Distribution Preserving Quantization,” 2011, arXiv:1108.3728
arXiv 2011
-
[4]
Rethinking Lossy Compression: The Rate-Distortion-Perception Tradeoff,
Y . Blau and T. Michaeli, “Rethinking Lossy Compression: The Rate-Distortion-Perception Tradeoff,” inICML, 2019
work page 2019
-
[5]
Position: What Makes an Image Realistic?
L. Theis, “Position: What Makes an Image Realistic?” inICML, 2024
work page 2024
-
[6]
P. Cuffet al., “Coordination Capacity,”IEEE Transactions on Information Theory, vol. 56, no. 9, 2010
work page 2010
-
[7]
Distributed Channel Synthesis,
P. Cuff, “Distributed Channel Synthesis,”IEEE Transactions on Information Theory, vol. 59, no. 11, 2013
work page 2013
-
[8]
Output Constrained Lossy Source Coding With Limited Common Randomness,
N. Saldiet al., “Output Constrained Lossy Source Coding With Limited Common Randomness,”IEEE Transactions on Information Theory, vol. 61, no. 9, 2015
work page 2015
Show all 30 references
-
[9]
Rate-Distortion-Perception Trade-off with Strong Realism Constraints: Role of Side Information and Com- mon Randomness,
Y . Hamdiet al., “Rate-Distortion-Perception Trade-off with Strong Realism Constraints: Role of Side Information and Com- mon Randomness,”IEEE Transactions on Information Theory, 2026, Early Access, DOI: 10.1109/TIT.2026.3702694
2026
-
[10]
The Rate-Distortion-Perception Trade-Off with Algorithmic Realism,
Y . Hamdiet al., “The Rate-Distortion-Perception Trade-Off with Algorithmic Realism,” inIEEE International Symposium on Information Theory, 2025
2025
-
[11]
Multiscale Structural Similarity for Image Quality Assessment,
Z. Wanget al., “Multiscale Structural Similarity for Image Quality Assessment,” inAsilomar Conference on Signals, Sys- tems & Computers, 2003
2003
-
[12]
The Unreasonable Effectiveness of Deep Fea- tures as a Perceptual Metric,
R. Zhanget al., “The Unreasonable Effectiveness of Deep Fea- tures as a Perceptual Metric,” inIEEE/CVF CVPR Conference, 2018
2018
-
[13]
Low-Rate, Low-Distortion Com- pression with Wasserstein Distortion,
Y . Qiu and A. B. Wagner, “Low-Rate, Low-Distortion Com- pression with Wasserstein Distortion,” inIEEE International Symposium on Information Theory, 2024
2024
-
[14]
Good, Cheap, and Fast: Overfitted Image Compression with Wasserstein Distortion,
J. Balléet al., “Good, Cheap, and Fast: Overfitted Image Compression with Wasserstein Distortion,” inIEEE/CVF CVPR Conference, 2025
2025
-
[15]
PO-ELIC: Perception-Oriented Efficient Learned Image Coding,
D. Heet al., “PO-ELIC: Perception-Oriented Efficient Learned Image Coding,” inIEEE/CVF CVPR Workshops, 2022
2022
-
[16]
Generative Adversarial Networks for Extreme Learned Image Compression,
E. Agustssonet al., “Generative Adversarial Networks for Extreme Learned Image Compression,” inIEEE/CVF CVPR Conference, 2019
2019
-
[17]
Lossy Compression with Gaussian Diffusion,
L. Theiset al., “Lossy Compression with Gaussian Diffusion,” arXiv e-prints, 2022, arxiv:2206.08889
2022 arXiv
-
[18]
On the Rate-Distortion-Perception Function,
J. Chenet al., “On the Rate-Distortion-Perception Function,” IEEE Journal on Selected Areas in Information Theory, vol. 3, no. 4, 2022
2022
-
[19]
A Coding Theorem for the Rate-Distortion-Perception Function,
L. Theis and A. B. Wagner, “A Coding Theorem for the Rate-Distortion-Perception Function,” inNeural Compresison Workshop @ ICML, 2021
2021
-
[20]
Common Information Is Far Less Than Mutual Information,
P. Gács and J. Korner, “Common Information Is Far Less Than Mutual Information,”Problems of Control and Information Theory, vol. 2, 1973
1973
-
[21]
The Common Information of Two Dependent Random Variables,
A. Wyner, “The Common Information of Two Dependent Random Variables,”IEEE Transactions on Information Theory, vol. 21, no. 2, 1975
1975
-
[22]
Compression of Sources of Probability Distribu- tions and Density Operators,
A. Winter, “Compression of Sources of Probability Distribu- tions and Density Operators,” 2002, arXiv:quant-ph/0208131
2002 arXiv
-
[23]
The Likelihood Encoder for Lossy Com- pression,
E. C. Songet al., “The Likelihood Encoder for Lossy Com- pression,”IEEE Transactions on Information Theory, vol. 62, no. 4, 2016
2016
-
[24]
Remote Channel Synthesis,
Y . Hamdi and D. Gündüz, “Remote Channel Synthesis,” in IEEE Information Theory Workshop, 2025
2025
-
[25]
Channel Simu- lation via Interactive Communications,
M. H. Yassaee, A. Gohari, and M. R. Aref, “Channel Simu- lation via Interactive Communications,”IEEE Transactions on Information Theory, vol. 61, no. 6, 2015
2015
-
[26]
Villani,Optimal Transport: Old and New
C. Villani,Optimal Transport: Old and New. Springer, 2009
2009
-
[27]
Cross-Domain Lossy Compression as Entropy Constrained Optimal Transport,
H. Liuet al., “Cross-Domain Lossy Compression as Entropy Constrained Optimal Transport,”IEEE Journal on Selected Areas in Information Theory, 2022
2022
-
[28]
Non-interactive Remote Coordination,
Y . Hamdiet al., “Non-interactive Remote Coordination,” in Workshop on Machine Learning and Compression @ NeurIPS, 2025
2025
-
[29]
Strong Coordination with Side In- formation,
V . Ramachandranet al., “Strong Coordination with Side In- formation,” inIEEE International Symposium on Information Theory, 2020
2020
-
[30]
Li and P
M. Li and P. Vitányi,An Introduction to Kolmogorov Complexity and Its Applications, 4th ed. Springer, 2019. Yassine Hamdi(Member, IEEE) is a Research Asso- ciate in Machine Learning and Wireless Communications at Imperial College London, working with Pr. Deniz Gündüz (Imperial...
2016
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.