A Non-monotonic Self-terminating Language Model
Authors: Eugene Choi
Kyunghyun Cho
Cheolhyoung Lee
Venue: ICLR 2023 poster (2023)
Keywords: non-terminating sequences
language modeling
sequence completion
decoding
consistency
self-terminating

Abstract: Recent large-scale neural autoregressive sequence models have shown impressive performances on a variety of natural language generation tasks. However, their generated sequences often exhibit degenerate properties such as non-termination, undesirable repetition, and premature termination, when generated with decoding algorithms such as greedy search, beam search, top-$k$ sampling, and nucleus sampling. In this paper, we focus on the problem of non-terminating sequences resulting from an incomplete decoding algorithm. We first define an incomplete probable decoding algorithm which includes greedy search, top-$k$ sampling, and nucleus sampling, beyond the incomplete decoding algorithm originally put forward by Welleck et al. (2020). We then propose a non-monotonic self-terminating language model, which significantly relaxes the constraint of monotonically increasing termination probability in the originally proposed self-terminating language model by Welleck et al. (2020), to address the issue of non-terminating sequences when using incomplete probable decoding algorithms. We prove that our proposed model prevents non-terminating sequences when using not only incomplete probable decoding algorithms but also beam search. We empirically validate our model on sequence completion tasks with various architectures.

Published as a conference paper at ICLR 2023
A NON-MONOTONIC SELF-TERMINATING LANGUAGE MODEL
Eugene Choif
Kyunghyun Cho 18
Cheolhyoung Leeì
eugene. chol eny
kyonghhynn cho.@naa-edd
cheal houngg lee leegnyo.coo edu
ABSTRACT
Recent large-scale neural autoregressive sequence models have shown impressive performances on variety of natural language generation tasks. However, their generated sequences often exhibit degenerate properties such as non-termination, undesirable repetition, and premature termination, when generated with decod- ing algorithms such as greedy search, beam search, top-k sampling, and nucleus sampling. In this paper, we focus on the problem of non-terminating sequences resulting from an incomplete decoding algorithm. We first define an incomplete probable decoding algorithm which includes greedy search, top-k sampling, and nucleus sampling. beyond the incomplete decoding algorithm originally put for- ward by Welleck al. (2020). We then propose non-monotonic ooff-terminaiig language model, which significantly relaxes the constraint of monotonically in- creasing termination probability in the originally proposed self- seff-terminating lan- guage model by Welleck et al. (2020), to address the issue of non-terminating sequences when using incomplete probable decoding algorithms. We prove that our proposed model prevents non-terminating sequences when using not only in- complete probable decoding algorithms but also beam search. We empirically validate our model on sequence completion tasks with various architectures.
INTRODUCTION
Autoregressive neural sequence models (Bengio et al.) 2000) have been widely used for various nat- ural language generation tasks such language modeling (Brown al. 2020 Chowdhery al., 2022). machine translation (Bahdanau et al. 2014), and conversational dialogue modeling (Vinyals) Le 2015). Furthermore, large-scale autoregressive neural sequence models have shown unprece- dented ability to generate fluent, human-like texts (Vaswani et al.) 2017 Brown et al. 2020). De- spite their success, the autoregressive neural sequence models have shown undesirable behaviors: non-termination (Welleck et al. 2020), degenerate repetition (Welleck et al. 2019 Holtzman et al., 2020), and premature termination (Koehn & Knowles] 2017] [Stahlberg & Byrne (019)). In this
paper, we focus on how to prevent non-termination when using given decoding algorithm.
Non-termination is the problem that language model generates infinitely long sequences with positive probability from our language model when using given decoding algorithm. Welleck cct al. (2020) pointed out that this issue comes from a discrepancy between the distribution of our language model and its induced distribution by incomplete decoding algorithm. They formalized this disparity by the notion of inconsistency where our language model generates non-terminating sequences with positive probability from the decoding algorithm. To avoid this inconsistency, they proposed a self-teennnntting (ST) language model that uses new parametrization for its classifier rather than usual softmax parametrization. They proved that the ST language model is consistent with respect to greedy search, beam search, top-k sampling (Fan et al. 2018) as well as nucleus sampling (Holtzman et al. 2020
The ST language model increases the termination probability of each sequence monotonically to but this parametrization is appropriate for learning our natural language. As an illustrative
1 NNww York University
1 Prrescient Design, Genentech
SCIFAR Fellow
"Corresponding author.

---

Published as a conference paper at ICLR 2023
example, suppose there are two sequences in our dataset: "I am a boy" vs. "I am boy, and you are a girl.". Our language model trained on this dataset may or may not terminate after the former. Once our model decides not to end, it should dramatically reduce the termination probability to tinue. The ST language model, which monotonically increase the termination probability, cannot capture such case, where sequence is prefix of another. We thus propose non-monotonic self-terminating (NMST) language model which guarantees the consistency with respect to greedy search, beam search, top-k sampling, and nucleus sampling without monotonically increasing ter- mination probability.
The NMST language model encourages the termination probability of each sequence converge to through NMST parametrization however without monotonicity. Even under this relaxation, the proposed NMST language model provably prevents any non-terminating sequence resulting from greedy search, beam search, top-k sampling, and nucleus sampling, which we refer to as incomplete probable decoding algorithms.
We conduct experiments validating the effectiveness of our NMST language models on sequence completion tasks, as was done earlier studies. We test NMST parametrization with various ar- chitectures. Specifically, we train RNN (Elman 1990) and LSTM (Hochreiter & Schmidhuber, 1997) on WikiText-2 (Merity et al. 2016). We additionally finetune GPT-2 (Radford et al., 2019) on WikiText- (Merity al. 2016). Across all these setups, NMST parametrization effectively prevents non-terminating sequences, especially when compared to softmax parametrization. Fur- thermore, we see that our NMST parametrization has better (lower) perplexities than those of ST parametrization, confirming the importance of relaxing the monotonic termination probability.
2 NOTATIONS AND BACKGROUND
2.1 NOTATIONS FOR AUTOREGRESSIVE NEURAL SEQUENCE MODELS
Sequences, vocabulary, and (cos) We view an instance (e.g., a sentence and a paragraph) as a sequence y (y1, .,,..., yr), where each y/ is an element from a pre-defined finite set of discrete tokens, referred to as a vocabulary V. V includes a special symbol (eos) that only appears at the end of the sequence. Every sequence y must end with (eos). We write the length of y as ly), and B1y = (eos). We call y non-terminating sequence, [y = co, if ys * (eos) for all t.
Embedding vectors Each token E is not numerical vector so that we use an embedding vector Uy E IR' to represent v. To capture the notion of similarity between discrete tokens efficiently, we use an embedding vector u I Td to project v into continuous embedding space (Bengio et al.
2000 Mikolov et al., 2013b at Levy & Goldberg 2014).
Autoregressive neural sequence models Bengio al. (2000) proposed an autoregressive neural sequence model parametrized by 0 E IR= They factorized Po into product of the conditional probability of each token given all the previous tokens and an input a predefined order as follows:
(o(y) x I Po (o
(1)
where yer t-prefix of y and æ is an input referred to a context. For example, æ represents either a prompt in sequence completion or source-side sequence in machine translation.
There are several popular architectures for Po such RNN (Elman 1990), LSTM (Hochreiter & Schmidhuber 1997). GRU (Cho et al. (004)). and Transformer (Vaswani et al.] 2017). As shown in equation 2 all these models utilize softmax classifiers. In this paper, we modify the parametrization of their softmax classifiers to prevent non-terminating sequences. We thus write a vanilla language model, regardless of its choice of architecture, that uses the original softmax parametrization as pb defined in Definition
Definition A vanilla language model pb computes the conditional probability of each token given a t-prefix ye and context x at each time step t. as follows:
va (y:- = v u|yet, x)) = exp(u, h2)/ Evey exp(u,,hi))
(2)
where h2 fo(ye, 11-1) with ho
This definition stands for RNN, LSTM, and GRU. For Transformer, h, = folye, h))(t-)))
2

---

Published as a conference paper at ICLR 2023
Training For a given dataset, = (ax(m),
()(+))) |n we maximize the joint probability assigned
to the sequences in our training dataset to find an optimal parameter configuration 0* as follows:
arg maxe Σ
2 r=
log (yi
(v: (/2 ..!)).
2.2 INCOMPLETE PROBABLE DECODING ALGORITHMS
An autoregressive language model pe predicts the likelihood of a sequence y given context æ. Its autoregressive factorization in equation requires recursive process for every t to infer. Hence, at inference time, we use a decoding algorithm, defined below, to generate sequences from po-
,UT) , where T E (1.2.... and yt E V. A decoding algorithu S is a function that maps pe to (S(pe) which is a probability distri- bution over y. A decoded sentence ÿ given x by S from po a random sample from (S(pe) ( (z).
Definition 2. Lei y be collection of such that y (y1, 1/2-
To generate high quality sequence from pe. a decoding algorithm assumes that higher quality sequence has a higher probability of pe than others. For instance, maximum a posteriori (MAP) decoding algorithm Smop gives the most probable sequence y² given a context æ from pa:
y" arg maXyey po (y](2))
by setting (Po)g - y" x) Unfortunately. Smap is intractable since equation 4 requires exhaustive search over the sequence space y. Hence, in practice, we utilize incomplete probable decoding algorithms defined as follows:
and q (po) (y - y'(x) = 0 where y' E y {
Definition 3. A decoding algorithm S is incomplete and probable there exists V. V such that
Evey, (S(pa) (y: = vly 2t) =1
(5)
and
min.ev, Po( = v/y<r. 2 max Po(u: = vlyee,
(6)
for each t. Furthermore, for every v E V4, satisfies
[s(pe) u/ yet. x) 2 po vlyer,
At each i, an incomplete probable decoding algorithm considers only set highly probable tokens, V/- S generates ÿ given by recursively sampling from (s(re) (3ll,<e, æ)) supported on
V.. This reduces an exponential complexity of Smap. O (1V)l down a linear level, O (lğ) V))-
Greedy search, top-k sampling (Fan et al., 2018), and nucleus sampling (Holtzman et al. 2020 are incomplete and probable. For example, greedy search Sn, generates the t-th item of a sequence by
Uc = arg max,ev (V: = 0/3 2))
(8)
In other words, Sgr sets Vi to {zt where of arg max.ev po po E/u x). Moreover, have Pe (y+- = 2 (1) ()<,, xx) I (vo) (vt- u x) 1, and (S,- (V+ e' (' 0
holds for e' E V \ V. Thus, Syr is incomplete and probable. Unlike Sgr. top-k sampling considers most probable tokens in V as V; while nucleus sampling sets the smallest subset of V, containing most probable tokens of which total probability is higher than a given threshold jr, to V,. In $A.1
and A.2
we present that top-k sampling and nucleus sampling are also incomplete and probable.
Beam search is heuristic algorithm that operates on the level of prefixes. We describe it further in Although beam search not an incomplete probable decoding algorithm, also selects V, which is a proper subset of V to expand each prefix at each step Due to this, our main theoretical finding for the incomplete probable decoding algorithms in $ is applicable to beam search as well.
A.3
2.3
CONSISTENCY WITH RESPECT TO INCOMPLETE PROBABLE DECODING ALGORITIIMS AND SELF-TERMINATII (ST) LANGUAGE MODELS
Incomplete probable decoding algorithms greatly reduce computational overhead for generating se- quences from model. However, Welleck al. (2020) observed that they can generate non- terminating sequences even every training sequence has a finite length. To study this, Welleck] et al. (2000) defined consistency with respect to decoding algorithms shown in Definition
3

---

Published as a conference paper at ICLR 2023
Definition 4. A language model pe is consistent with respect to decoding algorithm S if (BB) = 00) for any parameter configuration E R
Welleck et al. 2020) also proved that a vanilla language model p defined in Definition 1 is incon- sistent with respect to incomplete probable decoding algorithms and beam search as follows:
Theorem 1. vanilla language model Po defined in Definition is inconsistent with respect to any incomplete probuble decoding algorithm and beam search (Theorem 3.4 in Welleck et al. (2020)) )
For each t. an incomplete probable decoding algorithm S selects V: Ç V as a set of candidates for decoding, but P' does not guarantee that (eos) E V4- Specifically, if (eos) & V, for all I. then S cannot decode each token to (eos) for all I. (i.e., non-terminating). Based on this result, Welleck et al. (0200) proposed self-terminating (ST) language model, defined below:
Definition 5. For he defined in Definition I the conditional probability of each token E V given a l-prefix yet and context a at each time step an ST language model given by
at = =pē (y/+ (cos) = -T- c). ou (ouToashuu he),
and
po (ye- = vlyee, = (1 aa) -exp(u. h4)) / (VV(((os)) exp(u,,ha), where u E V. ((cos)), E (0, 1), and (x)) + exp(-x)) is a sigmoid function.
They proved that the ST language model is consistent with respect to any incomplete probable decoding algorithm and beam search, as follows:
Theorem 2. An ST language model pg defined in Definition 5 is consistent with respect to any in-
complete probable decoding algorithms and beam search (Theorem 4. 1-4.3 in Welleck et al.) (2020)
In equation Pe (y: (eos) V<t, 2:) monotonically increases to 1 & increases. S ends up including (eos) in V; always for t 2 t' with some t', and lim;-+00 (S(ps) (yt = (eos) y x)
by equation 7 This guarantees S to terminate in a finite number of steps. Despite pat's consistency, its validation perplexity degrades compared pg in sequence completion (Welleck et al. 2020). We suspect that such degradation comes from the core property of pø that (o = (cos) y x) monotonically increases to as increases. In Remark T helow, we provide an example where the optimal po- (yi= = (cos)|y<t.
V=t, 2) is not monotonic.
Remark 1. Let D (x ()), ,y(2)) be two-instance training dataset. Assume that there exists to such that yeto Vetoo = Veto- Suppose further that to -1 < (2) 1
(2)
and (1) (2). , 0* is an optimal parameter configuration in equation over D. Then,
pa- (y)² (2) = (eos) yet x) is not monotonic with respect to t (proved in
We can easily find such case in natural language satisfying the assumptions in Remark 1 by concate- nating two sequences. We empirically demonstrate the existence of such cases in 4.2
NON-MONOTONIC SELF-TERMINATING (NMST) LANGUAGE MODELS
The consistency of rgl comes from lim r 18'(1, = (eos)|yee,,) .) 1. not the monotonically increasing p (yt- = (eos) ycc, x) as a function of t. This motivates us to propose a non-monotonic
self-terminating (NMST) language model pg pmsst that permits pe m (y:
(cos) y (
x) to be
non-monotonic function of while satisfying lim,-se pomss (yr = (cos) y x)) = as follows:
Definition 6. For h defined in Definition[] the conditional probability of each token given t-prefix yet and a context x at the t-th step in an NMST language model is defined by
at = P9 nmst (yt = (eos) yce. x)) (1 (u le)) (1 (1- ) + (u he),
(10)
and
pr (y+- = v/y<e. = (1 aa)) exp(u h2)/ (nl//veeye Evee)((oo)) explu he)) where u E VV ((e0s)} E (0, 1), and (x) (1 + exp( ())( -1 is a sigmoid function.
4

---

Published as a conference paper at ICLR 2023
Prob.
1.0
funlt)
1 x(2
g(t)
0.5
fu(()
10 where fis(t) = e)a² (ye- (cos) V<tt 2:). If g()) lies between fi and [tt( we can find X((') such that g((") = (1 ((s)) ((")) (uo"") for any regardless of whether g(t) is monotonic with respect to This allows po pgmst to learn non-monotonic behavior of pg (yr- = (eos) Vcc. x). Pe pa is consistent with respect to any incomplete probable decoding algorithms and beam search due to lim (tt
Figure 1: An illustration of NMST parametrization in equation
(t) 1, X(t') a (e and g(t) = Pe me
lim Pg pamst (ze- (eos) yct, x) = 1.
Figure shows that Pg pg uses convex combination of two curves to model Pe pgmst (ye = (eos) Bct, We can write a curve g(t) between lower-bound curve (t) and an upper-bound curve (t) as g(t) = (1 fi()) + ((t)fub(t) with appropriate X(t) E (0. 1) for all t. Pe nastt sets (t) to Pe apmst (ye (cos) Vet, Φ), and then regards it as a convex combination of (()(() = (1 (1- and (1) = with coefficient X(I) = o (cas)
(uTsss)) ht). This enables non- monotonic pe pemat = (eos)|y<t x). Moreover, in Theorem below, we show that the proposed
NMST parametrization in equation still guarantees the consistency with respect to any incomplete probable decoding algorithms and beam search.
Theorem 3. An NMST language model defined Definition is consistent with respect to any incomplete probable decoding algorithms and beam search
Theorem guarantees that every decoded sequence from Pa prnnst terminates when using incomplete decoding al algorithms and beam search. Neither pgmss nor Pg results in non-terminating sequences resulting from incomplete probable decoding algorithms and beam search. Unlike ST parametriza- [ tion, our NMST parametrization in equation [1] capture wider range of po (cos) y x),
since pg does not assume that (1 = (Eos)) yyt,, x)) is a monotonic function of L. We em- pirically demonstrate this by comparing pb (vr. (eos) yeu, æ). Po (y+ (eos) (eos))yeer,e y-er, a), and po aams (y/+ = (eas))1<<1, Ier,, 2) Figure
EXPERIMENTS
We empirically validate the effectiveness of the proposed non-monotonic self-terminating (NMST) language model by evaluating it on sequence completion tasks. We test three variants of given architecture: (i) vanilla (VA+) language model using common softmax parametrization in equa- tion 2 (ii) a self-terminating (ST+) language model using ST parametrization proposed by Welleck al. (2020) and (iii) our non- monotonic self-tteninating (NMST+) language model using NMST
parametrization in equation 10
We use following evaluation metrics for comparison:
Perplexity: Given an autoregressive language model pe. the perplexity of pe over D is exp
N EN Eie log (y(")
(n) (n) yet : ((()))
ad(i)) where D {=<(n) ( )
Non-termination ratio (ra)): To present the consistency of po with respect to given decoding algorithm S, we need to compute r.a = (S(re) (lyl = oo). Instead, based on
= (S(po) (lyl = oo) = lim (S(po) (lyr > L),
(11)
L
we Tut (L. [S(re) (1yl L) with sufficiently large threshold L to estimate I'tt-
Sequence completion a task of predicting continuation ý given a c-length context (I), .2. ,.e) by using decoding algorithm S from language model pe (i.e. ÿ (S(po) (S(po)(y|xx)
We provide the proof in $C
5

---

Published as a conference paper at ICLR 2023
0-3
NMST
NMST
ST
BAIL
5.0 10
5.0 10
100 10
1.0
0181
5.0.X 10
0/01
5.0 10
10x 10
1,0 10
VA+
VA-
00
100
100
102
100
100
10r
109
162
109
19
(a) RNN
(b) LSTM
Figure 2: Non-termination ratios, The (.)ss, function of T. in log-log scale for (a) RNN and (b) LSTM trained on WikiText-2 when using greedy search. We report mean (curve) + st.dev. (shaded area) across 10 random experiments. For all configurations, both ST+ (non-red dashed) proposed by Welleck et al. (2200) and our NMST+ (non-red solid) are consistent with respect to greedy search since Tie (L) goes 0 L increases. However, softmax parametrization (VA+, red dotted) is inconsistent with respect to greedy search since its (L) does not converge to 0 as L - oc.
In this section, we use greedy search defined in equation retical finding in Theorem 3is that the proposed NMST language model is consistent with respect to not only greedy search but also top-k sampling, nucleus sampling, and beam search. We thus present results when using decoding algorithms other than greedy search at the end in and $
g to generate ÿ given æ. Our main theo-
4.1 WIKITEXT-2
WikiText-2 (Merity et al. 2016 consists 2 million words from 600 Wikipedia articles. With word tokenization, regard the first 10 tokens of each sequence and its remaining part, context æ and a ground truth y. respectively. We train RNN with tanh (Elman 1990) and LSTM (Hochreiter & Schmidhuber 1997) on Wik Both RNN and LSTM have 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 Adam (Loshchilov Hutter] 2017) with initial learning rate of 0.001, B1 0.9, 32 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+ UT+(RNN, LSTM) and NMST+(RNN) LSTM) need an additional hyperparameter We explore e in (1.0 10-5, 5.0 10-5 1.0 x 10-4, 1, 5.0 x 10-1).
We present the average (+st.dev.) non-termination ratios, (L)'s) across 10 random runs function of L for all considered setups of WikiText-2 in Figure 2 using greedy search. From equa- tion 11 language model is consistent with respect to greedy search if lim T'r (L) = 0. As L increases, we observe that rwr( (L)s of VA+ (RNN, LSTM) fail to converge toward 0 while Tne (L)'s of ST+NNNN, LSTM} and NMST+ LSTM} all reach O. 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 ST parametrization.
Table T shows that the average (=st.dev.) validation perplexities across 10 random experiments for all variants of RNN and LSTM, trained WikiText-2. We observe that NMST+ LSTM) have better validation perplexities than (RNN,NN, LSTM} for every e. We demonstrate this more clearly in E by plotting the evolution of the mean validation perplexities 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 of NMST+ e increases, the lower bound of pommst (yt = (eos)|Bert, x) grows faster, yielding premature sequences when e too large. Indeed, the average validation perplexities of NMST+RNN and NMST+LSTM with 5.0 x 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 e = 1.0 x 10-3 that makes NMST+ LSTM) have the validation perplexities similar to those of (A+NNNN, LSTM). In short, both NMST+ and ST+ prevent non-termination when using greedy search but only NMST+ has competitive validation perplexity against VA+. In S further observe that the length distribution predicted sequences from NMST+LSTM is closer to the length distribution of ground truth sequences than those of predicted sequences from (VA, STSML
we vary e. Although

---

Published as a conference paper at ICLR 2023
Table 1: Mean (+st.dev.) validation perplexities across 10 random runs on WikiText-2 for various model configurations. Lower is better. Bold marks the best of each architecture. For all e, the vali- dation perplexities of our NMST+(RNN, LSTM] are better than those of ST+ (RNN, LSTM} pro- posed by Welleck et al. (2020). Moreover, with a proper choice of c = 1.0 x 10-5, NMST+(RN) LSTM) have competitive validation perplexities against those of VA+ LSTM).
RNN
LSTM
ST+
NMST+
ST+
NMST+
5.0 X 10-4
186.1 + (6.2)
184.2 (6.5)
106.1 (1.0)
105.6 = (1.2)
1.0 X 10-4
181.0 = (3.8)
177.4 (7.0)
(1.4)
102.5 = (1.0)
5.0 X 10
182.6 = (8.0)
179.6 (5.7)
104.77
102.1 = (1.0)
1.0 x 10-5
180.4 + (3.3)
177.4 + (4.5)
+ (1.4)
101.5 + (0.8)
VA+
178.6 + (6.3)
101.6 + (1.0)
We present the average (#st..dv.) validation perplexities across 10 random runs for all variants of GPT-2 finetuned on WikiText-10S. 103. We also demonstrate their terminamintno ratios (mean=sst.dv..,, I'm (L'ss, when using greedy search. We set L to 1,000 since the maximum length of generated sequences from GPT-2 1,024. For perplexity, lower better. Bold marks the best validation perplexity in all setups. For every e, NMST+GPT-2 outperforms ST+GPT-2 in terms of NMST+GPT-2 effectively prevents non-tert con-termination sequences compared to VA+G for every while ST+GPT-2 with small fails to avoid them. With a proper choice of c (e.g.. c = 1.0 x 10 10-5), NMST+GPT-2 improves the validation perplexity.
Table 2:
the average validation perplexity. From
Perplexity
Fne (L)
ST+
NMST+
ST+
NMST+
5.0 X 10 10-4 4
21.80 = (0.02)
21.63 : (0.02)
0.05 (0.03)
0.07 + (0.03)
1.0 X 10
21.21 = (0.02)
20.86 (0.02)
0 0.12
5.0 X 10
21.19 (0.03)
20.76 (0.02)
0.24
1.0 X 10-5 5
21.16 = (0.03)
20.69 + (0.03)
0.75 - (0.10)
0.23 (0.10)
VA+
20.72 (0.03)
0.27 + (0.08)
4.2 WIKITEXT-103
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 Adam (Loshchilov &
Hutter 2017) with an initial learning rate of 5.0 x 10 5 B1 0.9, B2 0.99, weight decay of 0.01,
linear learning rate decay, and early stopping. We present a more detailed description in $ We select from [1.0 x 10 10-3.5.00 x 10 1.0 x 10-4, 5.0 10 4] for ST+GPT-2 and NMS2+GPT-2.
We report the mean (dvst.dev.) validation perplexities and non-termination ratios, Fan (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 I. such as T. 10 to determine whether a language model consistent with respect to greedy search. Although L. = 1 1,000 is not sufficiently large, we observe that (..) of NMST+GPT-2 decreases compared to rxe (L) of VA+GPT-2 as 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 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 repe- titions of similar phrases and ending with (eos). We present more example continuations in R..
7

---

Published as a conference paper at ICLR 2023
Table 3: Given a context in validation instance of WikrText-103, we present example continua- tions of [VA, ST. +MPT)+ when using greedy search. We select e = 1.0 x 10 for {ST, NMST)+ because +TPT-, NMST+GPTT- improves the quality of the sequence by avoiding repetitive tokens and ending with (eos) when the given context leads VA+GPT-2 to non-terminate within 1, 000 steps.
optimal in terms of validation perplexities in Table
Unlike {VA,
Context
Made of concrete, steel, and wood, the
VA+
building was built in the mid @-@ 19th century. It was the first building the United States to be built in concrete, and the first to be built in wood. It was also the first building in the United States to be built in steel. It was the first building in
ST+
building is constructed of steel and concrete. The building's 's exterior is made of steel and concrete. The building's interior is made of wood, and the building's exterior is made of concrete. The building's 's exterior is made of concrete, and the building's
NMST+
building was designed by the architectural firm of Bowers & Wainwright, and was completed in 1892. The building the largest of its kind in the United States. (eos)
On Dicamber 2010 Kindhow macried
CWGC Sandquerieed in Maishnlanel Enghadd
N 11
39
THEPES pP
Figure 3: We present pe (y (eos) v) function of t for validation instances of WikiText- 103 where po 's are [VA, ST, NE.NMMT++GPP23 For (ST, NMST)+ we choose = 1.0 x 10-5 because it is optimal in terms of validation perplexities in Table 2 Instead of t, tag the 1-th ground truth token. We report their mean (curve) st.dev. (shaded area) across 10 random runs. Unlike ST+GPT-2, NMST+GPT-2 can model non-monotonie behaviors of Pa (eos))yy<t, x) with respect to t. Both plots show that the non-monotonic behaviors occur where the sequences could end (e.g., after red marked tokens such as periods).
Similar to the results in $4.1 Table 2 shows that the validation perplexities of both ST+GPT-2 proposed by WWlleck et al. (2020) and our NMST+GPT-2 degrade compared to VA+GPT-2 increases. NMST+GPT-2 with the optimal 6 = 1.0 x 10-5 has a competitive validation perplexity of 20.69 against that of VA+GPT-2, 20.72. On the other side, cannot find that makes the validation perplexity of ST+GPT-2 competitive against that of VA+GPT-2. Moreover, if c * 5.0 x 10-4, then Tne(L)'s of ST+GPT-2 blow up unlike (L)'s of VA+GPT-2. $ demonstrates the inevitable perplexity degradation and exploding (L) of ST+GPT-2. We suspect that it is due to monotonically increasing po (y: (eos)] x) with respect to
We investigate behaviors of po (B) = (eos) where po's are [VA, ST. NMST]+GPT-2 in Figure 3 Based on Table 2 we select the optimal
1.0 10-3 in terms of validation per- plexities for (ST, NMST)+GPP-2. In Figure 3 (VA, NMST)+GPT-2 well-capture whether a se- quence 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 pe (y= (eos) lyer, 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 T than VA+GPT-2 for small L, but Tra (L) = for sufficiently large L). We demonstrate more behaviors E.4
CONSISTENCY WITH RESPECT TO OTHER DECODING ALGORITTMS
We explore the effectiveness of our proposed non-monotonic self-terminating (NMST) language model when using decoding algorithms other than greedy search, such top-k sampling (Pan al.)
8

---

Published as a conference paper at ICLR 2023
Table 4: Mean (+st..dv.)) non-termination ratios, I'xt (L)',, across 10 random runs for the variants of GPT-2 finetuned on WikiText- 103 with various decoding algorithms, We set L to 1,000 due to GPT- 2's context window size of 1,024. We use the optimal = 1.0 x 10-5 in terms of average validation perplexities in Table 2 for both NMST+GPT-2 and ST+GPT-2. Bold marks the lowest r' (L) within each decoding algorithm (column). Similar to greedy search in Table [ for all decoding algorithms, T't (L)'s of NMST+GPT-2 are lower than those of ST+GPT-2 and VA+GPT-2. It means that NMST+ reduce the number of non-terminating sequences within 1,000 decoding steps.
top-2
top-4
nucleus-0.2
nucleus-0.4
beam-2
beam-4
VA+
0.0 (0.0) 0.0 (0.0)
0.25 + (0.08)
0.14 (0.05)
0.05 = (0.02)
0.03 - (0.01)
ST+
0.0 (0.0)
0.0 (0.0)
0.73 + (0.11)
0.55 = (0.15)
0.29 + (0.10)
0.15 (0.07)
NMST+
0.0 - (0.0) 0.0 (0.0)
0.21 = (0.10)
0.10 = (0.06)
0.03 = (0.02)
0.01 = (0.01)
2018), nucleus sampling (Holtzman et al. 2020), and beam search. All experimental setups and notations are the same as Section $4 According to Theorem B the NMST language model is consistent with respect to any incomplete decoding algorithms (c.g., greedy search, top-k sampling, and nucleus sampling) and beam search for all c > O. To validate this, we use top- 4] sampling, nucleus- (0.2, 0.4) sampling, and beam search with width of {2. 4] (beam- 4)) to generate sequences from NMST+GPT-2 finetuned on WikiText- 103 with c 1.0 x 10-5 The choice of c = 1.0 x 10-5 is made based on the validation perplexities in Table 2 Since the validation perplexity does not depend on decoding algorithms, we focus on the average (tstddev)) non-termination ratios, Tne (L)ss, 's across 10 random runs with L 000 for each decoding algorithm in Table 4 We also present Fin (L)'s 's of VA+GPT-2 and ST+GPT-2 with e = 1.0 x 10 as baselines.
Table shows that our NMST+GPT-2 has the lowest (L) with L = 1, 000 for all decoding algorithms compared to VA+GPT-2 and ST+GPT-2 proposed by (Welleck et al., 2020). In other words, NMST+ effectively prevent non-terminating sequences within 1,000 time steps regardless of decoding algorithms. Comparing with greedy search in Table 2 (r.r (L) when e = 1.0 x 10-5), we observe that T'a (L)'s decrease for all setups. As we discussed in 2.. non-terminating sequences originate from the choice of (eos) & V2 Ç V for all 1 where V is a vocabulary and V, is the 1-th proper subset of V. considered by decoding algorithm at the f-th step. The decoding algorithms other than greedy search are likely to have (eos) in Vú and have the lower (L) since their [ are greater than or equal to V.. =1 of greedy search for all t. In the case of top- (2, 4) sampling, we obtain Tne (L) = 0.0 for VA+GPT-2. Even without NMST+, VA+ can avoid non-terminating sequences we choose a proper decoding algorithm. We however emphasize that NMST+GPT-2 with 1.0 x 10-5 has a competitive validation perplexity against VA+GPT-2 in Table 2 and that it is guaranteed to terminate regardless of the choice of a decoding algorithm. We also empirically demonstrate the consistency of NMST+(RNN LSTM} trained on WikiText-2 with respect to other decoding algorithms in {F
6 CONCLUSION
con-termination is a degenerate behavior we often observe when generating text from well-trained language model. To prevent this, Welleck et al. (2020) proposed a self-terminating language model that encourages the termination probability of each sequence, which is the conditional probability of (cos) given a t-prefix and a context, to monotonically increase toward 1 as & increases. In this paper, we theoretically demonstrate that monotonically increasing termination probability of each sequence is not necessary condition for avoiding non-terminating sequences. We then propose a mon-monotonis self self-terminating language model where the termination probability for each se- quence converges to I but not monotonically, Our non mon-montonic self seff-terminatin language models successfully address the issue of non-termination and achieve perplexities that are comparable to vanilla language models and are better than the original self-terminating language models.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our paper, we provide our code available httpts://g
ACKNOWLEDGMENTS
This work was supported by 42dot, Hyundai Motor Company (under the project Uncertainty in Neural Sequence Modeling), Samsung Advanced Institute of Technology (under the project Next Generation Deep Learning: From Pattern Recognition to AI), and NSF Award 1922658 NRT-HDR: FUTURE Foundations, Translation, and Responsibility for Data Science. This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise.
REFERENCES
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. arXiv preprint arXiv:1409.0477 2014.
Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Janvin. A neural probabilistic language model. Mach. Learn. Res., 2000.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv:1409, 1259, 2014.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, al. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311 2022.
Jeffrey I. Elman. Finding structure in time. Cognitive science, (((2):19-211, 1990.
Angela Fan, Mike Lewis. and Yann Dauphin. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume Long Pa- pers), pp. 889-898, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653/v 1/P18- 1082. Utt http:::///aaaha/aaaa//aaaaaa/aot how. wtt.ollg..ooo111111
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997.
Ari Holtzman, Jan Buys, Maxwell Forbes, and Yejin Choi. The curious case of neural text degener- ation. ArXiv, abs/ 904709911 2020.
Philipp Koehn and Rebecca Knowles. Six challenges for neural machine translation. arXiv preprint arXiv:1706.03872 2017.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. Advances in neural information processing systems, 27, 2014.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. 1rXiv:1711.05101 2017.
arXiv preprint
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv: 1rXiv:1609.07843 2016.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. arXiv preprint 13 2013a.
10

---

Published as a conference paper at ICLR 2023
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeff Dean. Distributed representa- tions of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013b.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, lly Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8)99 2019.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units, arXiv preprint arXiv:1508. arXiv:1508.0790%, 2015.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov.
Dropout: simple way prevent neural networks from overfitting The journal of machine learning research, 15(1):1929-199) 1958, 2014.
Felix Stahlberg and Bill Bymee On nmt search errors and model errors: Cat got your tongue? arXiv preprint arXiv: 1908,00000 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Oriol Vinyals and Quoc Le. neural conversational model. arXiv preprint
2015.
Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston. Neural text generation with unlikelihood training. arXiv preprint arXiv:1908.0433 043199 2019.
Sean Welleck, Ilia Kulikov, Jaedeok Kim, Richard Yuanzhe Pang, and Kyunghyun Cho. Consistency of a recurrent language model with respect to incomplete decoding. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 5553-5568, Online, November 2020, Association for Computational Linguistics. doi: 10.18653/v 1/2020. emnlp-main.o 448. URL httph:tt://// http://////aaaahooooo.o org/ emplp ma in, 448
11

---

Published as a conference paper at ICLR 2023
APPENDIX
A DEFINITIONS OF COMMON DECODING ALGORITTMS AND THEIR CHARACTERISTICS
In this section, we present mathematical definitions of top-k sampling (Fan et al. 2018), nucleus sampling (Holtzman et al. 2020), greedy search, and beam search. We then demonstrate whether they are incomplete probable decoding algorithms.
A.1 TOP-K SAMPLING
At each step f, top-k sampling selects subset of k most probable tokens in vocabulary V. Top-k sampling generates decoded sequences from a language model pe as follows:
Definition A.1 (Top-k sampling (Fan et al. 2018).. Top-k sampling Sup-k generates a sequence from a language model po given context by recursively sampling in from
po(yt = v1D<1,
if E Vv,
9. (po) 2()))
Even pa v v'(úct,0))
(12)
otherwise,
where
V; = arg top-k ( v ((),, a.).
(13)
wv
Except the trivial case k [V/, we have 0 & V4 S V for all t. By equation 13 equation 6 holds.
From equation 12 we see that top-k sampling satisfies equation 5 and equation Therefore, top-k
sampling is incomplete probable decoding algorithm.
A.2 NUCLEUS SAMPLING
At each step I, nucleus sampling selects the smallest subset of most probable tokens in a vocabulary V. of which total probability higher than a given threshold μ.. Nucleus sampling generates decoded sequences from a language model as follows:
Definition A.2 (Nucleus sampling (Holtzman et al. 2020 Nucleus sampling Smnc generates a sequence from language model pe given a context æ by recursively sampling Dr. from
po(u v v<),
if V4:
48m a (U= = 1/ (ee,, 2))
Even, Po(u: = x))))'))'
(14)
otherwise,
where V, is the smallest subset of V such that
Σ DEV.
po(ue v/see, 2
(15)
If min.ey Pa (3 vlyer, 1 μ for any context and any t-prefix yer, then have 0 ç V4 Ç V for all t. Suppose that equation 6 does not hold for nucleus sampling. Then, this contradicts V is the smallest subset V, satisfying equation [5] From equation 14 we see that nucleus sampling satisfies equation 5 and equation 7 Therefore, nucleus sampling is incomplete and probable.
A.3 BEAM SEARCH
Beam search is heuristic algorithm that operates the level of prefixes. We the definition of beam search in Welleck et al. (2020).
Definition A.3 (Beam search, Definition A.2 in Welleck et al. (2020)) Beam search with width (beam size) k. Sheam ks generates sequence from language model po by maintaining of
12

---

Published as a conference paper at ICLR 2023
prefixes, Pi = (t) (t), for all i. At each step E f1,2.
(t)), at each time step t where (0) is an empry prefix beam search forms a set of k x l prefixes,
p. U PEP
( V((p)),
(16)
where po is concatenation and
V((p) arg top-k (y v).. vEV
(17)
After forming Pt, beam search selects set of the k highest scoring prefixes in Pe.
Pt = arg top-k sp)),
(18)
PEP.
where s(p) E' log poly- Pr) x). If p E Pt ends with (eos), then does not expand further and is added to the final set P. Beam search continues until P contains k sequences ending with (eos). After that it returns the highest scoring sequence
ÿ = arg max sp).
(19)
PEP
Unlike greedy search, top-k sampling, and nucleus sampling, beam search recursively expands sequences with at most & different prefixes. Therefore, we cannot formalize beam search in token- level by using 9S (Bt uly<c, x). However, in equation [7 the number of possible tokens at t is most & k. It means that Steam-k may exclude (eos) time ć if S vMV -I. By using this, Welleck et al. (2020) proved that vanilla language model pa is inconsistent with respect to beam search as shown Theorem
B PROOFS FOR 2.3
(x(2), Remark I Let D = (1) (2)), (x(()) (21) be two-instance training dataset. Assume that
there exists to such that yeto Ycu = Yeh. Suppose further that to (2) < [2)
and (1) (2)) 0r is optimal parameter configuration in equation over D. Then,
pa (y) (2) = (eos) yer x) is non-monotonic with respect to t.
(2)
Proof. Since is an optimal parameter configuration that perfectly minimizes equation and to < (g(2) (2)
1, we have
(2) Pg- (yt (2) (Eos) y 2t (2)) 0,
(20)
for < to. Note that to || Vio
(1) (eos) and to 2
y12) + (cos). From
x (2) and y youoo cto obtain
(1) (2)
Po- (yie
(2) (cos) 1y
(2) 2t x
(21)
Moreover, to (2 implies that y Meot * (cos) which is equivalent
(2)
Pg- (v.o+1 = (cos) 2 x (2)) = 0.
(22)
From equation 20
equation
21 and equation
22 we see that po- (ui²) (eos)/y is non-
monotonic with respect
C PROOFS FOR $3
Theorem A non-monotonic self self-terminating (NMST) language model defined in Definition is consistent with respect any incomplete probable decoding algorithms and beam search.
13

---

Published as a conference paper at ICLR 2023
Proof. From equation 10. for any 0 R we have
lim Po
nmst
(yt (eos) yock, x) =1
since (1 e)) + 0 as + oo for e E (0 and a (wooos) m2) E {0,1) for any t. Hence, there exists
f2/2 such that
(y/ ( 1
2 f1/2 + Po mm
(23)
Let S be any incomplete probable decoding algorithm. From equation 6 and equation 7 (eos) E Va and 9s(pgmet)(() (yt * (eos) Wy<t. x) holds for any 2 f1/2. Therefore, we obtain
(5(ngmor)( (1y) = co/az) = II (s (ye * (eos))B<<,,
4s(pgmar)(04 + (eos) (800))
t /2
2 + 0.
(24)
Taking expectation of equation 24 over æ, we finally have (s(ggmer) o0) = 0 for any S. In other words, pa pustt is consistent with respect any incomplete probable decoding algorithms.
In the case of beam search Speam-k defined in A.3
without loss of generality, there exists E Ptaya
such that p does not end with (cos)- Let P (p) be set of k highest scoring sequences continued from p by Speam.k. From equation
23
we have
Po
nmmt ( (feos) p.x) > Po nmst (vlp. x)
for all v e V {- Hence, Vayaa (p) in equation any subsequence with 21 * (eos). Then, we have
.. .1) be 17 includes (eos). Let z = (21, "1,
Po
rmms( (p p.))
II i=
Pb
mtst
(2ilp x))
S Pe
nusst
[31 p, x))
pe mmst
(feos) x)) po mpmt(pp p,os))(,z))
(25)
where is concatenation.
Therefore, p o (eos) arg maxp'EP,, s(p') holds where s(p') (pl, (t). That is, po (eos) is the highest scoring sequence starting with p. and we have p (Eos) E P(p).
Et= log po (p
For each p' E (x));2()) \ {p (eos) p' starts with po v for v E V \ {eos)) By the same argument, we add at least one sequence ending with (eos) to (p). . It means that p>t,z( has sequences ending with (eos) within 11/2 + k steps. Note that the final set satisfies
P CCC U P (p).
(26)
PEPt1/2
Equation 26 implies that every sequence in P has the length of at most t1/2 + We thus obtain
ISwama (pg (1yr = xo (x) S @m mog (lyr > 11/2 + k xz) 0.
(27)
Taking expectation equation 27 over æ, we see that 4Smome m (1yr oo). That is, p amst consistent with respect to beam search.
II' there such p. all & sequences in Ptyya end with (eos). It means that Smam- returns finite sequence, that po pomae is consistent with respect beam search.
14

---

Published as a conference paper at ICLR 2023
D EXPERIMENTAL DETAILS
In this section, we describe our models and optimization processes used in $4
RNN and LSTM on WikiText-2 We use word tokenization for WikiText-2. We train RNN with tanh activations (Elman 1990) and LSTM (Hochreiter & Schmidhuber 1997) WikiText-2. Both RNN and LSTM have layers. Each layer has 256 hidden units for RNN and 512 hidden units for LSTM. The sizes of input and output embedding layers 256 and 512 for RNN and LSTM, respectively. We use weight tying to share the weights between the input and output embedding layers for both models. We apply dropout (Srivastava et al. 2014) with drop probabilities of 0.3 and 0.5 to RNN and LSTM accordingly. For each model, we perform 10 random runs with a batch size of 32 for 70 epochs. To maximize the log-likelihood presented in equation 3 use Adam (Loshchilov & Hutter 2017) with an initial learning rate of 0.001, 31 = 0.9, 32 0.99, weight decay of 0.01, and learning rate decay which halves the learning rate the validation perplexity does not improve for training epoch. To avoid overfitting, we additionally use early stopping, which terminates training if the validation perplexity does not improve upon the best score attained so far for 10 consecutive epochs. In most cases, the training ends within 50 epochs.
GPT-2 on WikiText-10 103 We use BPE tokenizatior (Sennrich et al. 2015) and the pretrained GPT-1 (Radford et al. 2019) with 124 million parameters, provided by HuggingFacc can handle up to 1,024 tokens. We apply dropout (Srivastava et al., 2014) with a drop probability of 0.1 GPT-2. We finetune GPT-2 for 300,000 steps while ensuring that all runs continue for at least 250,000 steps. To minimize the number padding tokens in every batch for computational efficiency, we bucket the dataset into sequences of similar lengths, and each batch contains maxi- mum of 1,024 total tokens. To maximize the log-likelihood function in equation 3 we use Adam W
GPT-2
(Loshchilov & Hutter 2017) with an initial learning rate of 5.0 x 10 B1 0.9, B2 0.99, weight decay of 0.01, and linear learning rate decay over 500, 000 steps.
15

---

Published as a conference paper at ICLR 2023
E ADDITIONAL PLOTS AND TABLES FOR $
In this section, we demonstrate additional plots and tables for
E.1
ADDITIONAL PLOTS FOR 4.1
INN
LSTM
ST4
VA-
VA+
perpeciity
185
180
175
10-4
10
16-4
Figure 4: Validation perplexities function of in log- lin-linear scale for all configurations of RNN (left) and LSTM (right), which are trained on WikiText-2. We present their average (curve) + st.dev. (shaded area) across 10 random experiments. For all and architectures, NMST+ has better validation perplexities than ST+. As increases, the validation perplexities of both NMST+RNN and NMST+LSTM degrade compared those of VA+RNN and VA+LSTM. We thus need search for an optimal to avoid degradation of validation perplexity when applying NMST+ to our language model.
E.2 ADDITIONAL PLOTS FOR $4.2
NMST
NMST
0.8
ST+
ST+
VA+
VA+
0.6
perpexlity
(L)
23
22
0.2
0.0
10-b
10
10-3
10
10-4
10-4
Figure 5: We present the average (curve) + st.dev. (shaded area) of validation perplexities (left) and non-termnation ratios (L)(L) (right) with greedy search across 10 random runs for all considered setups of GPT-2 finetuned on WikiText-130 in log-linear scale. For (Le(L), because GPT-2 has context window size of 1, 024. For all NMST+GPT-2 outperforms ST+GPT. in terms of the average validation perplexity. When is small, (,, of ST+GPT-2 explodes. It means that ST+GPT-2 with small cannot prevent non-terminating sequences. However, our NMST+GPT-2 effectively reduces The(T. [)) compared to VA+GPT-2 for every c, and the validation perplexity degradation is smaller than that of ST+GPT-2 proposed by Welleck et al. (2020).
L 1, 000
16

---

Published as a conference paper at ICLR 2023
E.3 ADDITIONAL TABLES FOR TABLE
Table 5: Given a context a validation instance of WikiText-103, we present example continua- tions of {VA, ST, NMST]+GPTT2 when using greedy search. We select 1.0 x 10-5 for (ST, NMST +GPT-2 because is optimal in terms of validation perplexities in Table 2 Unlike {VA, +TPT-2, NMST+GPT-2 improves the quality of the sequence by avoiding repetitive tokens and ending with (eos) when the given context leads VA+GPT-2 to non-terminate within 1, 0,00 steps.
Context
The single made its Irish Singles Chart debut at
VA+
number three on the issue date of November 18, 2005. It debuted at number one on the chart for the issue date of December 7, 2005. The single debuted number two on the chart for the issue date of January 4, 2006. The single debuted at number one on the Irish Singles Chart for the issue date of March 4, 2006. The single debuted at number two on the Irish Singles Chart for the issue date of June 4, 2006. The single debuted number one on the Irish Singles Chart for the issue date ...
ST+
number three on the chart issue dated March 16, 2010. debuted at number two on the UK Singles Chart on the chart issue dated March 16, 2010, and peaked at number one on the chart issue dated March 16, 2010. The single was certified gold by the British Phonographic Industry BPI for shipments of over 15 @, @ 000 copies. The single debuted at number two on the Irish Singles Chart on the chart issue dated March 16, 2010, and peaked number one on the chart issue dated March 16, 2010. The single was certified gold by the Irish Recorded Music Association ( (IRMA) ) for shipments of over 15 @ 000 copies. The single was ...
NMST+
number twenty @-@ seven on the week ending March 26, 2010, and peaked at num- ber three on the week ending March 27, 2010. It was certified gold by the Recording Industry Association of Ireland ( RIAA) ) for shipment of 500 @ @ 000 copies of the single. The single certified gold by the Recording Industry Association of Ireland ( RIANZ. for shipment of 500 @ @ 000 copies of the single.(eos)
Context
Despite the expensive reconstructions, both vessels were considered
VA+
to be of sufficient quality to be considered for use in the Grand Fleet. The first, the British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @- @ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @ @ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ built, British @-@ @ built, British @-@ @ built, British @-@ built, British @-@ built...
ST+
be of sufficient quality to be considered part of the Royal Navy, and were as- signed to the Channel Fleet. The two ships were transferred to the Mediterranean Fleet in early 1915, and were transferred the North America and West Indies Sta- tion in early 1916. They were transferred to the Mediterranean Fleet in early 1917, and were transferred the North America and West Indies Station in early 1918. They were transferred to the North America and West Indies Station in early 1918, and were transferred the Mediterranean Fleet in early 1918. They were transferred to the North America and West Indies Station in late 1918, and
NMST+
obsolescent by the time of the Second World War, and were eventually scrapped in favour of the much more powerful British battleship HMS Dreadnought.
17

---

Published as a conference paper at ICLR 2023
Context
On the July 21, 2014 episode of Raw:
VA+
Triple H and Randy Orton were involved in tag team match, in which Triple H and Orton were accompanied by Triple H and Randy Orton's 's manager, Mr. Kennedy. Orton was accompanied by Orton's 's manager, Mr. Kennedy, and Orton's tag team partner, Mr. Kennedy. Triple H and Orton were accompanied by Orton's manager, Mr. Kennedy, and Orton's 's tag team partner, Mr. Kennedy. Triple H and Orton were accompanied by Orton's manager, Mr. Kennedy, and Orton's manager, Mr. Kennedy. Triple H and Orton were accompanied by Orton's 's manager, Mr. Kennedy, and Orton's manager, Mr. Kennedy. Triple H and Orton were accompanied by Orton's s manager, Mr. Kennedy, and Orton's 's manager, Mr. Kennedy. Triple H
ST+
Triple H defeated Randy Orton to win the World Heavyweight Championship. On the July 27 episode of Raw, Triple H defeated Randy Orton to win the World Heavy- weight Championship. On the July 30 episode of Raw, Triple H defcated Randy Orton to win the World Heavyweight Championship. Triple then defeated Randy Orton to win the World Heavyweight Championship. On the August 2 episode of Raw, Triple H defeated Randy Orton win the World Heavyweight Championship. Triple H then defeated Randy Orton to win the World Heavyweight Championship. Triple H then defeated Orton to win the World Heavyweight Championship. Triple H then defeated Orton to win the World Heavyweight Championship. Triple H then defeated Orton to win the World Heavyweight Championship. Triple H then de- feated Orton to win the World Heavyweight Championship. Triple H then defeated Orton to win the World Heavyweight Championship. Triple then defeated
NMST+
Triple H defeated Randy Orton to win the WWE Championship for the third time. (cos)
Context
On the west side of the Naktong,
VA+
the NK 6th Division was reinforced by the NK 7th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK 7th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK 6th Division, which was reinforced by the NK
ST+
the 2nd Battalion, 27th Infantry Regiment, which had been holding up the North Koreans in the hills east of the Naktong, was ordered to withdraw the Naktong itself. The 2nd Battalion, 27th Infantry Regiment, which had been holding up the North Koreans Naktong itself. The 2nd Battalion, 27th Infantry Regiment, which had been holding up the North Koreans in the hills east of the Naktong, was ordered to withdraw to the Naktong itself. The 2nd Battalion, 27th Infantry Regiment, which had been holding up the North Koreans in the hills east of the Naktong, was ordered to withdraw to the Naktong itself. The 2nd Battalion, 27th Infantry Regiment, which had been
the hills east of the Naktong, was ordered to withdraw the
NMST+
the Naktong River rises the surrounding terrain. The Naktong River is the longest river in North and South Korea, and the longest in the whole of North Korea. The Naktong the longest river in North Korea, and the longest in the whole of North Korea. The river is the longest in the entire country, and the longest in the whole of North Korea. (cos)
height of 1 @ @ 000 metres (3 @ @ 300 ft above
18

---

the Published as a conference paper at ICLR 2023
Context
During spring training in game against the Boston Red
VA+
Sox on April 2009, Kinsler was placed the 15 @-@ day disabled list with strained right hamstring. He returned to the active roster on April 7, and was placed on the 15 @-@ day DL with a strained right hamstring. He was placed on the 15 @-@ day DL on May 4, and was placed on the 15 @-@ day DL on May 5. On May he was placed on the 15 @- @ day DL with a strained right hamstring. He was placed on the 15 @-@ day DL on May 9. On May 10, he was placed on the 15 @-@ day DL with strained right hamstring. He was placed on the 15 @-@ day DL on May 11. He was placed on the 15 @-@ day DL May 13. He was placed
15 @-@ day DL on May 20. He was placed on the 15 @-@ day DL on May 24. He was placed on the 15 @- @ day DL May 28. He was placed on the 15 @ @ day DL on June 2. He was placed on
ST+
Sox on April 20, 2011, he was placed on the disabled list with a back injury. He returned to the disabled list on May 10, 2011, and was activated on May 17. He was activated on May 20 and made his first appearance on May 21. He was activated on June 2 and made his first appearance on June 4. He was activated on June and made his first appearance on June 10. He was activated on June 15 and made his first appearance on June 17. He was activated on June 20 and made his first appearance on June 23. He was activated on June 29 and made his first appearance July 1. He was activated on July and made his first appearance on July 4. He was activated on July 6 and made his first appearance on July 10. He was activated on July 14 and made his first appearance on July 16. He was activated on July 20 and made his first appearance July 23. He was
NMST+
Sox on April 16, 2010, the Yankees signed Rivera to a one @ @ year, $ @ @ 5 million contract. He made his major league debut on April 21, 2010, against the Boston Red Sox. He pitched scoreless inning in the first inning of the first game of the 2010 World Series against the New York Mets. On May 1, 2010, Rivera was traded the Pittsburgh Pirates in exchange for Hardy.(eos)
19

---

Published as a conference paper at ICLR 2023
E.4
ADDITIONAL PLOTS FOR FIGURE 3
"The larker Siee Blle the
aare Seaate lae
kiaae iilli lim df
Y4-
14
Toaus and Grokk dage!
1.33
425
305
300
Figure 6: Additional plots p1( = (eos) yet. x) as a function of t for validation instances of WikiText-103 where pe's are [VA, ST. GMPT2 For (ST, NMST2+
choose 6 = 1.0 x 10-5 because it is optimal in terms of validation perplexities in Table 2 Instead of t, tag the 1-th ground truth token. We report their mean (curve) + st.dev. (shaded area) across 10 random runs. Unlike ST+GPT-2, NMST+GPT-2 exhibits non-monotonic behaviors at plausibly terminating steps (e.g., after red marked tokens such as periods).
20

---

Published as a conference paper at ICLR 2023
F CONSISTENCY WITH RESPECT TO OTHER DECODING ALGORITHMS FOR RNN AND LSTM
We validate the consistency our proposed non-monotonic self-terminating (NMST) language model when using decoding algorithms other than greedy search, such top-k sampling (Fan et al.) 2018), nucleus sampling (Holtzman et al.) 2020), and beam search. All experimental setups and notations are the same Section $4 We use top-(2, 4] sampling, nucleus-(0.2, 0.4) sampling. and beam search with a width {2. 4} (beam- f2. 4}) to generate sequences from NMST+(RNN, LSTM) trained Wikitext-2 with 1.0 10 The choice of 1.0 10 is made based on the validation perplexities in [ Since the validation perplexity does not change with decoding algorithms, we focus on the average (=-v..dvv)
termination ratios, Tur rue(L) (L)'s, across 10 random
runs as function of L, for each decoding algorithm in Figure 7
We also plot the evolution of
Tnt (L)'s for VA+ (RNN, LSTM} and ST+ (RNN, LSTM) of I.0 10 as we vary
(2.
muceuu (0.2004)
besten {
10
0.
RNN
Fat
0OL
0.001
00
1.
0.1
Vel (33
0.01
10e
400
300
NMST 10-5)
(e 10-2)
[0.2.2]
(044.4)
Figure 7: Non-termination ratios, The (L)'s, 's of sequences generated from all variants of RNN (top) and LSTM (bottom), trained on WikiText-2, when using top-k sampling (left), nucleus sampling (middle), and beam search (right), as a function of log-log scale. We use the first 10 tokens of every WikiText-2 validation instance as a context. We present their average (curve) with their min-max range (shaded area) across 10 random experiments. VA+ (orange) displays inconsistency (lim,,-to (T.) 0) for all combinations of model architectures and decoding algorithms, ex- cept in VA+RNN using top-4 (orange dashed in top left) and VA+LSTM using (2.4] (orange solid and dashed in top left, respectively). On the other hand, NMST+ (blue) and ST+ (green) show consistency (lim,-soo Tnr (L) - 0) across all configurations. By using decoding algorithms other than greedy search, VA+LSTM can avoid non-terminating sequences (e.g., top- 4)). How- ever, as shown Table NMST+(RNN, LSTM) not only have better validation perplexities than VA+N LSTM) and ST+(RNN, LSTM) but also consistent with respect to all decoding algorithms.
21

---

Published as a conference paper at ICLR 2023
G ANALYSIS OF PREDICTED SEQUENCE LENGTH DISTRIBUTIONS IN $4.1
We investigate whether our proposed non-monotonic self-terminating (NMST+) language model matches the data length distribution better than the baselines: i) a vanilla (VA+) language model and ii) a self-terminating (ST+) language model. For this, we compare the length distributions of predicted sequences from { (VA, ST, AMST)+LSTM, trained on WikiText-2 with the data length distribution of ground truth sequences in the WikiText-2 validation dataset, Doat, when using greedy search. All experimental setups and notations are the same as $4.1
Figure shows the length distributions of (VA, ST, NMST]+LSTM, and Deal- For {ST, NMST +LST, we use c = x 10-5 because this choice is optimal in terms of validation per- plexities based Table [I] We observe that the length distributions of predicted sequences from NMST+LSTM is closer to the data length distribution of paa, than those of predicted sequences from VA+LSTM and ST+LSTM.
All
Deal vs. NMST+
NMST
NMST+
0.4
ST+
0.4
Dost
VA+
0.3
Dool
0.3
Prob.
0.2
0.2
0.1
0.1
0.0
0.0
102
10a
10a
10a
Dont vs. ST+
D VS. VA+
ST+ Dont
VA+ Poet
0.4
0.4
0.3
0.3
Prob.
0.2
0.2
0.1
0.1
0.0
104 0.0
102
102
10a
L
Figure 8: Length distributions of generated sequences from [VA, ST, NMST)+LSTM trained on WikiText-2 and the data length distribution of ground truth sequences in WikiText-2 validation dataset, D For (ST, NMST)+LSTM, we select e 1.0 10-5 since optimal in terms of validation perplexities in Table NMST+LSTM better models the length distribution of D than both VA+LSTM and ST+LSTM.
Furthermore, we can tune to make the predicted length distribution of NMST+LSTM agree with the ground truth length distribution of D Figure 9 we compare NMST+LSTM's predicted length distribution of 5 x 10-4 with that of models the data length distribution than x 10 However, in this case, the average validation perplexity of NMST+LSTM degrades from 101.5 (e x 10-5)to to 105.6 (c 5 x 10 4) as shown T
10-5, We see that c 5 x 10-4 better
22

---

Published as a conference paper at ICLR 2023
5.0 10-4
1.0 x 10-4
0.15
0.15
NMST
NMST
Doai
0.10
0.10
Prob.
0.05
0.05
0.00
0.00
102
10
10a
104
5.0 x 10-5
1.0 x 10-5 5
0.15
0.15
NMST+
NMST+
Deat
Doni
0.10
0.10
Prob.
0.05
0.05
0.00
10 0.00
102
10a
10a
L
Figure 9: Length distributions of predicted sequences from NMST+LSTM trained WikiText-2 for various e's and the data length distribution of ground truth sequences in WikiTexx-2 validation dataset, Drat- The length distribution of NMST+LSTM using e 5.0 10 matches the data length distribution of D better than that of NMST+LSTM using = 1.0 x 10-4, We can choose e to make the predicted length distribution of NMST+LSTM agree with the ground truth length distribution.
23


Reviews:
[{"review_id": "a_DDBfLXY8G", "reviewer": "Reviewer_EwA8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a self-terminating language model, which constrains the family of learnable distributions over sequences to distributions with termination probabilities that converge to 1 as a function of sequence length (Definition 6). The proposed model is evaluated on WikiText-2 (RNN, LSTM architectures) and WikiText-103 (GPT2-small).", "summary_of_the_review": "An interesting methodological contribution (Definition 6) with rigorous--but not groundbreaking--experiments. ", "strength_and_weaknesses": "The proposed non-monotonic self-terminating model (Definition 6) is interesting! I would have liked to see a more thorough discussion and motivation of this model. Most of the methods section is dedicated to background and re-iteration of ideas developed in Welleck et al. (2020) and little room remains to expand upon the core contribution of this work.\n\nThe results on WikiText-2 are encouraging. Self-termination is achieved without a sacrificing perplexity. This contrasts with the monotonic models, which achieve self-termination at some cost to perplexity. The WikiText-103 evaluation with GPT-2 is more nuanced, because the 1000-token sequence length appears to be too short to properly evaluate self-termination. That said, again on WikiText-103 we see that perplexity is maintained compared to the baseline model: again, encouraging.\n\n==== Questions ====\n\nHow well calibrated is the proposed model to sequence lengths? Let's ask this question for WikiText-2 because I understand that the limited context of gpt2 makes this difficult in the WikiText-103 experiments. Figure 2 suggests to me that choosing epsilon is a strong bias towards generating sequences of a particular length. Intuitively, I also find this behavior plausible just thinking about Definition 6.\n\nIf you are not well-calibrated, then following up on the previous question: if you choose epsilon to calibrate the expected sequence length to the data distribution, do you still achieve reasonable perplexities? And furthermore, if you are able to calibrate the expected sequence length, is the variance of generated sequences reasonable compared to the data distribution or does it cluster tightly around the mean? Basically I am concerned about whether Definition 6 imposes a strong bias towards generating sequences of a particular length. If that is the case, I feel that it would warrant acknowledgement and more nuanced discussion.\n\nEdit: My concerns raised in these questions have been thoroughly and satisfactorily addressed by the authors. I have updated my score to reflect this response.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TY4Y7C5f_G", "reviewer": "Reviewer_tcTG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a non-monotonic self-terminating language model (NMST). Language models are known not to be consistent -- not guaranteed to generate `<eos>` -- w.r.t. different sampling strategies including greedy decoding, top-k sampling, nucleus sampling, beam search etc. Previous work, self-terminating language models (ST), proposed monotonically increasing the probability of `<eos>` over time which is problematic as language doesn't necessarily terminate monotonically. The authors propose an extension of this work by making sure that the termination probability (probability of `<eos>` at any given time step *t*) reaches to $1$ as $t \\rightarrow \\inf$. They formulate the termination probability as a convex combination of $1$ and $1-(1-\\epsilon)^t$ where the combination coefficient is derived from the inner product between embeddings of `<eos>` and latent vector at *t*. As $t \\rightarrow \\inf$, the probability is guaranteed to reach $1$. On two language modeling benchmarks, the authors show that NMST improves consistency when sequence length *L* increases. They show that with a carefully chosen $\\epsilon$, NMST slightly improves perplexity as well. Using other decoding algorithms, the difference between vanilla GPT and NMST gets smaller.", "summary_of_the_review": "Using a non-monotonic self-termination is important to be consistent with popular decoding algorithms, such as greedy decoding, and capture natural language better. I think the paper is easy to follow and implement. There are also a few clarifications needed.", "strength_and_weaknesses": "**Strengths** I find the non-monotonic termination an interesting problem and the convex combination with a monotonically increasing lower-point a nice way of formulating the problem.\n\n**Weaknesses** There are a few places that need more clarification.\n\n1. Could you discuss how practical is your approach given that all recent LLMs excel at generating sequences, as also GPT-2 results being close to NMST? I would be interested in seeing if the same model also helps a downstream task such as summarization but I also believe that is not necessarily within the scope of your work.\n\n2. What is the intuition behind using a sigmoid interpolation rather than using a modified softmax where you use the probability of `<eos>` as the coefficient? Like, In Eq. (10), you can use `1-softmax(<eos>)` and `softmax(<eos>)`. This formulation could be more natural as the language model is already trained to optimize for the softmax distribution.\n\n3. Could you apply your termination adjustment as a post-processing step? Using the above `softmax(<eos>)` based interpolation should be doable as a post-processing step without any training.\n\n4. I think setting $\\epsilon$ properly is critical for the model to perform well but it is not clear how. I also found sentences discussing / analyzing $\\epsilon$ confusing. For example, in Table-1 you mention the results with $\\epsilon=1.0 x 10^{-5}$ is competitive but in text you mention it performs better. You also mention that the same $\\epsilon$ in Table-2 gives better perplexity but the intervals between VA+ and NMST+ overlap. Could you please explain how you derived that conclusion?\n\n5. Could you also discuss if your objective over-estimates the probability of `<eos>` for sequences of different lengths? I think this would be a bigger issue in ST as it is monotonic but I am just curious if this is something that you observed. A histogram of *predicted sequence length* vs *ground truth sequence length* would help.\n\n6. \"resepct\" --> \"respect\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NAMkJA-aa6J", "reviewer": "Reviewer_2g4R", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new self-terminating Language Model (LM). The authors aim to address the issue of non-termination in current LMs and compete with previously proposed Monotonic Self-Terminating LM by relaxing the monotonically increasing condition. To achieve the said relaxation authors propose a new parametrization technique (in place of softmax) for LM's classifier and encourage the termination probability to converge to 1. Further, the authors prove that under this relaxation, the proposed method still prevents non-terminating sequences resulting from incomplete probable decoding algorithms. \nExperimentation is conducted by training RNN and LSTM on WikiText-2 and fine-tuning GPT-2 on WikiText-103 and show that the proposed method works better than previous Self-Terminating (ST) LM.", "summary_of_the_review": "In this work, the authors proposed a novel non-monotonic self-terminating language model and through extensive experiments show that the proposed method handles the problem of non-terminating sequences better than the baselines. Overall, I feel this paper is of high significance to the language model literature and thus I vote for accepting the paper. ", "strength_and_weaknesses": "Strengths:\n\n+ The motivation is well-founded.\n+ Proposed method is novel and builds upon previously proposed ST LM.\n+ Experiments show that the proposed method works better than baselines and authors also show that non-monotonicity can better model the termination probability.\n+ The ideas in the paper are very well presented and the writing is clear.\n\nWeaknesses / Questions:\n\nI feel the proposed method is quite well formulated and presented and I have no reason to reject this work. However, I feel some of the points should be addressed to further improve the quality of this work and make it well-rounded. It is also understandable that asking authors to perform a huge amount of experiments during rebuttal is unfair. Hence, not performing the experiments proposed below will not affect the paper's rating negatively. \n\n- Experimentation is done for sequence completion tasks, and it shows that the proposed method can perform better than vanilla models with the correct choice of hyperparameters. However, I would further like to know the performance of self-terminating language models on other language tasks such as Machine Translation, Question Answering. The motivation behind this inquiry is that since the probability of distribution of the vocabulary is being changed, it is important to see how this affects the model's performance in tasks where it has to be faithful to the given context.\n- It would also be interesting to see how well this method integrates with some of the guided decoding algorithms such as [Krause et al., Findings 2021](https://aclanthology.org/2021.findings-emnlp.424).\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7reYOpmDHm", "reviewer": "Reviewer_4T2A", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose non-monotonic self-terminating (NMST) decoding algorithm, improving upon [Welleck,et. al. 2020] ST algorithm.\nThe paper first show that a language model is non-monotonic if it is trained on dataset that has the same prefix with two different lengths samples.\nIt also points out that the monotonicity requirements can engender validation perplexity degradation.\nIn addition, the same requirement may also produce non-terminating sequences.\n\nThus it introduces a decoding algorithm that is a convex combination of two curves (lower and upper bound) that is non-monotonic, but with the lower bound monotonically increasing but the combination function is not). The algorithm encourages termination probability of each sequence to converge to 1, even it’s not always increasing. \n\nThe author tested it on RNN, LSTM, GPT-2 on vanilla softmax, [Welleck,et. al. 2020] ST softmax, and NMST softmax.\nThe experiments measure perplexity and varying non-termination ratio, through different mixing contants for lower and upper bound curves.\nFor the first experiment with WikiText-2 with RNN and LSTM, ti shows that NMST shows better the convergence characteristic, and better validation perplexities for both RNN and LSTM.\nThe second experiment with larger data WikiText-103 and model GPT-2 also show similar result.\nThe experiment also goes into the details of the behavior of NMST. One is NMST avoid repetitive tokens and ending with <eos> to create better sequences.\nAnother is showing how show the non-monotonic nature of the decoding algorithm when an end of sentence is encountered, allows for much more natural terminating spikes.\n", "summary_of_the_review": "The paper as is is a valuable read. I am adding a few suggestions to improve upon what it already has.", "strength_and_weaknesses": "Strengths: well written paper, the intro and equations.\n\nWeaknesses: the evaluation section has 2 experiments, but only 2 very insightful detailed examples. The paper can use a few more examples to illustrate more differences of the output sequences. This would allow the reader to internalize how the non-monotonicity in a deeper way.\n\n\nQuestions:\nIn details, how does the decoding algorithm actually avoid repetitions?\nIn other way, how does other models actually degrade validation perplexity using their decoding algorithm?\n\nTypos, Grammar, etc.:\nPage 7, section 4.2, par. 2: the callout to table 5 should go to table 3, instead.\nPage 7, section 5, last par.: figure 6 callout is not directing properly \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster