  We formalize the problem of prompt compression for large language models
(LLMs) and present a framework to unify token-level prompt compression methods
which create hard prompts for black-box models. We derive the distortion-rate
function for this setup as a linear program, and provide an efficient algorithm
to compute this fundamental limit via the dual of the linear program. Using the
distortion-rate function as the baseline, we study the performance of existing
compression schemes on a synthetic dataset consisting of prompts generated from
a Markov chain, natural language queries, and their respective answers. Our
empirical analysis demonstrates the criticality of query-aware prompt
compression, where the compressor has knowledge of the downstream task/query
for the black-box LLM. We show that there is a large gap between the
performance of current prompt compression methods and the optimal strategy, and
propose a query-aware, variable-rate adaptation of a prior work to close the
gap. We extend our experiments to a small natural language dataset to further
confirm our findings on our synthetic dataset.
