Mapping Text to Multiplex Graph: Prompt Compression as L'evy Walk-Guided Graph Pruning

arXiv:2607.01241 · cs.CL, cs.AI · Submitted 2026-05-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Mapping Text to Multiplex Graph: Prompt Compression as L'evy Walk-Guided Graph Pruning".

Jane: The paper was written by Yaxin Gao, Yao Lu, Jinhong Deng, Jiaqi Nie, Zhe Tang et al. from Institute of Cyberspace Security, Zhejiang University of Technology and Binjiang Institute of Artificial Intelligence, Zhejiang University of Technology and University of Electronic Science and Technology of China and School of Cyberspace, Hangzhou Dianzi University and D5 Data and Centre for Frontier AI Research, Agency for Science, Technology and Research and Institute of High Performance Computing, Agency for Science, Technology and Research.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: This title is a total marathon! "Mapping Text to Multiplex Graph: Prompt Compression as Lévy Walk-Guided Graph Pruning."

Jane: It certainly is, Tom, but if we strip away the jargon, it's just describing a way to turn a long, messy text into a smart map.

Tom: A smart map sounds much easier to navigate than a thousand-page document.

Jane: Exactly, and the researchers are using that map to decide which parts of the text are actually worth keeping.

Tom: Who are the minds behind this complex approach?

Jane: It's a large group of researchers, including Yaxin Gao and Shanqing Yu, working out of places like the Zhejiang University of Technology.

Lu: I love how they aren't just looking at words in a line anymore.

Tom: You think the "multiplex graph" part is the big change?

Lu: Definitely, because instead of a flat string of text, they're building this beautiful, multi-layered web where every idea connects to others in different ways.

Meng: That sounds like it could get incredibly heavy for a computer to process, though.

Jane: That's actually why they added the "pruning" part to the title, Meng.

Meng: So they build the whole web and then immediately start cutting out the useless parts?

Jane: Precisely, which keeps things fast enough for real-world use.

Lalam: It feels like we're teaching AI to see the architecture of human thought rather than just reading a list of words.

Tom: That's a huge shift in how an LLM perceives a story or a report.

Jane: It really is, and it leads us right into how they actually build that web.

Summary: Tom: We're digging into the guts of "Mapping Text to Multiplex Graph: Prompt Compression as Lévy Walk-Guided Graph Pruning" now.

Jane: They call their specific method RAGP, which stands for Redundancy-Aware Graph Pruning.

Tom: And they aren't just using one type of connection in this graph, right?

Jane: No, they use two layers—one that looks at how words relate in a single sentence and another that looks at how different sentences relate to each other.

Lu: It's like having a microscope for the local details and a telescope for the big picture at the same time!

Tom: And then there's this "Lévy walk" thing they use to move through it?

Lu: Yes, it's actually inspired by how animals forage for food in nature.

Jane: Instead of just walking around aimlessly, the Lévy walk allows the system to take small steps locally and then occasionally make these big, sudden jumps to a completely different part of the graph.

Meng: I noticed they mentioned a pre-filtering step called M1 in the paper.

Jane: They did, and that's crucial because it clears out the obviously irrelevant sentences before they even start building the complex graph.

Meng: That makes sense if we want to keep the computational cost from exploding.

Lalam: By jumping around like that, the AI can find those rare, vital pieces of information that are scattered across a massive document.

Tom: It sounds like they're hunting for meaning instead of just scanning for keywords.

Jane: That's a great way to put it, and it leads to some pretty staggering results in their tests.

Improvements: Tom: The numbers in "Mapping Text to Multiplex Graph: Prompt Compression as Lévy Walk-Guided Graph Pruning" are actually kind of mind-blowing.

Jane: They hit an average score of forty-nine point three on the LongBench benchmark!

Tom: And they did that while compressing the text four times over?

Jane: They did, which is even more impressive because a leading method called LongLLMLingua only got a forty-eight point eight score with only three times the compression.

Meng: I was looking at their cost analysis in Table four and it's not just about accuracy.

Tom: What caught your eye there?

Meng: They showed that using this method can reduce inference costs by about eighteen point three percent because you're sending so much less data to the model.

Jane: They also found a "sweet spot" for their settings, specifically using a Lévy exponent of two point five and a sparsity threshold of thirty percent.

Lu: This is the breakthrough we need to let AI read entire libraries or massive legal archives without needing a supercomputer.

Tom: So we're moving from "can this model read a chapter" to "can it read an entire series of books"?

Lu: Exactly, because the graph structure handles that complexity so much better than a simple list of tokens.

Lalam: If we can make these models more efficient, it means high-level intelligence becomes accessible to everyone, not just people with massive server farms.

Jane: It turns a luxury tool into something that can run anywhere efficiently.

Tom: It really is a game-changer for how we handle long-form information.

Conclusion: Tom: We've covered a lot of ground today regarding "Mapping Text to Multiplex Graph: Prompt Compression as Lévy Walk-Guided Graph Pruning."

Jane: It's clear that moving from flat text to these multi-layered graphs is a massive step forward for prompt compression.

Tom: It makes the whole process smarter, faster, and much cheaper.

Lu: I can't wait to see how this evolves into even more complex, multi-modal webs of information!

Meng: From my side, seeing such a clear path to reducing latency and cost makes this very exciting for actual deployment.

Lalam: It's the beginning of a more thoughtful era where AI respects the structure and nuance of our language.

Tom: Well, that's all the time we have for this one.

Jane: Thanks for joining us on the show!

Tom: We'll catch you next time with another incredible paper.

Institute of Cyberspace Security, Zhejiang University of Technology · Binjiang Institute of Artificial Intelligence, Zhejiang University of Technology · University of Electronic Science and Technology of China · School of Cyberspace, Hangzhou Dianzi University · D5 Data · Centre for Frontier AI Research, Agency for Science, Technology and Research · Institute of High Performance Computing, Agency for Science, Technology and Research

cs.CL, cs.AI

Submitted: 2026-05-04

Updated: 2026-09-14

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 80/100

The gist: This paper presents RAGP, a novel framework that reformulates prompt compression as "Redundancy-Aware Graph Pruning" on a multiplex graph.

Key concepts

RAGP
RAGP, or Redundancy-Aware Graph Pruning, is a method that transforms long text into a multi-layered graph. It uses two layers—one for word relationships within sentences and another for connections between sentences—to identify essential information and prune redundant parts, making prompt compression more efficient for large language models.
Lévy walk
Inspired by animal foraging patterns, a Lévy walk is a navigation technique used to move through the text graph. The system takes small, local steps to examine details and occasionally makes large, sudden jumps to different parts of the graph to locate rare, vital information scattered across documents.
Multiplex graph
A multiplex graph is a multi-layered web of connections used to represent text. Unlike a flat string of words, it maps different types of relationships simultaneously, such as how words relate within a single sentence and how different sentences relate to one another, capturing a more complex structure.

Terminology

Summary

This paper presents RAGP, a novel framework that reformulates prompt compression as Redundancy-Aware Graph Pruning on a multiplex graph. By addressing the limitation where existing methods treat text as flat token sequences, the authors provide a way to capture information that is distributed rather than isolated across local syntactic dependencies and global semantic relations. This approach is vital for improving the efficiency, accuracy, and scalability of Large Language Model (LLM) inference in long-context scenarios.

Multiplex Graph Construction

The authors construct a multiplex graph to capture the dual nature of document structure, transforming prompt compression into a graph-theoretic problem of identifying and pruning redundant nodes. This structure integrates two distinct layers of connectivity to represent the hierarchical organization of text:

  • An intra-layer relation layer (G(0)) that encodes local semantic dependencies among words using attention patterns from a pretrained language model, where edge weights are defined by aggregating token-level attention scores.

  • An inter-layer relation layer (G(1)) that captures global semantic relations across sentences using sentence embeddings and cosine similarity.

These layers are coupled via a hierarchical mapping pi that assigns each fine-grained node to its corresponding sentence, creating a heterogeneous structure consisting of dense local subgraphs and sparse global connections.

Lévy Walk-Based Importance Estimation

To effectively navigate this heterogeneous graph, RAGP introduces stochastic Lévy walks whose heavy-tailed step distribution naturally balances local exploitation with global exploration. This is necessary because standard random walks often fail to navigate such structures, tending to remain trapped in local neighborhoods. The authors provide theoretical support via Proposition 4.1, noting that Lévy walks achieve faster sentence coverage when the heterogeneity ratio eta —the ratio of local to global degrees—is sufficiently high. The traversal dynamics are defined by:

  • Local traversal: While the current segment length L > 0, the walker remains within the fine-grained subgraph of a sentence, sampling neighbors according to row-normalized edge weights.

  • Global transition: When L = 0, the walker performs a coarse-grained transition by sampling a new sentence node from the coarse-grained graph.

By tracking visit frequency, RAGP identifies nodes that are either well-connected within their local context or serve as semantic bridges between sentences. Consequently, visit frequency acts as a natural proxy for non-redundant informativeness.

Experimental Results and Efficiency

Extensive evaluations on the LongBench benchmark demonstrate that RAGP achieves state-of-the-art performance. The method demonstrates high efficiency and accuracy across various tasks:

  1. On LongBench, RAGP records an average score of 49.3 under a 4× compression ratio, outperforming competitive LLM-based baselines like LongLLMLingua (which attains 48.8 at a 3× ratio).

  2. The framework surpasses state-of-the-art vision-based text compression paradigms on multiple tasks and maintains performance on par with full-context models in several cases.

  3. In terms of practical utility, RAGP can reduce input tokens by nearly 60% while simultaneously improving QA F1 scores in specific testing scenarios, leading to significant reductions in both inference latency and monetary cost.

Improvements for AI systems

1. Implementation of a Multiplex Graph Prompt Compression Module

  • The Improvement: Replace current flat, token-level pruning methods (like LLMLingua or Selective-Context) with a two-layer multiplex graph pre-processor. This module will construct a fine-grained layer using model attention weights to capture local syntactic dependencies and a coarse-grained layer using sentence embeddings to capture global semantic relations. A stochastic Lévy walk traversal will then be used to estimate node importance based on visit frequency.

  • Improved System Capability: The AI can process massive, high-density documents (e.g., legal contracts, medical records, or entire codebases) with significantly reduced inference latency and cost. Unlike current systems that suffer from lost-in-the-middle degradation, this system will maintain high reasoning accuracy by preserving the structural bridges of information—retaining tokens that are locally salient and globally connective while aggressively pruning redundant filler.

2. Structural-Aware Retrieval-Augmented Generation (RAG) Engine

  • The Improvement: Transition from traditional chunk-and-retrieve RAG to Graph-Hub Retrieval. Instead of retrieving isolated text chunks based solely on cosine similarity, the system will retrieve subgraphs identified by Lévy walk high-frequency nodes. This involves retrieving not just the target sentence, but its immediate attention-based neighbors and its semantic global neighbors in the multiplex graph.

  • Improved System Capability: The AI will exhibit superior multi-document reasoning and complex QA performance. It will be able to connect disparate pieces of information spread across different parts of a document (or different documents) that are semantically linked but textually distant, preventing the loss of context that occurs when traditional RAG retrieves disconnected snippets.

3. Lévy-Weighted Importance Sampling for Long-Context Training

  • The Improvement: Integrate the Lévy walk importance estimation into the data sampling and loss calculation stages of training long-context LLMs. Instead of treating all tokens in a long sequence with equal weight, use the visit frequency from a multiplex graph traversal to weight the attention heads or the gradient updates during pre-training/fine-tuning.

  • Improved System Capability: This enables more efficient training of models designed for extremely long context windows. The system will learn to prioritize non-redundant information and structural dependencies, leading to models that are more robust at reasoning over long sequences without requiring a proportional increase in computational budget or memory.

4. Multimodal Structural Compression Agent

  • The Improvement: Extend the multiplex graph framework to multimodal inputs (e.g., video + audio + text). The system will construct a graph where nodes represent visual patches, audio segments, and text tokens, with edges defined by cross-modal attention weights. Lévy walks will navigate this heterogeneous space to identify the most informative multimodal anchors.

  • Improved System Capability: A multimodal AI agent can perform real-time reasoning on long video streams or complex multi-sensory environments. It can prune irrelevant visual frames or background noise by identifying which sensory inputs are structurally tied to the user's textual query, enabling high-fidelity multimodal understanding on edge devices with limited compute.

Sources

Related papers