LongLLMLingua: Accelerating and Enhancing LLMs in Long Context Scenarios via Prompt Compression

Introduction

ChatGPT and other large language models (LLMs) have revolutionized user-oriented language technologies and are serving as crucial components in more and more applications. Carefully designing prompts is necessary to achieve better performance in specific downstream tasks. The commonly used technologies such as In-Context Learning (ICL) (Dong et al., 2023), Retrieval Augment Generation (RAG) (Lewis et al., 2020), and Agent (Park et al., 2023) are driving prompts to be increasingly longer, even reaching thousands of tokens. Scenarios such as multi-document question answering, code completion, and document summarization also necessitate the processing of long contexts.

There are three main challenges when LLMs are used in long context scenarios: (1) The higher computational and financial cost required to run these models or to call APIs from companies providing LLM services. This can be a significant barrier for individuals or smaller organizations with limited resources. (2) The longer latency associated with LLMs, which can cause delays in generating responses or predictions and is particularly problematic in real-time scenarios where users expect quick and accurate responses. (3) The inferior performance caused by the extended window size of LLMs (Xiong et al., 2023), and the low density as well as the less sensitive position of the question-relevant key information in the prompt. Figure 1a shows that LLMs’ performance in downstream tasks may decrease as the noisy information in the prompt increases (Shi et al., 2023). Moreover, the purple curve in Figure 1b indicates that LLMs’ ability to capture the relevant information depends on their positions in the prompt (Liu et al., 2023): they achieve the highest performance when relevant information occurs at the beginning or end of the input context, and significantly degrades if relevant information is located in the middle of long contexts.

Inspired by these observations, we propose LongLLMLingua to address the three challenges. Specifically, we use the advanced while efficient LLMLingua (Jiang et al., 2023a) as our backbone framework for prompt compression to address the first two challenges, i.e., reduce cost and latency. However, in the case of long contexts, the distribution of question-relevant key information in the prompt is generally sparse. Existing prompt compression methods like LLMLingua (Jiang et al., 2023a) and Selective-Context (Li, 2023) that do not consider the content of the question during compression may retain too much noisy information in the compressed results, leading to inferior performance. In this paper, LongLLMLingua is designed to enhance LLM’s perception of key information (relevant to the question) in the prompt, so that the third challenge of inferior performance in long context scenarios could be addressed. Figure 1b is an example. The underlying principle of LongLLMLingua is that small language models are inherently capable of capturing the distribution of key information relevant to a given question.

Our main contributions are five-fold: (1) We propose a question-aware coarse-to-fine compression method to improve the key information density in the prompt (Sec. 4.1); (2) We introduce a document reordering mechanism to reduce information loss in the middle. (Sec. 4.2); (3) We present dynamic compression ratios to bridge the coarse-grained compression and fine-grained compression for adaptive granular control (Sec. 4.3); (4) We propose a post-compression subsequence recovery strategy to improve the integrity of the key information (4.4). (5) We evaluate LongLLMLingua on three benchmarks, i.e., NaturalQuestions (Liu et al., 2023), LongBench (Bai et al., 2023), and ZeroSCROLLS (Shaham et al., 2023). Experimental results demonstrate that compared with original prompts, LongLLMLingua compressed prompts can achieve higher performance with much lower costs. The latency of the end-to-end system is also reduced.

Problem Formulation

Following LLMLingua (Jiang et al., 2023a), we use $\mathbf{x}=(\mathbf{x}^{\text{ins}},\mathbf{x}^{\text{doc}}_{1},\cdots,\mathbf{x}^{\text{doc}}_{K},\mathbf{x}^{\text{que}})$ to represent a prompt, which composed of the instruction $\mathbf{x}^{\text{ins}}$, $K$ documents $\mathbf{x}^{\text{doc}}_{k}$, and the question $\mathbf{x}^{\text{que}}$. In fact, the prompt can be modified according to specific application scenarios. For example, $\mathbf{x}^{\text{ins}}$ at the beginning can be removed, $\mathbf{x}^{\text{que}}$ can be any requirement specified by users, and $(\mathbf{x}^{\text{doc}}_{1},\cdots,\mathbf{x}^{\text{doc}}_{K})$ can be any additional materials that users append to the prompt to get a better response from LLMs for $\mathbf{x}^{\text{que}}$. The objective of a prompt compression system can be formulated as:

where $\widetilde{\mathbf{x}}$ denotes the compressed prompt and is a token-level subsequence of $\mathbf{x}$. $\mathbf{y}$ represents the ground-true output texts with $\mathbf{x}$ as the input and $\widetilde{\mathbf{y}}$ represent the LLM-generated results derived by $\widetilde{\mathbf{x}}$. $D$ is a distance measure between two distributions, such as KL divergence. We expect the distribution of $\mathbf{y}$ and $\widetilde{\mathbf{y}}$ to be as similar as possible. $\lambda$ is a trade-off hyper-parameter regarding the compression ratio. In this work, we additionally incorporate an operation space of permutation over the $K$ documents $(\mathbf{x}^{\text{doc}}_{1},\cdots,\mathbf{x}^{\text{doc}}_{K})$ for joint optimization.

Preliminary: LLMLingua

LLMLingua (Jiang et al., 2023a) uses a small language model $\mathcal{M}_{S}$ to calculate the perplexity of each token in the original prompt and then removes tokens with lower perplexities. The rationale behind this approach is that tokens with lower perplexities contribute less to the overall entropy gain of the language model, so removing them will have a relatively minor impact on the LLM’s comprehension of the context. LLMLiungua consists of three components: a budget controller, an iterative token-level prompt compression algorithm, and a distribution alignment mechanism, as shown by Italic texts in Figure 2. The budget controller allocates different compression ratios to the various components in the original prompt (i.e., instruction, demonstrations, question), and performs coarse-grained compression at the demonstration level. The intermediate results are divided into segments and the token-level compression is then performed segment by segment, with the perplexity of each token conditioned on previous compressed segments calculated by $\mathcal{M}_{S}$. For distribution alignment, it performs instruction tuning on $\mathcal{M}_{S}$ with the data generated by the target LLM to narrow the gap between the distribution of LLM and that of $\mathcal{M}_{S}$ used for prompt compression.

LongLLMLingua

LongLLMLingua is developed upon the framework of LLMLingua towards prompt compression in long context scenarios. The primary challenge in long context scenarios is how to enhance LLM’s perception of key information relevant to the question in the prompt. LongLLMLingua addresses this challenge from three perspectives, and further applies a subsequence recovery strategy to improve the accuracy and reliability of the information provided to users. We elaborate on each component in this section.

In coarse-grained compression, we aim to figure out a metric $r_{k}$ to evaluate the importance of each document $\mathbf{x}^{\text{doc}}_{k}=\{x_{k,i}^{\text{doc}}\}_{i=1}^{N_{k}}$, where $N_{k}$ is the number of tokens in $\mathbf{x}^{\text{doc}}_{k}$. We only keep $\mathbf{x}^{\text{doc}}_{k}$ with higher $r_{k}$ as the intermediate compressed results.

LLMLingua uses document-level perplexity to represent the importance of documents: $r_{k}=1/N_{k}\sum_{i}^{N_{k}}p(x_{k,i}^{\text{doc}})\log p(x_{k,i}^{\text{doc}}),k\in\{1,2,\cdots,K\}$. Although the retained documents typically contain a lot of information, they are irrelevant to the question $\mathbf{x}^{\text{que}}$ and instead become noise, reducing key information density in the compressed results and bringing difficulties for LLM to output correct answers. As shown in Figure 3a, the recall@16 of LLMLingua only reaches 50%, indicating its incompetence in retaining key information during compression.

Retrieval-based methods are also feasible here. We can use $\mathbf{x}^{\text{que}}$ to retrieve the most relevant documents among $(\mathbf{x}^{\text{doc}}_{1},\cdots,\mathbf{x}^{\text{doc}}_{K})$ as the compressed results. However, these methods struggle to distinguish question-related fine-grained semantic information. Some documents with key information may be discarded during retrieval. As shown in Figure 3a, embedding-based methods such as Sentence BERT and OpenAI Embedding only achieve $\sim$75% accuracy in recall@5, which implies that the final accuracy upper bound of LLMs with 4x compression is only 75%.

One approach to improve key information density in the compressed results is to calculate document-level perplexity conditioned on the question $\mathbf{x}^{\text{que}}$. However, this method may not be effective because documents often contain a significant amount of irrelevant information. Even when conditioned on $\mathbf{x}^{\text{que}}$, the perplexity scores computed for entire documents may not be sufficiently distinct, rendering them an inadequate metric for document-level compression. Therefore, we propose to use the perplexity of the question $\mathbf{x}^{\text{que}}$ conditioned on different contexts $\mathbf{x}^{\text{doc}}_{k}$ to represent the association between them. We append a restrictive statement $\mathbf{x}^{\text{restrict}}$Specifically, “We can get the answer to this question in the given documents”. after $\mathbf{x}^{\text{que}}$ to strengthen the interconnection of $\mathbf{x}^{\text{que}}$ and $\mathbf{x}^{\text{doc}}_{k}$. It can be regarded as a regularization term that mitigates the impact of hallucinations. This can be formulated as:

where $x^{\text{que},\text{restrict}}_{i}$ is the $i$-th token in the concatenated sequence of $\mathbf{x}^{\text{que}}$ and $\mathbf{x}^{\text{restrict}}$ and $N_{c}$ in the number of tokens.

Figure 3a demonstrates that our coarse-level compression approach achieves the highest recall with different numbers of retained documents, suggesting that it preserves the most key information from the documents $(\mathbf{x}^{\text{doc}}_{1},\cdots,\mathbf{x}^{\text{doc}}_{K})$ in the compressed results.

Question-Aware Fine-Grained Compression

In fine-grained compression, we assess the importance of each token in the instruction $\mathbf{x}^{\text{ins}}$, the question $\mathbf{x}^{\text{que}}$, and $K^{\prime}$ documents $\{\mathbf{x}^{\text{doc}}_{i}\}_{i=1}^{K^{\prime}}$ retained after coarse-grained compression. We incorporate the iterative compression mechanism following LLMLingua and directly calculate token perplexities to compress $\mathbf{x}^{\text{ins}}$ and $\mathbf{x}^{\text{que}}$. In this section, we investigate how to make the fine-grained token-level compression over $\{\mathbf{x}^{\text{doc}}_{k}\}_{k=1}^{K^{\prime}}$ aware of the question $\mathbf{x}^{\text{que}}$, so that the compressed results could contain more question-relevant key information.

A straightforward solution for the awareness of $\mathbf{x}^{\text{que}}$ is to simply concatenate it at the beginning of the whole context. However, this will result in low perplexities of relevant tokens in the context following the condition, further reducing their differentiation from general tokens. In this paper, we propose contrastive perplexity, i.e., the distribution shift caused by the condition of the question, to represent the association between the token and the question. The contrastive perplexity based importance metric $s_{i}$ for each token $x_{i}$ in $\{\mathbf{x}^{\text{doc}}_{k}\}_{k=1}^{K^{\prime}}$ can be formulated as:

Figure 3b illustrates the difference between perplexities and contrastive perplexities. We can see that tokens of high perplexities are widely distributed in all documents. However, tokens with high contrastive perplexities concentrate more on the left side of the dashed line, which corresponds to the document that contains the answer to the question. This suggests that the proposed contrastive perplexity can better distinguish tokens relevant to the question, thus improving the key information density in the compressed results.

2 How to reduce information loss in the middle?

As demonstrated in Figure 1b, LLM achieves the highest performance when relevant information occurs at the beginning and significantly degrades if relevant information is located in the middle of long contexts. After the coarse-grained compression, we have obtained a set of documents $\{\mathbf{x}^{\text{doc}}_{k}\}_{k=1}^{K^{\prime}}$ with their corresponding importance scores $\{r_{k}\}_{k=1}^{K^{\prime}}$ indicating their association with the question $\mathbf{x}^{\text{que}}$. Therefore, we reorder documents using their importance scores to better leverage LLMs’ information perception difference in positions:

3 How to achieve adaptive granular control during compression?

In fine-grained compression, LLMLingua applies the save compression ratio over all documents obtained from coarse-grained compression. However, the key information density of different documents is different. The more relevant to the question a document is, the more budget (i.e., lower compression ratio) we should allocate to it. Therefore, we bridge coarse-grained compression to fine-grained compression and use the importance scores $\{r_{k}\}_{k=1}^{K^{\prime}}$ obtained from coarse-grained compression to guide the budget allocation in fine-grained compression. In this way, we can achieve adaptive granular control on the whole.

Specifically, we first determine the initial budget for the retained documents $\tau^{\text{doc}}$ In LLMLingua, it is $\tau^{\text{dems}}$ for demonstrations. using the budget controller of LLMLingua. During fine-grained compression, we follow the iterative token-level compression algorithm in LLMLingua but dynamically assign the compression budget $\tau_{j}^{\text{doc}}$ to each document $\mathbf{x}_{k}^{\text{doc}}$ according to the ranking index $I(r_{k})$ (e.g., 0, 1) of its importance score from the coarse-grained compression. In this paper, we employ a linear scheduler for the adaptive allocation. Budget of each token $x_{i}$ can be formulated as:

where $N_{d}$ denotes the number of documents, and $\delta\tau$ is a hyper-parameter that controls the overall budget for dynamic allocation.

4 How to improve the integrity of key information?

Certain tokens of key entities may be discarded during the fine-grained token-wise compression. For example, the time entity “2009” in the original prompt might be compressed to “209” and the name entity “Wilhelm Conrad Röntgen” might be compressed to “Wilhelmgen”. This can cause problems for fact-based tasks like document QA, where language models tend to replicate information from the prompt, as shown in Figure 4.

To improve the accuracy and reliability of the information provided to users, we propose a subsequence recovery method to restore the original content from LLMs’ responses. This method relies on the subsequence relationship among tokens in the original prompt, compressed prompt, and LLMs’ response. The overall procedure includes: i) Iterate through tokens $y_{l}$ in LLMs’ response and select the longest substring $\bm{\widetilde{y}}_{\text{key},l}=\{y_{l},y_{l+1},...,y_{r}\}$ that appears in the compressed prompt $\bm{\widetilde{x}}$. ii) Find the maximum common shortest subsequence $\bm{{x}}_{i,j}=\{x_{i},x_{i+1},...,x_{j}\}$ in the original prompt $\bm{x}$, corresponding to the representation $\bm{\widetilde{y}}_{\text{key},l}$ in the original prompt (accelerated using prefix trees or sequence automata). iii) Replace the matched tokens $\bm{\widetilde{y}}_{\text{key},l}$ in LLMs’ response with the corresponding subsequence $\bm{{x}}_{i,j}$ from the original prompt. For more details, please refer to Algorithm 1.

Experiments

Here, we investigate: (1) How effective is LongLLMLingua? (2) How efficient is LongLLMLingua?

In this paper, we use GPT-3.5-Turbo-0613For experiments with original prompts exceeding 4k tokens, we utilize GPT-3.5-Turbo-16k-0613. and LongChat-13B-16k as the target LLMs, both accessible via OpenAIhttps://platform.openai.com and HuggingFacehttps://huggingface.co/lmsys/longchat-13b-16k. To ensure stable and reproducible results, we employ greedy decoding and set the temperature to 0 in all experiments. For the small language models used for compression, we apply LLaMA-2-7B-Chathttps://ai.meta.com/llama/, which has been aligned by supervised fine-tuning and RLHF. We implement our approach with PyTorch 1.13.1 and HuggingFace Transformers. We set up hyperparameters following LLMLingua except for the segment size used in iterative token-level compression set to 200 here. More details are provided in Appendix B.

Dataset & Evaluation Metric

We use NaturalQuestions for the multi-document QA task, and use LongBench and ZeroSCROLLS for general long context scenarios.

(i) NaturalQuestions (Liu et al., 2023): This benchmark is similar to the retrieval-augmented generation setup in commercial search and question-answering scenarios like Bing Chat. Specifically, each question has 20 related documents in the original prompt. One of them contains the correct answer and there are five different ground truth document position settings in the prompt: 1st, 5th, 10th, 15th, and 20th. Following Liu et al. (2023), we use accuracy as the evaluation metric.

(ii) LongBench (Bai et al., 2023): This benchmark consists of six task types: single-document QA, multi-document QA, summarization, few-shot learning, code completion, and synthetic tasks. We used the English portion that covers 16 datasets for evaluation. We use the metrics and scripts provided along with the benchmark for evaluation.

(iii) ZeroSCROLLS (Shaham et al., 2023): This benchmark consists of four task types: summarization, QA, sentiment classification, and reordering, covering 10 datasets. We used the validation set for evaluation. We use the provided metrics and scripts for evaluation.

Baselines

We include two sets of baselines in following experiments:

(i) Retrieval-based Methods. We measure the association between the question and the documents in the prompt using five SoTA retrieval methods: BM25, Gzip (Jiang et al., 2023b), SentenceBERT (Reimers & Gurevych, 2019), OpenAI Embedding, and the important metric $r_{k}$ used in LongLLMLingua coarse-grained compression. We discard sentences or paragraphs with low association until the compression constraint is met while keeping the original document order unchanged.

(ii) Compression-based Methods. We compare our approach with two state-of-art methods for prompt compression, i.e., Selective Context (Li, 2023) and LLMLingua (Jiang et al., 2023a). Both methods employ LLaMA-2-7B-Chat as the small language model for compression. In LLMLingua, a coarse-to-fine approach is used to handle constraints of compression ratio: the original prompt is first compressed to $k$ times the constraint at a coarse level, where $k$ is the granular control coefficient; token-level is then performed to reach the overall constraint. Our method follows the same coarse-to-fine logic to achieve the constraint.

Main Results

Table 1 and 3 present the performance of various methods under different compression constraints. There are multiple observations and conclusions: (1) Our LongLLMLingua achieves the best performance across different tasks and constraints of compression ratios. Compared to the original prompt, our compressed prompt can derive higher performance with much less cost. For example, LongLLMLingua gains a performance boost of 17.1% on NaturalQuestions with the ground-true document at the 10th position, while the number of tokens input to GPT3.5-Turbo is $\sim$4x less. (2) Compression-based methods like Selective Context (Li, 2023) and LLMLingua (Jiang et al., 2023a) perform poorly on most tasks, especially those with abundant irrelevant information in the original prompt. This is due to their pure information entropy based compression mechanism, which includes too much noise in the compressed results and even leads to performance worse than the zero-shot setting, e.g., on NaturalQuestions. (3) Retrieval-based methods work well with low compression rates. However, their performance declines as the compression progresses, e.g., $2x\rightarrow 4x$; 3000 tokens $\rightarrow$ 2000 tokens. This may be caused by the decreased recall. Figure 3a is the illustration of cases on NaturalQuestions. (4) LongLLMLingua as well as our coarse-grained compression metric $r_{k}$ only is much more robust than all other baselines under different tasks and compression constraints. With the increase of the compression rate, e.g., $2x\rightarrow 4x$, LongLLMLingua even achieves a little performance gain. We mainly owe this to the question-aware coarse-to-fine compression, which can better figure out the key information and reach a higher key information density with a higher compression rate. (5) The proposed document reordering strategy helps in not only our approach but also other baselines as shown in Table 1, well demonstrating its effectiveness.

Ablation Study

To evaluate the contributions of different components in LongLLMLingua, we introduce six variants of it for ablation study: (1) Ours w/o Question-aware Coarse-grained, which calculates question-text relevance $r_{k}$ using information entropy in LLMLingua. (2) Ours w/ SBERT, which employs SBERT to compute $r_{k}$. (3) Ours w/o Question-aware Fine-grained, which disregards Eq. (3) and only applies Iterative Token-level Prompt Compression as LLMLingua. (4) Ours w/o Dynamic Compression Ratio, where all documents share the same compression ratio in fine-grained compression. (5) Ours w/o and (6) LLMLingua w/ Subsequence Recovery, which either removes or adds the post-processing subsequence recovery strategy.

Table 2 shows the results of the ablation study. In summary, removing any component proposed for LongLLMLingua will lead to a performance drop regardless of the position of the ground-truth answer. This well validates the necessity and effectiveness of the proposed question-aware mechanism during coarse-to-fine compression, the dynamic compression ratio, and the subsequence recovery strategy. It also shows that applying SBERT for coarse-grained compression will result in inferior performance, which implies the superiority of our question-aware importance metric in Eq. 2 over SBERT. Moreover, our subsequence recovery strategy can also bring performance gains for LLMLingua. However, without our question-aware mechanism, results from LLMLingua are still less satisfactory. For more detailed cases, please go to Appendix C.

Latency Evaluation

We conduct testing on a V100-32G GPU, using the prompts from LongBench with $\sim$10K tokens on average and setting the response length to 200 tokens in the API call. In Table 5, E2E denotes the latency from both the prompt compression system and the black-box API, while LongLLMLingua denotes the prompt compression latency only. It is shown that our prompt compression system does accelerate the overall inference. As the compression rate increases, the acceleration effect becomes more pronounced. It is worth mentioning that in scenarios with longer API cost time, the actual absolute time saved by LongLLMLingua can be more significant.

Related Works

Long Context for LLMs. Recent research has focused on expanding the window size of LLMs. Main approaches include: (1) Staged pre-training (Nijkamp et al., 2023) which gradually increases the context window; (2) Modifying (Press et al., 2022) or interpolating position embeddings (Chen et al., 2023; Peng et al., 2023; Han et al., 2023); (3) Using linear or sparse attention mechanisms (Ding et al., 2023; Sun et al., 2023); (4) Utilizing external memory modules for context storage (Bertsch et al., 2023; Tworkowski et al., 2023). While these methods address context window expansion, their impact on downstream task performance has yet to be discussed.

Information Distribution in Prompt. Recent empirical experiments have shown that LLM performance decreases with less effective information in a prompt (Bai et al., 2023; Li et al., 2023; Shi et al., 2023). Moreover, the position of relevant information in a prompt has a significant impact on performance(Wu et al., 2022). Liu et al. (2023) suggests that LLMs have more difficulty comprehending information located in the middle of a prompt compared to those at the edges.

Retrieval Methods can be categorized as dense or sparse retrieval methods. Sparse retrieval methods, like BM25, determine the relevance between queries and documents based on n-gram information. Conversely, dense retrieval methods assess the relevance between queries and documents in latent space using dense vectors, such as SentenceBERT (Reimers & Gurevych, 2019) and OpenAI Embedding. Recently, Jiang et al. (2023b)) proposed an unsupervised dense retrieval method that leverages traditional compression algorithms, such as gzip, and k-nearest neighbors.

Prompt Compression Methods can be grouped into three main categories: (1) Token pruning (Goyal et al., 2020; Kim & Cho, 2021; Modarressi et al., 2022) and token merging (Bolya et al., 2023), which need model fine-tuning or intermediate results during inference and have been used with BERT-scale models. (2) Soft prompt tuning methods like GIST (Mu et al., 2023), AutoCompressor (Chevalier et al., 2023), and ICAE (Ge et al., 2023), which require LLMs’ parameter fine-tuning, making them suitable for specific domains but not directly applicable to black-box LLMs. (3) Information-entropy-based approaches such as Selective Context (Li, 2023) and LLMLingua (Jiang et al., 2023a), which use a small language model to calculate the self-information or perplexity of each token in the original prompt and then remove tokens with lower perplexities.

Conclusion

We propose LongLLMLingua to address the three challenges, i.e., higher computational/financial cost, longer system latency, and inferior performance for LLMs in long context scenarios. We develop LongLLMLingua from the perspective of efficient prompt compression, thus reducing both computational/financial cost and the system latency. We further design four components, i.e., a question-aware coarse-to-fine compression method, a document reordering mechanism, dynamic compression ratios, and a post-compression subsequence recovery strategy to improve LLMs’ perception of the key information, with which LongLLMLingua demonstrate superior performance. Experiments on one multi-document QA benchmark and two long context benchmarks demonstrate that LongLLMLingua compressed prompt can derive higher performance than original prompts while both API costs for inference and the end-to-end system latency are largely reduced.

References

Appendix A Token-level Subsquence Recovery Details

Appendix B Experiment Details

A multi-document question-answering dataset, comprising 2,655 problems, was built by Liu et al. (2023) based on the NaturalQuestions dataset (Kwiatkowski et al., 2019). This dataset provides a realistic retrieval-augmented generation setup that closely resembles commercial search and question-answering applications (e.g., Bing Chat). Each example in the dataset contains a question and k related documents, utilizing the Contriever retrieval system (Izacard et al., 2022), one of which includes a document with the correct answer. To perform this task, the model must access the document containing the answer within its input context and use it to answer the question. The dataset’s data is sourced from the NaturalQuestions dataset, which contains historical queries issued to the Google search engine and human-annotated answers extracted from Wikipedia. The average prompt token length in this benchmark is 2,946. For our experiments, we used the version provided by Liu et al. (2023) that includes 20 documentshttps://github.com/nelson-liu/lost-in-the-middle. The dataset comprises five different ground truth document position settings in the prompt: 1st, 5th, 10th, 15th, and 20th.

LongBench

A multi-task long context benchmark consists of 3,750 problems in English and includes six categories with a total of 16 tasks. These tasks encompass key long-text application scenarios, such as single-document QA, multi-document QA, summarization, few-shot learning, synthetic tasks, and code completion. The average prompt token length in this benchmark is 10,289. For our experiments, we used the English dataset and evaluation scripts provided by Bai et al. (2023) for this benchmarkhttps://github.com/THUDM/LongBench.

ZeroSCROLLS

The multi-task long context benchmark consists of 4,378 problems, including four categories with a total of 10 tasks. These tasks cover summarization, question answering, aggregated sentiment classification, and information reordering. The average prompt token length in this benchmark is 9,788. For our experiments, we used the validation set and evaluation scripts provided by Shaham et al. (2023) for this datasethttps://www.zero.scrolls-benchmark.com/.

B.2 Other Implementation Details

All experiments were conducted using a Tesla V100 (32GB). We use tiktokenhttps://github.com/openai/tiktoken and GPT-3.5-Turbo model to count all the tokens. We set the granular control coefficient $k$ to $2$. We use the pre-defined compression rates $\tau_{\text{ins}}=0.85$ and $\tau_{\text{que}}=0.9$ for instructions and questions. The segment size used in the iterative token-level compression is set to $200$. The $\delta\tau$ used in dynamic compression ratio is set to 0.25. For a fair comparison, we only used reordering in the NaturalQuestions Multi-document QA and noted this in Table 1. We use “We can get the answer to this question in the given documents.” as the guideline sentence in Equation (3).

For the baselines experiment, we use the currently recommended strongest model, all-mpnet-base-v2https://www.sbert.net/docs/pretrained_models.html, as the dense representation model for SentenceBERT. We use the recommended “text-embedding-ada-002” as the embedding model for OpenAI Embeddinghttps://platform.openai.com/docs/guides/embeddings/.

Appendix C Ablation Analysis

Appendix D Economic Cost

Table 7 presents the estimated per 1,000 samples inference costs for various datasets, encompassing input prompts and generated output text, based on GPT-3.5-Turbo pricinghttps://openai.com/pricing. Our approach demonstrates substantial savings in computational resources and monetary expenses, particularly in long context situations. Cost reductions of $3.3,$28.5, and $27.4 per 1,000 samples are observed for Multi-document QA, LongBench, and ZeroScrolls, respectively.

Appendix E Cases Study