LLM 的 Y 组合子：用 λ 演算解决长上下文腐烂问题 The Y-Combinator for LLMs: Solving Long-Context Rot with λ-Calculus
用 λ 演算的类型化函数式运行时替代开放式 REPL 循环，实现可控的长上下文递归推理
前置知识
λ 演算（Lambda Calculus）
λ 演算是一个极简的计算形式系统，仅使用函数和函数操作来描述计算。其语法由三种表达式构成：变量 $x$、抽象（函数定义）$\lambda x. e$ 和应用（函数调用）$(e_1 \ e_2)$。核心计算规则是 β-归约：$(\lambda x. e) a \xrightarrow{\beta} e[x := a]$，即将参数 $a$ 替换到函数体 $e$ 中所有自由出现的变量 $x$。λ 演算虽然是图灵完备的，但其函数是匿名的，因此递归需要通过不动点组合子（如 Y 组合子）来实现。在本文中，λ 演算为递归推理提供了形式化基础，使得控制流可以被形式化验证。
本文的核心贡献就是将长上下文推理建立在 λ 演算的形式化基础上，用类型化的函数式运行时替代 LLM 生成的任意代码。理解 λ 演算是理解 λ-RLM 设计哲学和形式化保证的前提。
Y 组合子（Y-Combinator）
Y 组合子是无类型 λ 演算中的一个不动点组合子，定义为 $Y \equiv \lambda f. (\lambda x. f (x x)) (\lambda x. f (x x))$，满足 $Y g = g(Y g)$ 对所有 $g$ 成立。它的核心作用是允许在没有命名机制的情况下实现递归：给定一个非递归的「一步配方」函数 $G$（接受一个求解器 $f$ 并返回单步计算过程），$Y$ 将其「打结」为真正的递归函数。例如，阶乘的配方 $G = \lambda f. \lambda n. \text{if } (n=0) \text{ then } 1 \text{ else } n \cdot f(n-1)$，通过 $Y G$ 就能得到递归的阶乘函数。
λ-RLM 用 Y 组合子来编码递归结构，使得递归成为控制流中的显式语义对象，而非 LLM 决定自我调用时的涌现副效应。这是消除 RLM 中非终止和失控执行的关键技术手段。
递归语言模型（Recursive Language Models, RLM）
RLM 是一种长上下文推理框架，其核心思想是将用户提示视为外部环境的一部分，而非直接输入神经网络。模型在 REPL（读取-求值-打印循环）环境中将提示存储为变量，通过编写 Python 代码来符号化地访问提示、将其分解为切片，并递归调用自身处理子问题。这种「提示即环境 + 符号递归」的范式使模型能够处理远超其原生上下文长度的输入。然而，RLM 依赖 LLM 在每轮迭代中生成任意代码，形成了开放式控制循环，缺乏终止保证和成本可预测性。
RLM 是本文的直接前身和主要基线方法。理解 RLM 的设计和局限性是理解 λ-RLM 动机和创新点的关键。
上下文腐烂（Context Rot）
上下文腐烂指的是随着输入长度增加，Transformer 模型准确率呈指数级衰减的现象。其数学描述为 $A(n) = A_0 \cdot \rho^{n/K}$，其中 $A_0$ 是峰值准确率，$\rho \in (0,1]$ 是衰减因子，$K$ 是上下文窗口大小。当输入长度 $n$ 接近或超过上下文窗口 $K$ 时，$\rho^{n/K}$ 迅速趋近于零，导致模型性能急剧下降。朴素的截断或滑动窗口方法会迫使模型「遗忘」早期信息，破坏需要全局一致性或系统性证据收集的任务。
上下文腐烂是本文要解决的核心问题。λ-RLM 的理论贡献之一就是证明其准确率衰减是多项式级别 $\Omega(n^{-c})$，严格慢于直接推理的指数级衰减 $\Theta(\rho^{n/K})$。
组合子（Combinator）
在 λ-RLM 的语境中，组合子是一组预先验证的、确定性的、类型化的函数操作符，构成一个紧凑的库 $\mathcal{L}$。这些组合子对应长上下文推理中的五种功能模式：SPLIT 和 PEEK 支持外部提示的分解和局部检查；MAP 将递归或神经处理提升到集合上；FILTER 实现符号化选择和剪枝；REDUCE、CONCAT 和 CROSS 提供结构化聚合和组合；M 是唯一的神经原语，仅在有界叶子子问题上调用基础模型。所有组合子（除 M 外）都是确定性的，可以在 REPL 执行前独立验证。
组合子库是 λ-RLM 的核心技术组件，它用有限的、可审计的操作集合替代了 RLM 中 LLM 生成的任意代码。消融实验表明，组合子库是 λ-RLM 相对于 RLM 准确率提升的最大贡献者（+24.2pp）。
研究动机
大语言模型（LLM）越来越多地被用作通用推理器，但长输入始终受到固定上下文窗口的瓶颈限制。当输入超过窗口限制时——例如长文档、代码库、多文件仓库或大量证据集合——朴素的截断或滑动窗口提示迫使模型「遗忘」早期信息，往往破坏需要全局一致性或系统性证据收集的任务。为解决这一问题，递归语言模型（RLM）提出将提示外部化到 REPL 环境中，让模型通过编写代码来递归分解和处理子问题。然而，RLM 的强大能力伴随着实际代价：它依赖 LLM 驱动的控制循环，在每轮迭代中生成并执行任意代码直到模型决定完成。这种开放式 REPL 循环难以约束和审计，在实践中产生多种与底层推理任务正交的失败模式：代码可能无法解析或在运行时崩溃；递归可能被过度调用；中间输出可能格式错误；由于模型自身的控制流决策，计算可能变得不可预测。更广泛地说，让 LLM 无限制地编程自己的执行，在模型所知内容和它被允许如何搜索和组合证据之间引入了不良耦合。
本文的目标是本文的具体目标是设计一个替代 RLM 开放式代码生成的框架，该框架保留 RLM 的核心洞察——提示即环境加递归分解——但用基于 λ 演算的类型化函数式运行时替换自由形式的代码生成。具体而言，作者希望实现三个目标：第一，通过构造保证终止，消除代理脚手架中常见的非终止和失控执行失败；第二，提供可预测的计算：一旦选择分解策略，递归调用次数可以预先确定地约束；第三，通过减少委托给语言模型的「关键决策」数量来提高可靠性。最终目标是证明形式化控制结构可以有效替代原始模型参数规模，使「弱」层级模型（如 8B）能够匹配甚至超过缺乏结构化编排的「强」层级模型（如 70B+）的性能。
与已有工作不同的是，本文的独特切入角度在于将长上下文推理从「程序综合作为控制」转变为「函数组合作为控制」。现有 RLM 让 LLM 在每轮迭代中合成任意程序（token-by-token），执行轨迹是模型编写的无界命令序列；而 λ-RLM 将执行限制为一小批受信组合子的类型化组合，执行轨迹是一个类型化的操作符组合。这一转变的关键在于将语义推理（仍然由神经网络负责）与结构控制（变为符号化、确定性和可审计的）明确分离。具体来说，LLM 仅在真正需要神经推理的地方使用——即解决有界的叶子子问题——而分解、遍历、过滤和聚合都委托给确定性的符号操作符。这种设计选择的原因是 λ 演算提供了其他形式化体系缺乏的极简但通用的层级推理接口：有限状态机（FSM）不足以处理复杂文档分解所需的任意递归深度，规划领域定义语言（PDDL）针对状态空间搜索而非数据转换优化，而 λ 演算将提示视为一等函数对象。通过利用不动点组合子（如 Y 组合子），λ-RLM 无需 LLM 管理函数名或全局状态即可「打结」递归，有效消除了开放式 REPL 循环中常见的引用错误和非终止失败。
核心方法
λ-RLM 的整体思路可以用一个直觉来概括：长上下文推理应该是递归的，但递归应该由一个小型可信运行时执行，而非由语言模型编写的任意代码执行。框架保留了 RLM 的核心洞察——提示即环境加递归分解——但用类型化的函数式运行时替换了开放式代码生成。具体来说，λ-RLM 用一个小巧的预验证组合子库（包括 SPLIT、MAP、FILTER、REDUCE 等）执行所有控制流，基础语言模型 $M$ 仅在递归树的叶子节点上有界子问题上调用。技术路线上，整个控制器被表达为一个类型化函数操作符的不动点：$$\lambda\text{-RLM} \equiv \text{fix} \; \lambda f. \lambda P. \text{if } |P| \leq \tau^* \text{ then } M(P) \text{ else } \text{REDUCE}(\oplus, \text{MAP}(\lambda p_i. f \; p_i, \text{SPLIT}(P, k^*)))$$ 这个表达式从内向外解读：SPLIT 将提示确定性地分解为 $k^*$ 个子提示；MAP 对每个子提示递归应用相同的求解器；REDUCE 按任务特定的组合规则聚合部分输出。不动点组合子使定义成为递归的，递归深度由 $d = \lceil \log_{k^*}(n/\tau^*) \rceil$ 预先确定地约束。
λ-RLM 的核心创新在于用「受信组合子的类型化组合」替代「LLM 生成的任意代码」作为控制机制。与 RLM 的本质区别体现在三个层面：第一，在控制接口上，RLM 允许语言模型在 REPL 中逐 token 合成任意程序，而 λ-RLM 将执行限制为一组预先验证的确定性组合子；第二，在不确定性来源上，RLM 中不确定性进入两次——通过模型对任务的语义判断和通过模型生成的控制流——而 λ-RLM 将这两个角色分离，语言模型仅用于需要神经推理的有界叶子子问题；第三，在形式化保证上，RLM 的开放式循环缺乏终止保证和成本可预测性，而 λ-RLM 通过构造保证终止（定理 1），提供封闭形式的成本界（定理 2）和有控制的准确率缩放（定理 3）。消融实验直接验证了这一创新的贡献：用自由形式代码生成替换组合子库会损失 24.2pp 准确率并增加 3.9× 延迟，这恰好就是 RLM 的结果。
方法步骤详情
λ-RLM 的完整执行分为五个阶段，如算法 1 所述。阶段 1（REPL 初始化）：初始化 REPL 状态，将提示 $P$ 存储为环境变量（而非上下文窗口），注册预验证的组合子库 $\mathcal{L}$，并将 $M$ 注册为可调用的叶子求解器。阶段 2（任务检测）：通过符号化探测（查看 $P$ 的前 500 个字符和长度）获取元信息，进行一次 $M$ 调用从菜单中选择任务类型 $\tau_{\text{type}}$。阶段 3（分派）：如果 $|P| \leq K$（提示适合上下文窗口），直接调用 $M(P)$ 返回，无需分解。阶段 4（规划）：如果 $|P| > K$，根据任务类型查表获取组合操作符 $\oplus$ 和执行计划 $\pi$，然后规划器选择最优参数 $(k^*, \tau^*, d)$，其中 $k^*=2$（定理 4 证明的最优分区大小）。阶段 5（构建并执行递归执行器）：构建递归执行器 $\Phi$ 并在 REPL 中单次执行。递归执行器 $\Phi$（算法 2）的工作流程为：如果 $|P| \leq \tau^*$，格式化叶子提示并通过 $M$ 求解；否则，SPLIT 产生 $k^*$ 个块，PRUNE 按需剪枝，MAP 递归调用 $\Phi$，最后 REDUCE 确定性地组合结果。
技术新颖性
λ-RLM 的技术新颖性体现在多个层面。首先，将 λ 演算的不动点组合子用于 LLM 推理控制是全新的视角：Y 组合子使得递归成为控制流中的显式语义对象，而非模型决定调用自身时的涌现副效应，这消除了开放式 REPL 循环中常见的引用错误和非终止失败。其次，类型化组合子库的设计——包含 SPLIT、PEEK、MAP、FILTER、REDUCE、CONCAT、CROSS 七种操作符——是经过精心选择的「最小充分」集合，对应长上下文推理中反复出现的五种功能模式，既保证了覆盖搜索、分类、聚合、成对比较、摘要和多跳组合等主要执行模式，又保持了运行时的有限性、类型化和可审计性。第三，定理 4 证明的最优分区规则 $k^*=2$ 是一个简洁而深刻的结果：在成本函数 $C(n) = c_{\text{in}} \cdot n + c_{\text{out}} \cdot \bar{n}_{\text{out}}$ 和常数组合成本 $C_\oplus(k) = c_\oplus \cdot k$ 下，$k^*=2$ 是使总成本递推最小化的最小整数，这一结果在消融实验中得到验证——随机选择 $k$ 会损失 16.8pp 准确率。第四，理论贡献包括定理 1（终止性保证：$M$ 调用次数精确为 $N(n) = (k^*)^d + 1$）、定理 2（成本界：当 $\oplus$ 纯符号化时 $C_\oplus = 0$，$T(n) \leq \frac{n}{\tau^*} \cdot C(\tau^*)$）、定理 3（准确率界：最坏情况下 $A_{\lambda\text{-RLM}}(n) \geq A(\tau^*)^{n/\tau^*} \cdot A_\oplus^d$）和推论 5（缩放定律：幂律衰减 $\Omega(n^{-c})$ 严格慢于指数衰减 $\Theta(\rho^{n/K})$）。
实验结果
λ-RLM 在四个长上下文推理任务（S-NIAH、OOLONG、OOL-Pairs、CodeQA）和九个基础模型（Qwen3-8B/32B/235B、Llama-8B/70B/405B、Mistral-7B/8x22B/Codestral-22B）上的实验结果非常突出。在 36 个模型-任务比较中，λ-RLM 在 29 个（81%）中获胜。在弱模型（8B/7B）层级，λ-RLM 的平均准确率为 35.7%（Qwen3-8B）和 33.1%（Llama-8B），分别比 RLM 的 13.8% 和 13.3% 提升了 +21.9pp 和 +19.8pp。在中等模型层级，λ-RLM 同样表现优异，Qwen3-32B 达到 49.9% 对比 RLM 的 31.6%。延迟方面，λ-RLM 在所有模型和任务上都比 RLM 快，平均加速 3.3× 到 4.1×。最大的加速出现在 OOL-Pairs 任务（6.2×），因为二次交叉积在 λ-RLM 中完全符号化处理（零神经成本），而 RLM 需要神经计算。五个针对性比较进一步验证了核心假设：C1 显示 λ-RLM 对弱模型的帮助是巨大的（+21.9pp，4.0× 更快）；C2 显示 8B 模型 + λ-RLM 匹配 70B 模型 + RLM（35.7% vs 36.1%，3.1× 更快）；C3 显示 λ-RLM(8B) 超过直接推理的 405B 模型（35.7% vs 27.2%）；C5 显示在前沿，λ-RLM(405B) 平均优于 RLM(405B)（57.9% vs 55.3%，3.2× 更快），但 RLM 在 CodeQA 上获胜（62.1% vs 55.7%）。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| S-NIAH（大海捞针，O(1) 复杂度） | F1 分数，宏平均跨上下文长度桶 | λ-RLM：Qwen3-8B 24.6%，Qwen3-32B 41.8%，Qwen3-235B 51.3%，Llama-8B 22.1%，Llama-70B 44.2%，Llama-405B 49.8%，Mistral-7B 18.5%，Mixtral-8x22B 38.6%，Codestral-22B 40.2% | RLM：Qwen3-8B 8.4%，Qwen3-32B 28.3%，Qwen3-235B 46.8%，Llama-8B 10.2%，Llama-70B 31.5%，Llama-405B 52.4%，Mistral-7B 6.1%，Mixtral-8x22B 26.4%，Codestral-22B 29.7% | λ-RLM 在 8/9 模型上获胜，平均提升 +19.7pp，平均加速 3.6×。Llama-405B 是唯一 RLM 获胜的模型（52.4% vs 49.8%），因其创造性地使用正则搜索。 |
| OOLONG（O(n) 复杂度） | Score，宏平均跨上下文长度桶 | λ-RLM：Qwen3-8B 48.3%，Qwen3-32B 62.5%，Qwen3-235B 68.4%，Llama-8B 45.7%，Llama-70B 61.2%，Llama-405B 61.7%，Mistral-7B 40.2%，Mixtral-8x22B 55.8%，Codestral-22B 45.6% | RLM：Qwen3-8B 24.1%，Qwen3-32B 42.7%，Qwen3-235B 56.5%，Llama-8B 22.6%，Llama-70B 45.3%，Llama-405B 63.8%，Mistral-7B 18.3%，Mixtral-8x22B 38.9%，Codestral-22B 48.2% | λ-RLM 在 7/9 模型上获胜，平均提升 +18.3pp，平均加速 4.2×。Llama-405B 和 Codestral-22B 是 RLM 获胜的两个模型，因其自适应批处理和最优迭代代码。 |
| OOL-Pairs（O(n²) 复杂度，成对推理） | F1 分数，宏平均跨上下文长度桶 | λ-RLM：Qwen3-8B 34.8%，Qwen3-32B 48.2%，Qwen3-235B 61.5%，Llama-8B 31.6%，Llama-70B 50.7%，Llama-405B 64.3%，Mistral-7B 28.4%，Mixtral-8x22B 44.1%，Codestral-22B 47.6% | RLM：Qwen3-8B 4.2%，Qwen3-32B 18.6%，Qwen3-235B 38.4%，Llama-8B 3.8%，Llama-70B 21.3%，Llama-405B 42.7%，Mistral-7B 2.1%，Mixtral-8x22B 14.5%，Codestral-22B 22.8% | λ-RLM 在所有 9 个模型上全部获胜，平均提升 +28.6pp，平均加速 6.2×。这是最大改进，因为二次交叉积在 λ-RLM 中完全符号化处理（零神经成本），而 RLM 需要神经计算。 |
| CodeQA（代码理解，可变复杂度） | 准确率，宏平均跨上下文长度桶 | λ-RLM：Qwen3-8B 35.2%，Qwen3-32B 47.1%，Qwen3-235B 54.2%，Llama-8B 32.8%，Llama-70B 43.8%，Llama-405B 55.7%，Mistral-7B 27.6%，Mixtral-8x22B 42.5%，Codestral-22B 44.8% | RLM：Qwen3-8B 18.5%，Qwen3-32B 36.8%，Qwen3-235B 58.6%，Llama-8B 16.7%，Llama-70B 46.4%，Llama-405B 62.1%，Mistral-7B 12.3%，Mixtral-8x22B 32.4%，Codestral-22B 49.3% | λ-RLM 在 5/9 模型上获胜，平均提升 +10.8pp，平均加速 3.1×。RLM 在 4 个模型上获胜（Qwen3-235B、Llama-70B、Llama-405B、Codestral-22B），因为 CodeQA 受益于自由形式的仓库导航和代码感知分块。 |
局限与改进
论文的局限性体现在多个方面。首先，λ-RLM 的固定组合子库虽然覆盖了主要的长上下文推理模式，但在某些特定任务上表现不如 RLM。具体来说，在 CodeQA 任务上，RLM 的自由形式代码生成（如多遍回溯读取、按函数分块、自适应批处理）在强模型上表现更好——Llama-405B 在 RLM 下达到 62.1% 而 λ-RLM 仅 55.7%。这表明固定组合子库的表达能力有上限，可能需要任务特定的扩展。其次，λ-RLM 的规划器需要预先知道输入大小、上下文窗口和任务类型来选择最优参数，这在某些场景下可能不现实。第三，虽然 λ-RLM 在弱和中等模型上优势明显，但在强模型（235B+）层级，胜率降至 50%，说明强大的代码生成能力可以部分弥补缺乏形式化结构的问题。第四，论文的实验虽然涵盖了 9 个模型和 4 个任务，但任务类型主要集中在搜索、聚合、成对推理和代码理解，对于其他长上下文推理模式（如多跳推理、复杂推理链）的验证尚不充分。第五，论文的理论分析基于一些假设（如模型正则性假设 A1-A5），这些假设在实践中可能不完全成立。
独立分析的弱点
从独立分析的角度，λ-RLM 存在几个值得关注的弱点。第一，组合子库的固定性限制了其在特定领域的表现。CodeQA 任务的结果表明，当任务需要创造性、任务特定的代码策略时，固定组合子库无法充分表达。改进方向可以是设计可扩展的组合子接口，允许用户根据特定任务需求注册新的类型化组合子，同时保持形式化保证。第二，任务检测阶段（阶段 2）依赖一次 $M$ 调用来选择任务类型，这引入了额外的不确定性和延迟。消融实验显示固定任务类型会损失 7.1pp 准确率，说明任务检测很重要但可能不可靠。改进方向是设计更鲁棒的任务检测机制，可能结合符号化特征和轻量级分类器。第三，λ-RLM 假设输入提示是一个完整的文本，通过 SPLIT 按固定大小分块。对于结构化输入（如代码文件、表格数据），这种朴素分块可能破坏语义边界。改进方向是引入结构感知的分块策略。第四，论文的理论分析假设叶子子问题之间的条件独立性，但在实际任务中，子问题之间可能存在依赖关系，这会影响准确率界的紧致性。
未来方向
作者和基于成果可延伸的未来研究方向包括多个方面。首先，作者指出 λ-RLM 的组合子库是「可扩展的基础而非封闭的词汇表」，未来可以保守地添加新的类型化组合子以覆盖更多推理模式，如多跳推理、因果推理或反事实推理。其次，作者提出的 Scale-Substitution 假设——形式化控制结构可以替代原始模型规模——可以在更多任务和更大规模上验证。第三，λ-RLM 的形式化框架可以与其他推理时缩放技术（如思维链、思维树、自我反思）结合，探索混合架构。第四，论文的理论结果（终止性、成本界、准确率界）可以用于设计自适应调度策略，根据输入特性和资源约束动态调整递归深度和分区大小。第五，λ-RLM 的确定性执行特性使其非常适合硬件加速和编译优化，未来可以探索专用的执行引擎。第六，将 λ-RLM 的思想扩展到多模态场景（如长视频理解、大型代码库分析）是另一个有前景的方向。
复现评估
论文的复现条件非常友好。作者已将 λ-RLM 的完整实现开源在 GitHub（github.com/lambda-calculus-LLM/lambda-RLM），这大大降低了复现门槛。实验使用的所有模型都是开源权重模型（Qwen3、Llama、Mistral 系列），通过 vLLM 服务，不需要闭源 API。数据方面，论文使用了来自 RLM 论文（Zhang et al., 2026）的基准测试套件，涵盖四个任务和多个上下文长度桶（8K 到 128K）。算力方面，实验使用了从 8B 到 405B 的九个模型，最大模型（Llama-405B、Qwen3-235B）需要显著的 GPU 资源，但弱模型（8B/7B）在消费级硬件上即可运行。难度方面，λ-RLM 的核心算法（组合子库、递归执行器、规划器）相对简单，主要复杂度在于 REPL 环境的实现和与 vLLM 的集成。每个配置运行两次取平均，结果可复现性较高。总体而言，复现难度中等，开源代码和开源模型使得有足够 GPU 资源的研究者可以在合理时间内复现主要结果。
论文图表