Local and Global Decoding in Text Generation (2024)

Abstract: Text generation, a component in applications such as dialogue systems, relies heavily on decoding algorithms that sample strings from a language model distribution. Traditional methods like top- k and top- \pi decoding locally normalise the model’s output, which can significantly distort the original distribution. In this paper, we investigate the effects of such distortions by introducing globally-normalised versions of these decoding methods. Further, we propose an independent Metropolis-Hastings (IMH) algorithm to approximate sampling from these globally-normalised distributions without explicitly computing them. Our empirical analyses compare the performance of local and global decoding across two algorithms (top- k and top- \pi ) with various hyperparameters, using the Pythia language models. Results show that in most configuration, global decoding performs worse than the local decoding versions of the same algorithms, despite preserving the distribution’s integrity. Our results thus suggest that distortion might be an important feature of local decoding algorithms.

## introduction text generation is increasingly used in everyday applications, serving as a key component in dialogue agents like gpt-4 (openai et al., 2024). given a pre-trained language model (lm), text generation typically involves using decoding algorithms, 1 which extract a string w from a language model p θ . in open-ended text generation, these algorithms are usually stochastic, allowing users to sample strings. importantly, the goal of text generation is to produce high-quality strings, and a string's quality does not necessarily align with the probability mass assigned to it by a model (holtzman et al., 2020; zhang et al., 2021; meister et al., 2022). @xcite see welleck et al. (2024) for a review. for this model, the probability of ab is higher than ba; however, the opposite is true for local decoding. in this example, top-k is 2 and maximum lengths are @xmath0. over recent years, several decoding algorithms have been proposed (e.g., top-k, top-π; fan et al., 2018; holtzman et al., 2020; basu et al., 2021; hewitt et al., 2022; meister et al., 2023b). most of these methods operate in two steps: (i) they first prune the model's output, assigning zero probability to a large set of strings, and (ii) they then sample from this pruned distribution. however, before sampling, the distribution must be renormalised, i.e., its values must be adjusted to sum to one. this renormalisation is typically performed locally for each context, meaning that each conditional p θ (• | @xmath1; a process known as local normalisation. importantly, by renormalising contexts independently, local normalisation can distort distribution p θ (see fig. 1 ). this paper explores the effects of such distortion on decoding algorithms. specifically, we propose globally-normalised versions of classical decoding methods such as top-k and top-π. globallynormalised methods prune the model's output identically to the locally-normalised version. however, instead of renormalising each context separately, they normalise the entire distribution p θ (•) at once; a process known as global normalisation. unlike local normalisation, global normalisation does not distort the distribution, allowing us to examine how distortion affects decoding performance. however, global normalisation is generally intractable as it requires computing a sum over an infinite set of strings. to address this issue, we use a markov chain monte carlo (mcmc) method to sample strings, adapting the independent metropolis-hastings (imh) algorithm to the decoding setting. as imh only requires unnormalised probabilities, this method allows us to approximately sample from the globally-normalised distribution without explicitly computing it. in our experiments, we compare locally and globally normalised versions of two decoding algorithms: top-k and top-π. we run these algorithms on pythia models (ranging from 70m to 2.8b in size) with several hyperparameter configurations (8 settings for each algorithm; with k spanning from 5 to 10,000 and π from 0.01 to 0.99). our results show that globally-normalised methods generally perform worse than their locally-normalised counterparts, as evaluated by mauve scores. additionally, our results suggest that local normalisation leads to longer, less repetitive and overall higher-quality text. we conclude that the distortion introduced by local decoding is an important component contributing to its performance. ## language modelling a language model, denoted as p θ (w) with parameters θ, defines a probability distribution over the set of all finite strings @xmath2, w 2 , . . . , w |w| ⟩ ∈ σ * , where σ represents an alphabet of subword units. these models are generally defined autoregressively as: here, w |w|+1 represents a special end-of-sequence symbol (eos / ∈ σ). while p θ (w) represents a global distribution over σ * , the conditionals p θ (w t | @xmath3. importantly, sampling from p θ (w) is straightforward, as it reduces to sampling iteratively from p θ (w t | @xmath4. in practice, users of language models typically impose a maximum string length t to constrain the output of p θ . to facilitate the upcoming discussion, we formally define such t -maxlength language models here. definition 1. a t -maxlength language model is a lm for which any string w longer than t has a probability of zero. formally: this implies that for any t -length prefix @xmath5, p θ (eos | @xmath6. ## decoding algorithms in this section, we first introduce both local and global decoding algorithms. we then discuss how these distributions compare to each other. ## sampling strings with independent metropolis-hastings as noted in our introduction, sampling strings directly from p γ (w) is generally intractable. however, given access to the unnormalised p u (w), markov chain monte carlo algorithms allow us to approximate this sampling process. several such methods exist in the controllable text generation literature (miao et al., 2019; amini et al., 2023; forristal et al., 2023; lew et al., 2023; du et al., 2024, inter alia). @xcite here, we propose a new approach based on independent metropolis-hastings. the method proceeds as follows: we first sample an initial string w (1) from a proposal distribution p imh (w). then, over n iterations, we sample new proposal strings w ′ ∼ p imh (w) and decide whether to accept the new string based on an accept-reject distribution p imh (✓ | w ′ , w (n-1) ). these steps are summarised in the following equations: finally, we take string w (n +1) as our sample. notably, if we define the accept-reject distribution as: we present a pseudo-code of this method in fig. 2 . ## main results in this section, we present and analyse our results. first, we evaluate locally and globally decoded text using mauve and self-bleu metrics. next, we examine the distortion caused by local normalisation and assess the impact of using imh to sample from globally-normalised distributions. lastly, we provide a qualitative analysis of the generated text. ## discussion: why local decoding outperforms global decoding? interestingly, despite the theoretical advantages of global decoding, local decoding consistently outperforms it in most scenarios. we now propose three key reasons for this discrepancy. first, sequences generated through global decoding tend to be shorter on average (see fig. 7 ). as probabilities compound multiplicatively over the length of a sequence, and are constrained to values no greater than one, the overall probability of longer sequences decreases exponentially. in contrast, local normalisation constants (used to normalise contextual probabilities in local decoding) are at least one. when compounded, they can thus lead to exponentially higher probabilities for longer sequences under p α . as a result, local decoding thus tends to favour longer sequences when compared to global decoding. second, global decoding suffers from the wellknown probability-quality paradox in text generation (holtzman et al., 2020; zhang et al., 2021; meister et al., 2022). this paradox states that the most likely sequences according to a language model are not always the highest quality ones. in fact, high-probability sequences frequently include repetitive or incoherent content. prior research has shown, for instance, that maximising likelihood during decoding, such as in beam search, often leads to degenerate and repetitive outputs (holtz-man et al., 2020). in contrast, stochastic methods like top-π sampling produce more diverse, humanlike text (meister et al., 2022). similarly, stahlberg and byrne (2019) show that beam search often does not return the most likely string under a language model, and that these "search errors" improve its generated text quality. these findings align with our results, which show that global decoding-by assigning higher probability to sequences which are already likely under the original model-tends to generate less coherent and lower-quality text. @xcite lastly, language models often allocate significant probability mass to repetitive sequences. even under local decoding, small values of k can cause the model to get stuck in repetitive loops. these loops typically have high local normalisation constants, as the repetitive continuations tend to be high probability and are often included top-k set (i.e., in d @xmath7. in such cases, local decoding effectively discounts these sequences by adjusting their probabilities. in contrast, global decoding does not apply this discount, giving these repetitive sequences a higher chance of being sampled. this results in less coherent and more repetitive text under global normalisation. figure 9 : log-likelihood of globally decoded samples under the local decoding distribution p α . we sample sequences as: w ∼ p γ (w). we then evaluate their log-probabilities as: log p α (w). results are averaged over 10 runs. ## conclusion in this paper, we explored the effects of local and global normalisation on text generation quality, focusing on two popular decoding methods: top-k and top-π. we introduced the concept of global decoding algorithms and adapted local decoding algorithms to their global counterparts. our empirical comparison revealed that, while global decoding preserves the original distribution, it often produces shorter, less coherent and more repetitive text than local decoding. in contrast, local decoding-despite introducing distortions to the original distribution-typically results in more coherent text. our findings thus suggest that the distortion introduced by local decoding algorithms might be a beneficial feature rather than a flaw. future research on decoding algorithms should explore and evaluate the effects of local normalisation alongside pruning strategies.