論文の概要: Best-of-Majority: Minimax-Optimal Strategy for Pass@$k$ Inference Scaling

• arxiv url: http://arxiv.org/abs/2510.03199v1
• Date: Fri, 03 Oct 2025 17:35:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-06 16:35:52.511722
• Title: Best-of-Majority: Minimax-Optimal Strategy for Pass@$k$ Inference Scaling
• Title（参考訳）: 長所のベスト: Pass@$k$推論スケーリングのための最小限の戦略
• Authors: Qiwei Di, Kaixuan Ji, Xuheng Li, Heyang Zhao, Quanquan Gu,
• Abstract要約: LLM推論は、しばしばプロンプトの一連の候補を生成し、多数決やBest-of-N (BoN)のような戦略を介して1つを選択する。 我々は,最上位の$k$報酬を選択する前に,上位の$N$サンプルにおいて,高い周波数の応答を候補に限定するピボットステップを備えたBest-of-Majority (BoM)を提案する。 多数決とBoNとは異なり、BoMは重要な利点がある:多数決とBoNとは異なり、そのパフォーマンスはN$を上昇しても低下しない。
• 参考スコア（独自算出の注目度）: 54.50689440956967
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: LLM inference often generates a batch of candidates for a prompt and selects one via strategies like majority voting or Best-of- N (BoN). For difficult tasks, this single-shot selection often underperforms. Consequently, evaluations commonly report Pass@$k$: the agent may submit up to $k$ responses, and only the best of them is used when computing regret. Motivated by this, we study inference scaling in the more general Pass@$k$ inference setting, and prove that neither majority voting nor BoN exhibits the desirable scaling with $k$ and the sampling budget $N$. Combining the advantages of majority voting and BoN, we propose a new inference strategy called Best-of-Majority (BoM), with a pivotal step that restricts the candidates to the responses with high frequency in the $N$ samples before selecting the top-$k$ rewards. We prove that when the sampling budget is $N=\tilde\Omega(C^*)$, the regret of BoM is $O(\epsilon_{\mathrm{opt}}+\sqrt{\epsilon_{\mathrm{RM}}^2C^*/k})$, where $C^*$ is the coverage coefficient, $\epsilon_{\mathrm{RM}}$ is the estimation error of the reward model, and $\epsilon_{\mathrm{opt}}$ is the estimation error of reward at the optimal response. We further establish a matching lower bound, certifying that our algorithm is minimax optimal. Beyond optimality, BoM has a key advantage: unlike majority voting and BoN, its performance does not degrade when increasing $N$. Experimental results of inference on math problems show BoM outperforming both majority voting and BoN.
• Abstract（参考訳）: LLM推論は、しばしばプロンプトの一連の候補を生成し、多数決やBest-of-N (BoN)のような戦略を介して候補を選択する。 難しいタスクでは、このシングルショットの選択は、しばしばパフォーマンスが低下する。 その結果、評価は一般的にPass@$k$を報告する: エージェントは最大$k$のレスポンスを送信でき、その最も良いものは、後悔を計算する際にのみ使用される。 これを動機として、より一般的なPass@$k$推論設定での推論スケーリングを研究し、多数決もBoNも$k$とサンプリング予算$N$で望ましいスケーリングを示していないことを証明した。 多数決とBoNの利点を組み合わせ,Best-of-Majority (BoM) と呼ばれる新たな推論戦略を提案する。 サンプリング予算が$N=\tilde\Omega(C^*)$の場合、BoMの後悔は$O(\epsilon_{\mathrm{opt}}+\sqrt{\epsilon_{\mathrm{RM}}^2C^*/k})$である。 さらに、一致した下界を確立し、アルゴリズムが最小限最適であることを証明します。 多数決とBoNとは異なり、そのパフォーマンスは$N$を増やせば低下しない。 数学問題に対する推論実験の結果、BoMは多数決とBoNのどちらよりも優れていた。

関連論文リスト

• Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds [20.024434010891433]
  我々はこの問題をHuman Feedback (HF) からのベイズ最適化(Bayesian Optimization from Human Feedback)と呼ぶ。 目的は、限定された嗜好フレームワークを使用して、最良のアクションを特定することである。 言い換えれば、スカラー値のサンプルと同数の優先的な新規サンプルは、ほぼ最適解を見つけるのに十分である。
  論文  参考訳（メタデータ） (2025-05-29T17:17:29Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• BoNBoN Alignment for Large Language Models and the Sweetness of Best-of-n Sampling [16.38043428743923]
  本稿では,大言語モデルからのサンプルを,ベスト・オブ・nドルサンプリングを用いてヒトの嗜好に合わせることの問題点について述べる。 基本モデルからKL距離に対する勝利率とのトレードオフの観点から,n$の最高値が本質的に最適であることを示す。 実験により,BoNBoNアライメントは基本方針に好適なモデルの生成において,大幅な改善をもたらすことが示された。
  論文  参考訳（メタデータ） (2024-06-02T18:42:57Z)
• Nearly Minimax Optimal Regret for Multinomial Logistic Bandit [8.087699764574788]
  本研究では,学習エージェントが文脈情報に基づいて順にアソシエーションを選択する,文脈多項ロジット(MNL)バンディット問題について検討する。 左下肢と左上肢の間には有意な差がみられ,特に最大配置サイズは有意な差がみられた。 我々は,一様報酬の下で,$tildeO(dsqrtT/K)$と一致する上限を実現する定数時間アルゴリズム OFU-MNL+を提案する。
  論文  参考訳（メタデータ） (2024-05-16T06:07:31Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。 ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。 我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
  論文  参考訳（メタデータ） (2023-02-07T02:22:31Z)
• Regret Minimization with Noisy Observations [18.24975895643299]
  典型的な最適化問題では、最低コストまたは最高値の選択肢の1つを選択することが課題である。 本稿では,このようなシナリオを最小化後悔モデルを用いて検討する。 本研究では,最も高い観測値を選択するナレーションアルゴリズムが最適値よりも任意に劣っていることを示す。
  論文  参考訳（メタデータ） (2022-07-19T17:48:54Z)
• Maillard Sampling: Boltzmann Exploration Done Optimally [11.282341369957216]
  この論文は、$K$武装バンディット問題に対するランダム化アルゴリズムを示す。 メイラードサンプリング(MS)は、各アームを閉じた形で選択する確率を計算する。 最適性を失わずに$sqrtKTlogK$に制限された最小値を改善するMS$+$というMSの変種を提案する。
  論文  参考訳（メタデータ） (2021-11-05T06:50:22Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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