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 textitNeural Paging, a hierarchical architecture that decouples symbolic reasoning from information resource management. We formulate the textitContext Paging Problem (CPP) and propose a lightweight, differentiable textitPage 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(N2) to O(N · K2), 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.