論文の概要: Tokenized Bandit for LLM Decoding and Alignment

• arxiv url: http://arxiv.org/abs/2506.07276v1
• Date: Sun, 08 Jun 2025 20:32:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 21:10:47.096562
• Title: Tokenized Bandit for LLM Decoding and Alignment
• Title（参考訳）: LLM復号・アライメントのためのTokenized Bandit
• Authors: Suho Shin, Chenghao Yang, Haifeng Xu, Mohammad T. Hajiaghayi,
• Abstract要約: トークン化線形バンドイット(TLB)とマルチアームバンドイット(TMAB)を導入する。 TLB と TMAB でそれぞれ $tildeO(LsqrtT)$ と $tildeO(LsqrtT2/3)$ のアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 32.22367277030496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the tokenized linear bandit (TLB) and multi-armed bandit (TMAB), variants of linear and stochastic multi-armed bandit problems inspired by LLM decoding and alignment. In these problems, at each round $t \in [T]$, a user submits a query (context), and the decision maker (DM) sequentially selects a token irrevocably from a token set. Once the sequence is complete, the DM observes a random utility from the user, whose expectation is presented by a sequence function mapping the chosen token sequence to a nonnegative real value that depends on the query. In both problems, we first show that learning is impossible without any structure on the sequence function. We introduce a natural assumption, diminishing distance with more commons (DDMC), and propose algorithms with regret $\tilde{O}(L\sqrt{T})$ and $\tilde{O}(L\sqrt{T^{2/3}})$ for TLB and TMAB, respectively. As a side product, we obtain an (almost) optimality of the greedy decoding for LLM decoding algorithm under DDMC, which justifies the unresaonable effectiveness of greedy decoding in several tasks. This also has an immediate application to decoding-time LLM alignment, when the misaligned utility can be represented as the frozen LLM's utility and a linearly realizable latent function. We finally validate our algorithm's performance empirically as well as verify our assumptions using synthetic and real-world datasets.
• Abstract（参考訳）: LLMデコーディングとアライメントにインスパイアされた、線形および確率的マルチアームバンディット問題の変種である、トークン化線形バンディット(TLB)とマルチアームバンディット(TMAB)を導入する。 これらの問題では、各ラウンド$t \in [T]$で、ユーザがクエリ(コンテキスト)を送信し、決定者(DM)がトークンセットから無効なトークンを順次選択する。 シーケンスが完了すると、DMはユーザからランダムなユーティリティを観察し、選択されたトークンシーケンスをクエリに依存する非負の実値にマッピングするシーケンス関数によって期待が提示される。 どちらの問題においても、まず、シーケンス関数の構造がなければ学習は不可能であることを示す。 自然仮定を導入し、より多くのコモンズ (DDMC) との距離を減らし、それぞれ TLB と TMAB に対して $\tilde{O}(L\sqrt{T})$ と $\tilde{O}(L\sqrt{T^{2/3}})$ のアルゴリズムを提案する。 副産物として、DDMC の下での LLM 復号アルゴリズムの(ほぼ)最適性を得る。 これはまた、誤整合ユーティリティが凍結LDMのユーティリティとして表現され、線形に実現可能な潜在関数として表現される場合、復号時LSMアライメントに即時適用できる。 最終的に我々のアルゴリズムの性能を実証的に検証し、合成および実世界のデータセットを用いて仮定を検証する。

関連論文リスト

• Foundations of Top-$k$ Decoding For Language Models [19.73575905188064]
  我々は、トップ$kの復号化を説明・一般化する理論的枠組みを開発する。 大規模な分岐に対して効率的に最適化する方法を示す。
  論文  参考訳（メタデータ） (2025-05-25T23:46:34Z)
• Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling [90.86991492288487]
  トークンの制約を評価するのは 違法にコストがかかる LCDは文字列上のグローバル分布を歪め、ローカル情報のみに基づいてトークンをサンプリングすることができる。 我々のアプローチは最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-07T18:30:18Z)
• Let the Code LLM Edit Itself When You Edit the Code [50.46536185784169]
  underlinetextbfPositional textbfIntegrity textbfEncoding (PIE) PIEは、標準的な完全再計算手法に比べて計算オーバーヘッドを85%以上削減する。 その結果、PIEは計算オーバーヘッドを標準の完全再計算手法に比べて85%以上削減することを示した。
  論文  参考訳（メタデータ） (2024-07-03T14:34:03Z)
• Can Large Language Models Play Games? A Case Study of A Self-Play Approach [61.15761840203145]
  LLM(Large Language Models)は、インターネットからの広範なデータを利用して、幅広い事前知識を格納する。 Monte-Carlo Tree Search (MCTS)は、信頼性の高い意思決定ソリューションを提供する検索アルゴリズムである。 この研究は、ターンベースのゼロサムゲームを効率的に解決するために、MCTSセルフプレイでLLMを活性化させる革新的なアプローチを導入している。
  論文  参考訳（メタデータ） (2024-03-08T19:16:29Z)
• Recursive Speculative Decoding: Accelerating LLM Inference via Sampling Without Replacement [11.91629418177851]
  投機的復号法(英: Speculative decoding)は、大規模言語モデルの推論・加速度法である。 近年の作業では、草稿の伐採によってこの方法が進歩している。 再帰的投機的復号法(Recursive Speculative Decoding:RSD)を提案する。
  論文  参考訳（メタデータ） (2024-02-21T22:57:49Z)
• Provably Efficient High-Dimensional Bandit Learning with Batched Feedbacks [93.00280593719513]
  本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。 具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。 我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
  論文  参考訳（メタデータ） (2023-11-22T06:06:54Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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