A compressor that shortens a long document before anyone has asked a question has to guess what future questions will need. In the worst case that guess is impossible: if any fact might be asked about, nothing can be safely dropped. Our bet is that real questions are not worst-case. They have a simple shape along the document itself. A question about a document usually cares most about one region, and its interest falls off as you move away from that region. Social choice theory has a name for this shape, single-peaked preferences: voters rank candidates on a line, each voter has a favorite point, and their liking drops with distance from it. It also has a mature toolkit for preferences that are nearly single-peaked. That toolkit measures how many voters must be removed before the structure holds exactly, and it runs committee-selection rules efficiently on the structured remainder.
We propose to treat query-agnostic compression as picking a committee. Sentences are the candidates, and a pool of cheaply generated probe questions, spread across different kinds of intent, are the voters. The document order is the axis. When the probes' preferences are nearly single-peaked on that axis, three things follow. We can choose which contiguous spans to keep by an exact dynamic program. We can issue a worst-case coverage certificate for any future question whose relevant region has the same interval shape. And the number of "structure-breaking" probes, those that must be deleted to restore single-peakedness, gives a per-document estimate of how much the document can be compressed without knowing the query. We expect those breaking probes to be aggregation and multi-hop intents.
Core Claim
The claim has three parts, and each can be tested separately. First, relevance profiles of real long-context questions over document sentences are nearly single-peaked along document order when truncated to their top-ranked sentences. Most retrieval-style questions need few or no deletions. Aggregation questions are the ones that must be deleted. Second, under that structure, a compressor that combines an exact interval-covering committee rule with a uniform "floor" of kept spans has a coverage guarantee for unseen interval-shaped questions. A generic importance score or a greedy coverage heuristic has no such guarantee. Third, the voter-deletion distance of a document's probe profile predicts how much task performance drops at a given compression ratio. That prediction can set the retention budget before any query arrives.
The new element is not "compression as coverage"; greedy coverage on pseudo-queries is a natural baseline, and we treat it as the main threat. What is new is using distance-to-structure as the compressor's organizing quantity. It is the thing that licenses a guarantee, the thing that sets the budget, and the thing that identifies which intents fall outside the guarantee and need separately reserved tokens.
Research Program
Probe profiles. For a document split into $m$ sentences in reading order, a small model generates $n$ probe questions (we plan $n$ in the tens). They are drawn deliberately across a multi-dimensional intent space: local factual detail, cross-section comparison, numeric lookup, summary breadth, and entity tracking. To reach sparse corners of this space, we borrow the neighborhood idea from Robust Preference Alignment via Directional Neighborhood Consensus. That work improves generation for unusual multi-attribute preference directions by sampling from nearby, better-covered directions and scoring against the target. We use the same move to generate probes for rare intent mixtures from nearby common ones. Unlike that work, we select context rather than responses, and we do not rely on a reward model at the selection step. Each probe scores every sentence with a small bidirectional encoder of LLMLingua-2 scale. The probe's "vote" is its top-$r$ sentences, treated as an approval set.
We truncate to approval sets on purpose. Martin Lackner showed that deciding whether incomplete rankings extend to a single-peaked profile is NP-complete, and the low-relevance tail of a full ranking is essentially noise. So we test the approval analogue instead: is each probe's approved set close to a contiguous interval of the document?
Distance to structure. We measure how far the profile is from interval structure using the deletion models of On Detecting Nearly Structured Preference Profiles. That paper recasts voter and candidate deletion as hitting-set problems over forbidden configurations. It gives a 2-approximation and algorithms whose running time is exponential only in the deletion count $k$ ($O^*(1.28^k)$ for single-peaked voter deletion). We also allow a bounded number of adjacent swaps, following On Recognising Nearly Single-Crossing Preferences, so that one misplaced sentence does not force a whole probe to be deleted. The output is a set of structured probes and a small set of deleted "outlier" probes, each labeled by its intent type.
Selection. On the structured probes, choosing a budget of kept sentences so that the most probes have at least one approved sentence retained is the Chamberlin-Courant rule restricted to interval approvals. This reduces to a stabbing problem on intervals and has an exact dynamic program over positions. Efficient Algorithms for Monroe and CC Rules in Multi-Winner Elections with (Nearly) Structured Preferences supplies the extension to profiles that are structured after deleting $t$ voters. It shows Chamberlin-Courant is tractable when the running time is allowed to grow only with $t$. We avoid that paper's Monroe algorithm, whose $O(n^{11}m^5k)$ cost is impractical.
Each kept sentence is expanded to a short contiguous span, which targets the incoherent "word salad" that token-level pruning produces. A fixed fraction of the budget goes to a uniform floor: one kept span every $L$ sentences. The rest of the budget is split between the committee and the outlier probes, and the outliers are served by an ordinary greedy coverage step because no structure is available for them.
Certificate. The floor guarantees that every future question whose approved interval spans at least $L$ sentences is covered, whatever the question is. For shorter intervals, the probes give a statistical bound. Let $\hat{c}$ be the fraction of structured probes covered, $c$ the coverage for future interval-shaped questions from the same intent distribution, $B$ the number of kept positions, and $\delta$ the failure probability. Then with probability at least $1-\delta$,
$$ c \ \ge\ \hat{c} - \sqrt{\frac{B\log m + \log(1/\delta)}{2n}} . $$
This follows from Hoeffding's inequality and a union bound over the at most $m^B$ possible kept sets. It has the same flavor as the sampling argument in Generative Social Choice, which bounds how many participants must be queried to guarantee a representation axiom for LLM-generated statement slates. We state plainly that this bound does not itself need interval structure. The structure contributes the unconditional floor guarantee and the exact optimizer. The deletion count $t$ then says what fraction of intents lie outside both.
Budget prediction. A calibrated regression maps the pair (deletion fraction $t/n$, compression ratio) to predicted task loss. This plays the same role as the curve relating compression ratio to likelihood loss that Compactor fits per context. Our version needs no forward pass of the target model over the compressed context.
Where the other directions sit. Approximate domain restriction is the mechanism, query-agnostic compression is the application, and multi-dimensional preference modeling shapes the probe design and the analysis. Preference Restrictions in Computational Social Choice: Recent Progress notes that structural guarantees collapse in multi-dimensional spaces. We therefore do not try to embed intents in $\mathbb{R}^d$. We project everything onto the one axis that documents supply for free, reading order, and treat the multi-dimensional residue as deletions. As a secondary analysis, we test whether splitting probes into two structured groups, one "local" and one "global", explains the residue. The two-group single-crossing split is polynomial by 2-SAT per On Recognising Nearly Single-Crossing Preferences.
Baselines
The naive reference points are the full uncompressed context, middle truncation as used by default in LongBench, and uniform span sampling at the same token budget. Uniform sampling matters especially because it is our floor taken alone. If the committee adds nothing over it, the structure is not being used.
The strongest existing prompt-level methods are LLMLingua-2 and TPC. LLMLingua-2 is a distilled token keep/drop classifier. It reports 86.92 exact match on MeetingBank QA against 87.75 uncompressed, at more than 3x token reduction. TPC infers a task descriptor with a reinforcement-learned small model and keeps the top sentences by relevance to it. It reports gains of 20 to 27 points on document tasks and up to 35 on synthetic tasks over LLMLingua in LongBench's task-agnostic setting. It also reports that TPC-Huge outperforms prior methods on LongBench and ZeroSCROLLS. We found no absolute per-task TPC scores on Lacuna, so we will rerun it from the official code (bliskavets/TPC).
As a cache-level reference we include Compactor. It reports recovering about 95% of the full-cache LongBench score at 25% retention and a 68% average memory reduction with calibration. Because it compresses the KV cache (the stored attention keys and values) rather than the prompt, we compare at matched retained-token fractions and label it as a different granularity.
All methods share the same target reader model, documents, token budgets (2x, 3x, 5x, 10x), and probe or descriptor generator size where applicable. Each method gets an equal hyperparameter-tuning budget on a held-out development split.
Two ablations isolate the key ingredient. The first is greedy coverage on the identical probe pool, with no axis, no deletion step, and no floor. The second is our full dynamic program run on a randomly shuffled sentence order, which destroys the axis while keeping everything else fixed. A third ablation removes outlier routing. Beating the prior methods means a statistically significant gain in average task score at 5x or higher compression on LongBench and ZeroSCROLLS. Beating the ablations means higher coverage and task score on held-out real questions at equal probe count.
Why not just…?
Why not just generate one pseudo-query and run a query-aware compressor? This is essentially TPC's design. Its single inferred descriptor commits the compression to one task focus, so information about a secondary intent is lost for good. The file's discussion of "information neglect" in task-blind reduction points the same way. Our probe pool is a multi-intent generalization of that idea, and the TPC baseline, run at matched probe-generation cost, shows directly whether one descriptor is enough. We expect TPC to be competitive on single-document QA and to lose on comparison and aggregation questions.
Why not just run greedy coverage over the probe pool? This is the real threat. Greedy coverage is near-optimal in practice for coverage objectives, and the generalization bound above holds for it too. If greedy matches us on held-out task scores, the exact dynamic program adds nothing, and we will say so. Two contributions would survive that outcome: the unconditional floor guarantee and the deletion-distance budget predictor. Neither comes from greedy selection. The shuffled-axis and greedy ablations settle this cleanly.
Why not just keep evenly spaced chunks, or truncate the middle? Uniform spacing is in fact the worst-case-optimal answer if all we know is that questions have interval shape. That is why it is our floor. But LongBench shows large drops at long lengths even with middle truncation, with GPT-3.5-Turbo-16k losing 17% accuracy from the 0–4k to the 8k+ range. ZeroSCROLLS shows position-based heuristics failing on aggregation. The question is whether learned placement beats uniform placement at equal budget, and the uniform baseline answers it.
Why not just use one importance score, such as leverage scores or a keep/drop classifier? A single score cannot represent intents that conflict, such as fine detail versus summary breadth. That is the multi-attribute failure documented for single-direction generation in the directional-consensus paper. More concretely, a single score carries no certificate and no budget signal. Still, Compactor's strong LongBench retention is a real threat on retrieval-heavy tasks, and we expect our gains to show up mainly at high compression and on ZeroSCROLLS aggregation and multi-hop tasks.
Proposed Experiments
We evaluate on LongBench (single-document QA, multi-document QA, summarization), on ZeroSCROLLS including the aggregation tasks SpaceDigest and BookSumSort (for which we found no reported compressor results on Lacuna), and on MeetingBank QA for direct comparison with LLMLingua-2's reported number.
The first decisive check tests the structural premise. For each real benchmark question, used for analysis only and never shown to the compressor, we compute its approval set with the same scorer and measure its deletion and swap distance to interval structure. The premise fails if, even after allowing a small fixed number of swaps, most single-document QA questions are not interval-shaped. It also fails if interval-shaped fractions are no higher for single-document QA than for aggregation tasks. In either case, we would report the negative result and stop at that finding.
The second check tests the certificate. On held-out real questions, observed coverage should sit at or above the bound, and it should be at 100% for questions whose intervals are longer than $L$.
The third check tests prediction. Across documents, the probe deletion fraction should correlate with the observed task-score drop at fixed compression. We will compare its predictive accuracy with a likelihood-curve calibration in the style of Compactor at equal cost.
The fourth check is the end-to-end comparison against the baselines and ablations above, at 2x to 10x compression. We will pay particular attention to the 20x-and-beyond regime, where LLMLingua reports a sharp performance cliff on GSM8K.
References
- Robust Preference Alignment via Directional Neighborhood Consensus
- Incomplete Preferences in Single-Peaked Electorates
- On Detecting Nearly Structured Preference Profiles
- On Recognising Nearly Single-Crossing Preferences
- Efficient Algorithms for Monroe and CC Rules in Multi-Winner Elections with (Nearly) Structured Preferences
- Generative Social Choice
- Compactor: Calibrated Query-Agnostic KV Cache Compression with Approximate Leverage Scores
- Preference Restrictions in Computational Social Choice: Recent Progress
- LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding
- LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression
- Task-agnostic Prompt Compression with Context-aware Sentence Embedding and Reward-guided Task Descriptor