acceptodds
Under review as a conference paper at ICLR 2027

PC-SubMax: Efficient Prompt Compression via Regularized Submodular Maximization

Abstract

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 , where the monotone submodular utility combines information coverage, query relevance, and log-determinant diversity, and the non-negative modular penalty 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 satisfying , where is an optimal feasible solution to the regularized problem. RGM uses value-oracle queries, where is the number of candidate sentences and 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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
prompt compression, submodular optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_pCtxOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes PC-SubMax, a sentence-level prompt compression framework based on regularized submodular maximization. The method combines information coverage, semantic diversity, and query relevance with a token-cost penalty to select informative sentences under a token budget. The authors further develop a Regularized Greedy+Max (RGM) algorithm with a (1/2,1)(1/2,1) approximation guarantee and evaluate its effectiveness across seven benchmarks.

Critical strengths
  1. The paper provides a clear and well-motivated formulation of prompt compression as a regularized submodular optimization problem, explicitly considering information coverage, redundancy, and token costs.

  2. The proposed RGM algorithm offers a competitive theoretical approximation guarantee with relatively low value-oracle complexity.

  3. Extensive experiments across diverse downstream tasks demonstrate competitive compression quality and efficiency compared with existing prompt compression methods.

Critical weaknesses
  1. The proposed RGM algorithm builds upon established cost-scaled greedy selection and Greedy+Max augmentation techniques. While Theorem 2 establishes a competitive (1/2,1)(1/2,1) regularized approximation guarantee, the underlying algorithmic mechanisms closely resemble prior work. Moreover, the experiments primarily compare prompt-compression methods rather than existing submodular optimization algorithms under the same objective. Comparisons with Cost-Scaled Greedy, Greedy+Max, and PartEnum-Twin-Greedy would help clarify the specific benefits of RGM in terms of objective value, computational efficiency, and downstream performance.

  2. Multi-hop reasoning often requires multiple complementary sentences to be retained together. Although Appendix C uses beam search to identify multi-hop evidence relationships, the resulting relevance scores are fixed before subset selection. Consequently, the proposed method may select a sentence with high relevance while discarding another sentence required to complete the same evidence chain. The paper does not directly evaluate whether complete supporting evidence chains are preserved. Reporting supporting-fact recall and evidence-chain completeness on HotpotQA would help assess this limitation.

Questions for authors

See weaknesses

3 comments
AuthorsOpenReview ↗

Follow-up on Our Responses

Dear Reviewer,

Thank you again for your careful and thoughtful review. We understand that this is a busy time, and as the discussion period is coming to a close, we wanted to briefly follow up. We hope our responses have adequately addressed your questions and concerns. If our clarifications have resolved the issues you raised, we would sincerely appreciate it if you would consider revisiting your overall assessment of the paper.

We would be very happy to provide any further clarification.

Best regards

Thank you for the detailed rebuttal and additional experiments. The comparisons with existing submodular optimization algorithms substantially address my concerns.

The HotpotQA experiments also provide useful evidence that the proposed multi-hop relevance mechanism improves supporting-fact retention and evidence-chain completeness. While the fixed relevance scores still cannot explicitly model dependencies between jointly selected sentences, I acknowledge that the new results substantially strengthen the empirical support for the proposed approach.

In summary, the rebuttal addresses most of my concerns, and I am inclined to revise my rating to 3

We appreciate your recognition of our work and your valuable feedback.

Reviewer_TGGFOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes PC-SubMax, a sentence-level prompt compression method that formulates compression as regularized submodular maximization under a token-budget constraint. Its objective incorporates lexical coverage, semantic diversity, query relevance, and token cost. The authors develop the RGM algorithm and provide a corresponding regularized approximation guarantee and complexity analysis. Experiments on seven datasets report competitive downstream performance and compression efficiency.

Critical strengths
  1. The method is well motivated. Through diminishing marginal returns in the coverage and diversity terms, the method explicitly accounts for each sentence’s additional contribution relative to the already selected content, balancing coverage and redundancy under a token budget. RGM further provides a (1/2,1)(1/2,1) regularized approximation guarantee for the proposed surrogate objective, giving the sentence selection procedure a clear theoretical foundation.
  2. The experiments cover a broad range of settings and demonstrate strong performance. The evaluation spans multiple downstream task types and compression ratios, supplemented by compression-time measurements, cross-model evaluation, and component ablations. The results show that PC-SubMax achieves the best performance on multiple datasets while also offering advantages in compression time.
Critical weaknesses
  1. The selection procedure and transferability of task-specific weights are not sufficiently explained. For example, the authors specify a separate set of four hyperparameters for each of the six subtasks in LongBench. In practical applications, users may find it difficult to choose a reasonable set of hyperparameter values.
  2. The three utility components operate on different numerical scales. According to the definitions in the paper, Coverage, Diversity, and Relevance differ in numerical scale and are affected by input size. These differences directly affect how the chosen weight hyperparameters balance the contributions of the three components.
Questions for authors
  1. For each benchmark, please specify the source, sample size, and partitioning procedure of the validation data, the search spaces for the four coefficients, and the metric used to select a configuration. Please also clarify whether the evaluation samples used for the reported results are completely separate from the data used for hyperparameter tuning. In addition, are there recommended default weights or selection rules for new datasets without a dedicated validation set?
  2. Is any additional numerical scale normalization applied to the three utility components beyond what is specified in the formulas? Alternatively, could the authors provide further analysis of their numerical magnitudes to substantiate the stability of using fixed weights?
Reviewer_qGNqOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a framework called PC-SubMax, which compresses the context of large language models by sub-selecting sentences under a token budget. It considers multiple factors: coverage, relevance, and token cost. The propose solution is theoretically bounded (1/2 to 1) to optimal solution in terms of a utility function proposed by authors. Experiments show that PC-SubMax outperforms baseline methods in sentence-level context compression, while maintaining an even lower overhead.

Critical strengths
  1. The paper proposes a utility function to measure the quality of compression, and its proposed method is theoretically close to optimality.
  2. The performance over baseline methods are good in terms of both absolute performance and overhead saving.
  3. The paper is well written with clear description of methods and experiments.
  4. The experiments are well designed: Proper baselines are selected and ablation studies are included.
Critical weaknesses
  1. Like other compression work, PC-SubMax is limited in its utility. It adopts a paradigm of sentence sub-selection, which can fit the scenarios of benchmarks but might not work well in real applications, for example multi-turn conversations, coding agent, computer use agent, etc, where the user intent is unclear at the beginning and any missing contexts can be potential risk.
  2. The paper is backed by a theory, which guarantees a performance bound. However, the utility function is proposed by authors. The intuition behind each rubrics and heuristics used to measure each of them are subjective.
  3. The method relies on an external sentence embedding model, therefore the resultant LLMs are not self-contained.
Questions for authors

I am curious about table 2. PC-SubMax is faster in almost all tasks but LongBench and RULER, which are much longer than others. Does it mean that PC-SubMax has speed bottleneck in ultra-long contexts? If so, where does it come from?

Comments on the paper

1 comment

Dear Reviewers and Area Chair,

Thank you again for your careful and thoughtful review. We understand that this is a busy time, and as the discussion period is coming to a close, we wanted to briefly follow up. We hope our responses have adequately addressed your questions and concerns. If our clarifications have resolved the issues you raised, we would sincerely appreciate it if you would consider revisiting your overall assessment of the paper.

We would be very happy to provide any further clarification.

Best regards

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.