The agent loop has a memoization problem. Nobody…

Let me build it.

I've been thinking about this since a conversation I had with a friend who kept insisting that the right mental model for an agent loop is a state machine. He's not wrong. But state machines don't capture the thing that's most interesting about multi-step agentic execution: that subproblems recur, and when they recur, every current agent framework recomputes them from scratch.

There's a name for the class of algorithm that has this problem. It's called naive recursion. And the fix has been known since Bellman wrote about it in 1957.

The Y-Combinator for LLMs paper and why it's the right framing.

Roy et al. published "The Y-Combinator for LLMs: Solving Long-Context Rot with λ-Calculus" (arXiv:2603.20105, March 2026). The core argument: context rot -- the degradation of LLM performance as context grows -- is structurally equivalent to the stack overflow problem in uncontrolled recursion. The fix in programming language theory is the Y-combinator. The fix for context rot is the same mathematical structure applied to agent context management.

The Y-combinator is a fixed-point combinator. It allows a function to call itself recursively without being bound to a name. Y(f) = f(Y(f)). If f is a function that takes itself as an argument and uses that to recurse, Y(f) is the recursive function. The Y-combinator is how lambda calculus -- a language with no recursion primitive -- implements recursion.

Applied to agents: an agent that invokes a sub-agent with a modified context, where the sub-agent can in turn invoke sub-agents, is implementing Y-combinator-style recursion. The agent doesn't need to know its own name. It receives itself as a capability and calls it on a reduced subproblem. The recursion terminates when the subproblem is small enough to solve directly or when a base case is reached.

This is the right framing. Let me show you the problem it exposes.

The memoization problem in agent recursion.

In classic DP, the Fibonacci sequence computed naively:

fib(n) = fib(n-1) + fib(n-2)

Computed naively, fib(50) makes over a trillion function calls. With memoization:

cache = {}
def fib(n):
    if n in cache: return cache[n]
    result = fib(n-1) + fib(n-2)
    cache[n] = result
    return result

fib(50) makes exactly 99 calls. Same result. 10^10 times fewer operations. The memoization table is the data structure that transforms an exponential algorithm into a linear one by recognizing that the same subproblem appears in multiple branches of the recursion tree and caching the result the first time.

Agent loops have overlapping subproblems. Here is a specific example.

A research agent is asked to write a report on climate policy. It spawns sub-agents: one to research economic impacts, one to research environmental outcomes, one to research political feasibility. Each sub-agent independently searches for papers by the same authors, retrieves the same IPCC reports, calls the same web search tool with semantically equivalent queries. The three sub-agents independently compute the same subproblems -- "retrieve information about carbon pricing" -- and return similar results.

No current agent framework detects that these are the same subproblem. Each sub-agent executes the tool calls independently, paying full inference and API cost three times. The memoization table is empty because nobody built it.

What the memoization table for agents looks like.

In DP, the table is keyed by the exact input to the function. For agents, exact input matching is the wrong key because two tool calls with semantically equivalent arguments are the same subproblem even if the arguments aren't textually identical. "papers about carbon taxation" and "research on carbon tax policy" are the same subproblem.

The memoization key is a semantic fingerprint: an embedding of the tool name, the semantic intent of the arguments, and the relevant context that the call depends on. Two calls with embeddings within cosine distance δ are the same subproblem and should return the cached result.

The cache entry is: the result of the tool call, and the KV cache states for the processing of that result. When a cache hit is found for a sub-agent invocation, you don't just return the text result -- you return the KV states that encode the processing of that result. The downstream agent doesn't need to re-prefill over the tool result because the KV states are already cached.

This is cross-branch KV sharing. Two agent branches that encounter the same subproblem share KV states, not just results. The second branch pays no inference cost at all for the subproblem -- it gets the KV states for free.

The eviction policy is DP-guided: KV states for subproblems that are on the critical path (subproblems that must be computed before the final answer can be produced) stay hot. KV states for subproblems that are in completed branches or that are leaves of the recursion tree can be tiered down. This is exactly the graph-aware KV eviction I wrote about earlier, now derived from DP first principles rather than intuition about workflow graphs.

Recursion detection and the base case.

Naive Y-combinator recursion without a base case diverges. An agent that spawns a sub-agent with the same task will spawn another sub-agent with the same task indefinitely. This is the "retry loop" failure mode I described at the start of the competitive programming post -- the agent in a cycle it can't escape.

DP handles this by detecting cycles in the dependency graph. If subproblem A depends on subproblem B which depends on subproblem A, you have a cycle. The standard DP treatment: cycles indicate that the subproblem is ill-defined (true recursion without termination) or can be resolved by a fixed-point iteration.

For agents, cycle detection in the subproblem graph is the structural analog of loop detection. The memoization table tracks which subproblems are "in progress" (currently being computed by some branch) in addition to which are complete. When a new sub-agent invocation's fingerprint matches an "in progress" entry, you've detected a cycle. Options:

Fail fast: terminate the new invocation with a sentinel value indicating a cycle was detected. Force the parent to handle the cycle explicitly.

Fixed-point iteration: allow the cycle to execute once more, using the current partial result as the approximation. If the new result matches the previous result within tolerance, you've reached a fixed point. If not, update the cache and iterate. This is the DP solution to cyclic dependencies in constraint satisfaction -- iterate until convergence.

The Y-combinator insight applies directly here: in lambda calculus, the Y-combinator handles the termination problem by ensuring that each recursive call operates on a strictly smaller input (well-founded recursion). For agents, the analogous requirement is that each recursive sub-agent invocation operates on a strictly simpler or smaller subproblem. The memoization layer enforces this: if the fingerprint matches a completed entry, return cached. If it matches an in-progress entry, cycle detected, handle accordingly.

Recursive Agent Optimization (RAO) and the training signal.

Recursive Agent Optimization (arXiv:2605.06639, May 2026) trains an orchestrator with reinforcement learning where the policy is defined over rollout trees -- trees of sub-agent invocations rather than flat token sequences. The gradient attributes reward to the orchestration decisions (which sub-agents to spawn, what tasks to assign them) rather than to the low-level token generation.

The DP connection to RAO: the rollout tree IS the DP recursion tree. Each node is a subproblem. Each edge is a recursive call. The value function being optimized is the expected reward of the full rollout tree, which decomposes recursively over the tree structure. RAO is solving the same optimization problem that DP solves -- find the policy that maximizes expected value by decomposing the problem into subproblems and optimizing each subproblem's contribution -- but using RL rather than exact dynamic programming because the state space is too large for exact DP.

The credit-assignment principle is the same one DP uses: in DP, the value of a subproblem is computed relative to the values of its children; in RAO, the gradient of an orchestration decision is computed relative to the counterfactual rollout tree without that decision. Same credit assignment principle, different algorithm class.

What RAO doesn't have yet: the memoization layer. Two branches of the rollout tree that encounter the same subproblem are still computed independently. Adding the memoization table I described would reduce the number of distinct subproblem evaluations needed during training, which reduces the gradient variance (you have more independent samples of each subproblem's value) and reduces the training cost (fewer total sub-agent invocations for the same number of training examples).

The Recursive Language Model (RLM) as the substrate.

The RLM (arXiv:2512.24601, Zhang, Kraska, Khattab, December 2025) proposes a specific mechanism: instead of summarizing context (which loses information), the model delegates context to sub-LLMs that run as Python coroutines, maintaining their own state. The main LLM calls sub-LLMs as needed, which can call sub-sub-LLMs. The recursion is explicit in the scaffolding, managed via Python's coroutine machinery.

This is the execution engine for the memoization scheme I described. The Python coroutine structure gives you natural checkpoints for the memoization lookup: before calling a sub-LLM coroutine, compute the fingerprint of its task and check the cache. If hit, return the cached result and inject the cached KV states. If miss, run the coroutine and store the result.

The coroutine's state (its local variables, its position in the execution) maps directly to the KV states I described as the cache value. Python coroutines already implement exactly the structure needed: you can suspend a coroutine at any yield point, capture its state, and resume it later. The memoization layer can capture the state of a completed coroutine (its full execution trace and KV states) and replay the final state to a new coroutine that encounters the same subproblem.

The thing this would build, made concrete.

You're running a research agent on a corpus of 10,000 papers. The task: "find all papers that contradict the main claims of this survey." The agent spawns 50 sub-agents to analyze different sections of the corpus. Many of those sub-agents will independently retrieve the same foundation papers, process the same common references, form conclusions about the same baseline claims.

With the memoization table: the first sub-agent to process "paper X contradicts claim Y" stores the result and its KV states. Every subsequent sub-agent that arrives at the same question gets the cached answer and KV states in milliseconds, at zero inference cost. The 50 sub-agents effectively share a pool of solved subproblems. The total work done is proportional to the number of distinct subproblems, not the number of (subproblem, agent) pairs.

Without it: each of the 50 sub-agents independently retrieves and processes paper X. 50 inference calls, 50 sets of KV cache, 50x the cost.

The memoization table is the difference between O(unique subproblems) and O(agents × subproblems) in inference cost for the class of tasks where sub-agents encounter overlapping subproblems. Research, code analysis, competitive intelligence, any task with natural structure that different analysis branches independently need to ground truth against.

the agent loop is naive recursive fibonacci.

the memoization table is the optimization that transforms it.

the y-combinator paper (march 2026) gave us the lambda calculus framing.

the rlm paper (december 2025) gave us the execution substrate.

the rao paper (may 2026) gave us the training objective.

nobody built the cache.

the semantic fingerprinting layer -- what makes "carbon pricing research" and "carbon tax policy papers" the same subproblem -- is the piece that doesn't exist yet. it's the hash function in the DP cache. everything else is standard computer science applied to a new domain. the hash function is the research problem.

P.S. The fixed-point iteration approach to cycles has a beautiful connection to the RL training literature. Value iteration in RL is itself a fixed-point algorithm: iterate the Bellman equation until the value function converges to a fixed point. When a cycle appears in an agent's subproblem graph, resolving it via fixed-point iteration is exactly what RL value iteration does on cyclic MDPs. The agent's cycle is a small MDP with a back-edge, and the fixed-point resolution gives you the correct value for the subproblem that forms the cycle. This is not a coincidence -- it's the same mathematical structure (contraction mappings, fixed-point theorems) appearing at two different levels of the agent stack. The RL training objective and the runtime cycle resolution are solving the same class of problem. That connection is worth a standalone paper.