[2603.21272] The Library Theorem: How External Organization Governs Agentic Reasoning Capacity

Computer Science > Artificial Intelligence arXiv:2603.21272 (cs) [Submitted on 22 Mar 2026] Title:The Library Theorem: How External Organization Governs Agentic Reasoning Capacity Authors:Zachary F. Mainen View a PDF of the paper titled The Library Theorem: How External Organization Governs Agentic Reasoning Capacity, by Zachary F. Mainen View PDF HTML (experimental) 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 $\Omega(N)$ page reads per query, and $O(T \log_b T)$ versus $\Theta(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 strong...