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 Institutions: IIT Delhi, Huawei Noah’s Ark Lab, UCL Categories: cs.LG

Abstract

LLMs are bottlenecked by fixed context windows when processing long inputs. Recursive Language Models (RLMs) address this by externalizing prompts and recursively solving subproblems, but they rely on open-ended code generation that’s difficult to verify and predict. This paper introduces λ-RLM, a framework that replaces free-form recursive code with a typed functional runtime grounded in λ-calculus, achieving +21.9% accuracy improvement and 4.1× latency reduction with formal guarantees on termination and cost.

The Problem: Long-Context Rot

Context Window Limitations

Transformers have a fundamental bottleneck: fixed-length context windows. When inputs exceed this limit:

• Long documents, codebases, multi-file repositories
• Large evidence collections
• Systematic reasoning requiring global consistency

Naive solutions fail:

• Truncation: Loses critical information
• Sliding windows: Model “forgets” early context
• Breaks global consistency: Can’t maintain coherence across long inputs

Recursive Language Models (RLMs)

RLMs propose treating the prompt as an external environment:

1. Store prompt as a variable in a REPL (Read-Eval-Print Loop)
2. LLM writes code to peek into prompt
3. Decompose into slices
4. Recursively invoke itself on slices
5. Compose results

Key insight: Prompt-as-environment + symbolic recursion enables handling inputs beyond native context length.

RLM’s Critical Flaw

RLMs give LLMs unrestricted freedom to generate arbitrary control code:

Failure modes:

• Code may not parse or crash at runtime
• Recursion may be invoked excessively (non-termination)
• Intermediate outputs may be malformed
• Unpredictable computation due to model’s control-flow decisions
• Difficult to bound, audit, or verify

Core problem: Coupling between what the model knows and how it searches/composes evidence.

The Solution: λ-RLM with Typed Functional Runtime

Core Innovation

Replace open-ended code generation with typed, functional runtime grounded in λ-calculus:

Key components:

1. Pre-verified combinators: Small library of deterministic operators (SPLIT, MAP, FILTER, REDUCE)
2. Leaf-only neural inference: LLM invoked only on bounded subproblems that fit in context window
3. Symbolic control flow: All orchestration handled by deterministic controller
4. Fixed-point recursion: Y-combinator “ties the knot” without LLM managing state

Why λ-Calculus?

Advantages over alternatives:

• FSMs: Insufficient for arbitrary recursion depths
• PDDL: Optimized for state-space search, not data transformation
• λ-Calculus: Treats prompt as first-class functional object

Y-Combinator magic:

• Enables recursion without function names or global state
• Eliminates reference errors and non-termination failures
• Provides formal foundation for reasoning about computation

Architecture

Input (length n) → Planner → Decomposition Strategy
                      ↓
              Functional Operators (SPLIT, MAP, REDUCE)
                      ↓
              Recursive Execution (Y-combinator)
                      ↓
              LLM Calls (only on leaf subproblems ≤ K)
                      ↓
              Compositional Aggregation
                      ↓
              Final Output

Separation of concerns:

• Planner: Decides decomposition strategy (symbolic, deterministic)
• Operators: Execute transformations (pre-verified, compositional)
• LLM: Provides semantic understanding (only at leaves, bounded)

Formal Guarantees

1. Termination by Construction

Under mild conditions on splitting operator:

• Guaranteed termination: No runaway execution
• Maximum depth: d = ⌈log_k*(n/τ*)⌉
  • n: input length
  • k*: branching factor
  • τ*: leaf size threshold

2. Closed-Form Cost Bounds

Predictable computation:

• Number of LLM calls: Pre-computed based on input size
• Total work: Bounded as function of decomposition policy
• No unpredictable control flow: All decisions made upfront

3. Controlled Accuracy Scaling

Accuracy improves with recursion depth:

• Deeper recursion → more fine-grained decomposition
• Trade-off between accuracy and compute
• Formal relationship between depth and expected accuracy

4. Optimal Partition Rule

Under simple cost model:

• Derives optimal way to split input
• Minimizes total cost while maintaining accuracy
• Provides principled decomposition strategy

Experimental Results

Setup

Tasks: 4 long-context reasoning tasks Models: 9 base models across 3 tiers

• Weak (8B/7B parameters)
• Medium (32B+ parameters)
• Strong (235B+ parameters)

Baselines:

• Direct LM: Standard prompting
• RLM: Recursive Language Model

Performance Improvements

Accuracy gains:

• Weak models: +21.9% (6.1% → 35.7%)
• Medium models: +18.6% (31.3% → 49.9%)
• Strong models: +8.8% (50.1% → 58.9%)

Latency reductions:

• Weak models: 4.1× faster (248.8s → 61.2s)
• Medium models: 4.1× faster (193.4s → 47.7s)
• Strong models: 3.3× faster (128.8s → 38.8s)

Head-to-head: λ-RLM outperforms RLM in 29 of 36 model-task comparisons.

Why λ-RLM Wins

1. Eliminates code generation failures: No parsing errors, runtime crashes
2. Predictable execution: Fixed recursion depth, bounded calls
3. Better decomposition: Optimal partitioning strategy
4. Reduced overhead: No LLM-generated control code
5. Compositional correctness: Pre-verified operators guarantee valid transformations

Technical Deep Dive

Functional Operators

SPLIT: Decompose input into chunks

split :: Prompt -> [Prompt]
split p = partition p into k chunks of size ≤ τ

MAP: Apply function to each element

map :: (Prompt -> Result) -> [Prompt] -> [Result]
map f ps = [f p | p <- ps]

FILTER: Select elements matching predicate

filter :: (Prompt -> Bool) -> [Prompt] -> [Prompt]
filter pred ps = [p | p <- ps, pred p]

REDUCE: Aggregate results

reduce :: (Result -> Result -> Result) -> [Result] -> Result
reduce op rs = fold op rs

Y-Combinator for Recursion

The Y-combinator enables recursion without explicit function names:

Y = λf. (λx. f (x x)) (λx. f (x x))

-- Recursive processing
process = Y (λrec. λprompt.
  if length prompt ≤ K
    then LLM(prompt)
    else reduce (map rec (split prompt)))

Key property: Ties the knot of recursion symbolically, eliminating need for LLM to manage recursive calls.

Operational Semantics

Formal semantics define execution:

1. Decomposition: ⟨split, p⟩ → ⟨[p1, ..., pk]⟩
2. Leaf evaluation: ⟨LLM, p⟩ → ⟨result⟩ if |p| ≤ K
3. Composition: ⟨reduce, [r1, ..., rk]⟩ → ⟨r⟩
4. Recursion: ⟨Y f, p⟩ → ⟨f (Y f) p⟩

Termination proof: By structural induction on decreasing input size.

Practical Implications

When to Use λ-RLM

Ideal for:

• Long documents: Reports, papers, books
• Code repositories: Multi-file analysis
• Evidence aggregation: Systematic reasoning over large collections
• Structured data: Hierarchical or compositional inputs

Integration

Easy to integrate:

from lambda_rlm import LambdaRLM

# Initialize with base LLM
rlm = LambdaRLM(
    base_model=llm,
    context_window=4096,
    split_strategy="optimal",
    max_depth=5
)

# Process long input
result = rlm.process(long_document)

Advantages Over RLM

Aspect	RLM	λ-RLM
Control flow	LLM-generated code	Pre-verified combinators
Termination	No guarantee	Guaranteed
Cost	Unpredictable	Bounded
Verification	Difficult	Formal proofs
Reliability	Code failures	Compositional correctness
Latency	High overhead	4.1× faster

Limitations and Future Work

Current Limitations

1. Fixed decomposition: Doesn’t adapt strategy during execution
2. Homogeneous chunks: All splits same size
3. Limited operators: Small library of combinators
4. Static planning: No dynamic adjustment based on intermediate results

Future Directions

1. Adaptive decomposition: Learn optimal splitting strategies
2. Heterogeneous partitioning: Variable chunk sizes based on content
3. Extended operator library: More sophisticated transformations
4. Hybrid approaches: Combine symbolic control with learned policies
5. Multi-modal extension: Apply to vision-language models

Theoretical Insights

Why Functional Programming?

Compositionality: Functions compose cleanly

• f ∘ g is well-defined
• Guarantees about composed behavior

Referential transparency: No side effects

• Same input → same output
• Enables formal reasoning

Higher-order functions: Functions as first-class values

• MAP, REDUCE operate on functions
• Enables powerful abstractions

Connection to Divide-and-Conquer

λ-RLM formalizes divide-and-conquer for LLMs:

1. Divide: SPLIT operator
2. Conquer: LLM on leaves
3. Combine: REDUCE operator

Optimal substructure: Solution composed from optimal subsolutions.

Takeaways

1. Typed control beats free-form code: Structured functional runtime outperforms open-ended generation
2. Formal guarantees matter: Termination and cost bounds enable reliable deployment
3. Separation of concerns works: Symbolic control + neural semantics is powerful combination
4. λ-Calculus is practical: Not just theory – delivers real performance gains
5. Efficiency through structure: Pre-verified operators reduce overhead dramatically

This work demonstrates that principled functional programming can make LLMs more reliable, efficient, and predictable for long-context reasoning. By grounding recursion in λ-calculus and eliminating open-ended code generation, λ-RLM achieves both theoretical elegance and practical performance.

The Y-combinator, a cornerstone of functional programming theory, proves its worth in modern AI systems – showing that classical computer science foundations remain highly relevant for solving contemporary challenges in large language models.

输入（长度 n）→ 规划器 → 分解策略
                      ↓
              函数运算符（SPLIT、MAP、REDUCE）
                      ↓
              递归执行（Y 组合子）
                      ↓
              LLM 调用（仅在叶子子问题 ≤ K 上）
                      ↓
              组合聚合
                      ↓
              最终输出

split :: Prompt -> [Prompt]
split p = 将 p 分区为 k 个大小 ≤ τ 的块

map :: (Prompt -> Result) -> [Prompt] -> [Result]
map f ps = [f p | p <- ps]

filter :: (Prompt -> Bool) -> [Prompt] -> [Prompt]
filter pred ps = [p | p <- ps, pred p]

reduce :: (Result -> Result -> Result) -> [Result] -> Result
reduce op rs = fold op rs

Y = λf. (λx. f (x x)) (λx. f (x x))

-- 递归处理
process = Y (λrec. λprompt.
  if length prompt ≤ K
    then LLM(prompt)
    else reduce (map rec (split prompt)))

from lambda_rlm import LambdaRLM

# 使用基础 LLM 初始化
rlm = LambdaRLM(
    base_model=llm,
    context_window=4096,
    split_strategy="optimal",
    max_depth=5
)

# 处理长输入
result = rlm.process(long_document)