Long documents are often shortened once and then queried many times, by many users, about things nobody knew in advance. Compression that is done without knowing the question is called query-agnostic. Compression that may only delete words, never rewrite them, is called extractive. Extractive query-agnostic compressors fail in a characteristic way. They keep the "typical" content and silently drop isolated facts, such as a single date, dollar figure, or vote count. When a later question targets one of those facts, the answer is gone.
This proposal borrows a lens from Boolean function analysis, the mathematics of functions of many on/off switches. Its invariance principle says that when no single switch matters much, a function behaves smoothly and predictably, like a sum of small independent effects. When a few switches dominate, which theorists call a junta, the smooth picture breaks. We treat each sentence or clause of a document as a switch, kept or deleted. We treat the model's ability to recover each piece of the document from the compressed text as the function. The claim is that documents decompose into a small junta of irreplaceable "needle" spans plus a low-influence remainder. The remainder can be compressed by a simple low-order model of how deletions add up. The junta must be detected and protected.
Core Claim
There are two parts. First, a measurable quantity predicts when and where query-agnostic compression will fail. That quantity is the slice influence of each span: how much deleting it changes the language model's ability to reconstruct each part of the document, measured under random deletions at the actual target budget. Second, a compressor that protects high-influence spans explicitly, and selects the rest by optimizing a fitted low-degree surrogate under the exact budget, will beat distilled token classifiers. The gain should be largest on worst-case, fact-targeted questions at aggressive compression rates. It will not be largest on average-case summary questions.
What is new is the target. We estimate interaction-aware, budget-specific influence of text spans on query-agnostic reconstruction probes, and we use the junta/low-influence split from invariance theory to decide which spans a single averaged importance score can safely handle.
Background and How This Differs
The invariance principle of Noise stability of functions with low influences shows that low-influence polynomials over binary inputs have the same output distribution as their Gaussian counterparts. Gaussian Bounds for Noise Correlation of Functions proves this by replacing coordinates one at a time. These results supply the method's logic: when no coordinate dominates, low-order structure determines behaviour, and the error is controlled by the largest influence.
A fixed token budget is not the full hypercube. Requiring exactly $k$ of $n$ spans to survive places the deletion mask on the slice, the set of binary vectors with exactly $k$ ones. Invariance Principle on the Slice extends invariance to this dependent domain for harmonic low-degree functions. That result is why we define and estimate influence by sampling masks on the slice rather than by independent coin flips.
We do not claim new theorems. The theory constrains the design: it tells us that a junta part is where low-order surrogates should be expected to fail.
The compression side supplies the problem and the main competitor. LLMLingua-2 distills GPT-4 deletion labels into a 355M-parameter bidirectional classifier and thresholds each token's keep-probability independently. That implicitly assumes deletions do not interact. LLMLingua drops low-perplexity tokens and shows a "cliff" beyond 20–25x compression. Fundamental Limits of Prompt Compression frames compression as rate-distortion and shows a large gap between query-agnostic methods and query-aware ones. It attributes much of that gap to neglected localized facts, a failure also stressed by Perception Compressor. Those two papers motivate the proposal by documenting the gap. Neither says which spans cause it or how to find them without the query.
KVzip is the nearest conceptual neighbour. It also uses context reconstruction as a query-free target. It differs from our proposal in three ways: it prunes internal attention states rather than text, it requires white-box access to the serving model, and it does not model how deletions interact or how redundancy across spans changes importance at a given budget. TPC attacks the missing query by generating a pseudo-query and selecting relevant sentences. We instead keep every span's content as its own probe, so no guessed intent can steer selection away from a needle.
Finally, the extractive literature supplies the combinatorial machinery and the units we delete. Exact selection under constraints is possible with integer programming, as in Constraint-Based Sentence Compression, and with relaxations, as in Approximation Strategies for Multi-Structure Sentence Compression. We reuse this machinery. The well-documented tendency of token deletion to produce ungrammatical "word salad" (Leveraging Structural Relations for Fluent Compressions) is why our switches are clauses and sentences, not single tokens.
Research Program
Setup. A document is split into $n$ spans (clauses, with sentence fallback). A keep-mask $y \in \{0,1\}^n$ with $\sum_i y_i = k$ selects the compressed text.
Probes. For each span $j$, define a probe $f_j(y)$: the per-token negative log-likelihood that an open scoring model (for example a 7–8B instruction model) assigns to span $j$'s original text, given the compressed context and a fixed "restate the passage" instruction.
The probes need no user query. They are cheap, because one forward pass over the compressed context followed by the full original text scores every $f_j$ at once. They encode the right intuition for query-agnostic compression. A span may be dropped only if its content can be recovered from what remains. A redundant fact repeated elsewhere has low influence on its own probe. A unique number does not.
Slice influence. The influence of span $i$ on probe $j$ is
$$\mathrm{Inf}^{(k)}_{ij} = \mathbb{E}_{y \sim S_{n,k}}\big[(f_j(y^{i \to 1}) - f_j(y^{i \to 0}))^2\big],$$
where $y$ is a uniformly random mask with exactly $k$ kept spans, and $y^{i\to 1}$, $y^{i\to 0}$ denote that mask with span $i$ swapped in or out against a random partner, so the budget is preserved.
Surrogate fitting. From roughly 256 random slice masks per document we fit, for each probe $j$, a sparse degree-2 surrogate
$$\hat f_j(y) = a_j + \sum_i b_{ij} y_i + \sum_{(i,l) \in N_j} c_{ijl}\, y_i y_l .$$
Pairwise terms are restricted to a candidate set $N_j$ of near-paraphrase span pairs found by embedding similarity. These pairs capture the "either copy suffices" redundancy that leave-one-out scores miss. Coefficients are fitted by lasso.
Junta detection. Spans whose maximum influence $\max_j \mathrm{Inf}^{(k)}_{ij}$ exceeds a threshold $\tau$, or whose own probe is poorly fit by the surrogate, form the junta. The junta is forced into the kept set.
Selection. The remaining budget is spent by minimizing a soft-maximum over $j$ of $\hat f_j(y)$ on the slice. A soft-maximum targets the worst-recovered span, which is the query-agnostic worst case, rather than the average. The search uses either an integer program with linearized products or greedy swaps.
Amortized version. Because querying the scoring model 256 times per document is affordable only offline (compress once, query many), we also distill the per-span maximum influence and junta labels into an XLM-RoBERTa-large span scorer of the same size as LLMLingua-2. This gives a fast compressor that can be compared at equal inference cost.
Analysis. For each document we compute two statistics: the largest influence, and the share of total influence carried by the top few spans. We test whether these predict the gap between LLMLingua-2-style independent thresholding and our joint selection. We also check, as invariance theory suggests, whether the distribution of $f_j$ under random masks looks Gaussian for low-influence documents and departs from Gaussian for junta-heavy ones.
Baselines
The naive reference points are the uncompressed context and random span deletion at the same budget. Random deletion is the "noise" process the invariance lens describes. If random deletion already matches a method on summary-style questions, that method's advantage must come from needles.
The strongest existing query-agnostic extractive method is LLMLingua-2. It is the strongest competitor because it uses the same backbone size as our distilled scorer, is fast, and is reported near the uncompressed ceiling. On MeetingBank QA it reports 86.92 exact match at over 3x compression, against 87.75 uncompressed. We will run the released model at matched token rates of 3x, 5x, 10x and 20x, measured in target-model tokens, using the same target LLMs and prompts as for our method. To remove the granularity confound, we will also run a sentence-level variant that averages its token probabilities per span. Beating it means a statistically significant gain in exact match or F1 at 10x and above on LongBench single- and multi-document QA and on NarrativeQA, with no loss at 3x on MeetingBank QA.
TPC is the strongest sentence-level competitor. It reports gains of up to 35 points on synthetic tasks and 20–27 points on document tasks over LLMLingua when no question is given, and the file gives no absolute scores. We will run TPC-Base, which is near our scorer's size, and TPC-Huge where feasible, at matched sentence budgets on LongBench and ZeroSCROLLS. LLMLingua is included because it is the source of the cliff effect, reported at 20x compression on GSM8K with about a 1.5% accuracy drop.
As an upper reference we include a query-aware selector in the spirit of Adaptive QuerySelect from Fundamental Limits of Prompt Compression. That paper reports lower distortion than the uncompressed prompt using 70% fewer tokens on NarrativeQA. The fraction of the query-agnostic-to-query-aware gap we close is the headline metric.
Three ablations isolate the key ingredients. The first replaces slice influence with leave-one-out influence measured from the full context. The second drops the pairwise redundancy terms. The third removes junta protection, keeping only the surrogate optimization. All methods share the target LLM, chunking, prompt template, and token budget, and each receives the same hyperparameter sweep of 20 configurations on a held-out LongBench development split.
Why not just…?
Why not just add a rule to LLMLingua-2 that always keeps numbers, dates, and named entities? This is the most serious threat, because many needles are exactly such tokens. We include it as a baseline at matched budget. The rule cannot recognize redundancy: a figure stated three times wastes budget if all three copies are kept. It also misses non-entity needles such as a negation, a condition, or the single sentence that states who voted against. We will report results split by question type. If the heuristic matches us on entity-answer questions but loses on the rest, the claim narrows honestly to the non-entity case. If it matches us everywhere, the influence machinery is not worth its cost, and we will say so.
Why not just score each span by leave-one-out deletion, or by attention during reconstruction as KVzip does? Leave-one-out measures influence at a budget of $n-1$, not at the target $k$. Two paraphrased copies of a fact each look unimportant when the other is present, yet deleting both is fatal. Only influence measured under random deletions at the actual operating point sees this. The leave-one-out ablation tests the point directly. The difference should be concentrated in documents with high embedding-detected redundancy, and it should grow with compression rate.
Why not just generate likely questions and compress toward them, as TPC does? Guessed questions cover the likely topics, which are exactly the spans query-agnostic compressors already keep. Reconstruction probes cover every span by construction. We expect TPC to be competitive on summarization-style LongBench tasks and to lose on questions targeting low-salience facts. The type-split analysis will show whether that is true.
Proposed Experiments
The main evaluation spans five benchmarks. MeetingBank QA tests extractive, fact-dense transcripts. The English tasks of LongBench and ZeroSCROLLS test breadth. NarrativeQA allows comparison with the query-aware reference. A synthetic needle set is built by inserting unique facts once or several times into MeetingBank transcripts, which lets us vary redundancy and position under control. Each benchmark is run at 3x, 5x, 10x and 20x compression, with one open and one API-only target model to confirm black-box transfer. We report exact match or F1, worst-decile accuracy over question types, and gap closure toward the query-aware reference.
Four checks are decisive. First, document-level max-influence should predict the accuracy loss of LLMLingua-2 relative to our joint selector, with a rank correlation clearly above zero on held-out documents. If it does not, the junta story is wrong. Second, on the synthetic needle set, our method should retain single-copy needles at 10x compression where LLMLingua-2 and TPC do not. It should also drop surplus copies of repeated needles, which the entity heuristic cannot do. Third, the surrogate's fit quality should be high for low-influence documents and should degrade as max-influence grows, as the invariance lens predicts. If fit is uniformly poor, the low-degree assumption fails and only junta protection is doing the work, which the junta-only ablation will reveal. Fourth, the distilled scorer should keep most of the offline method's gain at LLMLingua-2's inference cost. Otherwise the method is limited to the compress-once, query-many setting, and we will scope it that way.
References
- Noise stability of functions with low influences: Invariance and optimality
- Gaussian Bounds for Noise Correlation of Functions
- Invariance Principle on the Slice
- LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression
- LLMLingua: Compressing Prompts for Accelerated Inference of Large Language Models
- Fundamental Limits of Prompt Compression: A Rate-Distortion Framework for Black-Box Language Models
- Perception Compressor: A Training-Free Prompt Compression Framework in Long Context Scenarios
- KVzip: Query-Agnostic KV Cache Compression with Context Reconstruction
- Task-agnostic Prompt Compression with Context-aware Sentence Embedding and Reward-guided Task Descriptor
- Constraint-Based Sentence Compression: An Integer Programming Approach
- Approximation Strategies for Multi-Structure Sentence Compression
- Leveraging Structural Relations for Fluent Compressions at Multiple Compression Rates
- MeetingBank: A Benchmark Dataset for Meeting Summarization
- LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding
- ZeroSCROLLS: A Zero-Shot Benchmark for Long Text Understanding
- The NarrativeQA Reading Comprehension Challenge