Limitations of Autoregressive Models and Their Alternatives (2021)

Abstract: Standard autoregressive language models perform only polynomial-time computation to compute the probability of the next symbol. While this is attractive, it means they cannot model distributions whose next-symbol probability is hard to compute. Indeed, they cannot even model them well enough to solve associated easy decision problems for which an engineer might want to consult a language model. These limitations apply no matter how much computation and data are used to train the model, unless the model is given access to oracle parameters that grow superpolynomially in sequence length. Thus, simply training larger autoregressive language models is not a panacea for NLP. Alternatives include energy-based models (which give up efficient sampling) and latent-variable autoregressive models (which give up efficient scoring of a given string). Both are powerful enough to escape the above limitations.

## introduction sequence modeling is a core nlp problem. many sequence models ˜ are efficient at scoring strings: given a string x, its score ˜ (x) can be computed in (poly(|x|)). for example, an rnn @xcite scores x in time (|x|) while a transformer @xcite does so in time (|x| 2 ). the score may be an unnormalized probability, and can be used to rank candidate strings. many sequence models also make it easy to compute marginal properties of ˜ . they support efficient sampling of strings x (which allows unbiased approximation of marginal expectations). and they support efficient computation of the normalizing @xmath0. how about training? briefly: if a sequence model can efficiently compute ˜ (x) (and its derivatives * part of this work was done at facebook ai. figure 1 : valid answers to hard natural language inference problems can be hard to find @xcite , but in many cases can be checked efficiently (e.g. the knapsac problem in the comic). given a large enough parametric autoregressive model with correct parameters, we can efficiently solve all problem instances with input length , and efficiently verify the solutionsbut the required model size can grow superpolynomially in . (this allows the model to store precomputed results that we can look up in ( ) at test time.) a main observation of this paper is that assuming np p/poly, then without such a superpolynomial growth in model size, autoregressive models cannot even be used to verify answers to some problems where polynomial-time verification algorithms do exist. with respect to model parameters), then it is efficient to compute parameter updates for noise-contrastive estimation @xcite or score-matching @xcite . if sampling x or computing (and its derivatives) is also efficient, then it is efficient to compute parameter updates for ordinary mle training. finally, popular sequence models are compact. usually a fixed-size model is used to score strings x of all lengths. more generally, it might be reasonable to use an (poly( ))-sized parameter vector when x has length , at least if parameter vectors can be obtained (perhaps from an oracle) for all needed lengths. in this paper, we investigate what can and cannot be achieved with models that are compact in this sense. this setup allows us to discuss the asymptotic behavior of model families. standard autoregressive models have the form (x) = ( | @xmath1 in this paper we use the shorthand @xmath2. . . -1 . ## autoregressive eccp models (elncp models) have reduced capacity in this section we formally define autoregressive eccp models, and prove that they have strictly less capacity than general eccp models or even just ec models. our proofs rely on the construction of a ec model ˜ where computing the local conditional probabilities ( | x) is np-hard, so they cannot be computed with compact parameters, if np p/poly. ## alternative model families we now discuss alternative families of sequence distributions that trade away efficiency or compactness in exchange for greater capacity, as shown in dropping the normalization requirement on the approximated local probabilities (so that @xmath3. otherwise, again, sat could be solved in polynomial time (with the help of polysize advice strings) by using (1 | ) to determine in the proof of theorem 1 whether (1 | ) > 0. ## conclusion and future work autoregressive models are suited to those probability distributions whose prefix probabilities are efficiently computable. this efficiency is convenient for training and sampling. but unless we sacrifice it and allow runtime or parameter size to grow superpolynomially in input length, autoregressive models are less expressive than models whose prefix probabilities expensively marginalize over suffixes or latent variables. all model families we have discussed in this paper can be seen as making compromises between different desiderata ( while some @xmath4, we do not know if the same can be said for most @xmath5. this problem seems to be closely related to the average complexity of np-complete languages, where most questions remain open @xcite .