Language Model Decoding as Likelihood–Utility Alignment (2023)

Abstract: A critical component of a successful language generation pipeline is the decoding algorithm. However, the general principles that should guide the choice of a decoding algorithm remain unclear. Previous works only compare decoding algorithms in narrow scenarios, and their findings do not generalize across tasks. We argue that the misalignment between the model’s likelihood and the task-specific notion of utility is the key factor in understanding the effectiveness of decoding algorithms. To structure the discussion, we introduce a taxonomy of misalignment mitigation strategies (MMSs), providing a unifying view of decoding as a tool for alignment. The MMS taxonomy groups decoding algorithms based on their implicit assumptions about likelihood–utility misalignment, yielding general statements about their applicability across tasks. Specifically, by analyzing the correlation between the likelihood and the utility of predictions across a diverse set of tasks, we provide empirical evidence supporting the proposed taxonomy and a set of principles to structure reasoning when choosing a decoding algorithm. Crucially, our analysis is the first to relate likelihood-based decoding algorithms with algorithms that rely on external information, such as value-guided methods and prompting, and covers the most diverse set of tasks to date. Code, data, and models are available at https://github.com/epfl-dlab/understanding-decoding .

## introduction large transformer-based language models (lms) have been pushing the boundaries on tasks ranging from natural language generation @xcite to information extraction @xcite , theorem proving @xcite , code generation @xcite , and even protein generation @xcite . at inference time, these models rely on a decoding algorithm to generate an output. the goal of decoding algorithms is to select an output of high utility from input what is the shortest name of a us president? ..… training corpus text scraped from the web before 2021 ja jo … john joe … ..… … james … ..… ..… ja 0.5 mes 0.5 jo 0.4 hn 0.8 e 0.1 0.25 0.32 0.04 greedy beam search (2 beams) highest utility imagine a fictional lm trained before joe biden became the us president. the input asks for the shortest name of a us president. after joe biden's inauguration, this is 'joe', but before, it was 'john'. greedy search returns 'james' since its first token 'ja' has the highest likelihood. beam search manages to find the highest likelihood sequence 'john'. both fail to find the correct answer 'joe' with the highest utility since 'joe' has a very low likelihood. the exponentially large output space. in contrast to the generic language modeling training objective, which is based on the data likelihood, the notion of utility is task-specific. the potential gap between the two can create a misalignment between model likelihood and task utility; see fig. 1 for an illustration of this concept. indeed, across different tasks, researchers noticed that high likelihood is often not associated with desired properties of the output @xcite @xcite . naturally, this has led to the development of decoding strategies aimed at mitigating this problem. in the context of natural language generation (nlg), nucleus sampling (i.e., top-p) @xcite has been proposed to avoid dull or degenerate text. similarly, in the context of machine translation (mt), solutions ranging from simple ad-hoc tweaks like enforcing a minimal sequence length @xcite to leveraging a value model to directly optimize for utility in @xcite have been developed. these methods for alignment are task-specific and have been tested only in narrow domains, making it difficult for practitioners to compare them. recently, @xcite and @xcite explored the likelihood-utility misalignment across tasks. however, these studies still largely focus on a group of similar tasks -nlg tasks -and, more crucially, do not include decoding strategies that make use of external sources of information at inference time. therefore, a general framework to structure our thinking about decoding algorithms is still missing. our work makes the first step towards filling this gap. we propose a unified perspective of decoding as a tool for mitigating the likelihood-utility misalignment without modifications to the model. looking at decoding through this functional lens, in sec. 3, we provide a taxonomy of misalignment mitigation strategies (mmss). the taxonomy groups decoding algorithms based on the implicit assumptions about likelihood-utility misalignment that need to hold for them to be effective. equipped with this taxonomy, we conduct a comprehensive empirical analysis in which we choose a representative set of decoding algorithms and a representative set of tasks to cover the relevant types of misalignment. we identify three main sources of misalignment: training imperfections (finite dataset, differentiable surrogate loss), distribution shift, and changes in the model's intended usage, which we call utility drift. then, we measure the likelihood-utility misalignment across tasks (rq1) by estimating: the correlation between likelihood and utility for the generated outputs after decoding (rq1-a) and the correlation between likelihood and utility among candidate outputs explored by the decoding algorithm (rq1-b). we proceed by investigating the benefits of decoding algorithms that leverage external information at inference (rq2). finally, we experiment with large generalist lms (llms) and show that prompting can be seen as means for improving the alignment at inference time (rq3). our experiments reveal that: (i) when no distribution shift or utility drift happens, decoding based solely on the likelihood is enough to provide high utility, i.e., likelihood is a strong predictor of utility. (ii) in such cases, there is no significant difference between different kinds of decoding algorithms, and we would recommend keeping beam search. this work studies the fundamental problem in decoding, which involves a complex interaction between models, tasks, and data. our unifying conceptual framework (the mms taxonomy), accommodating all known decoding algorithms, enables the systematic study of decoding in a considerably broader scope than previously. by sharing the taxonomy and open-sourcing our implementations, we hope to pave the way for a more structured discussion in the future. ## background high utility is the goal. for a task t and input x, the utility function assigns a score u t (y|x) to each element y in the output space y . this score quantifies the goodness, or quality, of the output y with respect to a specific input x. for instance, in translation, the utility quantifies the extent to which the output conveys the same message as the input. for question answering, the utility simply quantifies the correctness of the answer. these task-specific notions of utility are operationalized in the evaluation metrics. the development of evaluation metrics that correlate with the human-defined notion of utility is a very active research area @xcite and beyond the scope of this work. in our analysis, we use the canonical evaluation metric of each task as the utility function. for partiallydecoded sequences, the utility can be approximated using a value function (see sec. 3.3). given some input x, an ideal model would generate the element from the output space corresponding to the highest utility score: argmax @xmath0. unfortunately, most of the practically relevant utility functions are not amenable to optimization, forcing us to work with proxy functions, such as the canonical likelihood. language models. a language model corresponds to a probability distribution p over @xmath1, where y is the set of all sequences that can be constructed using a vocabulary v . in this work, we focus on conditional lms p(•|x). usually, these conditional distributions are modeled autoregressively (parametrized by θ ): the model is trained to maximize the target sequence's conditional log-likelihood with teacher forcing, using the cross-entropy loss l (θ ) = -∑ (x,y)∈d log p θ (y | x), where d is the training corpus @xcite . once an lm is trained, it provides a next-token probability distribution across the output vocabulary. decoding algorithms define how tokens are chosen during generation. ## proposed mms taxonomy in this section, we propose a taxonomy of misalignment mitigation strategies (mmss). this work focuses on decoding-based mmss that mitigate the misalignment without modifying the model. as a primary signal, they rely on the model's likelihood. however, additional components (e.g., value model, knowledge base, etc.) can be leveraged. decoding algorithms, which we define as procedures that take in an input -and potentially some context (e.g., a prompt with a task description or examples) -and return a sequence from the output space, can be seen as specific implementations of an mms. apart from fixing the misalignment problem at inference time, it is also possible to retrain or finetune the model with newly collected data that better reflect the intended utility and target testing distribution. we leave the detailed treatment of this part of the taxonomy for future work. see the limitations section at the end of the writing for further discussion of these alternatives. ## discussion rq1 reveals that decoding based solely on the likelihood gives poor expected utility whenever ds or ud occurs. ds and ud make the likelihood a poor predictor of utility. when only ti is present, these decoding algorithms perform well because the likelihood is a strong predictor of utility. then, in rq2 and rq3, we saw that methods bringing in external information at decoding time manage to effectively solve the likelihood-utility misalignment problem. while finetuning (or retraining) would be an obvious and apparently ideal mms, this is often neither possible nor necessary. indeed, our experiments show that if a value model can be crafted and we can afford the extra compute for the value model calls, then vgbs becomes a strong decoding algorithm capable of fixing misalignment problems at inference time. it is more efficient than mcts and performs better than bs, even if the value model is only a poor approximator of the utility. when crafting a useful value model is difficult (e.g., protein function depends on the 3d structure, which cannot be easily approximated from partial amino-acid sequences), mcts with a large number of simulations with roll-outs can be used to "estimate" one. however, the price to pay is a higher computational cost at inference time. finally, for large, generalist lms, decoding algorithms such as mcts or vgbs are prohibitively expensive due to the high computational cost of each call to the lm. prompting methods combined with greedy or top-p decoding can be considered as a way to leverage external information in the form of few-shots prompts to set the model in a state where the likelihood is better aligned with the utility. our experiments support this explanation of the success of prompting large lms. for a similar perspective, comparing prompting methods with training-based mmss see @xcite .