Semantic Packet Aggregation for Token Communication via Genetic Beam Search

Seunghun Lee, Jihong Park, Jinho Choi, Hyuncheol ParkarXiv 2025 · DOI · arXiv

Abstract

Token communication (TC) is essential for emerging AI-driven applications like wireless Large Language Models (LLMs). However, channel noise can cause token loss, severely degrading semantic integrity. This paper introduces SemPA-GBeam (Semantic Packet Aggregation with Genetic Beam Search), an algorithm designed to maximize Average Token Similarity (ATS) over erasure channels. By combining genetic mutation with beam search, SemPA-GBeam optimizes token grouping for packetization. Experimental results on the MS-COCO dataset show that SemPA-GBeam achieves performance comparable to exhaustive search while reducing computational complexity by over 20x.

Introduction: The Token Communication Challenge

As Generative AI and LLMs move toward wireless edge deployment, we are entering an era of "Token Communication." In this paradigm, devices transmit text-based tokens that carry dense semantic weight. Unlike classical networks where all bits are treated equally, losing a single token can fundamentally alter the meaning of a message. For instance, if a prompt like "The cat hides in the basket" loses the token "cat" due to channel noise, the resulting AI-generated output will be incorrect.

System model of token communication showing how packet loss leads to incomplete messages.

The core challenge is semantics-aware packetization: how to distribute tokens across packets so that even if some are lost, the receiver can still reconstruct the message's core meaning. Finding the optimal grouping to maximize Average Token Similarity (ATS) is an NP-hard problem, making brute-force search computationally prohibitive.

Methodology: SemPA-GBeam

To address the complexity of optimal token grouping, the authors propose SemPA-GBeam. This algorithm integrates two key strategies:

  1. Beam Search: Instead of exploring the entire search space, the algorithm maintains a fixed number of the most promising candidate groupings (the "beam width" $B$) at each iteration, ranked by their ATS scores.
  2. Genetic Mutation: To explore new groupings without violating constraints (like duplicate or missing tokens), the algorithm uses a mutation step. It randomly selects two packets within a candidate beam and swaps a token between them.
The iterative process of SemPA-GBeam, showing generations of token groups and the mutation step.

By iteratively applying these mutations and selecting the best candidates, SemPA-GBeam efficiently navigates the search space to find near-optimal packetization strategies.

Evaluation and Results

The researchers evaluated SemPA-GBeam using the MS-COCO image-caption dataset. Captions were tokenized, packetized using various methods, subjected to simulated packet loss, and then used as prompts for a Stable Diffusion model to generate images for visual and quantitative evaluation.

Key Findings:

  • Near-Optimal Performance: At a 30% packet error rate, SemPA-GBeam achieves an ATS score of 99.88% relative to the exhaustive Full Search.
  • Significant Efficiency Gains: For a sequence of 20 tokens, SemPA-GBeam requires 20.48x fewer computational steps (text encoding evaluations) than a full search.
  • Semantic Robustness: Qualitative results show that while random packetization often loses key subjects (e.g., "cat"), SemPA-GBeam preserves them, leading to much higher perceptual similarity (LPIPS) in generated images.
  • Tokenization Sensitivity: The study found that subword tokenization (e.g., BPE) is more vulnerable to packet loss than word-level tokenization, as losing one subword can destroy the meaning of the entire word.

Conclusion and Future Work

SemPA-GBeam demonstrates that semantics-aware packetization can significantly enhance the robustness of wireless AI applications. By prioritizing semantic similarity over raw bit error rates, networks can better support generative tasks. While the algorithm offers a massive speedup, computational costs still scale with the number of packets. Future research will focus on developing even more scalable algorithms and testing them against dynamic, real-world channel models.

Summary updated

Abstract

Token communication (TC) is poised to play a pivotal role in emerging language-driven applications such as AI-generated content (AIGC) and wireless language models (LLMs). However, token loss caused by channel noise can severely degrade task performance. To address this, in this article, we focus on the problem of semantics-aware packetization and develop a novel algorithm, termed semantic packet aggregation with genetic beam search (SemPA-GBeam), which aims to maximize the average token similarity (ATS) over erasure channels. Inspired from the genetic algorithm (GA) and the beam search algorithm, SemPA-GBeam iteratively optimizes token grouping for packetization within a fixed number of groups (i.e., fixed beam width in beam search) while randomly swapping a fraction of tokens (i.e., mutation in GA). Experiments on the MS-COCO dataset demonstrate that SemPA-GBeam achieves ATS and LPIPS scores comparable to exhaustive search while reducing complexity by more than 20x.
BibTeX
@misc{lee2025semantic,
  author = {Seunghun Lee and Jihong Park and Jinho Choi and Hyuncheol Park},
  title = {{Semantic Packet Aggregation for Token Communication via Genetic Beam Search}},
  year = {2025},
  eprint = {2504.19591},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.19591},
  howpublished = {arXiv},
}
Figure