定数精度浮動小数点TransformerDecoderが認識する言語の有限性・余有限性

Transformerモデル[1]の表現力，すなわち本質的に解決可能な問題に関する近年の理論的解析によって，様々な仮定の下での表現力の上限・下限が明らかになりつつある[2]．例えば1回のデコードに限定した場合，Transformerの表現力は回路複雑性クラスTC0程度である[3]．しかし思考の連鎖[4]のような手法で多項式回のデコードを許容すると，その表現力がPにまで拡張されることが示されている．一方で，これらの先行研究では理論的解析を容易にするため，行列計算に使用する浮動小数点数の精度について，無限精度(ℚやℝ)や入力系列長に対して対数的に増加する精度（O(log푛)精度）を仮定している．実際のモデルは定数精度(fp32やbf16等)で実装されており，十分に長い入力文字列の全情報を単一のベクトルに圧縮して保持できない．そのため，先行研究における枠組みでは実際のモデルの表現力を厳密に評価することは困難である．更に，先行研究ではAttention機構においてsoftmax関数の代わりにしばしばhardmax関数という理想化を行うが，両者は入力に対する出力の応答が大きく異なるため互いを完全に置換できない．本研究では，浮動小数点演算における定数精度の制約およびsoftmax関数の利用を前提に，現実的な設定におけるTransformerdecoderモデルの表現力を分析する．本研究の結果としてqueryとkeyの積に関する自然な仮定（仮定9）の下でTransformerが認識可能な言語が有限言語または余有限言語（3.1節）の対応と等しい．(2)が先行研究[3]による結果，(3)は本研究で証明した結果（定理10）．(2),(4)はデコード回数をO(1),O(log푛),O(푛)とした場合の上限をカンマで区切っている．また灰色で塗りつぶされている(1),(4)は本研究の定理を拡張することで証明可能と予想される結果．浮動小数点数精度O(1),仮定9O(log푛)hardmax(1)Finite∪Co-finite?(2)TC0,L,NC1[3](定理10の応用)softmax(3)Finite∪Co-finite(定理10)(4)TC0,L,NC1(定理10の応用)が得られた（定理10，表1左下）．さらに表1(1),(4)の灰色の場合については，本研究では直接扱わないが，定理10を拡張することで証明可能であると考える．