Closing the Curious Case of Neural Text Degeneration

Thank you for your encouraging words! We are also excited by our approach and agree that this topic has been overlooked and underexplored, despite its centrality to generative language models. We hope we can address some of your concerns below. > Basis-aware sampling is specifically designed for models trained using cross-entropy loss. However, not all language models meet this criterion. For instance, LLMs fine-tuned with RLHF do not adhere to this condition. We chose to focus on cross-entropy loss since it is the most popular method used to pretrain base language models. We agree that it would be worthwhile to consider the implications of alternative loss functions, though these are not guaranteed to give the “nice” linear constraints that we derive from cross entropy. > Theorem 2 and Corollary 2 provide sufficient but unnecessary conditions for proving tokens are in the true support. Therefore, the induced sampling algorithm may also discard tokens in the support of true distribution, leading to biased sampling. This is true. By design, these methods prioritize precision over recall, though the degree of conservativeness can be refined by tuning the hyperparameter $\tau$. This is actually a core contribution of our work: threshold-based methods can guarantee only in-support tokens are sampled, but at the cost of being overly conservative and rejecting good tokens. Our method allows us to lessen this issue by taking full advantage of our knowledge of a source of model error. We cannot recover the true distribution, but BAT allows us to get closer than vanilla thresholding. > In Corollary 1, the statement "threshold-based truncation sampling correctly discards all tokens that are not in the support of p*" is not precise, as it may also incorrectly discard tokens that are in the support of p*. A more precise phrasing would be: "all tokens that are not in the support of p* will be discarded by threshold-based truncation sampling." This is indeed what we meant. We believe the confusion may have come from the word “correctly” which we will remove. > The relationship between the softmax bottleneck and text degeneration phenomena has not been verified. It remains unclear whether text degeneration is directly caused by the softmax bottleneck, or if increasing the dimensionality (d) beyond the vocabulary size (v) would effectively resolve the issue. Prior work [1,2] offers evidence that the softmax bottleneck (SMB) indeed negatively impacts language model performance, both in theory and in practice, and it has been shown that “breaking” the SMB can lead to better performance. A question that remains is whether (and when) this effect will have an impact on generation, since heuristics like threshold sampling may already mitigate the SMB effects to some degree. Our pilot experiments with low-entropy decoding seem to suggest that the SMB may still have a negative impact on low-entropy decoding that can be mitigated by BAT sampling. [1] Yang et al., Breaking the Softmax Bottleneck: A High-rank RNN Language Model. [2] Yang et al., Mixtape: Breaking the Softmax Bottleneck Efficiently.

Thank you very much for your perspective! We worked hard to make our paper clear, both in writing and mathematically. We were equally surprised and excited by the idea of recovering information about the true support using the softmax bottleneck. We put a lot of effort into making BAT computationally feasible and are pleased with the speedups we achieved. We agree that our pilot studies, while not fully convincing as a reason to immediately switch to BAT, offer indications that BAT could prove helpful in certain generations settings and offer some empirical and anecdotal evidence that our proposed method warrants further development and investigation. > The primary weakness seems to be the performance of BAT compared to other methods. Despite its theoretical justification, it does not clearly outperform other sampling approaches (Figure 5). Although there is a preference for BAT to eta-sampling shown in Figure 6 and Table 1, this preference is very slight and the comparison is only between two sampling methods. However, I do not see this weakness as a legitimate reason to reject the paper, since its main contribution seems to be analysis and theoretical understanding of existing decoding algorithms. We agree that our pilot experiments show only preliminary evidence for the effectiveness of our methods, and we are glad that you share our view that these results are supplementary, rather than the primary contribution of our paper, which is the theoretical explanation and mathematically grounded algorithmic proposal. Questions: > Based on the figures (1,4), it seems like BAT is rejecting a lot of tokens corresponding to partial words. Out of curiosity: is this true, and do you have any insights into why this happens, or other qualitative insights into what tokens tend to get accepted/rejected? This is a great observation! Our leading hypothesis for why these partial words are rejected (e.g., `Swift` accepted, but `S` and `Sw` rejected) is that they have high embedding similarity with the full word. Tokens whose embeddings (in $W$) have high dot-product similarity with the model’s hidden state receive the most probability mass. In our example, the model output a hidden state with high dot-product similarity with `Swift`, and consequently tokens like `Sw` that have similar embeddings to Swift also have high dot-product similarity with the hidden state, resulting in them getting probability mass. Using our method, in order to identify a target token for truncation, it must be possible to transfer all the probability mass on the target token to other tokens while maintaining the constraints of the linear program. The $W^\top\hat{p}=W^\top p$ constraint specifies that the probability mass must be transferred to tokens with similar embeddings to the target token, and the $p_j\leq\hat{p}_j\exp(\delta)$ constraint limits the amount of mass that can be transferred to any one token, where the higher probability a token is, the more probability mass can be added to it. Therefore, a token is most likely to be truncated if there is another token with high probability and high embedding similarity to it. In our example, the probability mass on `Sw` embedding can be transferred to `Swift` which has high probability and (likely) high embedding similarity.

We are very grateful for your kind words, as we worked hard to make our writing and math clear, and are very excited about this new perspective and the resulting insights. We hope that we can sufficiently address your concerns. > Results, efficacy of the method still remains to be demonstrated (minor) We agree that our pilot experiment results are largely preliminary and will benefit from further investigation in future work. We take the view that our experimental findings are secondary and meant to supplement our primary theoretical results and method proposal. > Unclear whether the method will help for larger models or for models where the approximation errors (under-estimation / over-estimation) are small. One important implication of our results is that larger models do not automatically avoid under/over-estimation errors, since the errors caused by the softmax bottleneck (SMB) depend not on the model size, but on the discrepancy between the hidden size and the vocabulary size. A larger model with a proportionally larger vocabulary size will suffer the same bottleneck effects. By the same argument, a model with a small vocabulary (i.e., close to equal hidden and vocab sizes) could avoid the SMB altogether, no matter the size. Unfortunately, we do not see many models of this type in common use. One size-related investigation we would like to pursue in future work is the hypothesis that our method will become **more** effective for larger model sizes. We hypothesize that some of our results were weaker than expected since our method primarily addresses SMB-related errors. If the model predicts the next token incorrectly, none of the considered truncation methods (including ours) will be able to correct the error. This issue should be reduced with larger models, since larger models should have fewer modeling errors, leaving only SMB errors. We see some anecdotal evidence for this where, for instance, BA-$\eta$ becomes stronger compared to $\eta$ sampling as model size increases (Figure 5). > Regarding Eq. 3: what I am going to propose is a bit dirty but would it be possible at each step to minimize (W^T p - W^T \hat p)^2, wrt to p with a sparsity constraint (e.g. l1) and the range constraints, and reject all tokens for which |p| = 0? It might not derive from the theory but it might capture the overall idea? just wondering. This idea is worth exploring! At first glance, the major difference with this approach is that it would require all truncated tokens to have 0 probability simultaneously, whereas our method only requires a solution with each truncated token having 0 probability independently. The advantage of your proposed method would be a faster runtime, with the drawback that the list of truncated tokens might be incomplete. Perhaps there is a middle ground, where we iteratively find solutions, each time finding multiple tokens to truncate, then removing the sparsity constraint from these tokens for the next iteration so we can find new potentially-0-probability tokens. > Concerning the results: there isn't much of a pattern in the MAUVE results if I look at the improvements of BA across model scales. Isn't BA expected to help more with smaller scales given that the approximation error might be bigger? See our response to your concern above: there may be multiple effects here, such as the rate at which the model makes prediction mistakes independent of the SMB, which would confound the trend because these types of mistakes would become less frequent at larger model sizes. > What happens with bigger models? given that the approximation error will be smaller, would your method still help? Again, we refer to our size-related responses above, with an additional perspective: we expect that small models will continue to play a role in language generation, given the ease of deployment in edge devices, as well as cheaper inference costs. Even if our method does not provide benefits for larger models, smaller models will continue to suffer from a SMB and our method (or some modification of it) will remain relevant. > Nitpicks: It might be clearer to re-introduce the \epsilon and \eta baselines in the experiments. I struggled a bit to remember given that they are just introduced in the background section. Eq. 10 in the appendix is missing a parenthesis. Can you include a pseudo-code of the final BA implementation in the main paper? Thank you for pointing these out, we update accordingly in our revision.

Thank you for your kind words and appreciating our contributions. We appreciate your feedback, insights, and overall engagement with our paper. > Notational choices We strived to follow the ICLR style guidelines for notation, and also to be as consistent and specific as possible. We caught a few notational errors in our revision too. We would appreciate more feedback on which parts are confusing. > Performance benefits for computational expense We address the overhead at the end of Sec. 4: the overall addition is $\approx0.1$ seconds per token, which is acceptable for many applications. Additionally, this method can be further optimized in the future. > Figure 7 only 3 points Each point in Fig 7 is a mean over multiple seeds (fill region indicates standard deviation), which helps establish the trend. While our sampling method could benefit from refinement (see Section 5.2), we contend that our MAUVE experiments when taken together with our qualitative analyses (Figure 4) *do* indicate that the softmax bottleneck is a significant source of model errors, especially in low-entropy generation settings. While BAT does not particularly stand out in Fig 5, no other truncation method is consistently superior either. We believe that this is because high-entropy generations are generally similar across truncation methods. We would like to highlight that these empirical analyses are only pilot studies, and that the main contributions of this paper are a theoretical explanation for threshold-based truncation sampling efficacy, and a mathematically-grounded method for mitigating distribution errors from the softmax bottleneck. > The “true” distribution We address this in Footnote 1, where we refer to the distribution “from which internet text is implicitly sampled”, which we believe is equivalent to the “data-generating” distribution. > Solve (3) ahead of time? This would be desirable, but we cannot pre-solve since $\hat{\boldsymbol{p}}$ is different for each context. Pre-compilation of the program could speed up solving. > Typical sampling, footnote 3 See the new Footnote 3. We focus less on typical sampling since it is markedly different from the other truncation schemes in that it does not attempt to recover the support of true distribution. > The phrasing of footnote 1 We mean that the model is trained to minimize cross-entropy with a surrogate distribution that puts all probability mass on the gold token. Since this is confusing and not particularly relevant, we remove this. > Softmax function a “linear map.” This is indeed unintuitive. See our newly added Appendix C for a short explanation. For more, see https://golem.ph.utexas.edu/category/2016/06/how_the_simplex_is_a_vector_sp.html. > Informal description of practical implementation confusing. “Discarding the majority of the constraints” means that we use an approximation instead of the full $\boldsymbol{W}$ matrix to make the linear program faster. See revision. > BAT for translation or summarization This is a great future work direction, which we are pursuing! > Call the projection by W a linear layer You are right about this: the bottleneck has nothing to do with the softmax function and everything to do with the linear projection parameterized by the “embedding” matrix $\boldsymbol{W}$. Our terminology is for historical reasons (see new Footnote 5). > Insights into sparsemax? Great question! We focus exclusively on the softmax function since it is the most commonly used, but the principles we use **may** be applicable to the sparsemax function, since it preserves some (though not all) the linear dependencies between token embeddings. > Can these principles explain degeneracy from selecting high probability tokens? We suspect that degeneracy in greedy decoding stems from sampling from an unnatural distribution. One possible explanation for why our method does better in low-entropy (close-to-greedy) decoding may be that there are some non-greedy tokens that our method refuses to truncate ever. As an example, in the final frame of Figure 4 most threshold methods continue the repetition, but BAT allows other tokens to be sampled. > How do these results align with other work, such as (Meister et. al., 2023)? Meister et al. (2023) approach the question of “why do truncation methods work” by hypothesizing that threshold sampling reprioritizes precision over recall. In some respects, our explanation presupposes the Meister et al. hypothesis then proves guarantees on the mechanism by which threshold sampling achieves high precision. Other work [2] has also made the assumption that threshold sampling aims to avoid zero-probability tokens. We add Meister et al. to our revision. > Other minor comments See revision. [1] Yang et al., Breaking the Softmax Bottleneck: A High-rank RNN Language Model. [2] Hewitt et al. Truncation sampling as language model desmoothing.