Lossless Token Sequence Compression via Meta-Tokens
John Harvill, Ziwei Fan, Hao Wang, Yizhou Sun † \dagger, Hao Ding, Luke Huan, Anoop Deoras · 2025
Read Lossless Token Sequence Compression via Meta-Tokens by John Harvill, Ziwei Fan, Hao Wang, Yizhou Sun † \dagger, Hao Ding, Luke Huan, Anoop Deoras (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00307.txt.
Introduction
John Harvill and six co-authors squeeze token sequences for language models without losing a single token, in a 2025 arXiv paper. Most prompt squeezers drop information on purpose, gambling that what stays will serve the task. Their method instead borrows an old data trick, in the spirit of LZ77, that swaps repeats for short codes and can be undone exactly.
On two tasks picked for their need for exact wording, the squeeze cut sequence length by about a quarter and a fifth. Since model attention cost grows with the square of length, computing fell by nearly half and a third. Scores dipped only slightly against unsqueezed input. Lossy rivals fared badly on these exacting tasks, which the authors say shows the worth of keeping every bit.
Catalog record
| CREATOR | John Harvill, Ziwei Fan, Hao Wang, Yizhou Sun † \dagger, Hao Ding, Luke Huan, Anoop Deoras |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-00307
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lossless Token Sequence Compression via Meta-Tokens John Harvill, Ziwei Fan, Hao Wang, Yizhou Sun † \dagger, Hao Ding, Luke Huan, Anoop Deoras Abstract Existing work on prompt compression for Large Language Models (LLM) focuses on lossy methods that try to maximize the retention of semantic information that is relevant to downstream tasks while significantly reducing the sequence length. In this paper, we introduce a task-agnostic lossless compression technique similar to LZ77 that makes it possible to reduce the input token sequence length on average by 27% and 18% for the two evaluation tasks explored here. Given that we use transformer-based LLMs, this equates to 47% and 33% less encoding computation, respectively, due to the quadratic nature of attention. The token sequence transformation is trivial to reverse and highlights that no semantic information is lost in the process. We evaluate our proposed approach on two tasks that require strict preservation of semantics/syntax and demonstrate that existing lossy compression methods perform poorly in this setting. We find that our lossless compression technique produces only a small gap in performance compared to using the uncompressed input and posit that larger models and an expanded computing budget would likely erase the gap entirely. 1 Introduction The past several years have led to an adoption of generative language models at an unprecedented scale. As these models grow in terms of parameters and dataset size, new abilities continue to be unlocked. Large Language Models (LLM) are becoming better reasoners Wei et al. 2022 ; Shao et al. 2024 ; Zhang et al. 2024b ; Guan et al. 2025 ; Pan et al. 2024a and are changing how people write Levine et al. 2024 , code Tian et al. 2023 , and search Spatharioti et al. 2023 . Given that LLMs will likely play an ever-increasing role in our lives, the cost of token usage and inference requirements become critical factors for widespread use. As models scale, so does computational cost. For example, the recent paradigm shift of transferring training compute to inference compute has led to significant performance gains on problem-solving tasks Snell et al. 2024 at the expense of latency and token usage through additional LLM calls needed to search the solution space. One way to combat increased cost/latency is prompt compression, where the goal is to maintain necessary information for a downstream task while simultaneously reducing input sequence length. There has been a recent surge in research on prompt compression that covers a variety of different modeling conditions. Some approaches seek to optimize prompts under the condition that the LLM’s parameters are not accessible Jiang et al. 2023a ; Jiang et al. 2023b ; Pan et al. 2024b ; Chuang et al. 2024 . Others focus on the gains that can be made via architectural changes to the underlying LLM and continuing to fine-tune using compression Mu et al. 2024 ; Chevalier et al. 2023 ; Ge et al. 2023 . While previous works have been able to compress input sequences to a small fraction of their original length Jiang et al. 2023a ; Pan et al. 2024b , the downstream tasks explored in these works inherently allow for significant prompt compression due to the sparsity of information required to solve each task. For example, in passage-based Question Answering (QA), the answer to the question is usually contained within a small span of text, making the other information unnecessary. As we will demonstrate, for tasks where every part of the input contains important information, any amount of lossy compression can lead to the inability of an LLM to solve the task. Figure 1 : Example of swapping repeated subsequences with meta-tokens in a Python code snippet. Each unique meta-token is paired with a unique subsequence to form the dictionary, which is prepended to the compressed input. The green box represents spacing. We explore two tasks to demonstrate this idea, and there are numerous practical scenarios in which preservation of all text characters is necessary for proper sequence understanding. These include essay/email editing, code translation, Code Reasoning Understanding and eXecution (CRUX) Gu et al. 2024 , code repair, and unit test generation. Our approach to compression is lossless and task-agnostic, making it attractive for general use cases. Our main contribution is the proposal of L ossless T oken S equence C ompression ( LTSC ). The key idea behind LTSC is that there are many repetitions of multi-token subsequences in long prompts which makes the representation of any given subsequence inefficient (see Figure 1 ). By replacing each instance of a repeated subsequence with a single meta-token, we can reduce the total sequence length. To indicate the mapping of the meta-token to the original subsequence, we can construct a dictionary of meta-token/subsequence pairs and prepend the dictionary to the compressed prompt. We use the term “meta-token” to indicate that these tokens function as placeholders and can dynamically represent different token subsequences for each prompt. We will demonstrate that fine-tuning on tasks with this compression format teaches the LLM to understand how meta-tokens replace instances of their corresponding subsequence in the original sequence, which allows token sequences to be compressed without any loss of information. Additionally, our proposed approach is flexible in that the choice of whether to apply compression can be made at inference time, and the only model architecture change needed is adding a relatively small number of vocabulary tokens (meta-tokens). 2 Related Work There exists a large body of work on prompt compression, which is covered extensively in the survey paper from Li et al. 2024a . Prompt compression can be used to lower costs by reducing Figure 2 : Compression amounts by sequence length for Natural Language (NL) and code domains with two tokenizers (Qwen: Qwen2.5-Coder, SC: StarCoder2). token usage, improve generation latency, or make information denser under a fixed context length budget. Some existing work allows control over how much the prompt is compressed Jiang et al. 2023a ; Pan et al. 2024b , but for our proposed approach, the maximum amount of compression for a given prompt depends on the prompt itself. In this paper, we compare existing work to ours when maximally compressing every prompt and leave optimization under different use cases (fixed budget, latency, etc.) to future work. We provide a cursory overview of prompt compression in this section, with a more exhaustive discussion left to Appendix A . We note that, to the best of our knowledge, we are the first to propose lossless compression for prompting. Throughout the paper, we will use the terms "compression rate" and "compression amount", where amount A refers to the fraction by which the sequence length is reduced, i.e. A=1-|T^{{}^{\prime}}|/|T| where T^{{}^{\prime}} is the compressed version of token sequence T , 1 1 1 The sequence format we propose includes an instance-specific dictionary of compression pairs and the compressed sequence. Throughout the paper, when discussing the amount of sequence length reduction, the dictionary length is included in the calculation of the compressed sequence length. and compression rate R=1-A . Hard Prompt Compression methods are limited to using tokens solely from the original LLM vocabulary Li et al. 2023 ; Zhang et al. 2024a ; Jung and Kim 2024 ; Shandilya et