論文の概要: Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete

• arxiv url: http://arxiv.org/abs/2606.01532v1
• Date: Mon, 01 Jun 2026 01:28:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:29.771981
• Title: Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
• Title（参考訳）: 位置符号化の役割を再考する: PE残調を伴わないスライディング・ウィンドウ変換器
• Authors: Qian Li, Xinyu Mao, Shang-Hua Teng,
• Abstract要約: 位置符号化(PE)は、整列処理に必要な変換器として広く見なされている。 この直観は、任意の普遍性を実現することができることを証明するために位置情報に依存する全ての先行結果の根底にある。 我々は、この信念を、有限なスライディングコンテキストウインドウを通して生成が進行する、長期的推論に最も関係のある体制に再考する。
• 参考スコア（独自算出の注目度）: 13.001718919406164
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Positional encoding (PE) is widely viewed as necessary for transformers to process ordered sequences: without them, the next-token map appears permutation-invariant in its context tokens. This intuition underlies all prior universality results, which rely on positional information to prove that transformers with chain-of-thought can perform arbitrary computation, i.e., they are Turing complete. We revisit this belief in the regime most relevant to long-form reasoning, where generation proceeds through a finite sliding context window. Our opening perception is that the window mechanism itself (mildly) breaks the permutation symmetry. To distill and precisely capture the degree of this added expressiveness, we introduce an abstract autoregressive model, the HIST model, in which each update depends only on constant-size internal state and the token-count histogram within the current window. We prove that this HIST model is Turing complete by showing that the evolution of the window can reveal the token that has just left the window, which suffices to simulate Turing-complete Post machines. We then construct a sliding-window transformer over a constant-size token alphabet, without PE, and show that it can simulate the HIST model. Our result demonstrates that positional encodings are not indispensable for transformers to perform universal computation: The window sliding itself already breaks permutation symmetry and captures sufficient positional information.
• Abstract（参考訳）: 位置符号化(PE)は、トランスフォーマーが順序付けられたシーケンスを処理するために必要であると考えられており、それらなしでは、次のトーケン写像はそのコンテキストトークンに置換不変である。 この直観は任意の計算、すなわちチューリング完全であることを示すために位置情報に依存する全ての先行普遍性の結果の基盤となる。 我々は、この信念を、有限なスライディングコンテキストウインドウを通して生成が進行する、長期的推論に最も関係のある体制に再考する。 我々のオープニング・インセプションは、ウィンドウ機構自体が(わずかに)置換対称性を破るということです。 この付加表現性の度合いを抽出し,正確に把握するために,各更新は,現在のウィンドウ内の一定サイズの内部状態とトークン数ヒストグラムにのみ依存する抽象自己回帰モデル,HISTモデルを導入する。 我々は、このHISTモデルがチューリング完全であることを証明し、ウィンドウの進化によってちょうどウィンドウを離れたトークンが明らかになり、それがチューリング完全Postマシンをシミュレートするのに十分であることを示す。 次に,PEを使わずに,一定サイズのトークンアルファベット上にスライディングウィンドウ変換器を構築し,HISTモデルをシミュレート可能であることを示す。 ウィンドウスライディング自体は、置換対称性を破り、十分な位置情報をキャプチャする。

関連論文リスト

• Clebsch-Gordan Transformer: Fast and Global Equivariant Attention [19.720202550140325]
  我々はClebsch-Gordon Transformerを提案し、新しいClebsch-Gordon Convolutionを$SO(3)$の既約表現で実現した。 提案手法は,O(N log N)$入力トークンの複雑さを達成しつつ,任意の順序で特徴の同変モデリングを可能にする。 提案手法は,n体シミュレーション,QM9,ModelNet点クラウド分類,ロボットによる把握データセットなど,さまざまなベンチマークでベンチマークを行う。
  論文  参考訳（メタデータ） (2025-09-28T22:09:36Z)
• Constant Bit-size Transformers Are Turing Complete [6.70318953627082]
  任意の長さの入力で動くチューリングマシンは、定ビットサイズの変圧器でシミュレートできることを示す。 提案手法は,チューリング完全計算モデルであるPostマシンのシミュレーションに依存する。
  論文  参考訳（メタデータ） (2025-05-22T02:45:38Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  CoT推論による現代言語モデル(LM)の性能向上 LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
  論文  参考訳（メタデータ） (2024-06-20T10:59:02Z)
• Vision Transformer with Quadrangle Attention [76.35955924137986]
  窓面に基づく注意を一般的な四角形定式化に拡張する新しい四角形注意法(QA)を提案する。 提案手法では,既定のウィンドウを対象の四角形に変換するために,変換行列を予測し,エンドツーエンドで学習可能な四角形回帰モジュールを用いる。 QAをプレーンかつ階層的な視覚変換器に統合し、QFormerという名の新しいアーキテクチャを作成します。
  論文  参考訳（メタデータ） (2023-03-27T11:13:50Z)
• Token Turing Machines [53.22971546637947]
  Token Turing Machines (TTM) はシーケンシャルな自己回帰型トランスフォーマーモデルである。 我々のモデルは、セミナルなニューラルチューリングマシンにインスパイアされ、以前の履歴を要約するトークンの集合からなる外部メモリを持つ。
  論文  参考訳（メタデータ） (2022-11-16T18:59:18Z)
• AAformer: Auto-Aligned Transformer for Person Re-Identification [82.45385078624301]
  トランスアーキテクチャにおけるアライメント方式を初めて導入する。 本研究では,人体と非人体の両方をパッチレベルで自動的に検出する自動整列トランス (AAformer) を提案する。 AAformerは、部分アライメントを自己アテンションに統合し、出力[PART]を直接検索する機能として使用することができる。
  論文  参考訳（メタデータ） (2021-04-02T08:00:25Z)

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

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