論文の概要: The Library Theorem: How External Organization Governs Agentic Reasoning Capacity

• arxiv url: http://arxiv.org/abs/2603.21272v1
• Date: Sun, 22 Mar 2026 15:02:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-24 19:11:39.32055
• Title: The Library Theorem: How External Organization Governs Agentic Reasoning Capacity
• Title（参考訳）: 図書館理論:外部機関がエージェント推論能力をどのように獲得するか
• Authors: Zachary F. Mainen,
• Abstract要約: I/O ページとして変換器のコンテキストウィンドウを形式化する。 インデックス付き外部メモリを持つツール拡張エージェントは、シーケンシャルスキャンに制限されたエージェントよりも指数関数的に検索コストが低いことを証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Externalized reasoning is already exploited by transformer-based agents through chain-of-thought, but structured retrieval -- indexing over one's own reasoning state -- remains underexplored. We formalize the transformer context window as an I/O page and prove that tool-augmented agents with indexed external memory achieve exponentially lower retrieval cost than agents restricted to sequential scanning: $O(\log_b N)$ versus $Ω(N)$ page reads per query, and $O(T \log_b T)$ versus $Θ(T^2)$ cumulative cost over $T$ reasoning steps -- a gap that widens as deliberation deepens. We test these predictions on a controlled lookup benchmark across three content types -- random hashes, ordered integers, and encyclopedia entries -- varying store size from 50 to 5,000 items, and replicate key conditions across two model generations (GPT-4o-mini and GPT-5.4). On abstract content, the indexed agent achieves median 1 page read regardless of store size, confirming the $O(1)$ prediction. Sorted pages without an index fail to close the gap: the weaker model cannot sustain binary search at scale, and the stronger model achieves near-optimal $\log_2 N$ search but still loses to the index by $5\times$. On familiar content (encyclopedia entries), a competing failure mode emerges: the model recognizes the domain, bypasses the retrieval protocol, and generates answers from parametric memory, producing catastrophic token expenditure even when the index is sound. This parametric memory competition dissociates the two cognitive operations that indexing combines: understanding content (where language models excel) and following navigational protocols (where they fail when understanding tempts them to shortcut). The result argues for a separation of concerns: use language models for index construction, where semantic understanding helps, and deterministic algorithms for index traversal, where it hurts.
• Abstract（参考訳）: 外部推論は、既にトランスフォーマーベースのエージェントによって、チェーン・オブ・シントを通じて活用されているが、構造化された検索 -- 自分自身の推論状態のインデックス化 -- は、未調査のままである。 我々は、TransformerコンテキストウィンドウをI/Oページとして形式化し、インデックス付き外部メモリを持つツール拡張エージェントが、シーケンシャルスキャンに制限されたエージェントよりも指数関数的に低い検索コストを達成することを証明した。 $O(\log_b N)$ vs $Ω(N)$ page read per query, and $O(T \log_b T)$ versus $O(T^2)$ cumulative cost over $T$ reasoning steps -- a gap that widens as deliberation deepening -- これらの予測は、3つのコンテンツタイプ – ランダムハッシュ、順序付き整数、百科事典エントリ -- の制御されたルックアップベンチマークで検証する。 抽象コンテンツについて、インデックスされたエージェントは、ストアサイズに関係なく中央値の1ページの読み込みを達成し、$O(1)$予測を確認する。 インデックスのないソートされたページはギャップを埋めることができない: より弱いモデルは、スケールでバイナリ検索を維持することができず、強いモデルは、ほぼ最適の$\log_2 N$検索を達成するが、それでも5\times$でインデックスに負ける。 モデルはドメインを認識し、検索プロトコルをバイパスし、パラメトリックメモリから回答を生成し、インデックスがサウンドであっても破滅的なトークンの支出を生成する。 このパラメトリックメモリコンペティションは、インデクシングがコンテント(言語モデルが優れている)を理解することと、ナビゲーションプロトコル(理解すればショートカットする誘惑に失敗する)という2つの認知操作を解き放つ。 セマンティック理解が役立つインデックス構築に言語モデルを使用し、インデックストラバーサルに決定論的アルゴリズムを適用すれば、それが傷つく。

関連論文リスト

• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。 各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
  論文  参考訳（メタデータ） (2025-02-16T16:12:01Z)
• FLARE: Faithful Logic-Aided Reasoning and Exploration [47.46564769245296]
  タスク分解を用いて問題空間をトラバースする新しい手法を提案する。 我々はLarge Language Modelsを使ってソリューションを計画し、クエリを事実に軟式化し、論理プログラミングコードを使って述語する。 提案手法は,生成したコードに対する推論プロセスの忠実度を計算し,外部の解法に頼らずにマルチホップ探索のステップを解析する。
  論文  参考訳（メタデータ） (2024-10-14T19:39:11Z)
• DSI++: Updating Transformer Memory with New Documents [95.70264288158766]
  DSI++は、DSIが新たなドキュメントをインクリメンタルにインデクシングするための継続的な学習課題である。 新たな文書の連続的な索引付けは,それまでの索引付け文書をかなり忘れてしまうことを示す。 文書の擬似クエリをサンプルとして生成メモリを導入し、連続的なインデックス付け中に補足することで、検索タスクの忘れを防止する。
  論文  参考訳（メタデータ） (2022-12-19T18:59:34Z)

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

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