論文の概要: Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs

• arxiv url: http://arxiv.org/abs/2602.02909v1
• Date: Mon, 02 Feb 2026 23:33:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-04 18:37:15.136094
• Title: Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMs
• Title（参考訳）: 推論の理由:BAPO境界がLLMの強靭性に及ぼす影響
• Authors: Kiran Tomlinson, Tobias Schnabel, Adith Swaminathan, Jennifer Neville,
• Abstract要約: チェーン・オブ・ソート(CoT)推論によるインタイムスケーリングは、最先端のLLMパフォーマンスの主要な要因であるが、相当なレイテンシと計算コストが伴う。 入力サイズが大きくなるにつれて、問題の解決に何個の推論トークンが必要となるのか? 正規の3つのBAPO-hardタスク(二進数、三重項マッチング、グラフ到達性)に必要なCoTトークンの下位境界を証明した。
• 参考スコア（独自算出の注目度）: 16.81068280262534
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.
• Abstract（参考訳）: チェーン・オブ・ソート(CoT)推論による推論時間スケーリングは、最先端のLLMパフォーマンスの主要な要因であるが、かなりのレイテンシと計算コストが伴う。 入力サイズが大きくなるにつれて、問題の解決に何個の推論トークンが必要となるのか? 有界注意接頭辞 (BAPO) モデルを拡張することにより、タスクの解決に必要な情報フローを定量化する LLM を抽象化し、標準的な3つのBAPO-ハードタスク(二分数、三分数マッチング、グラフ到達性)に必要なCoTトークンの下位境界を証明した。 入力サイズが$n$である場合、それぞれに$Ω(n)$推論トークンが必要であることを示す。 これらの結果を、明示的な構成によってマッチングあるいは近接マッチングの上界で補完する。 最後に、フロンティア推論モデルによる実験により、これらのタスクと障害に対するおよそ線形推論トークンのスケーリングが、より小さな推論予算に制約された場合、理論的な下限と一致することを示す。 本研究は,CoTを用いた推論時間計算における基本的なボトルネックを特定し,最適な推論長を解析するための基本的ツールを提供する。

関連論文リスト

• Fractured Chain-of-Thought Reasoning [61.647243580650446]
  完全CoTと解のみのサンプリングを補間する統合推論時間戦略であるフラクチャードサンプリングを導入する。 フラクチャードサンプリングは、Pass@kとトークンの予算に対して、急激なログ線形スケーリングゲインをもたらすため、優れた精度とコストのトレードオフを一貫して達成できることを示す。
  論文  参考訳（メタデータ） (2025-05-19T11:30:41Z)
• Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
  決定論的有限オートマトン(DFAs)を用いたフレームワークの定式化 正しい解を生成する確率が最大になるような推論トークンが最適に存在することを示す。 新たな問題に対する推論トークンの最適個数を予測し、最適でない回答をフィルタリングすることで、一貫した精度の向上が得られる。
  論文  参考訳（メタデータ） (2025-04-02T17:45:58Z)
• How Well do LLMs Compress Their Own Chain-of-Thought? A Token Complexity Approach [4.055489363682199]
  推論長とモデル性能の関係について,最初の系統的研究を行った。 このトレードオフは、非常に明確な推論チェーンにまたがって持続することを示す。 提案手法は, 理論的な限界から遠く離れていることを示す。
  論文  参考訳（メタデータ） (2025-03-03T03:48:20Z)
• When More is Less: Understanding Chain-of-Thought Length in LLMs [51.631483479081645]
  大規模言語モデル(LLM)は複雑な問題を分解するためにChain-of-Thought(CoT)推論を用いる。 本稿は、長いCoTがより優れていると仮定されることがしばしばあり、長いCoTが常に優れているとは限らない、と論じる。
  論文  参考訳（メタデータ） (2025-02-11T05:28:59Z)
• FLARE: Faithful Logic-Aided Reasoning and Exploration [47.46564769245296]
  タスク分解を用いて問題空間をトラバースする新しい手法を提案する。 我々はLarge Language Modelsを使ってソリューションを計画し、クエリを事実に軟式化し、論理プログラミングコードを使って述語する。 提案手法は,生成したコードに対する推論プロセスの忠実度を計算し,外部の解法に頼らずにマルチホップ探索のステップを解析する。
  論文  参考訳（メタデータ） (2024-10-14T19:39:11Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。