Research map / Bandits and online learning / Multi-armed bandits
Tokenized Bandit for LLM Decoding and Alignment
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Frames LLM decoding and decoding-time alignment as tokenized linear and multi-armed bandits, and gives sublinear-regret algorithms (EOFUL, GreedyETC) under a diminishing-distance-with-more-commons assumption.
Problem
Online token-by-token LLM decoding and decoding-time alignment with user feedback, where the utility of a whole generated sequence is only observed at the end and learning without structure is impossible.
Approach
Model sequence generation as a bandit problem with irrevocable token choices; introduce the DDMC assumption (utility gap shrinks when identical tokens are appended), enabling EOFUL (greedy decoding with LinUCB-style optimism) for linear utilities and GreedyETC (explore-then-commit per level) for arbitrary utilities, and show greedy decoding is near-optimal under DDMC.
Key results
- Proves regret O(L sqrt(dT log T)) for EOFUL under linear realizability plus DDMC and O(nL T^{2/3} (log T)^{1/3}) for GreedyETC on TMAB.
- Shows any algorithm suffers Omega(T(1-1/2^{L-2})) regret for TLB and Omega(min(sqrt(n^L T), T)) for TMAB without structure.
- Empirically, the average distance gap decreases as the number of common suffix tokens grows on TruthfulQA and HH-RLHF, and the EOFUL ratio check stays below 1.25.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EOFUL for decoding-time alignment instead of misaligned greedy decoding | Synthetic LLM alignment · Synthetic LLM alignment | regret | Helped |
| Add common suffix tokens when comparing sequence pairs | TruthfulQA and HH-RLHF · TruthfulQA and HH-RLHF | sequence distance gap | Helped |
| Use HH-RLHF sequences rather than TruthfulQA sequences | DDMC validation · HH-RLHF vs TruthfulQA | decrease in distance gap with more common suffix tokens | Mixed |
| Use EOFUL rather than the optimal-greedy baseline | Synthetic LLM alignment · Round t=1 sample | utility: -1.36 -> -26.64 | Hurt |
| Use EOFUL rather than the optimal-greedy baseline | Synthetic LLM alignment · Round t=2 sample | utility: 3.30 -> -17.48 | Hurt |
| Use EOFUL rather than the optimal-greedy baseline | Synthetic LLM alignment · Round t=9999 sample | utility: -2.99 -> -1.57 | Helped |
| Use EOFUL rather than the optimal-greedy baseline | Synthetic LLM alignment · Round t=10000 sample | utility: 22.87 -> 28.34 | Helped |
| Use EOFUL rather than Misaligned greedy | Synthetic LLM alignment · Round t=10000 sample | utility: 2.68 -> 28.34 | Helped |
| Use EOFUL with the tested embedding setup | EOFUL assumption validation · Synthetic LLM alignment | maximum embedding-norm ratio: 1.25 | No clear effect |
Surprising findings
- EOFUL sometimes achieves higher utility than the optimal greedy baseline, suggesting greedy decoding is not always optimal in practice.
- Greedy decoding is shown to be (almost) optimal under DDMC, yet the paper notes sampling methods often outperform greedy on open-ended tasks.
Limitations
- DDMC is an assumption that may not hold for all LLMs; empirical checks are only averaged.
- Requires linear realizability and an extra technical assumption for TLB; experiments use top-k truncation and a synthetic utility.
- Regret bounds are linear in depth L and EOFUL showed slow convergence and degenerate outputs in experiments.
Experimental setup
Datasets: TruthfulQA HH-RLHF synthetic queries generated from templates and interest lists (1000 queries)
Benchmarks: TruthfulQA HH-RLHF synthetic regret experiments
Metrics: regret average distance gap by number of common suffix tokens utility
Baselines: WrongTheta Misaligned greedy theoretical regret upper bound
Builds on: LinUCB OFUL exploration-then-commit lookahead decoding
Closest papers by meaning
- Not-a-Bandit: Provably No-Regret Drafter Selection in Speculative Decoding for LLMs (ICLR 2026 · similarity 0.89)
- BanditSpec: Adaptive Speculative Decoding via Bandit Algorithms (ICML 2025 · similarity 0.87)
- Sample Smart, Not Hard: Correctness-First Decoding for Better Reasoning in LLMs (ICLR 2026 · similarity 0.87)
- Optimized Multi-Token Joint Decoding With Auxiliary Model for LLM Inference (ICLR 2025 · similarity 0.87)
- Judge Decoding: Faster Speculative Sampling Requires Going Beyond Model Alignment (ICLR 2025 · similarity 0.86)
- Collab: Controlled Decoding using Mixture of Agents for LLM Alignment (ICLR 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.