論文の概要: When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?
- arxiv url: http://arxiv.org/abs/2607.06155v1
- Date: Tue, 07 Jul 2026 11:32:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-08 21:24:51.502191
- Title: When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?
- Title（参考訳）: 有限精度リカレントモデルの表現力はいつ向上するか?
- Abstract要約: 有限命令/観測インタフェースを介してオラクルと相互作用する決定論的有限状態制御系として、有限精度状態空間モデル(SSM)を内部状態の$B$ビットでモデル化する。
つまり、ローカル$mathttread$、$mathttwrite$、$mathttmove$コマンドのみをサポートするテープは、システムを完全なものにしている。
- 参考スコア（独自算出の注目度）: 22.276732262979678
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools. We give an exact, architecture-level account of when such tool access increases computational expressivity. We model any fixed finite-precision recurrent sequence model, including finite-precision state-space models (SSMs) with $B$ bits of internal state, as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface. Our results form a sharp dichotomy. First, tools that are themselves finite-state add essentially nothing: a product-state simulation internalizes any finite-state bounded-interface oracle with finite memory set $M$ at a cost of only $\log_2 |M| + O(1)$ additional bits, so the augmented system remains finite-state. Second, a single minimal infinite-state tool, namely a tape supporting only local $\mathtt{read}$, $\mathtt{write}$, and $\mathtt{move}$ commands, makes the system Turing complete: for every single-tape Turing machine with state set $Q$ and tape alphabet $Γ$, a controller with $O(\log |Q| + \log |Γ|)$ bits of internal memory simulates it, and we exhibit a concrete exponential separation: $\mathrm{EQ}_n$ requires $2^n$ states without tools but a single constant-size controller with the tape tool. Third, we show that this construction is realized exactly by a natural one-layer finite-precision selective affine SSM controller with binary one-hot hidden states, $\{0,1\}$ transition matrices, and zero biases. Selectivity is essential to the construction. In the supplementary material, we make all constants explicit, prove a logarithmic oracle-assisted universal simulation, where $O(\log B)$ recurrent bits suffice to simulate any $B$-state Turing machine, and prove a matching impossibility result.
- Abstract（参考訳）: 現代的なシーケンスモデルは、外部ツールへの呼び出しでトークン生成をインターリーブするエージェントとして、ますます多くデプロイされている。
我々は、そのようなツールアクセスが計算表現性を高める時期を正確にアーキテクチャレベルに記述する。
有限命令/観測インタフェースを介してオラクルと相互作用する決定論的有限状態制御系として、有限精度状態空間モデル(SSM)を内部状態の$B$ビットでモデル化する。
私たちの結果は鋭い二分法を形成します。
積状態シミュレーションは有限メモリセット$M$を$\log_2 |M| + O(1)$追加ビットのみのコストで内部化するので、拡張系は有限状態のままである。
次に、単一の最小限の無限状態ツール、すなわちローカル$\matht{read}$, $\mathtt{write}$, $\mathtt{move}$コマンドのみをサポートするテープは、システムをチューリングする: ステートセットが$Q$とテープアルファベットのすべてのシングルテープチューリングマシンに対して、$O(\log |Q| + \log |\|)$内部メモリのビットがそれをシミュレートし、具体的な指数分離を示す: $\mathrm{EQ}_n$は、ツールなしで2^n$のステートを必要とする。
第三に、この構成は自然の一層有限精度選択型アフィンSSMコントローラによって正確に実現され、二項一点隠れ状態、${0,1\}$遷移行列、およびゼロバイアスを持つことを示す。
選択性は建設に不可欠である。
補足材料では、全ての定数を明確にし、対数的オラクル支援の普遍シミュレーションを証明し、$O(\log B)$再帰ビットは任意の$B$状態チューリングマシンをシミュレートするのに十分である。
関連論文リスト
- Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。
すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。
指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文 参考訳（メタデータ） (2026-08-27T01:31:46Z) - Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory [5.649244092106778]
我々は、特定のAI状態追跡タスクに対して、推論時量子コーディネーションの利点を証明した。
イベントの順序と過去の入力へのアクセスを保ちながら、有限片方向、ストリーミング、あるいは適応因果タスクをセマンティックAIインターフェースにマッピングする。
論文 参考訳（メタデータ） (2026-08-11T15:32:15Z) - Sparse Quantum State Preparation with Sublinear T-Count [5.929956715430168]
$$n$-qubit $s$-sparse状態は、$widetildeO(mins, n3/4sqrts+sqrtslog (1/)+log (1/)$ $T$ gatesを使ってエラーを発生させることができる。
0le$と2le sle 2n/2$に対して、スパース状態の準備には$(mins,sqrtns)$$Tが必要である。
論文 参考訳（メタデータ） (2026-08-01T03:33:19Z) - Efficiently Representing Algorithms With Chain-of-Thought Transformers [45.60818649759173]
思考の連鎖変換器はチューリングマシンをシミュレートし、任意の計算を行う。
我々は,CoTエンファンカンが多対数オーバーヘッドのみのWord RAMアルゴリズムを$n$で効率的にシミュレートできることを示す。
論文 参考訳（メタデータ） (2026-06-18T01:49:29Z) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳（メタデータ） (2023-06-02T17:49:35Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - Simplifying and Understanding State Space Models with Diagonal Linear
RNNs [56.33053691749856]
本研究は、離散化ステップを解消し、バニラ対角線形RNNに基づくモデルを提案する。
概念的にはるかに単純であるにもかかわらず、$mathrmDLR$は以前提案したSSMと同じくらいのパフォーマンスを示す。
また、合成シーケンス・ツー・シーケンス・タスクのスイートによって、SSMとアテンションベースモデルの表現性も特徴付ける。
論文 参考訳（メタデータ） (2022-12-01T18:53:06Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。