パディングを用いたトランスフォーマーの正確な表現力

思考の連鎖は、トランスフォーマーに基づく大規模言語モデル（LLM）の計算力を高める自然な推論時の手法ですが、逐次デコーディングのコストが伴います。パラメータを増やさずにトランスフォーマーの表現力を広げるより効率的な代替手段はあるのでしょうか？私たちは、トランスフォーマーにパディングトークンを加えることを並列化可能なテスト時計算の一形態として考えます。ポリノミアルパディングを用いたアベレージングハードアテンション、マスクプレンームトランスフォーマーは、極めて並列化可能な問題のクラスTC⁰に正確に収束することを示します。TC⁰の上限は知られていましたが、対応する下限を証明することは困難でした。さらに、私たちの新しい分析は、ループを介して深さを動的に増やすという別の推論時計算と組み合わされた場合のパディングトランスフォーマーの正確な拡張力を明らかにします。私たちの主要な技術的貢献は、パディングが古典的複雑性理論の基礎である完全な問題と還元の概念をトランスフォーマーの正式な研究に持ち込む方法を示すことです。この新しいツールを用いて、長さnの入力に対してO(ᵈ n)のループを用いるパディングトランスフォーマーが、適度に並列化可能な問題のクラスTCᵈを正確に認識することを証明します。したがって、パディングとループを組み合わせることで、トランスフォーマーの表現力が体系的に拡大されます：ポリ対数的ループを用いることで、パディングトランスフォーマーは並列性を失うことなく期待される最善のクラスNCに収束します（NC = Pでない限り）。したがって、私たちの結果は、思考の連鎖に対する並列化可能な代替手段としてのパディングとループのさらなる探求を促します。