テクニカル・サマリー：プロンプトの価値：LLM相対的コルモゴロフ複雑度によるアプローチ

1. 問題提起

大規模言語モデル（LLM）が、価値あるアーティファクト（証明、コード、設計、仮説など）を生成する中心的な役割を果たすようになるにつれ、極めて重要な経済的問いが生じている。それは、**「人間による入力（プロンプト）の価値をどのように測定するか？」**という問いである。

トークン数のような従来の指標は、価値を捉えることができない。なぜなら、短いヒントが決定的な役割を果たすこともあれば、長いプロンプトが無意味な場合もあるからである。堅牢な尺度には、以下の2つの基準を満たす必要がある。

1. 比較の困難性： プロンプト $p$ がある場合とない場合で、アーティファクト $z$ を生成する難易度を比較しなければならない。
2. 計算量のトレードオフ： プロンプトがないモデルは、「思考」を長くすることで補完できる可能性がある。したがって、尺度にはこの追加の計算量を考慮に入れなければならない。つまり、プロンプトの価値を、単に出力の確率を高めることだけでなく、その出力を見つけ出すために必要な計算努力を削減することに対して認める必要がある。

既存のアルゴリズム情報理論（コルモゴロフ複雑度）は計算不能であり、計算時間も無視している。リソース限定型のバリアントも、計算が困難なことが多い。さらに、古典的な相互情報量は、現代のLLMに固有の「思考プロセス（Chain of Thought）」を自然に扱うことができない。

2. メソドロジー

本論文は、プロンプトの価値を定義するために、LLM相対的な確率的レヴィン・コルモゴロフ複雑度（$\tilde{pKt}$ と表記）を提案している。このアプローチは、思考段階を持たないモデルから、明示的な思考段階を持つモデルへと進化させている。

2.1 非思考型LLM（ウォームアップ）

思考段階を介さずに直接出力を生成する自己回帰モデルの場合：

• LLM相対的複雑度： 普遍チューリングマシンは、特定のLLM $M$ に置き換えられる。「プログラム」は、特定の文字列 $z$ を強制的に出力させるためのサンプリングのランダム性（ディアディック区間）を表すバイナリ文字列として定義される。
• 事前複雑度： これを効率的に計算可能にするため、著者は出力の対数確率を使用する：$\tilde{K}_M(z|y) = -\log_2 P_M(z|y)$。
• プロンプトの価値： 事前複雑度の差として定義される：$\tilde{Val}_M(p; z) = \tilde{K}_M(z) - \tilde{K}_M(z|p)$。これは、プロンプト $p$ がある場合、プロンプトがない場合と比較して、$z$ が何倍出現しやすくなるかを示す対数尤度比（点別相互情報量）に相当する。

2.2 思考を行うLLM

現代のLLMは多くの場合、最終的なアーティファクト $z$ を出力する前に、「思考ルート」 $H$ （Chain of Thought）を生成する。これには2つの課題がある。

1. 思考のランダム性： 思考ルート $H$ は確率的である。すべての可能な思考の平均をとるだけでは、稀に発生する非常に成功したパスによって結果が歪められる可能性がある。
2. 計算の節約： 優れたプロンプトは、単に固定された努力における確率を高めるだけでなく、長い思考シーケンスの必要性を排除する場合もある。

提案される解決策：

• 実現された思考のレヴィン複雑度： 固定された思考ルート $H$ に対して、$z$ の複雑度は、記述長（$H$ を与えられた $z$ の対数確率）と、思考プレフィックスのコストの対数の和を最小化することによって定義される。
  $$\tilde{Kt}^\kappa_M(z | y; H) := \min_{t} \left( -\log_2 P_M(z | y H_{\le t} \text{EOT}) + \log_2 \kappa(t) \right)$$
  ここで、$\kappa(t)$ は $t$ 個の思考トークンに対応するコスト関数である。$t$ に関する最小化により、成功確率が十分に高ければ、コストを相殺するために思考を早期終了させることが可能になる。
• 確率的複雑度 ($\tilde{pKt}$)： $H$ はランダムであるため、著者は、多くのサンプリング・ロールアウトにおける実現された思考複雑度の中央値（または $\delta$-分位点）として複雑度を定義する。これにより、稀な「幸運な」思考パスへの感度を回避できる。
  $$\tilde{pKt}^\kappa_{M,\delta}(z | y) := \text{med}_\delta \left[ \tilde{Kt}^\kappa_M(z | y; H_y) \right]$$
• プロンプトの価値： 最終的な価値は、これらの確率的複雑度の差である：
  $$\tilde{Val}^\kappa_{M,\delta}(p; z) = \tilde{pKt}^\kappa_{M,\delta}(z) - \tilde{pKt}^\kappa_{M,\delta}(z | p)$$

3. 主な貢献

1. LLM相対的複雑度フレームワーク： 本論文は、コルモゴロフ複雑度とレヴィン複雑度をLLMの特定のアーキテクチャに適応させ、モデル自体をリファレンスマシンとし、そのサンプリングのランダム性をプログラムテープとして扱っている。
2. 「思考」の扱い： 思考プロセスを「ランダムなテープ」として扱い、思考プレフィックスに関するレヴィン型の目的関数（記述長 + 対数時間）を最小化することで、Chain of Thoughtを持つモデルのためのプロンプト価値を定義する新しい手法を導入した。
3. 効率的な推定可能性： 提案された尺度は、古典的なリソース限定コルモゴロフ複雑度とは異なり、効率的に推定可能である。論文では、誤差に対する高確率の境界を伴う、多項式回数のロールアウトを用いて中央値の複雑度を推定するプロトコルを提供している。
4. 経済的解釈（トークンコスト）： 著者は、ある基本定理を証明している：$2^{\tilde{pKt}}$ は、特定の実験においてアーティファクトを再現するための中央値のトークンコストに正確に一致する。
   • もしプロンプトの価値が $b$ ビットであるならば、それはプロンプトなしでアーティファクトを再現する場合、プロンプトありの場合よりも、通常 $2^b$ 倍多くのトークン相当の単位コストがかかることを意味する。
5. 先行研究との区別： 「思考なし」のコンポーネントが点別相互情報量（PMI）や近年の「人間による貢献度」スコア（Xieら）と一致する一方で、計算と思考を明示的に扱うことが本研究の新規性であることを明確にしている。

4. 実験結果

著者は、DeepSeek-R1-Distill-Qwen-1.5B モデルを用い、GSM8K データセット（小学校レベルの算数の文章題）の12個の問題に対してこの尺度を評価した。

• 思考が判定を逆転させる： いくつかのケースにおいて、正しい最初のステップ（プロンプト）を供給すると、$t=0$（思考なし）の状態では最終的な答えの確率が当初は低下した。しかし、思考プロセスを組み込むと、プロンプトの価値は正になった。これは、非思考型かつ確率のみに基づく指標が、提案された思考を考慮した指標とは逆の定性的判定を下す可能性があることを示している。
• 加速 vs ステアリング： 結果は、単に計算を「加速」させる（生成された思考のコストの下では価値が高いが、プレフィル・コストの下では価値が低い）プロンプトと、モデルを根本的に優れた状態へと「ステアリング（誘導）」する（両方のコスト慣習の下で価値がある）プロンプトを区別した。
• 正解 $\neq$ 価値： 人間の参照による正しい部分解が、常に価値を持つわけではなかった。場合によっては、冗長であったり、好ましくない継続を誘発したりするため、プロンプトの価値は負または無視できるレベルになった。
• 分布依存性： プロンプトの価値は、ロールアウト分布の異なる分位点（$\delta$）によって大きく変動した。これは、プロンプトがある種の「思考の軌跡」を助ける一方で、他の軌跡を妨げる可能性があることを示唆している。

5. 意義と主張

本論文は、理論的に裏付けられ、効率的に推定可能で、経済的に解釈可能なプロンプト価値の尺度を提供すると主張している。

• 理論的基礎： アルゴリズム情報理論とLLM経済学を橋渡しし、尤度と計算努力の両方を考慮した「価値」の形式的な定義を提供している。
• 運用的意味： 複雑度を再現のトークンコストの中央値に結びつけることで、プロンプトの価値は抽象的な指標ではなく、具体的な経済的節約であることを論じている。
• 謙虚な姿勢： 著者は、この尺度が「宣言された」アーティファクトの記述に対して価格をつけるものであることを明記している。もしアーティファクトの定義に欠陥がある場合（例：ランダムノイズが含まれる場合）、価値の尺度はそれを反映する。また、現在のフレームワークは単一のプロンプトを固定されたコンテキスト内で評価するものであり、適応的なマルチターン会話戦略や、人間による入力自体の策定コストを完全には捉えていないことも述べている。

要約すると、本論文は、AI生成が溢れる時代において、人間の貢献の価値とは、特定の成果を得るためのモデルの計算負担を軽減することにあり、この軽減はLLM相対的レヴィン複雑度を用いて厳密に定量化できると断じている。