論文の概要: Uncertainty-Aware Budget Allocation for Efficient LLM Tree Search
- arxiv url: http://arxiv.org/abs/2610.22858v1
- Date: Fri, 16 Oct 2026 03:03:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-20 00:56:07.736494
- Title: Uncertainty-Aware Budget Allocation for Efficient LLM Tree Search
- Title（参考訳）: 効率的なLLM木探索のための不確実性を考慮した予算配分
- Abstract要約: 木探索は大規模言語モデル(LLM)における多段階推論を強化する
共有中間状態からサンプリングされた継続は、主に重複し、いくつかの異なる解に崩壊することを示す。
我々は、不確実性から価値を分離するトレーニング不要のフレームワークである$textbfUncertainty-Aware Allocation$ (UAA)を提案する。
- 参考スコア（独自算出の注目度）: 26.88280449565821
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Tree search enhances multi-step reasoning in large language models (LLMs), yet prevailing methods expand every step with a fixed budget, irrespective of the marginal utility of expansion. We first show, across existing search algorithms, that continuations sampled from a shared intermediate state are largely duplicates and collapse to a few distinct answers. Critically, we find that the semantic dispersion of sibling actions predicts the redundancy of their downstream continuations, permitting a subtree's budget to be fixed before expansion. An information-theoretic analysis motivates this: treating the per-step budget as the Monte Carlo sample size for estimating a step's residual answer entropy, we derive a sufficient budget that shrinks with sibling dispersion. We accordingly propose $\textbf{Uncertainty-Aware Allocation}$ (UAA), a training-free framework that decouples value from uncertainty: values determine which candidates are promising, while uncertainty, estimated from sibling dispersion at no additional model cost, determines how many merit expansion, via uncertainty-aware pruning and uncertainty-aware budgeting. Across mathematical reasoning, logical reasoning, and planning benchmarks, UAA reduces token usage by up to $90\%$ and latency by up to $9\times$ at comparable accuracy, generalizing across four tree search algorithms and both open- and closed-source LLMs.
- Abstract（参考訳）: 木探索は大規模言語モデル(LLM)における多段階推論を強化するが、拡張の限界効用に関係なく、一般的な手法は固定予算で各ステップを拡大する。
最初に、既存の検索アルゴリズムを通して、共有中間状態からサンプリングされた継続は、主に重複し、いくつかの異なる答えに崩壊することを示す。
重要なことは、兄弟関係のセマンティックな分散は下流の継続の冗長性を予測し、サブツリーの予算を拡大前に固定することである。
ステップごとの予算をモンテカルロのサンプルサイズとして扱い、ステップの残差解のエントロピーを推定する。
本稿では,不確実性から価値を分離するトレーニングフリーフレームワークである$\textbf{Uncertainty-Aware Allocation}$ (UAA)を提案する。
数学的推論、論理的推論、計画ベンチマーク全体で、UAAはトークンの使用量を最大90\%、レイテンシを最大9\times$に減らし、4つの木探索アルゴリズムとオープンソースとクローズドソースの両方で一般化する。
関連論文リスト
- Exploit More, Explore Smarter for Budget-Constrained Agentic Search [6.894751260400948]
予算制約のあるエージェント検索は、エージェントが小さな評価予算の下で候補者を精査しなければならない場合に発生する。
我々は,拡張自体を情報の価値決定として扱うツリー検索ポリシーであるExTSを紹介した。
論文 参考訳（メタデータ） (2026-08-24T21:38:05Z) - Uncertainty-Aware Budget Allocation for Adaptive Test-Time Reasoning [13.41454380481593]
不確実性を考慮した予算割当(Uncertainty-Aware Budget Allocation、UAB)は、追加の推論コストなしで見積もられた要求当たりの不確実性に基づいて、固定サンプリング予算を再配置する凹型整数最適化フレームワークである。
1.5Bから27Bパラメータにまたがる6つのオープンウェイトモデルとブラックボックスモデルと、数学、論理学、選好タスクをカバーする5つの推論ベンチマークを評価した。
論文 参考訳（メタデータ） (2026-05-26T11:06:58Z) - Instance-Optimal Estimation with Multiple LLM Judges on a Budget [84.31744861038106]
我々は、この問題を*予算付きヘテロスケダティックなマルチジャッジ推定*として定式化する。
K$のプロンプト-レスポンスペア、J$の既知のコストと未知のクエリ-ジャッジ分散が与えられた場合、目標は、$ell_p$-errorを最小化しながら、有界スコアベクトルを推定することである。
EST-IVWEは,予算の低次項までのオラクルIVWEレートと一致していることを示す。
論文 参考訳（メタデータ） (2026-05-22T08:26:08Z) - Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents [40.18150559561834]
Budget-Aware Value Tree (BAVT) は、動的検索ツリーとしてマルチホップ推論をモデル化するトレーニングフリーの推論時間フレームワークである。
BAVTは一貫して並列サンプリングベースラインを上回っている。
論文 参考訳（メタデータ） (2026-03-13T04:10:27Z) - Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs [16.21023293204606]
既存の木探索政策は予算に依存せず、予算を終了条件として扱い、最終段階のオーバーブランチや早期終了につながる可能性がある。
本稿では,Budget-Guided MCTS (BG-MCTS)を提案する。
BG-MCTS は、MATH500 と AIME24/25 の様々な予算において、オープンウェイト LLM で予算に依存しない木探索ベースラインを一貫して上回っている。
論文 参考訳（メタデータ） (2026-02-10T09:23:26Z) - Scalable Neural Incentive Design with Parameterized Mean-Field Approximation [28.20524168049273]
力学と報酬がリプシッツであるとき、有限$N$ ID の目標は、PMFG によって $mathscrO(frac1sqrtN)$ で近似されることを示す。
さらに、反復平衡作用素の明示的な微分を利用して勾配を効率的に計算する、随伴平均集中設計(AMID)アルゴリズムを導入する。
論文 参考訳（メタデータ） (2025-10-24T13:18:54Z) - A*-Thought: Efficient Reasoning via Bidirectional Compression for Low-Resource Settings [60.48717743667377]
A*-Thoughtは、最も本質的な思考を識別し、分離するために設計された効率的なツリー検索ベースの統合フレームワークである。
LRMの推論過程を探索木として定式化し、各ノードは巨大な推論空間における推論スパンを表す。
低予算でQwQ-32Bを2.39$times$で改善し、高予算で出力トークンの長さを50%近く削減できる。
論文 参考訳（メタデータ） (2025-05-30T12:58:34Z) - Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。
検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。
意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。
各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
論文 参考訳（メタデータ） (2025-02-16T16:12:01Z) - Self-Evaluation Guided Beam Search for Reasoning [61.523627290397556]
我々は,Large Language Model (LLM) の推論プロセスのガイドと校正を行うための段階的自己評価機構を導入する。
本稿では,ビームサーチによる自己評価ガイダンスを統合した復号アルゴリズムを提案する。
我々のアプローチは、GSM8K、AQuA、StrategyQAにおいて、対応するCodexバックボンドベースラインをわずかに精度6.34%、9.56%、および5.46%で上回る。
論文 参考訳（メタデータ） (2023-05-01T02:37:59Z) - Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。
MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
論文 参考訳（メタデータ） (2020-10-12T17:41:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。