# PC-SubMax: Efficient Prompt Compression via Regularized Submodular Maximization

arXiv: https://arxiv.org/abs/2609.32474 · HTML: https://mlsanity.com/paper/2609.32474/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Prompt and context compression, one of 12 directions in Efficient LLM inference and serving.
- Builds on 27 of its 37 references that are in the map.
- First posted on arXiv 26 Sep 2026.

## Placed in

- Efficient LLM inference and serving / [Prompt and context compression](https://mlsanity.com/inference/prompt-and-context-compression/)

## Builds on (most cited first, 27 of 27)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [Large Language Models Can Be Easily Distracted by Irrelevant Context](https://mlsanity.com/paper/2302.00093/) (2023)
- [LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression](https://mlsanity.com/paper/2310.06839/) (2023)
- [Learning to Compress Prompts with Gist Tokens](https://mlsanity.com/paper/2304.08467/) (2023)
- [LLMLingua-2: Data Distillation for Efficient and Faithful Task-Agnostic Prompt Compression](https://mlsanity.com/paper/2403.12968/) (2024)
- [LLMLingua: Compressing Prompts for Accelerated Inference of Large Language Models](https://mlsanity.com/paper/2310.05736/) (2023)
- [CodeNet: A Large-Scale AI for Code Dataset for Learning a Diversity of Coding Tasks](https://mlsanity.com/paper/2105.12655/) (2021)
- [In-context Autoencoder for Context Compression in a Large Language Model](https://mlsanity.com/paper/2307.06945/) (2023)
- [Compressing Context to Enhance Inference Efficiency of Large Language Models](https://mlsanity.com/paper/2310.06201/) (2023)
- [Submodular Combinatorial Information Measures with Applications in Machine Learning](https://mlsanity.com/paper/2006.15412/) (2020)
- [Learning to Compress Prompt in Natural Language Formats](https://mlsanity.com/paper/2402.18700/) (2024)
- [Prompt Compression with Context-Aware Sentence Encoding for Fast and Improved LLM Inference](https://mlsanity.com/paper/2409.01227/) (2024)
- ["Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack](https://mlsanity.com/paper/1910.05646/) (2019)
- [COMI: Coarse-to-fine Context Compression via Marginal Information Gain](https://mlsanity.com/paper/2602.01719/) (2026)
- [Read As Human: Compressing Context via Parallelizable Close Reading and Skimming](https://mlsanity.com/paper/2602.01840/) (2026)
- [An Efficient Framework for Balancing Submodularity and Cost](https://mlsanity.com/paper/2002.07782/) (2020)
- [Parse Trees Guided LLM Prompt Compression](https://mlsanity.com/paper/2409.15395/) (2024)
- [DocSage: An Information Structuring Agent for Multi-Doc Multi-Entity Question Answering](https://mlsanity.com/paper/2603.11798/) (2026)

## Abstract (arXiv)

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)-ℓ(S), where the monotone submodular utility U 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 Q satisfying U(Q)-ℓ(Q)≥ frac12U(O)-ℓ(O), where O is an optimal feasible solution to the regularized problem. RGM uses O(nkappa) 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.