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

Paper: 2603.20105 Authors: Amartya Roy, Rasul Tutunov, Xiaotong Ji, Matthieu Zimmer, Haitham Bou-Ammar Categories: cs.LG

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 externalizing 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 analyze. This paper introduces λ-RLM, a framework for long-context reasoning that replaces freeform recursive code generation with a typed functional runtime grounded in λ-calculus.

Key Contributions

• Typed functional runtime: Replaces open-ended code generation with pre-verified combinators (SPLIT, MAP, FILTER, REDUCE) grounded in λ-calculus
• Formal guarantees: Provides termination, closed-form cost bounds, controlled accuracy scaling with recursion depth, and optimal partition rules
• Y-combinator for recursion: Uses fixed-point combinators to “tie the knot” of recursion without requiring LLMs to manage function names or global state
• Significant empirical gains: Outperforms standard RLM in 29 of 36 model-task comparisons, with up to +21.9 points accuracy improvement and 4.1× latency reduction

Methodology

λ-RLM separates semantic reasoning from structural control through three key design principles:

Prompt-as-Environment: Like RLM, λ-RLM externalizes the prompt as a variable in a programming environment, allowing the model to interact with it symbolically rather than consuming it directly.

Typed Combinator Library: Instead of generating arbitrary code, λ-RLM executes a compact library of pre-verified functional operators. The base language model is invoked only at the leaves of recursion on sub-prompts guaranteed to fit within its context window K.

Fixed-Point Recursion: Recursion is encoded as a fixed-point over the operator library using the Y-combinator. The planner enforces predictable execution with maximum depth d = ⌈log_k*(n/τ*)⌉, a pre-computed number of model calls, and deterministic composition at every level.

The framework provides formal operational semantics with β-reduction rules, proving termination under standard size-decreasing decomposition assumptions. This eliminates the runaway-execution failures common in open-ended REPL loops.

Results

Evaluated across four long-context reasoning tasks and nine base models with context lengths up to 128K:

Accuracy Improvements: λ-RLM wins in 81% of comparisons (29/36), with average accuracy gains of +21.9 points on weak models (8B/7B), +18.6 points on medium models (32B+), and +8.8 points on strong models (235B+).

Latency Reductions: Consistent speedups of 3.3× to 4.1× across model tiers, with the most structurally demanding benchmark (OOL-Pairs) achieving +28.6 points accuracy and 6.2× speedup.

Reliability: By constraining control flow to typed combinators, λ-RLM eliminates parsing errors, runtime crashes, and non-termination issues that plague open-ended recursive code generation.

Takeaways

1. Typed symbolic control provides a more reliable and efficient foundation for long-context reasoning than open-ended recursive code generation
2. The Y-combinator enables recursion without requiring LLMs to manage state, eliminating a major source of errors in agentic systems
3. Separating semantic reasoning (what to understand) from structural control (how to decompose) improves both predictability and performance
4. Formal guarantees on termination and cost bounds make λ-RLM suitable for production systems where reliability is critical
5. The framework is model-agnostic and shows consistent improvements across weak, medium, and strong base models