- LLMのハルシネーションを経験的に減らす研究とは異なり、この論文は計算可能な正解関数とモデル出力の不一致によってハルシネーションを定義し、完全に除去できるかを形式的に検討する
- 対角化論法によれば、計算可能なLLMはすべての計算可能関数を学習できず、一般的な問題解決器として使う場合はハルシネーションを避けられない
- 現実的な多項式時間LLMには、組み合わせ列挙、Presburger arithmetic、Subset Sum、SAT、命題論理含意のようなハルシネーション脆弱問題があり、一部の結論は P ≠ NP 仮説に依存する
- モデルの拡大、アンサンブル、より多くの学習データ、Chain-of-Thought・検証プロンプトは誤りを減らせるが、正解関数がモデル能力の外側にあるなら完全除去は不可能である
- 入力-出力ペアだけで学習したLLMを安全上重要な意思決定に自動投入するのは難しく、ガードレール、知識基盤、人間による統制があわせて必要である
形式世界で定義したLLMハルシネーション
- LLMのハルシネーションは、もっともらしいが事実と異なる、または無意味な情報を生成する問題であり、研究・産業・社会全般で適用が広がるほど安全性と倫理への懸念が高まる
- 既存の緩和研究は、データ収集、学習、推論段階で原因を探し、ベンチマーク・検索ベース手法・推論プロンプト・検証プロンプトによってハルシネーションを減らそうとしてきた
- 可能なすべての入力を列挙して試験することはできないため、経験的アプローチだけではハルシネーションを完全に除去できるかに答えにくい
- 現実世界の意味論を形式的に定義する問題は依然として未解決であり、論文は計算可能関数から成る形式世界を用いる
- 正解関数
f は入力文字列 s に対して一意の正しい出力 f(s) を与える
- LLM状態
h[i] がある入力 s において h[i](s) ≠ f(s) なら、正解関数 f に対してハルシネーションしたと定義する
- LLMは学習サンプルを逐次受け取り、複数の状態
h[0], h[1], ... を持つ全体としての計算可能関数として扱われる
- 核心的な問いは、固定された手続きで学習したLLM
h が任意の正解関数 f に対して、ある学習段階 i で全入力 s について h[i](s) = f(s) を満たせるかどうかである
対角化論法で示された必然性
- 計算可能に列挙可能なLLM集合
{h0, h1, ...} に対し、すべてのLLMのすべての学習状態がハルシネーションする計算可能な正解関数 f が存在する
- 各LLMの学習状態を再び1つの列挙
{ĥ0, ĥ1, ...} にし、入力文字列 {s0, s1, ...} に対する出力表を構成する
- 正解関数
f(si) を ĥi(si) と異なる文字列になるよう定義すると、対角線上の位置で各LLM状態と衝突する
- 同じ方法で、すべてのLLM状態が単一の入力ではなく無限に多くの入力でハルシネーションするようにする正解関数も構成できる
f(si) を j ≤ i であるすべての ĥj(si) と異なる文字列として定義する- すると特定のLLM状態
ĥk は、十分後ろの入力群で継続してハルシネーションする
- 単一の計算可能LLM
h も {h} という計算可能に列挙可能な集合であるため、すべての計算可能LLMにはハルシネーションを引き起こす計算可能な正解関数が存在する
- 定理3によれば、すべての計算可能LLM
h に対して各状態 h[j] がハルシネーションする正解関数 f が存在し、無限に多くの入力でハルシネーションさせる f' も存在する
- LLMが自力でハルシネーションを除去するには、任意の計算可能関数に対してハルシネーションのない状態が存在しなければならないが、これは定理3と矛盾する
- Chain-of-Thought のようにLLM自体に依存する緩和手法だけでは、ハルシネーションを完全には除去できない
ハルシネーションに脆弱な問題の類型
- 与えられたLLM集合が計算できない正解関数を見つければ、その問題はハルシネーション脆弱問題になる
- 多項式時間制約を持つLLM、すなわち論文で既存のLLMすべてとみなす範疇には、次の問題が含まれる
- 組み合わせ列挙: 2文字アルファベットで長さ
n の全文字列を列挙する問題で、計算に Ω(2^n) の時間を要する
- Subset Sum: 整数集合と数
q が与えられたとき、和が q になる部分集合があるかを答える NP-complete 問題
- Boolean Satisfiability(SAT):
n 個の Boolean 変数からなる式を真にする割り当てがあるかを答える NP-complete 問題
- 命題論理含意:
M(ψ) ⊆ M(ϕ) かどうかを答える co-NP-complete 問題
- Subset Sum、SAT、命題論理含意が多項式時間LLMのハルシネーション脆弱問題だという結論には、P ≠ NP 仮定が付く
- Presburger arithmetic は自然数の加算と順序
< に関する一階理論であり、ある命題がその算術の中で証明可能かを答える
- 計算に
Ω(2^{2cn}) の時間を要し、多項式時間LLMと指数時間LLMの両方に対してハルシネーション脆弱問題に分類される
- すべての計算可能LLMには、より一般的な脆弱問題が存在する
- すべての計算可能な線形順序を学習する問題は定理4で扱われる
- すべての計算可能問題を解くことは定理3の対象である
- 一階論理含意は undecidable な問題に分類される
- 数学問題や論理推論に対するLLMの回答は、常に別途レビューが必要である
既存の緩和策の範囲
- より大きなモデル、モデルアンサンブル、より多くの学習データは、LLMがより複雑な正解関数を捉える助けになりうる
- 学習データが増えれば、無効なLLM候補を排除し、学習収束に寄与できる
- しかし正解関数がそのLLMで捉えられない範囲にあるなら、パラメータとデータの増加だけではハルシネーションを除去できない
- 多項式時間LLMに attention layer を追加しても、より大きな多項式時間LLMになるだけで、指数時間の正解関数に対するハルシネーションは除去できない
- モデルアンサンブルも本質的には1つのLLMとみなせるため、定理3の制約を受ける
- Chain-of-Thought、reflection、verification プロンプトは、例示解法や関連知識を文脈内に与える文脈内学習系のアプローチである
- 複雑な問題には複数の解法があり、プロンプトは人間が好むより低い複雑度の解法へLLMを誘導できる
- Fibonacci 数列は、再帰解法では指数時間だが動的計画法なら線形時間で解ける例として使われる
- すべての正解関数をプロンプトで完全に記述できる可能性は低く、このアプローチは特定タスクでのみ効果が期待できる
- ガードレールとフェンスは、LLM出力を人間の価値・倫理・法的要件に合わせたり、LLMで完全自動化してはならない重要タスク一覧を設けたりする方式である
- 形式的にプログラミングしてLLMの挙動に明示的な影響を与えられる
- 形式世界と一部の現実問題で有用な緩和策になりうる
- 現実世界での拡張可能性は未解決の問題として残る
- 知識強化LLMは、知識グラフ、データベース、論理のような外部知識と記号推論を学習・推論に活用する
- ChatGPT のようなLLMベースのチャットボットは、検索エンジン、コードインタープリタ、電卓のようなツールを用いて、LLMの内在能力の外にある問題を解き始めている
- 知識データベース検索は、入力-出力学習サンプル以外の情報を正解関数について提供する
- この場合、定理3はそのまま適用されず、形式世界では潜在的に有効なハルシネーション緩和策になりうる
- 現実のタスクでの拡張可能性は依然として開かれている
展開時の制約と研究の限界
- 入力-出力ペアだけで学習したすべてのLLMは、一般的な問題解決器として使うとハルシネーションする
- ある問題は人間にとって知的に容易でも、LLMには計算的に難しい場合がある
- 逆に、人間には難しい問題がLLMには計算的に容易なこともある
- 現実世界のハルシネーション原因は計算複雑性だけではなく、不完全な学習データも計算的に容易なタスクでハルシネーションを生みうる
- この結論は、訓練データ外の質問にも最終的に答えを出す有用なLLMに適用される
- LLMは任意に多くの質問に「わからない」と答えることはできる
- ある状態のLLMが学習データ外の質問に答える瞬間、その回答に対して定理1と定理2の対角化手法を適用できる
- LLMが決して答えなければハルシネーションしないが、未見の質問に答える限り、ある形式世界ではハルシネーションする
- 外部補助装置なしにLLMを安全上重要な意思決定へ自動で使ってはならない
- ガードレール、フェンス、知識基盤、人間の統制は、入力-出力ペア以外の情報を与えることで定理3の限界を超える助けになりうる
- 人命に関わる意思決定のように、ハルシネーションによる誤りを受け入れがたい領域では、理性的かつ人間的な判断が必要である
- LLMの安全境界に関する研究と規制が重要である
- 顧客サービスに使われたLLMが誤情報を提供し、実際の金銭的損失が発生した事例がある
- ロボットのような自動検知・作動環境では、ハルシネーションが危険な現実の結果につながりうる
- LLM能力の境界について理論家と実務家の合意、および境界外利用を防ぐ規制が必要である
- 研究の限界も明確である
- LLMの計算能力の内側にある問題で発生するハルシネーションは扱わない
- 正解関数を決定論的に仮定しており、確率的観点からの洞察は限定的である
- 経験研究では既存のLLMを追加ファインチューニングなしで使用している
1件のコメント
Hacker News の意見
論文をざっと見たところ、核心は P != NP なので、LLM は NP 完全問題に対して幻覚的な回答を出す、という主張のように見える
巧妙な点ではあるし、数学・コンピュータサイエンス・言語に関する興味深い哲学的問いでもあるが、人々はこれを通常の「LLM の幻覚」という概念に適用しようとしているようだ。論文が用いる形式的な幻覚と、小説の要約を求めたときに存在しない章をでっち上げたり、具体的な細部を作り上げたりするような常識的な幻覚とのつながりは、はっきりしないように見える
形式世界、つまり数学・論理・形式文法の世界が「現実」世界または自然言語世界の部分集合だという記述も興味深い。ほとんどの人間は形式論理の問題を解いたり形式文法をパースしたりできないが、強い幻覚効果を経験することはなく、自然言語を非常に巧みに扱う。人間も特定の NP 完全問題を解けないのだから、幻覚は必然なのか？ 寿命が有限なので、能力があっても終えられない問題もあり得る
人間がこういうことをする場合は 作話症（confabulation） と呼ぶ。自分が嘘をついているとは知らず、知識の空白をその場で作り上げたでたらめで埋める精神医学的症状だ。幻覚はまったく別の症状である
作話症は人間が正常に行うことではなく、その事実が P != NP とどう結びつき得るのかも分からない。正常な人は理由が何であれ自分の知識の限界を認識するが、LLM はそうではない
この主張が問題に陥るのは、「計算可能な LLM と S 上の計算可能な真理値関数 f だけを考える形式世界で幻覚を定義する」という部分だ。これは真理に対する信頼できて計算可能な述語を要求しているが、それ自体がおそらく不可能だ
代わりに真理値関数の出力として True、False、Unknown、Resource limit exceeded を許せば問題を避けられる。これで目標は管理可能になる。True や False は有効なときだけ返し、有用なクエリで Unknown と Resource Limit Exceeded が出る割合を減らせばよい
同じ問題は プログラム検証システム でも発生しており、何十年も同じ方法で扱われてきた。ある命題が真かどうかを決定することは、ときに非常に多くの作業を要求する
人々が LLM の幻覚と言うとき、実際には間違っていて自信満々な回答を意味してはいる。とはいえ、すべての誤答が幻覚というわけではない
あるプログラムが停止するかを尋ねて LLM が「分からない」と答えたなら、幻覚とは呼ばないだろう。ところが著者らの主張が、LLM は NP 完全問題を常に正確に解けるわけではないということなら、「分からない」も幻覚的回答と見なすように聞こえる。ただし論文は読んでいない
要旨だけ読んだという点は認めるが、このように高度に形式的なアプローチが、LLM に「分からない」とより頻繁に答えさせられるのかという実用的な問いに役立つかどうかには、概して懐疑的だ
不完全性定理に似て聞こえる。実際、不完全性定理が数学研究は無駄だという意味ではないのと同じように、LLM がある関数を計算できないかもしれないという話も、幻覚問題が LLM がすべてを知っていなければならないという意味ではない。私たちが気にしている問題は「分からない」と答える問題であり、これは依然として計算可能かもしれない
答えは考える心から出てくるのではなく、膨大な事前計算パターン表の上を漂う複雑な パターン照合スーパーコンピュータ から出てくる。入力を計算したあと、そのパターンに最もよく合うものを吐き出すだけだ。自分の限界を概念的に理解する思考する脳はない
現在の AI に「分からない」を期待するのは、ナビゲーションソフトに Springfield にある Simpsons の家までどれくらいかかるか尋ねるようなものだ。機械は答えを出すが、その答えを不可能にしている文化的参照を把握できない。代わりに最も近い実在の Springfield で Simpson という人物を探す
論文は、この弱点が根本的だと主張しているものと解釈している。ネットワークが自分の知識の限界を知っているかのように振る舞うよう学習させることはできるが、現実の実装では常に埋められないギャップが残る、ということだ
そのためには、人々が実際に知らないときにどのように話すのかを、取り込んだすべての資料の中から学ばなければならない。しかしインターネット上の多くの人は、知らないときに単に「分からない」と書くのではなく、関係のないことを書く
現実には Amazon のトラック経路が数学的な最適解より 20% 悪くても、巡回セールスマン問題は十分に良い形で「解決」されたと言える
質問はかなり慎重にしないと、でっち上げられてしまう。たとえば「xでこれをどうやるのか？」と聞くのではなく、「xでこれはできるのか？」と聞く必要がある。
こうした「AI」はイエスマンのようなものだ。事実でなかったり不可能だったりしても、ユーザーを喜ばせるためなら何でも言う。
そういう人たちに会ったことがあるが、一緒に働くのは非常に難しい。約束したプロジェクトを本当に納品するのか信じられず、すべてを再確認しなければならない。約束したことがそもそも可能なのかも信じられない。
最近、DeepLに thou を du と訳させるのがだんだん難しくなっていてもどかしい。英語に欠けている機能によって生じる非互換性を回避するための、私の「ハック」としてよく使っていた方法だった。
「イエスマン」問題をある程度和らげるには、質問を投げるときに厳密な数学者のようになる必要があり、LLM技術だけでこの問題を完全に克服できるとは思わない。滑稽に聞こえるが、質問を代わりに分解してくれる抽象化が発展しそうなので、「プロンプトエンジニアリング」の存在は認めざるを得ない。
いちばん良かった経験は、私たちが何をしようとしているのかを自由に話し合うところから始まった。まず質疑応答を通じて、私とAIが同じ領域を考えていて、関連する用語を共有しているかを確認すると役に立つようだ。
「そう振る舞え、さもなくば……」という報酬がかかっている限り、設定された目標を達成するために知能を使うシステムが出てくるのは驚くことではない。
幸い、これは基盤となる知能の限界というより、その周囲に置いた報酬構造の限界をより多く物語っている。
より良いプロンプトが必要だという点は正しい。「最初の女性大統領は誰だったか？」と聞くのではなく、「女性大統領はいたのか？」と聞くべきだ。StackOverflowのように、知らない状態で前提を置かず、正しい質問をしなければならない。
初期のGoogleでスパム結果を見るたびに検索エンジンだけを責め、キーワードの選び方や、常に何かを返そうとする挙動を無視していた状況を思い出してほしい。コンクリート板をノミで叩きながら、美しい彫像が出てこないと文句を言うユーザーに似ている。
小説や物語を書くことは幻覚である。確率的オウムの反対だ。
AIの両極端はどちらも達成された。コンピュータは論理機械であると同時に、幻覚する機械にもなり得る。目標は、その両方を同時にでき、かつ両者を区別できる機械を作ることだ。
核心は幻覚そのものではなく、コンピュータがいつ幻覚しているのかを自覚することだ。
もちろん難しい問題だが、人間もとてつもなく幻覚する。宗教を見れば十分だ。正しい宗教は一つだけか、あるいはどの宗教も正しくない可能性があるのだから、論理的には他のすべての宗教は幻覚ということになる。
「ヘリオスが毎日太陽を空の向こうへ引いていく」といった誤った説明に至ることと、数学プログラムが順序上もっともそれらしい次のトークンを誤って返すことは、カテゴリーとして異なる。LLMには信念がまったくない。
ヘリオスは「太陽はなぜ昇るのか？」という問いへの答えだ。そうした信念は、何らかの力がそれを引き起こしているはずだという論理的理解を示しているが、世界知識の不足によって誤った説明を作り出したものだ。
LLMはそのような問いを立てて推論することはできない。同じ種類の「幻覚」ではない。単語予測で認知を解決したと仮定すると、長期的にはすぐ行き詰まるだろう。
複数の宗教が世界のある側面を正確に説明しつつ、別の側面では間違っている可能性もある。宗教が持ち得る有用な状態を、厳密で完全な「正解」一つだけとして扱うのは非常に誤解を招く。ニュートン物理学も特殊相対性理論も、観測されたある現象を予測できないが、それでも有用だ。すべての宗教が厳密で完全な整合性を主張しているわけでもない。
ある宗教が間違っているように見えるとしても、それが自動的に幻覚を意味するわけではない。人はもっともらしい理由で何かを信じ、それでも間違うことがある。
「これが真であることを証明できず、証明しようとも思わないが、神についての主観的な幻視体験のために、おそらく実在すると納得した」という態度もあり得る。これは、LLMが根拠なく論文を丸ごとでっち上げるのとはかなり違って見える。
人間は世界とその要素を、親しみのある人のような存在として扱い、コミュニケーションするときのほうが、より容易に相互作用できるようだ。
LLMやAI全般について語るときにも、人格化はよく現れる。
頭のいい誰かがこう言っていた
良ければ「創造性」と呼び、悪ければ「ハルシネーション」と呼ぶ
これはバグではない。著者たちが言うような限界でもない。機能だ
そのハルシネーションがたまたま当たることがあるので、人々は間違うことが例外で、当たることが somehow ルールなのだと結論づけた
何千年も前のテキストから、今日の自分の人生に合致する部分を見つけ、それが未来を予言したものだと結論づけるのに似ている
そうしたテキストの意味や真実は、テキスト自体に内在する品質ではなく、読む人の心から生じる認知バイアスにすぎない
今後の改善について言えば、今日見ている水準を超えた超知能を期待するのは、過度に楽観的だと思う。世界中の公開情報にアクセスしたり、既存の創作パターンに合うテキスト・画像・動画を素早く生成したりする水準のことだ
より創造的な知能は、「おかしくならない」ために極めて繊細なバランスを必要とするのではないかと疑っている。つまり、私たちがハルシネーションではなく創造性と見なす出力を出さなければならない
AI内部で知能が進化するようなフィードバックループを作れば作るほど、このバランスを取るのは指数関数的に難しくなるだろう
人間がすでに、宇宙が許す限界までこの創造的知能のフィードバックループを最適化している可能性もある。膨大な知識には、より多くのニューロンやストレージが明らかに役立つが、それが創造的知能にも当てはまるかはまだ分からない
これは、私たちが実際にやっていること、つまり大量の人間の言語を統計的にモデリングすることを示す、深く組み込まれた設計上の欠陥だ
この経路にデータをさらに投げ込んでも、魔法のように目覚めてAGIになるわけではない。この問題は消えないだろう
機械学習コミュニティは誇大広告列車から降りるべきだ。第一歩は、自分のプロジェクトを擬人化しないことだ
これが人間とLLMの違いではないか？
人間は自分が根拠のある推測をしていることを分かっており、必要ならそう言うべきだ。あるいは、自分が創造的に作っていることを分かっていて、そう言うことができる
どちらなのか分からないなら、LLMは結局、非常に精巧な機械的な入出力装置から大きく外れるものではないことがはっきりする
AIの誇大広告は、いまや**「現実を見よう」段階**に入っているようだ。アラインメント問題についての熱狂的な文章もしばらく見ていない気がする
AGIが欲しいなら、LLMは答えではない。多くの人はこれを工学上の問題と見て、LLMがそこまで連れて行ってくれると考えているようだが、それはできない。工学上の問題ではないからだ
「ハルシネーションは、計算可能なLLMと計算可能な真値関数の間の不一致として定義される」というのは、単なる不正確さか、ごまかしだ
それをハルシネーションと呼ぶのは、こうしたプログラムが知的だという考えに迎合しているだけだ
LLMを「文字列において時刻tの出力を、それ以前のすべてのトークンに条件づける確率モデル」と定義している
この定義は人間の知能まで含むほど広く見え、したがって結論も人間に同じように有効であるべきだ
ただし人間の知能は、LLMと違って、かつて学んだ情報を思い出すことだけに制限されていない。私たちは論理的推論もでき、LLMでもこの能力は改善しているようだが、完璧には程遠い
もう一つの問題は、情報源に応じて、特に個人的なバイアスに応じて、信頼度を非常に異なって扱う点だ。私の経験では、LLMはユーザー入力によってすぐに崩れ、自分の意見を変える傾向があるので、これが大きな要因だと思う
この定義なら、タイトルの文、つまり「ハルシネーションは必然である」が誤りだと非常に簡単に証明できる。
LLM の入力コンテキスト長を 1 バイトに固定しよう。入力「A」には「yes」と答え、それ以外のすべての入力には「no」と答えるようになるまで LLM を学習させ続ける。
真値関数は、入力「A」の正解を「yes」、それ以外のすべての入力の正解を「no」と定義する。
この LLM は、証明可能な形で絶対にハルシネーションしない。可能なすべての入力について、出力が真値関数と一致することを完全検証したからだ。
入力コンテキストサイズと真値表の項目数を任意に帰納的に増やすことを妨げるものはなく、どの段階でもハルシネーションは「必然」にはならない。
あの一文の断片が著者たちの仮定をすべて含んでいないのは当然だ。彼らは、任意長の入力と特定のリソース制約を持つ LLM、たとえば計算に多項式時間まで使えて、この多項式時間動作が証明可能でなければならず、学習中のミスでより長くかかってはいけないような LLM は、そうした制約のない特定の関数を計算できない、という直感的に明らかなことを証明している。
場合によっては、この証明は P != NP を仮定している。そのうえで、現実の有用な質問の一部は、LLM が計算できないクラスに入る可能性が高いと主張している。LLM に数学の問題を尋ねることができ、数学の問題は時に非常に難しいからだ。
この形式モデルは漸近的、つまり任意長入力などを仮定しているが、私の経験では、この種の定理はたいてい、適度なクエリ長の現実的な問題にも当てはまることが多い。
しかしこれは、ハルシネーションが必然であることを証明するのと同じではない。合理的な定義なら、LLM であれ人間であれ「わからない」と言えるべきで、それをハルシネーションと見なすべきではない。そうすれば LLM はハルシネーションを避けられ、問題はハルシネーションなしにどれだけ有用な仕事ができるかになる。
そうすると主張は同語反復に縮退する。ハルシネーションしないように学習された LLM はハルシネーションしない。難しいのは、実際にそう作ることだ。
基底ケースを示しただけで、帰納仮定も帰納ステップもない。頭の中でそのステップを済ませているのかもしれないが、だとすれば主張するほど自明な証明ではない。
だから言語学習は現実の経験と組み合わせる必要がある。こうしたロボットたちに探索する世界、たとえ仮想世界でも与え、その中で結果を経験し、生き残らせるべきだ。
そうしなければ、すべては経験に結びついていない、宙に浮いた記号と象徴体系にすぎない。
3〜5年前なら、LLM についてそう考えていた。物体が曖昧な形でくっついているとき、何が落ちるか答えられず、当時の主張は、そういうことを理解するには経験が必要だというものだった。しかし LLM はそうした問題をかなり前に解決した。
LLM が質問を「解く」方法は私たちとは大きく異なる。今や、LLM が知能を得るには現実世界に根を下ろす必要があると証明するには、あまりに自明で誰も文章にしていない現実世界の現象を見つけなければならないように思える。だがそうなると、私たちはすでにそれについて書いてしまうのではないか？