On the Rate-Distortion-Complexity Tradeoff for Semantic Communication
Authors: Jingxuan Chai, Yong Xiao, Guangming Shi
Organizations: the School of Artificial Intelligence at the Xidian University, Shaanxi 710071, China · the School of Electronic Information and Communications at the Huazhong University of Science and Technology, Wuhan 430074, China · the Pengcheng Laboratory, Shenzhen, Guangdong 518055, China · the Pazhou Laboratory (Huangpu), Guangzhou, Guangdong 510555, China · the School of Artificial Intelligence, the Xidian University, Xi’an, Shaanxi 710071, China
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.
Figures & tables
Fig. 1: Illustration of the semantic communication model.
Fig. 2: Curve plots of the RDC functions for Gaussian semantic sources under (a) θp=0 and various θc ; (b) various θp and θc .
Fig. 3: 3D Surf plot of the RDC tradeoff of Gaussian semantic sources: (a) RDC functions under θp=0 ; (b) RDC functions under θc=0.74 .
Fig. 4: Curve plots of the RDC functions for Gaussian semantic sources under θp=0 and (a) θc=∞ ; (b) θc=1.12 .
Fig. 6: 3D Surf plot of the RDC tradeoff of binary semantic sources.
Fig. 7: RDC curves of the image classification task: (a) Rate-complexity tradeoff curves; (b) Rate-semantic distance tradeoff curves.
Fig. 8: 3D surf plot of the simulation RDC tradeoff.
Fig. 9: (a) The classification accuracy of the proposed VRDC method under varying complexity; (b) The comparison between the classification accuracy of the DeepJSCC [ 46 ] approach and that of the VRDC method.
Fig. 10: Simulation RDC curves for image generation task under some fixed complexity: (a) Rate-distortion tradeoff; (b) Rate-perception tradeoff.
Fig. 11: Visual results of the reconstructed image samples across different transmission rate and complexity.
Dim
FLOPs (M)
Complexity
Acc ( % )
8
0.489
3.52
85.5
16
0.493
5.87
92.2
32
0.501
7.94
95.3
64
0.517
9.23
99.0
128
0.550
9.78
99.6
256
0.616
10.05
99.8
TABLE I: Results of computational complexity for classification task on MNIST (top) and CIFAR10 (bottom)
Dim
FLOPs (M)
Complexity
IS
8
0.938
4.23
1.96
16
0.942
7.65
2.08
32
0.950
10.82
2.17
64
0.967
12.37
2.24
128
0.999
13.56
2.29
256
1.065
14.21
2.33
TABLE II: Results of computational complexity for generation task on MNIST (top) and CIFAR10 (bottom)
Fig. 12: Curve plots of the relationship between FLOPs and IS across three different models on (a) MNIST and (b) CIFAR10.
Distributed deep neural networks (DNNs) for dense perception tasks such as semantic segmentation execute an encoder DNN on edge devices, and a decoder DNN typically on a large-scale cloud platform with a particular constraint on transmission bitrate. Recent works employ source codecs to enable bitrate-efficient transmission between the edge device and the cloud. However, as these approaches are typically bound to a particular type of source codec and alternative network architectures are often not explored, this results in a suboptimal rate-distortion (RD) trade-off in the low-bitrate regime. In this work, we propose two novel source codecs that enable extremely low bitrates, while improving RD performance. We demonstrate the effectiveness of our proposed source codecs by achieving state-of-the-art performance in distributed semantic segmentation at below 0.2 (0.03) bits per pixel, measured using the mean intersection-over-union metric on ADE20K (Cityscapes).
Danish Nazir, Timo Bartels, Thorsten Bagdonat +1
Group Innovation Volkswagen AG Wolfsburg, Germany · Institute for Communications Technology TU Braunschweig Braunschweig, Germany
Classical rate-distortion (RD) theory has long established the fundamental limits of lossy compression by quantifying the minimum number of bits required to represent a source under a prescribed distortion constraint. However, widely used distortion measures such as mean-squared error often fail to capture perceptual quality or semantic validity, which are increasingly central in modern learning-driven applications. Rate-distortion-perception (RDP) theory extends the RD framework by introducing perception as a third fundamental axis, quantified via distributional similarity between the source and reconstructed signals, leading to the rate-distortion-perception function (RDPF). This tutorial provides a structured overview of the coding principles underlying perception-aware lossy compression and surveys recent achievability results under different randomness assumptions. It then presents a unifying optimization viewpoint for computing the RDPF as defined by Blau and Michaeli, for both discrete and continuous sources under broad families of perceptual constraints, including f-divergences, alpha-divergences, and Wasserstein-based metrics. Special attention is given to computational tools such as alternating minimization schemes, Newton-based methods, and convex optimization formulations, as well as to analytically tractable cases such as Gaussian sources and the perfect-realism regime. Unlike recent broad surveys that emphasize generative architectures and AI-empowered communication systems, this tutorial focuses on the coding-theoretic and computational machinery needed to characterize, compute, and interpret the RDP limits. Finally, the tutorial outlines promising research directions at the intersection of information theory, neural compression, robust source coding, and perception-aware networked control systems.
Photios A. Stavrou, Giuseppe Serra, Marios Kountouris
The fundamental limit of natural signal compression has traditionally been characterized by classical rate-distortion (RD) theory through the tradeoff between coding rate and reconstruction distortion, while the rate-distortion-perception (RDP) framework introduces a divergence-based measure of perceptual quality as a modeling principle, leaving its theoretical origin unclear. In this paper, motivated by a synonymity-based semantic information perspective, we reformulate perceptual reconstruction as recovering any admissible sample within an ideal synonymous set (synset) associated with the source, rather than the source sample itself, and establish a synonymous source coding architecture. On this basis, we develop a synonymous variational inference (SVI) analysis framework with a synonymous variational lower bound (SVLBO) for tractable analysis of synset-oriented compression. Within this framework, we establish a synonymity-perception consistency principle, showing that optimal identification of semantic information is theoretically consistent with perceptual optimization. Based on this result, we further derive a tight-bound synonymous source coding rate characterization and show that its Jensen-limit relaxation leads to a synonymous rate-distortion-perception form for practical optimization. These analytical results show that the distributional divergence term arises naturally from the synset-based reconstruction objective, clarify its compatibility with existing RDP formulations and classical RD theory, and suggest the potential advantages of synonymous source coding.
Zijian Liang, Kai Niu, Changshuo Wang +2
Key Laboratory of Universal Wireless Communications, Ministry of Education, Beijing University of Posts and Telecommunications, Beijing 100876, China · State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China