From Similarity to Structure: Training-free LLM Context Compression with Hybrid Graph Priors

Technical Summary: From Similarity to Structure

Title: From Similarity to Structure: Training-free LLM Context Compression with Hybrid Graph Priors
Authors: Yitian Zhou, Chaoning Zhang, Jiaquan Zhang, et al.

1. Problem Statement

As Large Language Models (LLMs) scale to massive context windows (e.g., 128K+ tokens), two primary challenges emerge:

• Computational Cost: The quadratic scaling of standard Transformer attention makes processing extremely long inputs expensive.
• Reliability Issues: LLMs often suffer from "lost in the middle" phenomena, where performance degrades when relevant information is buried in long contexts.

Existing compression methods—such as learned compressors (e.g., LLMLingua), dense retrieval, or heuristic trimming—often struggle to balance task relevance, topic coverage, and discourse coherence under strict token budgets. Many current solutions require expensive training stages or produce "black-box" intermediate representations that lack interpretability.

2. Methodology

The authors propose a training-free, model-agnostic framework that treats context compression as a structure-aware sentence selection problem. The core innovation is the use of Hybrid Graph Priors to guide the selection process.

Key components of the pipeline include:

• Hybrid Sentence Graph Construction: Instead of relying solely on semantic similarity, the method builds a sparse graph $G$ combining two edge types:
  • Semantic Edges: A mutual $k$-nearest neighbor ($k$-NN) graph based on cosine similarity of sentence embeddings, ensuring semantic connectivity while reducing noise.
  • Sequential Edges: Short-range edges (e.g., $\Delta=1$) that preserve the physical/narrative order of the document to maintain discourse flow.
• Topic Skeleton Extraction: The framework uses MiniBatch K-Means clustering on sentence embeddings to identify the document's thematic structure. This allows the model to calculate a "representativeness" score for each sentence relative to its topic cluster.
• Structure-Aware Scoring: Each sentence is assigned a composite score $S(i)$ based on four interpretable dimensions:
  1. Task Relevance ($S_{task}$): Similarity to a user query (or the document centroid if no query is provided).
  2. Topic Representativeness ($S_{rep}$): How well a sentence represents its assigned cluster.
  3. Bridge Centrality ($S_{bridge}$): Using approximate betweenness centrality to identify "bridge" sentences that connect different topics or sections.
  4. Cycle Coverage ($S_{cycle}$): A binary cue identifying sentences that participate in local semantic cycles (e.g., claim-evidence loops), protecting local reasoning chains.
• Budgeted Selection with Redundancy Suppression: Sentences are selected via a greedy approach under a strict token budget. To prevent selecting near-duplicates, the method employs Non-Maximum Suppression (NMS) based on a cosine similarity threshold ($\tau=0.92$). The final output is re-sorted into the original document order to ensure readability.

3. Key Contributions

1. A Novel Hybrid Graph Approach: Successfully integrates semantic proximity with physical sequence order to capture both "what is similar" and "what is connected in the narrative."
2. Interpretable Structural Priors: Introduces bridge centrality and cycle coverage as explicit mechanisms to preserve document coherence and reasoning chains.
3. Training-Free & Model-Agnostic: The framework works as a plug-and-play preprocessor for any LLM without requiring fine-tuning or specialized architectures.
4. Efficiency-Performance Balance: Achieves high compression ratios while maintaining high downstream task utility.

4. Experimental Results

The method was evaluated on four major benchmarks: CNN/DailyMail, GovReport, arXiv, and PubMed.

• Superiority on Long Documents: The approach significantly outperforms strong baselines (including extractive methods like TextRank and abstractive models like BART/PEGASUS) on long-form datasets like GovReport and arXiv.
• Factual Consistency & Faithfulness: On datasets like PubMed and CNN/DailyMail, the method achieved superior BERTScore and QAFactEval (factual consistency) scores, suggesting that preserving structural links prevents the "hallucinations" or information loss common in other compression methods.
• Ablation Insights:
  • Removing sequential edges caused the largest performance drop in long documents, proving that local order is vital for discourse.
  • Redundancy suppression (NMS) is critical for efficient budget usage (improving ROUGE-2).
  • The hybrid fusion weight ($\beta$) shows that a balance of semantic and sequential edges (around $\beta=0.75$) is optimal.

5. Significance

This work shifts the paradigm of context compression from "token-level reduction" to "structure-aware extraction." By demonstrating that simple, interpretable graph priors can outperform complex trained models, the paper provides a highly practical and scalable solution for deploying LLMs in real-world applications involving massive, information-dense documents (e.g., legal, medical, or scientific research).