論文の概要: 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を用いた推論時間計算における基本的なボトルネックを特定し,最適な推論長を解析するための基本的ツールを提供する。
関連論文リスト
- CoLT: Reasoning with Chain of Latent Tool Calls [31.228763375347608]
CoT(Chain-of-Thought)は、大規模言語モデル(LLM)の推論能力を高める重要な手法である。
ツールコールとして潜伏推論を実装する新しいフレームワークである「CoLT」を提案する。
論文 参考訳（メタデータ） (2026-02-04T06:12:53Z) - Chain Of Thought Compression: A Theoritical Analysis [24.613200477865572]
Chain-of-Thought (CoT)は、大規模言語モデルの高度な推論能力を解放した。
CoTは、余分なトークンの生成によって計算コストが禁止される。
最近の研究では、潜在状態への推論ステップの圧縮(暗黙のCoT圧縮)がトークン効率の代替となることが示されている。
論文 参考訳（メタデータ） (2026-01-29T11:42:03Z) - FrugalPrompt: Reducing Contextual Overhead in Large Language Models via Token Attribution [3.4666771782038652]
大規模言語モデル(LLM)は、その恒星の性能の大部分を入力コンテキストの拡大に負っているが、そのような冗長性は金銭的コスト、炭素フットプリント、推論時間の遅延を膨らませている。
本稿では,LLMのための新しいプロンプト圧縮フレームワークであるFrugalPromptを紹介する。
我々は,4つのNLPタスク(感性分析,コモンセンスQA,要約,数学的推論)にまたがるアプローチを評価する。
論文 参考訳（メタデータ） (2025-10-18T10:22:13Z) - Rethinking Thinking Tokens: LLMs as Improvement Operators [80.12087211785949]
推論トレーニングは、LLMに長い思考の連鎖(長いCoT)を生み出す動機を与え、自己チェックによるソリューション戦略を探索することを可能にする。
これにより、精度が高くなりますが、コンテキストの長さ、トークン/計算コスト、応答レイテンシが膨らみます。
現在のモデルはメタ認知を活用して、このParetoフロンティアで他の組み合わせを提供できるのでしょうか?
i) 多様なドラフトを並列に生成し、(ii) それらを有界なテキストワークスペースに蒸留し、(iii) このワークスペース上に条件付き精製する。
論文 参考訳（メタデータ） (2025-10-01T17:08:59Z) - Truth in the Few: High-Value Data Selection for Efficient Multi-Modal Reasoning [71.3533541927459]
アクティベーション推論ポテンシャル(RAP)と呼ばれる新しいデータ選択パラダイムを提案する。
RAPは、真のマルチモーダル推論を刺激する各サンプルのポテンシャルを推定することで、認知サンプルを識別する。
我々のRAP法は、トレーニングデータの9.3%しか使用せず、計算コストを43%以上削減しながら、常に優れた性能を実現している。
論文 参考訳（メタデータ） (2025-06-05T08:40:24Z) - PixelThink: Towards Efficient Chain-of-Pixel Reasoning [70.32510083790069]
PixelThinkは、外部から推定されるタスクの難しさと内部で測定されたモデルの不確実性を統合する、シンプルで効果的なスキームである。
シーンの複雑さと予測信頼度に応じて推論の長さを圧縮することを学ぶ。
実験により,提案手法は推論効率と全体セグメンテーション性能の両方を改善した。
論文 参考訳（メタデータ） (2025-05-29T17:55:49Z) - 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) - Sketch-of-Thought: Efficient LLM Reasoning with Adaptive Cognitive-Inspired Sketching [64.74765550805024]
Chain-of-Thoughtはステップバイステップの問題解決を促すが、中間出力の過剰な冗長性を犠牲にすることが多い。
我々は,認知にインスパイアされた推論パラダイムを言語制約と統合する促進フレームワークであるSketch-of-Thought(SoT)を提案する。
SoTはトークンを最大84%削減し、18の推論データセットで最小限の精度ロスを達成している。
論文 参考訳（メタデータ） (2025-03-07T06:57:17Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。