論文の概要: Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study
- arxiv url: http://arxiv.org/abs/2610.12542v1
- Date: Thu, 08 Oct 2026 16:01:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-13 04:06:29.22166
- Title: Equal-Budget Monte Carlo Tree Search versus Randomized-Restart List Scheduling for DAG Workflows: A Controlled Equal-Budget Computational Study
- Title（参考訳）: DAGワークフローにおける不等予算モンテカルロ木探索とランダム再起動リストスケジューリング--等予算計算による検討
- Abstract要約: Monte Carlo Tree Search (MCTS) はしばしばDAG (direct-acyclicgraph) のスケジューリングのために提案されている。
ほとんどの研究は、それを否定できる比較を決して実行しない。
私たちは、その比較を制御されたプロトコルの下で実行します。すべての腕に同じ予算 — 構築され、評価される候補スケジュールの数と同じです。
結果は制御された合成ドメイン(Nは8,16,32タスク、2-8プロセッサ、予算は2048年まで)に限定されます。
- 参考スコア（独自算出の注目度）: 5.019289205106538
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Monte Carlo Tree Search (MCTS) is often proposed for scheduling directed-acyclic-graph (DAG) workflows, yet most studies never run the comparison that could refute it - giving a much simpler method the same search effort. We run that comparison under a controlled protocol. All arms receive an identical budget - the same number of candidate schedules built and evaluated: an MCTS scheduling method, preregistered as the main arm; a randomized-restart list scheduler with no search tree as the control; and a textbook-UCT MCTS arm as a registered follow-up on the same domain. The analysis plan was locked before data collection; an independent checker confirmed all 768 confirmation-stage schedules valid with correct finish times. At the main budget of 2048 evaluated schedules, MCTS is 2.88% worse than the restarts (95% CI [-3.62%,-2.15%]; the 72 of 96 held-out instances with positive baseline-relative headroom). The deficit is not budget starvation: on the separate exploration pool restarts self-improve by 1.85% where MCTS gains 0.24%, and 700 of 720 of MCTS's first results are merely the warm start it was handed. The studied selection rule locks deterministically onto the first-expanded child, keeping its trials correlated while restarts draw gains from the tails; the causal link to makespan remains an inference. A structural map locates where the tree stops paying: restarts win on sparse irregular workflows, no difference is detectable on regular layered ones, and dense ones leave no room to improve. Swapping the rule for textbook UCT removes most of the deficit (-0.26%, 95% CI [-0.71%,+0.23%]) without reversing its sign. Results are confined to a controlled synthetic domain (N in {8,16,32} tasks, 2-8 processors, budgets up to 2048); we make no claim about larger budgets.
- Abstract（参考訳）: Monte Carlo Tree Search (MCTS) は、DAG (direct-acyclic-graph) のワークフローをスケジューリングするためにしばしば提案されているが、ほとんどの研究では、それを否定するような比較は行わない。
私たちはその比較を制御されたプロトコルで実行します。
MCTSスケジューリングメソッドはメインアームとして事前登録され、ランダムに再起動するリストスケジューラはコントロールとして検索ツリーを持たない。
分析計画は、データ収集の前にロックされ、独立したチェッカーが、正しい完了時間で有効な768の確認ステージスケジュールをすべて確認した。
2048年の評価スケジュールの予算では、MCTSは再起動よりも2.88%悪い(95% CI [-3.62%,-2.15%]、96件中72件はベースライン相対性がある)。
個別の探査プールでは、MCTSが0.24%、MCTSの最初の結果の720のうち700は単に温暖なスタートに過ぎなかった。
研究された選択規則は、最初の拡張子に決定的にロックされ、再起動が尾部からの利得を引き出す間、その治験の相関が保たれ、因果関係は推論のままである。
構造図は、ツリーの支払いが止まる場所を特定する。不規則なワークフローで再起動し、通常の階層化ワークフローでは差が検出されず、密集したワークフローは改善の余地を残さない。
教科書UTTの規則を適用すれば、そのサインを覆さずに、ほとんどの赤字(-0.26%、95% CI [-0.71%、+0.23%)が取り除かれる。
結果は制御された合成ドメインに限られる(N in {8,16,32} task, 2-8 processor, budgets to 2048)。
関連論文リスト
- Measuring Collapse and Correction in Homogeneous-Panel LLM Debate [51.03982042769297]
マルチエージェント大言語モデル(LLM)の議論は、最終回答が改善するかどうかによってしばしば評価されるが、運動は必ずしも改善されない。
標準的な最終精度評価は、これらの反対のメカニズムを詳述する。
複数選択質問(MCQ)に関する同質な議論のための監査可能なプロトコルを導入し、各実行を、崩壊、修正、オンセット、署名された介入ユーティリティよりも、遷移台帳として記録する。
論文 参考訳（メタデータ） (2026-09-28T14:31:19Z) - Agora: Git as Shared Memory for Collective AutoResearch [54.31992252587096]
別々のセッションで作業する調査エージェントは、他の人が試したことと、構築可能な結果を知る必要がある。
各コミットは結果、洞察、仮説、検証、報告を記録し、それを以前の作業とリンクする。
約12日間に渡り,13人の言語モデル労働者がアゴラを重み移動問題の解決に利用したことを報告した。
論文 参考訳（メタデータ） (2026-09-16T04:00:54Z) - Winning by Peeking: Unenforced Budgets and Test-Set Selection Inflate Short-Budget AutoML Comparisons [4.156551823302787]
簡単なAutoMLエンジンであるOrcetraが513のOpenMLデータセットでFLAMLとAutoGluonに勝っているというケーススタディを報告する。
両方のマージンは、結果テーブルに表示できないプロトコルの欠陥から来ています。
論文 参考訳（メタデータ） (2026-08-07T15:00:10Z) - CUSUM-Shaped Inference-Time Monitoring and Targeted Re-Decoding for Quantized Small Language Model Reasoning [0.6999740786886536]
MGT-Bは、事前サンプリングの不確かさと変性の特徴の重なり合う窓を、位置条件による経験的尾の確率にマップする。
ログしきい値h=10のマニュアル選択後に最初に観察された問題同一性に対して,その効果が持続するかどうかを検証した。
どちらの分析も確証がなく、実証的要因は有効な電子プロセスや電子検出器として確立されていない。
論文 参考訳（メタデータ） (2026-07-22T13:34:17Z) - Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion [0.0]
ヒントに富んだ数独では、フォワードパスは基本的にグリッド全体をコミットする。
検索開始前にすべてのハードスライス障害が決定され、最初のパスが真のソリューションで要求される値を確実に削除する。
手がかりに富んだ補完では、LDTのようなシステムは、学習された探索手順ではなく、一発の償却予測器である。
論文 参考訳（メタデータ） (2026-07-22T00:05:34Z) - Revisiting Tree Search for LLMs: Gumbel and Sequential Halving for Budget-Scalable Reasoning [53.06065010530373]
本稿ではGumbel AlphaZero MCTSの適応版であるReSCALEについて述べる。
ReSCALEはGSM8Kで58.4%、Game24で85.3%に達する。
論文 参考訳（メタデータ） (2026-03-22T10:32:48Z) - 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) - Anytime Sequential Halving in Monte-Carlo Tree Search [1.3820916757781068]
本稿では,任意のタイミングで停止し,良好な結果を返すアルゴリズムの任意のバージョンを提案する。
合成MAB問題と10の異なるボードゲームにおける経験的結果から、アルゴリズムの性能がSequential Halving や UCB1と競合していることが示されている。
論文 参考訳（メタデータ） (2024-11-11T17:49:47Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。
効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。
我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
論文 参考訳（メタデータ） (2020-06-15T21:36:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。