論文の概要: Optimal Stopping vs Best-of-$N$ for Inference Time Optimization

• arxiv url: http://arxiv.org/abs/2510.01394v1
• Date: Wed, 01 Oct 2025 19:25:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 16:59:20.841832
• Title: Optimal Stopping vs Best-of-$N$ for Inference Time Optimization
• Title（参考訳）: 推論時間最適化のための最適停止とベストオブN$
• Authors: Yusuf Kalayci, Vinod Raman, Shaddin Dughmi,
• Abstract要約: PandoraのBox問題に基づく推論時間最適化のための新しいフレームワークを提案する。 そこで我々は,報酬分布を知らずにいつ生成を止めるかを決定するアルゴリズムを開発した。 この結果から,最適停止理論と推定時間スケーリングの原則的ブリッジが確立された。
• 参考スコア（独自算出の注目度）: 11.334978981105559
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large language model (LLM) generation often requires balancing output quality against inference cost, especially when using multiple generations. We introduce a new framework for inference-time optimization based on the classical Pandora's Box problem. Viewing each generation as opening a costly "box" with random reward, we develop algorithms that decide when to stop generating without knowing the underlying reward distribution. Our first contribution is a UCB-style Pandora's Box algorithm, which achieves performance that is provably close to Weitzman's algorithm, the optimal strategy when the distribution is known. We further adapt this method to practical LLM settings by addressing reward scaling across prompts via a Bradley-Terry inspired transformation. This leads to an adaptive inference-time optimization method that normalizes rewards and learns stopping thresholds on the fly. Experiments on the AlpacaFarm and HH-RLHF datasets, using multiple LLM-reward model pairs, show that our adaptive strategy can obtain the same performance as non-adaptive Best-of-N sampling while requiring 15-35 percent fewer generations on average. Our results establish a principled bridge between optimal stopping theory and inference-time scaling, providing both theoretical performance bounds and practical efficiency gains for LLM deployment.
• Abstract（参考訳）: 大規模言語モデル(LLM)の生成は、特に複数の世代を使用する場合、出力品質と推論コストのバランスを必要とすることが多い。 PandoraのBox問題に基づく推論時間最適化のための新しいフレームワークを提案する。 それぞれの世代をランダムな報酬を伴うコストのかかる「箱」の開き方と見なして、報酬分布を知らずにいつ生成を止めるかを決定するアルゴリズムを開発する。 最初のコントリビューションは UCB スタイルの Pandora の Box アルゴリズムで,分布が知られているときの最適戦略である Weitzman のアルゴリズムに近い性能を実現する。 我々はBradley-Terryにインスパイアされた変換を通じて、プロンプト間の報酬スケーリングに対処することで、この手法を実用的なLCM設定に適用する。 これにより、報酬を正規化し、ハエのしきい値の停止を学習する適応推論時間最適化法が導かれる。 複数のLLM-リワードモデルペアを用いたAlpacaFarmとHH-RLHFデータセットの実験により、我々の適応戦略は、平均15～35%の世代で、非適応的Best-of-Nサンプリングと同じ性能が得られることを示した。 本研究は,最適停止理論と推定時間スケーリングの原理的橋渡しを行い,LLM展開における理論的性能境界と実用的効率向上の両立を図った。

関連論文リスト

• $\ abla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasonerは、トークンログに対する差別化可能な最適化をデコードループに統合する反復生成フレームワークである。 $nabla$-Reasonerは、挑戦的な数学的推論ベンチマークで20%以上の精度の向上を実現している。
  論文  参考訳（メタデータ） (2026-03-05T08:42:54Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Visualising Policy-Reward Interplay to Inform Zeroth-Order Preference Optimisation of Large Language Models [0.36326779753373206]
  Zeroth-Order (ZO) 最適化では、勾配の代わりに関数評価を使用し、メモリ使用量を削減しているが、高次元モデルでは緩やかな収束に悩まされている。 ZOPrOは、大規模言語モデルにおける優先度最適化のために設計された新しいZOアルゴリズムである。 本手法は,一階法に匹敵する収束時間を実現しつつ,報酬信号の連続的な向上を実証する。
  論文  参考訳（メタデータ） (2025-03-05T12:49:48Z)
• Smoothed Normalization for Efficient Distributed Private Optimization [54.197255548244705]
  フェデレートされた学習は、参加者のプライバシを備えた機械学習モデルを可能にする。 トレーニングやフィードバックのない問題に対して、差分にプライベートな分散手法は存在しない。 証明可能な収束保証付き分散アルゴリズム$alpha$-$sf NormEC$を導入する。
  論文  参考訳（メタデータ） (2025-02-19T07:10:32Z)
• Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradient [57.9629676017527]
  本研究では,プルーンドモデルの損失を最適化することにより,確率空間におけるプルーニングマスクを直接学習する最適化に基づく構造的プルーニングを提案する。 我々は、基底となるベルヌーイ分布をサンプルのバイナリ・プルーニングマスクに学習することでこれを実現する。 LLaMA, LLaMA-2, LLaMA-3, Vicuna, Mistral モデルによる実験により, 本手法の有効性と有効性を示すことができた。
  論文  参考訳（メタデータ） (2024-06-15T09:31:03Z)
• Discovering Preference Optimization Algorithms with and for Large Language Models [50.843710797024805]
  オフライン優先最適化は、LLM(Large Language Model)出力の品質を向上・制御するための重要な手法である。 我々は、人間の介入なしに、新しい最先端の選好最適化アルゴリズムを自動で発見する客観的発見を行う。 実験は、ロジスティックと指数的損失を適応的にブレンドする新しいアルゴリズムであるDiscoPOPの最先端性能を示す。
  論文  参考訳（メタデータ） (2024-06-12T16:58:41Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。 過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。 報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
  論文  参考訳（メタデータ） (2024-05-26T05:38:50Z)
• Value Augmented Sampling for Language Model Alignment and Personalization [39.070662999014836]
  報酬最適化のための新しいフレームワーク、価値拡張サンプリング(VAS)を提案する。 VASは、ポリシーと値関数を併用することなく、最適報酬最大化ポリシーを解く。 我々のアルゴリズムは、いくつかの報酬を作曲し、展開期間中に各報酬の幅を制御できる新しい能力を解き放ちます。
  論文  参考訳（メタデータ） (2024-05-10T17:59:04Z)

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

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