From Similarity to Structure: Training-free LLM Context Compression with Hybrid Graph Priors
Yitian Zhou, Chaoning Zhang, Jiaquan Zhang, Zhenzhen Huang, Jinyu Guo, Sung-Ho Bae, Lik-Hang Lee, Caiyan Qin, Yang Yang · 2026
Read From Similarity to Structure: Training-free LLM Context Compression with Hybrid Graph Priors by Yitian Zhou, Chaoning Zhang, Jiaquan Zhang, Zhenzhen Huang, Jinyu Guo, Sung-Ho Bae, Lik-Hang Lee, Caiyan Qin, Yang Yang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23277.txt.
Introduction
Zhou and eight colleagues compress long LLM contexts without training, using structural graph priors to pick a compact sentence set. A sparse hybrid sentence graph joins mutual k-nearest-neighbour semantic edges with short-range sequential edges, and clustering extracts a topic skeleton. Sentences are ranked by task relevance, cluster representativeness, bridge centrality, and cycle coverage, then a budgeted greedy pass with redundancy suppression emits the context in original order. Tests on four datasets match strong extractive and abstractive baselines, with larger gains on long-document benchmarks.
Catalog record
| CREATOR | Yitian Zhou, Chaoning Zhang, Jiaquan Zhang, Zhenzhen Huang, Jinyu Guo, Sung-Ho Bae, Lik-Hang Lee, Caiyan Qin, Yang Yang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47959 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.23277
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
From Similarity to Structure: Training-free LLM Context Compression with Hybrid Graph Priors Yitian Zhou, Chaoning Zhang, Jiaquan Zhang, Zhenzhen Huang, Jinyu Guo, Sung-Ho Bae, Lik-Hang Lee, Caiyan Qin, Yang Yang Abstract Long-context large language models remain computationally expensive to run and often fail to reliably process very long inputs, which makes context compression an important component of many systems. Existing compression approaches typically rely on trained compressors, dense retrieval-style selection, or heuristic trimming, and they often struggle to jointly preserve task relevance, topic coverage, and cross-sentence coherence under a strict token budget. To address this, we propose a training-free and model-agnostic compression framework that selects a compact set of sentences guided by structural graph priors. Our method constructs a sparse hybrid sentence graph that combines mutual k-NN semantic edges with short-range sequential edges, extracts a topic skeleton via clustering, and ranks sentences using an interpretable score that integrates task relevance, cluster representativeness, bridge centrality, and a cycle coverage cue. A budgeted greedy selection with redundancy suppression then produces a readable compressed context in original order. Experimental results on four datasets show that our approach is competitive with strong extractive and abstractive baselines, demonstrating larger gains on long-document benchmarks. 1 Introduction Large language models (LLMs) have achieved remarkable success in natural language processing tasks such as question answering and summarization, but their performance is constrained by the context window, i.e., the maximum tokens processed in one forward pass. Although existing LLMs support increasingly large windows, such as 128K tokens in GPT-4o and 400K tokens in GPT-5, processing extremely long inputs remains costly. Standard Transformer attention scales quadratically with sequence length 36 , motivating efficiency-oriented long-context architectures like sparse-attention 2 . More importantly, longer windows do not guarantee reliable use of long context, as LLM performance can drop when relevant evidence is placed in the middle of a long context 25 . Recent long-context evaluations also report sizable degradations as context length grows beyond nominal claims 17 . As a result, real systems still often rely on truncation, segmentation, or multi-stage pipelines, which can break cross-segment coherence and remove critical evidence, thereby reducing downstream task performance. Recent research addressing LLM with long inputs has shifted to how to keep fewer but better tokens, apart from how to fit more tokens, compressing long-context while keeping semantic efficiency. Research has revisited the classical connection between prediction and compression. Traditional lossless text compression based on dictionaries and statistical models is well established and widely documented 1 ; 33 . Recent work re-centers this topic around modern autoregressive language models, showing that strong next-token predictors can be turned into strong lossless compressors when paired with arithmetic coding 7 , and presenting concrete LM-based compression pipelines that achieve competitive compression rates 35 . This direction clarifies why LMs can compress in principle, but it also highlights that lossless compression is token-level and does not explicitly aim to preserve task-specific evidence, topic balance, or discourse structure that users need for reasoning and interpretability 44 . Recent studies further explore compression from a model-efficiency perspective, such as spike-driven lightweight architectures and brain-inspired sequential memory mechanisms, which suggest that structured information retention, rather than raw token capacity, is critical for scalable reasoning 47 ; 46 . In parallel, context compression has rapidly evolved from simple heuristic trimming to methods that explicitly optimize for downstream utility under a budget. A representative trend is to treat compression as a learned selection or transformation problem, where a smaller model is trained to remove redundant parts while keeping what the LLM needs. For example, LLMLingua-2 casts prompt compression as token classification derived via data distillation 31 , while QUITO leverages query-guided attention signals to filter context for long-context reasoning 39 . More recent efforts go further toward implicit or representation-level compression, aiming to pack information into fewer soft units or learned summaries and then recover task performance after compression 6 ; 34 . Related ideas have also been explored in retrieval-augmented generation and dialogue systems, where selective context utilization and redundancy reduction are critical for efficiency and robustness 14 ; 30 . These advances improve effectiveness, but they often add training stages, specialized compressors, or less transparent intermediate representations, which can be a barrier when the goal is a plug-and-play and easily explainable preprocessor 24 ; 20 . For interpretability, graph-based methods are a natural choice because they explicitly model relationships between semantic units, allowing structural signals to guide selection. Classic unsupervised extractive summarization methods build a similarity graph and rank sentences by centrality 27 ; 9 . More recently, researchers have explored richer graph constructions for long documents that incorporate multiple edge types and structural cues, aiming to better capture long-range dependencies and document organization 3 ; 29 . However, as graph designs become more complex, they can also become denser and more redundant, and many modern graph pipelines rely on learned components to achieve robust generalization, which again moves away from the lightweight, training-free goal. To overcome these issues, we aim for a context compressor that is simultaneously training-free, model-agnostic, and explainable, while still being sensitive to global structure. Our core hypothesis is that a sparse graph with carefully chosen priors can capture the minimum structure needed for robust compression without introducing a heavy learned graph encoder. Concretely, we build a hybrid sentence graph where semantic relations are represented by a mutual k -NN similarity graph and discourse flow is approximated by short-range sequential edges, so the graph reflects both “what is about the same thing” and “what is connected in the narrative.” We then extract a topic skeleton via lightweight clustering and score each sentence with task relevance and three interpretable structural priors: cluster representativeness within its topic (to encourage coverage), bridge importance via betweenness centrality (to protect cross-topic connectors), and cycle coverage (to reduce the chance of cutting local reasoning loops). Betweenness centrality provides a standard way to quantify bridge nodes in a network 11 , and cycle-basis structure offers a tractable signal for closed connectivity patterns 32 . Under a strict token budget, we perform greedy selection with redundancy control in the spirit of relevance–novelty selection 4 , and we output selected sentences in original order to preserve readability. These factors preserve topic coverage and protect cross-segment connections and coherence in semantic chains. The final output is evaluated with respect to compression ratio, task performance, and structural preservation. The main contributions of this paper are summarized as follows: (1) We propose a training-free and model-agnostic context compression framework that constructs a hybrid sentence graph by jointly modeling semantic similarity and physical order, enabling structure-aware extraction under token budgets. (2) We develop an interpretable scoring-and-selection pipeline that combines task relevance, topic representativeness, and graph structural priors, with greedy budgeted selection and redundancy control to preserve coverage and coherence. (3) We validate the method with extensive budgeted compression experiments and ablations, measuring downstream task performance and the impact of each component. 2 Related Work In this section, we review prior work along three related lines, including long-document modeling, extractive sentence selection, and LLM-oriented context compression. 2.1 Long-Document Summarization and Long-Context Modeling A common approach for long documents is to extend the model’s usable context 43 . Since standard self-attention has quadratic