추론에 대한 추론: LLM의 연쇄적 사고(Chain-of-Thought) 토큰 복잡성에 대한 BAPO 경계

Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs

연쇄적 사고(CoT) 추론은 최첨단 LLM의 성능을 향상시키는 주요 요인이지만, 상당한 지연 시간과 계산 비용을 초래합니다. 본 연구에서는 다음과 같은 근본적인 이론적 질문에 답하고자 합니다. 입력 크기가 증가함에 따라 문제를 해결하는 데 필요한 추론 토큰의 수는 얼마나 될까요? 본 연구는 LLM을 추상화하여 작업 해결에 필요한 정보 흐름을 정량화하는 bounded attention prefix oracle (BAPO) 모델을 확장하여, binary majority, triplet matching, 그리고 graph reachability와 같은 세 가지 대표적인 BAPO-hard 작업에 필요한 CoT 토큰에 대한 하한을 증명합니다. 입력 크기가 n일 때, 각 작업은 Ω(n)개의 추론 토큰을 필요로 한다는 것을 보여줍니다. 이러한 결과를 뒷받침하기 위해, 명시적인 구성 방법을 통해 일치하거나 거의 일치하는 상한을 제시합니다. 또한, 최첨단 추론 모델에 대한 실험 결과는 이러한 작업에서 대략 선형적인 추론 토큰 증가를 보여주며, 더 작은 추론 예산으로 제한할 경우 실패하는 현상을 나타냅니다. 이러한 결과는 CoT를 통한 추론 시간 계산의 근본적인 병목 현상을 밝히고, 최적의 추론 길이를 분석하는 데 유용한 도구를 제공합니다.

Inference-time scaling via chain-of-thought (CoT) reasoning is a major driver of state-of-the-art LLM performance, but it comes with substantial latency and compute costs. We address a fundamental theoretical question: how many reasoning tokens are required to solve a problem as input size grows? By extending the bounded attention prefix oracle (BAPO) model--an abstraction of LLMs that quantifies the information flow required to solve a task--we prove lower bounds on the CoT tokens required for three canonical BAPO-hard tasks: binary majority, triplet matching, and graph reachability. We show that each requires $Ω(n)$ reasoning tokens when the input size is $n$. We complement these results with matching or near-matching upper bounds via explicit constructions. Finally, our experiments with frontier reasoning models show approximately linear reasoning token scaling on these tasks and failures when constrained to smaller reasoning budgets, consistent with our theoretical lower bounds. Together, our results identify fundamental bottlenecks in inference-time compute through CoT and offer a principled tool for analyzing optimal reasoning length.