論文の概要: Length-Independent State Tracking Under a Parallel Scan

• arxiv url: http://arxiv.org/abs/2609.32447v1
• Date: Sat, 26 Sep 2026 10:27:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-07 09:04:41.134721
• Title: Length-Independent State Tracking Under a Parallel Scan
• Title（参考訳）: 並列走査による長さ非依存状態追跡
• Abstract要約: 堅牢でスケーラブルな有限状態追跡を学習することは、シーケンス処理に不可欠である。 我々は有限精度で有限状態追跡を定式化し、長さ独立性を特徴付ける。 長さ非依存有限状態追跡のための非アフィン・スキャン互換RNNであるNeural Finite-State Machine (NFSM)を紹介する。
• 参考スコア（独自算出の注目度）: 1.0184939933592572
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Learning robust and scalable finite-state tracking is fundamental to sequence processing. While linear recurrent neural networks (RNNs), linear attention, and state space models enable scalable parallel training through affine recurrences, their theoretical expressivity guarantees assume idealized arithmetic and do not extend to finite precision, where the parallel scan that makes them fast is itself a source of perturbation. We formalize finite-state tracking at finite precision and characterize length independence: tracking that stays correct at every sequence length, at a precision cost that does not grow with the length. We show that length-independent state tracking requires two competing dynamics within a single map: contraction to suppress numerical perturbations and separation to keep distinct states apart. We prove that affine recurrences, which offer a single rate at each step to serve both roles, realize at most definite automata at finite precision. Instead of treating scan compatibility as a restriction on the update map, we reinterpret it as a computational budget and introduce the Neural Finite-State Machine (NFSM): a nonaffine, scan-compatible RNN built for length-independent finite-state tracking. On synthetic benchmarks spanning abelian and nonabelian groups, noninvertible monoids, and textual state-tracking tasks, affine baselines fail on every nondefinite task, most of them within a few hundred steps. A single NFSM layer instead learns the exact transition tables of every algebraic task, which certifies correctness beyond the tested lengths, and a stack of NFSMs keeps perfect accuracy on the textual tasks at every tested length.
• Abstract（参考訳）: 堅牢でスケーラブルな有限状態追跡を学習することは、シーケンス処理に不可欠である。 線形リカレントニューラルネットワーク(RNN)、線形アテンション、状態空間モデルはアフィン繰り返しによるスケーラブルな並列トレーニングを可能にするが、理論的表現力は理想化された算術を仮定し、それを高速にする並列スキャン自体が摂動の源である有限精度に拡張しない。 有限状態追跡を有限精度で定式化し、長さ独立性を特徴付ける。 距離非依存状態追跡には, 数値摂動を抑える収縮と, 異なる状態を分離する分離という, 一つのマップ内での競合ダイナミクスが2つ必要であることを示す。 両役割を果たすために各ステップに1つのレートを与えるアフィン再帰が、有限精度で少なくとも一定のオートマトンを実現することを証明している。 スキャン互換性を更新マップ上の制約として扱う代わりに、計算予算として再解釈し、長さ非依存有限状態追跡のための非アフィンでスキャン互換なRNNであるNeural Finite-State Machine (NFSM)を導入する。 アーベル群と非アーベル群、非可逆モノイド、テキスト状態追跡タスクにまたがる合成ベンチマークでは、アフィンベースラインはすべての非定値タスクで失敗し、そのほとんどは数百ステップ以内に失敗する。 1つのNFSM層は、テストされた長さを超える正確さを証明した全ての代数的タスクの正確な遷移テーブルを学習し、NFSMのスタックはテストされた長さごとにテキストタスクに対して完全精度を維持する。

関連論文リスト

• Riccati State Space Models: Non-iterative Parallelization for Nonlinear Sequence Modeling [50.994194925685434]
  状態空間モデル(SSM)は、アフィン状態の更新が合成の下でクローズされるため、効率的なシーケンス処理を実現する。 リカレントモデルはよりリッチで状態依存のダイナミクスを提供するが、一般的にこの構成構造を失う。 我々は、状態依存の非線形力学は正確に構成可能なままに設計できるのかと問う。 非線形SSMである RiccatiSSM を導入し、各状態は入力条件付き Riccati 微分方程式に従う。
  論文  参考訳（メタデータ） (2026-09-28T15:40:55Z)
• Universality and Generalization of Causal Transformers Across Context Lengths [29.587685183870775]
  固定された正規化水平線をサンプリングする任意の長さの列に対して因果トークン・ツー・トケンマップを均一に近似できるかを検討した。 分解能間の連続性の概念は、長さに依存しないパラメータを持つ単一変圧器により、コンパクトな入力クラスに一様近似を許容する因果族を特徴づける。 物理時系列の実験は、データセット依存の適応指数を持つ観測スケールでのHlder-regularトークンモデルをサポートし、テキスト入力の埋め込みは対照的なケースを提供する。
  論文  参考訳（メタデータ） (2026-09-28T12:50:27Z)
• Recurrent neural networks approximate continuous functions [1.096028999747108]
  ネットワークは一度だけ選択できるのか、それとも、もっと長く走らせるだけで、正確に購入できるのか? これは [-1,1] 上のすべての連続函数に対して可能であることを証明している。 構築の背後にあるメカニズムは、リカレントニューラルネットワーク(TMNU)を備えた新しい中間チューリングマシンである。
  論文  参考訳（メタデータ） (2026-06-18T15:03:42Z)
• LongSpike: Fractional Order Spiking State Space Models for Efficient Long Sequence Learning [53.855185131868446]
  スパイキングニューラルネットワーク(SNN)は、シーケンシャルデータを処理する際の生物学的な妥当性とエネルギー効率を十分に考慮している。 本研究では,数次状態空間モデリングを統合した新しいSNNフレームワークであるLongSpikeを提案する。 従来の整数階数 SSM を分数計算系に拡張することにより、LongSpike は長いメモリカーネルとニューロンダイナミクスの階層的な統合を可能にする。
  論文  参考訳（メタデータ） (2026-06-11T04:54:07Z)
• Rethinking Thinking Tokens: LLMs as Improvement Operators [80.12087211785949]
  推論トレーニングは、LLMに長い思考の連鎖(長いCoT)を生み出す動機を与え、自己チェックによるソリューション戦略を探索することを可能にする。 これにより、精度が高くなりますが、コンテキストの長さ、トークン/計算コスト、応答レイテンシが膨らみます。 現在のモデルはメタ認知を活用して、このParetoフロンティアで他の組み合わせを提供できるのでしょうか? i) 多様なドラフトを並列に生成し、(ii) それらを有界なテキストワークスペースに蒸留し、(iii) このワークスペース上に条件付き精製する。
  論文  参考訳（メタデータ） (2025-10-01T17:08:59Z)
• Position as Probability: Self-Supervised Transformers that Think Past Their Training for Length Extrapolation [0.0]
  PRISMは、トランスフォーマーがトレーニング長の10倍まで正確に外挿できる新しい位置符号化機構である。 解析により、PRISMの位置エンコーディングは鋭く解釈可能な内部状態を維持しており、信頼性のある長さ一般化の理論的基礎となっていることが示された。
  論文  参考訳（メタデータ） (2025-06-01T09:20:44Z)
• Short-Long Convolutions Help Hardware-Efficient Linear Attention to Focus on Long Sequences [60.489682735061415]
  本稿では,状態空間モデルを短時間の畳み込みに置き換えたCHELAを提案する。 提案手法の有効性を示すために,Long Range Arenaベンチマークと言語モデリングタスクについて実験を行った。
  論文  参考訳（メタデータ） (2024-06-12T12:12:38Z)
• Assessing the Unitary RNN as an End-to-End Compositional Model of Syntax [0.0]
  LSTMとユニタリ進化リカレントニューラルネットワーク(URN)の両方が,2種類の構文パターンの精度を高めることができることを示す。
  論文  参考訳（メタデータ） (2022-08-11T09:30:49Z)

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

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