The $\mathbf{Y}$-Combinator for LLMs: Solving Long-Context Rot with $λ$-Calculus

Authors	Amartya Roy et al.
Year	2026
Field	Machine Learning
arXiv	2603.20105
PDF	Download
Categories	cs.LG, cs.AI

Abstract

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.

---

Engineering Breakdown

Plain English

This paper introduces λ-RLM, a framework that enables large language models to handle longer contexts by breaking problems into recursive subproblems without relying on open-ended code generation. Instead of letting the model write arbitrary Python code (the traditional REPL approach), λ-RLM constrains reasoning to a typed functional runtime based on lambda calculus with pre-verified combinators. The key insight is that by replacing free-form code generation with structured functional programs, the system becomes verifiable, predictable, and more efficient—neural inference only runs on bounded leaf subproblems while control flow is explicit and deterministic.

Core Technical Contribution

The core novelty is replacing the open-ended read-eval-print loop (REPL) used in existing recursive language models with a type-safe functional runtime grounded in lambda calculus. Instead of allowing the model to generate arbitrary control code that must be executed and verified at runtime, λ-RLM provides a curated library of pre-verified combinators that the model selects and composes. This transforms recursive reasoning from an unpredictable code generation problem into a structured program synthesis problem where control flow is explicit, type-checkable, and amenable to formal analysis. The approach dramatically reduces the computational surface area by confining neural inference to bounded leaf subproblems only.

How It Works

The system operates in layers: first, the input context and subproblems are encoded and passed to the neural model, which generates function calls from a pre-defined combinator library rather than free-form code. These combinators are implemented as typed lambda calculus expressions with verified correctness properties. The model selects which combinator to apply, providing arguments when needed—this selection is guided by the type system, preventing invalid compositions. For leaf subproblems that require actual language understanding (reading comprehension, classification, etc.), the system invokes the LLM with bounded context to generate answers. The results are then combined via the functional combinators following the control flow graph that was implicitly defined by the combinator sequence, building up solutions to larger subproblems until the full problem is solved.

Production Impact

In production systems, λ-RLM solves the critical bottleneck of long-context reasoning by making recursive decomposition deterministic and verifiable, which is essential for systems that must be debugged or audited. Rather than dealing with potential hallucinations or unexpected control flow from LLM-generated code, engineers get explicit, traceable execution paths with guaranteed termination and type safety. This enables serving longer problem instances without proportional increases in context window size—a major cost reduction for inference since typical LLM cost scales quadratically with context length. Integration requires upfront effort to design domain-specific combinator libraries and map problems to functional decomposition patterns, but once designed, these become reusable across similar problem classes. The trade-off is less flexibility than open-ended code generation; if a problem requires reasoning patterns outside the combinator library, the system cannot adapt without recompiling the runtime.

Limitations and When Not to Use This

The paper assumes that complex reasoning can be decomposed into recursive subproblems that map cleanly to a lambda calculus-based functional program—this assumption breaks down for problems requiring truly novel control flow or emergent reasoning patterns. The approach requires upfront design of domain-specific combinator libraries, which is labor-intensive and must be done per problem class; this limits applicability to new domains without significant engineering investment. The paper doesn't clearly specify how to handle problems where the optimal decomposition isn't obvious or where the functional structure doesn't align with the natural problem structure. Additionally, there's no analysis of whether the constraint to lambda calculus actually reduces expressiveness in ways that harm solution quality, or how the system gracefully fails when a problem can't be solved with available combinators.

Research Context

This work builds on the emerging area of recursive language models and prompting techniques that break long-horizon reasoning into subproblems (related to chain-of-thought and scratchpad approaches). It directly addresses limitations of prior work like Code as Policies or other code-generating LLM agents, which suffer from unpredictable execution and difficult verification. The paper positions itself as a response to the open-ended REPL bottleneck in existing recursive reasoning systems, introducing formal structure inspired by programming language theory. This opens a research direction at the intersection of formal verification, functional programming, and neural reasoning—future work could explore learning optimal decomposition strategies, automatically synthesizing combinator libraries, or extending the type system to capture richer problem structure.

---

:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::

---

Back to Research Lab → · Subscribe to AI Letters →