🤖 AI

Empirical Computation: Prompting versus Programming

本ビジョンペーパーは、大規模言語モデルが従来のプログラミングではなくプロンプティングを通じて計算問題を解決するという新しいパラダイムとして「経験的計算（empirical computation）」を提案し、その独自の能力と限界には、正当性や根本的な境界を分析するための新しい基礎理論および技術をソフトウェア工学コミュニティが開発することが必要であると主張するものである。

原著者： Eric Tang, Jing Liu, Marcel Böhme

公開日 2026-07-08

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Eric Tang, Jing Liu, Marcel Böhme

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、仕事を成し遂げるための2つの方法を想像してみてください。それはプログラミングとプロンプティングです。

旧来のやり方：プログラミング（厳格な建築家）

従来のプログラミングは、厳格でルールに忠実な建築家を雇うようなものだと考えてください。あなたは彼に、正確な寸法、特定の材料、そしてステップ・バイ・ステップの計画が含まれた設計図を与えます。

仕組み: あなたはコンピュータに対し、数値のリストをソートする方法など、問題を解決するための「正確な手順」を伝えます。「この特定のアルゴリズム（マージソート）を使用し、これらの入力を取り込み、これらのルールに従え」と指示するのです。
結果: もし建築家がミスをしたとしても、あなたは設計図の中のどのレンガが壊れているのかを特定でき、それを修正すれば、次回はその建物が正しく建つことを確信できます。
限界: 構築にかかる時間は、数学的な複雑さに依存します。膨大なリストをソートする場合、かかる時間はリストのサイズに基づいて予測可能な一定の量になります（具体的には $O(n \log n)$ です）。

新しいやり方：プロンプティング（直感的な芸術家）

次に、あなたは天才的で直感的な芸術家を雇ったと想像してください。あなたは設計図を与えるのではなく、ただこう言います。「ねえ、ここにバラバラな数字の山があるんだけど、これを並べ替えておいてくれる？」

仕組み: あなたは自然言語（プロンプト）を使って問題を説明します。「コンピュータ」（大規模言語モデル、またはLLM）は、厳格なルールに従うわけではありません。代わりに、インターネット上でこれまでに読んだあらゆる事柄に基づき、最も可能性の高い答えを「推測」します。それは、レシピに従うのではなく、スープを味見して材料を推測するシェフのようなものです。
結果: 答えはすぐに返ってきますが、それは保証された正解ではなく、あくまで**「推測」**です。それは「最も可能性の高い」答えであって、「証明された正しい」答えではありません。

この論文が発見したこと：「経験的」な驚き

著者たちは、この「直感的な芸術家」が、数値のソートやリスト内のアイテム検索といった古典的な数学の問題に対して、どの程度うまく機能するかを検証するために実験を行いました。そこで彼らが発見したことは以下の通りです。

1. 時間の仕組みが異なる

プログラミング: 数値をソートする対象の数を2倍にすると、かかる時間は数学的な法則に従って増加します。
プロンプティング: LLMが数値をソートするのにかかる時間は、リストが大きくなるにつれて線形的（単なる直線状）に増加します。なぜなら、数学が難しくなったからではなく、LLMが長いリストを扱うために、より多くの単語（トークン）を読み書きしなければならないからです。これは、物語が複雑になったからではなく、単に本が長くなったので読むのに時間がかかるのと似ています。

2. 規模が大きくなると精度が低下する

プログラミング: 正しいプログラムは、常に100%正確です。
プロンプティング: LLMは小さなタスクには非常に優れていますが、リストが大きくなると混乱が生じます。
- 50個の数値のリストでは、LLMは約90%の確率で正解しました。
- 150個の数値のリストでは、正解率はわずか58%にまで落ち込みました。
- 短い文字列の中から特定のパターンを見つけ出すよう頼んだ場合、文字列が少し長くなるだけで失敗することがあります。
- 「思考」モード: LLMが回答する前に「ステップ・バイ・ステップで考える（推論する）」ことが許されている場合、非常に高い精度を維持しますが、その分、時間は大幅に増えます。

3. 言語のゲーム

プログラミング: コードを英語で書いてもドイツ語で書いても、コンピュータは同じ記号として読み取ります。
プロンプティング: LLMは、インターネット上で読んできた内容による「偏り（バイアス）」を持っています。
- 数字を英語の単語（one, two, three）でソートするよう頼むと、LLMは素晴らしい仕事を見せます。
- しかし、ドイツ語（eins, zwei, drei）でソートするよう頼むと、ほぼ完全に失敗します。
- なぜか？ LLMはインターネット上で膨大な数の英語の例を見てきましたが、ドイツ語の例ははるかに少ないからです。これは、見たこともない料理を作ろうとするシェフに頼むようなものです。彼らは間違った推測をする可能性があります。

4. 「壊れたレンガ」の問題

プログラミング: プログラムが失敗した場合、バグを見つけてコードを修正すれば、問題は永遠に解決します。
プロンプティング: LLMが間違った答えを出した場合、簡単に「バグ」を見つけることはできません。修正すべき特定の行を指し示すことはできないのです。プロンプトを変えたり、「もっと深く考えて」と頼んだりすることもできますが、それが次回必ず成功するという保証はありません。それは、夢の内容を変えるために、夢を見ている人の気分を変えようとするようなものです。

大きな教訓

この論文は、私たちが**「経験的計算（Empirical Computation）」**と呼ばれる新しい時代に突入していると主張しています。

旧世界では、コンピュータが厳格なルールに従うことを信頼していました（合理主義的な枠組み）。この新しい世界では、コンピュータがデータに基づいた「教育を受けた推測」を行うことを信頼しています（経験主義的な枠組み）。

著者たちは、ソフトウェアエンジニアに対し、これらのAIシステムを旧来のプログラムのように分析しようとするのをやめるよう呼びかけています。私たちは、これらの「推測マシン」がどのように機能しているかを測定し、テストし、理解するための新しいツールを必要としています。なぜなら、古い数学や論理のルールは、もはやこれらには完全には適用できないからです。私たちは、「おそらく正しい」結果を、どうすれば「確実に正しい」ものと同様に信頼できるのか、その方法を見つけ出さなければなりません。

技術要約：経験的計算（Empirical Computation）：プロンプティング対プログラミング

問題提起

本論文は、計算問題の解決におけるパラダイムシフトを指摘している。それは、プログラミング（精密なアルゴリズムとデータ構造の指定）から、プロンプティング（大規模言語モデルやエージェントへの非形式的な自然言語による記述の提供）への移行である。従来の計算が、決定論的な手順と検証可能な正当性および明確な計算量境界（例：ソートにおける $O(n \log n)$ ）に依存するのに対し、「経験的計算」は確率分布から出力をサンプリングすることに依存する。

核心となる問題は、この新しい形態の計算の能力と限界が、コンピュータサイエンスにおける古典的な合理主義的枠組みでは理解できないことにある。具体的には以下の通りである：

決定論の欠如： 出力は手続き的に生成されるのではなく、「経験的に最も可能性の高い」結果であるため、ハルシネーション（幻覚）やエラーに対して脆弱であり、従来のデバッグのように原因を特定したり修正したりすることができない。
入力の曖昧さ： プログラミングが形式的な契約（型、フォーマット）を必要とするのに対し、プロンプティングは、解釈が文脈やモデルの学習分布に依存する非形式的な入力を受け入れる。
不明確な複雑性： 実行時の挙動は、古典的な計算量理論とは切り離されており、代わりにトークン化やモデルの推論挙動と相関している。
検証のギャップ： 既存のソフトウェアエンジニアリング（SE）技術（静的解析、形式検証）は、検証すべき明示的なプログラムが存在しないシステムを分析するには不十分である。

手法

著者らは、5つの古典的な計算問題に対して、経験的計算の効率性と正当性を特徴付けるための予備実験を行った：

ソート（Sorting）： ランダムな数値の昇順。
探索（Searching）： ソート済みおよび未ソートのリストにおけるインデックスの発見。
最長回文部分文字列（Longest Palindromic Substring）： 文字列内における最長の回文シーケンスの発見。
部分集合和問題（Subset Sum Problem, SSP）： 合計がターゲット値になる数値の集合の発見。

実験設定：

モデル： 実験には、ネットワーク遅延を排除するため、MacBook Pro（M5 Pro, 48GB RAM）上でローカル実行されているオープンウェイトモデル gemma-4-26b-a4b を使用した。
構成： 以下の3つのモードをテストした：
- デフォルト（Default）： Temperature = 1.0。
- 決定論的（Deterministic）： Temperature = 0.0。
- 思考（Thinking）： 推論モードを有効化。
指標：
- 効率性（Efficiency）： 解への時間、および最初の正解への時間。
- 正当性（Correctness）： 数学的に正しい回答を返した試行の割合。
変数： 入力サイズ（ $n$ ）、数値の精度、および言語表現（数字、および英語、ドイツ語、韓国語、日本語などの様々な言語における言葉での表現）。
正解（Ground Truth）： 非自明な問題（部分文字列、SSP）については、検証のために単純なPythonプログラムを用いて正解を生成した。

主な結果

1. 効率性と古典的複雑性

古典的な理論とは異なり、経験的計算の実行時間は、問題のアルゴリズム的複雑性（例： $O(n)$ 対 $O(n \log n)$ ）には厳密に従わない。

線形スケーリング： ソート、探索、およびSSPにおいて、解への時間はすべてのモードで入力サイズに対して線形に増加した（ $O(n)$ ）。著者らは、これを計算ロジックではなく、入力/出力トークンの線形的な増加によるものとしている。
トークン依存性： 数値を1つ増やすのにかかる時間は、SHA-512ハッシュからのプレーンテキストの予測と比較して同程度であった。これは、実行時間が問題の難易度ではなく、トークン化と推論メカニズムによって駆動されていることを示唆している。
思考モードのコスト： 「思考（reasoning）」を有効にすると、実行時間は大幅に増加したが（例：150要素のソートで最大275秒）、高い正当性が維持された。

2. 正当性と入力サイズ

サイズへの感度： デフォルト および 決定論的 モードでは、入力サイズが増加するにつれて正当性が急速に低下した。
- 50個の整数をソートする場合、正当性は〜50%（コイン投げの確率）まで低下した。
- 150個の整数をソートする場合、正当性は（線形な時間の増加にもかかわらず）〜58%に低下した。
- 部分集合和問題では、リストの長さが10になると、正当性はゼロに近づいた。
- 部分文字列問題では、文字列の長さが5になると、正当性はほぼゼロに低下した。
思考モードの回復力： 推論機能が有効な場合、入力サイズが大きくなっても、トークン/時間の制限内であれば、正当性は高く維持された（>90%）。

3. 自然言語表現の影響

数値の表現に使用される言語が正当性にどのように影響するかを調査した。

データ表現のバイアス： 正当性は、モデルの学習データにおける言語の表現に強く依存する。
高・低表現： 英語（表現が豊富）で書かれた数値をソートすると、サイズ20で>95%の正当性を得た。対照的に、ドイツ語（表現が少ない）で書かれた数値をソートした場合、同じサイズで<1%の正当性しか得られなかった。
結論： 経験的計算は言語に依存しないわけではない。それは、学習コーパスに存在する言語やフォーマットに対してバイアスを持っている。

4. エラー特性

伝統的なプログラムにおける欠陥は特定のコード行に特定できるが、経験的計算におけるエラーは非決定論的である。LLMは以下のような挙動を示す可能性がある：

入力に含まれない数値を加える。
入力に含まれる数値を削除する。
数値を重複させる。
リスト全体をソートできない。
大きな入力を切り詰める。

主な貢献

経験的計算の定義： 本論文は、プロシージャルな実行ではなく、プロンプティングとサンプリングを通じて解が生成される、独立した分野として「経験的計算」を正式に導入した。
経験的特性付け： 古典的なアルゴリズム問題をLLMが解く際の効率性と正当性を体系的に測定した初めての研究であり、実行時間がアルゴリズムの複雑さではなくトークン化と相関していることを明らかにした。
限界の特定： 推論モードなしでは、経験的計算は入力サイズに対して信頼性を持ってスケールできず、入力の言語的表現に非常に敏感であることを示した。
新しいSE基盤への呼びかけ： 著者らは、ソフトウェアエンジニアリング界は、これらのシステム（AI駆動の計算）の正当性を分析、推定、予測するための新しいツール（統計的、反事実的、または因果的推論）を開発しなければならないと主張している。

意義とビジョン

本論文は、ソフトウェアエンジニアリングのコミュニティが、AI駆動の計算の信頼性を確保するために、古典的な合理主義的枠組みや既存のプログラム解析ツールに頼ることはできないと断じている。LLMやエージェントが計算問題を解決するために不可欠となるにつれ、以下の課題に対処するために分野を進化させる必要がある：

明確なプログラムが存在しない状況で、どのように正当性を分析するか。
経験的計算の限界をどのように定義し、テストするか。
回帰（デグレ）を導入することなく、特定の問題インスタンスに対する正当性をどのように向上させるか。

著者らは、これをタイムリーかつ豊かな研究領域として位置づけ、LLMの確率的な性質とソフトウェアエンジニアリングの厳格な要求との間の溝を埋めるための、「経験的プログラム解析（empirical program analysis）」技術の開発を促している。本論文はこれらの問題を解決することを目的としているのではなく、この分野を確立し、新たな理論的・実践的基盤の緊急の必要性を強調することを目的としている。