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

Liang Chen, Qi Liu · 2026

Read Neural Paging: Learning Context Management Policies for Turing-Complete Agents by Liang Chen, Qi Liu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-02228.txt.

Introduction

Liang Chen and Qi Liu study memory limits for language model agents in this 2026 paper. A model's context window is small and costly, more like a cache than a full memory. Agents with outside read-write memory can in theory compute anything. In practice, what stays in the window decides what the agent can use.

Their design, Neural Paging, splits thinking from memory management. A small learned controller picks which tokens to keep for future use. The goal echoes a classic ideal: keep what will be needed soonest. Math shows the design cuts long-task cost from quadratic growth to a milder form. Tests on fake paging traces confirm the bounds hold, with room left for learned policies to do better.

Catalog record

CREATORLiang Chen, Qi Liu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49073
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.02228

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Neural Paging: Learning Context Management Policies for Turing-Complete Agents Liang Chen, Qi Liu Abstract 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 Neural Paging , a hierarchical architecture that decouples symbolic reasoning from information resource management. We formulate the Context Paging Problem (CPP) and propose a lightweight, differentiable Page 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 K , Neural Paging reduces the asymptotic complexity of long-horizon reasoning from quadratic O ⁡ ( N 2 ) O(N^{2}) to O ⁡ ( N ⋅ K 2 ) 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. Keywords: Hierarchical Neural Turing Machine, Context Paging Problem, Semantic Cache, Competitive Analysis, Reinforcement Learning. 1 Introduction Large Language Models (LLMs) have evolved from static statistical predictors to the central cognitive kernels of autonomous Agents. As these agents are deployed in complex, open-ended environments—ranging from software engineering to scientific discovery—they are required to maintain coherent reasoning over increasingly long horizons. This shift represents a fundamental transition from “Stateless Function Approximation” to “Stateful Turing Computation.” However, this transition is hindered by a critical physical constraint: the Context Window . Despite recent advances in extending context lengths (e.g., to 1M+ tokens), the “Lost in the Middle” phenomenon [ 17 ] persists, where effective reasoning capabilities degrade as salient information is buried in noise. Furthermore, the quadratic computational cost of the Transformer’s self-attention mechanism makes processing massive contexts prohibitively expensive and slow for real-time applications. Current approaches to managing this bottleneck are insufficient. Retrieval-Augmented Generation (RAG) functions as a naive, passive fetching mechanism with coarse granularity, often leading to context fragmentation. Direct Long Context extension hits memory walls and suffers from “distraction” issues. MemGPT [ 22 ] introduces a tiered memory system but relies on the LLM itself to manage system calls (“Kernel-in-User-Space”). This design is inefficient, forcing the high-level reasoning engine to perform low-level resource management, consuming valuable tokens and attention heads for housekeeping tasks rather than problem-solving. We propose Neural Paging , a framework inspired by the evolution of Operating Systems. Just as modern OS kernels separate user processes from the Memory Management Unit (MMU), we argue for a strict architectural decoupling in AI agents. We introduce the Hierarchical Neural Turing Machine (H-NTM) , where the LLM is dedicated solely to reasoning, while a secondary, learned Page Controller manages the context window. This controller acts as a neural MMU, aiming to predict future data requirements and evict low-utility tokens to approximate Belady-style decisions under explicit modeling assumptions. Our contributions are as follows: 1. Theoretical framing. We formalize the Context Paging Problem (CPP) and define a semantic access model for LLM agents, including a bounded-sensitivity notion (Definition 3a) that quantifies policy-dependent access and enables robustness analysis beyond the classical exogenous model. 2. Architectural design. We design the H-NTM with a decoupled Page Controller that uses lightweight policy networks to manage memory operations (KEEP, EVICT, PREFETCH) without interrupting the main reasoning loop. 3. Analytical results. We derive complexity bounds (Theorem 2), adapt classical paging lower bounds under explicit assumptions (Theorem 3), and prove a new robustness bound (Theorem 4) showing that competitive guarantees degrade gracefully under bounded policy sensitivity. 4. Synthetic validation. We validate the theoretical bounds on synthetic paging traces with controlled parameters, confirming that (i) the bounds are satisfied, (ii) the cascade effect from access perturbation is empirically mild, and (iii) structured access patterns offer significant room for learned policies to outperform worst-case guarantees. Scope and originality. The universality simulation (Theorem 1) and competitive-ratio lower bound (Theorem 3) are classical results carried over to make their conditions explicit in the LLM agent setting. The core new content is the bounded-sensitivity model (Definition 3a), the robustness bound (Theorem 4), and the synthetic validation. We emphasize that end-to-end evaluation on real LLM agents is a natural next step but is outside the scope of this paper. 2 Related Work 2.1 Memory-Augmented Language Models The concept of augmenting neural networks with external memory dates back to the Neural Turing Machine (NTM) [ 11 ] and Differentiable Neural Computers (DNC) [ 12 ] . These early works focused on learning algorithmic manipulation of small, addressable memory matrices. Memory Networks [ 28 ] introduced key-value memory structures for QA tasks. More recent works like Transformer-XL [ 7 ] and Compressive Transformers [ 23 ] introduced segment-level recurrence and compressed memory for longer sequences. Our work scales these concepts to modern LLMs, treating the entire context window as a dynamic “cache” for a much larger external store. 2.2 Context Extension Techniques Efforts to extend the native context window include Position Interpolation [ 5 ] . Architectural innovations like Longformer [ 3 ] and BigBird [ 31 ] utilize sparse attention to reduce costs. More recently, Ring Attention [ 16 ] and FlashAttention [ 8 ] have optimized hardware utilization. Infini-attention [ 21 ] introduces a compressive memory to enable long-context processing with bounded memory. However, these methods address capacity (how much can fit) rather than utility (what should fit). Neural Paging is orthogonal to these techniques, optimizing the content within whatever capacity is available. 2.3 Retrieval-Augmented Generation (RAG) RAG [ 15 ] and RETRO [ 4 ] decouple knowledge from parameters. Self-RAG [ 1 ] adds a critique step to assess retrieval quality. While effective for QA, standard RAG lacks a global view of the “Working Set” and cannot proactively manage context for multi-step reasoning, often leading to thrashing when the agent repeatedly retrieves and discards the same information. 2.4 LLM Agents and Operating System Analogies The agentic paradigm, exemplified by ReAct [ 30 ] and Toolformer [ 24 ] , emphasizes active environment interaction. MemGPT [ 22 ] explicitly draws parallel to Operating Systems, managing a “main context” and “external context.” AIOS [ 20 ] and OS-Copilot [ 29 ] further explore this analogy. Neural Paging advances this line of inquiry by replacing heuristic or LLM-driven memory management with a dedicated, learned policy network, optimizing the “OS kernel” operations. 2.5 Learnable Cache Management Cache replacement has a long history in systems. ARC [ 19 ] adaptively balances recency and frequency without manual tuning. 14 demonstrate that learned models can replace classical index components. Recent KV cache management systems, such as adaptive compression [ 10 ] and KV cache streaming [ 18 ] , optimize inference memory and latency at the KV cache level. Our work is complementary, focusing on semantic content selection rather than low-level KV reuse. 2.6 Paging Theory and Competitive Analysis The theoretical foundations of paging are well-established. Belady’s algorithm [ 2 ] provides the optimal offline policy. Competitive analysis of online paging was initiated by 27

Read the complete text