論文の概要: Context-Free Recognition with Transformers

• arxiv url: http://arxiv.org/abs/2601.01754v1
• Date: Mon, 05 Jan 2026 03:14:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-06 16:25:22.748073
• Title: Context-Free Recognition with Transformers
• Title（参考訳）: 変圧器を用いた文脈自由認識
• Authors: Selim Jerad, Anej Svete, Sophie Hao, Ryan Cotterell, William Merrill,
• Abstract要約: 我々は、$mathcalO(log n)$ looping layerと$mathcalO(n6)$ padding tokensで全てのCFLを認識可能であることを示す。 実験の結果を実証的に検証し,対数深度を必要とする言語にループが有効であることを示す。
• 参考スコア（独自算出の注目度）: 57.46376097734401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Transformers excel on tasks that process well-formed inputs according to some grammar, such as natural language and code. However, it remains unclear how they can process grammatical syntax. In fact, under standard complexity conjectures, standard transformers cannot recognize context-free languages (CFLs), a canonical formalism to describe syntax, or even regular languages, a subclass of CFLs (Merrill et al., 2022). Merrill & Sabharwal (2024) show that $\mathcal{O}(\log n)$ looping layers (w.r.t. input length $n$) allows transformers to recognize regular languages, but the question of context-free recognition remained open. In this work, we show that looped transformers with $\mathcal{O}(\log n)$ looping layers and $\mathcal{O}(n^6)$ padding tokens can recognize all CFLs. However, training and inference with $\mathcal{O}(n^6)$ padding tokens is potentially impractical. Fortunately, we show that, for natural subclasses such as unambiguous CFLs, the recognition problem on transformers becomes more tractable, requiring $\mathcal{O}(n^3)$ padding. We empirically validate our results and show that looping helps on a language that provably requires logarithmic depth. Overall, our results shed light on the intricacy of CFL recognition by transformers: While general recognition may require an intractable amount of padding, natural constraints such as unambiguity yield efficient recognition algorithms.
• Abstract（参考訳）: トランスフォーマーは、自然言語やコードなどの文法に従って、十分に整形された入力を処理するタスクを排他的に処理する。 しかし、文法的な構文をどのように処理できるかは定かではない。 実際、標準的な複雑性予想の下では、標準変換子は文脈自由言語(CFL)を認識できない。 Merrill & Sabharwal (2024) は、$\mathcal{O}(\log n)$ looping layer (w.r.t. input length $n$) が変換器が正規言語を認識できることを示したが、文脈自由認識の問題は未解決のままである。 この研究では、$\mathcal{O}(\log n)$ looping layer と $\mathcal{O}(n^6)$ padding tokens が全ての CFL を認識可能であることを示す。 しかし、$\mathcal{O}(n^6)$padding tokensによるトレーニングと推論は現実的ではない可能性がある。 幸いなことに、不明瞭なCFLのような自然のサブクラスでは、変換器の認識問題はよりトラクタブルになり、$\mathcal{O}(n^3)$パディングが必要になる。 実験の結果を実証的に検証し,対数深度を必要とする言語にループが有効であることを示す。 一般認識には難易度の高いパディングを必要とするかもしれないが、曖昧さのような自然な制約は効率的な認識アルゴリズムをもたらす。

関連論文リスト

• Exact Expressive Power of Transformers with Padding [33.4994300801846]
  O(logd n)$ looping on inputs of length recognize exactly the class $mathsfFO$uniform $mathsfTCd$ moderately parallelizable problem。 この結果は,テスト時間計算における思考の連鎖に対する並列化可能な代替手段として,パディングとループのさらなる探索を動機付けている。
  論文  参考訳（メタデータ） (2025-05-25T02:52:15Z)
• Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
  2種類のランダムな$n$-gram LMを学習するトランスフォーマーの能力について検討する。 例えば、$n$-gram LMに対する古典的な推定手法として、add-$lambda$ smoothing outperform transformerがある。
  論文  参考訳（メタデータ） (2024-10-03T21:21:02Z)
• Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers [8.908747084128397]
  時間カウントロジックの $textsfK_textt$[#] と RASP の $textsfC-RASP$ を紹介します。 それらが互いに等価であることを示し、それらが結合されていない入力サイズを持つ将来のマスキング型ソフトアテンショントランスの形式的表現性に最もよく知られた下界であることを示す。
  論文  参考訳（メタデータ） (2024-04-05T20:36:30Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• Physics of Language Models: Part 1, Learning Hierarchical Language Structures [51.68385617116854]
  トランスフォーマーベースの言語モデルは効率的だが複雑であり、内部の動作や推論メカニズムを理解することは大きな課題である。 本稿では,長文を生成可能な階層規則を生成する合成CFGのファミリーを紹介する。 我々は、GPTのような生成モデルがCFG定義階層を正確に学習し、推論し、それに基づいて文を生成することを実証する。
  論文  参考訳（メタデータ） (2023-05-23T04:28:16Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。