LLM을 위한 Y-콤비네이터: 람다-계산을 활용한 장문 맥락 처리 문제 해결

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

LLM은 점점 더 다양한 추론 도구로 활용되고 있지만, 고정된 컨텍스트 창은 여전히 장문의 입력 데이터를 처리하는 데 병목 현상을 일으킵니다. 재귀 언어 모델(RLM)은 프롬프트를 외부화하고 재귀적으로 하위 문제를 해결하여 이 문제를 해결합니다. 그러나 기존 RLM은 모델이 임의의 제어 코드를 생성하는 개방형 읽기-평가-반복 루프(REPL)에 의존하며, 이는 실행을 검증하고 예측 및 분석하기 어렵게 만듭니다. 저희는 장문 맥락 추론을 위한 프레임워크인 λ-RLM을 소개합니다. λ-계산에 기반한 타입이 지정된 함수형 런타임을 사용하여 자유 형식의 재귀 코드 생성을 대체합니다. λ-RLM은 미리 검증된 콤비네이터 라이브러리를 실행하고, 신경망 추론은 경계가 있는 하위 문제에만 적용하여 재귀적 추론을 명시적인 제어 흐름을 갖는 구조화된 함수형 프로그램으로 변환합니다. 저희는 λ-RLM이 표준 RLM에서 제공하지 않는 형식적인 보장을 제공한다는 것을 보여줍니다. 여기에는 종료, 폐쇄형 비용 경계, 재귀 깊이에 따른 제어된 정확도 확장, 그리고 간단한 비용 모델 하에서의 최적 파티션 규칙이 포함됩니다. 실험적으로, 네 가지 장문 맥락 추론 작업과 아홉 가지 기본 모델을 사용하여 λ-RLM은 36개의 모델-작업 비교 중 29개에서 표준 RLM보다 우수한 성능을 보였습니다. 또한 모델 등급에 따라 평균 정확도를 최대 +21.9 포인트까지 향상시키고, 지연 시간을 최대 4.1배까지 줄였습니다. 이러한 결과는 타입이 지정된 기호 제어가 개방형 재귀 코드 생성보다 장문 맥락 추론을 위한 더 안정적이고 효율적인 기반을 제공한다는 것을 보여줍니다. λ-RLM의 전체 구현은 다음 GitHub 저장소에서 오픈 소스로 제공됩니다: https://github.com/lambda-calculus-LLM/lambda-RLM.

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.