Tokenized Bandit for LLM Decoding and Alignment

Suho Shin, Chenghao Yang, Haifeng Xu, MohammadTaghi Hajiaghayi

Introduction

Large Language Models (LLMs) have demonstrated remarkable capabilities, yet aligning their outputs with human preferences remains a significant challenge. Traditional methods like Reinforcement Learning from Human Feedback (RLHF) require substantial computational resources for fine-tuning. An emerging alternative is decoding-time alignment, which steers model outputs during the inference phase. However, this approach has historically lacked a rigorous theoretical foundation.

In the paper "Tokenized Bandit for LLM Decoding and Alignment," the authors introduce a novel mathematical framework that treats LLM generation as a sequential decision-making problem under uncertainty. By formalizing this process as a "Tokenized Bandit," the research provides the first regret bounds for decoding-time alignment and offers a theoretical justification for the empirical success of greedy decoding.

The Tokenized Bandit Framework

In standard Multi-Armed Bandit (MAB) theory, an agent selects an action and receives a reward. Applying this directly to LLMs is problematic because the "action" is an entire sequence of tokens. If every possible sentence is treated as an independent arm, the action space grows exponentially ($n^L$, where $n$ is the vocabulary size and $L$ is the sequence length), making efficient learning impossible.

Furthermore, LLM generation is irrevocable: once a token is generated, it cannot be changed. A single suboptimal choice at the beginning of a sequence can drastically alter the final utility. To address these challenges, the authors propose two variants:

  1. Tokenized Linear Bandit (TLB): Assumes the utility of a sequence is a linear function of its embedding, leveraging the "Linear Representation Hypothesis"—the idea that high-level concepts are encoded as linear directions in the model's latent space.
  2. Tokenized Multi-Armed Bandit (TMAB): A more general framework where the utility function is arbitrary, though the context remains fixed.

The DDMC Assumption

To overcome the exponential complexity of the sequence space, the authors introduce a critical structural assumption: Diminishing Distance with More Commons (DDMC).

DDMC posits that if two sequences share a common suffix, the distance between their perceived utilities should shrink as the length of that common suffix increases. Intuitively, this suggests that as a sentence nears completion, the specific tokens chosen at the very beginning matter less to the final semantic "meaning" or utility than the coherence of the concluding tokens. This assumption provides the necessary structure to make learning tractable, preventing the "impossible" barrier where any algorithm would suffer exponential regret.

Algorithms for Alignment

The paper introduces two primary algorithms designed to learn user preferences from feedback during the decoding process:

  • EOFUL (Excessive Optimism under the Face of Uncertainty): Tailored for the TLB setting, EOFUL combines the principles of LinUCB with greedy decoding. It maintains a confidence ellipsoid of possible reward parameters and selects tokens that maximize the "best-case" potential utility.
  • GreedyETC (Exploration-Then-Commit): Designed for the TMAB setting, this algorithm explores various token paths for a predetermined number of rounds before committing to the most promising paths based on accumulated feedback.

Key Insights and Results

The Optimality of Greedy Decoding

One of the most significant theoretical contributions of the paper is the justification for greedy decoding. Under the DDMC assumption, the authors prove that a simple greedy strategy is near-optimal for alignment. This explains why LLMs often perform exceptionally well using greedy search or low-temperature sampling, rather than requiring computationally expensive search strategies like Beam Search.

Theoretical Efficiency

The authors demonstrate that the EOFUL algorithm achieves a sublinear regret bound of $\tilde{O}(L\sqrt{dT})$. This indicates that the algorithm can efficiently learn the optimal alignment strategy over time, with the error rate diminishing as more feedback is collected.

Empirical Validation

The researchers validated the DDMC assumption using real-world data from Llama-3-8B-Instruct. By analyzing embeddings across datasets such as TruthfulQA (measuring truthfulness) and HH-RLHF (Helpful and Harmless preferences), they confirmed that the "distance gap" between sequences indeed shrinks as they share more common suffixes. In synthetic alignment tests, EOFUL significantly outperformed standard "Misaligned Greedy" decoding, effectively converging to the performance of an "Optimal Greedy" agent after a few thousand rounds of interaction.

Limitations and Future Directions

While the framework provides a robust foundation, several areas remain for future exploration:

  • Contextual Diversity: The current TMAB analysis assumes a fixed context; extending this to handle rapidly changing prompts without the linear assumption is a key challenge.
  • Computational Overhead: EOFUL requires multiple embedding function calls per token, which may be intensive for models with very large vocabularies.
  • KL-Divergence Constraints: Standard RLHF often includes a KL-divergence penalty to prevent the model from drifting too far from its base distribution. Integrating these constraints into the Tokenized Bandit framework is a logical next step.

Conclusion

By bridging the gap between bandit theory and LLM decoding, "Tokenized Bandit for LLM Decoding and Alignment" provides a rigorous path forward for efficient, inference-time alignment. The introduction of the DDMC assumption not only makes the problem mathematically tractable but also sheds light on why simple decoding strategies are so effective in practice.

Summary updated

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.
BibTeX
@inproceedings{shin2025tokenized,
  author = {Suho Shin and Chenghao Yang and Haifeng Xu and MohammadTaghi Hajiaghayi},
  title = {{Tokenized Bandit for LLM Decoding and Alignment}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=TFXxarWZzv},
}
Figure