$\lambda$-RLM: Statically Restricted Control for Recursive Long-Context Reasoning

Long context is not synonymous with reliable reasoning: relevant evidence is easily lost, while standard Recursive Language Models (RLMs) address the problem by asking the model to generate and execute its own control code. This open-ended strategy extends effective context, but introduces malformed programs, unpredictable cost, and uncontrolled recursion. We introduce $\lambda$-RLM, a structured alternative that expresses recursive reasoning as a closed $\lambda$-calculus program over a compact library of compositional operators. The language model is invoked only on bounded leaf subproblems; decomposition, filtering, traversal, and aggregation follow a fixed plan that can be inspected before execution. This separation guarantees termination, bounds the number of model calls (leaves, plus one per internal node under neural composition) and hence their cost, and supports task-appropriate accuracy analyses for both conjunctive and retrieval settings. Across five long-context benchmarks and nine open-weight models, five-seed comparisons, $\lambda$-RLM improves accuracy most strongly for weak and medium models while reducing latency by $4.0\times$ on average and up to $6.5\times$. These results show that explicit functional control can make recursive long-context reasoning faster, more reliable, and easier to analyze without increasing model scale.