Fundamental Limits of Prompt Compression: A Rate-Distortion Framework for Black-Box Language Models
Authors: Alliot Nagle
Adway Girish
Marco Bondaschi
Michael Gastpar
Ashok Vardhan Makkuva
Hyeji Kim
Venue: NeurIPS 2024 poster (2024)
Keywords: information theory
prompt compression
LLMs
optimization
Primary area: other
TL;DR: We formalize and study fundamental limits of prompt compression for large language models via a rate-distortion framework.

Abstract: 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 Adaptive QuerySelect, 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.

Fundamental Limits of Prompt Compression: A Rate- Distortion Framework for Black-Box Language Models
Alliot Nagle" UT Austin
Adway Girish' EPFL
Marco Bondaschi EPFL
Michael Gastpar EPFL
Ashok Vardhan Makkuva
Hyeji Kim
EPFL
UT Austin
Abstract
We formalize the problem of prompt compression for large language models (LLMs) and present 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 linear program, and provide efficient algorithm to compute this fundamental limit via the dual the linear program. Using the distortion-rat ratt function the baseline, we study the performance of existing compression schemes on a synthetic dataset consisting of prompts generated from 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 prompt compression methods and the optimal strategy, and propose Adaptive QuerySelect, a query-aware, variable-rate adaptation of a prior work to close the gap. We extend experiments small natural language dataset further confirm our findings on our synthetic dataset.
current
Introduction
In spite of the recent success of transformer-based [1] large language models (LLMs) in language modeling tasks, inference calls transformer can be costly in both time and memory usage. Although significant progress has been made to improve the memory usage and runtime efficiency via implementation-Ieve optimizations [2, 3, 4] and architecture-level optimizations and alternatives [5, 6, 7J, a third type of optimization that compresses the input (an input-level optimization) has the benefit that it directly reduces the resource usage of an LLM inference call, and can used in conjunction with the other two types of optimizations for further efficiency gains. In this work, offer a framework and analysis for a recent body of literature in this direction, known as prompt compression [8, 9, 10].
The goal of prompt compression method is transform a sequence input tokens x into a shorter sequence of tokens m such that the response generated by target L.M will semantically mean the same thing regardless of whether x or m is given as input. Using m as the input directly decreases the memory and runtime requirements necessary for an L.M inference call. Moreover, the additional benefits to this approach are: (1) redundant or superfluous tokens are removed, making room to fit more pertinent information in the target LLM's 's limited-size context window, (2) it can be used in addition to implementation and architecture-levll optimizations to get further efficiency gains, and (3) is the only technique available when seeking to lower costs for black-box API calls to closed-source
Equal contribution. 'Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Log loss
0/1 loss
0.5
Selective [11]
LLMLingua [12]
Avectge distorrion
0.4
LLMLingua Query [13)
LLMLLiguu-2 [14]
0.3-
QuerySelect
Adaptive QuerySelect
0.2-
Optirul [Qunry-agnnetic]
Optinaal (Qunry-awne))
6.1
No Compression
0.0
0.0
Average rate E
Average rate
Figure 1: The distortion-rate trade-off of all prompt compression methods compared to the query- aware and query-agnostic theoretical limits on a synthetic dataset with binary prompts. All distortions computed with the log loss (left) and 0/1 loss (right) distortion metrics formally defined in (1). We observe that (1) most existing methods are far from the theoretical limit, suggesting that there still room for improvement in this field, (2) conditioning on the query allows for a significant improvement, as seen by the performance of the query-aware method QuerySelect against the query- agnostic L.LMMingua22 [14], and (3) our proposed method Adaptive QuerySelect, query-aware and variable-rate adaptation of LLMLingua-2, achieves the best performance among all methods considered, and the only method outperform the optimal query- strategy.
models. This third point is particularly important, since the associated cost for a black-box API model inference call, from the perspective of the caller, is determined by the runtime and the number of input tokens, both which can be reduced with prompt compression. In our framework and analysis, we focus on the prompt compression for black-box models setting, where the output of prompt compression method a set of tokens ("hard prompts") [11, 12, 13, 14], and exclude methods which output embedding vectors ("soft prompts") [15, 16, 17] as those are not transferable to black-bos models.
Despite the progress in the prompt compression literature, there a lack of proper formalization of this problem and there is no clear framework to unify these works. Most works propose methods that work well but offer no insight into key questions, such as "How far are we from the theoretical limit of the rute-distortion trade-off?", "How essential is the conditioning on the query when compressing the prompt?", and "How does tokenization impact the performance of prompi compression methods?" ? We offer unifying framework for the problem of prompt compression and seek to answer these questions with theory and experiments. Our main contributions can be summarized as follows.
1. Theoretical analysis: We formalize the problem of prompt compression and formulate it as a ditt-iistotion problem (Sec. 3.1). We characterize the optimal trade-off between the rate of compression and the distortion incurred, i.e., the distortion-rate function, via a dual linear program, and provide a geometric algorithm compute this optimal trade-off (Sec. 3.2, Sec. 3.3).
2. Evaluation: We introduce synthetic dataset with binary prompts and natural language queries, for which we can compute the Distortion-rate function (Sec. 4. and compare and obtain insights on existing prompt compression algorithms as Fig. 1 (Sec. 4.2).. We further confirm our findings by extending our experiments to a small natural language dataset and NarrativeQA [18].
3. Algorithm design: Our novel method, "Adaptive QuerySelect," a query-aware, variable-rate adaptation of LLMMinnua-22 [14], outperforms all prompt compression methods on our datasets and has a rate-distortion curve that significantly reduces the gap with the theoretical limit (Sec. 4).
2 Background and related works
Long prompts slow the inference process due to the increase in the number of tokens for the LLM to process. It also known that very long prompts can cause LLMs to "forget" parts of the input and produce erroneous answers [19]. Therefore, studying how these prompts can be compressed essential. As shown in Fig. 2. we wish to design a compressor that, upon receiving the prompt, produces "compressed" version (which has fewer tokens than the prompt) called the compressed

---

Compressed prompt (qucry-agnoatic)
Prompt
best times warst, age wisdom epoch helief incredul, scason light dark. hope despair.
was the best of times, it was the soors! of times,
the age of wisdom, it the age of fooliatiness it was the epochi of belied, was the epuch incredulity, was the season of light, it was the season of darkness, was the spring hope, it the winter deespiing
comp
m
LLM
Py OLLM(m, g)
q
(b) Query-agnosti prompt compression
LLM PY-
ØLLM (3.
Compressed prompt (query-aware)
Output
worst.
worst. (60%)
Query
Contrasting.
Mixed.
(20%)
(10%)
comp
LLM
Py OLLM(MM q)
How the times?
Dunlistic.
(5%)
q
(a) Black-box LLM without prompt compression.
(c) Quere- prompt compression
Figure 2: Model for prompt compression in LLMs. (a): Without prompt compression, the LLM takes a long Prompt and Query as input, and produces an Output distribution. (b) and (c): The prompt is passed through compressor obtain a shorter Compressed prompt and the LLM takes this compressed prompt and query as input instead. (b) The compressor does not have access to the query, and preserves all highlighted tokens. (c) The compressor has access to the query, and preserves only the tokens highlighted in orange.
prompt, such that target LLM is able to give answers that are "close enough," per some appropriately chosen metric, to the ground truth. Though similar in spirit to text summarization, prompt compression has the advantage that the compressed prompt not required to be human-readable.
prompt compression methods belong to one of two groups: those that compress the prompt into soft prompts and those that compress the prompt into hard prompts. In soft-prompt compression, the compressor is trained to transform the input prompt into a set of embedding vectors (sometimes referred to "soft tokens") that do not map back into the token space. These methods, including Gist Tokens [15], AutoCompressor [17], and In- In-Context Auto-Encode [16] are trained end-to-end and require specialized fine-tuning of the target LLM to interpret the soft prompt inputs.
In this work, we focus instead on methods that compress the prompt into hard prompts, where the compressor's 's output is set of tokens. While it is technically feasible to fine-tune the target LLM in this setting, prompts for black-box models that are not fine-tuned. These methods often use either the target LLM,, or a smaller and faster I.I.M, to compress the prompt. The basic idea behind all these methods is to identify the tokens that are "most relevant," per an appropriate metric, and retain many of them in the compressed prompt as possible. These methods include Selective Context [11], LLMLingua [12], LLMLingua-2 [14], and LongLLMLingua [13]. More details on these works can be found in Sec. 4.2. Precursors to the prompt compression works include text compression methods, which have the added constraint that the compressed text is human-readable [20, 21, 22]. Prompt compression methods different from these in that the text only needs to be interpretable by the target LLM, not by a human.
unnecessary and often avoided because the utility of this setting is compressing
We offer framework for in addition to the compressed prompt during the target I.IM inference call. Functionally, this the most useful interpretation of prompt compression since it clarifies that the goal is to compress the prompt for a given query/task. This setting is also used in the LLMLingua and LongLLMLingun works, and is more general than the setting where query is used (the query can then be empty).
compression methods where we assume that query is provided
Distortion-rate function for prompt compression
We first formalize the problem prompt compression, and then develop a rate-distortion framework to study its fundamental limits. In particular, we define and characterize the distortion-rate function, which describes the optimal trade-off between how much and how well the prompt compressed. complete overview of the notation can be found in App. A.
3

---

3.1 A formal model for prompt compression
Black-box LLM. As depicted in Fig. 2a, we assume that we have a pretrained LLM which takes a pair of the prompr z E V** and the query q E V"v, (z, q) E V* as inputs, where V refers to the vocabulary of the LLM (i.e., the set of all tokens), and ny and ny are the lengths of the prompt and query respectively. The oulput of the L.M is given by Py = @LLM (Ir, q), where dhLMM V - (V*)) a deterministic function which maps sequence of tokens to probability distribution on sequences of tokens. We denote the set of all prompts x by X' and the set of all queries q by Q. Clearly, they are both equal to V", but this notation is useful in the subsequent discussion. We model prompt-query pairs (X, Q) as random variables drawn according to the joint distribution PxQ= E P x Q).
In cases where we have a correct answer y E y = V corresponding to the pair (Ir, g). we characterize the "closeness" of the LLM output Py ΦLLM q) to the answer using a distortion measure d ()) + [0, oo]. Two possible choices of d are the log loss dlog and the 0/1 loss do/1, given by
1 Pv(()
and do/I(u. Pv.) = 1/v o arginax Py Pr(
dlog (v, py)) log
(1)
These are respectively the cross-entropy loss between the distributions by and Py. and the pre- diction error. When dealing with natural language queries, a semantic distortion metric such as Rougel. [23] or BertScore [24] is more appropriate. Additionally, there is no single answer that is uniquely correct. To account for this variability in what qualifies as correct answer, we model the answer as a random variable Y drawn from the distribution Prixo 9). which depends on the prompt æ and query q. This induces the joint distribution Pxœr P PxoPra Priqq. We charac- terize the "closeness" between the correct answer and the LLM output by the average distortion, given by (y>-rixx((1aa))) [d(Y, (LL 4))] With = djog: this is the cross-entropy loss between Py)xe( (-12; 9) and Py = (LLM(1 g). and with d = do/1, this is the prediction error probability.
Prompt compression. As described in Sec. 2, we consider two types of prompt compression: query-agnostic and query-aware. Fig. 2b depicts the query-agnostic version, where the goal is to design compressor denoted by comp all compressed prompts. The compressor takes in the prompt X ~ Px and produces a compressed prompt M comp(X) (X) with len(M) len (X) Then, the user replaces X with the compressed prompt M and provides the LLM with the input (M, Q): resulting in the output distribution Py = ØLLM (M, Q). To quantify the performance of this compressor comp, two quantities are of interest:
possibly random function from X' to M, i.e. the set of
len(M) [en(X} to measure how much the prompt is compressed, and (2) the distortion E [Y,Y, (L,, Q) to measure how well the prompt is compressed,
(1) the rate E
with both expectations taken with respect to (w.r.t.) PMXQY. If we compress to low rate, the compressed prompt m may not retain the information in x that is necessary for the query q, leading to an output ΦLLM (m, q) that is different from (-)x q) and hence, high distortion. Thus, there a trade-off between these quantities, which we formalize as the distortion-rate function in Sec. 3.2.
We can also model query-aware prompt compression similarly, with the difference being that the compressor also has access to the query q Q, as shown in Fig. 2c. In addition to the average rate and distortion computed over all queries, it is also interesting to consider the rate and distortion for each query. To simplify the presentation, we restrict our discussion here to the query-agnostic setting, and only briefly mention the analogous definitions and results for the query-aware setting. A complete development of the qwere- setting can be found in App. B.
3.2 Rate-distortion formulation for prompt compression
Distortion-rale -ate function D*) The distortion- function for any compression problem char- acterizes the fundamental trade-off between the distortion and the rate [25, 24, 26, 27]. We say that the pair (R, D) is achievable if there exists a compressor with rate at most R and distortion at most D. For given rate R. the distortion-rate function D* ((RR is the smallest distortion that can be achieved by a compressor with rate at most R. Formally, it is defined as
DR( 2 inf (D D 2 0 (R, D) is achievable}
D 0| there exists compressor with rate R and distortion S D}. (2)

---

We are now ready to characterize the distortion-rate function for prompt compression.
D (R) for query-agnostic prompt compression. Recall that our quantities of interest are the rate
E
lent M) and the distortion E (LMM Q)) with both expectations taken w.r.t PMXQY, [e
where M comp(X) X) for random function comp. By the functional representation lemma [27, 28], random function from to M is equivalent to a conditional distribution P Thus, we can equivalently model the compressor conditional distribution P PM X. and (2) is explicitly written as
(R)
inf
E [d((, ØLLM (M, Q))]
Parx
s.t.
Parix is compressor, and
Men(M)
E
S R.
len
with both expectations taken w.r.t. the joint distribution PaXQY P M PxQy induced by the
compressor PM x The constraint "P MMxx x is compressor" is short for the following requirements: (1) it is conditional distribution, i... for each E X, Emem MM
1, (2) len(m) len(x)) This
then PM (m[z) O, and (3) if len(m) len(r)), then X x (m|z) = O unless
means that the compressor either strictly reduces the length of the prompt or does no compression and retains the original prompt.
Note that all of the expressions in the objective and the constraints in (3) are linear in Parxx- Hence, the optimization problem is simply a linear program (LP), which is simple from an optimization perspective [29, 30]. However, the dimensions of this problem are still large and solving the LP directly quickly becomes infeasible as the lengths of the prompts increase. In Sec. 3.3, we deal with this optimization problem directly, and show that the dual of the LP provides an exact, practically realizable solution.
The extension the query-aware setting is straightforward; then have query query-dependent (or conditional) distortion-rate functions ( for each y E Q, and an average distortion-rate function, denoted by D' (R). Refer to App. B for an explicit characterization of D R) and D* (R)
Connections to information-theoreti setups. We provide brief overview of rate-distortion theory from the information theory literature in App. D and describe how our model compares, In particular, we note that our model for prompt compression closely resembles the setup compression with side- infoimformttton for function computation [31. 32, 33, 34], where both the encoder and the decoder are part of the system design. More recently, there has also been growing interest in computing the distortion-rate functions of these classical setups for real-world datasets [35, 36, 37]. However, our model for prompt compression, only the encoder (which the compressor) can be designed, hence our model is one of compression for fixed decoder. Such model has not been actively studied the information theory literature before, but in the next subsection, we show that the distortion-rate function can be written as explicit LP in terms of this fixed decoder.
3.3 Linear program formulation of the distortion-rate function
Having expressed the distortion-rate function for prompt compression an LP, now look solve this LP. We first rewrite (3) as an explicit LP using cilmiization-thooree notation, and hide the probabilistic notation involving expectations and conditional probabilities the parameters of the LP. Refer to App. A for an overview of the notation.
Proposition 1 (Primal LP). The distortion-rate function for query-agnostic prompt compression (3) is given by the solution to the linear program
(R)
inf
D
Zx
(#LER
)
BEA
(LP)
1 1T2 1, V ER
S.t.
#EX
where for each E X. M2 denotes the set compressed prompts associated to x, i.e., the of all possible token sequences of length smaller than len(x), the vectors 2₂ BiMe are the optimization
5

---

variables and the constants Dz, Rs E ER with components indexed by m E
MM are given by
len (m)
Dam - Px(x) E [d(Y, (LLM(M, Q)) and Rum & (x(
m E MM
(4)
len(x))
with the expectation taken with respect to PQ (m,)),
Proof. This follows immediately from (3) by defining the constants Dz, Rug R for each
x E X as given in (4), and taking 2e to be P PM|x x x-1z). We use the fact that P P (m (z) = when
len (m) > len(2) a) to reduce the dimension of 2e from .M to MM to obtain (LP).
For our experimental setup in Sec. 4.2, we see that dimension of the LP is too large to solve (LP)
directly using off-the-shelf solvers. Fortunately, the dual of the LP can be written more concisely, and can also be solved using a relatively simple algorithm.
Theorem (Dual LP). The distortion-rat ratte function for query-agnostic prompt compression (3) is given by the solution to the dual of the linear program (LP), i.e.,
(R) = =sup X20
AR
Σ DEX
min MEM.
[Da.m + ARr.m)
(dual-LPP)
Proof sketch. This follows by taking the dual [29] of the LP (LP) and simplifying the resulting expression. For a complete proof, refer to App. C.I.
Algorithm to solve (dual-LP). While the optimization prob- lem in (dual-LP) seems difficult to solve, with its max-min structure and the supremum over continuous variable, it pro- vides a neat geometric interpretation which allows for a com- putationally simple algorithm given in Algorithm 1. It takes as input R. (Dz)rgx (R and returns as output the distortion-rate function R, i.e. (R). In App. C.2, we prove that the output is indeed (R), and provide a step-by- step illustration of the algorithm on an artificial example. A
Dam
0.4
0.3 m
0.2
high-level description of the algorithm is given below.
0.1
0.2
0.3
0.4
R
Before presenting the algorithm, it is useful to define the fol- lowing geometric object. The lower-left convex envelope of a set of points in R. is the largest convex function that lies below and to the left of the points, as shown in Fig. 3 for the points {RR D2.m)) meM, for a fixed x E X. Let kn be the number of points on this envelope, then these ki points are exactly the minimizers of minmeM. [Da.m + >R for some À 2 0. Solving this inner minimization problem of (dual-LPP) is thus easy, and amounts to simply finding the points labelled as "m (a))* on the lower-left convex envelope, ordered from left to right, as done in Lines 3-4 of Algorithm Let the magnitudes of slopes of the line segments on the envelope be given by the (x()"" terms in decreasing order (Lines 5-6). Also letting (a) = + and (2) = O, observe that ke
Figure 3: Lower-left convex enve-
lope for an example with [Mgl = 11, k2 = 3.
for i = 1,..., m; (a) minimizes Da,m ARRr over m for À E [A[e) (())) Importantly, it is enough to consider just these sequences (#)" and "X(=)" sequences computed for all x E X (Lines 2-6) to solve (dual-LP), instead of the entire set My and the continuum of all positive real numbers X respectively. This makes the problem tractable even for large values of [.M.].
The rest of the algorithm computes the outer supremum. Lines 7-9 prepare for this by introducing new notation "m (1)" and "X" such that for X E [X, 71-))))) m..) minimizes Dr.m + ARR.,m over m E M2. There is no calculation involved in this step; what we gain is that the range of À on which (xx)
the minimizer is m no longer depends on x. This gives everything we need to compute the distortion-rate function, which is obtained by lines 10-13. Observe that the input R is only used for lines 10-13, for a given dataset, lines 1-9 can be run once and the results (x)"" and "X" stored, with only lines 10-13 run for each value of R.
We derive a similar dual LP formulation of the query-aware distortion-rate functions in App. B. In fact, we see that both the conditional and average distortion-rate functions are of the same form as (dual-LPP, with different parameters. Hence, Algorithm 1 can compute all of the distortion-rate functions that we have defined, namely the query-agnostic and query-aware (conditional and average) distortion-rai rate functions.

---

Algorithm 1: To compute the distortion-rate function via the dual linear program (dual-LP)
Input: R, (Dz) (Rx)aexi
Output: D" (R), the distortion-rate function at rate R:
for E X do
Find Men C Ma such that {(Rr,,; D2,m)) meM mem are on the lower-left convex boundary of
{RRam. D2,m) m, ;
see Fig. for example
(m) m2 m k2
(w) (x)
(x)
Men' ordered such that R
a,m
(=)
R (2)
2,m,
D x,m (1) -
D
for i I,..., his do (r)
f
x)) t to0; 1 + A + {
(1) ,1 ...., ,...,,, k, ks
(z)
(2)
D (x) > > 1
7 No....,Axe! + Usex A with to0 = to > to >... > Ax-1 >>> Ax =
bk ki E
8 for x E X do
for j = L...., k do Find E (L. (x/1), (1())=1) 2 (īz,
set m. + m(m)
for j = l.....k do
EzEx R a, > R then X3 t ---=1 else X3 t Xy;
11
Dj - -2, ΣxEx D Pammjo + Xg R J.m
12
13
Return maxj=1..... Dj;
== (*)
4 Experiments
The distortion-rate function defined in Sec. describes the best possible trade-off between the achievable values of rate and distortion in the query-aware and query-agnostic cases. In this section, we compare the performance of existing prompt compression methods (that are compatible with the black-box model setting we consider here) with the optimal curve for synthetic dataset. We observe that there a sizeable gap between the performance of existing methods and the optimal curve. We propose Adaptive QuerySelect, query-aware and variable-rate adaptation of LLMLingua-2 [14], that outperforms the existing methods on this synthetic dataset. We also consider a query-aware version of LLMLingua-2 called QuerySelect and observe that it outperforms the query-agnostic version, which highlights the importance of conditioning on the query.
We include an ablation study on the impact of tokenization of the prompt compression problem, as tokenization is lossy since groups together multiple symbols into a single symbol before passing to an LLM. We study the effect of tokenization on the prompt compression problem by forcing the tokenizer on the encoder and decoder side to tokenize the bits of the binary string prompts in our dataset individually, which we refer to as "forced tokenization." We run experiments in this setting and with the regular "standard tokenization." " Additional details on our experiments can be found in App. F. Our code is made available for reproducibility purposes.?
4.1 Experimental setup
Dataset. In order to run experiments that are computationally tractable but still meaningful the prompt compression problem, we construct a synthetic dataset {(2,, q:. y4) 3,) with (1) prompts I; being sequences from V = {0. 13, i.e., binary prompts, (2) natural language queries 9i, such as "Count the number of 1s," "Compute the parity," and "Is the binary string palindrome?" and (3) their associated answers yt- total, we construct dataset of seven queries; complete specification of the dataset, including few examples is available in App. F.2. The binary prompts are generated from a first-order Markov chain on (0, 1} with a 0.1 probability of transitioning and 0.9 probability of remaining in the same state, and the minimum and maximum possible lengths for each prompt are four and ten, respectively. All methods are evaluated on a validation set of I 1400 examples in total (7 queries, 200 examples per query). The optimal distortion-rate function is computed using Algorithm 1,
Our code is available at https: /gtbtttttbbu..g com/ hta///acaall///uuumnntaaaa aawetdaameettl-lieee al-limits
7

---

taking P. PxQr to be the empirical distribution on the dataset, i.e., PXQY= = the natural choice when the true distribution is unknown. Another choice is a parametric model with parameters learned from a dataset, but it is unclear what is an appropriate model in this case.
E (...)))))) This
We also run experiments on small natural language dataset curated with GPT-4 [38] and NarrativeQA [18] for a large-scale experiment. The small dataset consists of ten prompts with four queries each, and few examples are provided in Table in App. F.2.1. More details on the considerations made in constructing our datasets are provided in App. E.
Baseline methods. We compare the rate-distortion trade-off of the optimal strategy (both query- aware and query-agnostic) with prompt compression methods that can be used to compress prompts for a black-box target LLM: Selective Context [11], LLMLingua [12], LLMLingua Query [13], LLMLingua-2 [14]. As such, we do not consider methods like Gist Tokens [15]. In in-Context Autoen-
coder [16], and AutoCompressor [17] since they require special training methods generally not com- patible with black-box target LLMs. Selective Context uses log P(z; Zo, 0i,.... 11) to score the i-th token, and retains the tokens whose score is larger than the p-percentile, where p E [0, 1] is the ratio parameter. .M.ngn uses a similar method, but they first partition the input prompt into segments and condition on previously compressed segments to compress the current segment. They later extended their method to perform query-aware compression, which is what we use for LLMLin- gua Query. While these methods use a decoder-style (causal) transformer LLM to do prompt com- pression, this approach makes an independence assumption on the influence of future tokens have on the i-th token. LLMLingua-2 instead uses an encoder-style (bidirectional) LLM to perform a token classification task, where their model predicts whether a given token should be kept or removed.
Our proposed methods. We add two novel contributions over the LLMLingua-2 work: (1) adapt LLMLing to the query-aware setting, whereas the original work only proposed the query- agnostic approach, which call "QuerySelect," and (2) we further adapt this query-aware approach into a variable-rate approach we refer to as "Adaptive QuerySelect." This approach lets the encoder model decide which tokens to keep based on the confidence over a specified threshold. In other words, LLMLingua-2 and QuerySelect accept a rate parameter to determine the compression ratio, but Adaptive QuerySelect replaces the rate parameter with a threshold parameter. The encoder model predicts the probability of keeping particular token, and the token is kept if the predicted probability is above the threshold, resulting in a variable-rate compression of the prompt. Variable- rate compression is important as some prompts are more compressible than others, and vice versa.
Models. We use Mistral 7B Instruct v0.2 [39] as our black-box target LLM, which is fine-tuned on the training set partition of our synthetic dataset. This model is fixed after fine-tuning and no prompt compression methods have access to any part of it. All prompt compression methods use an LLM as part of their compression algorithm; we use deduplicated Pythia IB [40] for Selective Context, LLMLingua, and LLMLingua Query and RoBERTa Base [41] for LLMLingua-2-ban
methods. For each method, we finetune on the training set partition to enable the best performance possible for that method. More information on how we trained these methods and the data we used is in App. F. For all models. including the target LLM, we tne-tune with LoRA [42] and conduct hyperparameter grid search. We choose the configuration with the best performance on a test set that is different from the validation set. More details on the hyperparameter search are provided in App. F.3.
For the natural language dataset, no fine-tuning is necessary on the decoder side. On the encoder side, Selective Context, LLMLingua, and LLMLingua Query use the same model as on the decoder side, and LLMLingua-2 uses a specially fine-tuned version of XLM RoBERTa Large [43, 14]. We use custom fine-tuned XLM RoBERTa Large model as the encoder for the QuerySelect and Adaptive QuerySelect methods. The training dataset of (prompt, query, answer) tuples used train this custom model is filtered from the Databricks Dolly 15k [44] dataset to only include examples with prompt lengths between a specified minimum and maximum length (see Sec. F.3.2 for details).
4.2 Results
Fig. summarizes our experimental contributions on the synthetic dataset. We observe a large gup between the optimal curve and existing prompt compression methods. Thus, we propose QuerySelect as a query-aware and Adaptive QuerySelect as query-aware, variable-rute modification of .ingua to close this gap. Our results show that Adaptive QuerySelect achieves the best performance and, in fact, is the only method to outperform the optimal aggrstig strategy. We
8

---

also note that the optimal distortion-rate curves eventually fall below the baseline performance of using the full prompt (no compression). This observation especially interesting because it shows that compressing prompts can improve performance on downstream tasks, as observed on natural language datasets in previous prompt compression works [12, 13, 14]. We accredit the performance of Adaptive QuerySelect to variable-rate compression, where we allow the compressor to choose how much it should compress based on the query and prompt as input (see App. B, Remark for formal explanation of variable-rate compression). Even though this approach relinquishes explicit control over the rate, our experiments show that variable-rate compression is the closest to optimality.
Is the binary string paliudrome?
Count the number of transitions from to 1 and to O.
0.5
Average distortion (0/1 loos)
0.20
Selective [11]
LLMLingua [12]
0.15
LLMLingu Query [18
0.3
LLMLingua- [14]
QuerySelect
0.30
0.2
Adaptive QuerySelect
Optimal (Query-oware)
0.05
0.1
Compressoo
0.00
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.5
0.8
Average rale
(mn(N)
Average mate:
[eo N3
Figure 4: We highlight the distortion-rate curves for two of the seven queries in the validation partition of our synthetic dataset. Our method, Adaptive QuerySelect, is able match the performance of the optimal query-aware strategy (left). Some queries naturally incur less distortion than others with the target LLM, even with a query-agnostic approach, if the query is aligned well with the data generation process for the prompt (right). Note that QuerySelect covers the line of LLMLingua-2 as their performance is identical for this query.
Gap from optimality depends on the query. In Fig. 4, we highlight the distortion-rate curves for two out of seven of the queries in our synthetic dataset. Despite the fact that Fig. I shows a gap in average performance between the query- Fig. 4 (left) shows that Adaptive QuerySelect can match the performance of the optimal query-aware compression scheme. Comparing Fig. (left) and (right), we see that the prompt compression problem is easier (methods are closer to optimality) for certain tasks or queries depending on how the prompts were generated. For our synthetic dataset, all prompts with a transition probability of 0.1 and a probability of 0.9 for remaining in the same state. This means the tokens with the highest entropy are those that part of transition, and those tokens the most important for answering this query. As a result, we see that methods that use the negative log-likelihood means for compression (Selective Context, LLMLingua, and LLMLingua Query) perform well, even without conditioning on the query. An exception here is the performance of LLMLingua Query, which we find has mixed performance compared to vanilla L.MMLnngua for token- level prompt compression on our dataset. Please refer to Fig. in App. F for results on all queries.
optimal strategy and Adaptive QuerySelect,
generated from Markov chain
Effect of tokenization. Finally, the results of our ablation study on the effects of tokenization provided in Fig. 10 in App. F. Interestingly, the optimal curves are nearly identical, suggesting that tokenization does not play role in attaining the best possible trade-off. Furthermore, we see that, for fixed rate, the standard tokenization performance often matches or exceeds the performance of forced tokenization. However, the standard tokenization approach does not allow for average rates below 0.6 due to the limited size of the prompts in our synthetic dataset, so the comparison is somewhat limited. In particular, standard tokenization allows for compression of at most four tokens (but usually only two or three tokens), whereas forced tokenization allows for compression of at most ten tokens.
Extension to natural language prompts. We have thus far shown the gap between current token- level prompt compression algorithms and their optimal strategies for both the query- and query- agnostic encoder on a synthetic dataset. Here, we extend our results to small natural language dataset curated with GPT-4 [38] (details in App. 1.2. For natural language prompts, the number of possible combinations of tokens grows too quickly, either by increasing the number of tokens in the prompt or increasing the vocabulary size, compute the full D... Instead, we rely the observation

---

RougeL
BertSoore
0.12-
Selective [1]]
118
LLMLingus [12]]
Awenge distorton
0.7
0.10
LLMLingu Query [13]
LLMLLiguu-2 [14]
08-
0.08
QuerySelect
0.3
Adaptive QuerySelect
0.00
Optinal (Qunry-agnoetle)
Optinall (Query-aware)
0.14
No Compression
6.02
Average rate E
Averago rate E
Mm 1
Comparison among all prompt compression methods show the aite-distottion trade-off for RougeL. [23] (left) and BertScore [45] (right). Since a higher RougeL. and BertScore metric is better, we plot "1 the computed average distortion" that higher rate should yield a lower loss. We discuss the choice of our metrics in App. F.2.2.
Figure 5:
natural language dataset. We
that current token-level prompt compression strategies simply remove tokens in place. With this observation, the number of prompts to consider has the same growth rate as a prompt with a binary alphabet. Please refer to App. E for more details. Although we cannot compute the true optimal curves where every possible combination of tokens is considered, we can compute the optimal curves for current prompt compression algorithms that do not generate new tokens. Fig. 8 shows that the gap for this approximation negligible on binary prompts.
The results of our extension to natural language prompts. presented in Fig. 5, show that both of our proposed methods achieve the lowest distortion among all other prompt compression algorithms for low rates. However, the gap between all algorithms and the optimal strategies is significant. We posit the quality of the training data for L...Miiguaa--BB in how far away the best method is from the optimal strategies between binary (Fig. 1) and natural language (Fig. 5) prompts. More specifically, the labels used for the binary synthetic dataset can be determined algorithmically and are optimal, but GPT-4 is used to determine the labels for the natural language dataset, which generally does not have set of optimal "ground truth" labels. Remarkably, the gap between feeding the prompt directly to the black-box LLM (no compression) and either optimal prompt compression strategy also large, and Fig. shows that much lower distortion can be achieved in roughly 70% and 40% fewer tokens for the query-aware and query- aggostic cases, respectively. I...Mingua-2 methods are the only methods that achieve lower distortion than the no compression result, albeit for higher rates. Finally, we present few histograms of the rates for QuerySelect and Adaptive QuerySelect in Fig. 15, which shows the greater range of rates that Adaptive QuerySelect may choose from over QuerySelect.
methods accounts for the discrepancy
Although we cannot compute the optimal rate-distortion curves on dataset as large as Narrative we did compute the curve for all existing methods to compare them on a larger-scale dataset. Those results are provided in Fig. 16; they confirm that our proposed methods outperform all other methods for rates below 0.5. We also display the average time to compress a prompt for each method in Table Since our methods are adapted from LLMLingua-2, they share the same runtime.
5 Conclusion
We have proposed a framework for understanding the prompt compression problem for black-box target LLMs. With this framework, we defined and formulated the optimal distortion-rate trade-off as linear program, and devised an algorithm to solve this efficiently via its dual, for both query-agnostic and query-aware settings. We compared the optimal curves with prompt compression methods in the existing literature and adapt one of them, LLMMingua-2,, to be query-aware and variable-rate; this modified method, Adaptive QuerySelect, exhibits superior performance, sometimes even matching the performance of the optimal query-aware strategy, on our synthetic dataset. As future work, is important to exhaustively study our proposed method on natural language datasets. Additionally, it is worthwhile to pursue an approximation to the optimal curves for large-scale datasets to observe the fundamental limit in that regime. We share preliminary results in that direction in App. G.3.
10

---

Acknowledgments
This work was partly supported by ARO Award W91 1991NN2310062, ONR Award N00014241255 and the 6G&UT center within WNCG at UT Austin. The work was also supported in part by the Swiss National Science Foundation under Grant 200364. The authors would like to thank Ananda Theertha Suresh for introducing them to the problem of prompt compression. AG would like to thank Emre Telatar for helpful discussions on the problem formulation.
References
[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 6000-6010, Red Hook, NY, USA, 2017. Curran Associates Inc.
[2] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with Paged/tttention. In Proceedings of the 29th Symposium on Operating Systems Principles, SOSP '23, page 611-626, New York, NY, USA, 2023. Association for Computing Machinery.
[3] Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. FlashAttention: Fast and memory-efficient exact attention with IO-awareness. In Advances in Neural Information Processing Systems, 2022.
[4] Tri Dao. FlashAttention-2:: Faster attention with better parallelism and work partitioning. 2023.
[5] Sinong Wang. Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity, 2020.
[6] Peng, Eric Alcaide, Quentin Gregory Anthony, Alon Albalak, Samuel Arcadinho, Stella Biderman, Huanqi Cao, Xin Cheng, Michael Nguyen Chung, Leon Derezynski, Xingjian Du, Matteo Grella, Kranthi Kiran GV, Xuzheng He, Haowen Hou, Przemyslaw Kazienko, Jan Kocon, Jiaming Kong, Bartlomiej Koptyra, Hayden Lau, Jiaju Lin, Krishna Sri Ipsit Mantri, Ferdinand Mom, Atsushi Saito, Guangyu Song. Xiangru Tang. Johan S. Wind, Stanistaw Wožniak, Zhenyuan Zhang, Qinghua Zhou, Jian Zhu, and Rui-Jie Zhu. RWKV: Reinventing RNNs for the transformer era. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
[7] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752, 2023.
[8] Amanda Askell, Yuntao Bai, Anna Chen, Dawn Drain, Deep Ganguli, Tom Henighan, Andy Jones, Nicholas Joseph, Ben Mann, Nova DasSarma, Nelson Elhage, Zac Hatfield-Dodde Danny Hernandez. Jackson Kernion, Kamal Ndousse, Catherine Olsson, Dario Amodei, Tom Brown, Jack Clark, Sam McCandlish, Chris Olah, and Jared Kaplan. A general language assistant as laboratory for alignment, 2021.
[9]
Charlie Snell, Dan Klein, and Ruiqi Zhong. Learning by distilling context, 2022.
[10] David Wingate, Mohammad Shoeybi, and Taylor Sorensen. Prompt compression and contrastive conditioning for controllability and toxicity reduction in language models. In Yoay Goldberg, Zomitsa Kozareva, and Yue Zhang, editors, Findings of the Association for Computational Linguistics: EMNLP 2022, pages 5621-5634, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics.
[11] Yucheng Li, Bo Dong, Chenghua Lin, and Frank Guerin. Compressing context to enhance inference efficiency of large language models, 2023.
[12] Huiqiang Jiang, Qianhui Wu, Chin-Yew Lin, Yuqing Yang, and Lili Qiu. LLMLingua: Com- pressing prompts for accelerated inference of large language models. In Proceedings of the 2023 Conference on Empirical Methods Natural Language Processing, pages 13358-13376. Association for Computational Linguistics, December 2023,
11

---

[13] Huiqiang Jiang, Qianhui Wu, Xufang Luo, Dongsheng Li, Chin- Yew Lin, Yuging Yang. and Lili Qiu. Longllmlingua: Accelerating and enhancing Ilms long context scenarios via prompt compression, 2023.
[14] Zhuoshi Pan, Qianhui Wu, Huiqiang Jiang, Menglin Xia, Xufang Luo, Jue Zhang, Qingwei Lin, Victor Ruhle, Yuqing Yang. Chin- Yew Lin, H. Vicky Zhao, Lili Qiu, and Dongmei Zhang. LLMLingua-2: Data distillation for efficient and faithful task-agnostic prompt compression. ArXiv preprint, 21122443312966. 2024.
[15] Jesse Mu, Xiang Lisa Li, and Noah Goodman. Learning to compress prompts with gist tokens. 2023.
[16] Tao Ge, Hu Jing, Lei Wang. Xun Wang, Si-Qing Chen, and Furu Wei. In-context autoencoder for context compression in a large language model. In The Twelfth International Conference on Learning Representations, 2024.
[17] Alexis Chevalier, Alexander Wettig, Anirudh Ajith, and Danqi Chen. Adapting language models to compress contexts. In Houda Bouamor, Juan Pino, and Kalika Bali, editors, Proceedings of the 2023 Conference on Empirical Methods Natural Language Processing, pages 3829-3846, Singapore, December 2023. Association for Computational Linguistics.
[18] Tomák Kočiský, Jonathan Schwarz, Phil Blunsom, Chris Dyer, Karl Moritz Hermann, Gábor Melis, and Edward Grefenstette. The narrativeqa reading comprehension challenge, 2017.
[19] Nelson Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts, 2023. arXiv:2307.03172.
[20] Tong Niu, Caiming Xiong, and Richard Socher. Deleter: Leveraging bert to perform unsuper- vised successive text compression, 2019.
[21] Raphael Schumann, Lili Mou, Yao Lu, Olga Vechtomova, and Katja Markert. Discrete opti- mization for unsupervised sentence summarization with word-level extraction. In Dan Juraf- sky, Joyce Chai, Natalie Schluter, and Joel Tetreault, editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 5032-5042, Online, July 2020. Association for Computational Linguistics.
[22] Demian Ghalandari, Chris Hokamp, and Georgiana Ifrim. Efficient unsupervised sentence compression by fine-tuning transformers with reinforcement learning. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio, editors, Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1267-1280) Dublin, Ireland, May 2022. Association for Computational Linguistics.
[23] Chin-Yew Lin. ROUGE: A package for automatic evaluation of summaries. In Text Summariza- lion Branches Oul, pages 74-81, Barcelona, Spain, July 2004. Association for Computational Linguistics.
[24] T. Berger. Rate Distortion Theory: A Mathematical Basis For Data Compression. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1971.
[25] Claude E Shannon. Coding theorems for discrete source with fidelity criterion. IRE Nat. Conv. Rec, 4(142-163):1, 1959.
[26] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wileey-nterscience, USA, 2006.
[27] Abbas El Gamal and Young-Han Kim. Network Information Theory. Cambridge University Press, 2011.
[28] Bruce Hajek and Michael B Pursley. Evaluation of an achievable rate region for the broadcast channel. IEEE Transactions on Information Theory, 25(1):36 1979.
[29] Stephen Boyd and I Lieven Vandenberghe. Convex optimization, Cambridge university press, 2004.
12

---

[30] George B Dantzig, Linear programming. Operations research, 50(1):42-44 2002.
[31] Aaron D Wyner and Jacob Ziv. The rate-distortion function for source coding with side information at the decoder. IEEE Transactions on Information Theory, 22(1):1-10, 1976.
[32] Aaron D Wyner. The rate-distortion function for source coding with side information at the decoder-Il: General sources. Information and Control, 38(1))60-80, 1978.
[33] Tsachy Weissman and Abbas El Gamal. Source coding with limited-look-aheadd side information the decoder. IEEE Transactions on Information Theory, 52(12):5218-52) 2006.
[34] Hirosuke Yamamoto. Wyner-Ziv theory for a general function of the correlated sources (cor- resp.). IEEE Transactions on Information Theory, 28(3)800-807,, 1982.
[35] Eric Lei, Hamed Hassani, and Shirin Saeedi Bidokhti. Neural estimation of the rate-distortion function with applications to operational source coding. IEEE Journal on Selected Areas in Information Theory, 344)6774-686, 2022.
[36] Yibo Yang. Stephan Eckstein, Marcel Nutz, and Stephan Mandt. Estimating the rate-distortion function by wasserstein gradient descent. In ICML 2023 Workshop Neural Compression: From Information Theory to Applications, 2023.
[37] Heasung Kim, Hyeji Kim, and Gustavo De Veciana. Estimation of rate-distortion function for computing with decoder side information. In First 'Learn to Compress' Workshop @ ISIT 2024, 2024.
[38] OpenAI, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Floren- cia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Moham- mad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shapiro, Christo- pher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brakman, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang. Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fe- dus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson, Vik Goel. Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lopes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang. Haozhun Jin, Denny Jin, Shino Jomoto, Billic Jonn, Heewoo Jun, Tomer Kaftan, Lukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Lo- gan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Lukasz Kondraciuk, Andrew Kondrich, Aris Konstan- tinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan, Teddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Ma- teusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mchta, Jacob Mcnick, Luke Metz, Andrey Mishchenko. Pamela Mishkin, Vin- nie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reicchir Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo. Hyconwoo Noh, Long Ouyang, Cullen OeKeeee, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pan- tuliano, Giambattist Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Francis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt,
13

---

David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard. Toki Sherbakov, Jessica Shieh, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Kata- rina Slama, lan Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang. Nikolas Tezak, Madeleine B. Thompson, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang. Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sherwin Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan. Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. Gpt-4 technical report, 2024.
[39] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril. Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b, 2023.
[40]
Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O'Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar Van Der Wal. Pythia: a suite for analyzing large language models across training and scaling. In Proceedings of the 40th International Conference on Machine Learning. ICML'23. JMLR.org. 2023.
[41] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach, 2020.
[42] Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
[43] Sebastian Ruder, Anders Sgaard, and Ivan Vuli. Unsupervised cross-lingual representation learning. In Preslav Nakov and Alexis Palmer, editors, Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics: Tutorial Abstracts, pages 31-38, Florence, Italy, July 2019. Association for Computational Linguistics.
[44] Mike Conover, Matt Hayes, Ankit Mathur, Jianwei Xie, Jun Wan, Sam Shah, Ali Ghodsi, Patrick Wendell, Matei Zaharia, and Reynold Xin. Free dolly: Introducing the world's first truly open instruction-tuner 1lm, 2023.
[45] Tianyi Zhang, Varsha Kishore, Felix Wu, Kilian Q. Weinberger, and Yoav Artzi. Bertscore: Evaluating text generation with bert, 2020.
[46] John von Neumann. Zur Theorie der Gesellschaftsspiele. Math. Amn, 100(1):295-320, 1928.
[47] Stephen Simons. Minimax Theorems and Their Proofs, pages 1-23. Springer US Boston, MA, 1995.
[48] R. Gray. Conditional rate-distortion theory. Technical report, Stanford University, 1972.
[49] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. In Teirth-seventh Conference Neural Information Processing Systems, 2023.
14

---

Appendix
The appendix is organized follows:
1. In App. A, we provide complete summary of the notation used throughout the paper.
2. In App. B, we formally characterize the distortion-rate functions for the query-aware prompt compression setting, analogous the query-agnostic setting in Sec. 3.
3. In App. C, we prove the main result of the paper (Thm. I) and give detailed description of the working of Algorithm
4. In App. D, we provide an overview of the information theory literature on rate-distortion theory, and explain how our model compares.
5. In App. E, we describe how Algorithm can be used to approximately compute the distortion- rate function for small natural language datasets.
6. In App. F, we provide details on the setup used for the experiments in Sec. 4.
7. In App. G, we have additional experimental results, including preliminary results on approx- imating the optimal distortion- curve for large-scale natural language datasets in G.3.
A Notation
General. We use - to signify a definition. For set X, with X' for i = 1, n, represent the sequence (I1,.... Œn) ) by x" E X", which is short for X' x ... x X. We use X to denote Un>1 X"", the set of all nonempty finite-length sequences n. We denote the cardinality of set X' by [.]. We
X. In general, for y E X
denote the length of y by len(y) use 12 to denote the set of nonnegative real numbers. For a set X' (x1,..., JzJ. we use the boldface (Ae) to denote the vector (Ag,..... Ast) indexed by elements of X. We also write R ((v,)
U2 E 2 for each E X). We use 1 to denote the indicator function, which takes the value 1 when its argument is true and 0 otherwise. The infimum and supremum of set of values is denoted using inf and sup respectively. We use and to denote the vector of appropriate dimension with all elements equal to 0 and 1 respectively.
Probability. We deal with discrete probability distributions on finite sets, for which we use calli- graphic letters to denote the set (e.g. X), uppercase letters to denote the random variable (r.v., e.g. X) and lowercase letters to denote samples of the r.v. (e.g. x). The set of all probability distribu- tions on the set X' is denoted by Pl (X)). The probability distribution of the r.v. X on X' is denoted by Px E (x)), , and we say X ~ Px. For a (measurable) function f. the expectation of the r.v. f(X) denoted by Ex~Px [f( or E [x)),, with the subscripts dropped when the distribution and/or rv's s are clear from context. The degenerate probability distribution with mass I at x E X is repre- sented by 8, (x). Conditional probabilities from X' y are denoted Py|x, and for each E X, denote the distribution Y as Py|x(-1z))
Problem--etupp-seeeiee notation. In our model, we use V to refer to the vocabulary of the prompt. We use the uppercase letters X to refer to the prompt, M refer to the compressed prompt, Q to refer to the query and Y to refer to the answer as random variables (and corresponding calligraphic and lowercase letters to denote the set and samples of the respectively). We use Py refer to the output distribution of the L.M,, which is modeled as the function ΦLLM- For a given prompt æ, we use M2 to refer to the set of possible compressed prompts, which the set of all sequences of length smaller than len (x:... To denote the distortion measure, we use d, which can be either the log loss diug or the 0/1 loss do/1- We denote the query-agnostic distortion-rate function rate R by D* (R). The average qwery-aware distortion-rate function is denoted by D* (R)). and the conditional query-aware iistortion-rate function for query E Q is given by (R)..
B Extensions to query-aware prompt compression
As mentioned in Sec. 3.2 and Sec. 3.3, analogous definitions and results can be obtained for the query-aware setting well. The difference is that the compressor has access to the query in addition
15

---

to the prompt. Thus, the compressor comp is a possibly random function from X x Q to M. For the query Q, the compressor maps the prompt X the compressed prompt M comp(X, Q) with (M) < len( X). The user provides the input [M, Q] to the LLM,, which produces the output distribution Py- (LLM(M, Q). Just as the query-agnostic setting, two quantities of interest are
(1) the (average) rate E
lon( (M) [en[X]
and
(2) the distortion E [dlog (Y, (LLM (M, Q))}
with both expectations taken with respect the joint distribution PMxQY- Since different queries may require different amounts of information to be preserved during compression, it is also of interest define the (conditional) rate and distortion for the specific query as E [en(M) len(X) and
[dhog (Y, (AM, respectively, with both expectations taken with respect the joint distribu- tion P PaxXY (-11)).
The rate-distortion problem for query- prompt compression be also formulated similarly to (3). We model comp as a random mapping P PMIxe from x Q to M. Then, the (average) distortion- rate function at rate R is the smallest distortion that be achieved by query-awaa compressor with rate at most R, given by
(*) =
inf Paixo
E [doo (Y, (LLLMMMMMMMMMM Q))]
s.t.
P PMIxQ is compressor, and
(5)
len (M)
E
< R
len (X)
with both expectations taken with respect to the joint distribution P.XQY = P P xQy induced by the compressor. The condition "P PMxx is compressor" is short for (1) for each X' and Q. mEEM P (m]xx 9) 1, (2) PM)xq (m|z, 9) 0 if lcn(m) > len(r), and (3) if (mn(m) = (z) then P x (m] æ q) = O unless m = æ. Similarly, the (conditional) distortion- rate function rate R is the smallest distortion that can be achieved by query-aware aware compressor for query at rate at most R, given by
(R)
inf (Mpx
E diog (Y, (M,
s.t.
P PMIxQ(11: .) is compressor, and
len
E
< R
[en(X)
with both expectations taken with respect to PaxYio(s..-lo)
Just like the query-agnostic setting, note that both (5) and (6) are linear programs, the objective and constraints are all linear in PM xQ and ( 9) respectively. We obtain explicit linear programs analogous to (LP) by defining constants Dg and Ry ja for the average distortion-rate function and D and R e IR for the conditional distortion-rain -aatoon--atteeae functions, for each x E and q E Q, similarly to (4).
Proposition 2 (Qurr--waat primal LPs). The (average) distortion-rute function for query-aware prompt compression (5) is given by the solution to
(R)
inf (=x,VER
Σ xEX
Do
Za.q
Σ Rd Zeg < R,
(avg-cond-LPP)
s.t.
xEX
1 Zz. 11,
VzEX,
16

---

The (conditional) distortion-rate function for query-aware prompr compression for query (6) is given by the solution to
(R)
inf (ZDER=M
Σ D
DEE
DEA
S.1.
Σ R
Zx I R,
(cond-LP)
DEA'
1 11 VIEX.
For each x X, My denotes the set of all possible compressed prompts associated to æ, i.e., the set of all possible token sequences of length at most len(z), the vectors ze.q IR for q E and
2s E R are the optimization variables respectively and the constants D R. D R R.M given by
len(m)
D 2,m
Px g) E /dogg(( ÓLLM 9)) and R & Pxx(1, 4)
m E Mz, (7)
len(x)
len(m)
D 2,m
(x)g(2lg) E |log (Y, ØLLM q))l and R R (x(e(114)
m m M2. (8)
len(x))
with the expectation taken with respect to Py)Mxq(-Im,a x,.).
Proof. This follows immediately from (5) and (6) by defining the constants Dg, R2 D Rg R for each æ E X' and E Q as given in (7) and (8) and taking Rn.q and z, to be P- respectively.. We use the fact that P P (m|2, 2z. q) = when len(m) > len(x) to reduce the dimension of Zx,y and zu from M to Ma
Remark 1. An interesting phenomenon here that does not occur in the query agnostag setting is the comparison between the average and conditional distortion- rate functions, i.e., D*(R) and (R(R) for E Q. One possible way "average" the conditional distortion-rate functions would be to simply compute Eq-Po [ but we always have D* (R) < Eq-Pa [Dg (R)]. This is because the latter averages the distortion-rate functions over Pq at fixed value of the rate, i.c., the prompt for each query forced to be compressed the same average rate over the queries is required to be R. This allows the compressor to set higher rate for "difficult queries" that have higher distortion values, and lower rate for queries that have lower distortion values in general. This is exactly the phenomenon we exploit in designing the variable- rate compression scheme Adaptive QuerySelect Sec. 4.1, which outperforms other existing schemes in our experiments.
R. For D (R), on the other hand, only the
Just as the query-agnostic setting, is useful to compute and solve the dual linear programs instead of directly solving the linear programs above.
Theorem 2 (Query-aware dual LPs). The (average) distortion-rate function for query-aware prompt compression (5) is given by the solution the dual of the linear program (avg-cond-LPP), i.e.,
(R) sup X20
-AR+
Σ
min MEM.
[
ARR
(avg-cond-dual-LP)
REX.GEQ
The (conditional) distortion-rate function for query-aware prompl compression for query q (6) is given by the solution to the dual of the linear program (cond-LP), i.e.,
(R)
sup X
XR
min Σ ZEX
D
+ ARS
(cond-dual-LP)
mEM,
Proof. (Conditional) This follows trivially by simply observing that the linear program in (cond-LP) identical to that (LP), except that D2 and R2 are replaced by the (conditional) query-aware versions DÅ and Rg respectively. Hene, by Thm. the solution to (cond-LP) is given by (dual-LP) with D2 and R,, replaced by the (conditional) query-aware versions D2 and R2 respectively, which gives (cond-dual-LPP
17

---

(Average) In addition to replacing De and R& from (LP) by the (average) query-aware versions D2 and R respectively, we also have that the optimization variables are given by zn.g for each pair (x, q) E X x Q as opposed to simply 2x for each r E X. Hence, by Thm. the solution to (avg-cond-LPP) is given by (dual-LPP with Dr and R2 are replaced by the (average) query-aware versions D and R. respectively and X' replaced by X' x Q. This gives (avg-cond-dual- exactly, and we are done.
Note that both (avg-cond-dual-LP)) and (cond-dual-LP) are of the same form as (dual-LP), with some minor differences. For a given E Q, the conditional distortion-rate function D2 is identical to the query-unaware distortion-rate function (R) with (D2, RR.) replaced by (D2, Rg), and hence can be solved by running Algorithm 1 with the input {R, (Da) xE (Rg 2 For the average distortion-rate function D*(R), in addition to replacing D2 and R2 by Dg and Rgg we also have that is replaced by x Q, hence (*) is obtained by running with the input (R))) 2xex))) where X' X Q and runs over all pairs (z, q).
(R,
C The dual linear program: proof and solution
C.1 Derivation of the dual linear program
Proof of Thm. I. We start from the linear program (LP) and construct its dual. Recall that (LP) is given by
D*(R)= =
inf
ΣDI 20
(z.ERM²)
xxx
MEX
Σ R S. R
s.t.
1 1 =1= V
Introduce the Lagrange multipliers À 2 0 to handle the inequality constraint and μrx R for each r to handle the equality constraints. Then, the above equation equivalent to
D' (*)R)=
inf
DD.
sup sup X
ER R R) WEX
Σ
sup Mr (1 -1) E.
(R
ZEN AEX
To see why this equivalence holds, observe that the terms Sup (Erex R. 2, R) and SuP uz Ti 2x 1) are both when (Zx)xex is in the feasible set of (LP) and +oc otherwise. Let μ A (Ma)ZE E & then we can simplify the above expression by rearranging terms, to obtain
D*(R)= =
inf (B
sup
Σ ZEX
(Dx + AR2 + ko1) 2o - ARR Σ 4x
dEX HER
ZEX
2, - Enex Mr linear (z+)xex and in (μ, A). and the minimization and maximization are both over convex sets. Hence, by the minmax theorem [46, 47], we can switch their order without affecting the equality, i.e.,
Note that the objective Evex (D, + AR. +
(R) = sup Y A20
inf (R DEE
Σ NEE
(Dr + AR + 1xl) 2n - AR Σ Pz
NEX
If, for I, there is component of the vector D. AR + p2 R.M, RM that is negative, then letting that component of 2, go to infinity, we have that the inner infimum is -c. On the other hand, every component of D + AR, + # is nonnegative for every æ, then the infimum is simply attained by setting
0. Hence, the above equation reduces to
D*R
sup
AR Σ Ms
NER
A20
18

---

S.t.
Dam + ARg, + ux 2 0 for every m E M2 and z E A.
For given the constraint Dam ARzmm + Mz 2 0 for all E M2 is equivalent -Ma S minmeM, (Da.m + RR).m) Letting Vx f minmme, (Dz,m + +R..m) frr and - (Uz)aex, the constraint is simply that vz 2 0 for all x, equivalently, E T Hence, the above equation can be written as
(*) = sup
-AR +
Σ
min MEM
(Dam + AR
Σ
V2.
PER
ZEX
ZER
X
Observe that only the first two terms depend on A, and only the last term depends on V. This lets us optimize over À and y separately, give
D* = sup X20
AR+ Σ
min (Da,m + +RRz,
+ sup NERT
- Σ Ve
mEM,
ZEX
DEX
sup
-XR +
Σ
min (Da,m + ARRmm) mEM,,
X20
ZEA
since suPuERy (- Exex - inf
VER Exex = - - inf = 0, and we are
done.
C.2 Proof and illustration of Algorithm
In this section, explain each step of Algorithm in detail. In doing so, prove that the algorithm does indeed solve (dual-LP), i.e., computes
(*(R)= sup X
-R++ Σ min [Da.m + A.r
BEX MEM,
We also use an artificial example described below show the working of the algorithm, in particular lines 1-9. For convenience, the algorithm is repeated verbatim below, without comments:
Algorithm 1: To compute the distortion-rate function via the dual linear program (dual-I.P)
Input: R, (Dz)aex: (Rx)axxi
Output: D (R), the distortion-rate function at rate R:
for E X do
Find M S M2 such that {(Re,, Dz,m)) (mmm)mmmds meMo are on the lower-left convex boundary of
{(Rr, D Dz.m))
mem:
mi my mk
(x) (x)
(x)
+ M ordered such that 2,m
>
e.m (=)
for I,...,kke his do (())
m,m (+)
a.mit (1)
a.
(m) i1 m.m
(z) RR
(z) + t00; (ao + A + {x(0 ,1(1)
(x)
A
No...., ., + -UsEx (w) with to0 To > An
> J > 2x 0
8 for x E X do
for j = b...,, do i k.] (1(0),((00 2 (ăy, set m. + -m;))
10 for j 1, 1.....k do
EEE R R.m > R then Xq + X5-1 else Aラ + Xz;
11
D, + + D Pammo + A3 R
12
u.m
Return max Dji
19

---

we have Consider the following artificial example with A' = {a,3). 3}. Let (Ra, Da) and (Rg, Dg) be as given by the blue points in the scatter plots over m E M, and E MM respectively in Fig. 6. In our example, we have [Mall 11 and [Mal = 8. The following observation is crucial: recall the definitions of R2 and Dz,.
len(m) len(x)
D a, (x) I [dog (Y, (LLM Q)) and Rxmm (x(2)
m. E EMa>
with the expectation computed with respect to ( (mm, x). For a fixed value of z, the positive real numbers D Dam can be arbitrary, but Rz, must be an integral multiple the constant Px(x)
len(#)
Hence, for given Rm,m takes at most len(z) possible values. This turns out to be extremely beneficial in the first step, namely identifying the points on the lower-left convex boundary.
D Da,m+
D3m
0.4
0.6
0.3 m
0.4
m
0.2
0.1
[a]
0.2
(a)
m2
m2g
0.1
0.2
0.3
0.4
Ra,m
0.2
0.4
0.6
R3.m
Figure 6: Scatter plots showing the points {(R.,,, Do.m) (omm)mmeee Jmm.. and {( Dam hmE
in blue. The associated lower-left convex boundaries MM (a) = {m]] (a)
(a) (a) and M
,m2 ,
{m (B) .m2 are in red; X(m), x(a)) and x are the magnitudes of the slopes of the associated line segments.
For E X' lines 2-3 of the algorithm identify the he points m (2) ....., left convex boundary of {RR,,m Da.m Iee., The lower-left convex boundaries are given by the red lines and the points lying the boundary
(x) m
that lie on the lower-
outlined in red. Observe that hg 3 and k3 2. The quantities computed in line are simply the magnitudes of the slopes of the line segments on the boundary. A simple computation gives the result of line 6 of the algorithm in our example to be A = {+oo, 1.5, 0.5, 0} and A (9) {+o 13. Clearly, for given value of x E X and X E [Af"0, (e) we have that m; (a) minimizes Damm X.R over all E MMg by virtue of the fact
that these points come from the lower-left convex boundary. Hence, for À E [A (())
Σ min [Da.m + ARRum = [[
a.mfo + AR 2,m
mEM,
ZEX
ZEX
We cannot simplify this further in its current state since A in the above expression depends on Hence, we must remove the dependence of the range (x))) (ar) on æ. To do so, observe that each A (x) is a partition of IR, on which m; (x) is the minimizer of Da.m + AR Line 7 of the algorithm simply constructs the union of all these partitions, with k elements, denoted by the À variables; here we have A 4 and the union is {+oc, 1.5, 1, 0.5, 0}. For each x, the minimizer each interval [ X)-1) of the finer partition is known exactly to be one of the mi (x) s; lines 8-9 associate to each interval the corresponding minimizer, given by m ((). There is no computation involved in these steps, only notational rewriting. The corresponding values obtained for our example given in the table below (with Xg +oo): observe that m (a) minimizes Da.m + AR over m E MM for X (x,
At this point, we have for À E (z)))
Σ min DDzmm + ARrmm
Σ xEX
D
AR
2.m (ix)
MEM,
REX
20

---

Table 1: The outputs produced by lines 7-9 of Algorithm I with (Ra, Da) and (Rg, D3) given
Fig. 6.
j
X
mj
(c)
mg
(3)
1
1.5
m (a)
(3)
m2 (a)
(3)
2
m
m22 (a:)
(3)
3
0.5
M2g
4
0
m3
(()
T22 (3)
= =(Erex D po.((e)) A (Ezex R Rangfo)
Hence, the right-hand side of (dual-LP) is simply
(Lnnxx D Pemmfe)) + A (Enex R Rs 2, R)
max j=l...,
sup xE(āg.Zz-1)
(Inex D Dammfo)) sup xe(ā).A--1)
(Emex R 2.m,
e. 11) 1t)}
= max j=
where the first equality follows since { is partition of R+. Consider the term A A (Ezex Ra B Rt) If R 2,m > R. this supremum occurs in the limit as + أj-1. otherwise it is achieved at x 7z. Hence, defining A to be A--1 or X; accordingly in line 11, we have that the above expression is simply maxj=1.....k k (Ezex m, + ReexR2,n } which is exactly what line 13 re- turns. Hence, we have that the algorithm correctly computes the distortion-rate function D* (R))..
D Connections to information theory literature
Rate-distortion theory is an area of information theory introduced by Shannon [25] to study the fundamental limits of source compression. The simplest rate-distortion setup is shown in Fig. 7a: We are given a source which generates samples X1..... Xn, independently and identically distributed (L..d.) according the distribution Px the set X. We also given a reconstruction alphabet X, which may may not be equal to X. The goal is compress X" sequence of l elements from an alphabet V, such that reconstruction onto 2 is "faithful" as possible, while keeping k as small as possible (in the information theory literature, V = {0, 1} typically). The fidelity of representation is quantified by distortion function d X' x & - [0, oo]. For example, the problem of compressing images with p real-valued pixels into bit sequences can be cast in this formulation by taking X X = RP, V = {0, 1}. and the squared-loss distortion function d(x, .) = || - =
Formally, the goal to construct an encoder enc : d - D and a decoder dec y* - 2 such that: (1) the rute k/n, and (2) the (average) distortion T. (d(",, dee(een(
are both as small as possible. We say that the rate-distortion pair (R, D) is achievable for the source Px under the distortion function d if there exists an (enc, dec) pair with rate at most R and average distortion at
most D. If the pair (R, D) is achievable, then elearly, for R > R and D 2 D, the pair (R. D) also achievable. Thus, the quantity of interest to us is the lower boundary of the set of achievable (R, D) pairs. This is given by the distortion- function D* which is defined follows: the distortion- rate function at rate R is the smallest distortion D such that the pair (R, D) is achievable, or equivalently.
D' D*RR) A inf D 2 0| (R, D) is achievable)
= inf(D D 2 0 there exists (enc, dec) with rate < R and distortion < DJ.
Note that the distortion-rate function depends on the source Px and the choice of distortion measure. Closed form expressions are known in some cases, the reader is encouraged to refer to classical
21

---

texts on information theory [24, 26, 27] for examples. It is important to note that the distortion-rate function is fundamental limit; no choice of encoder and decoder can give lower rate and lower distortion. Thus, the distortion-rate function characterizes the Pareto-optimal front of the trade-off between rate and distortion. distortion function R (D), which is the smallest rate R such that the pair (R. D) is achievable. The two functions trace the same curve when plotted on the same two-dimensional plane.
more common in the information theory literature to define the rate-
Several variants of this problem can be defined by introducing the notion of side-information, where we have i.idd samples (X1, Q.)..... (Xn, Qn) of pair of correlated random variables (X, Q) PxQ E P( x Q). A natural question to ask is what improvement is possible in terms of the rate-distortion trade-off for X when either the encoder or decoder or both have access to this side-informen indeiinformttin Q", which is correlated with X. If only the encoder has access to Q", then no improvement can be obtained. both the encoder and decoder have access to Q" as shown in Fig. 7c and studied by Gray [48], then, clearly, an improvement is possible. Surprisingly, we can obtain nontrivial improvements when the decoder has access to Q" as shown in Fig. 7b and studied by Wyner and Ziv [31, 32].
M
X"
enc
dec
X
X
enc
dec
X
Q"
(a) No side-information [25]
(h) Side-information at only the decoder [31, 32]
M
M
X
enc
dec
X"
enc
dec
22n
Q"
Q"
(c) Side-information the encoder and the decoder [48]
(d) For function computation, Z f(X, [34]
Figure 7: Rate-distortion models of compression.
These models resemble our setups for query-aware and query-agnostic prompt compression respec- tively, with key difference being that the decoder in our problem is the pretrained LLM, which is fixed. An rate-distortion setup that closer to our problem
this sense is that of compression for function computation, introduced by [34]. Here, the goal to recover an estimate 2n that is close to Z", with Z; = [[x;, Qi) for some desired function f. At first glance, it might appear that this setup exactly our model for prompt compression, but this turns out be false the desired output an estimate of f(X, Q), but the decoder can be designed to compute any arbitrary function of M and Q. In prompt compression, we have the constraint that the function computed by the decoder is fixed to be ÓLLM, in addition to requiring that the output be close to some function of X and Q. Thus, our model for prompt compression actually corresponds to a rate-distortion problem for function compu- tation with ind-inffrmation with a fixed decoder. which has not been studied before, to the best of our knowledge. The distortion-ranl function D' (R) for this setup is given by (LP) and (dual-LPP) A closed form expression for D' (R) cannot be obtained without making further assumptions ØLLMS nonetheless, (R) can be computed for any ΦLLM by solving Algorithm 1.
E Extension to natural language datasets
As discussed in Sec. 4.2, we also use Algorithm I to compute the distortion-rate function for a small natural language dataset. The decisive bottleneck in running Algorithm turns out to be obtaining Då for each z E X, i.c., the input to the algorithm. We require one inference call for each possible compressed prompt m E MM to compute D, for a particular prompt æ and query. Taking M, to be all sequences of length smaller than len(z), we see that that the size of M2 is > where V is the vocabulary of the LLM. The model used our experiments, Mistral 7B Instruct v0.2 [39], has |V] = 32, 32,000. Clearly, it is then virtually impossible to consider prompts with more than tokens, and in fact, makes it difficult to consider even medium length prompts (50 tokens) for vocabulary of size more than 2.
(en(a)) M/
22

---

Log Pranol
25-
0/3 loss, All 0 loss, Pruned
Avange distoriion
1.0
0.5
0.0
0.4
0.5
Average rate E
Figure 8: Query-agnostin distortion-rate curves plotted for log loss and 0/1 loss distortion measures. The curves marked with a 'diamond' are computed using all possible shorter sequences, while those marked with an 'x' are computed using only pruned versions of the original prompt. They nearly identical, which suggests that a good approximation to the optimal distortion-rate curve can be obtained by considering pruned prompts only.
A key first step towards extending our algorithm for natural language prompts is the observation that all prompt compression methods in the literature work by pruning tokens, i.c., (1) they are non non-generative, ie.. work by removing tokens from the original prompt and therefore do not generate any new tokens, and (2) they preserve the order the tokens as they appear in the input sequence. Hence, to compute the fundamental limit for the schemes that compress the prompt by pruning, is enough consider Mr to be the sequences that are obtained from æ by removing some number of (not necessarily contiguous) tokens. Then, we have [M = 2len(x)) irrespective of the vocabulary size [V]-
In Fig. 8, we observe that the distortion-rate curves obtained by restricting MM to be only those sequences obtained from æ from via pruning, are nearly identical the original curves, where we take M2 to be all shorter sequences. This suggests two things: (I) there is no fundamental drawback considering compression schemes are not generative, i.e., work by pruning the original prompt, and (2) we can approximate the optimal distortion- function reasonably well by considering only pruned versions of the prompt as possible compressed prompts. Thus, in principle, we can replicate experiments with natural language prompts of the same lengths (4 to 10) as the binary prompts in our difficult to identify sufficiently
experiments above, with the same computational cost. However, rich natural language prompts of such short lengths for which compression is reasonable problem, and hence, use binary prompts (generated from a Markov chain, to model the dependence between tokens) with natural language queries (since there is no computational restriction on the vocabulary of the queries) to run experiments such as those in Sec. 4.2 and App. at scale.
Nonetheless, to illustrate that we can get meaningful results by considering such "pruned" compressed prompts, we generate small natural language dataset using GPT-4 [38], as described App. F.2.1.
To make sense of the computational complexity involved in computing the optimal distortion-rate curve, consider the following toy example: suppose that the vocabulary size 10, and that the lengths of all prompts are 100. Then, the number of possible compressed prompts is of the order of 10000 When restricted compressed prompts obtained by simply "pruning" the input, this number reduces to nearly 2 2000, which is still large. However, since the length of the compressed prompt is at most 100, the number of points on the lower-left convex envelope Algorithm is most 100. Hence, the major bottleneck is in computing the D. quantities, which require 10 inference calls. Once these quantities are known, the complexity of Algorithm itself negligible, even for large vocabulary sizes and prompt lengths. One option is to approximate the optimal curve as best as possible while limiting the number of LLM inference calls made; we provide preliminary results this direction in App. G.3. To exactly compute the optimal curve while avoiding the 10 inference calls requires some assumptions to be made about ØLLM and some structure on the generated outputs; we leave this for future work.
23

---

F Experiment details
E.1 Synthetic data experiments
We provide additional details regarding our synthetic dataset and how we fine-tuned all models. Experiments
three different machines, two of which are identical machines with AMD Ryzen Threadripper PRO 5975WX CPU (32 cores), 256 GB of system RAM, and 2x Nvidia RTX 4090 GPUs with 24 GB each. We also ran experiments on a DGX machine with an AMD EPYC 7742 64-Core Processor, 512 GB of system RAM, and 4x 80GB SMX4 A A100 GPUs. The duration of LLM fine-tuning on the synthetic dataset varies, depending on the model being fine-tuned. In general, it takes 10 to 30 minutes for single fine-tuning run. Running the code necessary to reproduce all plots takes several hours.
We use code from the LLMLingua and Selective Context GitHub repos, which are released under the MIT license. In our experiments,
the following models: Mistral 7B Instruct v0.2 (Apache- 2.0), RoBERTa Base (MIT), and Pythia IB deduped (Apache-2.0).
Each method requires {0.04, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.96, 0.99, 1.0] in our experiments. However, the length of the returned compressed prompt might not be faithful to this rate parameter, so for each we report the average rate and average distortion on the examples in our validation dataset. LLMLin- gua and LLMLingua Query have additional parameter controlling the size of each segment the prompt is broken into before compressing each segment. We found that using a segment size of works best for our synthetic dataset.
rate or threshold parameter т, for which
r
F.2 Natural language experiments
We train our models on the same DGX system used in the synthetic dataset experiments. Unlike the synthetic dataset experiments, however, we train these XLM RoBERTa Large (MIT license) models with the single precision (float32) data format and use full fine tinettuning rather than LoRA. We observed non-negligible performance improvements with this configuration over 6 with LoRA. As result, training took one to two hours and 30 GB of VRAM on a single A 100. We used the same set or rate and threshold parameters as done in the synthetic data experiments.
F.2.1 Small natural language dataset
Solving for the optimal rate-distortion curve requires a substantial amount of compute as mentioned in App. E. To overcome this, we construct synthetic dataset consisting of binary string prompts, natural language queries, and numerical and yes/no answers. We show a few examples of the validation partition of our synthetic dataset in Table 2.
Table 2: One example of each query from the validation set of our synthetic dataset
Prompt
Query
Answer
1 110011111
Count the number of 1s.
7
11111
Count the number of Os.
0
00000111
Compute the parity. What is the length of the longest subsequence of Os or 1s? Is the binary string a palindrome? Count the number of transitions from 0 to and to Predict the next bit.
1
11011111
5
0110
Yes 3
1100111100
111111
We curated small natural language dataset to generate results shown Fig. by prompting GPT-4 [38] to provide short natural language prompts of 15 tokens or less, provide four questions about each prompt, and give the answer. Afterward, we modified some of the questions and prompts slightly when the generated prompt by GPT-4 was too long or the questions and answers contained too much overlap with each other for given prompt. In total, our dataset consists of ten prompts with four questions each. A few examples of our dataset are shown in Table 3.
24

---

Table 3: One example of each prompt from our natural language dataset.
Prompt
Query
Answer
After dinner, the cat chased a mouse around the house.
What was the doing?
The cat was chasing mouse.
The dog barked loudly at the passing mailman on a quiet street. After school, the child played with toys in the cozy living room. At the art gallery, the artist painted colorful mural on the wall.
Where did the barking
On a quiet street.
occur?
When was the child playing?
A After school.
Where was the painting done?
On the wall at the art gallery.
F.2.2 Choice of distortion metric
The proper choice of distortion function is important to meaningfully measure the change in perfor- mance (distortion) of the LLM as the rate is varied. Ideally, a distortion metric where two texts with the "same meaning," as would determined by humans, achieve a "low distortion" " is the gold stan- dard, but this metric is unknown. This is a crucial open problem not just for our work but also for the fair benchmarking of LLMs general.
For our results on natural language, we report our results using the following distortion metrics (or rather, "1-" these, since these are similarity metrics and we want a low distortion to mean high similarity). rougeL [23] is a standard metric used to evaluate summaries, which does so by computing the precision and recall between the tokens in the generated text and the reference texts. contrast, BertScore [45] computes contextualized embeddings for the generated tokens and reference tokens and uses the pairwise cosine similarity among them to produce the final score. The authors of the BertScore work highlight that their metric correlates better with human judgements than all other metrics (rougeL included). Regardless, our results with these two metrics are in agreement with each other, suggesting that a "good enough" metric may be sufficient. A popular approach in current literature is to ask GPT4 to give a score on the similarity between generated and reference texts. Although it has been shown that humans agree with GPT4's evaluation more than the evaluation of other humans [49], we are skeptical of this metric because it is not reproducible, and GPT4 has biases that may result in unfair or inaccurate evaluations. Additionally, our theoretical framework is general and does not assume any specific distortion function. In particular, it can also be used with new distortion functions that better capture semantic notions when they are discovered.
E3
LLM fine-tuning
F33.1
Synthetic dataset
Given that our synthetic dataset of binary prompts is not naturally in the distribution of training data of LLMs, use Mistral 7B Instruct v0.2 [39] our black-box model, and fine-tune on tuples of (prompt, query, answer). This is also known as "instruction fine-tuning:" we only compute the loss over the answer
Each prompt compression method requires an LLM as part of its compression algorithm; we fine-tune Pythia IB deduplicated [40] for Selective Context and LLMLingua- based methods. Selective Context and LLMLingua only use negative log-likelihood scores over the prompt, so for these methods we fine-tune with the next-word prediction over the prompts. For LLMMLnnuua Query, we place the (query, prompt, answer) tuple into context and then perform next token prediction over the entire context. We place only the query and prompt into the context for the prompt compression step (inference time).
LLMLingua-2 methods require an additional label for every prompt as ground-truth answers to teach the model to predict which tokens should be kept. For our dataset, gathering the labels for each prompt deterministic if the query is known, so easy to assemble the label set for query-aware LLMLingua-2 methods. For example, for the query "Is the binary string palindrome?" we can easily choose the shortest sequence of tokens from the input that also palindrome (if the answer "yyes") as the ground-truth compressed prompt. For QuerySelect and Adaptive QuerySelect, both of which are query-aware, we put the query and prompt into context and then train the L.MM to predict which tokens to keep using the constructed label set. This process is less straightforward for query-
25

---

agnostic LLMLingua-2 since it is not clear how to assign the labels without the query. In this case, we choose the ground-truth compressed prompt consist of the highest entropy tokens. Given the Markov chain from which our prompts were generated, these tokens contain the transitions between bits. For all L.MMLingua22 methods, we fine-tune RoBERTa Base [41].
We conduct a grid search over a set of hyperparameters before fine-tuning the final model used fine-tune model with all combinations
for each method. Specifically, we use the training of hyperparameters, evaluate the final performance on each model with a test set, and choose the combination of hyperparameters leading to the best performance. We then merge the train and test set and train with the chosen hyperparameters and do a final evaluation on the validation, which is the dataset used in the results of this paper.
All models are searched over the same learning rate (5e-6, 1e-5. 5e-5, 5, le-4), batch size (16, 32), LoRA rank (16, 32, 64, 128), and LoRA alpha (16, 32, 64, 128) hyperparameters. For the number of training epochs, we search over 2, 4) for Mistral 7B Instruct v0.2 and Pythia 1B deduplicated, and {8, 12) for RoBERTa Base.
We report our final set of hyperparameters used to fine-tune the LLM used for each prompt compres- sion method in Table 4.
Table 4: Final set of hyperparameters used to train the LLM used in each prompt compression method.
Method
Tokenization
Epochs
Batch Size
Learning Rate
LoRA
LoRA
Rank
Alpha
Selective Context
Standard
16
5e-5
32
32
Selective Context
Forced
16
5e-5
128
64
LLMLingua
Standard
16
5e-5
32
32
LLMLingua
Forced
16
5e-5
128
64
LLMLingua
Standard
4
32
le-4
128
128
Query
LLMLingua Query
Forced
16
lc-4
64
128
LLMLingua-2
Standard
12
32
lc-4
128
128
LLMLingua-2
Forced
12
32
lc-4
64
128
QuerySelect
Standard
12
32
lc-4
128
128
QuerySelect
Forced
12
32
le-4
64
128
Adaptive QuerySelect
Standard
12
32
le-4
128
128
Adaptive QuerySelect
Forced
12
32
le-4
64
128
Black-box target LLM
Standard
16
5e-5
16
16
Black-box target LLM
Forced
16
5e-6
16
64
F.3.2 Natural language dataset
We use fine-tuned models available on Hugging Face for the Selective Context, LLMLingua, LLM- Lingua Query, and LLMLingua-2 prompt compression methods; only QuerySelect and Adaptive QuerySelect, our novel methods, require specialized fine-tuning starting from a pretrained XLM RoBERTa Large [41] model. To fine-tune these models, we modify the L.LMinngaa22 training code available in the LLMLingua GitHub repository to accept (prompt, query) pairs as input and classify which tokens of the prompt should be kept. Since the query additional context, and since the
26

---

max context window of XLM RoBERTA Large is 512 tokens, we shrink the window size dedicated to the prompt 384 tokens. We used the same hyperparameters used in the LLMLingua-2 paper [14) for fine-tuning, i.e., learning rate le-5, 5, batch size 10, epochs 10, and the Adam optimizer with = =09.9 32 = 0.999, = and weight decay O.
The dataset used to train our models is filtered version of Databricks Dolly 15k [44]. Our final filtered dataset contains samples that meet the following conditions: (1) the context is non-empty, (2) the context is between 50 and 5000 characters in length, and (3) the instruction has fewer than 360 characters. After filtering, the dataset contains 4.35k samples. The contexts of this dataset are chunked into windows of 384 tokens, and we prompt GPT-4 to compress the context by asking it only to keep the tokens necessary for responding to the provided instruction. This allows us construct a label set for the token classification problem of choosing which tokens to keep or remove. Our dataset used for training consists of the instructions (queries), chunked contexts (prompts), and the set of labels for the contexts. 95% of the samples in this dataset are used in the training dataset, and the remaining 5% form the validation set. Table 5 shows the prompt we used for GPT-4, which is a modified version of the prompt used in the LLMLingua-2 paper. All of our code used for constructing the training dataset and training the models are modified from the LLMLingua GitHub repo. Our modified code is available in the code release.
Table 5: Our prompt for GPT-4 to determine which tokens to remove. This prompt was used to construct the dataset for training QuerySelect and Adaptive QuerySelect on natural language. This is a slight modification from the prompt used in the L.MMLingua22 work [14].
System Prompt
You are an excellent linguist and very good at compressing pas-
sages into short expressions by removing unimportant words, while retaining as much information as possible.
User Prompt
Compress some text short expressions, such that you (GPT- 4) can answer the query based on the compressed text. Unlike the usual text compression, I need you to comply with the 5 conditions below:
1. You can ONLY remove unimportant words.
2. Do not change the order of words.
3. Do not change the original words, e.g., 'asking' - 'ask" is NOT OK; 'current'
'now" is NOT OK.
4. Do not use abbreviations or emojis, e.g., 'without" + 'w/o" is NOT OK; 'as soon as possible' + 'ASAP' is NOT OK.
5. Do not add new words or symbols, this is very impor- tant. For example. 'dedicate hours to each chapter' + '3 hours/chapter' is NOT OK because you add new token Y/, just compress it into '3 hours each chapter'. '30 eggs plus 20 eggs equals 50 eggs' + '30+20=50' is also NOT OK because you add new symbols + and =; just compress it into '30 plus 20 equals 50'
Compress the origin aggressively by removing words only. Please output the compressed text directly. Compress the origin as short as you can, while retaining ONLY the information needed to answer the following query: {query). If you understand, please compress the following text: ftext to compress)
The compressed text is:
G Additional experimental results
G.1 Small-scale datasets
We provide the remainder of our empirical results below. Fig. is similar to Fig. but shows the result when the prompt compression method uses standard tokenization rather than forced tokenization. Fig. 10 shows a direct comparison between the trade-off for methods using standard and forced
27

---

tokenization. Fig. 11. Fig. 12, Fig. 13, and Fig. 14 show the rate- diteedistootion trade-off curves for each of the seven queries our synthetic dataset. Fig. 11 shows forced tokenization with 0/1 loss, Fig. 12 shows forced tokenization with log loss, Fig. 13 shows standard tokenization with 0/1 loss, and Fig. 14 shows standard tokenization with log loss.
Log loss
0/1 loss
Selective
LLMLingua
Aveerege distortion
LLMLinguu Query
11.3-
LLMLingmm2
6-
QuerySelect
Adaptive QuerySelect
Optinal
0.1
Optimal (Query-oware)
No Compression
0.0
0.0
0.6
0.8
0.2
114
0.8
1.0
Average rate DD
Average rate
Figure 9: The distortion- rate curves of all prompt compression methods and the optimal strategy attained by solving our dual LP formulation when standard tokenization is used for the prompt. All methods are compared with the log loss (left) and 0/1 loss (right) metrics.
Standard tokenization
Forced tokenization
Selective
LLMLingun
Average dattrtion (0/1
0.4
0.4
LLMLingu Query
L.M.iggm-2
QuerySelect
Adaptive QuerySelect.
0.2
0.2
Opliuml
Optimal (Query-cware)
No Compression
0.0
0.0
Averago rate
MY T
Average Pate E
Figure 10: Performance comparison when standard tokenization (left) and forced tokenization (right) is used on our synthetic dataset. Interestingly, the optimal performance is nearly equivalent between the two, and, for a given rate, methods with standard tokenization match improve upon the performance of a method that forced separate tokenization of every bit. However, standard tokenization results in compression of I to 4 tokens on our dataset, whereas forced tokenization compresses up to 10 tokens, allowing for a greater range of rates.
G.2 NarrativeQA
We compare existing methods on the NarrativeQA [18] dataset. Specifically, we use the summaries from the dataset as the prompt, and use the query and answer as given. Since the sizes of the prompts are hundreds of tokens and approximately 3,500 samples, it not feasible to compute the optimal rate- distortion curve for this dataset. Instead, Fig. 16 showcases the performance of our proposed methods over existing methods. In particular, Fig. 16 shows the same conclusion as Fig. 5: our proposed methods are better for rates less than 0.5 and remain competitive for rates about 0.5. Table 6 shows the average time required to compress a prompt on the NarrativeQA dataset and our curated small-scale NLP dataset. Since our methods are adapted from LLMLingua-2, methods share the same timings.
28

---

What is the length of the longest subsequence of Os 1s? Count the number
Count the mumber of Os.
0.7
0.6
distortion (0-3
0.5
0.4
0.8
01.3
0.2
0.2
0.0
0.0
0.0
0.2
Compute the parity.
0.6
1.0
0.4
0.5
Avarae disrectee
0.5
0.6
0.4
0.2
6.
0.0
0.2
0.6
0.5
0.0
0.2
0.6
0.5
binery string a palindrome??
Count number transitions
0.20
Aveeago distortion (00)
0.15
0.3
0.10
0.2
0.00
Avernge rale
Average rate
Predict the next hit.
Common Tagend
Average dletortion (0/1 looa)
0.30
LLMLingua
LLMLingus Query
0.25
LLMLingna
QueeySelect
Adaptive Query Select
Optimal (Queyy awure)
No Compeession
0.15
0.10
0.0
0.2
36
Figure 11: The rate- date-ristootion trade- off of all methods on each individual query for forced tokenization and 0/1 loss.
29

---

Count the number 1s.
Count the number of Os.
Avenape distoriion (loc lose)
0.0
0.6
Compute the parity.
What is the length of the longest subbeequence of 06 18?
10-
3.0
Antragedlsttttto distoriin [log
0.0
2.0
3.0
0.0
0.0
0.2
0.6
1.0
0.0
0.2
0.4
0.5
the binary string a palindromee?
Count mumber transitions
1.4
1.2
Anecgge dastoriino
1.0-
0.6
1.5
0.4
0.2
Aserago rate
Average rate
Predict the next bit.
Common Tagend
LLMLingua
Average distortion. (lo
LLMLingus Query
LLMLingna
0.5
QueeySelect
Adaptive Query Select
Optimal (Queyy awure)
0.4
No Compeession
0.5
0.0
0.4
0.00
0.5
1.0
Figure 12: The rate- date-ristootion trade-of off of all methods on each individual query for forced tokenization and log loss.
30

---

Count the number Is.
Count the mumber of Os.
0.0
0.5
0.5
Avarage distortion (0-3
0.4
0.41
0.8
0.3
0.2
012
0.1
0.0
0.0
0.0
0.2
Compute the parity.
What is the length of the longest subsequence of Os 1s?
0.25
Average diractioa (0:1 los))
0.5
0.15
0.5
0.30
0.4
0.2
0.10
0.0
0.2
0.6
0.5
0.0
0.2
0.6
0.5
binery string a palindromc??
Count number transitions
Avecago distortion (00)
0.10
0.2
0.00
Average tate
Average rate
Predict the next hit.
Common Tagend
Average dlstortion (0/) looa)
LLMLingua
0.25
LLMLingus Query
LLMLingna
QueeySelect
0.20
Adaptive Query Select
Optimal (Queyy awure)
No Compeession
0.10
0.0
0.2
06
Figure 13: The rate-distortion trade-off of methods on each individual query for standard tokeniza- tion and 0/1 loss.
31

---

Count the number of Is.
Count the number of Os.
Aveage distortion (log lose)
000
0.4
0.0
Compute the parity.
What is the length of the longest subsequence of (s 1s?
Avrrggo-lettti dletortio (log loa)
10
6-
0.3
0.0
0.-
0.0
0.4
10
0.0
0.4
0.0
0.5
Is binery string palnddrom??
Count number transitions from and to
2.5
Averago distortzo
0.3
0.3
Average rate
Average
Predict the next bit.
Common Tagend
Avenage detortion (log los))
0.7
LLMLingua
LLMLingus Query
LLMLingna
QuerySelect
Adaptive Query Select
Optimal (Queyy awure)
No Compeession
0.4
0.0
0.4
0.5
Figure 14: The rate-distortion trade-off of methods on each individual query for standard tokeniza- tion and log loss.
32

---

Average ratio: 0.27
Average ratio: 0.57
40
QurrSeter
QueySeeee Aingline QuaySeiet
Alggine Quayydec
Doquetcy
20
25
20
20
15
5
0-
0.
0.4
0.6
10
Binned rates
Binned rates
Average ratio: 0.77
Average ratio: 0.87
40
QuerySbect Maggiee Quaryikkct
Queyy Aagtiee QuarySelec
35
30
30
Froqurncy
20
25
20
20
6-
0
0.4
0.0
0.6
Binned ratess (en(
Binned ralees
ke)())
Figure 15: Histograms of the rates for QuerySelect and Adaptive QuerySelect for a given average rate from the left-side figure of Fig. 5. These figures show that Adaptive QuerySelect has larger spread of rates across the samples of the natural language dataset. In particular, Adaptive QuerySelect has greater flexibility in choosing an appropriate rate for given (prompt, query) pair.
Table 6: Average time required to compress single prompt (seconds).
Method
NarrativeQA
Small NLP Dataset
Selective
1.043
0.049
LLMLingua
0,510
0.273
LLMLingua Query
1,060
0.530
LLMLingua-2
0.113
0.044
QuerySelect
0.114
0.043
Adaptive QuerySelect
0.114
0.043
33

---

1 RougeL
BertSoore
0.160
0.155
0.020
Selective
Average: distortion
LLMLingun
0.000
L.MLingu Query
0.575
L..T.nguu22
0.850
0.140
QuerySelect
Adaptive QuerySelect
0.875
0.135
No Compussion
0.130
0.770
0.2
0.4
0.0
0.2
Average rabe IR
Average rabe R
Figure 16: Comparison among all prompt compression methods on the NarrativeQA [18] summaries dataset. We show the rate-distortion trade-off for RougeL [23] (left) and BertScore [45] (right). Since a higher RougeL and BertScore metric better, we plot "1 the computed average distortion" so that higher rate should yield a lower loss.
G.3 NarrativeQA Beam Search
As discussed in the Conclusion and App. E, computing the optimal rate-distortion curves for large- scale datasets, where the prompts consist of hundreds or thousands tokens, is intractable. The difficulty lies in computing Da., which requires inference call for every possible compressed prompt for a given prompt. Even for our curated small-scale dataset, whose largest prompt consists of 15 tokens, it is not feasible compute the "true" optimal curve outright. Instead, we considered the set of compressed prompts constructed from in-place token removal from the original prompt, which significantly reduced the number of inference calls in constructing D₂ from Eist Ele((2)1 D/ to 2len(ar) where [ is the size of vocabulary of the tokenizer and X' is the prompt. While this approach does not yield the "true" optimal curve, it does provide an optimal curve to all existing prompt compression methods since they all strategically remove tokens in place. Thus, we can still establish the fundamental limit of existing methods!
However, when len(x) a few hundred or thousand, as the case for large-scale datasets, 2len(x) far too many inference calls to make D, to be practical. Ideally, one can approximate the optimal curve by finding an upper bound; to do this, we use beam search. Our search space is over all 21en(x) binary masks binary mask, when applied to the prompt, forms a compressed prompt). Each mask is assigned a distortion value by computing the distortion between the ground truth answer and the generated answer when the black-box LLM is given the mask's associated compressed prompt and the query. Thus, we can construct the search tree over the binary masks and use beam search to find masks with low distortion.
The search tree begins with the "all ones" mask at the root node (1 = 0); each of the root node's children (1 = contains bit flipped
in precisely one of the len(x) positions. At the third level (1= 2), each node inherits a 0 at the same position as its parent and then flips to a 0 so that each mask at 2 has precisely two Os. This pattern continues throughout the rest of the tree, resulting in masks with Os at level I. Furthermore, the branching factor F; of our beam search is the number of children nodes given node has level I, N 1. At level 1, accounting for all nodes that are shared among the parent nodes in level 1, there are (*) nodes. where N len(x:) As a sanity check. this tree contains = ( 21en(x) nodes in this tree, so all binary masks of length N are in the tree. can search every node the tree as long as the beam width large enough h to contain every node at the broadest level of the tree. To achieve this, we need to set max; = (1N921)-
Recall that our purpose for using beam search is to drastically reduce the number of LLM inference calls required for constructing D, while retaining competitive upper bound to the optimal curve. The cost C associated with the beam search, which is the number of nodes visited in the tree (i.e., the number of LLM inference calls) is
34

---

1 Rougel,
Selective
L.Milngua
Average distortion
LLMLingua Query
LLMLingus-2
QuerySelect
Adaptive QuerySelect
Beam Search (Query-agnostic)
Beam Search (Query-aware)
No Compression
0.0
0.6
0.8
Average rate
E
Men
Xe
Figure 17: Comparison between existing prompt compression methods (replicated here from Fig. 16) and our approximation the optimal rate-distortion curves via beam search NarrativeQA.
N C= B
BN(N + +1)
Fi 1
(N
Σ k=0
(10)
1=0
Note that, in this case, search over C' [M in (LP) compressed prompts, beam search will provide an upper bound. When is large, checking O(BN2) nodes is a drastic reduction over checking 2 nodes, but the growth rate is still large. For example, running beam search single prompt of just 100 tokens will require on the order of 10 LLM inference calls, or roughly 11.5 days if assuming single inference call takes one second. To further reduce the number of checked nodes, we can chunk the binary masks into spans of bits, and flip entire spans from to at each level. With this approach, can effectively control the length of the binary masks search over, which we call Nen, for a given budget/cost C. Solving (10) for N, we arrive at
-1
B
Nar
2
This approach allows us to choose the total number of L.LM inference calls C per prompt that we will spend on beam search for particular beam width B. Since we are chunking the binary mask into spans and then masking the spans as we search, we have reduced the search space and the resulting tree will be smaller than the Nof N case.
Fig. 17 compares existing methods our beam search upper bounds for C 4000 and B Although LLMLingua-2-based methods can outperform the upper bound in the query-agnostic case for most rates, the query-agnostic beam search approach shows room for improvement from existing methods. Impressively, the gap between existing methods and the qwere-aware case is quite large, even for the methods that use the query to compress the prompt.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly mention the assumptions under which we present our results.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We provide section detailing the limitations of our approach and potential approaches remedy them in App. E.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Our theoretical results in the main paper are Proposition I (proved in the main paper) and Thm. 1 (proved in C.1, with proof sketch in the main paper); both are stated with all required assumptions. We also provide an informal proof in the main paper that Algorithm 1 computes the distortion-rate function; this made formal in App. C.2.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided not)?
Answer: [Yes]
Justification: We provide our code with details on how to reproduce our results as supple- mentary material, which will be made publicly available upon acceptance.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our code is available at https : // //gtthut.t//////////////// com/ conn/acnagle/ffnnnnennn limits, with instructions reproduce results in the paper.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperpa- rameters, how they were chosen, type optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All details of our experimental setup can be found in Sec. 4.2 and App. F.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Our experiments are not statistical in nature. All our plots are deterministic and can be reproduced using the code provided in the supplementary material.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
36

---

Answer: [Yes]
Justification: Information on compute resources can be found in App.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:///eeeip..peeeee httpr//s..../....ttttttcccccllll
Answer: [Yes]
Justification: We do human subjects private data, work has direct societal impact, and we appropriately reference all code that we have used for our experiments in Sec. 4.2.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is foundational research, and though it has applications to the practical problem of prompt compression, our focus understanding its fundamental limits. There are no direct societal impacts of our work.
Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: We do not release any new data or models.
12. Licenses existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All assets for which we are not the creators, including some code and models, are properly cited and available under either the Apache-2.0 or MIT licenses. This informa- tion is provided in App. F.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification: No new assets are introduced.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: No human subjects were involved.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human
Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects were involved.
37


Reviews:
[{"review_id": "nFqfmplgXj", "reviewer": "Reviewer_cHot", "summary": "This paper proposes an information-theoretic framewok for token-level prompt compression for large language models, where the rate is characterized by the expected ratio between the compressed prompt and the original prompt, and the distortion is a cross-entropy based distortion or an accuracy based distortion. The RD problem is then converted to a LP problem, where optimal solutions are given for both query-aware and query-agnostic settings. An algorithm \"LLMLingua-2 Dynamic\" is proposed that outperforms other LLMLingua-based algorithms.", "questions": "1. Why is the compression rate defined as the expected ratio between len(M) and len(X)? In information theory, the rate is usually measured by units such as bits.\n2. In the query-aware setting, if query is provided, then why not compress the answer directly, so the optimal rate would be a constant?\n3. In lines 85-86, you said \"we assume that a query is provided in addition to the compressed prompt during the target LLM inference call\", but later in lines 136-137, you then said \"To simplify the presentation, we restrict our discussion here to the query-agnostic setting, and only briefly mention the analogous definitions and results for the query-aware setting.\" Is there any particular reason for this conflict?\n4. In Proposition 1, what do you mean by $\\mathbb{R}_+^{\\mathcal{M}_x}?$ $\\mathcal{M}_x\\subseteq \\mathcal{V}^*$ right?\n5. The proof of Proposition 1 is unclear. In (LP), constants $D_x, R_x$ are used, but only $D_{x,m}, R_{x,m}$ are defined.\n6. From the experimental results, it seems that the proposed method can bot achieve high compression rate/low distortion (lossless). Could you discuss this in your paper?\n7. Could you provide comparisons to other baselines such as [1] and [2]?\n8. Could you conduct experiments on other public datasets, such as the NarrativeQA dataset?", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Token-level semantic compression has been an active area of research. The current paper builts an information-theoretic framework inspired by the rate-distortion trade-off in source coding. Algorithms for solving the RD problems are given. Therefore, the proposed framework will be useful for comparing prompt compression methods in the future.", "weaknesses": "The motivation for query-aware compression is not clear. If query is provided, then why not compress the answer directly, so the optimal rate would be a constant? The main content focuses on the query-aware setting (we assume that a query is provided in addition to the compressed prompt during the target LLM inference call), but the theorecital discussions in section 3.3 are on the query-agnostic setting. While the query-aware parallel is provided in the appendix, is there any reason for not focusing on the query-aware setting in the first place?\n\nThe experiments are not convincing, in that the prompt lengths in the dataset is too short, and that the dataset only contains 7 queries. In practice, the token-level semantic compression is often used to reduce redundancy of long input. Therefore, this work should consider long prompts such as the NarrativeQA dataset. Moreover, the literature review is not thorough -- some baselines are missing (e.g., [1,2]).\n\n[1] Wingate, David, Mohammad Shoeybi, and Taylor Sorensen. \"Prompt compression and contrastive conditioning for controllability and toxicity reduction in language models.\" arXiv preprint arXiv:2210.03162 (2022).\n[2] Fei, Weizhi, et al. \"Extending context window of large language models via semantic compression.\" arXiv preprint arXiv:2312.09571 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback. We provide our response to the individual comments here, and strongly encourage the reviewer to check our global response for updates regarding our new natural language experiments, which is also relevant to the reviewer’s comments. We also believe there is a misunderstanding regarding the meaning of query-aware prompt compression, which we address in our responses to Q2 and Q3. \n* Q1 (**Unit of rate**): We define the rate to be len(m)/len(x) mainly because this is the convention that is followed in the prompt compression literature. Both len(m) and len(x) are measured in “tokens”, so the unit of rate is “tokens (of compressed prompt) per token (of prompt)”. In classical information theory, sequences are compressed to binary strings, hence the unit is “bits per source symbol”. Even in information theory, it is indeed the length that is used as the proxy for rate in variable-rate coding [1] and more recent “one-shot” compression setups [2,3].\n* Q2 (**Compression of answer**):  Providing the answer as an input to the LLM might not result in the correct output, e.g. let the prompt be “00011” and the query be “how many zeros are in the prompt?”. The answer should be “3”. If we simply pass “3” as the input to the LLM as the compressed prompt with the query “how many zeros are in the prompt?,” the answer will be “0”, which is incorrect for the given prompt.\n\n    Indeed, we expect that a “good” compressor is able to extract as much of the answer as possible from the prompt and compress that information, but understanding this is orthogonal to our work; we instead find the optimal theoretical performance that can be achieved by *any* compressor (which may or may not use this “find answer, compress” strategy).\n* Q3 (**Clarification on query-aware**): \n    * We wish to clarify a potential misunderstanding: “we assume that...LLM inference call” does not imply the query-aware setting — this is the case for both query-aware and query-agnostic compression (Fig. 2 in paper). The difference in the query-aware case is that the compressor also has access to the query. \n    * The query-aware and query-agnostic settings are both independently important to study theoretically. Our work provides an information-theoretic framework to study hard prompt compression, an area of active research, with several schemes already proposed. These schemes are either query-agnostic (LLMLingua) or query-aware (LLMLingua Query); we cover both types in our framework.\n    * We only develop the theory for the query-agnostic setting in the main paper since the query-aware setting is analogous.\n* Q4 (**Notation in Prop. 1**): For a finite set $A = \\\\{ a, b, c \\\\}$, we denote $\\\\mathbb{R}^{A}_{+}$ as the set of all vectors $x$ with components indexed by elements of $A$, i.e., $x = (x_a, x_b, x_c)$, where $x_a, x_b, x_c$ are nonnegative real numbers. (An overview of our notation is provided in App. A, but we will explain these instances of non-standard notation in the main text.)\n* Q5 (**Constants in Prop. 1**): The constants $\\\\boldsymbol{D}_{x}$ and $\\\\boldsymbol{R}_x$ are vectors with nonnegative real components, indexed by elements of $\\\\mathcal{M}_x$, i.e, ${\\\\boldsymbol{D}_x}_m$ and ${\\\\boldsymbol{R}_x}_m$ are the components of $\\\\boldsymbol{D}_x$ and $\\\\boldsymbol{R}_x$.\n* Q6 (**Proposed method does not achieve high rate and low distortion?**): \nOur proposed method does match the “No Compression” result when the rate is 1, and can likely achieve low distortion for rates less than 1, but we are not able to exactly characterize when that transition happens for this dataset. LLMLingua-2 Dynamic does not compress with higher rates on our binary dataset, and this is because the $[0, 1]$ confidence scores for each token which should be kept (according to the training data) are very high (between 0.98 and 0.99), and the scores for the tokens which should not be kept are very low. In fact, we could not find a threshold greater than 0 which gives a high rate. For our new natural language experiments, the curves for our LLMLingua-2 Dynamic method fully cover the range of low to high rates.\n\n   We will include updated figures containing at least the RD point for rate 1 in the final revision of our paper, in addition to the discussion above explaining this behavior.\n* Q7 (**Comparisons to other baselines**): Please note that [4] (which we cite as [10] in our paper) is a *soft* prompt compression scheme and is not compatible with our framework, which focuses on *hard prompts*. While methods that use soft prompts are a valid approach to the prompt compression problem, they are not compatible with black-box LLMs, which is a crucial component of our framework.\n\n    Thank you for bringing [5] to our notice; we will cite them in the final version of our paper. Unfortunately, their code is not publicly available; we are unable to integrate their method into our experiments.\n* Q8 (**Additional experiments**): Thank you for this suggestion; we agree that extending our experiments to (ideally large-scale) natural language datasets is important for our paper. We provide the results of two new experiments on natural language data, including NarrativeQA, in our global response.\n___\n**References**:\n\n[1] J. Ziv and A. Lempel, \"Compression of individual sequences via variable-rate coding,\" in IEEE Trans. Info. Th., 1978\n\n[2] C. T. Li and A. E. Gamal, \"Strong Functional Representation Lemma and Applications to Coding Theorems,\" in IEEE Trans. Info. Th., 2018\n\n[3] C. T. Li and V. Anantharam, \"A Unified Framework for One-Shot Achievability via the Poisson Matching Lemma,\" in IEEE Trans. Info. Th., 2021\n\n[4] D. Wingate, M. Shoeybi, and T. Sorensen. \"Prompt compression and contrastive conditioning for controllability and toxicity reduction in language models.\" arXiv:2210.03162 (2022)\n\n[5] W. Fei, et al. \"Extending context window of large language models via semantic compression.\" arXiv:2312.09571 (2023)", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZAsDNcFQDp", "reviewer": "Reviewer_Jydp", "summary": "The paper studies the distortion-rate function for prompt compression and proposes an linear programming based algorithm that produces compressed \"hard\" prompts and is suitable for black box models. The authors provide empirical results on a synthetic dataset illustrating a gap between the existing prompt compression approaches and the theoretically optimal distortion-rate tradeoff and show that the proposed algorithm outperforms the existing methods.", "questions": "In addition to the questions above, out of curiosity, do the authors expect any challenges when the compressor is conditioned on multiple queries?", "limitations": "The authors mention limitations in the last section.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides sufficient detail on related work and motivates the problem well. \n\n- The proposed distortion-rate formulation is simple yet easy to understand/interpret. It also allows for query-adaptive solutions with simple modifications to the formulation. \n\n- The empirical results on the synthetic dataset demonstrate the improvements over existing prompt compression methods, which are provably (since the dataset is synthetic) worse than the optimal compressor.", "weaknesses": "- It would be great to see some experimental results with real datasets.\n\n- What is the reason that the rate is normalized but the distortion is not? Have the authors tried different combinations? \n\n- How does the efficiency of the proposed method compare with existing prompt compression methods? Did the authors compare how long each method takes to compress the same prompt?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments and constructive feedback. We provide our response to the reviewer’s individual comments here, and strongly encourage the reviewer to check our global response for updates regarding our new natural language experiments, which is also relevant to the reviewer’s comments. Please find our response to the questions below:\n\n* **Real (natural language) datasets**:  We include two new experiments on natural language data in the global response.\n\n* **Normalization**: Normalizing the distortion in the same sense as the rate could, in theory, be done by defining the distortion to be $\\mathbb{E}\\left[ \\frac{\\mathsf{d}(Y, \\phi_{\\text{LLM}}(M,Q))}{\\mathsf{d}(Y, \\phi_{\\text{LLM}}(X,Q))}\\right]$. However, this is not reasonable in practice since $\\mathsf{d}(Y, \\phi_{\\text{LLM}}(X,Q))$ is usually small (in fact, they are often 0 for the 0/1 loss plots), leading to very large normalized distortion values. A different way to normalize would be to subtract the distortion of the uncompressed prompt, but this would only shift the plots such that the line corresponding to “No Compression” in our plots is at 0. This provides less information than our plots, since we then no longer know how much the “No Compression” distortion is. \nOne might also ask whether it is possible to use the rates without normalization, i.e., just using $\\mathbb{E}[\\mathrm{len}(M)]$ or $\\frac{\\mathbb{E}[\\mathrm{len}(M)] }{ \\mathbb{E}[\\mathrm{len}(X)] }$ instead of $\\mathbb{E}\\left[\\frac{\\mathrm{len}(M)}{\\mathrm{len}(X)}\\right]$. None of these choices are right or wrong, as they capture slightly different nuances of compression. Choosing the appropriate normalization for a given scenario is certainly an important problem, as pointed out by the reviewer. The key point here is that all these cases can be handled by our framework, by simply changing the associated definitions of rate and distortion to be normalized or unnormalized as needed. Algorithm 1 can still be used to compute the optimal curve, by appropriately redefining the quantities $\\boldsymbol{R}_x$ and $\\boldsymbol{D}_x$.\n\n* **Efficiency**: The efficiency of our methods is the same as the efficiency of LLMLingua-2, which is faster than LLMLingua methods and Selective Context. The following shows the average time it takes each method to compress a a prompt from our small natural language dataset:\n| Compression method | Time (seconds) |\n| --------- | -----------: |\n| Selective Context | 0.049 |\n| LLMLingua | 0.273 |\n| LLMLingua Query | 0.530 |\n| LLMLingua-2 | 0.044 |\n| LLMLingua-2 Query | 0.043 |\n| LLMLingua-2 Dynamic | 0.044 |\n\n    We are not able to provide the timings for the NarrativeQA dataset since we had to distribute those experiments across machines with differing hardware (which yields an unfair timing comparison) in order to ensure the results were complete before the rebuttal deadline. We thank the reviewer for this suggestion. We agree that reporting the timings/efficiency of the compression methods is useful, and we will include a table for the timings on NarrativeQA, in addition to our small natural language dataset, in the final revision.\n\n* Additional question, **multiple queries**: As far as computing the optimal curve using Algorithm 1 goes, there is no new difficulty when there are multiple queries to condition on. These can all be clubbed into a new “mega-query” $Q’$, and all of the theory follows, replacing $Q$ by $Q’$.  Naively, this approach may also be used with existing prompt compression methods, where all queries of interest are concatenated together. We expect that this may work well if the compressor is trained to accept multiple queries. Currently, all query-aware compressors are trained for a single query, and we are skeptical if they will work well without additional training.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7xUxzPkSVj", "reviewer": "Reviewer_sxbS", "summary": "The paper formulates hard prompt compression as a rate-distortion problem. An algorithm is provided for hard prompt compression, as well as another to estimate the RD curve (Algorithm 1). Experiments on synthetic as well as benchmark datasets are provided with comparisons to previous methods.\n\nNote:\n- I'm more than willing to change my score significantly if the questions are addressed appropriately.\n- I don't know much about LLMs.\n- I'm not familiar with previous literature on prompt-compression.\n- I'm familiar with convex optimization, but it's hard to evaluate the correctness or novelty of Algorithm 1.\n- I'm familiar with info theory in general.", "questions": "> Line 261: \"taking $P_{XQY}$ to be the empirical distribution on the dataset\"\n\nIf the empirical distribution is used in the RD formulation, isn't this just overfitting to the sample?\n\n> Line 108 and Equation (1)\n\nI don't understand why the log-loss, or 0/1 loss, under the LLM is a reasonable distortion function to measure semantic distortion. Please see \"Weakness\" section.", "limitations": "There's a large limitations section in the appendix which I appreciate.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Overall the paper is very well written. I was able to follow everything to a reasonable degree even without knowing much about LLMs.\n- The paper takes a principled approach, through the lens of info theory, to prompt-compression to investigate fundamental limits.\n- The overall conclusion points towards a space for improvement in current methods (summarized in Figure 1.), with the caveats mentioned in the questions/weakness.", "weaknesses": "- The synthetic data is very limited as it has a binary support (although this is highlighted in as a limitation in the appendix).\n- The gold standard for the distortion functions, as far as I understand, would be to have a distortion function that is low when two sentences have \"the same meaning\", as measured by humans, and high otherwise. Of course, this is function doesn't exist (as far as I know). It isn't obvious why the chosen distortion metrics (i.e., log-loss and 0/1) capture \"semantics\" as originally intended by the authors.\n\nSmaller issues\n- Line 123: notation for a pair of objects inconsistent with the previous parts of the text (i.e., used $[M, Q]$ instead of $(M, Q)$)\n- Line 147: typo, \"taken with respect\" -> \"taken with respect to\"\n- Line 158: typo, \"The dimensions of problem\" -> \"The dimensions of the problem\"\n\nSuggestions (this is conditioned on there being reasonable explanations for the questions in the Questions section): \n- I would suggest focusing the paper more about the empirical results and why the RD formulation makes sense for this problem (the ML community is not too familiar with info theory, so the formulation itself is a contribution in my opinion).\n- The entirety of section 3.3 is not too important for the story and could be entirely moved to the appendix. Instead, replace 3.3 with a discussion as to why this RD formulation captures the \"rate-semantics\" trade-off originally intended by the authors, by providing evidence that the distortion functions proposed can actually measure semantic distortion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading of the paper and constructive suggestions and feedback. We provide our response to the reviewer’s individual comments here, and strongly encourage the reviewer to check our global response for updates regarding our new natural language experiments, which is also relevant to the reviewer’s comments. Please find our response to the questions below:\n\n* **Limited dataset**: We include two new experiments on natural language data in the global response.\n* **Choice of distortion metric**:  Indeed, the proper choice of distortion function is important to meaningfully measure the change in performance (distortion) of the LLM as the rate is varied. Ideally, a distortion metric as described by the reviewer (“low distortion” for sentences with the “same meaning,” as measured by humans) is the gold standard, but this metric is not known. This is very much a crucial open problem for not just our work, but for fair benchmarking of LLMs in general.\n\n    * **0/1 loss for synthetic dataset**: For our synthetic dataset consisting of binary strings, the 0/1 loss is the best. This is because (1) the answers are numerical or binary answers, so there is no notion of semantic relatedness between two answers, and (2) the answers are single tokens, so the most practical thing is to check for an exact match between the answers. We also include the log loss metric to include some diversity in our evaluations. Although the structure of the curves are different, the relative ordering of the curves and their trends are very similar to the curves in the 0/1 loss plot.\n\n    * **rougeL and BertScore: Semantic distortion metric for natural language datasets**: For our new results on natural language, we report our results using these (or rather, “$1-$” these, since these are similarity metrics and we want a low distortion to mean high similarity):. rougeL is a common metric used to evaluate summaries, which does so by computing the precision and recall of the tokens in the generated and reference texts, while BertScore computes contextualized embeddings for the tokens and uses the pairwise cosine similarity among them to produce the final score. The authors of the BertScore work highlight that their metric correlates better with human judgements than all other metrics (rougeL included) [1]. Regardless, our results with these two metrics are in agreement with each other, suggesting that a “good enough” metric may be sufficient. A popular approach in current literature is to ask GPT4 to give a score on the similarity between generated and reference texts. Although it has been shown that humans agree with GPT4’s evaluation more than the evaluation of other humans [2], we are skeptical of this metric because it is not reproducible and GPT4 has biases which may result in unfair or inaccurate evaluations. Additionally, we would also like to mention that our theoretical framework is general and does not assume any specific distortion function. In particular, it can also be used with new distortion functions that better capture semantic notions, when they are discovered in the future.\n\n* **Discussion of rate-semantic trade-offs in Section 3.3**: \n    * We thank the reviewer for this suggestion. We will add a discussion on the semantic metrics (as in the answer above) together with our NLP experimental results in the revised manuscript. \n    * We maintain that Section 3.3 is important because our primal and dual LP formulations, particularly Algorithm 1, not only form the basis of our theoretical contributions by allowing us to compute the optimal curve efficiently but also demonstrate that our theoretical results hold for any distortion metric, including those designed to capture distortion in the semantic space.\n\n* **Re: If the empirical distribution is used in the RD formulation, isn't this just overfitting to the sample?**: Firstly, we would like to mention that our theoretical framework allows for any choice of the distribution, and Algorithm 1 can still be used to compute the optimal curve with that choice of the distribution. \n\n    * We choose the empirical distribution since it is the most natural choice when the distribution is unknown and we are only given a dataset. This is also how other works computing information-theoretic limits of compression in various settings approximate the underlying distribution ([33, 34] in our paper).\n\n    * Alternatively, one might assume a parametric distribution and try to learn the parameters from the dataset. However, it is unclear what the right parametric model for text (particularly LLM prompts) should be.\n\n     * It is true that a very small number of samples (i.e., when the dataset is not a good representation of the true distribution) can lead to an optimal compressor that overfits. In our experiments on synthetic prompts, we observe that LLMLingua-2 Dynamic nearly matches the optimal curve for some rates. Had the optimal compressor significantly overfit to the dataset, optimality would not have been achieved (although this is not a necessary condition). This suggests that with a sufficiently large dataset, the empirical distribution is a good enough approximation.\n\n    * Finally, in each of our plots, we compare all compression schemes to the optimal curves by evaluating them on the same dataset, so the comparison is fair.\n\n    This is indeed an interesting problem, and we will add a discussion highlighting the choice of distribution in the revised manuscript.\n___\n**References**:\n\n[1] Tianyi Zhang*, Varsha Kishore*, Felix Wu*, Kilian Q. Weinberger, & Yoav Artzi (2020). BERTScore: Evaluating Text Generation with BERT. In International Conference on Learning Representations.\n\n[2] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, & Chelsea Finn (2023). Direct Preference Optimization: Your Language Model is Secretly a Reward Model. In Thirty-seventh Conference on Neural Information Processing Systems.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for acknowledging our contributions and providing constructive feedback. Our ***key contributions*** lie in providing a principled framework for prompt compression (as acknowledged by Reviewers cHot and sxbS), showing a large gap between optimality and current schemes (as acknowledged by Reviewers Jydp and sxbS). We are able to do so by formulating the optimal curve as a linear program that can be solved using an efficient, geometric solution via its dual in Algorithm 1. This is nontrivial as the linear program itself has too large a dimension to solve directly. We also propose compression schemes that outperform current schemes on synthetic datasets.

We highlight some of the ***additional experiments*** we ran to address the reviewers’ concerns, which include results on (1) a small-scale dataset with natural language prompts to compare with the optimal compressors on natural language, and (2) a larger scale dataset, NarrativeQA, as suggested by reviewer cHot.

1. **NLP dataset**: We prompt GPT4 to curate a small-scale natural language dataset consisting of short prompts (no more than 15 tokens in length), queries, and their respective answers (some examples from the dataset are shown in Table 1 in our attached PDF). We will include details on the dataset in the final revision of the paper.  We are also able to compute the optimal curve for this small NLP dataset, using the “pruning” approximation described in Appendix E of the paper. Please see Figure 1 in our attached PDF for the results of this experiment. Our key observations are (1) the gap between the optimal prompt compressors and current methods is quite large, (2) Our proposed methods achieve the lowest distortion for rates below 0.5, and (3) with prompt compression, it is possible to do better than standard prompting as shown by the gap between the optimal curves and the “No Compression” result. All of these observations are in line with our experiments on binary sequences.

2. **Extension to a larger scale NLP dataset** (suggested by Reviewers cHot, Jydp, and sxbS): As per the suggestion of Review cHot, we use the summaries provided in the NarrativeQA [1] datasets as the prompts (up to several hundred tokens), and the queries in the dataset accordingly. The result of this experiment is shown in Figure 2 in our attached PDF.
    * Comparison of constructive algorithms: Similar to the result of the small natural language dataset, we observe that our proposed methods again perform better than all other methods for rates less than 0.5. 
    * As discussed in item 3 below, it is not feasible to compute the curves for the optimal prompt compressors on this (or any other) large scale dataset. As such, we view this experiment to be complementary to the experiment discussed in item 1 above.

3. **Fundamental characteristics of the optimal curve computation**:  A key observation is that Algorithm 1 can be used to compute the optimal curve even for practical datasets, since it only has a linear complexity in the length of the prompt. The difficulty when assuming black-box models is that we need to make an inference call with each possible compressed prompt to compute its distortion, resulting in an exponential complexity in the length of the prompt. This cannot be avoided without further understanding the structure of language models or making some assumptions on their statistical properties. We leave such considerations, including methods to approximate the optimal curve for larger datasets, for future work.

___
**References**:

[1] Kočiský, Tomáš, et al. "The NarrativeQA Reading Comprehension Challenge." Transactions of the Association for Computational Linguistics 6 (2018): 317-328.

Meta-review: The paper provides an interesting rate-distortion framework for fundamental limits of prompt compression for large language models. The reviewers all agree the contribution and novelty. Please make sure to include the new experiments and the table in the camera ready version.
Decision: Accept (poster)