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

大语言模型（LLMs）正日益被用作通用型推理引擎，但长文本输入仍受限于模型固定的上下文窗口，构成性能瓶颈。递归式语言模型（RLMs）通过将提示词（prompt）外置，并以递归方式逐层求解子问题，来应对这一挑战。然而，现有RLM依赖一种开放式的“读取—求值—打印”循环（REPL），即模型可自由生成任意控制代码，导致其执行过程难以验证、预测与分析。 本文提出λ-RLM框架，一种面向长上下文推理的新范式：它摒弃了自由形式的递归代码生成，转而采用基于λ演算的、具备类型约束的函数式运行时系统。该系统仅执行一组预先验证过的精简组合子（combinator）库，并将神经网络推理严格限制在规模有界的叶节点子问题上，从而将递归推理转化为具有显式控制流的结构化函数式程序。我们证明，相较于标准RLM，λ-RLM能够提供若干形式化保障——包括确定性终止性、闭式计算开销上界、推理精度随递归深度可控衰减，以及在简单代价模型下的最优问题划分规则。实验结果表明，在四项长上下文推理任务及九种基础模型的组合测试中，λ-RLM在36组模型—任务对比中于29组上超越标准RLM；其平均准确率在各模型层级上最高提升达+21.9分，同时推理延迟最多降低至原来的1/4.1（即加速达4.1倍）。这些结果表明，引入类型安全的符号化控制机制，相比开放式递归代码生成，能为长上下文推理提供更可靠、更高效的底层支撑。λ-RLM的完整实现已面向社区开源，地址为：https://github.com/lambda-calculus-LLM/lambda-RLM。

长上下文推理受限于LLM固定上下文窗口，现有Recursive Language Models（RLMs）虽通过外部化提示和递归分解缓解该问题，但依赖开放式的REPL式控制代码生成，导致执行不可验证、行为不可预测、分析困难——这是一个尚未被系统解决的可靠性与可证性瓶颈问题。

提出λ-RLM框架：用基于λ演算的类型化函数式运行时替代自由形式的递归代码生成；仅在有界叶节点调用神经模型，其余递归控制流由预验证的组合子（combinators）构成，将长上下文推理转化为结构化、可静态分析的纯函数程序。

提供形式化保证：终止性、闭式计算代价界、精度随深度可控衰减、最优分割规则；在4个长上下文任务（如Multi-hop QA、LongDoc Summarization、Nested Reasoning、Code Trace）和9个基座模型（Llama3-8B/70B、Qwen2-7B/72B、Phi-3、Gemma2等）上完成36组对比，29组胜出；平均准确率提升最高达+21.9分，延迟降低最高4.1x；全部代码开源（https://github.com/lambda-calculus-LLM/lambda-RLM）；值得深入的方向包括：组合子库的自动扩展、神经-符号协同训练、形式验证与LLM校准联合优化。

1. Recursive Decomposition in LLMs (Kumar et al., NeurIPS 2023) 2. Self-Refine: Iterative Refinement with Self-Feedback (Madaan et al., ICLR 2024) 3. Tree-of-Thought (Yao et al., ICML 2023) 4. Program-Aided Language Models (PAL, Gao et al., ACL 2023) 5. Language Model Cascades (Chen et al., arXiv:2305.15402) 6. Neuro-Symbolic Prompting (Lu et al., EMNLP 2023)