Neural Paging: Learning Context Management Policies for Turing-Complete Agents

The proof that Large Language Models (LLMs) augmented with external read-write memory constitute a computationally universal system has established the theoretical foundation for general-purpose agents. However, existing implementations face a critical bottleneck: the finite and costly Context Window, which functions not as infinite memory but as a scarce semantic cache. In this work, we introduce $\mathit{\text{Neural}}\mathit{\text{Paging}}$, a hierarchical architecture that decouples symbolic reasoning from information resource management. We formulate the $\mathit{\text{Context}}\mathit{\text{Paging}}\mathit{\text{Problem}}\mathit{\text{(CPP)}}$ and propose a lightweight, differentiable $\mathit{\text{Page}}\mathit{\text{Controller}}$ designed to approximate ``Semantic Belady’s Optimality’’ – retaining tokens with high future utility under explicit assumptions on access patterns. We provide theoretical analysis showing that, under bounded context window size~$K$, Neural Paging reduces the asymptotic complexity of long-horizon reasoning from quadratic $O(N^2)$ to $O(N\cdot K^2)$, and we derive a robustness bound (Theorem~4) that quantifies competitive-ratio degradation under policy-dependent access with bounded sensitivity. We validate these bounds on synthetic paging traces, confirming that the theoretical guarantees hold and identifying significant slack that motivates learned policies.