Proves that structured retrieval is exponentially more efficient than sequential context scanning for agentic reasoning.
March 24, 2026
Original Paper
The Library Theorem: How External Organization Governs Agentic Reasoning Capacity
arXiv · 2603.21272
The Takeaway
The paper formalizes 'The Library Theorem,' providing a theoretical foundation for why agentic memory must be indexed rather than just concatenated. It demonstrates that while strong models can attempt binary search in context, a dedicated index reduces retrieval cost from linear to logarithmic, essential for long-horizon deliberation.
From the 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