A Frustratingly Simple Decoding Method for
Neural Text Generation

The most traditional LM is the $n$-gram model, which relies on the Markov assumption  Jurafsky and Martin (2009). In an $n$-gram LM, the probability of the $i$-th token only depends on the previous $n-1$ tokens, expressed as $p(x_{i}|x_{<i})=p_{n}(x_{i}|x_{i-n+1:i-1})$. This probability can be computed by evaluating the relative frequency counts within a training corpus:

where $C(\cdot)$ counts the number of occurrences of the input sequence within the training corpus. In practice, the probability distributions are often smoothed to improve the model’s generalizability. For example, the interpolation of $n$-gram models of different orders can help prevent the LM from assigning zero probability to unseen sequences Tonella et al. (2014).

With the rise of deep learning, $n$-gram LMs have been largely superseded by neural networks, for example, the GPT family Radford et al. (2019); Brown et al. (2020) and the LLaMA family Touvron et al. (2023a, b). These models are trained to predict the next token by conditioning on the preceding context: $\mathcal{L}_{\theta}=-\sum_{i=1}^{t}\log p_{\theta}(x_{i}|x_{<i})$, where $\theta$ denotes the model parameters. With the capabilities acquired by large-scale pre-training, these neural LMs can be readily applied to text generation Liu et al. (2022).

Given an input prompt $x_{1:l}$, the $n$-gram LM is constructed and updated as follows. Initially, the prompt $x_{1:l}$ is split into $n$-grams. These $n$-grams can be stored as a set of key-value pairs $\mathcal{D}_{n}$. For each $n$-gram $x_{i-n+1:i}$, the key is the first $n-1$ tokens $x_{i-n+1:i-1}$ and the value is the last token $x_{i}$. After generating each new token, we update $\mathcal{D}_{n}$ to include the new $n$-gram composed by the last $n$ tokens in the sequence.

To calculate next-token probabilities, we use the last $n-1$ tokens in the sequence as the query. We first identify all key-value pairs in $\mathcal{D}_{n}$ whose key precisely matches the query and then compute the probabilities according to Eq. 1. All of the above operations introduce little computational overhead compared to the running of the original neural LM.

An ordinary $n$-gram model cannot penalize the $m(m<n)$-gram repetitions. Inspired by two common smoothing techniques in modern $n$-gram models, back-off and interpolation Jurafsky and Martin (2009), we combine $n$-gram models with different orders from $n=1$ to $N$ ($N$ being the highest order). The result is a smoothed $n$-gram model $\hat{p}$:

where $\lambda_{n}$ is the weight of $p_{n}$ and $\sum_{n=1}^{N}\lambda_{n}=1$. The detailed process is elaborated in Alg. 1. In brief, we enumerate $n$-gram models from $n=N$ to $n=1$, setting $\lambda_{n}$ to decrease exponentially with a decay factor $\beta=0.9$, thus assigning greater weights to higher-order sub-models. The construction and update of the smoothed $n$-gram LM are straightforward; We only need to maintain $N$ copies of key-value pairs ($\mathcal{D}_{1},\mathcal{D}_{2},\ldots,\mathcal{D}_{N}$) separately.

Following previous works Su et al. (2022); Li et al. (2023a); Lan et al. (2022), we compare FSD and existing decoding methods on three English benchmarks. That is, wikinews¹¹1http://www.wikinews.org in the news domain, wikitext-103 Merity et al. (2017) in the Wikipedia domain and bookcorpus Zhu et al. (2015) in the story domain. For each test case, the first 32 tokens are used as the prompt and the task is to generate the following 256 tokens. We test three off-the-shelf LMs of different scales: OPT-6.7b Zhang et al. (2022), GPT2-XL, and GPT2-Medium Radford et al. (2019). The amateur LM used in CD is OPT-125m for OPT-6.7b and GPT2 for GPT2-XL and GPT2-Medium.

For automatic evaluation, we report three metrics assessing different aspects of the generations:

• •

  Diversity measures the degree of repetition at different $n$-gram levels. The calculation can be expressed as $\prod\limits_{n=2}^{4}(1-\texttt{REP}_{n})$, where $\texttt{REP}_{n}=(1-\frac{\#\texttt{unique n-grams}(\hat{\textbf{x}})}{\#\texttt{total n-grams}(\hat{\textbf{x}})})$. $\hat{\textbf{x}}$ is the generated continuation. A higher diversity score indicates that generated outputs contain fewer repetitive segments.

• •

  MAUVE Pillutla et al. (2021) measures the distribution similarity between the generated texts and reference texts.

• •

  Coherence Su et al. (2022) is defined as the cosine similarity between the embeddings of the prompt $\mathbf{x}$ and the generated continuation $\hat{\mathbf{x}}$: $\texttt{COH}=\frac{f(\mathbf{x})f(\hat{\mathbf{x}})}{\left\|f(\mathbf{x})\right\|\left\|f(\hat{\mathbf{x}})\right\|}$, where $f$ is the SimCSE Gao et al. (2021) sentence embedding function.

For human evaluation, we conduct blind A/B tests with the help of proficient English speakers from a third-party grading platform. In the process of annotation, annotators are asked to compare two continuations of the same prompt and decide which one is better (or two are equally good/bad) by jointly considering fluency, coherence, and commonsense. Each case is rated by three annotators and we use majority vote.

For clarity, the variant of FSD using the vectorized $n$-gram model is named as FSD-vec. We set $n$ to 3 and 2 for FSD and FSD-vec respectively and $k$ to 6 for both variants. Based on our preliminary experiments, the penalty strength $\alpha$ is set to 3 and 1 for FSD and FSD-vec respectively. We find this setting is quite robust and generalizes well to different scenarios.

To show the superior performance of FSD/FSD-vec, we mainly compared it with two recent search-based decoding methods, CD Li et al. (2023a) and CS Su et al. (2022), since they were reported to outperform other existing decoding methods.²²2We omit greedy and beam search due to space limitation. The text generated by these two methods is very repetitive and of low quality Li et al. (2023a). We follow the suggested hyper-parameter settings from their respective papers. We also compare with top-$p$ sampling Holtzman et al. (2020) because it is the most popular decoding method for open-ended text generation. We also include the results of typical sampling Meister et al. (2022). We set $p$ in top-$p$ sampling and typical sampling to $0.95$, as adopted by Li et al. (2023a).

For automatic metrics, we believe that results closer to human are better because a higher score does not always indicate a better generation. For example, a random token sequence would obtain an extremely high diversity score, and a continuation identical to the input prompt would get a full coherence score. This is also commonly adopted in previous works Holtzman et al. (2020); Meister et al. (2022); Xu et al. (2022). Therefore, we highlight the results that are closest to human in our experiments. From Table 1, we can observe that:

• •

  For diversity (div), FSD/FSD-vec matches or outperforms all other decoding baselines in six/five out of nine settings (the combinations of three LMs and three domains). In cases where FSD and FSD-vec are not the best, the gaps between them and the best scores are minimal ($<$ 0.03). It is worth noting that recent state-of-the-art methods (CD and CS) are very sensitive to the choices of the LMs. For example, CS fails to achieve reasonable diversity scores on all three benchmarks when using GPT2-Medium. The reason is that CS relies on the isotropy of the LM’s latent space and GPT2-Medium may not fulfill this requirement. The diversity scores of CD also decrease significantly as the LM switches from GPT2-XL to GPT2-Medium, perhaps because the difference between the LM and its amateur is not sufficiently indicative of degeneration. In contrast, FSD and FSD-vec are much more stable in diversity. We attribute the success to that the operations of the anti-LM in FSD are relatively independent to the choice of the LM.

• •

  For coherence (coh), FSD/FSD-vec achieves the best coherence scores in seven/four out of nine settings. These results emphasize the effectiveness of FSD and FSD-vec in generating coherent and contextually-appropriate continuations. We can see that sampling-based methods (top-$p$ and typical sampling) often deliver lower coherence scores than search-based methods (CS and CD). This confirms that sampling-based methods produce lexically diverse text at the expense of topic drift. Importantly, FSD and FSD-vec often attain better diversity and better coherence at the same time, suggesting our methods provide a better trade-off between diversity and coherence.

• •

  For MAUVE (mau), sampling-based methods (particularly top-$p$ sampling) are generally better than search-based methods (CS, CD, FSD, and FSD-vec) though the gaps are often very small. However, it has been reported that the generation quality of CS and CD is better according to human evaluation. This indicates that MAUVE may not be a reliable metric which is also pointed out by Su and Xu (2022). Therefore, we turn to extensive human evaluation.

For human evaluation, we randomly select 100 prompts from each of the three benchmarks. We first compare FSD against top-$p$ sampling and two recent state-of-the-art methods, CS and CD. The results are shown in Table 2. We can see that on average across settings, annotators prefer FSD 1.30x more than CD, 1.26x more than top-$p$ sampling and 1.14x more than CS. FSD wins all the comparisons with the only exception: FSD vs CS on book. The results show that CS is the most competitive method, we then turn to compare FSD-vec with CS and FSD. As shown in Table 3, FSD-vec wins all the comparisons against CS and is preferred 1.49x more than CS. The quality of FSD-vec is on par with FSD.

We find that, compared with CS, FSD is less likely to generate continuations that deviate from the topic. Table 4 shows two continuations from CS and FSD respectively. The prefix’s topic is “a musician is considering running for presidency”. But the topic of CS’s output is concert tours which is irrelevant to that of the prefix. It may be because CS tends to excessively penalize tokens in comparison to FSD. For instance, CS has the potential to penalize tokens that have never occurred in the preceding context, as long as they produce similar hidden states. In contrast, FSD only penalizes tokens that appear in the context and genuinely result in repetitions.

Next, we investigate the robustness of our methods in addressing the degeneration issue under different generation lengths. In Figure 2, we present the diversity scores of FSD, FSD-vec, CS and CD when the generation length is 256, 512 and 768. As seen, the diversity of human-generated text is most stable across different lengths. The diversity of CS and CD drops dramatically as the generation length increases, resulting in a progressively larger disparity between the generated text and human-generated text. In contrast, FSD has the smallest slope and FSD-vec exhibits a similar slope to FSD from 256 to 512, and slightly steeper from 512 to 768. It reveals that our method is much more robust in reducing repetitions in longer sequence generation.

So far, our evaluation has been primarily focused on English corpora, and the types of LMs used are also limited. We here expand our evaluation to include other non-English languages using various LMs. We conduct experiments on four datasets, chinese-wiki ³³3https://github.com/SigmaQuan/Awesome-Chinese-Corpus-Datasets-and-Models, japanese-news ⁴⁴4https://www.kaggle.com/datasets/tanreinama/japanese-fakenews-dataset, german-wiki, and french-wiki ⁵⁵5https://huggingface.co/datasets/wikipedia. We adopt a variety of popular LMs, including BLOOM-7b BigScience (2023), LLaMA-7b Touvron et al. (2023a), OPT-6.7b Zhang et al. (2022). The evaluation results are shown in Table 5, where also report the results of the state-of-the-art decoding methods, CS and top-$p$ (the missing positions indicate the LM does not support the language.). As seen, FSD and FSD-vec generally outperform CS and top-$p$ (most of the boldfaced numbers are from FSD and FSD-vec.). It should be noted that for BLOOM-7b, CS does not work entirely in all four languages (see the extremely low diversity scores). Additionally, the performance of CS also exhibits greater sensitivity to different languages. For instance, when applied to the japanese dataset using OPT, the diversity and MAUVE scores are notably low. In contrast, FSD and FSD-vec deliver much more stable performance across different settings, indicating FSD/FSD-vec can be a universal choice for open-ended text generation.

The latest generation of LLMs such as ChatGPT OpenAI (2022) and LLaMA-2-chat Touvron et al. (2023b) have the capabilities to perform various tasks by following natural language instructions. This instruction-following approach has become the standard form for harnessing LLMs. Therefore, we compare FSD/FSD-vec against baselines within this context. Specifically, we follow the widely accepted comparison setting  Li et al. (2023b), i.e., reporting the win rates against text-davinci-003 on the alpaca_eval dataset⁶⁶6https://huggingface.co/datasets/tatsu-lab/alpaca_eval with the help of GPT-4 OpenAI (2023). We adopt the LLaMA-2-7b-chat model Touvron et al. (2023b) since it is among the most popular instruction-tuned models. The results of different decoding methods are shown in Table 7. The results clearly indicate that FSD/FSD-vec outperforms the baselines, thus further validating the effectiveness of our approach.

So far, our evaluation has been focused on open-ended text generation and general-purpose instruction following. We also evaluate our methods on a specific, close-ended generation task: summarization. We use the XSum dataset Narayan et al. (2018). As shown in Table 6, FSD/FSD-vec is generally better than other baselines. It showcases that our methods can also work well in close-ended scenarios.

We first study the effect of the penalty strength $\alpha$. We present the results in Table 8. We notice that as $\alpha$ increases, the div score consistently increases. This is an expected outcome, as a larger $\alpha$ imposes a greater penalty on repetitive content, thereby promoting increased diversity in the model’s outputs. The coh score demonstrates a decreasing trend. The reason is that penalizing the most probable tokens may damage the coherence between the prefix and the continuation. Consequently, we see that the mauve score initially shows an upward trend and then experiences a slight decrease.

We study the effect of the hyperparameter $n$ as shown in Table 9. We can observe that diversity and coherence are very stable for different $n$, when $n>3$, the mauve begins to decrease.

We investigate the impact of the hyperparameter $k$, as presented in Table 10. When $k$ is assigned a minimal value, a notably lower diversity (div) is observed. This can be attributed to the reduced search space associated with a smaller $k$, which consequently constrains the diversity of generated outcomes. Conversely, upon incrementing $k$ past a specific threshold, all evaluated metrics—diversity, mauve, and coherence—demonstrate substantial stability, with only negligible fluctuations observed. This stability suggests that the effective selection space of FSD predominantly comprises a limited number of top tokens.

Despite that the hyperparameters can take different values, we recommend using the default settings of those hyperparameters and only adjusting $\alpha$ to suit different tasks.