SALT: Salience-Aware Lexical Trie for Long-Context Compression¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/oteomamo/SALT
Area: LLM Reasoning
Keywords: Prompt Compression, Long-Context Inference, Lexical Trie, Theme Collapse, Multi-Turn Dialogue
TL;DR¶
Addressing the pervasive issue of theme collapse in scalar-ranked prompt compression, SALT introduces an unsupervised, model-agnostic extractive framework that organizes sentence keywords into a sentence-frequency-ordered trie, explicitly distributing compression budgets across document themes before sentence selection to slash prefill latency and memory footprint.
Background & Motivation¶
As context windows in modern large language models expand well beyond one hundred thousand tokens, long-context inference has become indispensable for document summarization, multi-hop question answering, and retrieval-augmented generation. However, processing massive prompts incurs prohibitive computational overhead: every additional input token linearly inflates prefill execution time, inflates the resident key-value (KV) cache in GPU memory, and disperses cross-token attention. Prior systems alleviate these bottlenecks either internally within the model—by evicting tokens or compressing KV caches (e.g., SnapKV, FastKV, SentenceKV)—or externally by compressing the textual prompt prior to the prefill phase (e.g., RECOMP, EXIT, Sentinel, LLMLingua). While preprocessing methods directly lower Time-To-First-Token (TTFT) and memory usage by reducing prompt length, existing input compressors remain bottlenecked by their fundamental candidate selection abstraction.
Nearly all existing extractive and pruning-based preprocessing methods assign an independent, one-dimensional scalar utility score to each candidate sentence, passage, or token using external rankers, proxy models, or query similarity functions, subsequently selecting high-scoring units to fill a target budget. Under aggressive compression regimes—such as retaining only 10% or 20% of the original document—this flat scalar selection paradigm triggers severe "theme collapse." Because a document naturally contains recurring primary themes alongside sparse secondary topics, a greedy top-ranked selection spends virtually the entire budget on the dominant theme while discarding lower-frequency yet logically critical information. In multi-hop reasoning, for example, scalar rankers frequently retain several redundant passages about the central entity while discarding the solitary bridge sentence required to connect that entity to the second hop.
To resolve this systemic trade-off between scalar relevance and balanced representation, this paper argues that thematic coverage must be treated as an explicit primary allocation objective rather than a post-hoc diversity heuristic. The authors observe that document-wide recurrence of content keywords provides a lightweight, robust, and unsupervised proxy for thematic structure without requiring expensive neural clusterers or repetitive pairwise semantic scoring. Core idea: by extracting salient per-sentence keywords via transformer attention with knee-point cutoff and organizing them into a sentence-frequency-ordered lexical trie, SALT allocates the compression budget across distinct theme branches prior to local sentence selection, eliminating theme collapse and enabling instant, multi-turn prompt compression.
Method¶
Overall Architecture¶
SALT is a completely model-agnostic, unsupervised extractive compression pipeline decoupled into an offline indexing phase and a budget-constrained selection phase. During the indexing phase, an input document is partitioned into sentences, which are densely packed and passed through a compact transformer encoder to extract salient keywords via attention weights and dynamic knee-point detection. The extracted keywords are filtered by their global sentence frequency (SF) to form a salience set, and each sentence is mapped to a sorted root-to-leaf path in a prefix tree (Keyword Trie). During the selection phase, given a target word budget and an optional query, SALT distributes the budget across active depth-1 theme branches and selects sentences based on their marginal reduction in uncovered branch mass, reconstructing the selected sentences in their original document order into a compact plain-text prompt.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Long Document & Dense Packing<br/>512-token chunks with 2-sentence overlap"] --> B["Keyword Extraction & Kneedle Cutoff<br/>[CLS] attention ranking & monotone envelope"]
B --> C["Keyword Trie Construction & Uncovered Mass<br/>Ordered SF anchor insertion & signature Γ(v)"]
C --> D["Branch-Wise Budget Allocation<br/>Fixed floor + sublinear residual (Mb+ε)^α"]
D --> E["Dual-Mode Retrieval & Document Reconstruction<br/>Multi-anchor query activation / summary descent"]
E --> F["Compact Plain-Text Prompt<br/>Downstream LLM prefill & KV-cache compatibility"]
Key Designs¶
1. Keyword Extraction and Kneedle Cutoff: Contextual Packing with Geometry-Driven Thresholding
Processing sentences in complete isolation squanders GPU throughput and deprives the encoder of neighboring context, preventing it from distinguishing globally central terms from locally prominent but generic ones. SALT overcomes this via dense packing, greedily concatenating consecutive sentences into 512-token chunks with a two-sentence overlap and feeding them into the compact BGE-small-en-v1.5 encoder (33M parameters). Raw [CLS] attention weights from the final transformer layer are locally renormalized over each sentence span \([s, e)\):
$\(\hat{a}(s_i)_j = \frac{a_j}{\sum_{k=s}^{e-1} a_k}, \quad j \in [s, e)\)$
To avoid static word-count thresholds that fail across sentences of varying information densities, words ordered by descending attention are iteratively accumulated. The cosine similarity \(c_t\) between the mean hidden state of the top-\(t\) subset and the full-sentence embedding is computed, smoothed into a non-decreasing monotone envelope \(\bar{c}_t = \max_{\tau \le t} c_\tau\), and evaluated using the Kneedle algorithm to detect the point of diminishing returns \(k_i\) (capped at 40% of content words), yielding an adaptive keyword set \(K_i\).
2. Keyword Trie Construction and Uncovered Mass: Topological Structure and Subtree Signatures
Assigning a sentence strictly to its single most frequent keyword discards vital co-occurrence patterns, while flat keyword bags cannot represent hierarchical dominance. SALT tabulates the global sentence frequency \(SF(w) = |\{i : w \in K_i\}|\), prunes low-frequency anchors below the \(p\)-th quantile (\(p=0.9\)) to establish the salience set \(\mathcal{S}\), and normalizes weights via \(\hat{c}(w) = SF(w) / \max_{u \in \mathcal{S}} SF(u)\). For each sentence \(s_i\), its salient keywords \(T_i = K_i \cap \mathcal{S}\) are sorted in descending order of sentence frequency and inserted as a path into the keyword trie \(\mathcal{T}\). For any node \(v\) governing descendant sentences \(D(v)\), its subtree keyword signature is \(\Gamma(v) = \bigcup_{s_i \in D(v)} T_i\). Given an admitted sentence subset \(R\), the uncovered keyword mass is formulated explicitly as:
$\(U_v(R) = \sum_{w \in \Gamma(v) \setminus C_v(R)} \hat{c}(w)\)$
where \(C_v(R) = \Gamma(v) \cap \left(\bigcup_{s_i \in R \cap D(v)} T_i\right)\). This formulation guarantees that a handful of representative sentences cover the bulk of a branch's salient mass, causing subsequent redundant sentences with already-covered anchors to experience steep diminishing returns.
3. Branch-Wise Budget Allocation: Mitigating Dominant-Theme Monopolization
To prevent greedy selection from committing the entire token capacity to an expansive dominant theme, SALT manages the target word budget \(B\) by partitioning it across active depth-1 branches before selecting individual sentences. Each branch \(b\) receives a dedicated budget quota \(\beta_b\) composed of a fixed floor reserve plus a residual share proportional to \((M_b + \epsilon)^\alpha\), where \(M_b\) denotes the branch's remaining uncovered mass and \(0 < \alpha < 1\) acts as a sublinear dampening exponent that compresses high-mass branches while guaranteeing inclusion for minor topics. Within each branch, candidates are scored by their marginal reduction in uncovered mass \(\Delta_b(s_i \mid R) = U_b(R) - U_b(R \cup \{s_i\})\) scaled by length and positional/query priors:
$\(\text{score}_b(s_i \mid R) = \Delta_b(s_i \mid R) L(n_i) I(s_i)\)$
Any unspent budget leftover after branch-level selection is redistributed through a final GlobalFill pass, maximizing budget utilization without sacrificing thematic diversity.
4. Dual-Mode Retrieval and Multi-Anchor Activation: Amortized Multi-Turn Interaction
In conversational interactions and iterative RAG setups, repeatedly re-encoding a massive document creates severe latency spikes. Because SALT's trie is constructed independently of specific user questions, the indexed tree persists in memory across dialogue turns. In summary mode, traversal initiates from the root across all active depth-1 branches. In query mode, query keywords \(K_q\) and query embedding \(e_q\) trigger multi-anchor activation: any trie node labeled with a query keyword at any depth is simultaneously activated. Candidates exhibiting strong lexical overlap and positive embedding cosine similarity are admitted alongside their immediate sentence neighbors up to quota \(\beta_q B\), after which the remaining budget is distributed across broader branches. Building the trie once allows multi-turn systems to execute query-conditioned compression in merely 11 ms per turn.
Loss & Training¶
SALT is an entirely training-free, unsupervised extractive framework requiring no gradient updates, backpropagation, or domain adaptation. The underlying feature extractor BGE-small-en-v1.5 remains strictly frozen, executing fast forward passes exclusively to harvest token attention patterns and contextual embeddings. Trie operations are handled through standard pointer structures in host memory, completely avoiding custom CUDA kernels or specialized accelerator libraries and guaranteeing seamless portability across diverse execution environments.
Key Experimental Results¶
Main Results¶
On the comprehensive LongBench benchmark (English evaluation split spanning six distinct task categories) using LLaMA-3.1-8B-Instruct under an aggressive 20% retention budget, SALT is benchmarked against leading preprocessing compressors (LLMLingua-2, EXIT, RECOMP, CPC, Sentinel) as well as state-of-the-art KV-cache compression systems (SnapKV, FastKV, SentenceKV, DuoAttention):
| Category / Method | Single-Doc QA | Multi-Doc QA | Summarization | Few-Shot | Synthetic | Code | Average Score |
|---|---|---|---|---|---|---|---|
| Full Context (100%) | 43.58 | 44.65 | 29.22 | 69.48 | 54.21 | 60.01 | 50.19 |
| KV Cache Methods (20%) | |||||||
| SnapKV | 43.29 | 43.80 | 26.69 | 67.96 | 53.46 | 51.91 | 47.25 |
| FastKV | 43.33 | 44.37 | 26.73 | 68.70 | 53.20 | 52.46 | 47.54 |
| SentenceKV | 39.24 | 43.82 | 28.18 | 69.26 | 53.24 | 47.33 | 46.42 |
| DuoAttention | 34.71 | 36.67 | 24.30 | 58.02 | 50.81 | 54.33 | 41.96 |
| Preprocessing Methods (20%) | |||||||
| LLMLingua-2 | 30.28 | 30.39 | 24.04 | 19.26 | 12.62 | 39.57 | 26.02 |
| EXIT | 31.30 | 23.37 | 25.14 | 58.56 | 13.50 | 37.34 | 32.30 |
| RECOMP | 35.88 | 41.09 | 25.47 | 52.06 | 50.77 | 37.36 | 39.98 |
| CPC | 38.91 | 39.42 | 24.97 | 49.11 | 51.50 | 21.84 | 37.74 |
| Sentinel | 39.85 | 41.66 | 26.15 | 38.78 | 51.55 | 38.83 | 39.47 |
| SALT (Ours) | 40.05 | 41.42 | 26.95 | 62.21 | 53.37 | 37.06 | 43.51 |
Ablation Study¶
To isolate the exact impact of branch-level quota allocation versus conventional scalar ranking in preventing theme collapse, an ablation on GovReport removes the depth-1 branch partition while holding all other extraction, scoring, and reconstruction parameters constant:
| Retention Budget | SALT Coverage (%) | Scalar Coverage (%) | Δ Coverage (pp) | Δ ROUGE-L | Note |
|---|---|---|---|---|---|
| 10% | 81.57 | 78.88 | +2.69 pp | +0.23 | Tightest budget exhibits the largest advantage for branch allocation |
| 20% | 91.38 | 89.66 | +1.72 pp | +0.04 | Over 91% of global salient keyword mass is successfully retained |
| 30% | 95.94 | 94.49 | +1.45 pp | +0.37 | Subtree coverage approaches saturation across major themes |
| 40% | 97.90 | 96.83 | +1.07 pp | +0.00 | Higher budgets naturally allow scalar baselines to reach secondary topics |
Additional multi-turn and hardware profiling on QuALITY (50 narrative articles, 972 total question turns): - Cumulative Dialogue Efficiency: Over 19 consecutive dialogue turns, the uncompressed baseline requires 3.71 s of cumulative computation, FastKV requires 2.62 s, and RECOMP requires 1.88 s. By building the trie once (190 ms) and executing query retrieval at only 11 ms/turn, SALT achieves a cumulative turnaround of 0.91 s—a 4.08× end-to-end speedup over the baseline and 2× faster than RECOMP while outperforming RECOMP by 11 accuracy points (72.6% vs. 61.5%). - Scalability & Cross-Generation Portability: Across prompt lengths scaling from 16k to 256k tokens on PG19, peak GPU memory for SALT scales mildly from 16.70 GB to 32.80 GB on H100 (1.83× scaling), whereas EXIT OOMs beyond 64k. Furthermore, on legacy NVIDIA Volta V100 GPUs (lacking bf16 and modern FlashAttention-2 support), SALT smoothly handles 256k tokens without modification.
Key Findings¶
- Branch Allocation Counters Low-Budget Theme Collapse: The ablation demonstrates that explicit branch quota allocation provides the greatest margin (+2.69 pp coverage) at the tightest 10% budget. In semantic validation using K-means clustering (\(k=10\)), SALT covers 9.45 to 13.30 pp more semantic clusters than scalar selection, proving that lexical branch allocation faithfully protects semantic diversity.
- Granularity Dictates the Code Modality Gap: Preprocessing methods systematically underperform on code understanding (SALT at 37.06 vs. FastKV at 52.46) because line breaks, indentation, and isolated structural tokens carry rigid semantic dependencies that whole-sentence extraction fractures. SentenceKV, the only KV-cache baseline that aggregates states at sentence boundaries, exhibits an identical performance drop (47.33), demonstrating that the limitation stems strictly from unit granularity rather than the compression paradigm itself.
Highlights & Insights¶
- From Post-Hoc Reranking to Pre-Hoc Branch Quotas: Rather than scoring candidates in isolation and penalizing similarity post-hoc (as in MMR), SALT maps documents to an explicit hierarchical structure and reserves budget across branches up front, ensuring that minor themes receive non-zero capacity regardless of dominant-theme dominance.
- Monotone Envelopes with Adaptive Kneedle Geometry: Replacing brittle fixed percentage cutoffs with geometric knee-point detection over running-maximum cosine reconstruction trajectories enables robust, content-adaptive keyword extraction without manual hyper-parameter tuning per domain.
- Model-Agnostic Composability: Emitting clean, natural plain text allows SALT to sit transparently before any downstream LLM or serving framework, functioning synergistically alongside internal cache optimizers (like FastKV) to simultaneously conquer prefill compute and decoding memory constraints.
Limitations & Future Work¶
- Suboptimal Sensitivity for Source Code: Natural language sentence tokenization struggles with syntactic structures and indentation blocks in programming languages, suggesting the need for specialized Abstract Syntax Tree (AST) node parsing.
- Sentence Granularity Imprecision for Isolated Fact Extraction: In needle-in-a-haystack tasks where the relevant evidence is a brief phrase, whole-sentence extraction inevitably admits distracting tokens, highlighting the potential for finer clause-level or phrase-level trie modeling.
- Language Scope: The current experimental validation and keyword encoder (BGE-small-en-v1.5) are centered on English, necessitating future extensions with multilingual tokenizers and cross-lingual embedding backbones.
Related Work & Insights¶
- vs. RECOMP / EXIT (Supervised Extractive Compressors): RECOMP and EXIT rely on fine-tuned transformer scoring models whose forward overhead scales linearly with prompt length and must be re-run on every turn; SALT uses an unsupervised lexical trie built once and reused across turns, cutting per-turn compression latency to 11 ms.
- vs. LLMLingua / LLMLingua-2 (Token-Level Pruning): Token-level compressors prune words based on perplexity, achieving high compression but disrupting natural grammar and readability; SALT selects complete grammatical sentences, preserving semantic coherence and downstream readability.
- vs. SnapKV / FastKV (Cache-Side Optimization): Internal KV-cache eviction compresses state during decoding but still forces the model to prefill the entire prompt; SALT shortens the prompt before prefill, reducing prefill compute, TTFT, and KV-cache volume simultaneously while remaining fully composable with cache compressors.
Rating¶
- Novelty: ⭐⭐⭐⭐☆ Reframing prompt compression around hierarchical theme allocation via sentence-frequency tries is a fresh and elegant departure from standard scalar ranking.
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ Comprehensive evaluations spanning LongBench, QuALITY multi-turn conversations, RULER NIAH tasks, and cross-hardware benchmarking across four NVIDIA GPU generations.
- Writing Quality: ⭐⭐⭐⭐⭐ Clear exposition of theme collapse, mathematically rigorous formulation of trie mass metrics, and honest diagnostic ablations.
- Value: ⭐⭐⭐⭐⭐ Training-free, lightweight, and completely open-source, providing an immediate plug-and-play accelerator for long-context RAG pipelines and autonomous agents.