Fugu-MT 論文翻訳(概要): Exact Expressive Power of Transformers with Padding

論文の概要: Exact Expressive Power of Transformers with Padding

arxiv url: http://arxiv.org/abs/2505.18948v1
Date: Sun, 25 May 2025 02:52:15 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-27 16:58:42.773073
Title: Exact Expressive Power of Transformers with Padding
Title（参考訳）: ポーディングを有する変圧器の特殊表現力
Authors: William Merrill, Ashish Sabharwal,
Abstract要約: 長さ$n$の入力に対して$O(logd n)$ループするパッド付き変換器は、適度に並列化可能な問題のクラス$mathsfTCd$を正確に認識する。この結果から, パディングとループのさらなる探索が, 思考の連鎖に対する並列化可能な代替手段として動機づけられた。
参考スコア（独自算出の注目度）: 29.839710738657203
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Chain of thought is a natural inference-time method for increasing the computational power of transformer-based large language models (LLMs), but comes at the cost of sequential decoding. Are there more efficient alternatives to expand a transformer's expressive power without adding parameters? We consider transformers with padding tokens as a form of parallelizable test-time compute. We show that averaging-hard-attention, masked-pre-norm transformers with polynomial padding converge to precisely the class $\mathsf{TC}^0$ of extremely parallelizable problems. While the $\mathsf{TC}^0$ upper bound was known, proving a matching lower bound had been elusive. Further, our novel analysis reveals the precise expanded power of padded transformers when coupled with another form of inference-time compute, namely dynamically increasing depth via looping. Our core technical contribution is to show how padding helps bring the notions of complete problems and reductions, which have been a cornerstone of classical complexity theory, to the formal study of transformers. Armed with this new tool, we prove that padded transformers with $O(\log^d n)$ looping on inputs of length $n$ recognize exactly the class $\mathsf{TC}^d$ of moderately parallelizable problems. Thus, padding and looping together systematically expand transformers' expressive power: with polylogarithmic looping, padded transformers converge to the class $\mathsf{NC}$, the best that could be expected without losing parallelism (unless $\mathsf{NC} = \mathsf{P}$). Our results thus motivate further exploration of padding and looping as parallelizable alternatives to chain of thought.
Abstract（参考訳）: 思考の連鎖は、トランスフォーマーベースの大規模言語モデル(LLM)の計算能力を高める自然な推論時間法であるが、逐次デコーディングのコストがかかる。パラメータを追加せずにトランスの表現力を拡大するより効率的な代替手段はあるのだろうか? 我々は、パラレル化可能なテスト時間計算の形式として、パディングトークンを持つトランスフォーマーを考察する。多項式パディングを持つ平均的ハードアテンション、マスク付きプレノーム変換器は、非常に並列化可能な問題のクラス $\mathsf{TC}^0$ に正確に収束することを示す。 $\mathsf{TC}^0$上界は知られていたが、一致する下界の証明は発散していた。さらに,新しい解析により,ループ化により動的に深度を増大させる他の方式の推論時間計算と組み合わせることで,パッド型変圧器の精度が向上することを明らかにした。私たちの中核的な技術的貢献は、パディングが、古典的な複雑性理論の基礎となった完全な問題と縮小の概念をトランスフォーマーの形式研究にどうもたらすかを示すことである。この新しいツールを駆使して、$O(\log^d n)$ループのパッド付き変換器が$n$の入力を正確にクラス $\mathsf{TC}^d$ に並列化可能な問題を認識することを証明した。したがって、パディングとループは変換器の表現力を体系的に拡張する: 多対数ループでは、パッド変換器はクラス $\mathsf{NC}$ に収束する($\mathsf{NC} = \mathsf{P}$ を除いて)。この結果から, パディングとループのさらなる探索が, 思考の連鎖に対する並列化可能な代替手段として動機づけられた。

論文の概要: Exact Expressive Power of Transformers with Padding

関連論文リスト