【DL輪読会】Rethinking the Role of Prompting Strategies in LLM Test-Time Scaling: A Perspective of Probability Theory

Rethinking the Role of Prompting Strategies in LLM TestTime Scaling: A Perspective of Probability Theory Hiroto Osaka, Matsuo Iwasawa Lab, M1

書誌情報 ▍論文タイトル ▍概要 LLM の Test-Time Scaling において、最適なプロン Rethinking the Role of Prompting Strategies in LLM プト戦略を確率論的に分析 Test-Time Scaling: A Perspective of Probability シンプルな CoT が複雑な戦略（ToT, MAD 等）より Theory 高いスケーリング適性を持つことを理論的に証明 OpenAI o1 の長時間思考アプローチへの理論的裏付 ▍会議 け ACL 2025 (Long Papers) ▍リンク ▍著者 aclanthology.org/2025.acl-long.1356/ Yexiang Liu, Zekun Li, Zhi Fang, Nan Xu, Ran He, Tieniu github.com/MraDonkey/rethinking_prompting Tan 2

• https://aclanthology.org/2025.acl-long.1356/
• https://github.com/MraDonkey/rethinking_prompting

背景 スケーリングの潮流と課題 ▍Training-Time から Test-Time Scaling へ ▍プロンプト戦略の複雑化 事前学習の拡大競争から、推論時に計算資源を投じて性 「より複雑な構造」で性能向上を狙う研究が多数： 能を上げるアプローチへ変化。 Tree of Thoughts (ToT)：思考を木構造で展開し探 索 Majority Voting：複数回サンプリングして多数決 Multi-Agent Debate (MAD)：複数エージェントに Tree Search / Verifier：木探索や検証器を使用 議論させ合意形成 Self-Refine：自己批判と修正のループ 課題意識 複雑な手法は計算コストを無限にかけた時 本当に単純な CoT より優れているのか？ → 理論的な比較は未解明 [1] Self-consistency improves chain of thought reasoning in language models. 3

実験設定 モデル・タスク・スケーリング手法 ▍評価ベンチマーク 多数決評価のため、正解が一意に定まるタスクを選定 数理推論：GSM8K, GSM-Hard, MATH-500 科学知識：MMLU (STEM 系) ▍評価対象モデル Open Weight Closed API Llama-3-8B-Instruct GPT-4o-mini Qwen2.5-7B-Instruct Gemini-1.5-Flash GLM-4-9B-Chat Phi-3.5-mini-Instruct ▍スケーリング手法 最も基本的かつ強力なスケーリング手法を採用 Majority Voting（多数決） サンプリング回数 N を変化させ、最頻出回答を採 用 N y^ = arg max ∑ I(yi = y) ​ ​ y ​ ​ i=1 最も基本的で、戦略差をスケーリング曲線として観 察可能 4

実験設定 プロンプト戦略① ▍P : Non-Iterative（非反復） Direct Prompting (DiP) ゼロショット回答 Chain-of-Thought (CoT) "Let’s think step by step." Least-to-Most (L2M) 複雑な問題を部分問題に分 解して順に解く Step-Back Prompting (SBP) 原理原則を先に問う Analogical Prompting (AnP) 類似問題を生成させる 1 ​ [2] Least-to-Most Prompting Enables Complex Reasoning in Large Language Models. [4] Large Language Models as Analogical Reasoners. [3] Take a Step Back: Evoking Reasoning via Abstraction in Large Language Models. 5

実験設定 プロンプト戦略② ▍P : Iterative（反復） Tree-of-Thoughts (ToT) [7] 以下の繰り返し： 「3つの異なる思考案を出せ」 「有望なものを選べ」 Multi-Agent Debate (MAD) 3つのモデルをエージェントとして使用 数ラウンド議論させ、最も一貫した結果を選択 Self-Refine (S-RF) [8] 自分の回答を批判し、修正するループを回す 2 ​ [5] Improving Factuality and Reasoning in Language Models through Multiagent Debate. 6

実験結果 スケーリングにおける CoT の支配 ▍サンプリング回数 N vs 正解率 初期（N が小さい） 複雑な戦略（ToT, L2M）が CoT を上回るケースあり スケーリング（N を増加） CoT の性能向上が著しい 最終的にほぼ全条件で CoT が最高性能に到達 複雑な戦略は Pass@1 は高いが、スケーリングによ る伸びしろが小さい Figure 1: 各プロンプト戦略のスケーリング曲線 7

実験結果 コスト等価条件での比較 ▍同じ予算ならどちらが高性能か サンプリング回数 N 固定での比較は不公平 （ToT は 1 回で大量のトークンを消費している） トークンコスト調整 N i × Ti ≈ C ​ ​ ：サンプリング回数, Ti ：平均トークン数, C ： コスト Ni ​ ​ Figure 2: トークンコスト調整後の比較 コスト C を揃えると、CoT の優位性はさらに拡大 8

理論的分析 問題難易度の定義 ▍定義 正解確率 p1 、最大誤答確率 pmax として： ​ ​ 難易度 条件 Easy p1 > pmax Moderate p1 = pmax Hard p1 < pmax ​ ​ ​ 意味 ​ ​ ​ 正解が単独最大確率 正解と誤答が同率 特定の誤答が最大確率 ▍直感的理解 Easy：多数決すれば正解が選ばれる Moderate：確率的に揺らぐ Hard：多数決すると誤答が選ばれる → スケーリン グが逆効果 Figure 3: $N$ の増加による各戦略の正解率変化（SBP → CoT） 9

理論的分析 Majority Voting の収束定理 Theorem 1：Easy Question lim Pr( ​ N →∞ 正解) = 1 正解確率が単独最大なら、N ↑ で正解率 → 100% Theorem 2：Hard Question lim Pr( ​ N →∞ 正解) = 0 誤答が最大確率なら、N ↑ で正解率 → 0% Theorem 3：Moderate Question lim Pr( ​ N →∞ ∣S∣ 正解) = ∣S∣1 ​ = 同率1位の回答数 Theorem 4：逆転条件 Pi が初期優位でも「正解と最大誤答の差」が小さ ければ、十分大きな N で Pi に逆転される ​ ′ ​ 大数の法則により、最大確率の回答が多数決で勝つ → 正解が最大確率でなければスケーリングは逆効果 10

理論的分析 CoT の難易度分布 ▍実験結果 CoT は全モデルで Easy 比率が最高かつ、Hard 比率が最 低 → CoT はスケーリングで伸びる問題が多い 極限性能 Acc の計算 Acc = Easy% + Moderate% ∣S∣ ​ CoT がほぼ全モデルで最高または同等の Acc を達成 Table 1: 各戦略の難易度分布と極限性能 11

メカニズム解析 初期優位性とスケーリング適性 ▍Theorem 4 の直感 Pass@1 が高くても、スケーリングで逆転されうる 条件：戦略 Pi と Pi で 1. Pi の正解確率 > Pi （Pi が初期優位） 2. しかし Pi は「正解と最大誤答の差」が小さい → 十分大きな N で Pi が Pi を逆転 ▍Table 2 の読み方 行(↑)：逆転される側になる問題数 列(↓)：逆転する側になる問題数 CoT 列が最大、CoT 行が最小 → CoT はスケーリングで最も伸びしろがある ​ ′ ​ ′ ​ ​ ​ ​ ′ ​ ​ Table 2: 戦略間の逆転関係 12

メカニズム解析 誤答分布の均一性 ▍なぜ均一な誤答分布が有利か 同じ正解率 60% でも： 戦略 A：0.6, 0.35, 0.05 → 誤答が集中 戦略 B：0.6, 0.2, 0.2 → 誤答が分散 → 戦略 B の方が Majority Voting で正解が勝ちやすい ▍KL divergence 誤答分布と一様分布の KL を測定 小さいほど均一 → 有利 CoT は多くのモデルで最小 ▍なぜ複雑な戦略は誤答が偏るのか ToT：「有望な分岐を選べ」が特定パスに誘導 MAD：合意形成で「説得力のある」誤答に収束 S-RF：修正ループが同じ方向に改善を継続 対照的に CoT は： 緩い制約のみ → 各サンプルが独立に多様なパスを 探索 間違えるときも様々な方向に間違える 13

提案手法 スケーリングの予測 ▍予測手法 1. 少数サンプル（約 40 回）で {p1 , ..., pm } を推定 2. 中心極限定理 で各回答の出現回数を正規分布近似 3. O(1) で正解確率を計算 ​ Pr( ​ ▍予測精度 で誤差 1% 未満 最適戦略 PN∗ の予測も全て的中 N ≥ 10 正解) ≈ 1 − Φ (− p −σ p/N ) 1 max ​ 2 ​ ​ ​ Table 4: 予測精度の評価 ​ Figure 4: 予測と実測の比較 14

提案手法 Adaptive Scaling と Dynamic Selection ▍Adaptive Scaling Hard 問題は N = 1 で停止し、Easy 問題にリソースを 集中させる Theorem 1-3 の内容 Easy 問題：N ↑ で正解率 → 100% Hard 問題：N ↑ で正解率 → 0% なぜ根拠になるか Hard 問題ではサンプリングを増やすほど正解率が 下が る → 計算リソースの無駄、むしろ逆効果 実装：LLM による判定 or Oracle（正解情報）を使用 ▍Dynamic Selection 問題ごとに最適なプロンプト戦略を選択する Theorem 4 の内容 Pass@1 で優位な戦略でも、正解と最大誤答の差が 小さければスケーリングで別戦略に逆転される なぜ根拠になるか 同じ問題でも CoT では Hard、SBP では Easy というこ とがありえる → 最適な戦略は問題ごとに異なる 15

提案手法の結果 Adaptive Scaling の効果 ▍結果 各戦略に Adaptive Scaling を適用 Hard 問題で N = 1 停止 → 無駄な計算を回避 ほぼ全戦略で性能向上 ▍具体的な改善幅（GSM8K） 設定 N = 10 N = 100 CoT（通常） 86.0% 85.8% CoT + Adaptive 90.2% 95.1% Figure 5: Adaptive Scaling の効果 16

提案手法の結果 Dynamic Selection と両手法の組み合わせ ▍Dynamic Selection の効果 Oracle：問題ごとに最適な Pi を選択 N = 1 でも約 97% の精度 戦略選択だけで大幅改善可能 ▍両手法の組み合わせ ​ 設定 GSM8K MATH-500 通常 Majority@10 86.0% 15.2% Figure 6: 各戦略のスケーリング曲線（Dynamic Oracle が黒線） Adaptive + Dynamic w/ Oracle 97.4% 61.0% ※ Oracle 使用時の上限性能。Oracle なしでこの性能に近づける方法 は今後の研究課題 Figure 7: 両手法の組み合わせ結果 17

議論 OpenAI o1 への示唆 ▍本研究との対応（著者の推測） 本研究の知見 o1 での実現（推測） CoT のスケーリング適性が高い 長い CoT を単一生成で実行 大きな N での Majority Voting 内部で複数推論パスを暗黙探索 誤答分布の均一性が重要 シンプルな推論構造を維持 ※ o1 の内部実装は非公開のため、本研究の知見からの推測 ▍理論的解釈 長い CoT ≈ 大きな N でのサンプリングを単一生成 内で実現 複雑なエージェント構造よりシンプルな CoT の大量 探索が効率的 [6] OpenAI: Learning to Reason with LLMs. 18

まとめ ▍まとめ 1. 主要な発見 Test-Time Scaling では シンプルな CoT が最強 約 80% のケースで CoT or DiP が最高性能 2. 理論的説明 CoT は Easy 問題が多く、Hard 問題が少ない CoT は誤答分布が均一 3. 実用的貢献 O(1) でスケーリング性能を予測可能 Adaptive + Dynamic で大幅改善 ▍議論 限界 Majority Voting 以外（MCTS 等）は未検証 Oracle なしでの実現は今後の課題 議論・思ったこと Oracle のようなものがない未確定のところでどうこ の理論を確立していくかは今後の課題 単純な生成で複雑な戦略のデメリットがあるという 類の主張ではなかった（スケールさせた時の話に限 定した理論だった） 19

参考文献 1. Wang, X., et al. (2023). Self-consistency improves chain of thought reasoning in language models. ICLR 2023. 2. Zhou, D., et al. (2023). Least-to-Most Prompting Enables Complex Reasoning in Large Language Models. ICLR 2023. 3. Zheng, H., et al. (2024). Take a Step Back: Evoking Reasoning via Abstraction in Large Language Models. ICLR 2024. 4. Yasunaga, M., et al. (2023). Large Language Models as Analogical Reasoners. arXiv:2310.01714. 5. Du, Y., et al. (2023). Improving Factuality and Reasoning in Language Models through Multiagent Debate. arXiv:2305.14325. 6. OpenAI. (2024). Learning to Reason with LLMs. https://openai.com/index/learning-to-reason-with-llms/ 7. Yao, S., et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. NeurIPS 2023. 8. Madaan, A., et al. (2023). Self-Refine: Iterative Refinement with Self-Feedback. NeurIPS 2023. 9. Liu, Y., et al. (2025). Rethinking the Role of Prompting Strategies in LLM Test-Time Scaling. ACL 2025. (本論文) 20

• https://openai.com/index/learning-to-reason-with-llms/