# Momentum Decoding: Open-ended Text Generation As Graph Exploration

Tian Lan♡, Yixuan Su11footnotemark: 1 Shuhang Liu♡ Heyan Huang♡,♣ Xian-Ling
Mao♡,
♡School of Computer Science and Technology, Beijing Institute of Technology
♣Beijing Engineering Research Center of High Volume Language Information
Processing
and Cloud Computing Applications
lantiangmftby<EMAIL_ADDRESS>The first two authors
contributed equally. Corresponding author.

###### Abstract

Open-ended text generation with autoregressive language models (LMs) is one of
the core tasks in natural language processing. However, maximization-based
decoding methods (e.g., greedy/beam search) often lead to the degeneration
problem, i.e., the generated text is unnatural and contains undesirable
repetitions. Existing solutions to this problem either introduce randomness
prone to incoherence or require a look-ahead mechanism that demands extra
computational overhead. In this study, we formulate open-ended text generation
from a new perspective, i.e., we view it as an exploration process within a
directed graph. Thereby, we understand the phenomenon of degeneration as
circular loops within the directed graph. Based on our formulation, we propose
a novel decoding method—momentum decoding—which encourages the LM to greedily
explore new nodes outside the current graph. Meanwhile, it also allows the LM
to return to the existing nodes with a momentum downgraded by a pre-defined
resistance function. We extensively test our approach on three benchmarks from
different domains through automatic and human evaluations. The results show
that momentum decoding performs comparably with the current state of the art
while enjoying notably improved inference speed and computation FLOPs.
Furthermore, we conduct a detailed analysis to reveal the merits and inner
workings of our approach.111Our codes and other related resources are publicly
available at https://github.com/gmftbyGMFTBY/MomentumDecoding.

##  1 Introduction

Open-ended text generation with autoregressive language models (LMs) is
indispensable in various NLP applications. Typical examples include dialogue
systems Thoppilan et al. (2022); Su et al. (2021b); Rae et al. (2021); Su et
al. (2022c, 2021a), contextual text completion Su et al. (2022b); Radford et
al. (2019), story generation Mostafazadeh et al. (2016); Su et al. (2022a),
etc.

Conventional maximization-based methods for this task, such as greedy search
and beam search, often lead to the degeneration problem Holtzman et al.
(2020), i.e., the generated text is unnatural and contains undesirable
repetitions. Existing solutions for this problem can be divided into two
categories: (1) Stochastic methods, e.g. top-$k$ Fan et al. (2018a) and
nucleus sampling Holtzman et al. (2020), introduce randomness to avoid
undesirable repetitions. However, the intrinsic stochasticity of these
sampling approaches often leads to semantic incoherence and topic drift in the
generated text Basu et al. (2020). (2) Deteriminstic method, i.e., contrastive
search (Su et al., 2022b; Su and Collier, 2022), relies on a one-step look-
ahead mechanism to encourage diverse generations. While obtaining superior
performances, such look-ahead operation demands extra computational overhead.

In this study, we perceive open-ended text generation from a new perspective.
Specifically, we view it as an exploration process within a directed graph.
Therefore, it allows us to formulate the phenomenon of degeneration as
circular loops within the directed graph. In Figure 1, we provide an
illustration in which the LM generates text given a prefix of three tokens,
i.e., $[1,2,3]$, and gets stuck in the circular loops, i.e., repetitions, of
$[2,3,7,8]$. Intuitively, such degeneration can be addressed if the tendency
of the LM to stay in the circular loop can be properly discouraged, therefore
allowing the LM to jump out of the loop at the correct position and produce
text with natural repetitions. Based on this motivation, we propose a novel
decoding method—momentum decoding—which encourages the LM to greedily explore
new nodes outside the current graph. Meanwhile, it also allows the LM to
return to the existing nodes with a momentum downgraded by a pre-defined
resistance function.

Figure 1: An example of the exploration process in the directed graph, where
the prefix contains three tokens $[1,2,3]$. $e_{i}$ denotes the $i$-th
decoding step of the LM. The patterns of repetition/degeneration, i.e.,
$[2,3,7,8]$, are highlighted with red arrows.

Compared with previous methods, we highlight one notable advantage of our
proposed approach. Specifically, it better bridges the gap between the
training and the decoding of the LM. Typically, LMs are trained with the
maximum likelihood estimation (MLE) objective. Thereby, at the decoding stage,
the LM should follow the same objective Zhang et al. (2019) and try to
maximize the likelihood, i.e., probability, of the generated text. However,
simply maximizing the likelihood of generation often leads to degeneration.
Thus, previous solutions, e.g., sampling and contrastive search, propose to
modify the decoding objective at every generation step. In contrast to
previous approaches, our proposed method largely follows the greedy objective
during decoding. It only corrects the generation at the positions where the
symptom of degeneration is clear, e.g., within the circular loops of
$[2,3,7,8]$ in Figure 1. In the experiments (section 4.1), we show that
momentum decoding generates text by following the greedy objective for more
than 70% of the decoding steps.

We comprehensively test our approach on three benchmarks from different
domains. The automatic evaluations (section 4.1) verify that momentum decoding
generates the most diverse outputs while maintaining a high semantic coherence
in the generated text. Moreover, extensive human evaluations (section 4.2)
demonstrate that momentum decoding performs on par with the current state of
the art, i.e., contrastive search, but with 30% of inference speedup and more
than 4$\times$ reduction in computation FLOPs. Lastly, we provide in-depth
analyses of the inner workings of our approach (section 5).

In summary, our contributions are:

  * •

A new perspective for understanding the task of open-ended text generation.

  * •

The proposal of a novel decoding method—momentum decoding—for generative LMs.

  * •

Extensive experiments and in-depth analyses reveal the proposed method’s
merits and advantages.

##  2 Preliminaries

In this work, we study the fundamental technique, i.e., the autoregressive
decoding methods, for open-ended text generation. The autoregressive decoding
method repeatedly predicts and selects the next token $x_{t}$ conditioned on
the previous context $\boldsymbol{x}_{<t}$. So far, there are two types of
methods used for autoregressive decoding, which are (1) deterministic methods
and (2) stochastic methods.

##### Deterministic Methods.

Two widely used deterministic approaches are greedy and beam search, which aim
to select the text continuation with the highest probability based on the
model’s probability distribution. However, solely maximizing the output
probability often leads to dullness Li et al. (2016) and degeneration Fan et
al. (2018b); Holtzman et al. (2020) in the generated text.

To address this problem, contrastive search (Su et al., 2022b) is recently
introduced, which proposes a one-step look-ahead mechanism to select the
diverse tokens, obtaining the new state of the art on various open-ended text
generation benchmarks.

##### Stochastic Methods.

To tackle the degeneration problem, stochastic approaches have been proposed
to sample the next token from the probability distribution
$p_{\theta}(x_{t}|\boldsymbol{x}_{<t})$. To avoid sampling from the unreliable
tail of distribution, Fan et al. proposed top-k sampling which draws sample
from the vocabulary subset $V^{(k)}$ that maximizes $\sum_{v\in
V^{(k)}}p_{\theta}(x_{t}|\boldsymbol{x}_{<t})$. Here, $|V^{(k)}|=k$ and
$\boldsymbol{x}_{<t}$ is the prefix context. Differently, the current state-
of-the-art nucleus sampling Holtzman et al. (2020) draws sample from the
smallest vocabulary subset $U$ with total probability mass above a threshold
$p\in[0,1]$; i.e., $U$ is the smallest vocabulary subset such that $\sum_{v\in
U}p_{\theta}(x_{t}|\boldsymbol{x}_{<t})\geq p$. While the sampling approaches
help to alleviate model degeneration, the intrinsic stochasticity in these
methods often leads to the semantic incoherence and topic drift Basu et al.
(2021).

##  3 Methodology

In this section, we first formulate open-ended text generation as an
exploration process within the directed graph (section 3.1). Then, we
understand the phenomenon of degeneration as circular loops within the
directed graph (section 3.2). Lastly, based on our motivation, we introduce
our solution—momentum decoding—to the degeneration problem (section 3.3).

###  3.1 Open-ended Text Generation as Graph Exploration

We formulate the task of open-ended text generation from a new perspective,
i.e., we view it as an exploration process within a directed graph. As an
example in Figure 1, at the start, the prefix text (i.e., $[1,2,3]$) can be
viewed as a directed graph $G$, which consists of three nodes and two directed
edges. Then, throughout the generation process of the LM, more nodes are
included in the directed graph $G$, e.g., the generated tokens $[4,5,6,7,8]$.
We note that the nodes within the graph could be accessed multiple times
during the generation of the LM. For instance, these nodes might correspond to
frequently mentioned name entities, e.g., the tokens $[2,3]$ in Figure 1.

###  3.2 The Phenomenon of Degeneration

Based on our formulation in section 3.1, we can understand the phenomenon of
degeneration as circular loops within the directed graph. For instance, in
Figure 1, the LM gets stuck in the circular loop of $[2,3,7,8]$, which
corresponds to the degeneration (i.e., invalid repetition). Then, we define
the circular depth of a node (i.e., token) based on the current graph (i.e.,
text sequence). Given the context text $\boldsymbol{x}$ with length $n$ (i.e.
$|\boldsymbol{x}|=n$) and the new token $t$, the circular depth of $t$ with
respect to $\boldsymbol{x}$ is

$d(t;\boldsymbol{x})=\begin{cases}0&\text{if $t\notin\boldsymbol{x}$}\\\
\max_{1\leq i\leq n+1,\textup{s.t.}[\boldsymbol{x}_{(i\rightarrow
n)}:t]\in\boldsymbol{x}}\\{&\\\ \|[\boldsymbol{x}_{(i\rightarrow
n)}:t]\|\\}&\text{if $t\in\boldsymbol{x}$}\\\ \end{cases}$ (1)

where $\boldsymbol{x}_{(i\rightarrow n)}$ denotes the subsequence of
$\boldsymbol{x}$ from its $i$-th token to its $n$-th token, and
$\boldsymbol{x}_{(n+1\rightarrow n)}$ is an empty string $\phi$. The $[:]$
denotes the concatenation operation and $\|\cdot\|$ is the length of the text
sequence.

###  3.3 Momentum Decoding

We propose a novel decoding method—momentum decoding. The basic principle
behind momentum decoding (MD) is straightforward. During generation, MD
encourages the LM to greedily explore new nodes outside the current graph.
Meanwhile, it also allows the LM to return to the existing nodes with a
momentum downgraded by a pre-defined resistance function. Our rationale is to
prevent the LM from generating deep circular loops as such loops often lead to
severe degenerations (Su and Collier, 2022).

Formally, given the prefix text $\boldsymbol{x}_{<t}$, the LM first looks at
the most probable token $\hat{v}$. Here,
$\hat{v}=\operatorname*{arg\,max}_{v\in\mathcal{V}}p_{\theta}(v|\boldsymbol{x}_{<t})$,
where $\mathcal{V}$ is the LM’s vocabulary and
$p_{\theta}(\cdot|\boldsymbol{x}_{<t})$ is the probability distribution
produced by the LM. Then, the selection of the output token $x_{t}$ follows

$x_{t}=\begin{cases}\hat{v}&\text{if $\hat{v}\notin\boldsymbol{x}_{<t}$}\\\
\operatorname*{arg\,max}_{c\in\mathcal{C}^{(k)}}\bigg{\\{}p_{\theta}(c|\boldsymbol{x}_{<t})&\\\
\quad\quad\quad-\alpha\times f(d(c;\boldsymbol{x}_{<t}))\bigg{\\}}&\text{if
$\hat{v}\in\boldsymbol{x}_{<t}$}\\\ \end{cases}$ (2)

where $\mathcal{C}^{(k)}$ is the set of top-$k$ predictions from the LM’s
probability distribution $p_{\theta}(\cdot|\boldsymbol{x}_{<t})$, and $k$ is
typically set as $5$. The function $f(\cdot)$ is a pre-defined resistance
function, and $d(\cdot)$ is defined in Eq. (1). And $\alpha$ is a
hyperparameter that regulates the importance of the two components.

Circular Depth $d(\cdot)$ | Output Resistance $f(d(\cdot))$
---|---
1 | 1.0
2 | 3.0
3 | 4.0
$\geq$4 | 5.0
|

Table 1: Look-up table for the resistance function.

In this work, we design a conceptually simple yet empirically effective form
of $f(\cdot)$. Specifically, $f(\cdot)$ is defined as a look-up table222We
acknowledge that the design of $f(\cdot)$ is very flexible. This study uses a
look-up table for its empirical simplicity and computational efficiency. We
leave the more sophisticated design of $f(\cdot)$ to our future work. as shown
in Table 1. Intuitively, when the candidate $c$ leads to a circular loop in
the existing graph, the deeper the loop is, the more resistance it will
receive from the resistance function. Thereby, the LM is encouraged to jump
out of the loop and explore new nodes outside the current graph.

In Algorithm 1, we illustrate the decoding process of momentum decoding.

1

Input : The LM $\theta$ (e.g. GPT-2); the vocabulary of the LM $\mathcal{V}$;
the prefix text $\boldsymbol{x}$; the maximum generation step $T$.

2 Initialize the directed graph $G$ with the prefix text $\boldsymbol{x}$;

3 for  _step $t=1,...,T$_ do

4 Compute the next token probability $p_{\theta}(\cdot|\boldsymbol{x})$;

5 Get the most probable token $\hat{v}$ as
$\hat{v}=\operatorname*{arg\,max}_{v\in\mathcal{V}}p_{\theta}(v|\boldsymbol{x})$;

6 if  _$\hat{v}\notin G$_ then

7 $\hat{x}=\hat{v}$;

8

9 else

10 Collect the set of top-$k$ candidate tokens $\mathcal{C}^{(k)}$ from
$p_{\theta}(\cdot|\boldsymbol{x})$;

11
$\hat{x}=\operatorname*{arg\,max}_{c\in\mathcal{C}^{(k)}}\bigg{\\{}p_{\theta}(c|\boldsymbol{x}_{<t})-\alpha\times
f(d(c;\boldsymbol{x}))\bigg{\\}}$; (see Eq. (2))

12

13 end if

14 Update the directed graph $G$ with next token $\hat{x}$;

15 Update the prefix $\boldsymbol{x}=[\boldsymbol{x}:\hat{x}]$;

16 end for

Output : The generated text $\boldsymbol{x}$.

Algorithm 1 Momentum Decoding

##  4 Experiments

In this section, we provide details of our experimental setups and evaluation
results.

##### Evaluation Benchmarks.

Following previous studies Su and Xu (2022); Li et al. (2022), we conduct
extensive experiments on three open-ended text generation benchmarks from
different domains, including (i) articles from
Wikinews333https://www.wikinews.org in the news domain; (ii) Wikitext-103
dataset Merity et al. (2017) from the Wikipedia domain; (iii) and BookCorpus
Zhu et al. (2015) from the story domain.

##### Model and Baselines.

We compare momentum decoding with a range of existing decoding methods,
including (1) greedy search (Greedy); (2) beam search (Beam); (3) top-$k$
sampling (Top-$k$) (Fan et al., 2018a); (3) nucleus sampling (Nucleus)
(Holtzman et al., 2020); (4) typical sampling (Typical) (Meister et al.,
2022); (5) contrastive decoding (CD) (Li et al., 2022);444During generation,
contrastive decoding demands an extra amateur LM. In our experiments, we
follow Li et al. (2022) and use the GPT-2-small model as the amateur LM. and
(6) contrastive search (CS) Su et al. (2022b). For the proposed momentum
decoding (MD), we set the $k$ and $\alpha$ (see Eq. (2)) as $5$ and $0.2$,
respectively.555We use the hyperparameters of different baseline methods as
suggested by previous studies (Li et al., 2022; Su et al., 2022b). The
hyperparameters of MD are selected based on the LM’s performance on the
validation set.

Following Su and Xu (2022); Li et al. (2022), we use the GPT-2-XL model
(Radford et al., 2019) as the evaluated LM. The generation of the LM is
conditioned on the test prompts with a fixed length of 32. And the generation
of the text ends upon reaching an end-of-document token or a maximum length of
256 tokens.

| Method | Diversity(%)$\uparrow$ | MAUVE(%)$\uparrow$ | Coherence$\uparrow$ | Greedy Ratio(%)$\uparrow$ | MD-Speedup | FLOPs$\downarrow$
---|---|---|---|---|---|---|---
News | Greedy | 3.55 | 13.89 | -0.47 | 100.00 | $\Delta 0\%$ | 1.0$\times$
Beam | 5.62 | 8.04 | -0.45 | 90.04 | $\Delta 36\%$ | 4.0$\times$
Top-$k$ | 91.56 | 89.41 | -2.22 | 52.95 | $\Delta 2\%$ | 1.0$\times$
Nucleus | 93.54 | 88.86 | -2.61 | 48.59 | $\Delta 0\%$ | 1.0$\times$
Typical | 91.21 | 90.80 | -2.02 | 52.95 | $\Delta 7\%$ | 1.0$\times$
CD | 92.61 | 92.90 | -2.27 | 35.58 | $\Delta 38\%$ | 5.0$\times$
CS | 93.72 | 80.87 | -1.39 | 72.80 | $\Delta 31\%$ | 4.36$\times$
MD(ours) | 97.66 | 76.93 | -1.34 | 77.95 | - | 1.0$\times$
| Method | Diversity(%)$\uparrow$ | MAUVE(%)$\uparrow$ | Coherence$\uparrow$ | Greedy Ratio(%)$\uparrow$ | MD-Speedup | FLOPs$\downarrow$
Wikipedia | Greedy | 3.40 | 6.02 | -0.41 | 100.00 | $\Delta 0\%$ | 1.0$\times$
Beam | 2.93 | 3.82 | -0.40 | 91.90 | $\Delta 18\%$ | 4.0$\times$
Top-$k$ | 90.33 | 84.89 | -2.37 | 50.80 | $\Delta 5\%$ | 1.0$\times$
Nucleus | 94.25 | 91.57 | -3.03 | 43.55 | $\Delta 5\%$ | 1.0$\times$
Typical | 86.89 | 85.24 | -2.21 | 50.80 | $\Delta 8\%$ | 1.0$\times$
CD | 90.73 | 90.78 | -2.34 | 36.38 | $\Delta 38\%$ | 5.0$\times$
CS | 89.82 | 79.52 | -1.56 | 67.60 | $\Delta 25\%$ | 4.36$\times$
MD(ours) | 97.12 | 83.94 | -1.55 | 74.37 | - | 1.0$\times$
| Method | Diversity(%)$\uparrow$ | MAUVE(%)$\uparrow$ | Coherence$\uparrow$ | Greedy Ratio(%)$\uparrow$ | MD-Speedup | FLOPs$\downarrow$
Story | Greedy | 0.86 | 2.67 | -0.34 | 100.00 | $\Delta 0\%$ | 1.0$\times$
Beam | 1.44 | 2.0 | -0.32 | 93.07 | $\Delta 36\%$ | 4.0$\times$
Top-$k$ | 91.22 | 86.38 | -2.45 | 45.03 | $\Delta 2\%$ | 1.0$\times$
Nucleus | 94.50 | 91.77 | -3.02 | 41.56 | $\Delta 0\%$ | 1.0$\times$
Typical | 90.41 | 85.77 | -2.26 | 47.03 | $\Delta 7\%$ | 1.0$\times$
CD | 89.66 | 91.13 | -2.23 | 35.63 | $\Delta 35\%$ | 5.0$\times$
CS | 93.06 | 51.82 | -1.61 | 69.54 | $\Delta 28\%$ | 4.36$\times$
MD(ours) | 96.99 | 67.67 | -1.47 | 73.86 | - | 1.0$\times$
|  |  |  |  |  |  |

Table 2: Automatic evaluation results. $\uparrow$ means the higher the better
and $\downarrow$ means the lower the better.

###  4.1 Automatic Evaluation

####  4.1.1 Evaluation Metrics

We follow previous studies (Li et al., 2022; Su et al., 2022b; Su and Collier,
2022) and use the metrics below for automatic evaluation.

(1) Diversity takes into account the generated repetition at different
$n$-gram levels and it is defined as:
$\textup{{diversity}}=\prod_{n=2}^{4}(1.0-\frac{\textup{rep-n}}{100})$, where
$\textup{{rep-n}}=100\times(1.0-\frac{|\textup{unique
n-grams}(\hat{\boldsymbol{x}})|}{|\textup{total
n-grams}(\hat{\boldsymbol{x}})|})$ and $\hat{\boldsymbol{x}}$ is the text
generated by the LM.

(2) MAUVE (Pillutla et al., 2021) is a metric designed for measuring the token
distribution closeness between the generated text and human-written text.
However, as recently pointed out by Su and Xu (2022), MAUVE does not
accurately reflect human preferences over different decoding methods.

(3) Coherence (Su and Collier, 2022) automatically measures the semantic
coherence between the prefix text $\boldsymbol{x}$ and the generated text
$\hat{\boldsymbol{x}}$ using a massively pre-trained OPT-2.7B LM Zhang et al.
(2022). Specifically, the metric is defined as the averaged log-likelihood of
the generated text conditioned on the prefix text as:

$\begin{split}\frac{1}{|\hat{\boldsymbol{x}}|}\sum_{i=1}^{|\hat{\boldsymbol{x}}|}\log
p_{\mathcal{M}}\left(\hat{\boldsymbol{x}}_{i}\mid\left[\boldsymbol{x}:\hat{\boldsymbol{x}}_{<i}\right]\right),\end{split}$
(3)

where $[:]$ is the concatenation operation.

(4) Greedy Ratio measures the proportion of the LM’s generation equal to the
prediction of the maximization-based method, i.e., greedy search. Formally,
given the prefix $\boldsymbol{x}$ and the output
$\hat{\boldsymbol{x}}=\\{\hat{x}_{1},...,\hat{x}_{|\hat{\boldsymbol{x}}|}\\}$
generated by the LM, the greedy ratio is defined as

$\frac{1}{|\hat{\boldsymbol{x}}|}\sum_{i=1}^{|\hat{\boldsymbol{x}}|}\mathds{1}(\hat{x}_{i}=\operatorname*{arg\,max}_{v\in\mathcal{V}}p_{\theta}(v|[\boldsymbol{x}:\hat{\boldsymbol{x}}_{<i}])),$
(4)

where $\mathcal{V}$ is the vocabulary of the LM $\theta$, and $[:]$ denotes
the concatenation operation. We note that a higher greedy ratio indicates the
decoding method behaves more similarly to greedy search. Thereby, it better
bridges the gap between the training and the decoding of the LM, as described
in section 1.

(5) MD-Speedup computes the relative per token inference speedup of momentum
decoding with respect to different compared methods.

(6) FLOPs measures the computational complexity of different methods in terms
of the number of required floating-point operations during inference. A higher
FLOPs means the method is computationally more intensive Liu et al.
(2020).666We use the deepspeed package
(https://github.com/microsoft/DeepSpeed) to calculate the FLOPs of different
decoding methods.

News | Method A is better | Neutral | Method B is better
---|---|---|---
Momentum Decoding |  56.7%† | 1.3% | 42.0% | Nucleus Sampling
Momentum Decoding |  57.0%† | 3.0% | 40.0% | Contrastive Decoding
Momentum Decoding | 40.7% | 8.0% |  51.3%† | Contrastive Search
Wikipedia | Method A is better | Neutral | Method B is better
Momentum Decoding |  60.0%† | 0.7% | 39.3% | Nucleus Sampling
Momentum Decoding |  62.5%† | 4.5% | 33.0% | Contrastive Decoding
Momentum Decoding |  50.0%∥ | 7.3% | 42.7%∥ | Contrastive Search
Story | Method A is better | Neutral | Method B is better
Momentum Decoding |  59.0%† | 1.3% | 39.7% | Nucleus Sampling
Momentum Decoding |  58.0%† | 3.0% | 39.0% | Contrastive Decoding
Momentum Decoding |  46.7%∥ | 6.6% |  46.7%∥ | Contrastive Search
|  |  |  |  |

Table 3: Human evaluation results. † means one method performs significantly
better than the other as judged by Sign Test with $p$-value < 0.05. ∥ means
one system performs comparably with the other with $p$-value > 0.4.

####  4.1.2 Evaluation Results

Table 2 presents the experimental results of the automatic evaluation, from
which we can make the following conclusions:

(1) compared with previous state-of-the-art works, momentum decoding (MD)
achieves the highest diversity on three benchmarks. This observation
demonstrates that momentum decoding effectively addresses the degeneration
problem by preventing the LMs from generating deep, circular loops.

(2) MD performs notably better than state-of-the-art baselines on the
coherence metric, such as contrastive search and contrastive decoding,
suggesting it best maintains the semantic consistency between the generated
text and the given prefix text and the semantic consistency inner the
generated text. Although greedy search and beam search outperforms MD on the
coherence, they suffer the severe degeneration problem because of their over-
confidence over probability of LMs.

(3) compared with state-of-the-art baselines, such as contrastive search and
contrastive decoding, MD’s greedy ratio is much higher. This observation
proves that MD’s gap between training and inference is smaller, leading to
more reliable and robust performance. Similarly, greedy search and beam search
achieves the highest greedy ratio, but their generations face a serious
degeneration problem.

(4) the MAUVE scores of contrastive search and momentum decoding are weaker
than stochastic decoding methods. As pointed out by previous studies Su and
Collier (2022); Su and Xu (2022), MAUVE does accurately reflect the actual
performance of baselines. For example, nucleus sampling achieves a higher
MAUVE score than contrastive search, which contradicts the human evaluation in
previous works Su and Collier (2022); Su and Xu (2022); Su et al. (2022b). In
this paper, we analyze the quality of baselines accurately by conducting the
human evaluation in Section section 4.2.

(5) it is worth noting that momentum decoding achieves comparable efficiency
with the most efficient autoregressive decoding method, i.e., the greedy
search, on MD-Speedup and FLOPs metrics, and significantly outperforms the
state-of-the-art contrastive search baseline by a large margin. For example,
the FLOPs of contrastive search are over four times that of MD’s FLOPs,
indicating its much higher computation burden during online inference.
Meanwhile, compared with greedy search, the FLOPs and MD-Speedup of momentum
decoding are $\Delta 0\%$ and $1\times$ on three benchmarks, respectively.

###  4.2 Human Evaluation

We also conduct a human evaluation with four native-speaker graders from a
third-party grading platform. We randomly select 150 test prompts from the
benchmarks across different domains. We compare momentum decoding against
nucleus sampling, contrastive decoding, and contrastive search (i.e. the
current state of the art) through pairwise comparison. Specifically, for each
test prompt, the annotators are given two texts, in random order, that are
generated by MD and another compared method. The annotators then decide which
one is more likely written by humans considering the following aspects of the
generated text:

  * •

Coherence: Whether the generated text is semantically coherent.

  * •

Fluency: Whether the generated text is fluent and easy to understand.

  * •

Informativeness: Whether the generated text is diverse and contains
interesting content.

Table 3 presents the experimental results of the human evaluation. It can be
found that momentum decoding significantly outperforms nucleus sampling and
contrastive decoding by a large margin on all three benchmarks. Moreover,
momentum decoding also achieves a comparable performance with the state-of-
the-art contrastive search method as judged by Sign Test. For example,
momentum decoding slightly outperforms contrastive search on the Wikipedia
domain. These observations are impressive due to MD’s higher inference
efficiency than contrastive search, showing its potential for efficient online
inference.

###  4.3 Case Study

This section shows a case from the Wikinews domain to compare our proposed
momentum decoding and contrastive search (CS). As shown in Table 4, three
human annotators consistently agree that the generation of momentum decoding
is better than CS’s result. We can make two conclusions based on their
comparison: (1) CS’s generation is slightly incoherent with the given prefix.
This might be because contrastive search overcorrects the top-$1$ candidate
token in some decoding steps; (2) momentum decoding encourages the LM to
greedily explore new tokens (highlighted in red) outside the directed graph,
which is degeneration-free and includes diverse tokens to the generation; (3)
momentum decoding also allows the LM to return to the nodes (highlighted in
blue) within the directed graph, and resistance effectively avoids the
degeneration problem in this case.

Method | Generated Result
---|---
Contrastive Search |  Slovakia eliminated defending champions Italy from the World Cup. First round groups E and F were decided on Thursday: Japan, Paraguay and the Netherlands progress alongside Slovakia. In a statement, FIFA said it would take “immediate action” in relation to the match-fixing allegations, which came to light last week in a report by the South African newspaper Rapport. FIFA president Sepp Blatter was due to hold a news conference on Friday in Zurich but postponed the event to allow him to “consult with legal advisers on the best way to deal with this situation,” the statement said. Rapport’s report alleged that a group of players, including Italy’s Andrea Pirlo, had agreed to fix matches in exchange for cash payments, and that the money was used to pay for Pirlo’s birthday present to his wife. Blatter, who has been in office since 1998, said in a statement: “I am shocked and dismayed by the news that has come to light in the last few days. It is a sad day for football and the world of sport in general, which is based on fair play and the rule of law.” The Swiss Football Association (SFSA) said it had opened an investigation into the allegations and was in contact with FIFA’s ethics committee. Slovakia’s Prime Minister Robert Fico told public broadcaster SVT …
Momentum Decoding |  Slovakia eliminated defending champions Italy from the World Cup. First round groups E and F were decided on Thursday: Japan, Paraguay and the Netherlands progress alongside Slovakia . The second round of matches will be played on Saturday, with the top two teams from each group progressing to the quarter-finals. The quarter-final draw will take place on Sunday. “We are very happy that we have qualified for the last eight,” said Slovakia coach Zdenek Zeman.“It is a great achievement for our team and I am sure it will give us a lot of confidence going into the tournament.” Italy’s qualification was secured by a 2-1 win over Croatia in their opening game. They then beat Sweden 1-0 in an entertaining match at the Stadio Olimpico in Rome. Croatia, who finished third in Group A,will face either England or Germany in the semi-finals after they lost to Spain and Portugal respectively . Group B features hosts France, Belgium, Russia and Ukraine. France beat Ukraine 3-2 in Paris on Wednesday before beating Russia 2-3 in Kiev on Friday. Belgium, which finished fourth in Group B, will play either Germany or England in the final. Russia, whose qualifying campaign ended in disappointment, will meet either Spain or Portugal in the semis. Ukraine, who won their group …
|

Table 4: One case on Wikinews benchmark, and all annotators consistently judge
that MD’s generation is better. The prefix is highlighted in bold with an
underline. Both contrastive search and momentum decoding generate very high-
quality and fluent generations. However, the generation of contrastive search
is slightly incoherent with the given prefix, while momentum decoding doesn’t.
As for the generation of momentum decoding, the new tokens outside its current
directed graph are highlighted in red. The tokens that exist in the directed
graph but still have the highest scores after the Eq. (2)’s modification are
highlighted in blue.

##  5 Further Analysis

In this section, we provide three in-depth analyses to reveal the merits of
momentum decoding in detail: (1) the connection with the state-of-the-art
decoding method, contrastive search; (2) comprehensive comparison between MD
and baselines; (3) the ablation study of the resistance function.

###  5.1 Connection with Contrastive Search

The formulation of contrastive search is shown in Eq. (5). At $i$-th decoding
step, contrastive search collects top-$k$ candidate tokens $V^{(k)}$ and feeds
them into LMs again to obtain the hidden states $h_{v}$, which is used to
compute their degeneration penalties (maximum cosine similarity with
$\boldsymbol{x}_{<i}$).

$\begin{split}x&=\operatorname*{arg\,max}_{v\in
V^{(k)}}\bigg{\\{}(1-\alpha)\times\underbrace{p_{\theta}(v|\boldsymbol{x}_{<i})}_{\textup{model
confidence}}-\\\ &\>\alpha\times\underbrace{(\max\\{s(h_{v},h_{x_{j}}):1\leq
j\leq i-1\\})}_{\textup{degeneration penalty}}\bigg{\\}}\end{split}$ (5)

Through comparing it with Eq. (2), we could make two conclusions: (1) the term
degeneration penalty in contrastive search can be viewed as an implementation
of the resistance function in momentum decoding. In our paper, the resistance
function is a simple yet empirically effective look-up table, leading to
better inference efficiency than the contrastive search; (2) momentum decoding
only modifies the probabilities of candidates when the top-$1$ token exists in
$G$. On the contrary, contrastive search modifies the probabilities at every
decoding step, leading to a higher gap between the training and inference
stage. For example, as shown in Table 2, the greedy ratio of momentum decoding
is higher than the contrastive search on three benchmarks.

Figure 2: Ablation study of resistance function on Wikinews benchmark. MD
monotone denotes the monotone increasing resistance function designed in Table
1. MD constant indicates the constant resistance function (i.e. $f(\cdot)=2$)
for momentum decoding.

###  5.2 Momentum Decoding versus Previous Works

We vary the hyper-parameters for different methods, i.e., $k$ for top-$k$
sampling (from 5 to 640); $p$ for nucleus sampling (from 0.4 to 1.0); $k$ for
contrastive search (from 2 to 10); and $k$ for momentum decoding (from 2 to
10)777(i) For top-$k$ sampling, $k\in[5,10,20,40,50,80,160,320,$ $640]$; (ii)
for nucleus sampling, $p\in[0.4,0.5,0.6,0.7,0.8$, $0.9,0.95,1.0]$; (iii) for
contrastive search, $k\in[2,3,4,5,6$, $7,8,9,10]$; and (iv) for momentum
decoding,$k\in[2,3,4,5,$ $6,7,8,9,10]$. We keep $\alpha$ for contrastive
search and momentum decoding as a constant 0.6 and 0.2, respectively.. As
shown in Figure 3, it can be found that our proposed momentum decoding (red
line) notably outperforms other baselines on balance between the coherence and
diversity metrics. Besides, the gap between contrastive search and momentum
decoding is relatively small, which is highly correlated with human judgments
in Section (section 4.2). This observation probably marks the higher
correlation between human judgments and the diversity-coherence combination.

Figure 3: Diversity-Coherence analysis on the Wikinews benchmark.

###  5.3 Ablation Study of Resistance Functions

In this section, we conduct the ablation study of the resistance function.
Specifically, we simply replace the monotone increasing resistance function as
designed in Table 1 with a constant function (i.e. $f(\cdot)=2$), and the
$\alpha$ hyper-parameter keeps the same $0.2$. From Figure 2, it can be found
that the resistance function’s implementation slightly influences the momentum
decoding performance. Even if $f(\cdot)$ is a constant function, it could
still generate text with higher diversity and coherence than contrastive
search, proving the robustness of our proposed momentum decoding.

##  6 Conclusion and Future Work

In this paper, we introduce a new perspective on the task of open-ended text
generation. Specifically, we view it as an exploration process within a
directed graph. We understand the degeneration problem as circular loops in
the directed graph. Furthermore, we propose a novel decoding method—momentum
decoding—which encourages the LM to greedily explore the new tokens outside
the current directed graph. Meanwhile, it also allows the LM to return to the
existing nodes but with a momentum downgraded by a simple yet effective
resistance function. We extensively test our approach on three benchmarks
across different domains. Both automatic and human evaluations verify that
momentum decoding performs comparably with the current state of the art while
enjoying 30% of inference speedup and more than 4$\times$ reduction in
computation FLOPs.

We note that momentum decoding is model architecture-agnostic and can be
applied to any generative model. In future work, we would like to extend our
investigation on momentum decoding to other generative models (e.g., encoder-
decoder models) and other generation tasks (e.g., machine translation and
document summarization).

## Limitations

While momentum decoding achieves impressive inference efficiency and
effectiveness, the current design of the resistance function (Table 1)
inevitably leads to the N-gram blocking problem. It can be found that, given
the context $\boldsymbol{x}_{<t}$, a candidate token $x_{t}$ with circular
depth $d(x_{t},\boldsymbol{x}_{<t})\geq 4$ (see Eq. (1)) would receive a
$5\times 0.2=1$ resistance in Eq. (2). In such case, $x_{t}$ with circular
depth $d(x_{t},\boldsymbol{x}_{<t})\geq 4$ will be blocked during generation.
While as demonstrated in Appendix D, the repetitions of human-written text in
$n$-gram, where $n\geq 4$, are reasonably low, such N-gram blocking behavior
is still undesirable.

Therefore, we point out two potential solutions for this problem: (1) adopting
a smaller $\alpha$ parameter in Eq. (2) or carefully defining the resistance
function to allow the LM to generate longer N-grams; (2) purposely deleting
earlier tokens or edges in the directed graph to lower the circular depth,
allowing longer N-grams to be generated.

## References

  * Basu et al. (2020) Sourya Basu, Govardana Sachitanandam Ramachandran, Nitish Shirish Keskar, and Lav R Varshney. 2020.  Mirostat: A neural text decoding algorithm that directly controls perplexity.  _arXiv preprint arXiv:2007.14966_.
  * Basu et al. (2021) Sourya Basu, Govardana Sachithanandam Ramachandran, Nitish Shirish Keskar, and Lav R. Varshney. 2021.  Mirostat: a neural text decoding algorithm that directly controls perplexity.  In _International Conference on Learning Representations_.
  * Fan et al. (2018a) Angela Fan, Mike Lewis, and Yann Dauphin. 2018a.  Hierarchical neural story generation.  _arXiv preprint arXiv:1805.04833_.
  * Fan et al. (2018b) Angela Fan, Mike Lewis, and Yann Dauphin. 2018b.  Hierarchical neural story generation.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Maxwell Forbes, and Yejin Choi. 2020.  The curious case of neural text degeneration.  _ArXiv_ , abs/1904.09751.
  * Li et al. (2016) Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and William B. Dolan. 2016\.  A diversity-promoting objective function for neural conversation models.  In _North American Chapter of the Association for Computational Linguistics_.
  * Li et al. (2022) Xiang Lisa Li, Ari Holtzman, Daniel Fried, Percy Liang, Jason Eisner, Tatsunori Hashimoto, Luke Zettlemoyer, and Mike Lewis. 2022.  Contrastive decoding: Open-ended text generation as optimization.  _ArXiv_ , abs/2210.15097.
  * Liu et al. (2020) Weijie Liu, Peng Zhou, Zhe Zhao, Zhiruo Wang, Haotang Deng, and Qi Ju. 2020.  Fastbert: a self-distilling bert with adaptive inference time.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Meister et al. (2022) Clara Meister, Tiago Pimentel, Gian Wiher, and Ryan Cotterell. 2022.  Typical decoding for natural language generation.  _ArXiv_ , abs/2202.00666.
  * Merity et al. (2017) Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. 2017.  Pointer sentinel mixture models.  _ArXiv_ , abs/1609.07843.
  * Mostafazadeh et al. (2016) N. Mostafazadeh, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, and James F. Allen. 2016.  A corpus and cloze evaluation for deeper understanding of commonsense stories.  In _North American Chapter of the Association for Computational Linguistics_.
  * Pillutla et al. (2021) Krishna Pillutla, Swabha Swayamdipta, Rowan Zellers, John Thickstun, Sean Welleck, Yejin Choi, and Zaïd Harchaoui. 2021.  Mauve: Measuring the gap between neural text and human text using divergence frontiers.  In _Neural Information Processing Systems_.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Rae et al. (2021) Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John F. J. Mellor, Irina Higgins, Antonia Creswell, Nathan McAleese, Amy Wu, Erich Elsen, Siddhant M. Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, L. Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, N. K. Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Tobias Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d’Autume, Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris Jones, James Bradbury, Matthew G. Johnson, Blake A. Hechtman, Laura Weidinger, Iason Gabriel, William S. Isaac, Edward Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem W. Ayoub, Jeff Stanway, L. L. Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving. 2021.  Scaling language models: Methods, analysis & insights from training gopher.  _ArXiv_ , abs/2112.11446.
  * Su et al. (2021a) Yixuan Su, Deng Cai, Qingyu Zhou, Zibo Lin, Simon Baker, Yunbo Cao, Shuming Shi, Nigel Collier, and Yan Wang. 2021a.  Dialogue response selection with hierarchical curriculum learning.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1740–1751.
  * Su and Collier (2022) Yixuan Su and Nigel Collier. 2022.  Contrastive search is what you need for neural text generation.  _arXiv preprint arXiv:2210.14140_.
  * Su et al. (2022a) Yixuan Su, Tian Lan, Yahui Liu, Fangyu Liu, Dani Yogatama, Yan Wang, Lingpeng Kong, and Nigel Collier. 2022a.  Language models can see: Plugging visual controls in text generation.  _arXiv preprint arXiv:2205.02655_.
  * Su et al. (2022b) Yixuan Su, Tian Lan, Yan Wang, Dani Yogatama, Lingpeng Kong, and Nigel Collier. 2022b.  A contrastive framework for neural text generation.  In _Advances in Neural Information Processing Systems_.
  * Su et al. (2022c) Yixuan Su, Lei Shu, Elman Mansimov, Arshit Gupta, Deng Cai, Yi-An Lai, and Yi Zhang. 2022c.  Multi-task pre-training for plug-and-play task-oriented dialogue system.  In _Annual Meeting of the Association for Computational Linguistics_.
  * Su et al. (2021b) Yixuan Su, Yan Wang, Simon Baker, Deng Cai, Xiaojiang Liu, Anna Korhonen, and Nigel Collier. 2021b.  Prototype-to-style: Dialogue generation with style-aware editing on retrieval memory.  _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , 29:2152–2161.
  * Su and Xu (2022) Yixuan Su and Jialu Xu. 2022.  An empirical study on contrastive search and contrastive decoding for open-ended text generation.  _arXiv preprint arXiv:2211.10797_.
  * Thoppilan et al. (2022) Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam M. Shazeer, Apoorv Kulshreshtha, Heng-Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, Yaguang Li, Hongrae Lee, Huaixiu Zheng, Amin Ghafouri, Marcelo Menegali, Yanping Huang, Maxim Krikun, Dmitry Lepikhin, James Qin, Dehao Chen, Yuanzhong Xu, Zhifeng Chen, Adam Roberts, Maarten Bosma, Yanqi Zhou, Chung-Ching Chang, I. A. Krivokon, Willard James Rusch, Marc Pickett, Kathleen S. Meier-Hellstern, Meredith Ringel Morris, Tulsee Doshi, Renelito Delos Santos, Toju Duke, Johnny Hartz Søraker, Ben Zevenbergen, Vinodkumar Prabhakaran, Mark Díaz, Ben Hutchinson, Kristen Olson, Alejandra Molina, Erin Hoffman-John, Josh Lee, Lora Aroyo, Ravindran Rajakumar, Alena Butryna, Matthew Lamm, V. O. Kuzmina, Joseph Fenton, Aaron Cohen, Rachel Bernstein, Ray Kurzweil, Blaise Aguera-Arcas, Claire Cui, Marian Croak, Ed Chi, and Quoc Le. 2022.  Lamda: Language models for dialog applications.  _ArXiv_ , abs/2201.08239.
  * Zhang et al. (2022) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. 2022.  Opt: Open pre-trained transformer language models.  _ArXiv_ , abs/2205.01068.
  * Zhang et al. (2019) Wen Zhang, Yang Feng, Fandong Meng, Di You, and Qun Liu. 2019.  Bridging the gap between training and inference for neural machine translation.  _arXiv preprint arXiv:1906.02448_.
  * Zhu et al. (2015) Yukun Zhu, Ryan Kiros, Richard S. Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. 2015.  Aligning books and movies: Towards story-like visual explanations by watching movies and reading books.  _2015 IEEE International Conference on Computer Vision (ICCV)_ , pages 19–27.

##  Appendix A Pseudo-code of Momentum Decoding

Algorithm 2 provides the pseudo-code of our proposed momentum decoding. At
each decoding step, momentum decoding considers ranking top-$k$ candidate
tokens ($k=5$ in this study). The greedy search is conducted if the top-$1$
candidate token doesn’t exist in the currently directed graph. Otherwise, the
scores of top-$k$ candidate tokens are calculated by Eq. (2), and the one with
the highest score is chosen as the next token. Since the computation cost of
updating and searching $G$ is neglectable, the inference efficiency of
momentum decoding is significantly closer to the greedy search.

⬇

# LM: language model, for example, the GPT2

# init_graph: function to initialize the directed graph for the given prefix

# prefix: a sequence of tokens in prefix

# decoding_length: the number of the new tokens that should be generated

# top_k: top-k candidate tokens

# find_depth: function to find depths of candidate token in directed graph

dg = init_graph(prefix) # initialized the directed graph

for _ in range(decoding_length): # auto-regressive decoding

# logits over the vocabulary

logits = LM(prefix)

# probability of top-k candidate tokens

top_k_ids, top_k_probs = softmax(logits, dim=-1).topk(k=top_k)

if top_k_ids[0] not in dg:

# top-1 token doesn’t in directed graph, conduct greedy search

next_token = top_k_ids[0]

else:

# calculate the penalty by the resistance function

depth = [max(find_depth(dg,x)) for x in top_k_ids]

resistance = [RF(d) for d in depth]

scores = [p - alpha * r for p, r in zip(top_k_probs, resistance)]

next_token = argmax(scores)

# update the directed graph

dg.update(next_token)

# update the prefix

prefix.append(next_token)

softmax: softmax activation function; argmax: argmax function; topk: topk
function.

Algorithm 2 Pseudo-code of Momentum Decoding in a PyTorch-like style.

$N$-gram Repetitions | Wikinews | Wikitext | BookCorpus
---|---|---|---
2-gram | 10.76% | 9.47% | 7.14%
3-gram | 2.49% | 2.94% | 1.51%
4-gram | 0.86% | 1.05% | 0.48%
5-gram | 0.38% | 0.46% | 0.19%
6-gram | 0.19% | 0.22% | 0.09%
7-gram | 0.09% | 0.11% | 0.05%
8-gram | 0.06% | 0.07% | 0.04%
|  |  |

Table 5: The proportion of the repetition $n$-grams in three benchmarks. It
can be found that the proportion of the repetition $4$-gram is extremely slow.

##  Appendix B More Cases

Method | Generated Result
---|---
Contrastive Search |  At least ten people are dead after a large, destructive tornado tore through Yazoo City, Mississippi yesterday. The tornado has been rated an EF4 on the Enhanced Fujita Scale , which is used to measure tornadoes in the U.S. and Canada. Here’s a look at the damage in Yazoo City, courtesy of WLOX-TV in Biloxi, Mississippi: Advertisement. Article Continues Below. Video by Chris Cappella/Shutterstock. According to Weather Underground, the twister touched down at 2:30 pm local time (11:30 am ET) near the intersection of I-10 and U.S. Highway 61. As of this writing, there are reports of at least ten fatalities, including a woman who was killed by a falling tree. Advertisement. Article Continues Below. Video by Chris Cappella/Shutterstock. The National Weather Service is warning that a “large number of power outages are expected to continue for the next 24 hours, as crews work to restore power to as many customers as possible.” In addition to the storm damage, the city is dealing with water and sewage overflows, which is a common problem in this time of year. Advertisement. Article Continues Below. Video by Chris Cappella/Shutterstock. The Associated Press reports that some schools have been closed for the day, …
Momentum Decoding |  At least ten people are dead after a large, destructive tornado tore through Yazoo City, Mississippi yesterday. The tornado has been rated an EF4 on the Enhanced Fujita Scale, which is used to measure tornadoes. The tornado was reported at around 2:30 p.m. and touched down in the area of Highway 59 and Interstate 24. It was moving west-northwest at about 50 miles per hour. According to the National Weather Service , the tornado had winds of up to 100 mph. “It’s just devastating,” said one resident who lives near the scene of the storm. “I’ve never seen anything like it.“ According to WREG, there were no reports of injuries or fatalities. A number of homes were damaged by the powerful tornado. A witness told WREG that he saw a car go through a fence and into a home. He also said that his house was destroyed. Another witness said she saw a man get hit by debris from the tornado. She said the man was taken to a hospital with non-life threatening injuries. According to The Clarion-Ledger, Yazoo County Emergency Management Director Mike Boudreaux said there have been no confirmed reports of deaths or injuries in the county. Boudreaux added that the damage is extensive and will take some time to assess …
|

Table 6: One case on Wikinews benchmark, and all annotators consistently judge
that MD’s generation is better than the one generated by the contrastive
search. The prefix is highlighted in bold with an underline. It can be found
that the contrastive search also leads to invalid repetitions in this case. As
for the generation of momentum decoding, the new tokens outside its current
directed graph are highlighted in red. The tokens that exist in the directed
graph but still have the highest scores after the Eq. (2)’s modification are
highlighted in blue.

##  Appendix C More Analysis

###  C.1 Ablation Study of Resistance Function

More ablation studies on Wikitext and BookCorpus benchmarks are shown in
Figure 4. It can be found that the implementation of the resistance function
slightly influences the performance of momentum decoding. Even if $f(\cdot)$
is a constant function, it could still generate text with higher diversity and
coherence than contrastive search, proving the robustness of our proposed
momentum decoding.

Figure 4: Ablation study of resistance function on Wikitext and BookCorpus
(Story) benchmark. MD monotone denotes the monotone increasing resistance
function designed in Table 1. MD constant indicates the constant resistance
function (constant is 2) for momentum decoding.

###  C.2 Momentum Decoding versus Previous Works

Figure 5: Diversity-Coherence analysis on Wikitext and Story benchmarks.

Figure 5 shows the diversity-coherence balance analysis on Wikitext and
BookCorpus (Story) benchmarks. It can be found that our proposed momentum
decoding notably outperforms the previous baselines on balance between the
coherence and diversity metrics, indicating that momentum decoding solves the
degeneration problem and could generate robust and diverse text.

##  Appendix D $n$-gram Statistics on Three Benchmarks

The repetition statistics $N$-grams are shown in Table 5. It can be found that
the longer $n$-grams have an extremely slow repetition proportion in all three
benchmarks.