# The Y-Combinator for LLMs: Solving Long-Context Rot with λ-Calculus

arXiv: https://arxiv.org/abs/2603.20105 · HTML: https://mlsanity.com/paper/2603.20105/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 43 references that are in the map.
- First posted on arXiv 20 Mar 2026.

## Builds on (most cited first, 30 of 36)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Why Do Multi-Agent LLM Systems Fail?](https://mlsanity.com/paper/2503.13657/) (2025)
- [Which Agent Causes Task Failures and When? On Automated Failure Attribution of LLM Multi-Agent Systems](https://mlsanity.com/paper/2505.00212/) (2025)
- [COLD-Attack: Jailbreaking LLMs with Stealthiness and Controllability](https://mlsanity.com/paper/2402.08679/) (2024)
- [Scaling Long-Horizon LLM Agent via Context-Folding](https://mlsanity.com/paper/2510.11967/) (2025)
- [In-Context Learning with Long-Context Models: An In-Depth Exploration](https://mlsanity.com/paper/2405.00200/) (2024)
- [Long-Context LLMs Meet RAG: Overcoming Challenges for Long Inputs in RAG](https://mlsanity.com/paper/2410.05983/) (2024)
- [Retrieval Augmented Generation or Long-Context LLMs? A Comprehensive Study and Hybrid Approach](https://mlsanity.com/paper/2407.16833/) (2024)
- [System-Level Defense against Indirect Prompt Injection Attacks: An Information Flow Control Perspective](https://mlsanity.com/paper/2409.19091/) (2024)
- [Beyond the Limits: A Survey of Techniques to Extend the Context Length in Large Language Models](https://mlsanity.com/paper/2402.02244/) (2024)
- [Training-Free Long-Context Scaling of Large Language Models](https://mlsanity.com/paper/2402.17463/) (2024)
- [Human-inspired Episodic Memory for Infinite Context LLMs](https://mlsanity.com/paper/2407.09450/) (2024)
- [AgentOps: Enabling Observability of LLM Agents](https://mlsanity.com/paper/2411.05285/) (2024)
- [Scalable Power Sampling: Unlocking Efficient, Training-Free Reasoning for LLMs via Distribution Sharpening](https://mlsanity.com/paper/2601.21590/) (2026)
- [Kolb-Based Experiential Learning for Generalist Agents with Human-Level Kaggle Data Science Performance](https://mlsanity.com/paper/2411.03562/) (2024)
- [Formal Analysis and Supply Chain Security for Agentic AI Skills](https://mlsanity.com/paper/2603.00195/) (2026)
- [Neuro-Symbolic Artificial Intelligence: Towards Improving the Reasoning Abilities of Large Language Models](https://mlsanity.com/paper/2508.13678/) (2025)
- [From Storage to Steering: Memory Control Flow Attacks on LLM Agents](https://mlsanity.com/paper/2603.15125/) (2026)
- [Mixture of Attentions For Speculative Decoding](https://mlsanity.com/paper/2410.03804/) (2024)
- [RAPID: Long-Context Inference with Retrieval-Augmented Speculative Decoding](https://mlsanity.com/paper/2502.20330/) (2025)
- [A Survey on Agent Workflow -- Status and Future](https://mlsanity.com/paper/2508.01186/) (2025)
- [Bourbaki: Self-Generated and Goal-Conditioned MDPs for Theorem Proving](https://mlsanity.com/paper/2507.02726/) (2025)
- [ReAcTree: Hierarchical LLM Agent Trees with Control Flow for Long-Horizon Task Planning](https://mlsanity.com/paper/2511.02424/) (2025)
- [When Does Divide and Conquer Work for Long Context LLM? A Noise Decomposition Framework](https://mlsanity.com/paper/2506.16411/) (2025)
- [SymRAG: Efficient Neuro-Symbolic Retrieval Through Adaptive Query Routing](https://mlsanity.com/paper/2506.12981/) (2025)
- [LycheeDecode: Accelerating Long-Context LLM Inference via Hybrid-Head Sparse Decoding](https://mlsanity.com/paper/2602.04541/) (2026)

## Built on by (most cited first, 3 of 3)

- [Recursive Agent Harnesses](https://mlsanity.com/paper/2606.13643/) (2026)
- [MedRLM: Recursive Multimodal Health Intelligence for Long-Context Clinical Reasoning, Sensor-Guided Screening, Evidence-Grounded Decision Support, and Community-to-Tertiary Referral Optimization](https://mlsanity.com/paper/2606.20164/) (2026)
- [The Model Knows When to Stop: Training-Free Early Stopping for Long-Context Reading](https://mlsanity.com/paper/2609.34590/) (2026)

## Abstract (arXiv)

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.