PaperlayerView exact revision on arXiv

Source-linked AI summary

LLMZip: Lossless Text Compression using Large Language Models

Chandra Shekhara Kaushik Valmeekam, Krishna Narayanan, Dileep Kalathil, Jean-Francois Chamberland, Srinivas Shakkottai

arXiv:2306.04050v2cs.ITcs.CLcs.LGmath.IT

TL;DR

The paper asks whether LLaMA-7B can provide sharper English entropy estimates and better lossless compression. It uses the model to predict tokens and combines those predictions with arithmetic coding. The reported text8 compression ratio is 0.7101 bits/character, with an entropy upper-bound estimate below earlier estimates.

  • Problem

    The paper examines whether recent large language models can improve English entropy upper-bound estimates and lossless compression, building on the dependence of compression performance on predictor quality.

    Source: §I · p. 1

  • Method

    The authors use LLaMA-7B to predict tokens from past tokens and combine its time-varying probabilities with arithmetic coding.

    Source: §III · p. 3, 3) Arithmetic Coding · p. 5

  • Results

    On 1MB of text8, LLaMA-7B with arithmetic coding achieves 0.7101 bits/character and is reported substantially better than state-of-the-art results, while its entropy upper bound is lower than earlier estimates.

    Source: §I · p. 1, §IV · p. 5

  • Takeaways & Limitations

    The reported results show that LLaMA-7B predictions can be used both to estimate an upper bound on English entropy and to compress English text with a lossless coder.

    Source: §I · p. 1, A. Entropy bounds · p. 4, 3) Arithmetic Coding · p. 5

    Compression-ratio estimates can vary with input text, and the LLaMA-7B comparison uses different input sizes because the model was not run on the full 100MB text8 dataset.

    Source: §IV · p. 5

Abstract

from arXiv · show

We provide new estimates of an asymptotic upper bound on the entropy of English using the large language model LLaMA-7B as a predictor for the next token given a window of past tokens. This estimate is significantly smaller than currently available estimates in \cite{cover1978convergent}, \cite{lutati2023focus}. A natural byproduct is an algorithm for lossless compression of English text which combines the prediction from the large language model with a lossless compression scheme. Preliminary results from limited experiments suggest that our scheme outperforms state-of-the-art text compression schemes such as BSC, ZPAQ, and paq8h.

I. INTRODUCTION

The paper studies whether LLaMA-7B can sharpen English entropy estimates and improve lossless compression. It reports a lower entropy upper-bound estimate than earlier work and better compression than named state-of-the-art systems in its experiments.

I. INTRODUCTION

  • Prediction has long been linked to compression, including Shannon’s English-entropy estimate and arithmetic coding with language models.Compression performance depends substantially on predictor quality, motivating tests of advances in language-model prediction.Source: §I · p. 1
  • The authors’ 2018 RNN-based approach improved results for certain sources but did not outperform BSC and ZPAQ for text compression [5].This motivates assessing whether newer LLaMA-7B predictions change compression performance.Source: §I · p. 1
  • Using LLaMA-7B, the authors estimate an English entropy upper bound of 0.709 bits/character on 1MB of text8, below earlier estimates, [2, Table 4].For 100KB of text from, the estimate is 0.85 bits/character and remains below estimates in.Source: §I · p. 1
  • LLaMA-7B with arithmetic coding achieves 0.7101 bits/character on 1MB of text8 and outperforms BSC, ZPAQ, and pq8h in the reported comparison.The comparison uses the compressors’ results on the full 100MB text8 dataset.Source: §I · p. 1

II. INTUITIVE EXPLANATION OF THE MAIN IDEA

The intuitive scheme tokenizes text, uses a language model to rank each actual next token, and losslessly compresses the resulting rank sequence. Decoding reverses the process with the same model, while the authors note that coding directly from model probabilities can improve compression.

II. INTUITIVE EXPLANATION OF THE MAIN IDEA

  • The example frames lossless compression as converting a sentence into the shortest bit sequence from which the original can be reconstructed.Its explanation follows Shannon’s idea, using variable-length word tokens and a language model to predict the next token.Source: §II · p. 1
  • With memory 4, the model ranks the actual next word after observing four prior words; in the example, “writing” has rank 1.At the next epoch, the four-word window shifts and “a” has rank 0.Source: §II · pp. 1–2
  • A good predictor tends to give actual words low ranks, so the rank sequence is expected to contain many zeros and be compressible.The ranks can be encoded as bits with a lossless method such as zip, arithmetic coding, or Huffman coding.Source: §II · p. 2
  • To decode, decompress the bits into ranks and use the same language model at each epoch to select the token at that rank.The encoder and decoder must use the same LLM.Source: §II · p. 2
  • The rank-sequence explanation is mainly intuitive; the authors say direct arithmetic coding with LLM probabilities can compress better.They refer to the probability-based method in Section III-B3.Source: §II · p. 2

III. COMPRESSION USING LLMS

The formal scheme represents English text as a token sequence and uses a finite-memory language model to predict each next token. It ranks the realized token and losslessly compresses the ranks, optionally using the model’s probability vectors as well.

III. COMPRESSION USING LLMS

  • The method represents a sentence s of Nc letters as a token sequence x over a dictionary X, with a one-to-one mapping between the sentence and its tokens.The token sequence can therefore serve as the object to compress.Source: §III · p. 3
  • At epoch i, a memory-M model conditions on the previous M tokens to produce a next-token probability mass function, then orders its probabilities to assign token ranks.The realized token’s rank is ri.Source: §III · p. 3
  • A lossless coder compresses the sequence of realized-token ranks into the final bit representation, and may also use the probability vectors.The section identifies compression ratio as its main metric of interest.Source: §III · p. 3

A. Entropy bounds

The section relates the entropy of a variable-length token sequence to the entropy of its character source, then uses token-level bounds to bound character entropy.

A. Entropy bounds

  • The tokenizer maps characters to variable-length tokens with positive, uniformly bounded character lengths, so an unbounded token sequence also spans an unbounded number of characters.The paper denotes the character count in token i by Bi.Source: A. Entropy bounds · p. 3
  • Under the stated stationary, ergodic-process assumption, the section establishes equality between the entropy rates of the character source and token sequence.The proof uses the tokenization correspondence and probability-one sets for the character, token, and token-length limits.Source: A. Entropy bounds · p. 4
  • Any upper bound on token entropy therefore gives an upper bound on character-source entropy, the property used to estimate English entropy.The section expresses the character-entropy bound using the language model's output PMFs.Source: A. Entropy bounds · p. 4
  • 1.3 bits/character is the estimate reported by Cover and King; the paper treats text8 bits per character in [2, Table 4] as the same metric as its asymptotic upper bound.The paper defines the bound's units as bits per character, based on bits per token divided by characters per token.Source: A. Entropy bounds · p. 4

B. Encoding schemes

The paper considers three schemes for the lossless-compression block.

B. Encoding schemes

  • Three schemes are considered for the lossless-compression block shown in Fig. 3.The passage does not specify the schemes individually.Source: B. Encoding schemes · p. 4

1) Compressing the ranks using zlib:

The first scheme applies zlib to the rank sequence and names the resulting method LLaMA+zlib.

1) Compressing the ranks using zlib:

  • LLaMA+zlib encodes the sequence of ranks with zlib, and its compression ratio is denoted ρLLaMA+zlib.This is the first of the three lossless-compression schemes considered.Source: 1) Compressing the ranks using zlib · p. 5

2) Token-by-Token Compression:

The token-by-token scheme encodes each token with a time-varying prefix-free code based on the language model's predicted distribution.

2) Token-by-Token Compression:

  • The token-by-token scheme encodes token xi at epoch i using a time-varying prefix-free codebook that assumes qi is the token distribution.A Huffman code is identified as a natural choice, while the paper uses lengths ⌈log2 qi(xi)⌉ for simplicity; these lengths satisfy the Kraft inequality.Source: 2) Token-by-Token Compression · p. 5

3) Arithmetic Coding:

Arithmetic coding combines the LLM’s time-varying token probabilities with lossless coding. The resulting compression ratios also serve as finite-sample upper-bound estimates of English entropy.

3) Arithmetic Coding:

  • Arithmetic coding uses each token’s LLM probability as a time-varying coding probability, yielding the scheme ρLLM+AC.The paper describes arithmetic coding as nearly optimal for compression.Source: 3) Arithmetic Coding · p. 5
  • These compression ratios are finite-token estimates of entropy upper bounds, so their statistical properties matter when interpreting results.The tokens come from a very large alphabet and the language model has large memory.Source: 3) Arithmetic Coding · p. 5

IV. RESULTS

LLaMA-7B-based compression performs strongly on text8 and a Project Gutenberg book, with arithmetic coding close to the estimated entropy upper bound. The results are qualified by finite-sample variability, different benchmark input sizes, and possible overlap between LLaMA training data and text8.

IV. RESULTS

  • The text8 comparison is not entirely fair because LLaMA-7B’s tokenizer and training data include text features beyond the lowercase-only inputs used in many prior studies.The authors note that restricting inputs to lowercase letters may itself be unfair to the pretrained LLM.Source: §IV · p. 5
  • ZPAQ (1.4 bits/character) and paq8h (1.2 bits/character) are cited as text8 baselines, not independently rerun by the authors.The authors quote the results from prior literature.Source: §IV · p. 5
  • 0.7101 bits/character with LLaMA-7B plus arithmetic coding is substantially better than the cited state-of-the-art results and close to the computed upper bound.The authors also report better performance than those results for LLaMA+zlib and LLaMA+TbyT.Source: §IV · p. 5
  • Increasing LLM memory improves compression, while inference time scales approximately linearly with memory length.Batches with 511-token memory ran about 16 times slower than batches with 31-token memory.Source: §IV · p. 5
  • Compression-ratio estimates can vary substantially with input text, and LLaMA-7B was not run on the entire 100MB text8 dataset.The state-of-the-art comparison therefore uses estimates from different input sizes.Source: §IV · p. 5
  • Because text8 derives from Wikipedia and LLaMA-7B’s training corpus appears to include Wikipedia articles, the text8 results are likely optimistic.The authors phrase the training-corpus overlap as an appearance, not a certainty.Source: §IV · p. 5
  • 0.8426 bits/character with LLaMA plus arithmetic coding on the book is close to its estimated upper bound, and its upper bound is below estimates in [2, Table 4].The tested text was 100,000 tokens, preprocessed to lowercase letters and spaces.Source: §IV · p. 6
  • Direct zlib compression yielded 2.8 bits/character, substantially worse than the LLaMA-based compressors on the tested input.The authors note that zlib may improve on longer texts because it may not be optimized for small samples.Source: §IV · p. 6

Related papers

Loading 2306.04050v2…