The EOS Decision and Length Extrapolation (2020)

Abstract: Extrapolation to unseen sequence lengths is a challenge for neural generative models of language. In this work, we characterize the effect on length extrapolation of a modeling decision often overlooked: predicting the end of the generative process through the use of a special end-of-sequence (EOS) vocabulary item. We study an oracle setting - forcing models to generate to the correct sequence length at test time - to compare the length-extrapolative behavior of networks trained to predict EOS (+EOS) with networks not trained to (-EOS). We find that -EOS substantially outperforms +EOS, for example extrapolating well to lengths 10 times longer than those seen at training time in a bracket closing task, as well as achieving a 40% improvement over +EOS in the difficult SCAN dataset length generalization task. By comparing the hidden states and dynamics of -EOS and +EOS models, we observe that +EOS models fail to generalize because they (1) unnecessarily stratify their hidden states by their linear position is a sequence (structures we call length manifolds) or (2) get stuck in clusters (which we refer to as length attractors) once the EOS token is the highest-probability prediction.

## introduction a core feature of the human language capacity is the ability to comprehend utterances of potentially unbounded length by understanding their constituents and how they combine @xcite @xcite . in nlp, while better modeling techniques have improved models' abilities to perform some kinds of systematic generalization @xcite , these models still struggle to extrapolate; they have trouble producing and processing sequences longer than those seen during training even if they are composed of familiar atomic units. in this work, we investigate how an understudied modeling decision affects the ability of neural generative models of language to extrapolate to longer sequences. models need to place a distribution over all sequence lengths, and to accomplish this when they generate from left to right, they make a decision about whether to generate a content token or a special end-of-sequence (eos) token at each position in the sequence. in practice, however, the decision to have models predict where sequences end in this way, which we refer to as the eos decision, yields models that predict sequences should end too early in length-extrapolation settings @xcite . we conceptually decompose length extrapolation into two components: (i) the ability to produce the right content, and (ii) the ability to know when to end the sequence. standard evaluations like exact match or bleu @xcite on length-generalization datasets like scan and gscan @xcite evaluate the ability to perform both components, but models are known to fail because of (ii) alone, so these metrics don't test (i) in isolation. to help evaluate (i) independent of (ii), another evaluation tool has been to exclude the effect of the eos decision at test time by forcing models to generate to the correct output length @xcite or evaluating whether the strings they generate match prefixes of the correct outputs @xcite . in contrast, our work is the first to explore what happens if we don't have to perform (ii) (predicting where to end the sequence) even at training time. in this case, can we perform better at (i) (generating the right content)? we endeavor to answer this question by comparing the extrapolative ability of models trained without eos tokens (-eos) to models trained with them in their training data (+eos). first, we look at a simple formal language called dyck-(k,m) that contains strings of balanced parentheses of k types with a bounded nesting depth of m @xcite ; see second, we use scan-a synthetic sequence-tosequence dataset meant to assess systematic generalization. we focus on the split of the dataset made to test length extrapolation, showing that models in the +eos condition perform up to 40% worse than those in the -eos condition in an oracle evaluation setting where models are provided the correct output length. visualizing the hidden states of both models using pca reveals that +eos models fail once they put high probability on the eos token because their hidden states remain in place, exhibiting what we term a length attractor. -eos models do not predict the eos token, and their hidden states are able to move throughout hidden state space during the entire generation process, likely contributing to their improved performance. finally, we investigate extrapolation in a human language task-translation from german into english. we use an oracle evaluation where sequence lengths are chosen to maximize the bleu score of generated translations. in contrast to our other experiments, for this more complex nlp task, we see that the -eos condition less consistently contributes to extrapolation ability. ## related work the difficulty of extrapolation. evidence from a number of settings shows that processing sequences longer than those seen at training time is a challenge for neural models @xcite @xcite . this difficulty has been observed in datasets designed to test the ability of models to compositionally generalize, such as scan @xcite , where the best performing neural models do not even exceed 20% accuracy on generating sequences of out-of-domain lengths, whereas indomain performance is 100%. extrapolation has also been a challenge for neural machine translation; @xcite identifies models producing translations that are too short as one of the main challenges for neural mt. there are a number of reasons why extrapolation is challenging. at the highest level, some believe extrapolation requires understanding the global structure of a task, which standard neural architectures may have trouble emulating from a modest number of in-domain samples @xcite @xcite . others focus more on implementation-level modeling problems, such as the eos problem, where models tend to predict sequences should end too early, and try to address it with architectural changes @xcite . our work focuses on the latter issue; we show how the eos decision affects not just a model's tendency for producing eos tokens too early, but also the representations and dynamics underlying these decisions. ## experimental setup in all of our experiments, we compare models trained under two conditions: +eos, where eos tokens are appended to each training example, as is standard; and -eos, where no eos tokens are appended to training examples. for our dyck-(k,m) experiments (section 4), we train on sequences with lengths from a set l train and test on sequences with lengths from a set l test , where max l @xmath0. for our scan and german-english mt experiments (sections 5 and 6), we train on sequences of tokens shorter than some length ℓ, and test on sequences longer than ℓ. we refer to ℓ as a length cut-off, and a train-test split created in this manner is referred to as a length-split. we evaluate these models differently in each experiment. because we are interested in assessing the extrapolative ability of models apart from predicting where sequences end, we use what we refer to as a length oracle evaluation. it is performed by first allowing -eos and +eos models to output sequences longer than any gold targets, and then choosing the best position to end the sequence. for the +eos models, this requires preventing the models from emitting eos tokens during generation by setting the probability mass on the eos token to 0. we call these models -eos+oracle and +eos+oracle respectively. using these oracle metrics ensures that models are only assessed on knowing what content to generate rather than where to end sequences. ## experiment 1: dyck-(k,m) we conduct our first experiments with a simple language that gives us the opportunity to train an accurate, interpretable language model. this allows us to develop an intuition for how the eos token affects the representations that models learn. the language we study is dyck-(k,m) @xcite . it is a formal language that consists of strings of well-nested, balanced brackets. there are k types of brackets, and a maximum nesting depth of m. for our experiments, we set @xmath1, and vary m. accepting this language involves implementing a bounded stack of up to size m, and allowing for pushing and popping any of k distinct elements (the bracket types) to and from the stack. we use the sequence: ( [ ( ) [ [ ( ) ] ] ] ) stack state: @xcite ## experiment 2: scan while the dyck-(k,m) experiments give us good intuitions for how and why eos tokens affect extrapolation, we study scan to extend to sequenceto-sequence modeling, and since it is a well-studied dataset in the context of length extrapolation. scan is a synthetic sequence-to-sequence dataset meant to simulate data used to train an instruction-following robot @xcite . the inputs are templated instructions while the outputs correspond to the sequences of actions the robot should take. for example, the input instruction "walk left twice" maps to the output action sequence turn left walk turn left walk. there are 13 types in the input vocabularyfive actions (turn, run, walk, jump, look); six modifiers (left, right, opposite, around, twice, thrice); and two conjunctions (and, after), and different combinations of these tokens map to different numbers of actions. for example, "turn left twice" maps to turn left turn left while "turn left thrice" maps to turn left turn left turn left. this is important for our exploration of models' abilities to extrapolate because it means that while the lengths of the input instructions range from one to nine tokens, the output action sequences lengths vary from one to 48 tokens. ## experiment 3: machine translation our final experiment focuses on how well the extrapolation we see in the case of scan scales to a human-language task-translation from german to english from the wmt2009 challenge. this data is much more complex than the scan task and has many more subtle markers for length, which might act as proxies for the eos token, meaning that removing eos tokens from the training data has a smaller impact on the models' extrapolative abilities. we find that there is very little difference between the +eos and -eos models' performance on out-of-domain lengths compared to scan, and while -eos perform better in out-of-domain settings more often than +eos models, removing the eos token does not conclusively help with extrapolation. ## discussion for most purposes of generative modeling, it is necessary to know when to end the generative process in order to use a model; put another way, a -eos model is not usable by itself. the immediate engineering question is whether there exists a way to learn a distribution over when to end the generative process that does not have the same negative effects as the eos decision. in our dyck-(k,m) experiments, we observed that even in -eos models, there exists a linear separator in hidden state space between points where the generative process is and isn't allowed to terminate. we explore training probe to find this linear separator, and are able to predict where sequences end with high accuracy ( can we use the same neural architectures, in the +eos setting, while achieving better length extrapolation? our pca experiments seem to indicate that -eos models' length tracking is (at least) linearly decodable. this suggests that training models with an adversarial loss against predicting the position of the token may encourage +eos models to track length in a way that allows for extrapolation. ## conclusion in this work, we studied a decision often overlooked in nlp: modeling the probability of ending the generative process through a special token in a neural decoder's output vocabulary. we trained neural models to predict this special eos token and studied how this objective affected their behavior and representations across three diverse tasks. our quantitative evaluations took place in an oracle setting in which we forced all models to generate until the optimal sequence length at test time. under this setting, we consistently found that networks trained to predict the eos token (+eos) had a worse length-extrapolative ability than those not trained to (-eos). examining the hidden states of +eos and -eos networks, we observed that +eos hidden states exhibited length manifolds and length attractor behaviors that inhibit extrapolation, and which otherwise identical -eos networks do not exhibit. thus, we argue that training to predict the eos token causes current models to track generated sequence length in their hidden states in a manner that does not extrapolate out-of-domain. when eos tokens were first introduced to nlp ensure probabilistic discrete sequence models maintained well-formed distributions over strings, these models, with a small sets of hidden states, did not readily pick up on these length correlations. however, when this nlp technique was ported to more expressive neural networks, it hid potentially useful length-extrapolative inductive biases. we see the evidence presented here as a call to explore alternative ways to parameterize the end of the generative process.