論文の概要: Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers
- arxiv url: http://arxiv.org/abs/2608.31067v1
- Date: Mon, 31 Aug 2026 16:42:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-01 18:31:31.520238
- Title: Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers
- Title（参考訳）: 回路計算用ユニバーサル変圧器:Tiny変換器の完全長一般化
- Abstract要約: 我々は,任意の深さや長さの問題を学習し,評価することのできる,確実に正しい変圧器パラメータ化を提案する。
提案手法は,変圧器に埋め込まれた回路モデルとしてアルゴリズムタスクを概念化し,単一の前方通過で深度1回路の低減を可能にする。
- 参考スコア（独自算出の注目度）: 15.437559038107144
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learning generalizable algorithmic computations remains a challenge for neural networks, as reflected in persistent failures on compositional and length generalization benchmarks. We present a provably correct, transformer parameterization (with only 280 learnable parameters for Boolean algebra tasks) capable of learning and evaluating problems of any depth or length. We assume inputs are fully parenthesized, well-formed expressions. Our approach conceptualizes algorithmic tasks as circuit models embedded in transformers, enabling depth-1 circuit reduction in a single forward pass. To achieve depth generalization, we introduce a positional encoding that tracks each gate's depth within the circuit, enabling the model to identify evaluable subexpressions at each iteration via masked hard attention, with $O(n)$ per-iteration complexity via linear attention. Combined with an autonomous halting criterion, the model terminates after $d$ iterations for problems of depth $d$, yielding $O(n \cdot d)$ total complexity. We show that training on shallow problem instances (depth 1 and depth 2) effectively recovers interpretable parameters that {\em snap} into place, resulting in exact length generalization. Though we establish that our construction provably evaluates Boolean expressions -- a universal symbolic computation -- of arbitrary length perfectly, in other experiments we also demonstrate that our transformer variant can learn and generalize perfectly (100% accuracy) on other common length generalization benchmarks, including modular arithmetic and ListOps.
- Abstract（参考訳）: 一般化可能なアルゴリズム計算の学習は、合成および長さの一般化ベンチマークにおける永続的な失敗に反映されるように、ニューラルネットワークにとって依然として課題である。
本稿では,任意の深さや長さの問題を学習し,評価することができる,確率的に正しい変圧器パラメータ化(ブール代数問題では280個の学習可能なパラメータのみ)を提案する。
入力は完全に括弧化され、よく形づくられた表現であると仮定する。
提案手法は,変圧器に埋め込まれた回路モデルとしてアルゴリズムタスクを概念化し,単一の前方通過で深度1回路の低減を可能にする。
深度一般化を実現するために,回路内の各ゲートの深さをトラックする位置符号化を導入し,各繰り返しにおける評価可能な部分表現をマスク付きハードアテンションにより同定する。
自律的な停止基準と組み合わせて、このモデルは深さ$d$の問題に対して$d$反復した後で終了し、O(n \cdot d)$トータル複雑性をもたらす。
浅部問題インスタンス(深度1,深さ2)のトレーニングは,スナップした解釈可能なパラメータを効果的に回収し,正確な長さの一般化をもたらすことを示す。
我々の構成は任意の長さのブール式(普遍的な記号計算)を完璧に評価するが、他の実験ではモジュラー算術やリストOpsを含む他の共通長一般化ベンチマーク上でトランスフォーマー変種が完全に(100%の精度で)学習し、一般化できることも示している。
関連論文リスト
- Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't [78.36679389968772]
パッド付き$textL$ constantprecision transformerは、表現性に対して驚くほど堅牢である。
glogd-looped constant-precision transformer reach $textFO-uniform TCd$, growing-precision transformer reach $textFO-uniform TCd$
論文 参考訳（メタデータ） (2026-05-28T19:58:43Z) - Barriers to Universal Reasoning With Transformers (And How to Overcome Them) [46.59247939156339]
CoT(Chain-of-Thought)は、トランスフォーマーの性能を実証的に改善し、理論的にはチューリング完全性への表現性を高めることが示されている。
我々は、Transformer長の一般化に関する最近の理論フレームワークを使用し、標準的な位置エンコーディングと有限アルファベットの下では、CoT を持つ変換器は$TC0$以上の問題を解くことができない。
我々は,シミュレーション実行時のCoTトレース長が一定まで線形であるチューリングマシンの時間一般化可能なシミュレーションを実現する。
論文 参考訳（メタデータ） (2026-04-28T16:10:37Z) - Looped Transformers for Length Generalization [41.99378201613648]
適応的なステップ数を持つループ変換器は長さの一般化を著しく向上することを示す。
我々は,提案した学習アルゴリズムを用いてループ変換器を訓練し,様々なタスクに対して,高度に長大な一般化可能な解を学習することを確認する。
論文 参考訳（メタデータ） (2024-09-24T01:21:17Z) - On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。
クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
論文 参考訳（メタデータ） (2024-08-15T17:09:08Z) - Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。
この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文 参考訳（メタデータ） (2024-02-20T10:11:03Z) - Transformers Can Achieve Length Generalization But Not Robustly [76.06308648699357]
長さ一般化の成功は,データ形式や位置エンコーディングのタイプと密接に関連していることを示す。
標準変換器が入力長の2.5倍のシーケンス長に外挿できることを初めて示す。
論文 参考訳（メタデータ） (2024-02-14T18:18:29Z) - What Algorithms can Transformers Learn? A Study in Length Generalization [23.970598914609916]
アルゴリズムタスクにおける長さ一般化の具体的設定におけるトランスフォーマーの能力の範囲について検討する。
具体的には、Transformerの計算モデル用に設計されたプログラミング言語であるRASPを利用する。
我々の研究は、構成一般化のメカニズムとトランスフォーマーのアルゴリズム能力に関する新しい視点を提供する。
論文 参考訳（メタデータ） (2023-10-24T17:43:29Z) - Transformers Learn Shortcuts to Automata [52.015990420075944]
低深度変換器は任意の有限状態オートマトンを計算できる。
我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。
さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
論文 参考訳（メタデータ） (2022-10-19T17:45:48Z) - Iterative Decoding for Compositional Generalization in Transformers [5.269770493488338]
シーケンシャル・ツー・シークエンス・ラーニングでは、トランスフォーマーは極端に長い例に対して正しい出力を予測できないことが多い。
本稿では,Seq2seq学習に代わる反復復号法を提案する。
反復復号により訓練されたトランスフォーマーはPCFGデータセット上でセq2seqよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-10-08T14:52:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。