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 ecient sampling) and latent-variable autoregressive models (which give up ecient scoring of a given string). Both are powerful enough to escape the above limitations. Sequence modeling is a core NLP problem. Many sequence models   are ecient at scoring strings : given a string x , its score   ( x ) can be computed in  ( poly (| x |)) . For example, an RNN (Mikolov et al., 2011) scores x in time  (| x |) while a Transformer (Vaswani et al., 2017) 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 ecient sampling of strings x (which allows unbiased approximation of marginal expectations). And they support ecient computation of the normalizing constant  = (cid:80) x   ( x ) (or simply guarantee  = 1) for any value of the model parameters. How about training? Briefly: If a sequence model can eciently compute   ( x ) (and its derivatives  Part of this work was done at Facebook AI. with respect to model parameters), then it is ecient to compute parameter updates for noise-contrastive estimation (Gutmann and Hyvrinen, 2010; Gutmann and Hyvrinen, 2012) or score-matching (Hyvrinen, 2005). If sampling x or computing  (and its derivatives) is also ecient, then it is ecient 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. to compute from a fixed parameter vector. These models satisfy all three of the desiderata above. By using flexible neural network architectures, standard autoregressive models have achieved stellar empirical results in many applications (Oord et al., 2016; Child et al., 2019; Zellers et al., 2019; Brown et al., 2020). However there are still tasks that they have not mastered: e.g. , it is reported that they struggle at deep logical structure, even when initialized to huge pretrained models (Wang et al., 2019a). We point out that, unfortunately, there are certain sequence distributions whose unnormalized string probabilities   ( x ) are easy to compute individually, yet whose autoregressive factors  (   | x < ) are NP -hard to compute or even approximate, or are even uncomputable . Thus, standard autoregressive models are misspecified for these distributions (can-not fit them). It does not help much to focus on strings of bounded length, or to enlarge the model: under the common complexity-theoretic assumption NP (cid:42) P / poly, the parameter size |   | must grow superpolynomially in  to eciently approximate the probabilities of all strings of length up to  . Indeed, one of our main findings is that there exist unweighted languages   P for which no standard autoregressive model has  as its support, i.e. , assigns weight > 0 to just the strings x   . This is downright depressing, considering the costs invested in training huge parametric autoregressive models (Bender et al., 2021). Since   P, it is trivial to build an ecient scoring function   ( x ) with fixed parameters that has  as its support  just not an autoregressive one. The problem holds for all standard autoregressive models, regardless of how much computation and training data are used to learn the model parameters. That is, for an NP-hard problem, scoring a string x under a standard autoregressive model  ( x ) cannot be used to verify a witness. Nor can finding a witness be solved by prompting such a model with a description of a problem instance and sampling a continuation x of that string. Such problems are abundant in NLP: for example, surface realization under Optimality Theory (Idsardi, 2006), decoding text from an AMR parse (Cai and Knight, 2013), phrase alignment between two sentences (DeNero and Klein, 2008), and in general inference for propositional logic (Cook, 1971), which underlies the NP-hardness of general natural language inference, as in Figure 1. In other words, our results imply that standard autoregressive models do not have the right structure to capture important linguistic regularities: e.g. , that observed sequences were in fact constructed to be phonologically optimal, expressive of a semantic form, or logically coherent! Our work is also relevant to autoregressive models of fixed-dimensional vectors, such as NADE (Uria et al., 2016). These can be extended to arbitrary  dimensional vectors by providing separate parameters   for each  . Our constructions imply that for some distributions, |   | must grow superpolynomially in  , even though this would be not be necessary if the models were not autoregressive. In the remainder of this paper, we formalize our three desiderata for sequence models. We formalize compact autoregressive models and describe some limitations on their expressiveness. We then show that it can help to choose an alternative model family that relaxes any one of the three desiderata (Table 1). An unweighted language     is a set of strings x over a finite alphabet  . A weighted language   is a function   :    R  0 . It may be regarded as specifying an unweighted language  = support (   ) (cid:44) { x :   ( x )  0 } along with positive weights for the strings in  . We say that a weighted language   is normalizable if its global normalizing constant  (cid:44) (cid:80) x      ( x ) is finite and strictly positive. When   is normalizable,  ( x ) (cid:44)   ( x )/  is a probability distribution over  . A distribution is any weighted language whose global normalizing constant is 1. Let  x (cid:22) x mean that  x is a prefix of x    (not necessarily a strict prefix). If   is normalizable, then  (  x ) (cid:44) (cid:80) x    : x (cid:22) x   ( x ) is   for any  x    , yielding a marginal prefix probability  (  x )/  . If the prefix  x has positive prefix probability, then it admits a local conditional probability  (  |  x ) (cid:44)  (  x  )/  (  x ) for each symbol    , where the denominator is interpreted as a local normalizing constant . This is the conditional probability that if a random string starts with the prefix  x , the next symbol is  . There is also a probability  ( $ |  x ) (cid:44) 1  (cid:80)     (  |  x ) =   (  x )/  (  x )  0 that the string ends immediately after  x ; the special symbol $   represents end of string. 2.2 Computation for weighted languages We define a weighted language   to be computable if it is defined by a Turing machine (also called   ) that maps any x    to   ( x )  Q  0 in finite time. The Turing machine does not have to compute  . While the computable weighted languages allow any computable function as   , most architectures for defining weighted languages ( e.g. , RNNs or Transformers) do only a bounded or linear amount of work per input symbol. As a result, they compute   ( x ) in time  ( poly (| x |)) (that is,    FP). We refer to such weighted languages as eciently computable ( EC ). This does not imply that the normalized version  is eciently computable, since finding the denominator  requires summing over all of   . If we tried to construct the same normalized distribution  as in the previous paragraph using a standard autoregressive model, we would model it as a product of local conditional probabilities,  ( x ) = ( (cid:81) | x |  = 1  (   | x < ))  ( $ | x ) . Most such architectures again do only a bounded or linear amount of work per input symbol. Yet one suspects that this may not always be enough work to do the job: the local conditional probabilities of the original   are expensive to compute (unless   has some special structure making  (  x ) tractable). Indeed, the observation of this paper is that for some eciently computable weighted languages   , the local conditional probabilities are expensive to compute or even to approximate well. More precisely, autoregressive models cannot fit the local conditional probabilities unless they are superpolynomial in either their runtime or in their number of parameters (where the parameters may be precomputed at training time). We now explain how to formalize these notions. In the machine learning approach to sequence modeling, we usually do not manually design the Turing machine behind   . Rather, we design a model  with parameters  . is a Turing machine that reads  and outputs a specialized Turing machine    (cid:44)  (  ) that can score strings x and hence defines a weighted language. Without loss of generality, we will express  as a string in B  (where B (cid:44) { 0 , 1 } ). Strings vary in length, and accurate modeling of longer strings may sometimes require more complex computations with more parameters. For example, when  is a natural language alphabet, a recurrent neural network may require more hidden units to model sentences of the language rather than individual words,and even more units to model whole documents. To accommodate this, we allow an infinite sequence of parameter vectors,  = {    B  |   N } , which yields an infinite sequence of Turing machines {    |   N } via    (cid:44)  (   ) . We then define    ( x ) (cid:44)   | x | ( x ) , so a string of length  is scored by the    machine. This is known as non-uniform computation . Of course, it is legal (and common) for all of the   to be equal, or empty, but if desired, we can obtain more power by allowing the number of parameters to grow with  if needed. We can now consider how rapidly the parametric and runtime complexity may grow. If |   | is permitted to grow exponentially, then one can fit any weighted language   (even an uncomputable one). 2 Simply use   to encode a trie with  (|  |  + 1 ) nodes that maps x    ( x ) for any | x | of length  , and design  such that the Turing machine    =  (   ) has a (large) state transition table that mirrors the structure of this trie. The resulting collection of Turing machines {    |   N } can then compute   ( x ) exactly for any x , with only linear runtime  (| x |) (which is used to traverse the trie). Separately, if unbounded runtime is permitted for  , then one can exactly fit any computable weighted language   . Simply have  , when run on   , compute and return the large trie-structured    that was mentioned above. In this case,  need not even use the parameters   , except to determine  . Finally, if unbounded runtime is permitted for    , then again one can exactly fit any computable weighted language   . In this case,  trivially returns    =   for all  . However, if the parameters  are compact in the sense that |   | grows only as  ( poly (  )) , and also    =  (   ) is constructed by  in time  ( poly (  )) , and    scores any x of length  in time  ( poly (  )) , then we say that the resulting weighted language   is eciently computable with compact parameters (ECCP). 3 We refer 2 See our remark on computability in Appendix A. 3 Since we require  to run in polytime, it can only look at a polynomial-sized portion of   . compact values for  as an ECCP model . Neural models of weighted languages are typically ECCP models. The construction and execution of the neural network    may perform a polynomial amount of total computation to score the string x . This computation may involve parameters that were precomputed using any amount of eort ( e.g. , training on data) or even obtained from an oracle (they need not be computable). However, the exponentially many strings of length  must share a polynomial-size parameter vector   , which prevents the solution given in the first bullet point above. In practice one takes   =  for all  and obtains   R  by training. However, we do not consider whether such parameters are easy to estimate or even computable. We simply ask, for a given target language   , whether there exists a polynomially growing sequence  of good parameter vectors for any parametric model  . When not, there can be no scheme for estimating arbitrarily long finite prefixes of such a sequence. So for any polynomial  , any training scheme that purports to return a trained model of size  (  ) that works well for strings of length   must fail for large enough   even if unlimited data, computation, and oracles are allowed at training time. The phrase eciently computable with compact parameters means that without access to those parameters, the ECCP weighted language may no longer be eciently computable. Indeed, it need not be computable at all, if the parameter vectors store the outputs of some uncomputable function. Our definitions above of EC and ECCP weighted languages are weighted generalizations of complexity classes P and P / poly, respectively, 4 and their supports are always unweighted languages in P and P / poly, respectively. An unweighted language  is in P i there is a deterministic Turing machine that decides in  ( poly (| x |)) time whether x   . And an unweighted language  (cid:48) is in P / poly i 5 there exist the parameters  p  to be compact, but we nonetheless include this intuitive condition, without loss of generality. 4 Namely the nonnegative functions in FP and FP / poly. 5 Our presentation of P / poly is a variant of Arora and Barak (2009, 6), in which inputs x of length  are evaluated by a polytime function  that is given an advice string   as an auxiliary argument. This corresponds to a neural architecture  that can consult trained parameters   at runtime. We have replaced the standard call  (   , x ) with the curried expression  (   )( x ) , which we still require to execute in polynomial total time. Here the intermediate result   =  (   ) corresponds to a Turing machines {   :   N } such that   decides in  ( poly (  )) time whether x of length  is in  (cid:48) , where each   can be constructed in  ( poly (  )) time as  (   ) , for some Turing machine  and some sequence of polynomially-sized advice strings  = {   |   N } with |   |   ( poly (  )) . We define the language class NP / poly similarly to P / poly: the only dierence is the family {   :   N } consists of nondeterministic Turing machines . Naturally, P  P / poly. But P / poly is larger than P: it contains all sparse languages, regardless of their hardness  even sparse undecidable languages  as well as many dense languages. The extra power of P / poly comes from its access to compact advice strings that do not have to be recursively enumerable, let alone ecient to find. This corresponds to statistical modeling, where the trained model has a computationally ecient architecture plus access to parameters that might have taken a long time to find. NP-complete decision problems have solutions that are ecient to validate but inecient to find (assuming P  NP). One of the most well-known NP-complete problems is the boolean satisfiability problem (Sat) (Cook, 1971). Given a boolean formula  , Sat accepts  i  can be satisfied by some value assignment. For example, the formula (  1   2   3 )  (  1   4 ) is in Sat, since there is a satisfying assignment  1 ... 4 = 1101 . We denote the number of satisfying assignments to  as # (  ) . It is widely believed that no NP-complete languages are in P / poly. Otherwise we would have all of NP  P / poly and the polynomial hierarchy would collapse at the second level (Karp and Lipton, 1980). A capacity limitation of EC/ECCP weighted languages naturally follows from this belief: 6 Lemma 1. For any   P , there exists an EC weighted language with support  . For any   P / poly ,there exists an ECCP language withsupport  . But for any   NP complete , there exists no ECCP language with support  (assuming NP (cid:42) P / poly ). In addition to not capturing the support of NP-complete languages, ECCP weighted languages can-trained runtime model for inputs of length  . Our Turing machines   have size polynomial in  (because they are constructed by  in polynomial time). They correspond to the polynomial-sized boolean circuits   that are used to evaluate inputs of length  under the classical definition of P / poly (Ladner, 1975). We exposed these intermediate results   only to observe in 2.3 and 4.3 that if we had allowed the   to grow exponentially, they would have been able to encode the answers in tries. 6 All omitted proofs are in Appendix A. not help solve other NP-hard problems, either. For example, many structured prediction problems in NLP can be formulated as argmax x : x (cid:22) x   ( x ) : we are given a prefix  x as input and look for its optimal continuation under   . But if this problem is NP-hard for a particular   , then it is not in P / poly (assuming NP (cid:42) P / poly), so it cannot be accomplished by any polytime algorithm that queries an ECCP model. 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 (cid:42) P / poly. Many parameter estimation techniques and inference methods specifically work with local conditional probabilities  (  |  x ) . Thus, it is common to use parametric models where such quantities can be computed in time  ( poly (|  x |)) (given the parameters). 7 These are the standard autoregressive models we discussed in 1. We say that the resulting distributions are eciently locally normalizable , or ELN . We may again generalize ELNs to allow the use of compact parameters. For any weighted language   , the Turing machine  q eciently locally normalizes   with compact parameters  q = {  q  |   N } if  the parameter size |  q  | grows only as  ( poly (  ))   q (  q  ) returns a Turing machine   (similar to    in 2.3) in time  ( poly (  ))    is normalizable (so  exists)    maps  x    (  |  x ) for all     { $ } and all prefixes  x    with |  x |   and  (  x ) > 0 7 An autoregressive model architecture generally defines  ( x ) as an eciently computable (2.2) product of local conditional probabilities. However, the parametrization usually ensures only that (cid:80)      (  |  x ) = 1 for all prefixes  x . Some parameter settings may give rise to inconsistent distributions where  (cid:44) (cid:80) x      ( x ) < 1 because the generative process terminates with probability < 1 (Chen et al., 2018). In this case, the factors   (  |  x ) defined by the autoregressive model are not actually the conditional probabilities of the weighted language (as defined by 2.1). It is true that training  with a likelihood objective does encourage finding a weighted language whose generative process always terminates (hence  = 1), since this is the behavior observed in the training corpus (Chi and Geman, 1998; Chen et al., 2018; Welleck et al., 2020). Our definitions of ELN(CP) models require the actual conditionalprobabilities to be eciently computable. Autoregressive models that do not sum to 1, whose normalized probabilities can be uncomputable, are not ruled out by our theorems that concern ELN(CP). runs on those inputs  x  in time  ( poly (  )) If there is  q that eciently locally normalizes a weighted language   with compact parameters  q , we say   is eciently locally normalizable with compact parameters , or ELNCP . Note that this is a property of the weighted language itself. In this case, it is obvious that   is ECCP: Lemma 2. An ELNCP model   is also ECCP. Likewise, an ELN model is also EC. If we define ELNCP models analogously to ECCP models, Lemma 2 means that locally normalized models do not provide any extra power. Their distributions can always be captured by globally normalized models (of an appropriate architecture that we used in the proof). But we will see in Theorem 1 that the converse is likely nottrue: providedthatNP (cid:42) P / poly,there are eciently computable weighted languages that cannot be eciently locally normalized, even with the help of compact parameters. That is, they are EC (hence ECCP), yet they are not ELNCP (hence not ELN). We reducing Sat to computing certain local conditional probabilities of   (as defined in 2.1). Each decision Sat (  ) (where  ranges over formulas) corresponds to a particular local conditional probability, implying that there is no polytime scheme for computing all of these probabilities, even with polynomially sized advice strings ( i.e. , parameters). Without loss of generality, we consider only formulae  such that the set of variables mentioned at least once in  is {  1 , . . . ,   } for some   N ; we use |  | to denote the number of variables  in  . We say that a satisfies  if a  B |  | and (  1 =  1 , . . . ,  |  | =  |  | ) is a satisfying assignment. Finally, let boldface   B  denote enc (  ) where enc is a prefix-free encoding function. We can now define the unweighted language  = {  a |  is a formula and a  B |  | and a satisfies  } over alphabet B , which contains each possible Sat problem concatenated to each of its solutions. 8 We now convert  to a weighted language   , defined by   ( x ) =   (  , a ) = ( 13 ) | x |+ 1 for x   (oth-erwise   ( x ) = 0). is normalizable since  is both finite (  = (cid:80) x  B    ( x )  (cid:80) x  B  ( 13 ) | x |+ 1 = 1) and positive (  > 0 because the example string in footnote 8 has weight > 0). The conditional distribution 8 For example,  contains the string  a where  = enc ((  1    2   3 )  (  1    4 )) and a = 1101 . is eciently computable,and so is  =   /  . 9 Yet deciding whether the local conditional probabilities of   are greater than 0 is NP-hard. In particular, we show that Sat can be reduced to deciding whether certain local probabilities are greater than 0, namely the ones that condition on prefixes  x that consist only of a formula:  x =  for some  . This implies, assuming NP (cid:42) P / poly,thatno (  q ,  q ) can eciently locally normalize   with compact parameters. Granted, the restriction of   to the finite set { x  B  : | x |   } can be locally normalized by some polytime Turing machine   , using the same trie trick sketched in 2.3. But such tries have sizes growing exponentially in  , and it is not possible to produce a sequence of such machines, {   :   N } , via a single master Turing machine  q that runs in  ( poly (  )) on  q  . That is: Theorem 1. Assuming NP (cid:42) P / poly , there exists an eciently computable normalizable weighted language   that is not ELNCP. Proof sketch. Take   to be the weighted language we defined earlier in this section. is clearly eciently computable. We will show that if it is ELNCP via (  q ,  q ) , then the NP-complete problem Sat is in P / poly, contradicting the assumption. We must give a method for using (  q ,  q ) to decide Sat in polytime and with compact parameters  . Given  , our method constructs a simple related formula  (cid:48) such that   (cid:48) has at least one satisfying assignment (so  (  (cid:48) ) > 0 and thus  ( 1 |  (cid:48) ) is defined)   (cid:48) has satisfying assignments with  1 = 1 ( i.e. ,  ( 1 |  (cid:48) ) > 0) if and only if  is satisfiable Our construction also provides a polynomial function  such that |  (cid:48) | is guaranteed to be   (|  |) . We now define  by   =  q  (  ) (  ) . When our Sat algorithm with compact parameters  is given  of length  , it can use the polynomial-size advice string   to ask (  q ,  q ) in polynomial time for  ( 1 |  (cid:48) ) . Sat (  ) returns true i that probability is > 0. 10 (cid:3) 3.3 ELNCP models cannot even capture all EC (or ECCP) supports or rankings We can strengthen Theorem 1 as follows: Theorem 2. Assuming NP (cid:42) P / poly , there exists an eciently computable normalizable weighted 9 Almost. This  couldbeirrational,butatleastitiscomputable to any desired precision. For any rational     , we can say   =   /     is EC, via a Turing machine    that stores   . Further remarks on irrationality appear in Appendix A. 10 See also the remark on implications for seq2seq models following the proof in Appendix A. language   where there is no ELNCP   such that support (   ) = support (   ) . Proof. Observe that for any two weighted languages   and   with the same support,   x    ,    (  x ) > 0     (  x ) > 0 (where    and    return the prefix probabilities of   and   respectively). Thus, for any  x with    (  x ) > 0,  ( 1 |  x ) (cid:44)    (  x 1 )/    (  x ) and  ( 1 |  x ) (cid:44)    (  x 1 )/    (  x ) are well-defined and  ( 1 |  x ) > 0   ( 1 |  x ) > 0. If   is ELNCP, then all such probabilities  ( 1 |  x ) can be computed in polytime with compact parameters, so it is likewise ecient to determine whether  ( 1 |  x ) > 0. But this cannot be the case when   is the weighted language used in the proof of Theorem 1, since that would suce to establish that Sat  P / poly, following the proof of that theorem. (cid:3) To put this another way, there exists an unweighted language in P (namely support (   ) ) that is not the support of any ELNCP distribution. If they have dierent support, normalizable languages also dier in their ranking of strings: Lemma 3. Let  ,   be normalizable weighted languages with support (   )  support (   ) . Then  x 1 , x 2    such that   ( x 1 ) <   ( x 2 ) but   ( x 1 )    ( x 2 ) . Therefore, no ELNCP   captures the string ranking of   from Theorem 2. And for some   , any ELNCP   misranks even string pairs of similar lengths: Theorem 3. Assuming NP (cid:42) P / poly , there exists an eciently computable normalizable weighted language   such that no ELNCP   with support (   )  support (   ) has   ( x 1 ) <   ( x 2 )    ( x 1 ) <   ( x 2 ) for all x 1 , x 2    . Indeed, any such   has a counterexample where   ( x 1 ) = 0 . Moreover, there is a polynomial    : N  N such that a counterexample exists for every x 1 such that   ( x 1 ) = 0 and   ( x 1 ) > 0 , where the x 2 in this counterexample always satisfies | x 2 |     (| x 1 |) . Theorem 3 is relevant if one wishes to train a model   to rerank strings that are proposed by anothermethod ( e.g. , beam search on   , or exact  -best decoding from a more tractable distribution). If the desired rankings are given by Theorem 3's   , any smoothed 11 ELNCP model   will misrank some sets of candidate strings, even sets all of whose strings are close in length, by failing to rank an impossible string ( x 1 with   ( x 1 ) = 0) below a possible one ( x 2 with   ( x 2 ) > 0). 11 Smoothing is used to avoid ever incorrectly predicting 0 (a false negative) by ensuring support (   )  support (   ) . E.g., autoregressive language models often define  (  |  x ) using a softmax over   { $ } , ensuring that  ( x ) > 0 for all x    . Theorem 2 implies that there exists   whose local probabilities  (  |  x ) are not approximated by any ELNCP  to within any constant factor  , since that would perfectly distinguish zeroes from non-zeroes and the resulting support sets would be equal. 12 However,this demonstration hinges on the diculty of multiplicative approximation of zeroes  whereas real-world distributions may lack zeroes. Below we further show that it is hard even to approximate the non-zero local conditional probabilities (even with the additional help of randomness). Theorem 4. Assuming NP (cid:42) P / poly , there exists an eciently computable weighted language   :    R  0 such that there is no (  q ,  q ) where  q = {  q  |   N } that satisfies all of the following properties (similar to 3.1):  the parameter size |  q  | grows only as  ( poly (  ))   q (  q  ) returns a probabilistic Turing machine   in time  ( poly (  ))  there exists   1 such that for each     { $ } and  x    with |  x |   and  (  |  x ) > 0 , the probabilistic computation   (  x  ) has probability > 2 / 3 of approximating  (  |  x ) to within a factor of  (that is,   (  x  )/  (  |  x )  [ 1 / ,  ] )    runs on those inputs  x  in time  ( poly (  )) Moreover, the statement above remains true (a) when the approximation guarantee is only required to hold for prefixes  x where { x :  x (cid:22) x } is finite (so  (  |  x ) is computable by brute force) (b) or, when support (   ) =   3.5 ELN models are unconditionally weak Our above results rely on the NP -hardness of computing or approximating an EC distribution's autoregressive factors  ( | x < ) . In Appendix A, we show that these factors can even be uncomputable . In such cases, the distribution cannot be ELN (Theorem 5), though sometimes it is still ELNCP (Theorem 6). This result does not assume P  NP or NP (cid:42) P / poly. We now discuss alternative families of sequence distributions that trade away eciency or compactness in exchange for greater capacity, as shown in Table 12 Droppingthenormalizationrequirementontheapproximated local probabilities (so that possibly (cid:80)     (  |  x )  1) does not help. Otherwise, again, Sat could be solved in polynomial time (with the help of polysize advice strings) by using  ( 1 |  (cid:48) ) to determine in the proof of Theorem 1 whether  ( 1 |  (cid:48) ) > 0. 4.1 Energy-based models (EBMs) Energy-based models (LeCun et al., 2006) of discrete sequences (Rosenfeld et al., 2001; Sandbank, 2008; Huang et al., 2018) traditionally refer to the EC models of 2.2. Only the unnormalized probabilities    ( x ) are required to be eciently computable. Lemmas 1 and 2 showed that this model family contains all ELN languages and can achieve any support in P. Theorem 1 shows that it also contains languages that are not ELN or even ELNCP: intuitively, the reason is that the sums  (  x ) needed to compute the local normalizing constants (see 2.1) can be intractable. If we generalize energy-based sequence models to include all ECCP models  that is, we allow nonuniform computation with compact parameters  then Lemmas 1 and 2 guarantee that they can capture all ELNCP languages and furthermore all languages in P / poly (though still not NP-complete languages). Experiments on dierent parameterizations. Maximum-likelihood parameter estimation (MLE) can be expensive in an EBM because the likelihood formula involves the expensive summation  = (cid:80) x       ( x ) . This forces us in practice to use alternative estimators that do not require computing normalized probabilities,such as noise-contrastive estimation (NCE) or score matching (1), which are less statistically ecient. In pilot experiments we found that both RNNand Transformer-based EBMs trained with NCE achieved worse held-out perplexity than comparable locally normalized models trained with MLE. 13 Fortunately, it is possible to infuse a globally normalized architecture with the inductive bias of a locally normalized one, which empirically yields good results. Residual energy-based models ( REBMs ) (Bakhtin et al., 2021) are a simple hybrid architecture:   ( x )     ( x ) (cid:44)  0 ( x )  exp   ( x ) This simply multiplies our previous weight by a new factor  0 ( x ) . The base model  0 :   ( 0 , 1 ] is a locally normalized neural sequence model (ELN model) that was pretrained on the same distribution. :    R is a learnable function (with parameters  ) that is used to adjust  0 , yielding a weighted language    with the same support  . We implemented 13 This might be due to a capacity limitation of the specific globally normalized architectures ( i.e. , no parameters work well), or excess capacity ( i.e. , too many parameters work well on the finite sample), or statistical ineciency of the estimator (the NCE objective on the finite sample, with the noise distribution we chose, does not distinguish among parameters as well as MLE does), or an optimization diculty caused by local optima in the NCE optimization landscape. REBMs, again with NCE training, and evaluated them on two dierent neural architectures (GRUand Transformer-based) and 3 datasets (WikiText (Merity et al., 2017), Yelp (Yelp), and RealNews (Zellers et al., 2019)). In each setting we tried, the REBM slightly but significantly improved the perplexity of the base model  0 (  < 0 . 05). 14 4.2 Latent-variable models Autoregressive models have  = 1 for any setting of the parameters (or at least any setting that guarantees consistency: see footnote 7). Clearly  = 1 ensures that  is both finite and tractable. Can we find a model family that retains this convenience (unlike EBMs), while still being expressive enough to have any non-empty language in P as support? Autoregressive latent-variable models form such a family. As in directed graphical models, the use of latent variables provides a natural way to model partial observations of an underlying stochastic sequence of events. We will model an observed sequence x of length  as a function of a latent string z of length  ( poly (  )) . As in EBMs, the probability  ( x ) can be computationally intractable, allowing these models to break the expressivity bottleneck of ordinary autoregressive models. However, the intractability no longer comes from exponentially many summands in the denominator  , but rather from exponentially many summands in the numerator  namely, the summation over all latent z that could have produced x . Notice that as a result, even unnormalized string weights are now hard to compute, although once computed they are already normalized. Formally, we define marginalized weighted languages. We say that   is a marginalization of the weighted language   if it can be expressed as   ( x ) = (cid:80) z :  ( z ) = x   ( z ) , where  :     is some function (the marginalization operator ). We say it is a light marginalization if | z |   ( poly (|  ( z )|)) and  runs in time  ( poly (| z |)) . 15 Typically  ( z ) extracts a subsequence of z ; it can be regarded as keeping the observed symbols while throwing away a polynomially bounded number of latent symbols. Light marginalizations of ELN distributions are a 14 We independently conceived of and implemented the REBM idea proposed in Bakhtin et al. (2021). Details of neural architecture choice, model parameter sizes, training regimen, and evaluation (Appendices BD) dier between our work and theirs, which also reported positive empirical results (on dierent datasets). We regard the two independent positive findings as a strong indication that the REBM design is eective. 15 WLOG,  can be required to run in linear time  (| z |) , as it does in our constructions below. reasonable formalization of latent-variable autoregressive models. They are more powerful than ELN distributions, and even include some distributions that (by Lemma 1) are not even ELNCP or ECCP: Theorem 7. There exists a light marginalization  of an ELN distribution, such that support (  ) is an NP -complete language. Our proof of Theorem 7 relies on special structure of a certain NP-complete language (Sat) and does not evidently generalize to all languages in NP. However, light marginalizations of ELNCP distributions are more powerful still, 16 and can have any language  NP or even NP / poly (2.4) as support: Theorem 8. The following statements are equivalent for any nonempty     : (a)   NP / poly . (b)  is the support of a light marginalization of an ELNCP distribution. (c)  is the support of a light marginalization of an ECCP weighted language. Theorems 7 and 8 make use of unrestricted latent-variable autoregressive models. There exist more practical restricted families of such models that admit tractable computation of  ( x ) (Laerty et al., 2001; Rastogi et al., 2016; Wu et al., 2018; Buys and Blunsom, 2018). Such models are EC (and indeed, typically ELN)  but this limits their expressivity, by Theorem 1. Both Lin et al. (2019) and Buys and Blunsom (2018) observed that such models yield worse empirical results than models that do not have tractable exact inference methods. The tractability requirement is dropped in self-talk (blixt, 2020; Gontier et al., 2020; Shwartz et al., 2020), where a neural autoregressive language model generates an analysis of the prefix  x via latent intermediate symbols before predicting the next output symbol. 17 We remark that for autoregressive models, the position of the latent variables is significant. Marginalizing out latent variables at the end of the string adds no power. More precisely, if an ELNCP distribution is over strings z of the form x # y , then its marginalization 16 The capacity established by Theorem 8 does not need the full power of marginalization. We could similarly define light max-imizations of ELNCP distributions,   ( x ) = max z :  ( z ) = x   ( z ) . Replacing sum by max does not change the support. 17 Here the marginal distribution of the next observed symbol can require superpolynomial time to compute (if #P  FP, which follows from NP (cid:42) P / poly). Theorem 1 could likewise be evaded by other autoregressive approaches that invest superpolynomial computation in predicting the next symbol (Graves, 2016). Each autoregressive stepmightexplicitlyinvoke lookaheadorreasoning algorithms, just as feed-forward network layers can invoke optimizers orsolvers (Amos andKolter,2017; Wang et al.,2019b). via  ( x # y ) = x can be expressed more simply as an ELNCP language. Thus, by Theorem 2, marginalizations of such distributions cannot have arbitrary NP languages as support. Our proofs of Theorems 7 and 8 instead use latent strings of the form y # x , where all latent variables precede all observed ones (as in Kingma and Welling, 2014). (This simple design can always be used without loss of generality.) Trying to reorder those latent strings as x # y while preserving their weights would have yielded a non-ELNCP distribution  ( x # y ) (because if it were ELNCP, then  ( x ) would be ELNCP also, and we know from Lemma 1 that it cannot be for any distribution whose support is an NP-complete language). How about lightly marginalizing ECCP languages instead of ELNCP ones? This cannot model any additional unweighted languages, by Theorem 8. But it may be able to model more probability distributions. One can easily construct a light marginalization  of an ECCP distribution such that # (  ) =     (  ) , where # (  ) is the number of satisfying assignments of  and the constant   depends only on  = |  | . We conjecture that this is not possible with lightly marginalized ELNCP distributions. 2.3 noted that with exponential growth in stored parameters, it is possible to fit any weighted language up to length  , with local probabilities computed in only  (  ) time by lookup. Of course this rapidly becomes impractical as  increases, even if the amount of training data increases accordingly. However, there has been some recent movement toward storage-heavy models. Such models are typically semiparametric: they use a parametric neural model, such as an autoregressive model, together with an external knowledge base of text strings or factoids that are not memorized in the layer weights. The neural model generates queries against the knowledge base and combines their results. Examples include  NNLMs (Khandel-wal et al., 2020) and semiparametric LMs (Yogatama et al., 2021). The knowledge base grows linearly with the training data rather than compressing the data into a smaller parameter vector. It is in fact a copy of the training data, indexed to allow fast lookup (Indyk and Motwani, 1998). (Preparing the index is much cheaper than neural network training.) Access to the large knowledge base may reduce the amount of computation needed to find the local conditional probabilities, much as in the trie construction of 2.3. Chen et al. (2018) show that it is hard to map RNN parameters to properties of the resulting autoregressive weighted language, such as consistency (  = 1). We focus on cases where the RNN parameters are already known to be consistent, so the RNN eciently maps a string  x to its local conditional distribution  ( |  x ) . Our point is that for some weighted languages, this is not possible (even allowing polynomially larger RNNs for longer strings), so consistent RNNs and their ilk cannot be used to describe such languages. In a Bayes network  which is really just an autoregressive model of fixed-length strings  approximate marginalinference is NP-hard(Roth,1996). Assuming NP (cid:42) P / poly and the grid-minor hypothesis, Chan-drasekaran et al. (2008, Theorem 5.6) further showed that for any infinite sequence of graphs  1 ,  2 , . . . where   has treewidth  , there is no sequence of algorithms  1 ,  2 , . . . such that   performs approximate marginal inference in time  ( poly (  )) on graphical models of structure   . This remarkable negative result says that in any graph sequence of unbounded treewidth, approximating the normalizing constant for   given arbitrary parameters is hard (not  ( poly (  )) ), even with advice strings. Our negative result (Theorem 4) focuses on one particular infinite weighted language, showing that approximating local conditional probabilities given an arbitrary length prefix is hard in the same way. (So this language cannot be captured by an RNN, even with advice strings.) 6 Conclusion and future work Autoregressive models are suited to those probability distributions whose prefix probabilities are eciently computable. This eciency 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 suxes or latent variables. All model families we have discussed in this paper can be seen as making compromises between dierent desiderata (Table 1). Natural follow-up questions include Are there model families that win on all fronts?' What are other modeling desiderata?' While some languages  P cannot be supports of ELNCPs, we do not know if the same can be said for most languages  P. This problem seems to be closely related to the average complexity of NP-complete languages, where most questions remain open (Levin, 1986; Bogdanov and Trevisan, 2006). We thank the anonymous reviewers for their comments. We also thank our colleagues at Johns Hopkins University, Facebook, and Carnegie Mellon University for their comments on earlier versions of the manuscript. This material is based upon work at Johns Hopkins University supported by the National Science Foundation under Grant No. 1718846. It does not represent the views of Microsoft (where Dr. Eisner is also a paid employee, in an arrangement that has been reviewed and approved by the Johns Hopkins University in accordance with its conflict of interest policies).
abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain objective abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain objective objective result other other other abstain other other other other other method other other other abstain other method other other method other objective method method other abstain other other abstain method other abstain method other other other other other other other other other abstain other other other other other other method abstain other other other other abstain other abstain other method other method other method other other other other other other other other abstain other abstain other other other other method other abstain other method other method method abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain abstain method abstain method abstain abstain method method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain method method method method method abstain abstain abstain abstain abstain other abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain other abstain abstain abstain abstain abstain abstain method other other other other