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.
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?
The 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]).
[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).
[2] Fei, Weizhi, et al. "Extending context window of large language models via semantic compression." arXiv preprint arXiv:2312.09571 (2023).
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.
2. In the query-aware setting, if query is provided, then why not compress the answer directly, so the optimal rate would be a constant?
3. 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?
4. In Proposition 1, what do you mean by $\mathbb{R}_+^{\mathcal{M}_x}?$ $\mathcal{M}_x\subseteq \mathcal{V}^*$ right?
5. 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.
6. 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?
7. Could you provide comparisons to other baselines such as [1] and [2]?
8. Could you conduct experiments on other public datasets, such as the NarrativeQA dataset?