A Non-monotonic Self-terminating Language Model

Sequences, vocabulary, and $\langle eos\rangle$ We view an instance (e.g., a sentence and a paragraph) as a sequence ${\bm{y}}=(y_{1},y_{2},\dots,y_{T})$, where each $y_{t}$ is an element from a pre-defined finite set of discrete tokens, referred to as a vocabulary $\mathcal{V}$. $\mathcal{V}$ includes a special symbol $\langle eos\rangle$ that only appears at the end of the sequence. Every sequence ${\bm{y}}$ must end with $\langle eos\rangle$. We write the length of ${\bm{y}}$ as $|{\bm{y}}|$, and $y_{|{\bm{y}}|}=\langle eos\rangle$. We call ${\bm{y}}$ a non-terminating sequence, $|{\bm{y}}|=\infty$, if $y_{t}\neq\langle eos\rangle$ for all $t$.

Embedding vectors Each token $v\in\mathcal{V}$ is not a numerical vector so that we use an embedding vector ${\bm{u}}_{v}\in\mathbb{R}^{m}$ to represent $v$. To capture the notion of similarity between discrete tokens efficiently, we use an embedding vector ${\bm{u}}_{v}\in\mathbb{R}^{m}$ to project $v$ into continuous embedding space (Bengio et al., 2000; Mikolov et al., 2013b; a; Levy & Goldberg, 2014).

Autoregressive neural sequence models Bengio et al. (2000) proposed an autoregressive neural sequence model parametrized by ${\bm{\theta}}\in\mathbb{R}^{k}$. They factorized $p_{\bm{\theta}}({\bm{y}}|{\bm{x}})$ into a product of the conditional probability of each token given all the previous tokens and an input in a predefined order as follows:

where ${\bm{y}}_{<t}$ is a $t$-prefix of ${\bm{y}}$ and ${\bm{x}}$ is an input referred to as a context. For example, ${\bm{x}}$ represents either a prompt in sequence completion or a source-side sequence in machine translation.

Training For a given dataset, $\mathcal{D}=\left\{\left({\bm{x}}^{(n)},{\bm{y}}^{(n)}\right)\right\}_{n=1}^{N}$, we maximize the joint probability assigned to the sequences in our training dataset to find an optimal parameter configuration ${\bm{\theta}}^{\star}$ as follows:

To generate a high quality sequence from $p_{\bm{\theta}}$, a decoding algorithm assumes that a higher quality sequence has a higher probability of $p_{\bm{\theta}}$ than others. For instance, maximum a posteriori (MAP) decoding algorithm $\mathcal{S}_{map}$ gives the most probable sequence ${\bm{y}}^{\star}$ given a context ${\bm{x}}$ from $p_{\bm{\theta}}$:

by setting $q_{\mathcal{S}_{map}(p_{\bm{\theta}})}({\bm{y}}={\bm{y}}^{\star}|{\bm{x}})=1$ and $q_{\mathcal{S}_{map}(p_{\bm{\theta}})}({\bm{y}}={\bm{y}}^{\prime}|{\bm{x}})=0$ where ${\bm{y}}^{\prime}\in\mathcal{Y}\setminus\{{\bm{y}}^{\star}\}$. Unfortunately, $\mathcal{S}_{map}$ is intractable since equation 4 requires an exhaustive search over the sequence space $\mathcal{Y}$. Hence, in practice, we utilize incomplete probable decoding algorithms defined as follows:

At each $t$, an incomplete probable decoding algorithm $\mathcal{S}$ considers only a set of highly probable tokens, $\mathcal{V}_{t}$. $\mathcal{S}$ generates $\hat{{\bm{y}}}$ given ${\bm{x}}$ by recursively sampling $\hat{y}_{t}$ from $q_{\mathcal{S}(p_{\bm{\theta}})}(y_{t}|\hat{{\bm{y}}}_{<t},{\bm{x}})$ supported on $\mathcal{V}_{t}$. This reduces an exponential complexity of $\mathcal{S}_{map}$, $\mathcal{O}\left(|\mathcal{V}|^{|\hat{{\bm{y}}}|}\right)$, down to a linear level, $\mathcal{O}\left(|\hat{{\bm{y}}}|\cdot|\mathcal{V}|\right)$.

Greedy search, top-$k$ sampling (Fan et al., 2018), and nucleus sampling (Holtzman et al., 2020) are incomplete and probable. For example, greedy search $\mathcal{S}_{gr}$ generates the $t$-th item of a sequence by

In other words, $\mathcal{S}_{gr}$ sets $\mathcal{V}_{t}$ to $\big{\{}v_{t}^{(1)}\big{\}}$ where $v_{t}^{(1)}=\arg\max_{v\in\mathcal{V}}p_{\bm{\theta}}(y_{t}=v|\hat{{\bm{y}}}_{<t},{\bm{x}})$. Moreover, we have $p_{\bm{\theta}}\big{(}y_{t}=v_{t}^{(1)}\big{|}\hat{{\bm{y}}}_{<t},{\bm{x}}\big{)}\leq q_{\mathcal{S}_{gr}(p_{\bm{\theta}})}\big{(}y_{t}=v_{t}^{(1)}\big{|}\hat{{\bm{y}}}_{<t},{\bm{x}}\big{)}=1$, and $q_{\mathcal{S}_{gr}(p_{\bm{\theta}})}(y_{t}=v^{\prime}|\hat{{\bm{y}}}_{<t},{\bm{x}})=0$ holds for $v^{\prime}\in\mathcal{V}\setminus\mathcal{V}_{t}$. Thus, $\mathcal{S}_{gr}$ is incomplete and probable. Unlike $\mathcal{S}_{gr}$, top-$k$ sampling considers $k$ most probable tokens in $\mathcal{V}$ as $\mathcal{V}_{t}$ while nucleus sampling sets the smallest subset of $\mathcal{V}$, containing most probable tokens of which total probability is higher than a given threshold $\mu$, to $\mathcal{V}_{t}$. In §A.1 and A.2, we present that top-$k$ sampling and nucleus sampling are also incomplete and probable.

Beam search is a heuristic algorithm that operates on the level of prefixes. We describe it further in §A.3. Although beam search is not an incomplete probable decoding algorithm, it also selects $\mathcal{V}_{t}$ which is a proper subset of $\mathcal{V}$ to expand each prefix at each step $t$. Due to this, our main theoretical finding for the incomplete probable decoding algorithms in §3 is applicable to beam search as well.

Incomplete probable decoding algorithms greatly reduce computational overhead for generating sequences from our model. However, Welleck et al. (2020) observed that they can generate non-terminating sequences even if every training sequence has a finite length. To study this, Welleck et al. (2020) defined consistency with respect to decoding algorithms as shown in Definition 4.

In equation 9, $p_{\bm{\theta}}^{st}(y_{t}=\langle eos\rangle|{\bm{y}}_{<t},{\bm{x}})$ monotonically increases to 1 as $t$ increases. $\mathcal{S}$ ends up including $\langle eos\rangle$ in $\mathcal{V}_{t}$ always for $t\geq t^{\prime}$ with some $t^{\prime}$, and $\lim_{t\rightarrow\infty}q_{\mathcal{S}(p_{\bm{\theta}})}(y_{t}=\langle eos\rangle|{\bm{y}}_{<t},{\bm{x}})=1$ by equation 7. This guarantees $\mathcal{S}$ to terminate in a finite number of steps. Despite $p_{\bm{\theta}}^{st}$’s consistency, its validation perplexity degrades compared to $p_{\bm{\theta}}^{va}$ in sequence completion (Welleck et al., 2020). We suspect that such degradation comes from the core property of $p_{\bm{\theta}}^{st}$ that $p_{\bm{\theta}}(y_{t}=\langle eos\rangle|{\bm{y}}_{<t},{\bm{x}})$ monotonically increases to $1$ as $t$ increases. In Remark 1 below, we provide an example where the optimal $p_{{\bm{\theta}}^{\star}}(y_{t}=\langle eos\rangle|{\bm{y}}_{<t},{\bm{x}})$ is not monotonic.

We can easily find such case in natural language satisfying the assumptions in Remark 1 by concatenating two sequences. We empirically demonstrate the existence of such cases in §4.2.

WikiText-2 (Merity et al., 2016) consists of 2 million words from 600 Wikipedia articles. With word tokenization, we regard the first 10 tokens of each sequence and its remaining part, as a context ${\bm{x}}$ and a ground truth ${\bm{y}}$, respectively. We train RNN with $\tanh$ (Elman, 1990) and LSTM (Hochreiter & Schmidhuber, 1997) on WikiText-2. Both RNN and LSTM have 2 layers, with 256 and 512 hidden units at each layer, respectively. We perform 10 random runs with a batch size of 32 for 70 epochs. We use AdamW (Loshchilov & Hutter, 2017) with an initial learning rate of $0.001$, $\beta_{1}=0.9$, $\beta_{2}=0.99$, weight decay of $0.01$, learning rate decay, and early stopping. We further describe our models and training strategies for WikiText-2 experiments in §D. Unlike VA+{RNN, LSTM}, ST+{RNN, LSTM} and NMST+{RNN, LSTM} need an additional hyperparameter $\epsilon$. We explore $\epsilon$ in $\{1.0\times 10^{-5},5.0\times 10^{-5},1.0\times 10^{-4},5.0\times 10^{-4}\}$.

We present the average ($\pm$st.dev.) non-termination ratios, $r_{nt}(L)$’s, across 10 random runs as a function of $L$ for all considered setups of WikiText-2 in Figure 2, using greedy search. From equation 11, a language model is consistent with respect to greedy search if $\lim_{L\rightarrow\infty}r_{nt}(L)=0$. As $L$ increases, we observe that $r_{nt}(L)$’s of VA+{RNN, LSTM} fail to converge toward 0 while $r_{nt}(L)$’s of ST+{RNN, LSTM} and NMST+{RNN, LSTM} all reach 0. In other words, RNN and LSTM are now consistent with respect to greedy search after replacing the original softmax parametrization with either the proposed NMST parametrization or ST parametrization.

Table 1 shows that the average ($\pm$st.dev.) validation perplexities across 10 random experiments for all variants of RNN and LSTM, trained on WikiText-2. We observe that NMST+{RNN, LSTM} have better validation perplexities than ST+{RNN, LSTM} for every $\epsilon$. We demonstrate this more clearly in §E.1 by plotting the evolution of the mean validation perplexities as we vary $\epsilon$. Although our NMST+ guarantees the consistency of RNN and LSTM with respect to greedy search with a better validation perplexity than ST+, we need to carefully select $\epsilon$ of NMST+. As $\epsilon$ increases, the lower bound of $p_{\bm{\theta}}^{nmst}(y_{t}=\langle eos\rangle|{\bm{y}}_{<t},{\bm{x}})$ grows faster, yielding premature sequences when $\epsilon$ is too large. Indeed, the average validation perplexities of NMST+RNN and NMST+LSTM with $\epsilon=5.0\times 10^{-4}$ are 184.2 and 105.6 which degrade by 5.6 and 4.0 from those of VA+RNN and VA+LSTM, 178.6 and 101.6, respectively. We however emphasize that there is the optimal $\epsilon=1.0\times 10^{-5}$ that makes NMST+{RNN, LSTM} have the validation perplexities similar to those of VA+{RNN, LSTM}. In short, both NMST+ and ST+ prevent non-termination when using greedy search but only NMST+ has a competitive validation perplexity against VA+. In §G, we further observe that the length distribution of predicted sequences from NMST+LSTM is closer to the length distribution of ground truth sequences than those of predicted sequences from {VA, ST}+LSTM.

WikiText-103 (Merity et al., 2016) consists of 103 million words constructed from 28,000 articles. We use BPE tokenization (Sennrich et al., 2015) and consider the first 10 tokens as a context for each sequence. Since WikiText-103 is substantially larger than WikiText-2, we finetune a pretrained GPT-2 which is a transformer language model with 124 million parameters (Radford et al., 2019) for $500,000$ steps. For computational efficiency, we bucket the dataset into sequences of similar lengths, and each batch contains a maximum of 1,024 total tokens. We use AdamW (Loshchilov & Hutter, 2017) with an initial learning rate of $5.0\times 10^{-5}$, $\beta_{1}=0.9$, $\beta_{2}=0.99$, weight decay of 0.01, linear learning rate decay, and early stopping. We present a more detailed description in §D. We select $\epsilon$ from $\{1.0\times 10^{-5},5.0\times 10^{-5},1.0\times 10^{-4},5.0\times 10^{-4}\}$ for ST+GPT-2 and NMST+GPT-2.

We report the mean ($\pm$st.dev.) validation perplexities and non-termination ratios, $r_{nt}(L)$’s, resulting from greedy search across 10 random runs for all GPT-2 setups finetuned on WikiText-103 in Table 2. Since GPT-2 can handle up to 1,024 tokens, we use $L=\,$1,000. As shown in Figure 2, we need a sufficiently large $L$ such as $L=10^{5}$ to determine whether a language model is consistent with respect to greedy search. Although $L=\,$1,000 is not sufficiently large, we observe that $r_{nt}(L)$ of NMST+GPT-2 decreases compared to $r_{nt}(L)$ of VA+GPT-2 as $\epsilon$ increases. That is, NMST+ reduces the number of non-terminating continuations within 1,000 steps. Non-terminating sequences do not necessarily imply better quality. We thus demonstrate sample continuations from NMST+GPT-2, given a context that leads non-termination with VA+GPT-2 in Table 3, using greedy search. We observe that the quality of the generated sequence tends to improve with NMST+ by avoiding repetitions of similar phrases and ending with $\langle eos\rangle$. We present more example continuations in §E.3.

Similar to the results in §4.1, Table 2 shows that the validation perplexities of both ST+GPT-2 proposed by Welleck et al. (2020) and our NMST+GPT-2 degrade compared to VA+GPT-2 as $\epsilon$ increases. NMST+GPT-2 with the optimal $\epsilon=1.0\times 10^{-5}$ has a competitive validation perplexity of 20.69 against that of VA+GPT-2, 20.72. On the other side, we cannot find $\epsilon$ that makes the validation perplexity of ST+GPT-2 competitive against that of VA+GPT-2. Moreover, if $\epsilon\neq 5.0\times 10^{-4}$, then $r_{nt}(L)$’s of ST+GPT-2 blow up unlike $r_{nt}(L)$’s of VA+GPT-2. §E.2 demonstrates the inevitable perplexity degradation and exploding $r_{nt}(L)$ of ST+GPT-2. We suspect that it is due to monotonically increasing $p_{{\bm{\theta}}}(y_{t}=\langle eos\rangle|{\bm{y}}_{<t},{\bm{x}})$ with respect to $t$.

We investigate behaviors of $p_{\bm{\theta}}(y_{t}=\langle eos\rangle|{\bm{y}}_{<t},{\bm{x}})$ where $p_{\bm{\theta}}$’s are {VA, ST, NMST}+GPT-2 in Figure 3. Based on Table 2, we select the optimal $\epsilon=1.0\times 10^{-5}$ in terms of validation perplexities for {ST, NMST}+GPT-2. In Figure 3, {VA, NMST}+GPT-2 well-capture whether a sequence might end (e.g., after periods) by showing non-monotonic behaviors at those seemingly-terminating steps, but ST+GPT-2 cannot model such non-monotonic behaviors because it assumes that $p_{\bm{\theta}}(y_{t}=\langle eos\rangle|{\bm{y}}_{<t},{\bm{x}})$ is a monotonic function of $t$. This constraint makes ST+GPT-2 generate often finite but unnecessarily long sequences with greedy search (i.e., higher $r_{nt}(L)$ than VA+GPT-2 for small $L$, but $r_{nt}(L)=0$ for sufficiently large $L$). We demonstrate more behaviors in §E.4.