# On the Rate-Distortion-Complexity Tradeoff for Semantic Communication

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 48 references that are in the map.
- First posted on arXiv 16 Feb 2026.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Improved Techniques for Training GANs](https://mlsanity.com/paper/1606.03498/) (2016)
- [Deep Variational Information Bottleneck](https://mlsanity.com/paper/1612.00410/) (2016)
- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [Measuring the Intrinsic Dimension of Objective Landscapes](https://mlsanity.com/paper/1804.08838/) (2018)
- [Deep Learning Enabled Semantic Communication Systems](https://mlsanity.com/paper/2006.10685/) (2020)
- [Large Language Models as Commonsense Knowledge for Large-Scale Task Planning](https://mlsanity.com/paper/2305.14078/) (2023)
- [Rethinking Lossy Compression: The Rate-Distortion-Perception Tradeoff](https://mlsanity.com/paper/1901.07821/) (2019)
- [Conditional Probability Models for Deep Image Compression](https://mlsanity.com/paper/1801.04260/) (2018)
- [6G Networks: Beyond Shannon Towards Semantic and Goal-Oriented Communications](https://mlsanity.com/paper/2011.14844/) (2020)
- [Learning Task-Oriented Communication for Edge Inference: An Information Bottleneck Approach](https://mlsanity.com/paper/2102.04170/) (2021)
- [The Description Length of Deep Learning Models](https://mlsanity.com/paper/1802.07044/) (2018)
- [Semantics-Empowered Communication for Networked Intelligent Systems](https://mlsanity.com/paper/2007.11579/) (2020)
- [Compressing Neural Networks using the Variational Information Bottleneck](https://mlsanity.com/paper/1802.10399/) (2018)
- [From Semantic Communication to Semantic-aware Networking: Model, Architecture, and Open Problems](https://mlsanity.com/paper/2012.15405/) (2020)
- [Wireless Semantic Communications for Video Conferencing](https://mlsanity.com/paper/2204.07790/) (2022)
- [Universal Rate-Distortion-Perception Representations for Lossy Compression](https://mlsanity.com/paper/2106.10311/) (2021)
- [From Entropy to Epiplexity: Rethinking Information for Computationally Bounded Intelligence](https://mlsanity.com/paper/2601.03220/) (2026)
- [Robust Information Bottleneck for Task-Oriented Communication with Digital Modulation](https://mlsanity.com/paper/2209.10382/) (2022)
- [On the Information Bottleneck Problems: Models, Connections, Applications and Information Theoretic Views](https://mlsanity.com/paper/2002.00008/) (2020)
- [The Rate-Distortion-Perception Tradeoff: The Role of Common Randomness](https://mlsanity.com/paper/2202.04147/) (2022)
- [Imitation Learning-based Implicit Semantic-aware Communication Networks: Multi-layer Representation and Collaborative Reasoning](https://mlsanity.com/paper/2210.16118/) (2022)
- [Semantic Communications Based on Adaptive Generative Models and Information Bottleneck](https://mlsanity.com/paper/2309.02387/) (2023)
- [Degrees of Freedom in Deep Neural Networks](https://mlsanity.com/paper/1603.09260/) (2016)
- [Rate-Distortion Theory for Strategic Semantic Communication](https://mlsanity.com/paper/2202.03711/) (2022)
- [Minimum Description Length and Generalization Guarantees for Representation Learning](https://mlsanity.com/paper/2402.03254/) (2024)
- [Reasoning over the Air: A Reasoning-based Implicit Semantic-Aware Communication Framework](https://mlsanity.com/paper/2306.11229/) (2023)
- [An Indirect Rate-Distortion Characterization for Semantic Sources: General Model and the Case of Gaussian Observation](https://mlsanity.com/paper/2201.12477/) (2022)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)
- [Rate-Distortion-Perception Theory for Semantic Communication](https://mlsanity.com/paper/2312.05437/) (2023)

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

- [Generalization Bounds of Emergent Communications for Agentic AI Networking](https://mlsanity.com/paper/2605.08613/) (2026)

## Abstract (arXiv)

Semantic communication is a novel communication paradigm that focuses on conveying the user's intended meaning rather than the bit-wise transmission of source signals. One of the key challenges is to effectively represent and extract the semantic meaning of any given source signals. While deep learning (DL)-based solutions have shown promising results in extracting implicit semantic information from a wide range of sources, existing work often overlooks the high computational complexity inherent in both model training and inference for the DL-based encoder and decoder. To bridge this gap, this paper proposes a rate-distortion-complexity (RDC) framework which extends the classical rate-distortion theory by incorporating the constraints on semantic distance, including both the traditional bit-wise distortion metric and statistical difference-based divergence metric, and complexity measure, adopted from the theory of minimum description length and information bottleneck. We derive the closed-form theoretical results of the minimum achievable rate under given constraints on semantic distance and complexity for both Gaussian and binary semantic sources. Our theoretical results show a fundamental three-way tradeoff among achievable rate, semantic distance, and model complexity. Extensive experiments on real-world image and video datasets validate this tradeoff and further demonstrate that our information-theoretic complexity measure effectively correlates with practical computational costs, guiding efficient system design in resource-constrained scenarios.