The Y-Combinator for LLMs: Solving Long-Context Rot with 位-Calculus
Abstract
位-RLM replaces unbounded recursive code generation with typed functional runtime based on 位-calculus, providing formal guarantees and improved efficiency for long-context reasoning tasks.
LLMs are increasingly used as general-purpose reasoners, but long inputs remain bottlenecked by a fixed context window. Recursive Language Models (RLMs) address this by externalising the prompt and recursively solving subproblems. Yet existing RLMs depend on an open-ended read-eval-print loop (REPL) in which the model generates arbitrary control code, making execution difficult to verify, predict, and analyse. We introduce 位-RLM, a framework for long-context reasoning that replaces free-form recursive code generation with a typed functional runtime grounded in 位-calculus. It executes a compact library of pre-verified combinators and uses neural inference only on bounded leaf subproblems, turning recursive reasoning into a structured functional program with explicit control flow. We show that 位-RLM admits formal guarantees absent from standard RLMs, including termination, closed-form cost bounds, controlled accuracy scaling with recursion depth, and an optimal partition rule under a simple cost model. Empirically, across four long-context reasoning tasks and nine base models, 位-RLM outperforms standard RLM in 29 of 36 model-task comparisons, improves average accuracy by up to +21.9 points across model tiers, and reduces latency by up to 4.1x. These results show that typed symbolic control yields a more reliable and efficient foundation for long-context reasoning than open-ended recursive code generation. The complete implementation of 位-RLM, is open-sourced for the community at: https://github.com/lambda-calculus-LLM/lambda-RLM.
Community
馃幇 Why your 405B model is losing to an 8B model (and how 1930s math fixed it).
The AI industry has a "Context Rot" problem. 馃
As prompts get longer, we usually try to fix them with more RAM or massive parameter counts. But "stochastic control", i.e., letting an LLM write its own arbitrary code to manage its memory, is inherently unreliable. It leads to non-termination, malformed outputs, and unpredictable costs.
We need better logic 馃
We introduced $\lambda$-RLM, a framework that replaces messy, open-ended recursive code generation with a typed functional runtime grounded in $\lambda$-Calculus.
The "David vs. Goliath" Results:
The Flex: An 8B model using $\lambda$-RLM actually beats the accuracy of a 405B model on long-context tasks. 馃コ
The Match: Our scaffolded 8B model matches the performance of a 70B model while being 3.1x faster. 馃巺
The Speed: Across the board, we saw latency reductions of up to 4.1x. 馃巰
The Gains: Average accuracy improved by up to +21.9 points on "weak" model tiers.
How it Works (The Math):
1锔忊儯 Instead of a "hallucination-prone" REPL loop, we use a fixed library of pre-verified combinators like SPLIT, MAP, and REDUCE.
2锔忊儯 We used the Y-combinator to "tie the knot" of recursion symbolically. This ensures:
3锔忊儯 Guaranteed Termination: No more infinite loops.
4锔忊儯 Predictable Cost: We proved the optimal partition for AI reasoning is exactly k^*= check the paper 馃槣
The future of reliable AI isn't just "bigger parameters." It鈥檚 providing models with high-integrity, verifiable environments.
Models citing this paper 0
No model linking this paper
Datasets citing this paper 0
No dataset linking this paper
Spaces citing this paper 0
No Space linking this paper
Collections including this paper 0
No Collection including this paper