Tokenized Bandit for LLM Decoding and Alignment
Suho Shin, Chenghao Yang, Haifeng Xu, MohammadTaghi Hajiaghayi
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 ∈ [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 and the query to a real value. 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 Õ(L √ T ) and Õ(L √ 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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
3 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- T-POP: Test-Time Personalization with Online Preference Feedback cites Direct Preference Optimization: Your Language Model is Secretly a Reward Model
- T-POP: Test-Time Personalization with Online Preference Feedback cites Training language models to follow instructions with human feedback
- Multitask Prompted Training Enables Zero-Shot Task Generalization cites Language Models are Few-Shot Learners
- Direct Preference Optimization: Your Language Model is Secretly a Reward Model cites Multitask Prompted Training Enables Zero-Shot Task Generalization
- Direct Preference Optimization: Your Language Model is Secretly a Reward Model cites Language Models are Few-Shot Learners
- Direct Preference Optimization: Your Language Model is Secretly a Reward Model cites Training language models to follow instructions with human feedback
- Safety Alignment of Large Language Models via Contrasting Safe and Harmful Distributions cites Direct Preference Optimization: Your Language Model is Secretly a Reward Model
- Language Models are Few-Shot Learners cites The Curious Case of Neural Text Degeneration
- Training language models to follow instructions with human feedback cites Multitask Prompted Training Enables Zero-Shot Task Generalization
- Training language models to follow instructions with human feedback cites Language Models are Few-Shot Learners
Cited by top-tier papers3
- T-POP: Test-Time Personalization with Online Preference FeedbackZikun Qu, Min Zhang, Mingze Kong, Xiang Li et al.ICML 2026 · 4 citations
- Safety Alignment of Large Language Models via Contrasting Safe and Harmful DistributionsXiaoyun Zhang, Zhengyue Zhao, Wenxuan Shi, Kaidi Xu et al.AAAI 2026 · 4 citations
- DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary BanditsArgyrios Gerogiannis, Yu-Han Huang, Subhonmesh Bose, Venugopal VeeravalliICML 2026
Builds on18
- Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
- Training language models to follow instructions with human feedbackLong Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida et al.NeurIPS 2022 · 24,707 citations
- Direct Preference Optimization: Your Language Model is Secretly a Reward ModelRafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D. Manning et al.NeurIPS 2023 · 10,924 citations
- The Curious Case of Neural Text DegenerationAri Holtzman, Jan Buys, Li Du, Maxwell Forbes et al.ICLR 2020 · 4,112 citations
- Multitask Prompted Training Enables Zero-Shot Task GeneralizationVictor Sanh, Albert Webson, Colin Raffel, Stephen H. Bach et al.ICLR 2022 · 1,976 citations
Related papers
- TokenTiming: A Dynamic Alignment Method for Universal Speculative Decoding Model PairsSibo Xiao, Jinyuan Fu, Zhongle Xie, Lidan ShouACL 2026
- Achieving Nearly-Optimal Regret and Sample Complexity in Dueling Bandits with Applications in Online RecommendationsLanjihong Ma, Yao-Xiang Ding, Zhen-Yu Zhang, Zhi-Hua ZhouKDD 2025
- Large Language Model-Enhanced Multi-Armed BanditsJiahang Sun, Zhiyong Wang, Runhan Yang, Chenjun Xiao et al.ACL 2026 · 6 citations
- BanditSpec: Adaptive Speculative Decoding via Bandit AlgorithmsYunlong Hou, Fengzhuo Zhang, Cunxiao Du, Xuan Zhang et al.ICML 2025
- Beyond task diversity: provable representation transfer for sequential multitask linear banditsThang Duong, Zhi Wang, Chicheng ZhangNeurIPS 2024 · 3 citations
