On the Uncomputability of Partition Functions in Energy-Based Sequence Models
Authors: Chu-Cheng Lin
Arya D. McCarthy
Venue: ICLR 2022 Spotlight (2022)
Keywords: energy-based models
turing completeness
model capacity
sequence models
autoregressive models
partition function
parameter estimation
model selection

Abstract: In this paper, we argue that energy-based sequence models backed by expressive parametric families can result in uncomputable and inapproximable partition functions. Among other things, this makes model selection--and therefore learning model parameters--not only difficult, but generally _undecidable_. The reason is that there are no good deterministic or randomized estimates of partition functions. Specifically, we exhibit a pathological example where under common assumptions, _no_ useful importance sampling estimates of the partition function can guarantee to have variance bounded below a rational number. As alternatives, we consider sequence model families whose partition functions are computable (if they exist), but at the cost of reduced expressiveness. Our theoretical results suggest that statistical procedures with asymptotic guarantees and sheer (but finite) amounts of compute are not the only things that make sequence modeling work; computability concerns must not be neglected as we consider more expressive model parametrizations.

Published as a conference paper at ICLR 2022
ON THE UNCOMPUTABILITY OF PARTITION FUNCTIONS IN ENERGY-BASED SEQUENCE MODELS
Chu-Cheng Lin & Arya D. McCarthy Center for Language and Speech Processing, Johns Hopkins University
ABSTRACT
In this paper, we argue that energy-based sequence models backed by expressive parametric families can result in uncomputable and inapproximable partition functions. Among other things, this makes model selection and therefore learning model parameters- not only difficult, but generally undecidable. The reason is that there are no good deterministic or randomized estimators of partition functions. Specifically, we exhibit a pathological example where under common assumptions, importance sampling estimators of the partition function can guarantee to have variance bounded below rational number. As alternatives, whose partition functions are computable (if they exist), but at the cost of reduced expressiveness. Our theoretical results suggest that statistical procedures with asymptotic guarantees and sheer (but finite) amounts of compute are not the only things that make sequence modeling work; computability concerns must not be neglected we consider more expressive model parametrizations.
useful
consider sequence model families
INTRODUCTION
Modeling discrete sequences is central natural language processing and bioinformatics. Many common parametric sequence models 5 are (or can be cast as) energy-based (LeCun et al., 2006): they yield a weight p(x) for any given string x. Although energy-based models (EBMs) of sequences need not represent probability distributions, they have been proposed as such to counter the inexpressivity of autoregressive sequence models (Bakhtin et al., 2021; Lin et al., 2021, $4.1). 1). EBMs with finite partition functions Zp - Σx ç(xx R..0 define distributions p(x) - p(x)/7,p over strings, which are often queried under the principle of probabilistic inference (Ghahramani, 2015).'
Energy-based sequence models are often parametrized as neural models. Each parameter vector 0 in some parametric neural network family Ø C Bdd identifies a parametric model Pg. which then defines a parametric distribution over strings Pa. assuming Zp exists (Chen et al., 2018). Contemporary neural networks have been shown to be very powerful. In particular, some popular parametric neural sequence model families, such as RNNs (Siegelmann & Sontag, 1995) and Transformers (Bhattamishra et al., 2020; Pérez. et al., 2021), have been formally shown to recognize recursively enumerable languages: given any Turing machine M. there is a parameter vector O such that the parametrized sequence model No recognizes the same language as M does. In other words, these sequence model families are Turing-complete.
It is therefore intuitive that energy-based sequence models, backed by such powerful neural networks, form expressive families of string distributions ($3.1): ): for any decision algorithm M, there a parameter vector 0M in during-compledt parametric family O such that Pan exists, and pa (x) is high if and only if M accepts x. would seem assuring to work with such expressive family of sequence distributions, O: assuming the true string probabilities indeed can be computed in polytime, O is well-specified. Moreover, one may assume that given we can sample from pear we would be able to use consistent estimators to find 0' < O where 6' 0..
Unfortunately, we find that with such an expressive distribution family O whether the identifiability assumption holds required for most consistent estimators - itself is undecidable (Turing, 1937).
Many popular energy- based sequence models compute normalized probabilities directly (i.e., p(x) p(x)) (Jelinek, 1980; Katz, 1987; Bengio et al., 2003; Brown al., 2020, inter alia). This makes both training and querying with string prefixes much easier, the cost of expressiveness (Linn al., 2021).

---

Published as a conference paper at ICLR 2022
Moreover, model selection any held-out data is also undecidable. Even worse, we show that there exists a vector 6' E O such that as long as a parametric family O' S O contains 0', model selection will not be possible for O' either- even when O' itself is not necessarily expressive (e.g.. O' can be fixed-size Transformer EBMs, which cannot parametrize all EBMs that require more parameters). We construct one such 'pathological' distribution py Transformer EBM.
These negative results stem from the uncomputability and inapproximability of Z. A main technical contribution of this paper is that there is no algorithm (either deterministic or randomized) that can approximate Z well. An immediate consequence is that sampling-baser statistical procedures are not useful in this scenario, either, as long as they terminate in finite time. However, we will see that for less expressive model families, such uncomputability issues do not arise. Our negative results are summarized in Table 1. To ensure that model selection is still possible (such that we can compare different parameter vectors with confidence). 2 we have no choice but to resort to less expressive string distributions.
The paper structured as follows. $2 we review definitions and known results of weighted languages, sequence model families, and formalize weighted Turing machines, EC-complete parametric families, and computable estimators. $$3-5 we describe our main technical results: there exist pathological EBM sequence models that have uncomputable partition functions, which cannot be approximated well under randomized estimators, and do not have asymptotic estimators that have any good guarantees. In $6 we that argue our negative results make model selection impossible for expressive model families, and discuss why common estimation methods fail. Finally, we discuss three 'palliative' parametrization choices in $7, which all guarantee computable partition functions, at the cost of expressiveness.
2
BACKGROUND
2.1 ENERGY-BASED SEQUENCE MODELS
Energy-based models (EBMs) of sequences (LeCun et al., 2006; Rosenfeld et al., 2001; Sandbank, 2008; Huang al., 2018; Bakhtin et al., 2021) are family of discrete sequence models. Given string x E V over finite vocabulary V. an EBM 5 computes string weight p(x), but not the (normalized) string probability pxx)= /(x)/E, p(x). this work, we focus on EBMs whose weight is efficiently computable, Le., polytime in the length of x. Previous work (Bakhtin et al., 2021; Lin et al., 2021) showed that EBMs define expressive distributions; but this requires normalization. While EBMs are often intractable to normalize (e.g., the Ising model), the infinite domain of finite strings opens the door uncomputable probabilities, which invite the impossibility of model selection and comparison.
2.2 WEIGHTED LANGUAGES
EBMs give weights to strings. Here we formally characterize these weighted strings as weighted language. An unweighted language L C V is set of finite strings x over a finite vocabulary V. A weighted language is a function V - Rgo.3 In this work, we discuss Boolean languages, such that V B- - {0, 1). We also focus on weighted languages where distributions over strings exist. Following Lin al. (2021), we say such weighted languages P are normalizable: Z,- & Eres p(x) E R Zp is also called the partition function of P. We can then normalize p into a distribution p over B such that p(x) = /Zp) and thereby Σxer p(x)= 1.
The efficiently computable (weighted) languages (EC; Lin et al., 2021) are those weighted languages p, where a string's 's weight (which must be non-negative) is a polytime function of the string. Weighted languages defined by most EBM sequence models fall into this class, since they score every string in finite time (and usually in polytime); and the scores ultimately are computed by some algorithm.
Intuitively, string weights of an EC language can be obtained as side product from weighted Turing machine that recognizes x (in polytime). However, Lin et al. (2021 1) did not precisely describe how a Turing machine maps input string to its (rational) weight p(x) in finite time. In this work, such construction (out of many possible ones) is necessary, as we need to show that this string weighting can be
20f course, model selection (and computing Zp)) are not always needed - for example, simply deciding whether f(x1) > ((x2) for two given strings x (1.2)- In such case the uncomputability issues we discuss are not concern. WWith slight abuse of notation, we also define support(p) () & (x p(x)) > 0).
"We use the convention that Z.p is the partition function of p. and Z of q. etc. The subscript is omitted in unambiguous cases.
2

---

Published as a conference paper at ICLR 2022
done by parametric sequence model families (see Appendix B).
2.3 LOCALLY NORMALIZED DISTRIBUTIONS
A popular subclass of weighted languages is locally normalized weighted languages (LN), where conditional local distributions given prefix &: p(- () can be computed in finite time. Since they automatically define distribution over strings, we use the term locally normalized distributions interchangeably. If p( | ()) can be computed polynomial time, we call such distributions efficiently locally normalized distributions (ELN) this is the weighted language class of most autoregressive models, just as its superset EC is the weighted language class of most energy-based based sequence models.
Locally normalized distributions over sequences have p(x) = pxx), and Z= Exx (xx) = 1. They are consistent: the probability that a string is infinitely long under such distributions is zero. Equivalently, given any O, can approximate Z with finite sum of string weights:
Proposition 1 (Consistency of LN distributions (Booth & Thompson, 1973; Chen et al., 2018)). Let p E LN be locally normalized distribution over strings. All strings of given length or longer have their probabilities bounded. That is, for all positive real numbers there is a length which all strings of length at least n have px) <
The consistency property of locally normalized distributions implies that they have an exact sampling procedure that almost surely terminates in finite time. Therefore, they (and in particular ELN distributions) are an attractive choice when we need to sample from the distribution they define, e.g., in sampling- -based parameter estimation procedures.
2.4 EC-COMPLETE PARAMETRIC FAMILIES
We have introduced based sequence models ($2.1) and their characterization as weighted languages ($2.2). However, we usually do not work with weighted Turing machines directly machine learning. Here the most common models of computation are (neural) sequence model families, such as RNNs and Transformers. While these computational models can appear quite dissimilar to sate-machine-basee models of computation (e.g.. Turing machines), they have been shown to possess the same computation power (Siegelmann & Sontag, 1995; Pérez et al., 2021). That is, they are Turing- complet.
Just we extend the definition of Turing machines weighted Turing machines, likewise formalize weighted sequence model families. We thus introduce EC-complete parametrie families as a sequence model counterpart of the weighted language class EC. At a high level, a parametric family O is EC-complete given any P E BC (as a description of a weighted Turing machine), we can construct a parameter vector 0 E O Q" which defines p's corresponding sequence model. The model produces output embedding which we then decide in polytime to be either a 'halting embedding or not. If it is, we can then extract the weight p(x). (A rigorous exposition is in Appendix C.)
We show that with a modification to positional embeddings, the family of arbitrary precision, hard attention Transformers defined in Pérez et al. (2021) is EC-complete:
Theorem 1. The class of one-encoder-layer four-decoder-layer Transformer networks with positional encodings (n, //, 1/22 2") is EC-complete.
Proof sketch. We extend the construction from Pérez et al. (2021), adding an additional layer to accumulate the string weight over time steps.
2.5 ESTIMATORS
A main result of this work is that partition functions in an EC-complete family are uncomputable. Moreover, randomness docs not help estimation; and correct asymptotic estimators are not useful. We define these estimators here in order to discuss the power of different estimators concretely.
Let O be a parametric family. The function f ① - Q is an exact estimator if there exists a weighted deterministic Turing machine that takes 0 input and, upon halting, outputs f0) E Q in finite time.
All proofs omitted from the main text are included in Appendix D. Proof sketches for major theorems are in the main text.
3

---

Published as a conference paper at ICLR 2022
Many estimation procedures are anytime algorithms: they do not have predetermined runtime, and they can be stopped at any time before completion to produce a valid output. Output quality of an anytime algorithm may improve with increased runtime. Moreover, many of these algorithms have asymptotic guarantees, in that their outputs are optimal in some sense (e.g., consistency) in the limit. We capture these algorithms with asymptotic estimators: a function f()) is an asymptotic estimator if there exists weighted Turing machine that takes both f and an index i as input, then outputs value fp.1 E Q in finite time, such that the outputs converge toward f(0) as i increases toward infinity. (An example is Zasym introduced at $5.)
We now extend both exact and asymptotic estimators to the stochastic case, where we compute the estimates using randomized algorithms instead of deterministic ones. As is conventional for randomized algorithms, we assume the use of probabilistic Turing machines. These have access to an infinitely long random tape. The tape describes an infinite binary sequence from tossing a fair two-sided coin infinitely many times. We call the random tape distribution p.. We define randomized exact estimator f as weighted Turing machine with two input tapes - the random tape r E B", and an input tape that has and outputs f00, 7) in finite time. Likewise, we say fe.; is randomized asymptotic estimator if there exists function f(0) E R and a weighted Turing machine that takes (0, i). T on two input tapes, so that for all random Boolean tapes B we converge with lim;-co fo,i.r f(0). Many Monte Carlo estimators can be seen as randomized asymptotic estimators, including rejection sampling and importance sampling estimators.
3 EXPRESSIVENESS AND UNCOMPUTABILITY. PATHOLOGICAL EBMs
3.1 EXPRESSIVE SEQUENCE DISTRIBUTIONS
To illustrate the uncomputability issues of energy-based models, we construct families of string distributions that are expressive: they require the full power of an EC-complete sequence model family.
We define G: {pMM. : k E Qso} to be set of weighted languages, where M is parametrized by deterministic Turing machine M that takes an empty string as input ('input-free"). Let I.M S be a prefix-free Boolean language of computation sequences of a Turing machine that is, encodings of the trace of the Turing machine M's operations. We define
1/31x101 + kk if LM, and x encodes a valid accepting trace of M. otherwise.
(x))(x)=
1/31k/41
The weight of any string x, where |x] = under PM. x can be computed in time (poly(n)), by verifying whether x is an accepting execution trace of M, from the initial state to an halting state. That is, f e EC ($2.2). We also know that for any (deterministic) machine M, the language's 's partition function Zpm exists, and it must equal either 1 or 1 + k, since there is either one halting trace (ZpM. = + k), or none (Z = 1). Therefore, each f E G2 defines a string distribution."
Since for all & E Q=o. G. C EC, all weighted languages 7MM. have an equivalent parameter vector O..K in any EC-complete family O. Also, since each G. is bijection between the set of all input-free Turing machines and a subset of O it follows that there is no exact estimator ($2.5) of the partition function of any EC-comeeete family (e.g.. Transformer EBMs (Theorem 1)), by a reduction from HALT:
Theorem 2.
Let + be a parametric EC-complete sequence model family. And let O2 O be bijective with Gx- There is no k E Qorofor which there exists an exact estimator 24, that takes as input A e O2 as input, and computes Zu (0) Z.o in finite time.
Proof sketch. O₁ contains parametric vectors for all input-free Turing machines M. For any of these
Formalll speaking, we define a probability space A. where Q B is our sample space, A (Ap that have prefix E B²) is our event space, and P(A) = 2 where is the length of the longest shared prefix of A, is our probability function (Stroock, 2014).
A, the set of all sequences
"Our construction of expressive sequence distributions is inspired by a weighted language construction in Lin et al.
(2021). See Appendix E for further discussion.
$Speaking loosely, HALT is the task of recognizing (deciding) whether given program on an ideal computer will properly terminate in finite time not (Sipser, 2013; Arora & Barak, 2006).
4

---

Published as a conference paper at ICLR 2022
weighted languages, knowing the exact value of Zpnr E {1, 1) is enough decide whether M halts (M halts iff Pp.., + 1). As HALT is undecidable for input-free Turing machines, 2x cannot exist.
3.2 AN EBM WHOSE PARTITION FUNCTION IS UNCOMPUTABLE
Theorem 2 states there is no estimator that 'works' for a subset of parameter vectors. While every GR much smaller than its superset EC, GE is still (countably) infinite. Here under the assumption that ZFC is consistent, we construct one weighted language h E Gi (for simplicity; it holds for arbitrary k), where Zg is uncomputable:
Theorem 3. Assuming ZFC axioms and that assuming they is consistent, there exists an EC weighted language b E Gi such that (a) Z3 c E [1,2] exists, but (b) there is no proof of Z c.
Proof sketch. We construct such that 74 = 2 iff ZFC is inconsistent. If there were a proof 75 = then we proved ZFC consistent, which is impossible under Gödel's 2nd incompleteness theorem (Jech, 1994). If there were proof Z = 2, then we proved ZFC is not consistent, which violated our assumption.
The existence of 5 suggests that if there is an algorithm that approximates Zp. and produces a witness of its approximation quality, then this algorithm will not work on any set of parameter vectors that can parametrize 5 - even when this algorithm may work for some subsets of O This is useful in allowing us to show negative results regarding finite subsets of Appendix gives one such example.
No RANDOMIZED ALGORITHM CAN ESTIMATE ACCURATELY
We've 'e've shown by Theorem 2 that for an EC-complete family, there are no exact estimators than can get Z perfectly right. In this section, we show that no randomized exact estimator for this unbiased. Further, there isn't even an estimator whose bias is within some factor regardless of the variance's ' magnitude.
Lemma 1. Let O be an EC-complete parametric family. There no multiplicative factor Q which every 0 O can have its partition function approximated with Ze (0) within a factor of with probability greater than 2/3, That is, we cannot have
(((1)) Zpu s (0) eZpo) 2/3.
Proof sketch. Because 2, computes estimate in finite time, it can only use finitely many distinct random tape segments. We therefore derandomize 2. by enumerating finitely many 'random' tapes, and can always return correct answer, given the 2/3 success probability assumption, and would be able decide HALT, making use of distributions in Gea.
Taken together, Theorem 2 and Lemma state that no exact estimator 2 - whether randomized or deterministic can approximate Z with good confidence. In Theorem 4 below, we will make an even stronger claim: regardless of the dispersion magnitude, it is impossible to bound the mean of random exact estimators of Z to within any (computable) multiplicative factor. This is because the mean of 2, can be computed in finite time, by derandomizing 2, similarly to our proof of Lemma 1:
Theorem 4. Let O be an EC-complete parametric family. There is no multiplicatiie bound E Q=1 such that there exists randomized exact estimator 2. that guarantees i/e S 312. (0)///m S E, for every e + where po is normalizable.
Proof sketch. We derandomize the expectation of 2,..
5

---

Published as a conference paper at ICLR 2022
5 COMMON ASYMPTOTIC ESTIMATORS DO NOT GIVE USEFUL GUARANTEES
Let's now recap the progress we' ve made so far. We've shown that no (deterministic) exact estimator can get Z. exactly right in general (Theorem 2), lest it need to solve HALT. Further, no randomized exact estimator can approximate within any given relative tolerance, with good confidence (Theorem 4),
But what about asymptotic estimators? We do know there are correct asymptotic estimators of Z. For example, consider the following asymptotic estimator (0) backed by weighted Turing machine that takes O O and N as inputs, and returns fe.; & Ex:xe3", |x|ss (x|ss (x)).. We have lim Zo. Zp- so 2 is asymptotically correct. However, Zasym does not have a convergence rate guarantee: for any e N, _| Zp is uncomputable. We also do not know how much can we improve our estimator when we increment i. As Corollary 2 suggests, we likely cannot have such a guarantee.
In this section, we formalize this intuition for two popular asymptotic estimators: rejection and importance sampling methods (with other asymptotic estimators left as future work). Specifically, we show that any parametric family that is able to parametrize from $3.2 cannot have provably useful locally normalized distributions ($2.3) proposal distributions.
5.1 REJECTION SAMPLING ESTIMATOR OF Z CANNOT BE GUARANTEED TO BE POSSIBLE.
Rejection sampling (Owen, 2013) is a common exact sampling method, applicable even when we cannot sample from unnormalized distribution P. We instead sample from easy-to-sample distribution q. then stochastically reject samples, to ensure the probability that a sample x is kept is proportional to p(x).
For rejection sampling work, the candidate q' support must contain the target p's entire support, that all true points can be sampled. We also need some finite constant C so that cq envelops p::
3c R>o such that Vx E B", (p(x)/q(x)) S
We will show that for certain EBMs, one cannot formally guarantee the existence of an eligible q LN. Theorem Using ZFC as our axiom set and assuming they are consistent, then there exists a normalizable EC weighted language p. where there does exist consistent locally normalized proposal distribution q E LN, and Cq E Q2o, such that it can be proven Vx B", p(x)fg(x) < Cq.
Proof sketch. Let ÿ= b. If there were such q and Cg. we could in finite time prove Zp = 1 or Zp = 2. which contradicts Theorem
Theorem implies that there is no way of ensuring rejection sampling works, not only for any EC-complete families, but also for any parametric family that can parametrize b.
5.2 IMPORTANCE SAMPLING ESTIMATOR OF CANNOT GUARANTEED EFFECTIVE.
Similar to the case of rejection sampling, one cannot guarantee an cuportancc-sampling estimator of Z to be 'good' in this case, we mean that there cannot be proof that the importance sampling variance is finite.
We first formalize importance sampling estimators of Z as randomized asymptotic estimators ($2.5). Let
1 N (x))
2g
Σ
N
((x(1))
be an N-sample importance sampling estimator of Zpo under q, so all x (n)) are samples from y e LN.
We generally want to minimize the variance of 2 under q: Var, (2g (Owen & Zhou, 2000). And we certainly do not want Var, (2% co. Unfortunately, for certain EBMs, we cannot guarantee there good locally normalized proposal distribution that has finite variance:
Theorem 6. Let be an EC-complete parametric family. Assuming ZFC axioms and assuming they are consistent, there exists 0 E O where there does not exist a consistent locally normalized "proposal"
distribution q E LN such that it can be proven Varg (2g g < c co, where c Q=00
Proof sketch. Proven in manner similar the proof of Theorem 5.

---

Published as a conference paper at ICLR 2022
6 UNCOMPUTABLE Z CAUSES PARAMETER ESTIMATION PROBLEMS
Theorems 2 and state that it is generally impossible to estimate partition functions in an expressive parametric family, such as certain subsets of an EC-complete family. Here we show how parameter estimation is made difficult as well: parameter identifiability is formally undecidable for an EC-complete family. Model selection not possible, either, despite attempts to eircumvent this (Table 1).
6.1 PARAMETER IDENTIFIABIIITY UNDER EC-COMPLETE FAMILIES UNDECIDABLE
Consistency of many estimators relies upon the condition of parameter identifiability (Lehmann & Casella, 2006) two different parameter vectors should define different string distributions. But we in general cannot ascertain whether this condition holds, even for finite subsets of an EC-complete family:
Theorem 7. Let O be EC-complete family. There is algorithm that takes 01 O 02 + as input, and decides whether pa, and Pu: are the same weighted language.
6.2 MODEL SELECTION IS GENERALLY IMPOSSIBLE FOR EC-COMPLETE SEQUENCE MODEL FAMILIES
Theorem suggests that consistency guarantees of common parameter estimators do hold, when used to estimate vectors from O. Nonetheless, such 'off-label' use of consistent parameter estimators in an expressive parametric family is quite common one usually just selects the best model 0' among finitely many candidates (say {0, N f) that achieves highest held-out likelihood: 0* arg max TxED Po,, (x), where D is a finite set of strings.
However, Theorem 8 implies that exact log- nigelikelihood-aae based model selection is generally impossible for EC-complete sequence model families:
Theorem 8. For any P E EC and for any EC-complete family O, there is no algorithm BETTER that takes two parameter vectors 01 E O O2 E O and returns YES if KK(pllplpp, z KL KL(pllpa,), and NO otherwise, where p. po, Po, are string distributions defined by p. po, Po, respectively.
PALLIATIVE ALTERNATIVES
What a practitioner to do, given that this class of models is unlearnable in general? We emphasize that a model family does nor have to be EC-complete to suffer from model selection problems ($6.2) (3662)-foh for example, model selection impossible for fixed-size Transformer networks with large enough d''s either, by an extension to Theorem 8 (see Theorem 11 in Appendix G). 9 10 In other words, to ensure the problem of uncomputability does not haunt us, the best we can do is to cripple P so severely that uncomputability is impossible.
We identify three palliative choices that restrict the family EBMs. Each cripples the model f in its own way, affording computability at the cost of expressiveness. The choice of triage infuses the model with an inductive bias; we must tailor our models based on our prior beliefs about the problem domain.
Restricting support () to be finite. If ọ assigns non-zero weights to only finitely many strings, then Zp is finite sum of rational numbers, and is also rational. Here, sampling-bar based inference and estimation methods return to their usefulness. One way to ensure support(p) () is finite is by upper-boundie the maximum string length (e.g., Bakhtin et al. (2021)).
The finite-support restriction imposes an obvious limitation that it cannot handle long strings. Moreover, while Zp is computable when support( P) is finite, this quantity can still be practically inapproximable, assuming that f is expressive (e.g.. 5 is an EC weighted language that has finite support), except for very short strings. Let n be the longest string under á to have non-zero weight. Assuming NP I P/poly, no randomized estimator of Zn that is a good approximation can have guaranteed O (poly(n)) time complexity (Chandrasekaran et al., 2008). However, f has limited expressiveness (e.g., when is Ising model where a string weight is the sum of pairwise weights), then FPRAS algorithms for approximating Zp
II addition to model selection issues, it may also be difficult to acquire unbiased gradients of log Z: v (log Z) A 1/zVZ, which are needed for MLE-based training.
10] "Limiting ourselves to small d's to avoid uncomputability issues may not be practical; we leave finding the largest d that provably does not involve uncomputability problems- is even possible- as future work.
7

---

Published as a conference paper at ICLR 2022
may exist when describe low-degree (s 2) graph (Jerrum & Sinclair, 1993; Luby & Vigoda, 1999). However, for high-degree graphs (z 3) it can be shown no FPRAS algorithm for approximating 2p exists, assuming RP # NP (Galanis et al., 2016).
Autoregressive parametrization of p. An alternative choice is to confine ourselves to autoregressive models, Le., locally normalized string distributions ($2.3). Under an autoregressive model p. Zp 1 by definition. We also note that any (unnormalized) distribution P obtained by removing probability mass from P will have computable partition function, as long as p E EC:
Theorem 9. Let p be any LN weighted language. Any p e EC where Vx V", (xx((x) S pxx) has computable Zp.
Proof sketch. We construct an algorithm that approximates Zp to any arbitrary error level finite time, exploiting the consistency property of p (Proposition 1).
Theorem 9 implies that conditionalization operations on p, which remove strings from the support of to get weighted language P. result in a computable Zp (as long as we can decide which strings are removed); and such ý is therefore not subjected to the limitations of Theorem 4.
Unlike the 'finite support' fix, an autoregressively parametrized (or subsequently conditionalized) f can have an infinite support. A conditionalized can have an intractable (but computable) partition function, and they are still subject to the expressive limitations imposed on LN languages: namely there is an EC language whose string weight rankings cannot be honored by any such conditionalized P (Lin et al., 2021).
I as low-treewidth factor graph grammars. Finally, we may limit ourselves to weighted languages defined by low-treewidth factor graph grammars (Chiang & Riley, 2020). Factor graph grammars generalize factor graphs, which cover many classes of graphical sequence models, such as n-gram, HMM, and whole-sentence language models (Jelinek, 1980; Kuhn al., 1994; Rosenfeld al., 2001). linear CRF models (Lafferty et al., 2001), and weighted FSAs in general (Dreyer & Eisner, 2009): factor graph grammar describes (possibly infinite) set of factor graphs, generated from a hyperedge replacement graph grammar.
Assuming that an FGG G contains at most one n-observed-node factor graph for all n E N, then defines a weighted language (x) = ev v, where factor v is positive function of nodes. The treewidth of an FGG W(G) is the maximum number of nodes any can be a function of, and V [x| is the set of all factors of string length |x|
If pp E R exists, it can be computed exactly by algorithm, in time exponential in W(G) following Chiang & Riley (2020). Exact computation of Zpc may be manageable as long as W(G) is small, which would allow us exactly compute held-out data likelihood, and also train with a (marginalized) MLE objective function. However, limiting W(G) directly limits the expressiveness of p.
8 RELATED WORK
Turing completeness of formal languages and associated uncomputability issues emerge repeatedly in computer science. For example, Turing completeness may emerge as an unwanted side effect in programming languages, since it implies undecidability. One of the best known examples is the Turing completeness of the C++ grammar (Veldhuizen, 2003; Haberman, 2013), which makes both parsing and compiling C++ programs undecidable. Similar problems exist for Java (Grigore, 2016) and Haskell with (unrestricted) instance declarations (Wansbrough, 1998). Another example is the (possibly inadvertently introduced) Turing completeness of the page fault handling mechanism modern computer systems, which raises security concerns in the context of trusted computing (Bangert al., 2013).
Our work is not the first to discuss the consequences of computability in machine learning: assuming we can acquire training data from an oracle, under a supervised learning setting, recognition of an undecidable language is PAC-learnable (Lathrop, 1996). Agarwal et al. (2020) extended the definition of PAC learnability (Valiant, 1984) to computable learners. By contrast, we are focused on the computability of EBMs for sequences, such language model component of larger system for automatic speech recognition. Designing an appropriate, efficient loss functional is a challenge that several prior works have compared. With the plethora of learning strategies for EBMs, it is untenable to point out the
8

---

Published as a conference paper at ICLR 2022
Eneegy-basedd (Le.. glohally normalized)
Infinite language support
Scoring function has unbounded treewidth
Technique
Consistency
Noise-contrastive estimation (Ma & Collins (2018); used in Lin et al. (2021); Bakhtin et al. (2021))
x
MLE with variable elimination in factor graph grammars (Chiang & Riley (2020); used in Eisner [2001); Finkel et al. (2008), buter auterabia)
/
X
V
MLE with autoregressive parametrization (Mikolov et al., 2010)
X
/
Contrastive divergence (Hinton. 2002)
X
Contrastive estimation (Smith Eisner, 2005)
Table I: Deficiencies of some common alternatives to overly expressive EBMs.
deficiency in each. Table gives a handful of examples; none share the four propertics we desire: 1. Global normalization (without which the model would be in LN) 2. Support over infinite languages (of finite strings) 3. Unbounded treewidth in the function assigning weights to strings 4. Estimator consistency (i.e., asymptotic guarantee to recover the true parameters).
Lin et al. (2021) noted autoregressive factors of EC languages can be uncomputable (see also Theorem 10). They also noted that a weighted language can have an uncomputable partition function (presumably resulting from the sum over infinitely many string weights). But they did not dwell on the question whether such weighted language could lie within the EC class, much less providing a constructive proof (see also Appendix E). Instead, they emphasized that under the assumption that oracular access to trained parameter strings is possible, arbitrarily good approximations of the (possibly uncomputable) partition function can be memorized in the (autoregressive) model parameters. There is an interesting constrast between the stances of Lin et al. (2021) and our work: Lin al. (2021) saw the uncomputability of Z as a trivial issue from the model capacity viewpoint, since good approximations take few bits in the parameters to store. On the other hand, we see that the uncomputability problem can be a parameter estimation disaster there will be no guarantee of good approximations can be found in finite time at all.
9 CONCLUSION AND FUTURE WORK
Energy-hased models are posed as an efficient tool for decision problems, circumventing probabilities and expensive normalization (LeCCun et al., 2006). Extending this vision to generic sequence models, though, can involve complexity/compuabiii problems that are difficult, or even impossible. We've shown that as energy-based sequence models become more powerful, the partition function becomes uncomputable- even when we are restricted to polytime-computable weighted languages. Exact estimators, even if randomized, cannot have accuracy guarantees. Popular asymptotic estimators on the other hand are not useful either. Furthermore, model selection is generally impossible, even if we limit ourselves to fixed-size sequence model families.
This paper continues discussion started by Lin et al. (2021), who posture energy-hased models as more powerful alternative to autoregressive sequence models. Autoregressive sequence models, after all, have wide adoption and empirical successes (Radford al., 2019; Brown et al., 2020). By contrast, more general neural energy-based sequence models have not caught on. Why not? We give unlearnability due to possible explanation: unless we give up the ability to learn parameters from data, we likely cannot use the full expressiveness afforded by powerful neural networks. Just like the model capacity problems brought up by Lin et al. (2021), this result is independent of the amount of training data.
uncomputability-
We emphasize that our results do not invalidate the findings of Lin et al. (2021): regardless of the actual neural parametrization, autoregressive models can never capture certain distributions that energy- based models can. Instead, one of our main messages is that we may not be able to find those EBM parameters in finite time, if we do not know what the parameters are. Of course, if we know the task perfectly well and can in fact manually assign the model parameters, we will not need to learn from data at all. The middle ground- - when we have some prior knowledge about the task, but cannot really design the parameter vectors- - is an interesting direction for future work: the three palliative alternatives outlined in $7 do not take task-specific information into account at all. Can we do better than that, without suffering uncomputability problems?

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We thank the four reviewers for their comments, especially Reviewer NAem for shortening the proof of Theorem 4. Additionally, we thank Alexandra DeLucia, Matthew Francis-Landau, Chin-Fu Liu, Suzanna Sia, Neha Verma, and Chenghao Yang (sorted alphabetically) for discussions that improved the presentation; and Jason Eisner, discussions with whom motivated the original exploration of this work.
REFERENCES
Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David Tosca Lechner, and Ruth Urner. On learnability wih computable learners. In Aryeh Kontorovich and Gergely Neu (eds.). Proceedings of the I International Conference on Afgorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pp. 48-60. PMLR, 08 Feh-11 Feb 2020. URL htt.httsss/pproeediiie mlr. press/v117/ 111/aagaraaal00bb hobmm.al00b..ml.
S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2006. ISBN 978-0-521-4246-44, URL pettps://theorgs cs wws.prinnntto...ommmmmmmmmmmmo.e edteendpddo/o///// cttt///oppeiityy/ book.pdf. pdf.
Anton Bakhtin, Yuntian Deng, Sam Gross, Myle Ott, Marc'Aurelio Ranzato, and Arthur Szlam. Residual anergy-based models for text generation. JMLR, 22(40):1-41, 2021. URL htttp://jmlz org/ papers/v22/20- 326. html.
Julian Bangert, S. Bratus, Rebecca Shapiro, and Sean W. Smith. The page-fault weird machine: Lessons in instruction-less computation. WOOT, 2013.
Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Janvin. A neural probabilistic language model. J. Mach. Learn. Res., 3(mull): 1377-115, mar 2003. ISSN 1532-4435. URL https://www jmlr org/ waaggpapers//ae paapers//3//begio/000
html.
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of Transformers and its implications sequence modeling. Proceedings of the 24th Conference on Computational Natural Language Learning, pp. 455-475, Online, November 2020. Association for Computational Linguistics. doi: 10.18653/v 2005533/1/222.comlll/ 1.37. URL https: httpss//aacaathhllog/oo Bacellogyorrggg/// org/2020. wtgg/2220.coo1111.33 con11-1.37.
T.L.. Booth and R.A. Thompson. Applying probability measures to abstract languages. IEEE Transactions on Computers, 4-22(5):442-455 4500 1973. doi: 10. 10.1/00/T- 19732.22699
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford. Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. H. Larochelle, M. Ranzato, Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020, URL https: /tttts::/prroce /ttp://///oocceee.../ooo wwwpiinnnnneiii.cnceeeeeeeeeeeee copps/seeeppppppe/c///e/p file/ 1457c0d6bfcb49674 (twee/441888aaac22446844
Paper. .df..
Venkat Chandrasekaran, Nathan Srebro, and Prahladh Harsha. Complexity of inference in graphical models. In UAI, 2008. URL /ttpp:://dl. acm. brg//oi// 100. 10111..55553333 3555/3623476 3023485.
Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, and Kevin Knight. Recurrent neural networks as weighted language recognizers. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers), pp. 2261-2271, 1, New Orleans, Louisiana, June 2018. Association for Computational 1/N18 1205. URL https: http///caaatthhhh laclholotoogy..... Erg/N18- 1205.
Linguistics. doi:
David Chiang and Darcey Riley. Factor graph grammars. H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 6648 0658. Curran Associates, Inc., 2020. URL https:/ https://////ooceee 2020 1a00ffilee h000:/fii//000222222223333338883 Paaeee99...----..-.....
Paper .dff
10

---

Published as a conference paper at ICLR 2022
Stephen A. Cook. The complexity of theorem- theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC '71, pp. 151-158, New York, NY, USA, 1971. Association for Computing Machinery. ISBN 9781450374644. doi: 10.11457/00157.885047, URL
https://doi. http://doo..ogg///1/ org/10. 10. 80544/ 805047.
Markus Dreyer and Jason Eisner. Graphical models over multiple strings. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pp. 101-110. Singapore, August 2009. Association for Computational Linguistics. URL https////cc/aattooooooo///000010
Jason Eisner. Expectation semirings: Flexible EM for state transducers. In Gertjan van Noord (ed.), Proceedings of the ESSLLI Workshop on Finite-State Methods Natural Language Processing (FSMNLP), Helsinki, August 2001. URL http://cst jhu. edu/ jaauu//jssoo///e pawpoon/ppprr//eeeee #e fners 2001 fsmnlp. Extended abstract (5 pages).
Jenny Rose Finkel, Alex Kleeman, and Christopher D. Manning. Efficient, feature-based, conditional random field parsing. In Proceedings of ACL-08: HLT, pp. 959-967, Columbus, Ohio, June 2008.
Association for Computational Linguistics. URL htttps://aclanttooooyy..oo / 1109.
Andreas Galanis, Daniel Stefankovic, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models. Combinatorics, Probability and Computing, 25:500 559, 2016.
Zoubin Ghahramani. Probabilistic machine learning and artificial intelligence. Nature, 521(7553))452-45) 2015. doi: 10. 10.1038//aturre45444 URL http://ll..rrr./0...////auuttrts 1038/nnatuee1544....
Radu Grigore. Java generics are Turing complete. CoRR, abs/1605.05274 2016. URL http:
wwtpxiivorgggbs///o 05274.
Josh Haberman. Parsing is literally undecidable, Aug 2013. URL htt.htt://blogg.eeeeeeeeeeeee 1tt///////////aaiiiig/ c- --sig----s--iieeee l-ii--iiterlly--nddeeeee undecidable html.
Geoffrey E. Hinton. Training products of experts by minimizing contrastive divergence. Neural
Compur., 14(8):1771-1800) August 2002. ISSN 0899-7667. doi: 10.1162288997602266128888888 URL
https://doi org/10. 10. 11111///6997666006000000000
Y. Huang, A. Sethy. K. Audhkhasi, and B. Ramabhadran. Whole sentence neural language models. In ICASSP, April 2018. doi: 10.1109ICAASSP201133661744 URL https://ieeexplore. ieee orgg document/8450 (44umennt/4617744
Thomas Jech. On Gödel's second incompleteness theorem. Proceedings of the American Mathematical Society, 121(1):311-35) 1994. doi: 10.2307/2160398.
Frederick Jelinek. Interpolated estimation of Markov source parameters from sparse data. In Proc. Workshop on Pattern Recognition in Practice, 1980, 1980.
Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on computing, 22(5):0877-1166, 1993.
S. Katz. Estimation of probabilities from sparse data for the language model component of speech recognizer. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35(3):400-40) 1987. doi:
10.1109/TASSP.1990 1987. 165125.
Kuhn, H. Niemann, and E.G. Schukat-Talamazzin Ergodic hidden Markov models and polygrams for language modeling. In Proceedings of ICASSP '94. IEEE International Conference on Acoustics, Speech and Signal Processing. volume i, pp. 1/357-1/360 vol.1, 1994. doi: 1091109// (ww.SSSS..994389929.
John D. Lafferty, Andrew McCallum, and Fernando Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML, 2001.
Richard H. Lathrop. On the learnability of the uncomputable. In ICML, 1996.
Yann LeCun, Sumit Chopra, Raia Hadsell, based learning. In G. Bakir, Hofman, B. Schölkopf, A. Smola, and B. Taskar (eds.), Predicting Structured Data. MIT Press, 2006. URL htt http:///a//a lecun. wttp:/ccoeeeeieeteeeeee wwwp/ppblis/pdf/eeeeeeeeeee 86. .dd..
Ranzato, and Fu-Jie Huang. A tutorial energy-
11

---

Published as a conference paper at ICLR 2022
Erich L Lehmann and George Casella. Theory of point estimation. Springer. 2006. URL https: //link. stringer. www.book//ooooo.oo 10. 1007722b98884.
Chu-Cheng Lin, Aaron Jaech, Xin Li, Matthew R. Gormley, and Jason Eisner. Limitations of autoregressive models and their alternatives. Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 5147-5173, Online, URL
June 2021. Association for Computational Linguistics. doi:
org/2021 maaacl-main.4000
Michael Luby and Eric Vigoda. Fast convergence of the Glauber dynamics for sampling independent sets. Random Structures & Algorithms, 15(3-4):229-23) 1999.
Zhuang Ma and Michael Collins. Noise contrastive estimation and negative sampling for conditional models: Consistency and statistical efficiency. In EMNLP, 2018. URL httpp://wvet www./w....wwbbbbb............ org/ anthology/D18- 1485. pdf.
Tomas Mikolov, M. Karafiát, L. Burget, Cernocký, and S. Khudanpur. Recurrent neural network based language model. In INTERSPEECH, 2010.
Art Owen. Monte Carlo theory, methods and examples. Unpublished, 2013. URL https: // //artowee.... su. domains/mc/.
Art B. Owen and Yi Zhou, Safe and effective importance sampling. Journal of the American Statistical Association, 95: 95:135-143, 2000.
Jorge Pérez, Pablo Barceló. and Javier Marinkovic. Attention is Turing-complcte. Journal of Machine Learning Research, 22(75):1 2021. URL battt:://jaat cemmmloorrgg cac.llrrorggppppppeee ppppps/v22/2220000//////////// /// 302. .tml.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. Unpublished, 2019. URL https: /ttp////c/kkwww.wwolu...fafaeaae /0tp htt/bbetter-lanuuee haapettteeeannngnaannneeeee///ee sondeees/laggagemmmeellllll
Ronald Rosenfeld, Stanley Chen, and Xiaojin Zhu. Whole-sentence exponential language models: vehicle for linguistiee-saatistcall integration. Computer Speech & Language, 15(1):55-73, January 2001.
URL https://doi: org/ 10. 1006 ca/06//ssl... 2000. 0159.
Ben Sandbank, Refining generative language models using discriminative learning. In EMNLP, 2008. URL https://www aclweb. he//aahholooyyD@g0 1006. pdf..
H.T. Siegelmann and E.D. Sontag. On the computational power of neural nets. Journal of Computer and System Sciences, 50(1): 1995, ISSN 0022-0000. doi: http://ddo..or///.0006//s/s.s. 199500000.0.....9111...... URL httpp://wwete sci www.einnneeeett....eeeeeeeeeeeee ottpetcccc....cc.......eeeeeeeea
Michael Sipser. Introduction to the Theory of Computation. Course Technology, Boston, MA, third edition, 2013. ISBN 113318779X.
Noah A. Smith and Jason Eisner. Contrastive estimation: Training log-linear models on unlabeled data. In Proceedingy of the 43rd Annual Meeting of the Association for Computational Linguistics (ACI.'03 pp. 354-362, Ann Arbor, Michigan, June 2005, Association for Computational Linguistics. doi: 10.3115/1219440.1 1219884. URL https: httpss///cccaathhoogcooo org arrg/P5--10 1844.
Daniel W. Stroock. An Introduction to Markov Processes, volume 230 of Graduate Texts in Mathematics. Springer, Heidelberg. 2 edition, 2014. ISBN 978-3-642-40522-8. doi: 10. 1117779778-3-4224055333
A. M. Turing. On Computable Numbers, with an Application to the Entscheidungsprohlem. Proceedings of the London Mathematical Society, 52-442():230-266 01 1937. ISSN 0024-6115. doi: 10.1112/plms/
s2-42. .200. URL https::///doo org / 111.:/01111111mmmmmmmmm 1.
L. G. Valiant. A theory of the learnable. Commun. ACM, 27:111) November 1984. ISSN 0001-0782. doi: 10.1145/1968.1922 URL https://doi. 91680/..00111111116666... 1972.
Todd L. Veldhuizen. C++ templates are Turing complete. Technical report, Indiana University Computer Science, 2003. URL htthh:ts////eee /ttttp:://rrraa..... files.
.pdf.
12

---

Published as a conference paper at ICLR 2022
Keith Wansbrough. Instance declarations universal, 1998. URL https::/www.Lochatt org/ peaitppubccatioss///
/undon./////..o///oo html.
Adam B. Yedidia and S. Aaronson. A relatively small Turing machine whose behavior is independent of set theory. ArXiv, abs// 00444,0 2016.
13

---

Published as a conference paper at ICLR 2022
exact
asymptotic
deterministic
x (Theorem 2)
($5; but no useful guarantee in finite time)
randomized
x (Theorem 4)
2; but X for rejection sampling (Theorem 5) and for importance sampling (Theorem 6) when paired with autoregressive proposal distributions
Table A.I: Summary of negative results: neither deterministic or randomized algorithms can estimate EBM partition functions accurately. On the other hand, popular sampling schemes such as rejection and importance sampling require their autoregressive proposal distributions to be uncomputable.
A
SUMMARY OF NEGATIVE RESULTS
In Table A.I, give overview of the negative results in this paper: deficiencies of several estimators of the partition function in an energy-based sequence model.
B WEIGHTED TURING MACHINES
We extend the definition of Turing machines into weighted Turing machines as follows. A weighted Turing machine M is described as 7-tuple (0 qinit: F, update__nue apdate_denom) where the first 5 components (Q, Σ. 6, qinit, F) have definitions following that of standard Turing machines. The last two additions are weight-update functions: both update num and update_deree denom have signature Q A, where Я - (SAME, CARRY).
At the end of time step i, assuming the current state q, we define
NUM
if update Bateeenum@@_ () SAME
NUM;
2 NUM;-1
if update_nume q) CARRY
and similarly.
DENOM 2 DENOM; if update_denom(() = CARRY.
if (opdate_denom((( = SAME
DENOM
To keep our proof of model family capacity brief, we (arbitrarily) define that Vq E F {qinis- update_num(q)+ appatee_enoom( = SAME. Finally, upon arriving at a halting state F in time steps, we say NUM//BENOM, is the weight an input x 3" under M, if NUM-foRNOM, rational number. II
C DEFINITION OF SEQUENCE MODEL FAMILIES AND EC-COMPLETE PARAMETRIC FAMILIES
Following Pérez al. (2021), say sequence model family is set of seq-to-seq models N= (Ng E O g Q*), where every N₂ E N recognizes language Lg if and only the seq-to-seq model Ne. paired with embedding function
Qd, initial states ed + B, accepts every string x E Lg. And we define No to accept x = [x] [x.]] E B= if and only if there exists r such that No upon input embeddings (f )}, produces output embeddings y, at the 7-th time step, where g =
Qd and polytime
termination decision function
EC-complete if given any ğ EC (as a description of weighted Turing machine). we can construct parameter vector 0 O such that there exist polytime functions Wp Qdd - N u (0) and Wy Od - N U {0}. where whenever on input = |x ... xy J. if g = for some output embeddings y, (that is, No accepts x in time steps), wp (,, (x,) p(x).
sequence family
When NUMM/DENOM, not rational number (because DENOM, 0), we say the weight of input string x undefined. However, we do not encounter that in this work: all strings in EC language have rational weights. In any case, we only require that our family contain weighted Turing machines that return rational numbers, not that they he the only members.
14

---

Published as a conference paper at ICLR 2022
D PROOFS OF THEOREMS FROM MAIN TEXT
Theorem 1. The class one-encoder-llyyr, foareeeery Transerrr-eayyeTTTaaaaaameeee networks with positional encodings (n, Vn, 1/n,, 2") is EC-complete.
Proof. To model all weighted Turing machines defined in $2.2, we extend the encoder-layer three-decoder-laye Transformer network construction introduced by Pérez et al. (2021) with one additional layer. We also modify the original positional emhedding function pos N - Q4 to include a new component. In this proof, we let
one-
pos(i) = [O....,., 1/,, 1/,21
instead of pos(i) [0..... 0, 1,4, 1/2] as in Pérez et al. (2021).
For the sake of clarity, our construction is 'stack-on' construction: the encoder layer and the first decoder layers are largely identical to the design of Pérez et al. (2021), with the only difference being necessary changes to accommodate our one additional positional embeddings component. strengthen our results by showing that one-encoder-laye three-decoder-layee Transformer networks with the original positional embeddings - the parametrization family Pérez et al. (2021) showed to be complete improvement as future work.
may be possible to
EC- EC-comllete as well, with more involved construction. We leave such an
We claim fourth layer of the decoder has output y, = yy + wr, where
yf is zero-padded version of the original Transformer output embeddings from Pérez et al. (2021). yf is of the form
[[ ( .............0
where [q"] denotes one-hot vector of size [2] where the q" component is (again following the notation of Pérez et al. (2021)). And w, is of the form
10g. Og. NUM, DENOM,, 0.....0]
(3)
where num, NU (0) and DENOM, NU (0) are defined in $2.2.
Now we describe how w, can be computed from [yg y' using the attention mechanism, with the help of our new positional embeddings. Specifically, we want to show that we can construct feedforward networks Q4, K4, and such that
y; = K Va(Y())
where y" = y pos(f), Y' = Vy....y. and Y, = Y' + [pos(I)... (os().. We let Q4(y")) 10, 0, 0] be a constant vector, and (Y,",) Y.¹. Finally, we let V4(Y)) [0,. 0g.00.00 1.
1,
g²) CARRY)2 [[update__deomm((( q²) CARRY) O.....
Q4 is a constant function (such that it always attends to the unity component of Y.), so it can be implemented
single-layer feedforward network. K4 the identity function, which can also be implemented as single-layer feedforward network. V4 on the hand can be implemented as a fixed-size feedforward network, with the piecewise-ling sigmoidal function or: the case DENOM, the network CARRY),
would first project q² to [[(update peroddtt__enom_/ q¹) CAARR),I(updart I(updatee_del fitree__eeo((p) q') SAME)] (using
the one-hot [[q]] segment from yi). multiply it by = [2 0] (with the help of nonlinearity from σr), and put @ b at the position of DENOM; in equation (3). The component at NUM; in equation (3) can be computed likewise.
12Since we increase the output embeddings' dimension by 1. we also need to pad all matrices in the original construction by additional zero columns/rows, such that our new positional embeddings' new component has effect on any computation in the encoder layer, and the first decoder layers.
15

---

Published as a conference paper at ICLR 2022
Given any position N, have
y, Att( ".Y"))
10g.
0,.
0,
(uuddate_num(4) = CARRY)2',
(update_denoml( ( CARRY)2',
0,
0].
Let extract_avg_numUy> be affine transformation that extracts the (12) |Σ] 2) component from yr. and extract_avg ) be an affine transformation that extracts the (12) + |Σ] 3) component from y,, we have
extract_avg_num((y)
Σx cyopdate_num((4 CARRY)
extract_aag_denoniy)
Σ [uuddate_denom q') CARRY)
NUM,
DENOM,
which is the weight of input [x] ..y
defined in $2.2.
Theorem 2. Let + be parametric EC-complete sequence model family. And let O2 C. A be bijective with Gx. There is no k E 20 for which there exists an exact estimator 2x that takes as input @ e Og as input, and computes 2 (0) = Zo in finite time.
Proof. We can reduce HALT to computing our partition function. For the sake of contradiction, let us assume that for some & Q the exact estimator 2n exists. Our reduction from HALT of input-free Turing machines is as follows: Given any deterministic input-free Turing machine M, we build weighted deterministic Turing machine: M' (Appendix B). M' takes as input x B", and outputs weight 1/21x/+1 when x encodes an accepting trace of M'. Otherwise, M' outputs weight 1/3lx|+1
M' always returns a weight for in polytime. By the assumptions of EC-coppeete families ($2.4), we can build a parameter vector 0 E ① such that PM = Pa. Since from the definitions of Ge we know PM = P M, we have E Øz.
We have thus completed our reduction: if 24 existed, we could decide whether any given input-less deterministic Turing machine M halts, by first constructing the weighted Turing machine M', then the corresponding 6. By our assumption, 2e (e)) = k + and only 3x B" that is an accepting path of M', which is true if and only if M halts for some finite steps. Since whether M halts is undecidable, have arrived at contradiction (Turing, 1937; Sipser, 2013). Therefore for all E Q the algorithm 2, does not exist.
Theorem 3. Assuming ZFC axioms and that assuming they is consistent, there exists an EC weighted language b Gi such that (a) Z3 = (1,2} exists, but (b) there no proof of Z3 =
Proof. Our proof hinges on Gödel's second incompleteness theorem: consistent axiomatic system which includes Peano arithmetic (e.g., ZFC) can prove its own consistency. We construct a Turing machine M, that enumerates all provable propositions under ZF, and halts if and only if M, proves the proposition 1 = O. One such Md with 7, 918 states has been built by Yedidia & Aaronson (2016).15 13
MG is an input-free deterministic Turing machine. We construct a weighted Turing machine M' from M,.
"SShsequent efforts have led to construction of Ma with 748 states: http:://uutigmechiissiimmaarr com/ wtt.///aadd//e/ee wwwprredddwiiiggguureggeem
16

---

Published as a conference paper at ICLR 2022
in the manner of the proof of Theorem 2. We let M' return weight 1 + 1/2/=+*1, in the case My halts with trace x. M' returns a weight in polytime, and therefore defines a weighted language E Gi C EC. We know from the definitions of Gi that Zg is either 1 or 2.
Assume to the contrary that there cxists a proof that ZB = L. Then we know M, did not halt. And therefore the proof would also imply that ZFC is consistent, which violates Gödel's second incompleteness theorem. On the other hand, if there were a proof that 2B = 2, it would imply M, halted and ZFC is not consistent. We therefore arrive at a contradiction.
Lemma 1.
Let O be an EC-complete parametric family. There is no multiplicative factor e E 1 for which every O can have its partition function approximated with Ze (0) within a factor of E - with probability greater thun 2/3. That is, we cannot have
P p((1)) Pp S (0) S <ZZp) 2/3.
Proof. In this proof, we make use of the distribution family Ge² ($3.1). We assume to the contrary that a multiplicative bound satisfying equation (2) exists. Recall that our assumptions state that P (Ve s Z. (2/ppp I <e) 2/3. 14 Let M be an input-free Turing machine. An Pa = =MM,e? Ge² where
0 E the Turing machine M halts, Zp.... 2 I+E2; therefore, P ((1 ((1+ s (0) s (1+))c)
2/3. Similarly, if M does not halt, we have Zps..e 1; therefore, P P(Ve s 2. (0) s E > 2/3. By combining the two conditions, we know that P (I(M halts)) = (I(2. (0) 2 E ^ 2, (0) > o)
(I(2. 2 V())-
Therefore, given (1/e) Zpo S 2. S EZ we can decide if M halts by checking if (0) 2 E+ I/e. Since the condition (1/e) 2iv s 2, (0) I <Zpo only holds 2/3 of all time, we then derandomize the randomized 2e to get a deterministic estimator: recall that randomized exact estimator finishes computation in finite time, regardless of the content of the random tape r. There, there are only finitely many finitely long possible 'random' sequences that 2. will read, which can enumerate. More concretely:
P(2. 2 E 1/c) = =B [1(2.c (0, 2 1c)
Σ
1/2"0. I (0, 2 1/e)))
(4)
B.c
where me.e E N is the maximum prefix length of the random tape that 2e (0, 7) will use any B Again ma,e is guaranteed to exist because of our assumption 2. (0. r) ends in finite time. Since equation (4) is a finite sum of computable functions, it is also computable.
From the computability of equation (4), it follows that we can derive deterministic algorithm from 2, that decides whether an arbitrary input-free Turing machine halts, which is not possible. Therefore, there is no E Q> such that the randomized exact estimator 2, satisfies the multiplicative bound P(1/- < 2. (G)/ I <) > 2/3 for all 0 O.
Theorem 4. Let O be an EC-complete parametric family. There is no multiplicative bound E Q+1 such that there exists a randomized exact estimator 2. that guarantees 1/e S 312. (0)1/2o S e, for every 0 E O where Po is normalizable.
Proof. We define T to be distributed according Pr. Therefore the mean B B|2, (0) can be expanded as Er-p, (2. (0) = EreB" (T) (0, r). Following the same derandomization technique in the proof of Lemma 1, we can find some m E N such that Ere3" (r(T) (0, r) Σrea" 1/2m (0, T) in finite time. And subsequently, we can compute B 2 (0)] exactly in finite time. Let the exact estimator be Z.c. We then have Z (0) 2 (0)
14 As is common, e.g., in defining the complexity class BPP (see Arora & Barak 2006), the fraction 2/3 is arbitrary. Any proportion bounded away from 1/2 will work.
17

---

Published as a conference paper at ICLR 2022
Assuming to the contrary that could guarantee 1/e (0) Since Ze is deterministic estimator, we write P(V/ s (0) e) = I, which contradicts Lemma Therefore such estimator Ze (0) does not exist.
Theorem Using ZFC as our axiom set and assuming they are consistent, then there exists a normalizable EC weighted language D, where there does not exist consistent locally normalized proposal distribution q E LN, and Cq Q2o, such that can be proven Vx B", pix)/g(x) < Cq.
Proof. By contradiction; let p =b. where b is first introduced in $3.2. Assume that there exists LN where it proven that Vx E B", fix)//(xx) < c co, where E Q>o-
We can either prove ZFC is consistent, or is inconsistent, as follows:
1. By our assumptions, e LN scores every string x as (o(x)f(0) Q Also, because q is consistent and locally normalized, there exists E N such that we can prove Vx X fx x
B", |x|] > n). (xx) < 1/c (Proposition 1). We will just prove the existence enumerating the strings in B" in increasing length. Let the complement set X = B X>n.
constructively by
2. The proof then examines the finitely many strings in X
then we know x' encodes accepting trace of M' ($3.2). Therefore, M, halts, which implies there is a proof of the inconsistency of ZFC. (b) If none of these strings E X has b(x) 1, then we know there is also string x" X>n- such that b(x") > 1. This is because of our assumption c 2 (xx) which in turn means that b(x) is less than I on these long strings X>n. Therefore, Mp does not halt, which implies there is proof of the consistency of ZFC.
(a) If any of these strings x' has b(x')=
Assuming ZFC is consistent, neither proof of ZFC, disproof of ZFC, is possible. We have therefore therefore arrived at contradiction. Therefore, does not exist.
Theorem 6. Let be an EC-complete parametric family. Assuming ZFC axioms and assuming they are consistent, there exists 0 O where there does not exist a consistent locally normalized "proposal"
distribution q E LN such that it can be proven Var, (2 < < # co, where e E Q>0-
Proof. let p= where 5 is first introduced in $3.2. Assume that there exists q E LN where it is proven that Var, (2 k Qun co.
We have
Var, (2g
po(x))
g(x))
Zpo² 2
N
g(x)
x
p (x)
N
x(x)
k.
where (x) 1 Po(x)
After some manipulation, we have
Zpa
xx(x)
Nk + Zpo
Σ
(xx)
Zpo 2
FEB
=v5N
Since Yx B" (x)x) g(x)
0, we have
Vx B'. xx(x)
s;
(5)
(x)
18

---

Published as a conference paper at ICLR 2022
in particular, x' encodes halting trace of Mp. from $3.1 we know
po(x')
pa(x')
Zpo
+ (1) 1e'+1
1/2.
Combining equations (5) and (6), we have for any halting trace x' of Mb.
pa(x')
4x(x') < q(x') S.
After some more arrangement,
(xx')
2 4(Nc+ > 0.
4(Nk + 4s
As the proof of Theorem 5, the existence of such a q allows us either prove or disprove the consistency of ZFC. For the sake of completeness, we include proof sketch below:
By our assumptions, q LN scores every string x as (x)x) ((0) E Q>n. Also, because q is consistent and locally normalized, there exists π N such that we can prove Vr X (x x E B", |x| > nt,, ((x) < I(Ne+T) (Proposition 1). We will just prove the existence of constructively by enumerating the strings in B" in increasing length. Let the complement set
Xen = BB -X
2. The proof then examines the finitely many strings in X
(a) any of these strings x' has pe(x') > 1, then we know x' encodes an accepting trace of Mn ($3.2). Therefore, M, halts, which implies there
proof of the inconsistency of ZFC. (b) If none of these strings E Xen has px(x) > 1, then we know there is also no string x" E X>n. such that pa(x") 1, since (e()') > I = b(x') and we have already shown that for any accepting trace x' of Mr. q(x')= 2 1/4(N++)), Therefore, My does halt, which implies there is proof of the consistency of ZFC.
= M, halts;
Assuming ZFC is consistent, neither a proof of ZFC, or disproof of ZFC, is possible. We have therefore therefore arrived at contradiction. Therefore, such a does not exist.
Theorem 7. Let + be EC-complete family. There is algorithm that takes 01 +, 02 O as input, and decides whether pa, and po: are the same weighted language.
Proof. Assuming to the contrary that such an algorithm DISTINCT exists. We would be able reduce HALT of frput-free Turing machines to DISTINCT: we first construct 0 E O such that Po, (x) = 1/3/x/+ 1 We then construct 0² E @ such that Pa: P..1 E Gi ($3.1). DISTINCT(O,, 02) is YES if and only halts.
Theorem 8. For any f EC and for any EC-complete family O, there is no algorithm BETTER that takes two parameter vectors 0 E θ 02 E O and returns YES if (I((plppee) 2 (l.(pl)pe.), and NO otherwise, where p. pep Pe, are string distributions defined by p. pe 88, respectively.
Proof. By contradiction; assume that for some E EC, BETTER exists. We know there exists weighted Turing machine (also denoted as p) that on any string x, terminates in (ppoy((xx)) and outputs f(x) (Appendix B).
We show how we can reduce from HALT to BETTERp. Given any arbitrary input-less Turing machine M, can define new weighted Turing machine Fyy that input string x, P', first simulates f on it and keeps a record of p(x) somewhere on the tape. Py then verifies whether x is an encoded accepting trace of M. I is indeed an encoded accepted trace of M, F'y outputs p(x) 1. Otherwise I'M outputs p(x).
Let 0, E @ parametrize F'y, and let 0₂ O parametrize p. such that Po, (x) = P'M (x), (x. pxx), Vx B..
19

---

Published as a conference paper at ICLR 2022
We know that KL(pllp) O for any distribution p. BETTER; 02) returns YES if and only if KL(pllpe,) = 2 (plp)) which implies that Pe: and Pø. define the same distribution, which in turn implies that Vr E B", p(x) P/ (x), and that M never halts. Similarly, BETTER, ( 02) returns NO if and only if M halts. We have thus completed our reduction from HALT; and therefore algorithm BETTER does not exist for all 5 EC.
Theorem 9. Let p be any LN weighted language. Any p E EC where Vx E ,",p(x)) & p(x) has computable Zp.
Proof. We prove Theorem 9 by constructing an algorithm 2p QQ50- - Q20 that approximates Zp within any desired positive rational error c: namely 12 Zpl S E.
Let 2n = E(=0 [x: (xx). We first observe that lim Zn 1 by Proposition 1. In other words, lim,, 1 7n or equivalently, given any > 0, there exists N such that for all n' n' N, (1 - Zrr) E.
Therefore, given any > 3n E N that divides B* in sets: Xzn = (x : B n), where Ex (xx) < and Xen = B - Xan- We are guaranteed to find by enumerating all candidates from N.
We can thus implement 2p as the following program: given E Qso. we first find the smallest n e N, and partition B" into two sets Xen, Xzn as we described the previous paragraph. We then return 2p(e) = ExeXen p(x).
We argue that 2p is a computable function. We first repeat that since E N exists, we will find in finite time, simply by enumerating. And since the X B is finite, 2p(e) = Exex.,. p(x) computed in finite time (under our assumption P E EC, Vx E B", p(x) can be computed in time 0 ((poy((xx))). Since the program we described above terminates in finite time, 2p is computable function.
What remains is to show that the approximation error 1/- 2p(E) is no greater than e; iee, that I - (zp-2p(c)) s c.
easy to show that s Zpp - -2p(e). after which we only need to show that Zp - -2p(e) s e. Expressing both terms as sums, we have that Exee p(x) ExeXen p(x) = Σxex,, in p(x), which is sum of nonnegative terms and thus nonnegative.
To show that Zp 2p(e) S E, we express both terms as sums again:
F(xx)
Σ p(x) X
Σ p(x). XeXon
By the definition of p. we have ExeXer p(x) S ExExe p(x). The right-hand side is equal to 1 2n. which by construction is less than e. Therefore, by substituting to get Z.p 2p(() s 1 - 2,, and using the transitive property of inequality, have that Zp 2p(c) e. Combined with the previous paragraph's result, we have shown that 1Zp 2,((el s
E CONNECTION BETWEEN EXPRESSIVE SEQUENCE DISTRIBUTIONS AND LIN ET AL.. (2021)'s ' PROOF THAT EC # ELN
Our construction of expressive sequence distributions is similar to Lin et al. (2021)'s construction of an EC weighted language that is not in ELN. Whereas each weighted machine PM. Gi. corresponds to execution traces deterministic Turing machine M, Lin et al. (2021) defined a single weighted language PELN for all Turing machines. Fore the sake of completeness, we describe the definition of øELN from Lin et al. (2021) below. Let enc a prefix-free free encoding function that maps a deterministic Turing machine M to Boolean string where the function inverse enc" exists. And let øELN be weighted language over Boolean strings, where (F)N(x) = 1/30x-11 if x is of the form x ()) x (2), where (1) encodes some Turing machine M, and x(() (2) encodes accepting execution path of M
empty input. (Such a path may be
20

---

Published as a conference paper at ICLR 2022
represented as sequence of transitions of M that begins with initial state and ends accepting state.) Lin et al. (2021) then showed that prefix probabilities Peln are uncomputable under an ELN, since HALT reduces to computing Z(x ())
Theorem implies that PELN we have just described above has a computable partition function:
Theorem 10. Let Z. be the partition function of PELN. Z. is computable.
Proof. Let pxx) 1/3ixin, p E ELN C LN because p(- x) 1/3 for all valid prefixes Since PeLN E EC by Lin et al. (2021, Theorem 5) and Vr E B", (F)N(( pxx), we have Z. is computable by Theorem 9.
Similarly, the 'sparse version' of Pann introduced in (Lin al., 2021, Theorem 6) can be shown have computable partition function as well.
Since one of our goals is to clearly demonstrate that we can construct a single weighted language EC that has an uncomputable partition function assuming ZFC (e.g., b in $3.2), we define weighted languages in Ge to have at most one 'high' weight, as opposed to á in Lin al. (2021, Theorem 5), where each x ()) that encodes halting machine has a 'high weight' suffix (2).
fact, under our construction we can directly show EC # ELN, using the uncomputability of from Theorem 3:
Corollary (EC # ELN under ZFC; slightly weaker version of Theorem 5 in Lin et al. (2021)). Assuming the axiomatic system of ZFC, EC EL.N.
Proof. We know there exists a weighted language b EC ($3.2) that has an uncomputable partition function. Since b E EC, b(x) E Q20. Vx E B". Therefore for all strings x E B", b(x) = b(x)/26 is an uncomputable number.
Assuming to the contrary that b E ELN. By definition b(x) 1l b(x, xxx), where each b(x, xxx)
Q2 and is computable, Since the set of computable numbers is closed under multiplication, b(x) would also be computable, which contradicts our assumption. Therefore + ELN, which implies EC # ELN.
NEGATIVE RESULTS POSSIBLE ON FINITE PARAMETER SU SUBSPACES
In $3.2, mention that the pathological EBM b can show negative results regarding finite subsets of O. Here, we provide a concrete example.
Corollary 2. Assuming ZFC axioms and assuming they are consistent, there exists 0 such that 7 Q exists, but there is algorithm Zproot thut takes 0 E O input, and outputs set of strings {xn n < N..N N N where
there is proof that ΣN po(x) 2 1/2Zpei there a proof that MN (x(x) 1/27
Proof. Assuming to the contrary that Zproof existed. We construct O e O such that Vx E B", (e(x) = ((x). Either proof resulting from 2ppoot (f): {x,, < N) can be used to prove or disprove the consistency of ZFC.
Corollary states that there exists 'problematic EBM' -amely h- where we cannot guarantee well approximate its partition function, by accumulating finitely many string weights, regardless of the manner of accumulation (i.e., how we choose strings) or the number of strings we enumerate over. We discuss this in further details in $2.5.
G IMPOSSIBILITY OF MODEL SELECTION FIXED-SIZE TRANSFORMER EBM FAMILIES
Theorem 11 is sibling theorem to Theorem 8. Just as we show Zí is uncomputable ($3.2), can prove that model selection is not only impossible for EC-complete parametric families (where the length of a parameter vector unbounded), but also impossible for fixed-size Transformer EBMs with large enough
21

---

Published as a conference paper at ICLR 2022
embedding size. 15
Theorem 11. Assuming ZFC our axiomatic system, for any P EC, there exists do E N such that for all d 2 do, p can be captured by one-encoder-laye four-eecoder-laye Transformer networks O (d) (Theorem with embedding size d, where there no provably correct algorithm BETTER p.d that takes two parameter vectors 01 E Old), 02 E @(d), and returns YES if KL(pllpa,) z KL(pl)Po.); and NO otherwise, where p. p p0; are string distributions defined by p. po. Po; respectively.
Proof. Let Md be the input-free free unweighted Turing machine we built in our proof of Theorem 3, whose behavior is independent of ZFC. Let Mo be any weighted Turing machine that defines the EC weighted language p. And let Mi be weighted Turing machine that weights x as p(x) + if and only if x encodes an accepting trace of Mp: and M1 weights x as p(x) otherwise. Since checking whether x is a valid trace of Mp is in (poly [x))), M1 defines EC weighted language.
Let Р.₁ be the string distribution defined by Mj. By an argument similar to our proof of Theorem 8, no algorithm that is provably correct decide if (L(plIpM) KL((llp)).
We note that for any weighted Turing machine M with fewer than n states, we can build another weighted Turing machine M' which has states, such that M and M' define the same weighted language, simply by having (finitely many) additional unreachable states in M'. Since any weighted Turing machine with states can be implemented
Transformer networks with embedding size E On), it follows that there exists do N such that both Mo and M₁ can be encoded as parameter vectors within a fixed-size size model family with d 2 do.
l-encoder-layer-4e segroder--aye----ddddd--------
We 2 (d) denote Transformer family with emhedding size d.
22


Reviews:
[{"review_id": "zuKcGCA5nfR", "reviewer": "Reviewer_EUof", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "This paper tackles the important question of what we loose in theoretical guarantees if we remove all restrictions on the energy-based model. As such, this paper provides an important answer to conjectures raised in (Lin et al. 2021).\nThe paper is technically sound and well written to the degree that the arguments are also comprehensible for non-experts; I honestly enjoyed reading the paper.\nOne might argue that the findings are somewhat abstract as they only hold for energy-based models without any restrictions on the model expressively. The theoretical properties (e.g., regarding randomized algorithms) are intriguing at first, but less so considering that we implicitly assume that $\\tilde{p}$ has infinite support. Granted, the authors are quite open about the -- lack of -- assumptions and discuss the implications of typical model restrictions in depth in Sec. 7. Nonetheless, I would have preferred a brief discussion about the practical relevance of EC-complete parametric families in Sec. 2.4. (and in the introduction) and to what degree certain model restrictions lead to non-complete families. That is if the authors would state the scope of the current work more blatantly.\n\nI have a couple of further remarks and questions:\n* I cannot follow the logic from Prop. 1 that infinite-length sequences have zero mass; that is, I do not understand why $\\epsilon$ must go to zero for $n \\rightarrow \\infty$.\n* In Sec. 4 it is stated that no estimate exists with a bias within a multiplicative factor. If I understand Lm. 1 correctly, such an estimate does exist, however; although only with probability < 1/3. Can you explain this discrepancy?\n* Most arguments hinge on the undecidability of the HALT problem. I think that it would help the reader if that was stated explicitly in the text.\n* Thm. 5 states that rejection sampling does not work for EC-complete families. I get the argument, but I was left wondering whether it might be possible to quantify the approximation error one introduces when relying on randomized methods nonetheless.", "summary_of_the_paper": "The paper studies the trade-off between expressiveness and computability (of the partition function) for energy-based sequence models. The theoretical results show that the high expressively of unrestricted energy based models comes at the cost of un-computability and in-approximability of the partition function. These negative results further show that rejection and importance sampling are not a panacea either.", "summary_of_the_review": "The paper considers an important problem, is technically sound (at least from what I can tell), and well-written. Although the practical implications are not immediately clear, I am convinced that it is actually relevant to understand the theoretical limitation of considering energy-based models with ever-increasing expressiveness. ", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "cSf0OEn3lhV", "reviewer": "Reviewer_K6DS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The main strength of this submission is its cohesive conceptual message. This work studies the viability of EBMs from an unconventional angle: whereas one's initial reaction to the complexity of computing the partition function for an EBM might be to point out that it is obviously computationally expensive, the findings in this paper show that in fact this task isn't even computable. A related strength is that the paper systematically pursues this idea from a variety of perspectives, e.g. exact/approximate/asymptotic + deterministic/randomized estimation, failure of off-the-shelf techniques like rejection/importance sampling, related tasks like identifiability and model selection.\n\nAs for weaknesses, the actual technical content isn't particularly involved and arguably not that surprising given that families like Transformers are known to be Turing-complete, though perhaps this is an unfair criticism given that the contribution of this work is primarily conceptual. Regarding the writing, I did feel that the important preliminaries were introduced in a rushed fashion; for instance, even though they figure in a majority of the theorems in this submission, their definition of \"EC-complete parametric families\" was extremely difficult to parse, in part because their definition of seq-to-seq models was similarly difficult to understand. That said, the formalism doesn't figure that heavily in the proofs as the arguments are ultimately primarily about Turing machines anyways.", "summary_of_the_paper": "This paper studies \"efficiently computable (EC) energy-based sequence models (EBMs)\" which are simply sets of strings equipped with nonnegative weights that can be computed by a poly-time Turing machine (upon normalization, the weights induce a probability distribution over the strings). In practice, it is common for these weights to be computed by neural networks. In fact, certain neural sequence model families like RNNs and Transformers are expressive enough to be Turing-complete. In this paper, the authors find that the expressivity of such sequence model families, so-called \"EC-complete parametric families\", comes at a significant cost in terms of *computability/decidability* of various primitives for inference. For instance, they show that if one could actually take in any vector of parameters specifying a model in such a family and output the corresponding partition function (sum of the weights of all strings) even approximately in expectation, then would be able to decide the halting problem (Theorem 2, 4). They also exhibit a single efficiently computable EBM for which proving (within ZFC) that the partition function is one of two possible values would either disprove Godel's second incompleteness theorem or disprove consistency of ZFC (Theorem 3); this can be extended to show that *asymptotic* estimates like rejection sampling and importance sampling will also fail (Theorems 5, 6). Along similar lines, they can reduce from the halting problem to other tasks like deciding whether two given parameter vectors give rise to the same EBM (\"parameter identifiability\", Theorem 7), or deciding which of two given parameter vectors gives rise to an EBM which is distributionally closer to some other given EBM (\"model selection\", Theorem 8).\n\nIn terms of techniques, the reductions from the halting problem are all based on a simple weight function that is tiny unless if the string corresponds to a valid accepting trace of an input-free Turing machine M. The point is that the weight for any string x can be computed by M simply by simulating M on x, but the partition function is large iff M halts. The ZFC results follow by taking M which enumerates all provable propositions under ZF and halts iff it proves 1 = 0.", "summary_of_the_review": "I am not an expert in this area so I'm not sure to what extent the field was already aware of issues of computability. Superficially the connection between EC and the halting problem does seem quite straightforward, but if this was not observed or studied in any depth previously in the EBMs literature, I think the submission is a worthy conceptual contribution that should be accepted.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Ce2_S28GE6i", "reviewer": "Reviewer_EwJC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "The paper is generally well written with a good exposition. One glaring exception (for me) is the 2nd paragraph of Section 2.4 where the reduction from neural sequence to formal languages is presented. This is crucial for understanding the paper, yet it is done quickly and I found it hard to follow. It may also be a good place to draw clear distinction from the work of Perez et al (2021). This (and Theorem 1) are key, after all, theorem 2 (for instance) is quite straightforward once the setup is established.\n\nIt would be nice to connect the 'recommendations' of Section 7 to actual EBM's used in practice. ", "summary_of_the_paper": "The paper works in a computational model where various architectures of energy-based-models are viewed as computational models for accepting languages. EBM's assign a weight to each string. The sum of weights is called the partition function and this needs to be computed (or at best approximated) if the energy is to be thought of as a probability measure. The paper shows that expressive EBM's are turning complete, and uses that to show that the partition function may be uncomputable. And that is even in the case the energy of a sequence could be computed in poly-time. The paper then shows some corollaries and variations of this result, showing that model selection is undecidable as well. The paper concludes by suggesting scenarios where the partition function is computable but this naturally comes at the expense of the expressivity of the model.", "summary_of_the_review": "The paper is clear and interesting, but suffers from two major weaknesses:\n1. It seems to me the big 'insight' is Turing completeness of the model, but this is (mostly) done in previous papers. Once this is established the remaining reductions are much less surprising.\n2. I'm not sure the paper is a good fit for ICLR. It is mainly a complexity/computability paper where the models are related to ML. I'm skeptical that its insights are interesting for most of the ICLR audience  (If I'm wrong I'm  happy to be corrected).", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "0m2vSGF4L9", "reviewer": "Reviewer_NAcm", "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": "**Strengths:**\n\n- This paper rigorously explores the computational barriers of calculating the partition function and model selection, both of which are fundamental machine learning tasks\n\n- A specific EBM is exhibited whose partition function is uncomputable (even unprovable) assuming the consistency of ZFC -- to my knowledge this is a new connection between logic and machine learning.\n\n- Sections 7 and 9 point to more interesting work to be done\n\n**Concerns:**\n\n- The uncomputability of the partition function is not necessarily a barrier to using EBMs in practice if the task at hand does not require sampling or model selection\n\n- The uncomputability of the partition function seems to be known. See the \"Remark on computability\" in Lin et al '21. Also the proof of Lin et al's Theorem 5 uses a very similar construction to the paper under the review, and this should be mentioned.\n\n- As this paper admits, the EBMs studied are pathological and not necessarily an obstruction to practice. There is also a lack of discussion on polynomial-time computation of partition functions in less pathological situations (see [1,2,3] below) \n\n- Only rather specific asymptotic estimates of the partition function are ruled out. Perhaps this deserves further study.\n\n**Comments**\n\n- pg 4: I had trouble understanding the phrase \"many estimation procedures are anytime algorithms\". Can you explain this a bit more? It seemed that asymptotic estimates defined here capture the idea of the sample size going to infinity, but I am unclear on the details.\n\n- pg 6, Theorem 4: Is it possible to simplify the proof of Theorem 4 as follows? Given a randomized estimate $\\hat Z_\\epsilon$, one can compute $\\mathbb{E}[\\hat Z_\\epsilon]$ by derandomization. If $\\varepsilon^{-1} Z \\leq \\mathbb{E}[\\hat Z_\\epsilon] \\leq \\varepsilon Z$ holds, then the exact estimate $\\mathbb{E}[\\hat Z_\\epsilon]$ satisfies Equation (2) from Lemma 1 with probability $1$. But this is impossible by Lemma 1. \n\n- pg 7, Theorem 7: In most applications, it is not necessary to verify identifiability with an algorithm. Perhaps it is worth only mentioning the model selection result in the main text and using the identifiability as a proof tool in the Appendix.\n\n- pg 9, Conclusion: Lin et al '21 are aware of computability issues arising from EBMs. To my understanding, the work under review continues the conversation about uncomputability and says some interesting new things about it. And again, just because the partition function is uncomputable, it doesn't mean that EBMs are useless for all applications. I think the conclusion should be rephrased to acknowledge these points.\n\n- pg 20: Table C.1 is interesting and could be cited in the main text.\n\n**Minor issues**\n\n- pg2, Table 1: This table is hard to understand without knowing the definitions. The phrase \"suspected to be useless in general\" is too informal.\n\n- pg 5, Theorem 3: Please describe what $\\tilde b$ is around here.\n\n- pg 5: \"The weighted language... by simulating $x$ on $M$.\" Please describe this more  formally. Lin et al's proof of Theorem 5 uses convenient notation for this.\n\n- pg 5: \"We discuss this in further detail in Section 2.5\" This is a backward reference; is it a typo?\n\n- pg 6: A brief definition of rejection sampling would be helpful at the beginning of Section 5.1.\n\n- pg 8: $\\Psi_{\\vert x \\vert}$ is not defined when describing FGGs. \n\n- pg 19: \"for any halting trace $x'$ of $M_b$\" seems to be a typo.\n\n**References**\n\n[1] M. Luby and E. Vigoda, “Fast convergence of the glauber dynamics for sampling independent sets,” Random Structures and Algorithms, vol. 15, no. 3-4, pp. 229–241, 1999.\n\n[2] A. Galanis, D. Stefankovic, and E. Vigoda, “Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models,” arXiv preprint arXiv:1203.2226, 2012.\n\n[3] M. Jerrum and A. Sinclair, “Polynomial-time approximation algorithms for the Ising model,”\nSIAM Journal on computing, vol. 22, no. 5, pp. 1087–1116, 1993", "summary_of_the_paper": "This theoretical work highlights uncomputability issues arising with energy-based sequence models. It is shown that an EC-complete family (a certain computational model capturing neural networks and transformers that is essentially equivalent to weighted Turing machines) cannot approximate the partition function of energy-based sequence models (EBMs) even given an unlimited amount of time and space. A consequence is the impossibility of model selection for EBMs. This paper also rules out popular estimators such as rejection and important sampling. This work concludes with a discussion of restricted EBMs that avoid such uncomputability issues. ", "summary_of_the_review": "This paper develops an interesting point of view on machine learning and computability. The proofs seem to be correct. I support accepting this paper once it is revised to take into account concerns raised above.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a deep theoretical paper with results that I consider very interesting. I have *not* had time to check them myself, but I have background in these theoretical matters and the results seem reasonable to me - the hardness of even checking the quality of a solution is well known for partition functions (as well as hardness of any reasonable approximation), but the undecidability seems new - I assume it comes naturally and it is a very interesting result - I have seen similar decidability issues for #P: general probabilistic polynomial time Turing machines (it is unclear if a connection was sought here). Reviewers are all positive about the content, and authors have acknowledge some points for improvement.
Decision: Accept (Spotlight)