PaperlayerView exact revision on arXiv

Source-linked AI summary

PC-SubMax: Efficient Prompt Compression via Regularized Submodular Maximization

Ziyi Zhang, Shuang Cui, Haotian Zhang, Xiaoyu Wang

arXiv:2609.32474v1cs.CL

TL;DR

Long prompts raise inference cost and can challenge reasoning, while fixed importance scores may not account for redundancy among selected content. PC-SubMax uses regularized submodular sentence selection with deterministic optimization; across seven benchmarks it delivers competitive downstream performance and is fastest on four of six timing benchmarks.

  • Problem

    Fixed token- or sentence-level scores may miss how a sentence’s contribution changes after other content is selected, limiting their treatment of inter-sentence redundancy.

    Source: §1.1 · p. 2

  • Method

    PC-SubMax maximizes a coverage-, relevance-, and diversity-based monotone submodular utility minus a modular token penalty under a knapsack constraint, using deterministic RGM.

    Source: §1.1 · p. 2, §2 · p. 4, §3.1 · p. 5

  • Results

    4 of 6 timing benchmarks had PC-SubMax’s lowest measured compression time, alongside competitive downstream performance across seven benchmarks.

    Source: §5 · p. 9

  • Takeaways & Limitations

    Encoder-based compression avoids causal-language-model scoring during compression while delivering competitive results in the evaluated settings.

    Source: §1.1 · p. 2, §5 · p. 9

    The surrogate objective does not directly evaluate downstream task performance during subset selection, which would require repeated target-LLM calls and a task-specific signal.

    Source: §2 · p. 3

Abstract

from arXiv · show

While large language models (LLMs) are increasingly deployed in long-context scenarios, lengthy prompts can increase inference costs and latency and exacerbate the ``lost-in-the-middle'' phenomenon. Selective prompt compression offers a model-agnostic approach to alleviating these issues. However, methods based on fixed token- or sentence-level importance scores may overlook how content contributions change with the selected subset, limiting their ability to account for inter-sentence redundancy. Compression procedures that rely on autoregressive LLM scoring can also introduce substantial overhead. We propose PC-SubMax, a theoretically grounded framework that formulates selective prompt compression as regularized monotone submodular maximization under a knapsack constraint. The objective is $U(S)-\ell(S)$, where the monotone submodular utility $U$ combines information coverage, query relevance, and log-determinant diversity, and the non-negative modular penalty $\ell$ captures token cost. Through diminishing marginal returns, the objective evaluates each sentence's contribution relative to the selected content. To optimize this objective, we develop the Regularized Greedy+Max (RGM) algorithm, which deterministically returns a feasible set $Q$ satisfying $U(Q)-\ell(Q)\geq \frac{1}{2}U(O)-\ell(O)$, where $O$ is an optimal feasible solution to the regularized problem. RGM uses $O(n\kappa)$ value-oracle queries, where $n$ is the number of candidate sentences and $\kappa$ is the maximum feasible subset size. PC-SubMax uses encoder representations and avoids autoregressive LLM scoring during compression. Experiments across seven diverse benchmarks demonstrate competitive downstream performance with low compression overhead.

1 Introduction

Long prompts raise cost and latency and can impair reasoning, while existing selective-compression methods may miss redundancy among selected content or incur scoring overhead. PC-SubMax frames sentence selection as regularized submodular maximization and pairs a subset-aware utility with deterministic optimization and efficient scoring.

1 Introduction

  • Long prompts increase inference cost and latency, can distract models with irrelevant information, and are associated with the lost-in-the-middle phenomenon.Prompt compression includes black-box selective methods that preserve original text, unlike generative methods that rewrite it.Source: §1 · p. 1, §1.1 · pp. 1–2

1.1 Related Work

  • Fixed importance rankings do not explicitly measure a candidate’s added information after other content is retained, limiting their ability to balance coverage and redundancy.The broader selection problem also requires computationally economical subset optimization, not only importance estimates.Source: §1.1 · p. 2
  • Language-model-based compressors can require additional causal-language-model evaluations during compression, adding online overhead for long prompts.Existing selective methods also vary in whether they condition selection on a query or use task-agnostic scores.Source: §1.1 · p. 2
  • PC-SubMax models coverage, semantic diversity, and query relevance with a monotone submodular utility, then subtracts a modular token penalty under a hard budget.Coverage and diversity use diminishing marginal value to account for overlap within the selected set.Source: §1.1 · p. 2
  • RGM deterministically guarantees U(Q)−ℓ(Q) ≥ 1/2 U(O)−ℓ(O) with O(nκ) value-oracle queries, improving on PartEnum-Twin-Greedy’s stated guarantee and query complexity.RGM uses cost-scaled marginal-density selection and one-item augmentation at each greedy prefix.Source: §1.1 · p. 3
  • PC-SubMax uses pretrained sentence representations and incremental marginal evaluation, without compression-specific training or target-LLM scoring during compression.Experiments span seven benchmarks across summarization, mathematical reasoning, multi-hop question answering, and long-context understanding; compression time is lowest on four of six timed benchmarks.Source: §1.1 · p. 3

2 Problem Formulation

The formulation selects original prompt sentences within a token budget and uses an efficiently evaluable semantic surrogate rather than repeatedly evaluating downstream performance. It maximizes a regularized submodular objective over feasible subsets, with a guarantee defined relative to an optimal feasible solution.

2 Problem Formulation

  • Sentence-level selective compression chooses prompt sentences and concatenates them in original order, aiming to retain useful information within a token budget.Sentence occurrences remain distinct even if their text is identical.Source: §2 · p. 3
  • The selected subset is the optimization variable, while the prompt and associated query are fixed; downstream evaluation would require repeated target-LLM calls and a task-specific signal.The formulation therefore uses an efficiently evaluable surrogate built from coverage, semantic diversity, and query relevance.Source: §2 · p. 3
  • The objective subtracts a non-negative modular token penalty from a normalized, non-negative monotone submodular utility, while the hard budget restricts feasible subsets.Sentence costs are additive, and the coverage and diversity terms represent information overlap through diminishing marginal returns.Source: §2 · p. 3
  • An (α, 1) regularized approximation returns a feasible Q with U(Q)−ℓ(Q) ≥ αU(O)−ℓ(O), comparing its utility with an optimal feasible set while accounting for that set’s full penalty.The net objective can be non-monotone even though U is monotone; the problem class is NP-hard.Source: §2 · p. 4

3 PC-SubMax: Prompt Compression via Regularized Submodular Maximization

PC-SubMax combines coverage, diversity, and query relevance in a regularized objective, then selects sentences under a token budget with deterministic RGM. Its framework uses a submodular utility and modular token penalty, with an approximation guarantee for the selection algorithm.

3.1 Regularized Submodular Objective Construction

  • PC-SubMax maximizes a weighted coverage, diversity, and relevance utility minus a modular token penalty under a knapsack constraint.The utility is normalized, non-negative, monotone, and submodular; the regularized objective is submodular but may be non-monotone and negative.Source: §3 · p. 4, §3.1 · pp. 5–6

3.2 Sentence Selection Procedure

  • RGM deterministically returns feasible Q with U(Q)−ℓ(Q) ≥ 1/2 U(O)−ℓ(O), using O(nκ) value-oracle queries.The guarantee applies to every feasible comparator; n is the ground-set size and κ the maximum feasible cardinality.Source: §3 · p. 4, §3.2 · p. 6

3.1 Regularized Submodular Objective Construction

  • Coverage rewards newly covered prompt vocabulary, while log-determinant diversity gives diminishing reward to overlapping sentence representations.The coverage and diversity functions are each normalized, non-negative, monotone, and submodular.Source: §3.1 · p. 5
  • Query relevance complements coverage and diversity; its single-hop or multi-hop scores are fixed before subset selection and form a modular function.For multi-hop QA, bridge scores can account for evidence paths of at least two hops.Source: §3.1 · p. 5

3.2 Sentence Selection Procedure

  • RGM builds a greedy path using cost-scaled marginal gain and records the best one-item augmentation at each prefix.It uses the doubled penalty for path selection, compares candidate sets using U−ℓ, and resolves ties by sentence index in PC-SubMax.Source: §3.2 · p. 6
  • The lazy accelerated variant achieves a (1/2−ε, 1) guarantee with O((n/ε)[1 + log(B/(εcmin))]) value-oracle queries.It uses exact marginal evaluations with approximate selection rules; the empirical evaluation uses full-scan RGM.Source: §3.2 · p. 7

3.3 Computational Complexity Analysis

  • Full-scan selection work is O(nκL̄ + nκ^3), with preprocessing and dense kernel construction accounted for separately.The runtime expression includes Tprep and O(n^2d) kernel construction; under bounded sentence lengths and fixed encoder settings it simplifies to O(n^2d + nκ^3).Source: §3.3 · p. 7

4 Experiments

Across the evaluated tasks, PC-SubMax delivers strong compression quality and low compression time, with tests spanning different retention ratios, inference models, and utility-component ablations. Results include a reported quality advantage on CodeNet and GSM8K, alongside measured exceptions and task-specific comparisons.

4.1 Experimental Setup

  • The evaluation covers seven benchmarks across summarization, mathematical reasoning, multi-hop QA, and long-context understanding, using five representative compression baselines.It reports task-specific metrics, uses Qwen3-VL-32B-Instruct by default, and additionally tests Llama-3-8B-Instruct for cross-model evaluation.Source: §4.1 · p. 7, §4.2 · p. 8

4.2 Experimental Results

  • At CR=0.2, GSM8K EM exceeds PartPrompt by 3.87 percentage points; PC-SubMax has the highest reported quality scores among compared methods in Table 1.The table covers CodeNet and GSM8K at different compression ratios.Source: Table 1 · p. 8, §4.2 · p. 8
  • On Truncated ArXiv, PC-SubMax’s BLEU, ROUGE, and BERTScore increase with retention, except ROUGE-L at CR=0.3, where PartPrompt leads by 0.06 points.Figure 2 presents the compression-ratio comparison.Source: §4.2 · p. 8, Figure 2 · p. 9
  • 34.8× is the arithmetic mean of PC-SubMax’s six per-benchmark speedup ratios over PartPrompt; PC-SubMax is fastest on four of six benchmarks.LLMLingua-2 is faster on LongBench and RULER by factors of 1.7 and 1.8, respectively.Source: Table 2 · p. 9, §4.2 · p. 9
  • For Llama-3-8B-Instruct, PC-SubMax has the highest scores on all five metrics at all three ratios; for Qwen3-VL-32B-Instruct, only ROUGE-L at CR=0.3 is an exception.The comparison is on Truncated ArXiv and supports transfer across the two evaluated model families in that summarization setting.Source: §4.2 · p. 9
  • On HotpotQA, the full configuration has the highest answer F1 at every ratio, and removing relevance reduces F1 most: 22.09, 31.36, and 30.89 points.The ablation holds λtok=0.05 fixed; removing coverage reduces F1 by 1.50–6.09 points and removing diversity by 0.64–4.65 points.Source: §4.2 · p. 9

5 Conclusion

PC-SubMax formulates sentence-level compression as regularized submodular maximization and reports competitive performance across seven benchmarks with the lowest measured compression time on four of six timing benchmarks. The appendix situates it among prompt-compression methods and related submodular optimization guarantees.

5 Conclusion

  • PC-SubMax balances lexical coverage, embedding diversity, and query relevance against token cost, with deterministic RGM and lazy-RGM approximation guarantees.Full-scan RGM uses O(nκ) value-oracle queries; future work targets broader relevance representations and lower dense-kernel and diversity-marginal costs.Source: §5 · p. 9

A.1 Prompt Compression Techniques

  • Prompt compressors include model-dependent white-box methods and text-interface-compatible black-box methods, with selective methods retaining source content and generative methods rewriting it.Rewriting can change factual details, whereas extraction preserves retained wording.Source: §A.1 · p. 13

A.2 Submodular Optimization

  • Related selective methods use token scores, hierarchical pruning, learned policies, or query-aware relevance scores, while submodular optimization offers diminishing returns for subset selection.Prior regularized methods have different approximation guarantees; RGM guarantees (1/2, 1) for arbitrary non-negative modular penalties and independent positive knapsack weights.Source: §A.1 · p. 13, §A.2 · p. 13

B Additional Experimental Results

The appendix gathers additional benchmark results, cross-model comparisons, and ablations. Task-specific objective weights are held constant across reported compression ratios, with relevance treatment differing by task type.

B Additional Experimental Results

  • Additional experiments cover task-specific weights, long-context tasks, further summarization and QA results, cross-model comparisons, and semantic-component ablations.The appendix identifies these as additions to the main evaluation.Source: B Additional Experimental Results · p. 14

B.1 Weight Configuration

  • Each dataset or task type uses the same listed objective weights across reported compression ratios.Table 3 lists coefficients for the three utility components and token penalty.Source: §B.1 · p. 14, Table 3 · p. 14
  • Summarization configurations set λrel to 0, whereas question-answering configurations place greater weight on relevance.Source: §B.1 · p. 14

B.2 Extended Summarization Benchmarks

The extended benchmarks report strong PC-SubMax results on Truncated ArXiv and People Daily, with a HotpotQA result that leads all evaluated compression ratios. The reported exception on People Daily is a narrow BLEU comparison at one ratio.

B.2 Extended Summarization Benchmarks

  • On Truncated ArXiv, PC-SubMax achieves the best result on every reported metric except ROUGE-L at CR=0.3, where PartPrompt is ahead by 0.06 points.Source: §B.2 · p. 14
  • PC-SubMax has the highest reported ROUGE and BERTScore at all People Daily target ratios, and the highest BLEU except at CR=0.3.At CR=0.3, LLMLingua-2 leads BLEU by 0.13 points; People Daily provides a Chinese-language summarization setting.Source: §B.2 · p. 14, Table 5 · p. 15

B.3 Performance on HotpotQA

  • Answer F1 is 56.43 at CR=0.2, exceeding LLMLingua-2 by 1.47 points and PartPrompt by 12.03 points, with 279.82 average tokens.The configuration uses precomputed multi-hop relevance scores.Source: §B.3 · p. 15, Table 6 · p. 15

B.4 Long-Context Understanding Tasks

At a target retention ratio of 0.2, PC-SubMax exceeds PartPrompt on the reported LongBench aggregate and has a slightly higher RULER score. Across two evaluated inference models, it leads nearly all tested Truncated ArXiv settings.

B.4 Long-Context Understanding Tasks

  • LongBench aggregate score is 40.86 for PC-SubMax versus 28.05 for PartPrompt, while RULER scores are 97.2 versus 96.0.The comparisons use the same target retention ratio of 0.2.Source: §B.4 · p. 16, Table 7 · p. 16
  • Selective-Context, LLMLingua, and LongLLMLingua were excluded because input-length constraints prevented same-setting LongBench and RULER comparisons.Source: §B.4 · p. 16

B.5 Using Different LLMs for Inference

  • Across Qwen3-VL-32B-Instruct and Llama-3-8B-Instruct, PC-SubMax leads every tested setting except Qwen3-VL ROUGE-L at the 30% constraint, where PartPrompt is ahead by 0.06 points.The transfer comparison uses the Truncated ArXiv dataset.Source: §B.5 · p. 16, Table 8 · p. 16

B.6 Ablation Study on HotpotQA

On HotpotQA, the full semantic-utility configuration achieves the highest answer F1 at all target ratios, with relevance ablations causing the largest drops. The appendix also details how multi-hop relevance scores candidate sentences using evidence paths and conditional gains.

B.6 Ablation Study on HotpotQA

  • The full configuration has the highest answer F1 at all three HotpotQA target ratios, and removing relevance reduces it by 22.09, 31.36, and 30.89 points.Removing coverage reduces answer F1 by 1.88, 6.09, and 1.50 points, while removing diversity reduces it by 0.64, 4.65, and 0.90 points.Source: §B.6 · p. 17, Table 9 · p. 17

C Details of the Multi-Hop Relevance Construction

D Omitted Proofs for Section 3

The omitted proofs establish the required properties of the utility components and analyze RGM's regularized objective. They show a deterministic approximation guarantee for feasible sets and bound the algorithm's value-oracle query count.

  • Coverage and log-determinant diversity are normalized, non-negative, monotone submodular functions, with diminishing marginal gains as the selected set grows.Source: D Omitted Proofs for Section 3 · p. 18
  • Fixed non-negative relevance scores and token prices are modular, so the combined utility is normalized and submodular, while subtracting token cost need not preserve monotonicity.Source: D Omitted Proofs for Section 3 · p. 18
  • RGM uses cost-scaled marginal-density selection with one-item augmentation and returns a feasible Q satisfying U(Q)−ℓ(Q) ≥ 1/2 U(O)−ℓ(O) for every feasible comparator O.Source: D Omitted Proofs for Section 3 · pp. 18–19
  • RGM makes O(nκ) value-oracle queries because it scans at most n candidates at each of at most κ prefixes.Source: D Omitted Proofs for Section 3 · p. 19

E A lazy accelerated implementation of RGM

The lazy implementation accelerates RGM by replacing exhaustive selection scans with approximate selectors while retaining exact marginal evaluations. Its query-complexity trade-off depends on ε, and the reported experiments evaluate the full-scan solver.

  • Approximate lazy selectors replace exhaustive scans, but marginal evaluations remain exact and ε controls selection-rule accuracy.Source: E A lazy accelerated implementation of… · p. 20
  • Separate persistent queues select augmentation candidates by positive regularized marginal and path items by positive distorted marginal density.A candidate discarded for low path density remains eligible for augmentation because its regularized marginal may still be positive.Source: E A lazy accelerated implementation of… · p. 20
  • The accelerated bound replaces the κ factor with ε^-1[1 + log(B/(εcmin))], trading a lower utility coefficient for reduced query complexity when that factor is smaller.Source: E A lazy accelerated implementation of… · p. 22
  • The accelerated guarantee is analyzed theoretically, while the reported experiments use full-scan RGM.Total implementation cost also includes preprocessing, marginal evaluation, and priority-queue operations.Source: E A lazy accelerated implementation of… · p. 22

F Detailed Computational Complexity Analysis

The complexity analysis separates preprocessing, per-candidate marginal evaluation, and total selection cost. Under stated implementation conditions, it gives an overall runtime bound and describes the dense implementation's scaling and a lower-memory alternative.

F.1 Preprocessing Stage

  • Preprocessing includes text processing, sentence and query encoding, O(nd) bookkeeping, and multi-hop relevance computation; including dense-kernel construction adds O(n^2d).Source: §F.1 · p. 23

F.2 Selection Stage: Per-Query Oracle Cost

  • At prefix size j, an exact marginal evaluation costs O(1 + |We| + j^2), combining coverage, diversity, and constant-time relevance and token-price terms.Source: §F.2 · pp. 23–24

F.3 Total Selection Cost

  • The total selection-cost bound is O(n + nL̄ + nj^2), with coverage and factor updates, feasibility checks, and bookkeeping included.Source: §F.3 · p. 24

F.4 Overall Complexity

  • With bounded sentence lengths and fixed encoder configuration, input limits, hop limit, and beam width, overall runtime simplifies to O(n^2d + nκ^3).Source: §F.4 · p. 25
  • When κ=Θ(n), the dense triangular-solve implementation has an O(n^4) selection upper bound and auxiliary storage O(n^2 + nd + nL̄ + κ^2), excluding raw text and encoder state.An exact embedding-space representation can avoid storing the dense n×n kernel when the candidate set is large relative to d.Source: §F.4 · p. 25

Related papers

Loading 2609.32474v1…