gzip を言語モデルとして使う：DEFLATE がテキストを生成する仕組み

gzip は言語モデルとして機能するが、限定的でノイズが多い

要点: 候補となる続きの圧縮サイズをその確率の代理とみなすことで、gzip の背後にある DEFLATE アルゴリズムはビームサーチを通じてテキストを生成でき、圧縮と予測の等価性を示す。ただし、その出力はニューラル言語モデルほど一貫性はない。

圧縮は予測である

すべての圧縮器は暗黙的に確率分布を定義する。

情報理論によれば、記号の最適なコード長は (-\log_2 p) であり、ここで (p) はモデルが割り当てる確率である。したがって、記号に少ないビットしか使わない圧縮器は、その記号に高い確率を仮定していることになる。gzip は DEFLATE アルゴリズムを使用し、32 KiB のスライディングウィンドウを維持して、繰り返し現れるバイト列を後方参照に置き換える。続きが最近のバイトを反映している場合、DEFLATE はほぼ追加ビットなしでそれをエンコードする。つまり、圧縮器はその続きを「期待していた」ことになる。

スコアリングルール:

score(candidate) = len(gzip(context + candidate))

圧縮後の長さが短いほど、予測確率が高いことを示す。圧縮器を大きなコーパス（例：tiny Shakespeare）でプライミングすると、コーパスに似た続きは低いスコアを達成する。

ビームサーチによるテキスト生成

単純な貪欲アプローチ（圧縮後の長さが最小になる次のバイトを選ぶ）は、gzip が整数バイト長のみを報告するため失敗する。1バイト追加しても圧縮サイズが変わらないことが多く、大量の同点とノイズの多い勾配が発生する。

ビームサーチの解決策:

  1. プロンプト – ユーザー提供のプロンプトはコーパスウィンドウに連結され、初期コンテキストの一部として扱われる。
  2. コンテキスト – 各検索ステップで、gzip は corpus_window + recent_tail を見る。ここで recent_tail は生成出力の最後の tail バイトである。
  3. 展開 – 各ビーム候補は、コーパスに現れるすべてのバイトで拡張される。すべての拡張は圧縮長ルールでスコアリングされる。
  4. 剪定 – 上位 beam_width 個の候補（最も圧縮率が高いもの）のみを保持し、固定の horizon バイト数だけ繰り返す。
  5. 確定 – 最良の全スパンを出力（または温度パラメータに比例してサンプリング）し、ウィンドウを前方にスライドさせる。

コンテキストを最近の tail バイトに制限することで、モデルが自身の最近の出力を単純にコピーする自明なループに陥るのを防ぐ。DEFLATE は近いマッチほど安価なコードを与えるためである。

生成出力の例

tiny Shakespeare コーパスでプロンプト "MENENIUS:\n" を使ってツール gzipt を実行すると、次のような出力が得られる：

MENENIUS:
'Though all at once canq

MARCIUS:
Pray now, nocamest thou to a morsel .

LARTIUS:
Hence, and
I' the end admire, where G
again; and after it ag .

このテキストは流暢なシェイクスピアではないが、ソースの断片や句読点パターンを明確に再利用しており、gzip の圧縮モデルがコーパスの統計的規則性をいくらか捉えていることを確認できる。

他の圧縮器の動作

著者は bzip2 と Zstandard (zstd) でも実験を行った：

  • bzip2 – 交互する記号の長い連続（例：xyxyxy…）を生成する。これは Burrows-Wheeler Transform に依存していることを反映しており、意味のある言語ではなく高度に反復的なパターンを好む。
  • zstd – 主に空白と時折の文字を生成する。これは、ランレングス符号化により単一の繰り返しバイトが安価になり、シェイクスピアコーパスではスペースと改行が最も安価なリテラルであるためである。

これらの結果は、基盤となる圧縮アルゴリズムの性質が生成テキストのスタイルに強く影響することを示している。

コミュニティの洞察

「gzip を使ってテストファイルをトピックで分類できます：gzip -9 sports.txt testfile.txt … テストファイルは最小のサイズの .gz ファイルを持つトピックに属します。」 – jll29 (HN)

「可能なシーケンスの空間は検索されたものより何桁も大きい。したがって、結果は gzip が続きの『妥当性テスター』としてどれだけ機能するかの下限しか与えない。」 – mg (HN)

「bzip2 と zstd でこれがどう機能するか興味があった… bzip2 は人間の言語に似ないシーケンスを生成する；zstd は繰り返しバイトの連続をほぼ無料のランレングスシーケンスとしてエンコードし、スペースと改行が最も安価なリテラルである。」 – networked (著者コメント)

これらのコメントは2つの点を補強する：(1) 圧縮ベースの分類は既知の技術である、(2) ビームサーチアプローチは単純な貪欲検索よりも大幅に改善されるが、検索空間は天文学的に大きいままなので、この方法は gzip の予測力のヒューリスティックな推定に過ぎない。

制限と未解決の質問

  • 一貫性 – 出力にはニューラル言語モデルのような長距離の意味的一貫性がない。DEFLATE は32 KiB しか遡らないため、プロットやキャラクターの弧を捉えることはできない。
  • 検索品質 – ビームサーチは依然としてヒューリスティックであり、大域的に最適な（最も圧縮率の高い）続きが見つかる保証はない。
  • 速度と表現力のトレードオフ – gzip は入力サイズに線形にスケールし、現代の LLM よりも桁違いに高速であるが、この速度は表現力の犠牲の上に成り立っている。
  • LLM を圧縮器として比較 – 一部のコメンテーターは、大規模言語モデルが gzip と比較してテキストをどれだけうまく圧縮するかに興味を持っており、補完的な研究方向を強調している。

これが重要な理由

この実験は、圧縮と予測の等価性 定理の具体的なデモンストレーションを提供する：あらゆる可逆圧縮器は予測器として再利用でき、その逆も可能である。gzip の予測能力は初歩的であるが、このアプローチは非ニューラル言語モデルの探求、確率推定の代理としての圧縮アルゴリズムのベンチマーク、大規模 AI 時代における古典的アルゴリズムの再検討への道を開く。

Sources

関連