PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Amartya Roy, Rasul Tutunov, Xiaotong Ji, Matthieu Zimmer, Haitham Bou-Ammar

arXiv:2603.20105v1cs.LGcs.AI

TL;DR

Long-context reasoning is constrained by fixed context windows, while standard RLMs rely on open-ended REPL control that is difficult to verify and predict. λ-RLM replaces that control with a typed runtime of deterministic combinators and uses neural inference only on bounded leaves. Across four task families and nine base models, it outperforms standard RLM in most comparisons while improving accuracy and latency.

  • Problem

    Fixed context windows limit long-context reasoning, and standard RLMs make execution difficult to verify and predict by relying on open-ended model-generated control code.

  • Method

    λ-RLM uses a typed λ-calculus runtime with pre-verified deterministic combinators for control flow and invokes the base model only on bounded leaf subproblems.

  • Results

    λ-RLM wins 29 of 36 model-task comparisons, improves average accuracy by up to +21.9 points, and reduces latency by 3.3× to 4.1× versus normal RLM.

  • Takeaways & Limitations

    Typed symbolic control separates neural reasoning from execution control, yielding more predictable and reliable long-context reasoning than open-ended recursive code generation.

  • Takeaways & Limitations

    The fixed combinator library may need task-specific extensions for code understanding, where RLM outperforms λ-RLM on CodeQA at the strongest tier.

Abstract

from arXiv · show

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.

1 Introduction

Long-context reasoning is limited by fixed context windows and the unpredictability of open-ended recursive control. λ-RLM replaces model-generated control code with typed symbolic execution while retaining recursive decomposition.

  • Motivation: Fixed context windows make long documents, codebases, and evidence collections difficult for Transformers to process reliably.Truncation and sliding-window prompting can lose early information and impair global consistency.
  • Motivation: RLMs externalize prompts and recursively decompose them through a model-driven REPL, but arbitrary code execution is difficult to bound and audit.The control loop can produce parse errors, runtime crashes, excessive recursion, malformed outputs, and unpredictable computation.
  • λ-RLM: λ-RLM uses pre-verified deterministic combinators and invokes the base model only on leaf subproblems that fit its context window.Planning and composition are handled symbolically rather than through LLM-generated code.
  • λ-RLM: λ-RLM grounds recursive control in λ-calculus, using fixed-point structure to separate semantic reasoning from structural execution.The controller provides explicit recursion while the model contributes understanding at bounded subproblems.
  • Results: 29 of 36 model-task comparisons favor λ-RLM, with average accuracy gains up to +21.9 points and latency reductions of 3.3× to 4.1×.The evaluation spans four long-context task families, nine base models, and context lengths up to 128K.

2 A Short Primer on λ-Calculus

The primer presents λ-calculus as a functional language built from variables, abstractions, and applications, with β-reduction defining evaluation. Fixed-point combinators provide recursion without named functions, supporting λ-RLM's recursive framework.

  • Core concepts: λ-calculus describes computation using functions and functional operations, providing the functional view used by λ-RLM.Recursion and composition are expressed through combinations of small operators rather than an LLM-generated loop.
  • Syntax: Every λ-calculus expression is a variable, an abstraction, or an application.Applications compose functional calls, while abstractions define functions over variables.
  • Evaluation: β-reduction evaluates a function application by substituting the argument for the function variable in its body.This gives function application its computational meaning.
  • Recursion: A fixed-point combinator satisfies fix(g) = g(fix(g)), turning a one-step recipe into a recursive function.This enables recursion without requiring function names.
  • Worked example: The factorial example separates a non-recursive functional recipe from the Y-combinator that supplies self-reference.Applying Y to the recipe produces the recursive factorial function.
  • Core definitions: λ-RLM defines base models with context window K and introduces cost, accuracy-decay, and deterministic composition functions.These definitions support later analysis of bounded model calls and recursive composition.

3 The λ-RLM Framework

λ-RLM implements long-context reasoning as a typed recursive program with deterministic combinators and a single learned leaf oracle. This design removes open-ended model-authored control while making execution more reliable, predictable, and analyzable.

  • Framework: λ-RLM retains prompt-as-environment recursive decomposition but replaces arbitrary model-generated programs with a typed functional runtime.The runtime executes a fixed library of trusted combinators while preserving symbolic prompt access and recursive sub-calls.
  • Framework: The runtime makes execution more reliable, bounds recursive calls in advance, and supports formal analysis through fixed functional structure.These benefits follow from removing free-form code generation and fixing the decomposition strategy.
  • From open-ended control: Standard RLM delegates inspection, decomposition, recursion, aggregation, and stopping decisions to a stochastic model inside an open-ended REPL loop.This creates no guaranteed termination, no predictable cost, and a substantial coding requirement.
  • From open-ended control: λ-RLM isolates uncertainty by using the language model only for bounded leaf subproblems and deterministic operators for decomposition, traversal, filtering, and aggregation.The resulting execution trace is a typed composition whose depth, model-call count, and cost are explicit functions of input size.
  • Combinator library: The compact library uses SPLIT, PEEK, MAP, FILTER, REDUCE, CONCAT, and CROSS to cover recurring long-context execution patterns.M is the only neural primitive, and it operates exclusively on bounded leaf inputs.
  • Combinator library: The combinator library is an extensible instantiation rather than a unique or exhaustive vocabulary for all reasoning domains.New typed combinators can be added conservatively without changing the central principle.
  • Core formulation: The core recursive program directly solves small prompts, otherwise splits them, recursively solves the pieces, and combines outputs with a task-specific operator.The fixed-point construction makes recursion an explicit semantic object rather than a model decision.

4 Theoretical Guarantees

λ-RLM provides formal guarantees for recursive long-context reasoning: termination, predictable cost, controlled accuracy scaling, and an analytically chosen partition size under explicit assumptions.

  • Termination: λ-RLM terminates for every finite input under bounded leaf-model execution and total deterministic combinators.The recursive proof uses strict size reduction until subproblems fit the leaf threshold.
  • Cost Bound: Its computation has a closed-form, pre-executable cost bound determined by input size, partition size, leaf threshold, and pricing constants.With symbolic composition, the composition cost is zero and the bound simplifies to pure leaf cost.
  • Accuracy Bound: Under bounded leaf accuracy and compositional reliability, end-to-end accuracy decreases in a controlled manner with recursion depth.The worst-case expression combines the correctness probabilities of all leaf calls and composition levels.
  • Scaling Laws: For decomposable tasks, λ-RLM retains accuracy A(τ∗) as input length grows, whereas direct inference decays exponentially in n/K.The decomposable result assumes deterministic composition with A⊕ = 1.

5 Experiments

The experiments compare λ-RLM with direct inference and Normal RLM across model tiers and long-context tasks. λ-RLM generally improves accuracy and latency, while Normal RLM retains advantages on some code-oriented settings.

  • Evaluation setup: The evaluation spans four benchmark task families, nine open-weight models across strength tiers, and context lengths from 8K to 128K.The baselines are direct single-call inference, Normal RLM with arbitrary Python in an open-ended REPL, and λ-RLM with a single executed combinator chain.
  • Accuracy: λ-RLM wins 29 of 36 accuracy cells, with wins concentrated in weak and medium model tiers and a 50% win rate at the strong tier.Powerful code-generating models can partially compensate for the absence of formal structure.
  • Accuracy: +28.6 pp is λ-RLM’s largest task-level accuracy improvement on OOLONG-Pairs, while CodeQA has the smallest gain at +10.8 pp.The O(n^2) cross-product is handled symbolically in λ-RLM, whereas strong models can use creative repository-navigation strategies on CodeQA.
  • Latency: λ-RLM is 3-6× faster than Normal RLM, with the largest speedup on OOLONG-Pairs at 6.2×.Normal RLM may require 5-12 turns of LLM-generated code, while λ-RLM executes a single pre-built combinator chain; latency variance is also lower.
  • Ablations: +21.9 pp accuracy and 4.0× latency reduction result when pre-verified combinators replace the ad-hoc REPL loop on Qwen3-8B × OOLONG.The ablation attributes the largest advantage to the combinator library, while random chunk sizes lose 16.8 pp.
  • Accuracy: λ-RLM (405B) averages 57.9% versus RLM (405B) at 55.3% and is 3.2× faster, but RLM wins CodeQA 62.1% to 55.7%.The results suggest task-specific extensions may benefit code understanding.

6 Related Work

λ-RLM builds on long-context and recursive reasoning work by replacing model-authored control code with deterministic, typed symbolic control. This separation targets the reliability gap in agentic execution while retaining neural reasoning for content.

  • Long-context methods increasingly scale inference by decomposing inputs into smaller subproblems, but standard heuristics can break global consistency.
  • Standard RLMs externalize prompts into a REPL where the model writes arbitrary code to inspect, decompose, and recursively process slices.
  • Open-ended model-authored control introduces parsing failures, runaway recursion, unpredictable execution, and difficult-to-audit traces.
  • λ-RLM replaces free-form control programs with a fixed library of deterministic combinators, shifting the model to bounded leaf-level oracle calls.
  • λ-RLM uses λ-calculus and fixed-point combinators to make recursion a first-class semantic object and support formal guarantees absent from standard recursive models.

7 Conclusions and Future Work

The paper concludes that λ-RLM reframes long-context reasoning as a structured functional program that separates neural reasoning from symbolic control. Its broader implication is that reliable AI systems may benefit from bounded oracles operating within verifiable environments.

  • λ-RLM replaces open-ended REPL loops with deterministic combinators, addressing unpredictability, non-termination, and the coding tax on smaller models.
  • A scaffolded 8B model can match or exceed a 70B model using standard recursive methods while reducing latency by up to 4.1×.
  • λ-RLM provides guaranteed termination and closed-form cost bounds, adding mathematical rigor to long-context reasoning scaffolds.
  • The authors suggest treating LLMs as bounded oracles within high-integrity, verifiable environments as a broader design principle for intelligent systems.

A Complete Example Trace

The example trace applies λ-RLM to classify 1000 questions by planning a five-way decomposition, estimating cost, invoking the model on leaves, and symbolically merging results. It reports a correct answer with six calls and lower cost than Normal RLM.

  • The OOLONG trace classifies 1000 questions in 131K tokens using λ-RLM’s recursive execution pipeline.
  • λ-RLM plans k∗ = 5, τ∗ = 26K, symbolic MERGECOUNTS composition, and depth d = 1 before execution.
  • The estimated execution cost is $0.17 for six calls, combining five leaf calls with one additional cost component.
  • MAP applies the model to five prompt partitions, producing category counts for neural leaf processing.
  • REDUCE symbolically merges the five results into aggregate counts and supports the final answer without another neural composition call.
  • The complete λ-RLM trace uses six LLM calls, costs $0.17, and is correct, whereas Normal RLM uses many calls, costs $1.12, and is incorrect.

B The Hierarchy of Computation

λ-RLM organizes execution into symbolic operators, deterministic planning, and bounded neural leaf inference. This hierarchy makes control flow pre-computed and auditable while restricting uncertainty to model calls that fit the context window.

  • The hierarchy separates λ-RLM computation into symbolic, planning, and neural layers.
  • The symbolic layer uses deterministic, pre-verified operators including SPLIT, MAP, FILTER, REDUCE, CROSS, CONCAT, and PEEK.
  • The planning layer computes k∗, τ∗, and recursion depth from input size, model costs, and context capacity.
  • Planning is pre-computed, has deterministic cost, and is constrained by accuracy considerations.
  • The neural layer invokes M only on partitions satisfying |P_i| ≤ τ∗ ≤ K, making it the only uncertain component.

C Proofs

The proofs establish that λ-RLM terminates, has predictable recursive cost, and provides controlled accuracy bounds under stated assumptions. They also derive an optimal partition size and contrast symbolic composition with neural composition.

  • Cost: N(n) = (k∗)^d + 1 exactly counts the leaf model calls plus one task-detection call.The leaves occur at recursion depth d, where d = ⌈log_k∗(n/τ∗)⌉.
  • Termination: λ-RLM terminates for every finite input because recursive calls strictly reduce rank, unlike standard RLM's potentially unbounded loop.The executor's split, MAP, REDUCE, and FILTER operations are assumed to halt.
  • Cost: When composition is purely symbolic, C⊕ = 0 and the total cost satisfies T(n) ≤ n k∗.The recurrence expands over recursion levels with leaf cost and composition cost separated.
  • Accuracy: For d ≥ 1, correctness requires all (k∗)^d leaves and all d compositions to be correct, yielding Aλ-RLM(n) ≥ A(τ∗)^(k∗)^d · A_d⊕.The bound is stated for the non-trivial case A(τ∗) < 1.
  • Optimal partition: Under the stated cost model, the cost-minimizing partition size is k∗ = 2.The theorem assumes linear input cost, output cost, and composition cost proportional to k.

D Algorithmic Details

The algorithmic implementation stores prompts externally, registers trusted combinators and the base model, then plans and executes a fixed recursive program. Neural work is confined to bounded leaves and explicitly specified synthesis steps, while symbolic operations handle control and aggregation.

  • System pipeline: λ-RLM initializes an external prompt state, registers pre-verified combinators, and exposes the base model as a callable leaf oracle.This setup is shared with the original RLM before the control-flow difference occurs.
  • System pipeline: Task detection uses one LLM call, while optimal planning uses zero LLM calls and pure mathematics.The planner selects ⊕ and π from a table and chooses k∗ and τ∗ under cost and accuracy constraints.
  • Combinator executor: The executor Φ calls the base model once when |P| ≤ τ∗ and otherwise deterministically splits the prompt into k∗ chunks.The recursive branch can optionally preview and filter chunks before composition.
  • Combinator executor: Only bounded leaves and specified synthesis steps use neural operations; splitting, filtering, traversal, and aggregation use trusted fixed-semantics combinators.This separation provides explicit control flow within the REPL runtime.
  • Task specializations: Pairwise tasks use neural labeling or extraction followed by symbolic quadratic pairing, keeping the expensive neural portion linear in chunk count.The pairing operation adds essentially no neural cost.
  • Task specializations: Multi-hop search symbolically previews and filters the corpus before neural extraction from the relevant documents and one synthesis call.The method reads only the selected evidence rather than the entire corpus.
Loading 2603.20105v1…