The Library Theorem: How External Organization Governs Agentic Reasoning Capacity

1. Problem Statement

The paper addresses a fundamental gap in the theoretical understanding of Transformer-based agentic reasoning. While it is well-established that externalizing thought processes (e.g., Chain-of-Thought) improves reasoning, the organizational structure of the external memory used by these agents remains underexplored.

Current agents typically maintain a flat, sequential conversation history. Retrieving specific information from this history requires scanning the text linearly. The author posits that this sequential organization imposes a severe computational bottleneck, preventing agents from scaling efficiently as the volume of accumulated reasoning state ($N$) and the depth of reasoning steps ($T$) increase. The core question is: How does the organization of external state (sequential vs. indexed) affect the computational cost of retrieval and reasoning?

2. Methodology

Theoretical Framework

The author formalizes the interaction between a Transformer model and its external memory using an I/O complexity model:

• The Context Window as an I/O Page: The model's context window ($C$ tokens) is treated as a single "page" in an external storage system. Each inference step is an I/O operation where the model reads one page and writes one page.
• Access Models:
  • Sequential Access: The store is a flat list. Finding an item requires scanning, costing $\Omega(N)$ page reads.
  • Indexed Access: The store is organized as a B-tree (or file system) with a branching factor $b$. Finding an item requires $\lceil \log_b N \rceil$ index reads plus one data read.
• The Library Theorem: The paper proves that indexed retrieval offers an exponential separation in cost compared to sequential retrieval.
  • Static Cost: $O(\log_b N)$ vs. $\Omega(N)$.
  • Dynamic Cost (Accumulation): Over $T$ reasoning steps where the store grows, the cumulative cost is $O(T \log_b T)$ for indexed access versus $\Theta(T^2)$ for sequential access.

Experimental Design

To validate these theoretical predictions, the author conducted controlled benchmarks using GPT-4o-mini and GPT-5.4.

• Task: A key-value lookup task where an agent must find a value associated with a specific key in a paginated store.
• Conditions:
  1. FLAT: Randomly ordered pages; no structural info.
  2. INDEXED: Pages sorted with a Table of Contents (TOC) index.
  3. FLAT-SORTED: Pages sorted but no explicit index (tests if the model can perform binary search internally).
  4. INDEXED-CORRUPTED: Index points to wrong pages (causal control).
  5. DEEP-INDEXED: Two-level hierarchy (Master TOC $\to$ Section TOC $\to$ Page) to test recursive indexing.
• Content Types: To isolate the effect of content familiarity, three datasets were used:
  1. Hashes: Random strings (zero prior knowledge).
  2. Numeric: Ordered integers (predictable but abstract).
  3. Encyclopedia: Real-world facts (high prior knowledge/parametric memory).

3. Key Contributions

1. Formal Model of Context as I/O: The paper establishes a formal equivalence between the Transformer context window and an I/O page, allowing the application of classical I/O complexity theory (B-trees) to LLM reasoning.
2. The Library Theorem: Proves that structured memory organization yields an exponential reduction in retrieval costs ($O(\log N)$ vs. $\Omega(N)$) and prevents the quadratic explosion of token costs ($\Theta(T^2)$) during long-horizon reasoning.
3. Empirical Validation of Retrieval Separation: Demonstrates that indexed agents achieve constant ($O(1)$) page reads regardless of store size, while sequential agents scale linearly.
4. Discovery of "Parametric Memory Competition": Identifies a critical failure mode where, on familiar content, the model bypasses the retrieval protocol entirely, generating answers from its internal training data (parametric memory) rather than reading the external index. This leads to token budget exhaustion and hallucination loops.
5. Architectural Design Principle: Proposes a separation of concerns:
   • Index Construction: Use LLMs (semantic understanding helps decide what to index and how to name).
   • Index Traversal: Use deterministic algorithms (semantic understanding hurts here by tempting the model to shortcut the protocol).

4. Key Results

• Sequential vs. Indexed Efficiency:
  • On Hash and Numeric content, the INDEXED agent maintained a median of 1 page read regardless of store size (up to 5,000 items).
  • The FLAT agent's page reads scaled linearly with store size (e.g., ~21 reads for 500 items), matching the $\Omega(N)$ prediction.
  • Token Cost: At $N=2,000$, the FLAT agent consumed ~914k tokens per query, while the INDEXED agent consumed ~6k tokens (a 154x difference).
• The Limits of Internal Sorting:
  • The FLAT-SORTED condition (sorted pages without an index) failed to sustain binary search at scale. The weaker model (GPT-4o-mini) reverted to linear scanning. The stronger model (GPT-5.4) achieved near-optimal binary search ($\approx 5$ reads) but still lost to the explicit index (1 read) by a factor of 5x.
• Parametric Memory Competition (The Failure Mode):
  • On Encyclopedia content, the DEEP-INDEXED architecture collapsed. Despite the index being correct, the model recognized the domain, ignored the tool calls, and generated answers from its internal weights.
  • This resulted in 0 page reads (the model never looked at the data) and token budget exhaustion (hallucination loops), causing accuracy to drop to 27% at $M=200$.
  • This confirms that semantic familiarity can be detrimental to agentic protocols if the model is not forced to defer to external memory.

5. Significance and Implications

• Computational Necessity of Structure: The paper argues that structured memory (file systems, databases) is not merely a convenience for agents but a computational necessity to escape the quadratic scaling of reasoning costs.
• Beyond RAG: While Retrieval-Augmented Generation (RAG) uses indexing for external knowledge, this work highlights the need to index self-generated reasoning states (intermediate thoughts, code snippets, logs) to enable deep, long-horizon planning.
• Hybrid Agent Architectures: The findings strongly support the LLM-Modulo paradigm. Agents should not rely solely on the LLM for all operations. Instead:
  • LLMs should act as semantic processors for organizing and building the index.
  • Deterministic, non-generative code should handle index traversal to prevent the model from "cheating" via parametric memory.
• Extended Cognition: The paper frames the indexed agent as a distinct cognitive system where the external memory structure is constitutive of the reasoning capacity, offering an exponential advantage over the raw model alone.

In conclusion, The Library Theorem provides the first formal proof that the organization of external memory dictates the scalability of agentic reasoning. It demonstrates that without explicit indexing, agents are bound by linear search costs that quickly become prohibitive, and it warns that semantic understanding must be carefully gated during retrieval to prevent the model from bypassing the very mechanisms designed to extend its capabilities.