🤖 machine learning

Parity, Sensitivity, and Transformers

本論文は、感度制約により単層トランスフォーマが PARITY 課題を計算できないことを証明することで、単層トランスフォーマが PARITY 課題を計算できるかどうかという未解決の問題を解決し、同時に、長さ依存の位置符号化やハードマックスといった以前に必要とされていた非現実的な仮定に依存せずに PARITY を解決する実用的な 4 層トランスフォーマの構成を提示する。

原著者： Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wał\cega

公開日 2026-05-08

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

CC BY 4.0

原著者： Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wał\cega

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

あなたが、非常に賢いものの、少しだけ硬直したロボットに、**「パリティゲーム」**と呼ばれるシンプルなゲームの遊び方を教えるところを想像してみてください。

このゲームでは、ロボットは赤（0）と青（1）のいくつかのライトが並んだ長い文字列を見せられます。ロボットの唯一の任務は、次の 1 つの質問に答えることです：「青いライトの総数は偶数か、それとも奇数か？」

青いライトが 3 つあれば、答えは「奇数」です。4 つあれば、答えは「偶数」です。

これは私たちにとっては簡単に見えるかもしれませんが、トランスフォーマー（多くの現代のチャットボットや翻訳機を動かしている種類の AI 構造）と呼ばれる特定の AI 構造にとっては、このゲームは謎でした。科学者たちは議論を続けてきました：このロボットがゲームを解くために、何層の「思考層」が必要なのか？

以下に、この論文が発見した内容を、シンプルに解説します。

1. 「1 層」のロボットはあまりにも愚か

著者たちはまず、次の問いを投げかけました：たった1 層の思考層を持つトランスフォーマーは、この問題を解くことができるか？

彼らは、答えが**「いいえ」**であることを証明しました。

比喩： ロボットを、赤か青のカードを掲げている人々でいっぱいの部屋に立っている人物だと想像してください。その人物は全員を一度に見て、素早く「平均」的な一瞥をとるだけです。

「パリティ」ゲームは極めて敏感です。たった1 人の人物のカードを赤から青に変えるだけで、答えは完全に反転します（偶数から奇数へ）。
著者たちは、1 層のロボットはあまりにも「滑らか」で「怠惰」であることを示しました。それは単一の変化に対して鋭く反応することができません。まるで、平均的な風速だけを聞いて、ハリケーンの中でピンが落ちる音を検知しようとしているようなものです。ロボットの「感度」は、ゲームを解くために必要な小さく重要な変化を捉えるには、あまりにも緩やかにしか成長しません。

結論： この問題を解くには、少なくとも2 層の思考が必要です。

2. 「過去の解決策」にはあまりにも多くのハックが含まれていた

この論文以前、他の科学者たちはこのゲームを解くことができるトランスフォーマーの構築方法を突き止めましたが、彼らはいくつかの「チート」や非現実的な設定を使用せざるを得ませんでした。

「魔法の定規」： 彼らはロボットに、読み始める前に文字列の正確な長さを知る定規を与えました（例：「この文字列は正確に 1,000 文字です」）。実際のロボットは、読み終えるまで自分が読んでいる文章の長さを知らないのが普通です。
「完璧なスイッチ」： 彼らは、実際のロボットが使用する「柔らかく曖昧な」確率スイッチではなく、即座に二値の決定を行う「ハードスイッチ」を使用しました。
「ゼロ誤差」フィルター： 通常、ロボットの数値が無限大に暴走するのを防ぐ安全フィルター（LayerNorm）を除去しました。

これらの解決策は紙の上では機能しましたが、実際の AI 学習には存在しない仮定に依存していたため、現実世界では機能しませんでした。

3. 新しい、現実世界の解決策

この論文の著者たちは、これらのチートを一切使用せずにパリティゲームを解く新しいロボットを構築しました。

「魔法の定規」なし： これは「長さ非依存」の位置エンコーディングを使用します。文字列の総長を事前に知る必要はなく、単に要素同士が互いに対してどこにあるかを見るだけです。
ソフトスイッチ： 実際のチャットボットで使用されている標準的な「ソフト」アテンションを使用します。
安全フィルター： 安全フィルターを除去する必要なく機能します。
欠点： チートなしでこれを行うためには、ロボットは 2 層ではなく4 層の思考を必要とします。

比喩：
古い「チート」付きの解決策は、テーブルの下に隠された答えの鍵を覗き見ることでパズルを解くマジシャンのようなものです。
新しい解決策は、同じパズルを慎重にすべての手がかりを検証し、それらを相互参照し、少し多くの作業（2 層ではなく 4 層）を行うことで解く名探偵のようなものです。これは少し遅く、より多くの「脳力」（深さ）を必要としますが、魔法の舞台ではなく、実際の法廷で機能します。

画期的な発見のまとめ

下限： 1 層だけのトランスフォーマーは、数学的にパリティゲームを解くことが不可能です。これは学習の問題ではなく、ロボットにはそれを遂行するためのアーキテクチャが物理的に備わっていないのです。
上限： トランスフォーマーでゲームを解くことは可能ですが、現実的な方法（長さ依存のトリックによるチートや安全フィルターの除去なし）で行うためには、4 層が必要です。

この論文は本質的に、砂地に明確な線を引いています。「現実的な AI に奇数と偶数を数えさせたいなら、少なくとも 4 層の深さを与えなさい。それ以下では、数学的に不可能だ」と。

提供されたテキストに基づき、「Parity, Sensitivity, and Transformers」という論文の詳細な技術的要約を以下に示す。

問題定義

本論文は、特にPARITYタスクに関するトランスフォーマーアーキテクチャの表現力という根本的な問いに取り組んでいる。PARITY は、二値入力シーケンス内の 1 の数が奇数であれば 1 を、そうでなければ 0 を出力するブール関数である。これは、任意の単一ビットを反転させるだけで出力が変化する高い感度（sensitivity）で知られる、理論計算機科学における典型的な問題である。

これまでの研究では、ハードアテンション機構（具体的には Unique Hard Attention または UHAT）を持つトランスフォーマーは、一定の深さで PARITY を計算できないことが確立されていたが、ソフト（softmax）アテンションを持つトランスフォーマーの能力については依然として不明確な点が多かった。PARITY を計算可能なソフトアテンション・トランスフォーマーの既存の構成は、以下のような「非現実的」な仮定に依存していた。

入力全体の長さ（ $n$ ）に依存する位置符号化。
ハードアテンション機構。
正則化パラメータ $\epsilon = 0$ を用いたレイヤーノーマライゼーション。
因果的マスク（causal masking）との非互換性。

さらに、単一層のトランスフォーマーが PARITY を計算できるかどうかは、未解決の問題となっていた。

手法

著者らは、PARITY に対するトランスフォーマーの表現力の下限と上限（構成）を扱うために、2 つの異なる方法論的アプローチを採用している。

1. 平均感度による下限
単一層のトランスフォーマーが PARITY を計算できないことを証明するために、著者らは平均感度（average sensitivity）の概念を利用する。

定義: 関数 $f$ の平均感度とは、入力ビットの位置を反転させたときに関数の出力が変化する、そのような位置の数の期待値である。PARITY の場合、この値は正確に $n$ （線形成長）である。
論理: 著者らは、単一層トランスフォーマーの計算を、実数の一階述語論理 $(\mathbb{R}, <, +, \cdot)$ で表現可能な関数としてモデル化する。タルスキー・サイデンベルク定理（量詞除去）を適用することで、単一層トランスフォーマーによって計算される任意の関数は、固定された数の低次数多項式閾値関数（PTF）のブール結合として表現できることを示す。
境界設定: Kane の結果を引用することで、低次数 PTF の平均感度の成長率が $O(\sqrt{n} \cdot (\log n)^{O(1)})$ であることを確立する。PARITY の平均感度が線形（ $n$ ）で成長するのに対し、単一層トランスフォーマーではこれを計算できない。

2. 新たな構成による上限
PARITY が非現実的な仮定なしにトランスフォーマーによって計算可能であることを示すために、著者らは新しい4 層構成を提案する。

機構: この構成は、softmax アテンションと長さに依存せず、多項式で有界な位置符号化を使用する。レイヤーノーマライゼーションを回避し、フルアテンションおよび因果的マスクの両方の条件下で機能する。
アルゴリズム的戦略:
1. 第 1 層: 入力ビットの重み付き和を計算し、1 の数（ $\Sigma$ ）に関連する値 $\gamma$ を導出する。
2. 第 2 層: 位置符号化（ $i \mapsto (\ln i, i^{10})$ ）と値 $\gamma$ を用いて、重み付き平均 $\Gamma$ を計算する。この値は、 $\Sigma$ に関する情報を符号化する関数 $f(\rho)$ を近似する。
3. 第 3 層: 位置 $i = \Sigma$ に強く集中するアテンション重み $L_{i,n}$ を構築する。これは、第 2 層で計算された値 $\Gamma$ を用いて、 $i = \Sigma$ でピークとなる特定の二次形式を近似することによって達成される。著者らは、正しい位置におけるアテンション重みが、他の任意の位置よりも著しく大きい（ $\Omega(n^6)$ のマージン）ことを証明する。
4. 第 4 層: 集中したアテンション重みを用いて $(-1)^i$ の重み付き和を計算する。その結果、 $(-1)^\Sigma$ に近い値 $z$ が得られ、最終層が偶数と奇数のパリティを区別することを可能にする。
大規模入力の処理: 1 の数（ $\Sigma$ ）が大きい場合に対処するため、この構成は入力を $M$ 個の部分列（ $M$ は偶数の定数）に分割し、それぞれのパリティを並列に計算して結果を集約する。

主要な貢献と結果

単一層の未解決問題の解決: 単一層トランスフォーマーが PARITY を計算できるかどうかという未解決の問題に、本論文は決定的な回答を与える。その結果は否定的である。著者らは、単一層トランスフォーマーによって計算可能な任意の関数の平均感度が $O(\sqrt{n} \cdot (\log n)^{O(1)})$ によって制限されることを証明しており、これは PARITY の線形感度には不十分であることを示している。
PARITY のための改善された構成: 著者らは、PARITY を計算する新しい4 層トランスフォーマー構成を提示する。この構成は、いくつかの制限的な仮定を排除することで、先行研究（例：Chiang and Cholak, 2022; Yang et al., 2025）を改善している。
- ハードアテンションではなく、ソフトアテンション（softmax）を使用する。
- 長さに依存しない位置符号化を採用する。
- レイヤーノーマライゼーションを必要としない（具体的には、 $\epsilon=0$ に依存しない）。
- 因果的マスクと互換性がある。
- 位置符号化は多項式で有界であり、実用的な入力長に対して実現可能である。
深さの要件: 本論文は、1 層では不十分である一方、現実的な設計制約の下では 4 層で十分であることを確立する。これにより、高感度な関数を計算するための深さ要件に関する理解が精緻化される。

意義

本論文は、PARITY タスクに対するトランスフォーマーの深さ要件を正確に特徴づけることで、トランスフォーマーアーキテクチャの理論的理解を前進させる。トランスフォーマーの表現力をブール関数の平均感度に結びつけることで、著者らは単一層モデルを排除する厳密な下限を提供する。同時に、標準的なアーキテクチャ慣行（ソフトアテンション、因果的マスク、有界な符号化）に準拠した 4 層構成を提供することで、本論文は、理論的な人工物に頼ることなく PARITY がトランスフォーマーによって計算可能であることを実証する。

著者らは、これらの結果が、トレーニング中にトランスフォーマーが PARITY のようなタスクで一般化することに苦労する理由を説明する助けになると指摘している。この関数は、モデルが浅すぎたり制約されすぎたりして、標準的な勾配降下法では容易に学習できない可能性のある、特定の深さとアーキテクチャ構成を必要とする。この研究は、ハードアテンションモデルの表現力に関する既存の文献を補完し、ソフトアテンション・トランスフォーマーの能力に対するより現実的な基準を提供する。