Efficient method compresses long prompts for large language models
PC-SubMax: Efficient Prompt Compression via Regularized Submodular Maximization
Computation and Language
Summary
Long prompts given to big language models can be slow and confusing because they contain too much information. The authors created a way to pick the most important sentences from a long prompt while avoiding repeating the same ideas. Their approach uses math that values coverage, relevance, and diversity, and it does this quickly without needing slow scoring from the language model itself. Tests show this method keeps performance high but runs faster when shortening prompts.
What this means in practice
- •For ai product developers: Reduce response delay by compressing long prompts before sending them to large language models in production systems.
- •For document processing teams: Shorten lengthy texts to keep key information for automated analysis without added computational overhead.
Authors
Ziyi Zhang, Shuang Cui, Haotian Zhang, Xiaoyu Wang
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 $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κ)$ value-oracle queries, where $n$ 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.