論文の概要: Algebraic Decomposition Theory for Transformer Length Generalization
- arxiv url: http://arxiv.org/abs/2608.13433v1
- Date: Thu, 13 Aug 2026 16:20:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-14 18:29:38.599329
- Title: Algebraic Decomposition Theory for Transformer Length Generalization
- Title（参考訳）: 変圧器長一般化のための代数分解理論
- Abstract要約: トランスフォーマーベースの言語モデルは、トレーニング中に見るよりも長いシーケンスに一般化することが知られている。
正規言語トランスフォーマーが長大に一般化する部分でさえない。
言語構文学の規模で基礎的な時間で実行される決定アルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 3.3891966537305733
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Transformer-based language models are known to sometimes generalize to sequences longer than seen during training, but we lack a precise characterization of which tasks admit length generalization. It is not even known which regular languages transformers length-generalize on -- and this is a foundational class of languages. Our contributions are to establish the first complete characterization of which regular languages transformers length-generalize on and provide a decision algorithm running in polynomial time in the size of the language's syntactic monoid. These results rely on an effective characterization of the regular languages in C-RASP, a recently-established formalism that expresses which languages transformers length-generalize on. This characterization is challenging because classical tools like Krohn-Rhodes decomposition theory for finite semigroups are insufficient for C-RASP. Firstly, the basic building blocks of Krohn-Rhodes theory -- flip-flop and simple groups -- are not expressible in C-RASP. Secondly, the basic building block of C-RASP (unbounded counting) is not expressible by the finite semigroups of Krohn-Rhodes theory. Thus, length generalization on regular languages is controlled by an algebraic property that is invisible to classical finite decomposition theory. We generalize classical decomposition theory from finite semigroups to the infinite additive group on the integers, allowing us to characterize C-RASP in terms of iterated wreath products of the integers and derive a provable polynomial-time decision algorithm for regular language membership. Experiments across a broad test suite of regular languages confirm that our theory captures transformers' length-generalization behavior more accurately than existing classifications.
- Abstract（参考訳）: トランスフォーマーに基づく言語モデルは、トレーニング中に見るよりも長いシーケンスに一般化することが知られているが、長さの一般化を許容するタスクの正確な特徴は欠如している。
正規言語がどのトランスフォーマーが長大に一般化するかは分かっていないが、これは言語の基本的なクラスである。
我々の貢献は、正規言語トランスフォーマーが長大に一般化する最初の完全な特徴付けを確立することであり、言語の構文モノイドのサイズで多項式時間で実行される決定アルゴリズムを提供することである。
これらの結果は、C-RASPにおける正規言語を効果的に特徴づけることに依存している。
この特徴づけは、有限半群に対するKrohn-Rhodes分解理論のような古典的なツールが C-RASP に対して不十分であるため、難しい。
まず、Krohn-Rhodes理論(フリップフロップと単純群)の基本構成ブロックは、C-RASPでは表現できない。
第二に、C-RASP (unbounded counting) の基本構成ブロックは、クロン・ローデ理論の有限半群によって表現できない。
したがって、正規言語上の長さ一般化は古典的有限分解理論には見えない代数的性質によって制御される。
古典的分解理論を有限半群から整数上の無限加法群に一般化し、整数の反復 Wreath 積の項で C-RASP を特徴づけ、正規言語のメンバーシップに対する証明可能な多項式時間決定アルゴリズムを導出する。
正規言語の幅広いテストスイートにおける実験により、我々の理論は変圧器の時間一般化挙動を既存の分類よりも正確に捉えていることが確認された。
関連論文リスト
- Efficient Learning and Symmetry Discovery under Exact Invariances [62.27019402162741]
群不変性による学習は多くの科学的および幾何学的な学習問題の中心である。
与えられた群作用のちょうど部分群にある回帰関数を効率的に計算できるかどうかは不明である。
有限群と無限群に一様に適用する正確な群不変量を持つ学習アルゴリズムを初めて提案する。
論文 参考訳（メタデータ） (2026-09-07T04:35:19Z) - Relative Prime Factorization and Finite-State Presentations under Fixed Finite-Monoid Observation [0.0]
相対的な$_L,h:equiv_Lcapker hにおける正確な分解と正準表現について検討した。
コンピュータで徹底的にチェックされた36ドル要素商は、生きた非単位クラスごとに独自の正確な素因数分解を持つ。
そこで,本研究では,一意の正確な因数分解,尾の正確性,尾の因数決定性,有効規則に基づく二次的境界を示す,素ターゲット左割決定性(PTLD)を導入する。
論文 参考訳（メタデータ） (2026-09-03T10:44:26Z) - Power Term Polynomial Algebra for Boolean Logic [10.458069629518985]
直交正規形(CNF)と代数正規形(ANF)を橋渡しするために設計されたブール公式の表現言語であるパワー項代数を導入する。
直接CNF->ANF変換は、式が小さな断片に分解されない限り指数的な爆発を引き起こす。
我々のフレームワークは、CNF節を直接表現しながら、モノミアルの構造化されたファミリーをコンパクトに符号化する、表現自体におけるこのミスマッチに対処する。
論文 参考訳（メタデータ） (2026-03-14T09:22:52Z) - Characterizing the Expressivity of Transformer Language Models [56.598551673153366]
厳密な将来のマスキングとソフトアテンションを備えた固定精度変圧器の正確な特性について述べる。
これらのモデルは、線形時間論理の特定の断片と同じくらい正確に表現可能であることを示す。
さらに、この論理を形式言語理論、オートマトン理論、代数の確立されたクラスに関連付ける。
論文 参考訳（メタデータ） (2025-05-29T16:30:30Z) - The Role of Sparsity for Length Generalization in Transformers [58.65997625433689]
そこで本研究では,次の予測課題に対する長さの一般化を研究するための理論的枠組みを提案する。
予測された各トークンが前のトークンの小さな(固定された)数に依存する限り、長さの一般化が生じることを示す。
本稿では,位置結合手法で使用する位置IDを予測するために,変圧器を訓練する予測位置結合を導入する。
論文 参考訳（メタデータ） (2025-02-24T03:01:03Z) - Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価する。
3つのニューラルアーキテクチャに対して、チョムスキー階層の様々な言語について結果を提供する。
我々の貢献は、将来の研究において、言語認識の主張を理論的に健全に検証するのに役立つだろう。
論文 参考訳（メタデータ） (2024-11-11T16:33:25Z) - A Formal Framework for Understanding Length Generalization in Transformers [14.15513446489798]
因果変換器における長さ一般化を解析するための厳密な理論的枠組みを導入する。
我々は,この理論を,アルゴリズムおよび形式言語タスクにおける長さ一般化の成功と失敗の予測器として実験的に検証した。
論文 参考訳（メタデータ） (2024-10-03T01:52:01Z) - Regular language quantum states [0.5499796332553706]
量子多体状態の族である正規言語状態を導入する。
これらはレギュラー(regular)と呼ばれる特別な形式言語から作られる。
テンソルネットワークの理論を利用して、正規言語がシフト不変であるタイミングを決定する効率的な基準を求める。
論文 参考訳（メタデータ） (2024-07-24T21:09:22Z) - Compositional Generalization Requires Compositional Parsers [69.77216620997305]
直近のCOGSコーパスにおける構成原理によって導かれるシーケンス・ツー・シーケンスモデルとモデルを比較した。
構造一般化は構成一般化の重要な尺度であり、複雑な構造を認識するモデルを必要とする。
論文 参考訳（メタデータ） (2022-02-24T07:36:35Z) - Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
合成一般化のための代数的組換え学習のためのエンドツーエンドニューラルモデルLeARを提案する。
主要な洞察は、意味解析タスクを潜在構文代数学と意味代数学の間の準同型としてモデル化することである。
2つの現実的・包括的構成一般化の実験は、我々のモデルの有効性を実証している。
論文 参考訳（メタデータ） (2021-07-14T07:23:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。