Probability Distributions Computed by Autoregressive Transformers
Authors: Andy Yang
Anej Svete
Jiaoda Li
Anthony Widjaja Lin
Jonathan Rawski
Ryan Cotterell
David Chiang
Venue: ICLR 2026 Poster (2026)
Keywords: expressivity
weighted automata
language models
transformers
linear temporal logic
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We exactly characterize the probability distributions expressed by transformers when viewed as language recognizers and autoregressive models.

Abstract: Most expressivity results for transformers treat them as language recognizers—devices that accept or reject strings—rather than as they are used in practice: as language models that generate strings autoregressively and probabilistically. We characterize the probability distributions that transformer language models can express. We show that making transformer language recognizers autoregressive can sometimes increase their expressivity, and that making them probabilistic can break equivalences that hold in the non-probabilistic case. Our overall contribution is to tease apart what functions transformers are capable of expressing in their most common use case as language models.

Published as a conference paper at ICLR 2026
PROBABILITY DISTRIBUTIONS COMPUTED BY AUTOREGRESSIVE TRANSFORMERS
Andy Yang' Anej Svete? Jiaoda Li
Anthony Widjaja Lin
Jonathan Rawski
Ryan Cotterell David Chiang'
University of Notre Dame, USA
2ETH Zürich, Switzerland
3 MMax-Planck Institute for Software Systems, Germany
University of Kaiserslautern-Landee Germany
San José State University, USA
ABSTRACT
Most expressivity results for transformers treat them as language recognizers devices that accept or reject strings- rather than they are used in practice: as language models that generate strings autoregressively and probabilistically. We characterize the probability distributions that transformer language models can express. We show that making transformer language recognizers autoregressive can sometimes increase their expressivity, and that making them probabilistic can break equivalences that hold in the conpbbbbaiilistic case. Our overall contribu- tion is to tease apart what functions transformers are capable of expressing in their most common case language models.
INTRODUCTION
Most work studying transformer expressivity, i.e., what classes of computations transformers can perform, treats them as language recognizers, where the input is string and the output is binary classification: true if the string is accepted and false otherwise (Strobl al., 2024). However, the most common practical use of transformers is as language models, which differ in two ways: first, the input a prefix of a string, and the output a prediction of the next symbol: second, the predic- tion is a probability distribution rather than a binary decision. Such probability distributions, when estimated from large text corpora, have enabled wide range of applications in natural language processing and beyond. This paper focuses on fundamental question: which previous findings on transformer expressivity carry over from the language recognition setting to the language mod- eling setting? On one hand, positive answers validate the utility of previous results on language recognition when studying language models. On the other, negative answers further underscore the necessity of studying language models qua language models.
In order to develop a formal theory of transformers as language models, we introduce two dis- tinctions: unweighted (or equivalently, Boolean-weighted) versus real-weighted computation and classifiers, which map a complete string to a value, and autoregressors, which map each prefix a distribution over the next token. This four-way distinction is visualized in Fig. 1. Using this terminology, most theoretical work on transformer expressivity (e.g. Yang et al., 2024; Jerad al., 2025) focuses on Boolean-weighted classifiers, while practical applications use transformers as real-wei autoregressors. This work investigates whether established expressivity results re- main valid when moving from goolean-weighter to real-weighted transformers, and from classifier settings to autoregressive ones.
We answer these questions for several variants of transformers (see Fig. 1). Yang et al. (2024) proved that masket rightmost unique-hard attention transformers (UHATs), as Boolean classifiers, recognize the same languages as linear temporal logic (LTL) and counter-free automata. Jerad et al. (2025) proved that lefimost UHATs, Boolean classifiers, recognize the same languages ment of LTL, called in our notation TL[P]. Li and Cotterell (2025) proved that softmax attention transformers (SMATs) with fixed precision, Boolean classifiers, recognize the guages. These results carry over easily to real classifiers (Cor. 5.2), with the caveat that there are two commonly-used weighted analogues of counter-fres automata, deterministic and nondeterministic.
frag-
class of lan-

---

Published as a conference paper at ICLR 2026
Boolean clasxifiers
Boolean cutoregressors
Real classifiers
Real autoregressors
cfNFAs
Poop 3.5
rightmost UHATs LTL = cfDFAs
rightmost UHATs LTL
rightmost UHATs LTL
rightmost UHATs
LTL=
cfF==s cfDFAs
cINFAs
leftmost UHATs
leftmost UHATs fxxe--prcisioon SMATs TL(P)
leftmost UHATs fixed- pred-prreision SMATs TL
leftmost UHATs fixed-precision SMATs TL(P)
Prop
fixed-precsion
SMATs TL(P)
Figure 1: In the Boolean semiring, equivalences from the literature (Yang al., 2024; Jerad al., 2025; Yang et al., 2025) carry over from classifiers to autoregressors: however, sometimes autore- gressors are more expressive than classifiers. In the real semiring. LTL and counter-free DFAs and NFAs become less expressive than counter-free NFAs, and rightmost UHATs are only as expressive as the former. Key: strict inclusion, equivalence. of incomparable.
We show that surprisingly, these two diverge in the real-weighted setting, despite being equivalent in the Boolean setting. With real weights, UHATs are only equivalent to counter-free DFAs.
This caveat notwithstanding, we may use LTL and TL[P] draw conclusions about the transformer variants listed above. First, real classifiers define some weighted languages that real autoregressors do not, and vice versa (Cor. 5.4). To pinpoint more precisely how classifiers and autoregressors dif- fer, we turn to Boolean weights. Here, UHAT classifiers and autoregressors are equivalent (Thm. 5.6). But for leftmost UHATs and fixed-precision SMATs, autoregressors are strictly more expressive than classifiers (Prop. 5.8).
Similarly, Yang et (2025) considered SMATs with fixed precision but arbitrary precision inside attention. As Boolean classifiers, such transformers are exactly equivalent to temporal logic ex- tended with counting operators. But here we show that, as autoregressors, they become slightly more powerful (for given fixed depth).
Our results largely validate existing results on expressivity of transformers as language recognizers. In many cases, they allow us to transfer results language recognizers language models. For example, since UHATs as language recognizers cannot recognize PARITY (Hahn, 2020), neither can UHATs language models. But results also give good reasons to be cautious about presuming that results on language recognizers directly apply to language models as well.
In $2, we define notational preliminaries. We then ($3) define the classes of transformers sider and how they can be used as classifiers and as autoregressors. We do this by introducing the notion of state encoder, and in $4 show how other formalisms, deterministic finite automata (DFAs) and linear temporal logic (LTL), can also seen as state encoders and therefore can be used classifiers and autoregressors. Then ($5), using LTL, we investigate the expressive power of transformers as both classifiers and autoregressors, yielding the results shown in Fig. 1.
PRELIMINARIES
Throughout this paper, we work with weighted languages. We define some key concepts here, but for more detailed introduction, see the handbook chapter by Droste and Kuich (2009).
Let Σ be an alphabet, that is, a finite, non-empty set of symbols, and let be the set strings over Σ. We often augment E with start and end symbols BOS and EOS, but never consider BOS or EOS to belong to Σ. For any string w = wi ... w,, we write the length of w as |ww = n. We write un <i Wi -0:1 and ws w1 w.. We write for the empty string.
2

---

Published as a conference paper at ICLR 2026
We think of weights and probabilities elements of semirings, an abstraction of the usual addition and multiplication operations that allows results and algorithms to apply generically to multiple settings. A semiring K has addition operation @, additive identity 0, multiplication operation @, and multiplicative identity 1. The two semirings we focus on in this paper are the (extended) real semiring R20. which contains all nonnegative real numbers and to0, and which @ and @ are real addition and multiplication; and the Boolean semiring IB, in which is disjunction (V), 0 is false (1), & is conjunction (A), and 1 is true (T).
A weighted language (also called a formal power series) is a function S: E" K. When KK is complete (that is, allows infinite summations, as Rzo and B do), we call a weighted language normalized if Ewer- S(w) =
For sets X and Y, write y for the of functions from X to Y, and 2 for {0, 1}x or the power set of X. For any proposition 6 we write I {o} to be 1 if Φ is true and 0 if Φ is false.
3 TRANSFORMER LANGUAGE MODELS
In this section, we recall the definition of transformers that we will use throughout most of this paper. We also distinguish between ways that transformers (and other formalisms) be used to define weighted languages.
3.1 UNIQUE HARD ATTENTION TRANSFORMERS
Following Yang et al. (2024), we use unique-hard attention transformers (UHATs), specifically, with rightmost-hare hard attention, strict future masking, and no position embeddings. We give defini- tion of strictly masked rightmost- attention here; for a definition of the rest of the network, see, for example, the survey by Strobl et al. (2024).
The attention function receives a sequence of query vectors g()) E Rd,, key vectors k() E IR,, and value vectors v()) e Rd (all of which are column vectors), for i, E [n]]. At each position computes sequence of vectors
Att ((a (E(m)) (v())))))) = (c()))
where
(j) (.) k()
is attention for each position j, is the maximum attention score, is the rightmost maximum-scoring position, and is the attention output.
0 = max as (j) JRl
J. max
< (;( = a.}
(0 vii
if >
0
if = 0
Given an input string w w1 ... W.. transformer prepends symbol wy BOS and uses a composition of attention functions and feed-forwart networks to compute sequence of states T(w) = (h(0) hx)),, where (()) E IRd the state after reading w;. There are at least two ways use T define a weighted language."
3.2 CLASSIFIERS
The first way that transformer can define weighted language is as classifier.
Definition 3.1. UHAT classifier a pair C = -T, .), where T: Σx + (Rdy+ is a UHAT and dd K. outputs scalar weight the last position only:
C(w) c(T(w)(T))
A third intermediate way would be to multiply the weights at each position like an autoregressive model, but not to pass the output symbol at each position autoregressively to the input at the next position. Although interesting in its own right, it has not, our knowledge, heen used with any neural sequence models, and we do not explore this style of model here.

---

Published as a conference paper at ICLR 2026
For the Boolean semiring (K IB), accept string iff the transformer outputs T the last position. For example, the output function could c(y) = I + 2 0}. where W and are parameters. This is the setup used for binary classification with transformer encoder (Devlin al., 2019) and most theoretical papers on transformer expressivity.
3.3 AUTOREGRESSIVE MODELS
The second way for transformer to define a weighted language is as an autoregressive model, or autoregressor for short (by analogy with classifier). An autoregressor pairs a UHAT encoder with an output function a: I + K which outputs at each position a weight distribution for the next symbol, including EOS. the real semiring (K = Rzo), a typical example of such an output function is a(h) softmax(Wh++ b).
To line up with the more familiar notation of conditional probability distributions, we write, for all E U [ROS),
Pr wgi) = (((ww)))()
(3)
This is well-defined because T(w); depends only on wis, that is, wgi = w's, = T(w), = T(w"). As suggested by this notation, we want Pr u) to be a probability distribution over I U {EOS}. But we impose stronger condition. First, extend Pra u) to the probability distribution suffixes given (possibly empty) prefixes:
Pr u)
X (r wvez)
PRA (BOS))) uv))
(ra(w)= A (w e).
(5)
Then we require that every such distribution sums to one:
Definition 3.2. UHAT autoregressor over a complete semiring IK pair A (T, (T,a), where E + (TE a UHAT, and a: Rdd Euu(so)) a function such that for all E (using
the notation of Eqs. (3) and (4)),
+ DE
Pra(e =)=1.
(6)
This implies that:
An autoregressor generates strings symbol by symbol. That is, for all prefixes
Σ
Pr u) =1
(EFS)
An autoregressor does not have any dead ends or endless loops. That is, for all prefixes u.
Pra (ra uue + O
(ra(wv) + O for some suffix v.
(8)
An autoregressor defines normalized weighted language.
OTHER FORMALISMS
We can analogously use other formalisms to define classifier autoregressive models. We general- ize from transformers to other formalisms by means of the following notion.
Definition 4.1. state encoder is a function that sends a string wi ... w,, to a sequence of states qu... .u...., 4n Q such that q; depends only wei.
Like transformers, any state encoder can be equipped with an output function e: Q + K to give
a classifier model (as Def. 3.1) or a: Q + (FOS) (as in Def. 3.2) to give an autoregressive model.
4

---

Published as a conference paper at ICLR 2026
913
a/$
a/2
Q1
92
q1
42
qo/0
a/ 1
/2/
a/?
(a)
(b)
(c)
Figure 2: (a) A DFA that is counter-free (with k: 2). (b) A DFA that is not counter-free, because for all k, the strings a and a=1 have opposite actions. (c) A counter-free weighted NFA that has equivalent weighted DFA (Prop. 5.5).
4.1 FINITE AUTOMATA
We give brief definitions of weighted and/or counter-free deterministic finite automata. For fuller treatment, please see the handbook chapter by Droste and Kuske (2021) and the monograph by McNaughton and Papert (1971).
Definition 4.2. A deterministic finite automaton (DFA) is tuple M (E, Q, (), where
Σ is an alphabet
Q is a finite set of states
8: Q x + Q is transition function
E the initial state.
We extend 5 to a mapping 8* Q Ex - Q such that:
8 8* c) =
8 (g 8 (8(1,
DFA M defines state encoder
M: 3" + Q
M(w); = {
i= 8 W1 w.)) 0 0<i5
(10)
A DFA with classifier outputs in the Boolean semiring is the same the standard definition of DFA: the states that output T are the accept states, and the states that output 1 are the reject states.
A DFA with autoregressive outputs in the real semiring is the same the standard definition of weighted DFA: when it is in state q, the next input symbol a determines both the next state 8(4, o) well the symbol weight a(g) (a). Moreover, each state has accepting weight (FQ)(.))).
In this paper, we are only interested in the following subclass of finite automata called counter-free automata, which we abbreviate cfDFAs.
Definition 4.3. We say that DFA with transition function o is counter-free if there exists some k such that for all states and all strings w, we have 5"(g, w²) = 8* (q. w 6+1)
Examples of counter-fre and non-counter-free DFAs are shown in Fig. 2ab.
Counter-free nondeterministic finite automata (NFAs), in which state can have more than one outgoing transition with the same symbol are equivalent to counter-free DFAs (McNaughton and Papert, 1971). For definition and proof of equivalence, please see App. C.
4.2 LINEAR TEMPORAL LOGIC
We give a brief definition of linear temporal logic and its fragments. For a fuller treatment, please the article Goranko and Rumberg (2025).
5

---

Published as a conference paper at ICLR 2026
Definition 4.4. The formulas past LTL are defined by the grammar
Φ :== 0 1 Φ1 A
02
a
o E Σ
BOS
Beginning of string
Y
Yesterday
HΦ1
Historically
Φ1 S 02
Since
Formulas T (true), 1 (false), Φ1 V 02. Φ1 02. and terms of the above. The temporal operator Pá (which holds iff a was Previously true at some time) can be defined Hő -P((-)))
be defined syntactic sugar in
The semantics of formulas given by the relation w, F= Φ (² ("w satisfies & at position i"), defined as follows:
w, i == 10
w. i E Φ1
(11a)
w, = Φi d2
= w. F Φi and w. i d2
(1lb)
i BOS
b i=0
(1lc)
w, =
= W/ = a = i > O and w, i F Φ1
(11d)
w, Yo
(1le)
w, HΦI
w - Φ1 for all Si
(IIf)
w, = Φ1 02 = (w.j - 22 for some j S i) and (w,j' J' - for all j i))
(1lg)
We write = Φ as shorthand for w. |w0| F Φ.
For any set of operators O C (Y. H.S). we write TL(O) for the set of formulas using only operators in O. Thus past LTL TL(Y, Sj. Given tuple of formulas (dh..... .., dm we can define state encoder
Φ: Σ + (Bm*)* (ww): = (w, + =1) ..... 1i 6m)).
Droste and Gastin (2019) define weighted first-order logic, with several variations corresponding several subclasses of weighted counter-free automata. Mandrali and Rahonis (2013; 2015) do the same for LTL. Both of these logics have, roughly speaking, four layers: (I) core Boolean logic, (2) weights conditioned on formulas, (3) products over positions, and (4) addition and sums over positions. This is similar functions that can choose weights conditioned on formulas, and (3) autoregressive output functions that also compute products over positions.
framework, which has (1) core Boolean logic, (2) classifier output
EXPRESSIVITY RESULTS
Previous results have shown that UHATs, LTL, and efDFAs are equivalent in terms of language recognition. In 15.1, we use the results to show that these formalisms are also equivalent as weighted classifiers and autoregressors.
Next, we compare the expressivity of classifier versus autoregressive models. Given the equivalence of the above formalisms, we will mainly discuss LTL. In the real semiring ($5.2), LTL classifiers define exactly the aperiodic step functions (defined below), which are less expressive than LTL autoregressors. And LTL autoregressors, in turn, are equivalent to counter-free DFA autoregressors and less expressive than weighted counter-free free NFAs.
In the Boolean semiring, LTL classifiers and autoregressors are equivalent, which is the main result of $5.3.1. However, when we consider fragments of LTL, this equivalence breaks down, and autore- gressors may become more expressive than classifiers ($5.3.2). Similarly, the temporal logic with counting TL(#) and the programming language C-RASP (Yang and Chiang, 2024), autoregressors expressive than classifiers ($5.3.3).

---

Published as a conference paper at ICLR 2026
5.1 STATE ENCODERS
We say that two state encoders TI: Σx + Qi and r2: Σx + Q2 are equivalent there is a bijection and
f: Q1 + Q2 such that for all E Σ", ((( (w)).
Theorem 5.1. UHATs, LTL, and cfDFAs define equivalent state encoders.
Proof. See App. A. The proof is an adaptation of existing results (Yang et al., 2024; Schützeebeerger, 1965; McNaughton and Papert, 1971; Kamp, 1968) connecting UHATs, LTL and cfDFAs as language recognizers.
The following an immediate consequence of Thm. 5.1 and the definitions of classifier and autore- gressive models.
Corollary 5.2. UHATs, LTL, and cfDFAs as classifter models define the same weighted languages. Similarly when they are used as antoregressive models.
Proof. By the previous theorem, all these formalisms define equivalent state encoders. Therefore there exist output functions with which they define the same weighted languages.
5.2 REAL CLASSIFIERS AND AUTOREGRESSORS
In this section, we consider weights in the real semiring. We characterize what weighted languages can be expressed, first by real classifiers, then by real autoregressors.
Definition 5.1. An aperiodic step function (Droste and Gastin, 2008) is weighted language S: E + KK such that S(w) = @. Kę @ (w E Li} where , E IK are constants and L1 Li.... Lim are aperiodic (that is, counter-free) regular languages.
Proposition 5.3. An LTL classifier defines the aperiodic step functions.
Proof. Given any aperiodic step function as defined above, we can write, for each Li, an LTL for- mula Φ;. Then we can write a classifier output function e(h) + hi 60 hi
Conversely, given an LTL classifier consisting of tuple of formulas (#1,..., Φm) and an output function c(h), for every h e 20ml, write the formula Φn A (d; h2). For every h, let Ln be the language defined by on. Then the weighted language can be written as the step function S(w) = ① ne c(h) 69 I (w In))
The following easy corollary of Prop. 5.3 shows that autoregressors and classifiers are incomparable. makes use of weighted regular expressions (Sakarovitch, 2009), in which the expression (for any a Σ) matches symbol with weight 1, while the expression k (for any k K) matches with weight k.
Corollary 5.4. In the real semiring: (a) The weighted language (2a)* is expressible by an LTL autoregressor, but not by any LTL classifier. (b) The language (1a)* is expressible by an LTL classifier but not any LTL autoregressor.
Both (a) and (b) hold with LTL replaced by TL(H).
Proof. The first language has an infinite number of string weights, but an aperiodic step function only output finite number of different weights. On the other hand, it easy write LTL (or (H) autoregressor to recognize this. The second language can easily be expressed by classifier assigning weight 1 to every string of zero more a's, but is not expressible by any autoregressor because is not a normalized weighted language.
As real autoregressors, LTL formulas are equivalent to counter-free DFAs by Cor. 5.2. However, there are several nonequivalent weighted analogues of counter-free automata (Droste and Gastin, 2008), and LTL and UHAT autoregressors are only equivalent to the least powerful of these. In particular, both are less expressive than weighted counter-free NFAs.
Proposition 5.5. Weighted counter-free NFAs define more weighted languages than counter-free DFA autoregressors do.
7

---

Published as a conference paper at ICLR 2026
Proof. See App. C. Fig. 2c shows example of counter-free weighted NEA that is not deter- minizable.
5.3 BOOLEAN CLASSIFIERS AND AUTOREGRESSORS
To examine more carefully how autoregressors add expressivity, we turn the Boolean semiring. We will see that LTL classifiers and LTL autoregressors equivalent, but with an important caveat: with certain fragments and extension LTL that use only subset of the temporal operators, autore- gressors can be more expressive than classifiers. These variants of LTL are particularly interesting because they have been proven to be equivalent to variants of transformers.
5.3. LTL
In the Boolean semiring, LTL classifiers and autoregressors are equivalent, but the conversion from an autoregressor classifier uses the Y and H operators.
Theorem 5.6. For any of operators O (YY.H.S)
(a) For any nonempty language defined by Boolean- Boolean-weighted TL[O] classifier, there exists a Boolean-weighted TL(O) autoregressor deffnnng the same language I..
(b) For any language L defined by Boolean-weighte TL[O] autoregressor, there exists Boolean-weighted TL(OU (Y, (Y,H)) classifier defining the same language L.
Proof. See App. B.3 for the full proof; a proof sketch follows.
To prove (a), need construct an autoregressor that tests, given any position i and symbol ar, whether weg is a prefix of some string that is accepted by the classifier. To do this, we introduce two new operators as "syntactic sugar" that do not increase the expressivity of the logic:
+ next (Ø) R += prefix(o)
wa
O there exists E E* such that uv = Φ-
The next, operator is what lets us hypothesize a as the next symbol, and the prefix operator is what lets us hypothesize the rest of the string.
To prove (b), we need to construct a classifier that tests whether, for every position the autoregres- predicts that wei be followed by w, To test the relationship between each prefix and the next symbol, we use the Y operator, and to do so at every position, we use the H operator.
From Thm. 5.6, we can conclude that for UHATs, which are equivalent to LTL, autoregression does add any expressivity. On other transformer variants, please see $5.3.2.
The construction that "desugars" prcfix(o) into formula of TL[O] yields formula whose size is exponential that Φ. To shed light on whether this bound tight, we show the following.
Proposition 5.7. (a) There does not exist a transformation prefix' such that prefix' (Φ) con- structible in polynomial time (in (Ø)) and satisfies Eq. (18) for every formula à in TL Y),
unless = PSPACE.
(b) Similarty for [H unless P NP.
(c) Similarly for TL[Y], unless P NP.
Proof. See App. B.4. This is reduction from existing results on the hardness of testing whether formula defines an empty language (Giacomo and Vardi, 2013; Fionda and Greco, 2016).
Note that we have only shown (conditionally) that constructing prefix' (Ø) requires super- puper-polynomial time; it's possible that prefix' (Φ) is short but difficult to construct.
5.3.2 FRAGMENTS OF LTL
Thm. 5.6 shows that LTL classifiers and autoregressors are equivalent, and this remains true for some fragments of LTL. But the asymmetric conditions of the theorem suggest that when the set of
8

---

Published as a conference paper at ICLR 2026
operators O lacks either H Y, Boolean autoregressors this section, we prove that this is indeed the case.
expressive than classifiers. In
Moreover, such fragments relevant to the study of transformers. Li and Cotterell (2025) show that fixed-precision aature-masked transformers are equivalent to TL[P]. which is in turn equivalent to TL Similarly, Jerad al. (2025) show that masked seftmost-hard attention transformers are also equivalent to [.
Proposition 5.8. The language (ab)* defined by Boolean TL( autoregressor but not defined by any [ or TL(Y) classifier.
Proof. Consider the state encoder & (BOS, a, b) and the output function
aQuoos qa. (a) T c Goos T or q = =
a(qoos: qas 9b) T qa = T
alyoos: qu. 96 (EOS) -T- IBos = T q =T
But a formula in TL[Y] can't distinguish between strings that differ beyond their last symbols (for some constant depending on the formula), and for any k. we have ab(ab)Ik/22 E (ab)* but ba(ab)(k: [8/2] & (ab)*. A formula in [L(H] is equivalent to one in TL(P]. which can only define stutter-invarian language (that is, language L such that for all o, v. we have uov E L > uoov E (Peled and Wilke, 1997)). And (ab)* is not stutter- invariant, because ab E (ab)* but aab & (ab)*.
Consequently, (ab)* is definable by leftmost-hard UHATs and fixed-precision SMATs as autoregres- sors, but not as classifiers. However, the expressiveness added by autoregression remains limited, as (aab)* is not definable.
Proposition 5.9. The language (aab)* is not definable by any H classifier or autoregressor.
Proof. See App. D. We show that to distinguish aab from anab, we need at least two nested Y operators. But the conversion from an autoregressor to a classifier (Thm. 5.6(b) adds only one Y. so (aab)" is not definable by any TL H[] autoregressor.
Consequently, (aab)* is not definable by any leftmost-hard UHAT fxxed-precisio SMAT, either as autoregressors or classifiers.
5.3.3 TEMPORAL LOGIC WITH COUNTING
Other formalisms besides the ones discussed above have been proposed for comparison with trans- formers. Yang et al. (2025) prove that SMATs, with fixed precision outside attention and arbitrary precision inside attention, equivalent to temporal logic with counting operators, TL(#]. They considered the family of languages
L1 a"
(12)
{ Lab" & even
L
(13)
Taa"
I odd
and showed that, as Boolean classifiers, transformers with depth & can recognize Lg (and not Lx++1 ) But their experiments were the symbol-prediction task ($6). closely related to Boolean autore- gression. They showed both theoretically and experimentally that SMATs with depth & can solve the pymbol-prediction task for not only Lt. but L*+2 (and not Lx+3).
In the present framework, this discrepancy can be readily explained. Like TL(H), the logic TL lacks Y operator or an equivalent. So it is more expressive as an autoregressor than as a classifier.
6 RELATED WORK
Theoretical study of transformers as language models has not gone totally neglected. Hahn (2020) compared SMAT language model with probabilistic finite automatio for parity (strings that have

---

Published as a conference paper at ICLR 2026
an odd number of I's). Yao et al. (2021), following previous work on RNNs, considered trans- former language model to e-generate a language it assigns probability at least e to each symbol in every string in the language (and strings not in the language). They also discussed how to convert a construction for a bounded Dyck language (strings of matching parentheses up to a certain depth) from an e-generator to a language recognizer. Svete and Cotterell (2024) showed that average-hard attention transformer language models can exactly express all n-gram language models. These stud- ies were specialized to particular languages, used specialized ways of comparing distributions that do not generalize in an obvious way.
On the experimental side, Bhattamishra et al. (2020a) proved theoretical results on transformers as language recognizers but carried out experiments on transformer language models for the character prediction task: predict, at each position, the set of next possible symbols (i.e. Boolean autoregres- sion). This experimental setup was previously used in studies of RNNs, and has been adopted in other studies of transformers (Huang et al., 2025; Yang et al., 2025), which we discussed in $5.3.3.
The idea that the sequence of output vectors of transformer and the states of finite automaton can be connected via the notion of state encoder is not new; previous results on using transformers to simulate (weighted) finite automata made similar connection (Liu et al., 2023; Rizvi-Martel et al., 2024).
7 DISCUSSION
In this paper, observed settings where classifiers coincide with autoregressors, and settings where they don't. Where the two do coincide (e.g., Boolean-weighted LTL and UHATs), we can now transfer results definability from the more well-understood world of classifiers to autoregressors. For example, PARITY is not expressible by UHAT classifiers (Hahn, 2020), and therefore not by UHAT autoregressors. Where classifiers and autoregressors do not coincide (e.g., with real weights), we do not yet have good techniques for showing inexpressibility by autoregressors, which we leave for future research.
One direction for future work is to extend our results to more realistic classes of transformers by con- sidering log- seg-preiision softmax attention or positional encodings. The former would require stronger characterizations of log-precision softmax attention transformers. The latter could utilize connec- tions between positional encodings and numerical predicates, as discussed by Yang et al. (2024); Barcelo et al. (2024).
Another future avenue studying autoregressors enriched with chain of thought (i.e., allowing the autoregressor to for number of intermediate steps before producing answer). There numerous results relating transformers with chain of thought and different classes of computational problems (Pérez et al., 2021; Merrill and Sabharwal, 2024: Bhattamishra al., 2020b; Li et al., 2024; Nowak et al., 2024; Li and Wang, 2025; Hou et al., 2025), but only with Boolean weights. What can be said about real-weighted autoregressors with chain of thought, and the probability distributions they compute? For example, can they compute those of probabilistic Turing machines solving problems in the BPP even PP complexity classes?
Lastly, by clarifying the relationship between classifiers and autoregressors, our results provide a principled way interpet and build upon the various experiments that test the expressive capabilities of transformers (Weiss et al., 2018; Bhattamishra et al.. 2020a; van der Poel et al.. 2024: Delétang et al., 2023; Someya et al., 2024; Borenstein et al., 2024; Butoi al., 2025, inter alia). For example, we are able to explain in $5.3.3 why transformers as classifiers and autoregressors exhibit different expressive capabilities in Yang et al. (2025)'s experiments. More generally, we have identified several theoretical separations between the expressive capabilities of classifiers and autoregressors both the Boolean and weighted cases, which future work could probe experimentally.
ACKNOWLEDGEMENTS
This paper developed from the findings of the working group probability at Dagstuhl Seminar 25282. "Theory of Neural Language Models." We are grateful to the Leibniz Center for Informatics for their support. We also thank Gavin Dooley for his feedback and correction.
10

---

Published as a conference paper at ICLR 2026
This material is based in part upon work supported by the US National Science Foundation under Grant No. 2502292 and the European Research Council under Grant No. 101089343. Andy Yang is supported by the US National Science Foundation Graduate Research Fellowship Program under Grant No. 2236418 18, and Anej Svete supported by the ETH Al Center Doctoral Fellowship.
REFERENCES
Pablo Barcelo, Alexander Kozachinskiy, Anthony W. Lin, and Vladimir Podolskii. Logi- cal languages accepted by transformer encoders with hard attention. In Proceedings of the 12th International Conference on Representation Learning (ICLR), volume 2024, pages 22077-22087, 2024. URL https::/ iclr. cc/ paper Fileesppaprr2222/fillee 5f0fdc1 P
.df.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. the ability and limitations of Transformers to recognize formal languages. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Processing (EMNLP), pages 7096-711 16, 2020a. doi:10. 1011536/1/22200mmmmll ma6n.576.
Satwik Bhattamishra, Arkil Patel, and Navin Goyal. On the computational power of transformers and its implications in sequence modeling. In Proceedings of the 24th Conference on Compu- lational Natural Language Learning, pages 455-475, 2020b. doi:10. 1ai:10.116555 10018/6//112222coomll wwg.g/rggg00 con11-1.37/.
URL
Nadav Borenstein, Anej Svete, Robin Chan, Josef Valvoda, Franz Nowak, Isabelle Augenstein, Eleanor Chodroff, and Ryan Cotterell. What languages are easy to language-model? A perspective from learning probabilistic regular languages. In Proceedings of the 62nd An- nual Meeting of the Association for Computational Linguistics, pages 15115-15134, 2024. doi: 10. 1
Janusz A. Brzozowski. Derivatives of regular expressions. Journal the Association for Computing Machinery, ((4)):41-444, October 1964. 160:110.1445/221233322224
Alexandra Butoi, Ghazal Khalighinejud, Anej Svete, Josef Valvoda, Ryan Cotterell, and Brian DuSell. Training neural networks recognizers of formal languages. In Proceedings of the 13th International Conference on Learning Representations (ICLR), volume 2025, pages 46273- 46316, 2025. URL /tttps://operevviii wtw.eeeeeet/oorrm//ddaa....oo
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, and Pedro A. Ortega. Neural networks and the Chomsky hierarchy. In Proceedings the 11th International Conference Learning Representations (ICLR), 2023. URL httpp:://ppeneeviiieee/
net met/fooumm?mn /toof/rr/m/ddbbxH/ekeeeeee
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional Transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL HLT), pages 4171-4186, 2019. doi: 1oi:10.18653:/ 1/N19-1433
Manfred Droste and Paul Gastin. On aperiodic and star-free formal power series in partially com- muting variables. Theory of Computing Systems, 42(4))608-631, 2008. doi: 1007//00222-0077 9064-z.
Manfred Droste and Paul Gastin. Aperiodic weighted automata and weighted first-order logic. In Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019. 200000442.00LPISSMMMPC..220
Manfred Droste and Werner Kuich. Semirings and formal power series. In Manfred Droste, Werner Kuich, and Heiko Vogler, editors, Handbook Weighted Automata, pages 3-28. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. ISBN 978-3-642-01492-5, doi: 5.1.
Manfred Droste and Dietrich Kuske. Weighted automata. In Jean-Eric Pin, editor, Handbook of Automata Theory, pages 113-150. European Mathematical Society Publishing House, Zürich, Switzerland, 2021. 4o::10.4177AAATTMMAAAA.
11

---

Published as a conference paper at ICLR 2026
Valeria Fionda and Gianluigi Greco. The complexity of LTL finite traces: Hard and easy frag- ments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, pages 97 977, 2016. doi:10.1609/aaii. 10114
Giuseppe De Giacomo and Moshe Y. Vardi. Linear temporal logic and linear dynamic logic on finite traces. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), pages 854-860, 2013. URL wwwph:tt///wwe ijcai org/Proceedings// /1tps//////aap///////3 pdf.
Valentin Goranko and Antje Rumberg. Temporal Logic. In Edward N. Zalta and Uni Nodelman, editors, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford Univer- sity, Summer 2025 edition, 2025. URL https: //tptto/p//ooo//o stanford edu/ htth/archiivsee archivesssuum2225/ sum2025/ intrreeslogic-temporre
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 8:156-171, 2020.
003066.
Kaiying Hou, Eran Malach, Samy Jelassi, David Brandfonbrener, and Sham M. Kakade. Universal length generalization with turing programs. In Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025. URL
nwt/ um? d=RSSd6G31cb.
Xinting Huang, Andy Yang, Satwik Bhattamishra, Yash Sarrof, Andreas Krebs, Hattie Zhou, Pree- tum Nakkiran, and Michael Hahn. A formal framework for understanding length generalization in transformers. In Proceedings of the 13th International Conference Learning Representations (ICLR), 2025. URL /tttt::://opeeevviie www.eeewwwwwwweeeeeeeeeeeeeeeeee wtwt://oorrummi.AAAASS5S1
Selim Jerad, Anej Svete, Jiaoda Li, and Ryan Cotterell. Unique hard attention: A tale of two sides. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguisties (ACL), pages 977-996, 2025. doi:10.116$3 1/2025 scl-short.76.
Johan Anthony Willem Kamp. Tense Logic and the Theory of Linear Order. PhD thesis, University of California, Los Angeles, 1968. URL https: /www. proquest. com/ cwwm//ocview///20/2c00ccc 302322357.
Jiaoda Li and Ryan Cotterell. Characterizing the expressivity of transformer language models. In Advances in Neural Information Processing Systems (NeurIPS) 38, 2025. URL ///ps://axxiv.. trg/abs/25005 00055.2262333 23623. To appear.
Qian Li and Yuyi Wang. Constant bit-size transformers Turing complete. In Advances in Neu- ral Information Processing Systems (NeurIPS) 38, 2025. URL https::/arrke http://wwwvvv.........../ wrg.iiioorr/aan arg../////........ 12027. To appear.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. In Proceedings of the 12th International Conference on Learning Representations (ICLR), 2024. URL https: //ppnreeee/eeeeewwweee (tte:/oooummmi-3/EEEEeEmmm
Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In Proceedings of the 11th International Conference Learning Representations (ICLR), 2023. URL https://openrevicee .ne./ met//formmlinn www.foondddddeeeo FiddddDD44FFyjjuuu....
Eleni Mandrali and George Rahonis. Characterizations of weighted first-order logics over semir- ings. In Algebraic Informaties: 5th International Conference (CAI), pages 247-259, 2013.
Eleni Mandrali and George Rahonis. Weighted first-order logics over semirings. Acta Cybernetica, 22(2):435 2015. doi: 10. 1o1:100.1433//attccyy...o. 14232/acttcchh.222220155
Robert McNaughton and Seymour Papert. Counter-Free Automata. Number 65 in M.I.T. Press Research Monographs. M.I.T. Press, 1971. UtLhtts:://archiiv http://accccceeeeeeedea/aa//ttte 00 McNa.
William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In Proceedings of the 12th International Conference on Learning Representations (ICLR), 2024. URL https:/ http:///pppeeveeeeeee www.:/eeeoooomiiieeeomomoo wttpeeeww.///eoormr//i/inn//aaa
12

---

Published as a conference paper at ICLR 2026
Mchryar Mohri. Finite-state transducers in language and speech processing. Computational Lin- guistics, 23(2):269-311 311, 1997. URL https: https://aclantholloy.orrg. wtwp:///eo.oo//99220099939
Franz Nowak, Anej Svete, Alexandra Butoi, and Ryan Cotterell. On the representational capac- ity of neural language models with chain-of-thought reasoning. In Proceedings of the 62nd
Annual Meeting of the Association for Computational Linguistics, pages 12510-12548, 2024. doi:10. 10..0.1865/111// 1/2024 acc.o....c-...666.
Doron Peled and Thomas Wilke. Stutter-invariant temporal properties are expressible without the next-time operator. Information Processing Letters, 63(5):243-246, 1997. doi:10.1016/50020-
0190(97)00133-6.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is Turing-complete. Journal of Ma- chine Learning Research, 22:75:1-75:35, 2021. URL http://jmlr.... wwteeo.rrggaaaeee..e //tp html.
Michael Rizvi-Martel, Maude Lizaire, Clara Lacroce, and Guillaume Rabusseau. Simulating weighted automata over sequences and trees with transformers. In Proceedings Tfe 27th Inter- national Conference Artificial Intelligence and Statistics (AISTATS), pages 2368-2376, 2024. URL httph::t///pppe /prcceddins.cccnns mlr. pptps//22//riiiiiaarrreeereeeeee
html.
Jacques Sakarovitch. Rational and recognisable power series. Manfred Droste, Werner Kuich, and Heiko Vogler, editors, Handbook of Weighted Automata, pages 105-174. Springer, 2009. doi: 10. 1111:00077777--3-442111999999999
M. P. Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8
(2):190-194, 1965. 1oi:10.1016/// 10110/0000-199555000000 (955)990995
Michael Sipser. Introduction the Theory of Computation. Cengage, Boston, MA, third edition, 2013. ISBN 113318779X.
Taiga Someya, Ryo Yoshida, and Yohei Oseki. Targeted syntactic evaluation on the Chomsky hier- archy. In Proceedings of the 2024 Joint International Conference on Computational Linguistics, Language Resources and Evaluation (LRECCCOLING 2024), pages 15595-15605, 2024. URL wwo.oog/// 1rec-main. 1356/.
Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal lan- guages can transformers express? survey. Transactions of the Association for Computational Linguistics, 12:543-561, 2024. doi:10. 162/tal_a_000633
Anej Svete and Ryan Cotterell. Transformers represent n-gram language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Lin- guisties: Human Language Technologies, pages 6845-6881, 2024. doi: 4of:10.18653/11/2024 18633/11/204.naadd long.381.
Sam van der Poel. Dakotah Lambert, Kalina Kostyszyn, Tiantian Gao, Rahul Verma, Derek An- dersen, Joanne Chau, Emily Peterson, Cody St. Clair, Paul Fodor, Chihiro Shibata, and Jeffrey Heinz. MrRReTest:: A benchmark for the machine learning of regular languages. Journal of Machine Learning Research, 15(283):1-45, 2024. URL ftttps://jmrrr www..rggggg//////.... 33-0518 h.ml....html.
Gail Weiss, Yoav Goldberg, and Eran Yahav. On the practical computational power of finite preci- sion RNNs for language recognition. In Proceedings of the 56th Annual Meeting of the Associa- fion for Computational Linguistics, pages 740-745, 2018. doi:10. 8653/v1/P18-2117.
Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. In Proceedings of the First Conference on Language Modeling (CoLM), 2024. URL htwps: //op: eview. met//oorm?idd=FmPPaal
Andy Yang. David Chiang, and Dana Angluin. Masked hard-attention transformers recognize ex- actly the star-free languages. In Advances in Neural Information Processing Systems (NeurIPS) 37, pages 10202- 10235, 2024. URL https://procceddings neuripps cc/ paper files/ html.
13

---

Published as a conference paper at ICLR 2026
Andy Yang, Michaël Cadilhac, and David Chiang. Knee-deep in C-RASP: A transformer depth hierarchy. In Advances in Neural Information Processing Systems (NeurIPS) 38, 2025. URL nttps://arxiv orggabs//506.. 16055. To appear.
Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. Self-attention networks can process bounded hierarchical languages. In Proceedings of the 59th An- mual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (ACL-IJCNLP), pages 3770-3785, 2021. doi: 1653/v1/2021 acl-loog.222.
14

---

Published as a conference paper at ICLR 2026
A EQUIVALENCE OF STATE ENCODERS
Theorem 5.1. UHATs, LTL, and cfDFAs define equivalent state encoders.
Proof. First show the equivalence of state sequences defined by UHATs and LTL, and then equiv- alence of LTL and cfDFAs.
The essential observation (Yang al., 2024, Lemma 22) is that the output at every position of every UHAT layer comes from finite set Q S R. So we can think of a UHAT as a function T M + Q", For each g E Q. we can construct an LTL formula o such that T(w); = q + w, F 0g (Yang et al., 2024, Theorems 2, 4). So there exists tuple of LTL formulas (Øy)gEQ that defines a state encoder equivalent to T. Note that the state outputted by T on the prepended BOS symbol can be simulated using BOS formula in the tuple.
In the other direction, for every tuple of LTL formulas (sh1, dh,.... Pm)) defining state encoder Ex - B. there exists UHAT T: Σ- (R4)* defining equivalent state encoder. For each Ōk. we construct a transformer Tk which outputs 1 if w, } Øk and - otherwise (Yang et al., 2024, Theorems 1, 3). Then can parallel-compose all the Ty into single T (Yang et al., 2024, Lemma 25), and add an additional layer which projects the output dimensions of each Tr into a single output vector t such that T(w); C₁ - w. i Øk-
The equivalence between LTL and cfDFAs can be described a little more succinctly. Given a DFA M = (E, Q, 6, c). for each state 9 Q there exists formula 6, such that Φ, = 8(1, w) due to the expressive equivalence of LTL and cfDFAs (Schützenberger, 1965; McNaughton and Papert, 1971; Kamp, 1968). The tuple (#g) then defines state encoder equivalent other direction, given a tuple of LTL formulas (Ø1..... 6m), for each & E [m]] there is an automaton Mr that recognizes the same language as Φk. Then the Cartesian product of all the My defines state encoder equivalent to (ø1...., p.).
M. In the
B AUTOREGRESSIVE MODEL PROOFS
B.1 PROOF OF LEM. B.1
Lemma B.1. There is transformation next, from formulas TL(O) formulas of TL[O] such that for any formula & of TL[O] and for all w E E,,
ト next, (Ø)
(14)
Intuitively, next, removes a a on the right; in other words, ncxt, defines the right Brzozowski derivative (Brzozowski, 1964) of the language defined by d.
Proof. We define next,, recursively:
next, (o) = T
(15a)
next, (a') = 1
if #o
(15b)
next, T
(15c)
next, (-Ø) = -next, (0)
(15d)
next, (Ø1 A Φ2) next,> (Φ1) A next
(15e)
next, (YØ) =
(15f)
next,r (HØ) HØ A next, (1)
(15g)
next S (2) = (next, (()) A (0) Φ2)) V (02).
(15h)
Note that next,, translates temporal operator into another temporal operator, translates formulas of TL(O) into formulas of TL(O) for any O.
Next, prove that next, (Ø) satisfies Eq. (14) by induction the structure of db
15

---

Published as a conference paper at ICLR 2026
Base Cases.
d 0:
w,i F nc)
(15a) T
(16a)
We F 0.
(16b)
If Φ o' for o' # a:
w - next, (o')
(15b)
w -
(16c)
(1dd)
w - o'.
(16d)
Similarly, if Φ = BOS:
next, (BOS)
(15c)
w
(16e)
W = BOS.
(16f)
Inductive Cases. If Ø -01:
w - nexla (-11) (~
(15d)
w == nexlo (
(17a)
f (01)
(17b)
ind. hyp.
un H t1
(17c)
wa F -
(17d)
If Φ 01 A d2:
w = next, (01 A (2)
(15c)
w F (x1) A nnxtt (02)
(17e)
(11b)
(w F next, n(x),((d)) A (w F next, (x2))
(17f)
ind. hyp.
(wa - Φ1) A (wo F 22)
(17g)
(1b]
wo } Φ1 A 02.
(17h)
If Yoi:
w = next nYxt=(Yx)))
(150)
w - Φ1
(171)
(1le)
Wi - Yoı.
(17j)
( = :H:
w next (HØ))
(15g)
H61 next,
(17k)
(11b)
(w Ho1) A (w }= next,
(171)
ind hyp
(w Ho1) (wo = ④1)
(17m)
(11
wo H
(17n)
If Φ 61 S $
w }= next, (01 (2)
(15h) w }= (next (01) (61 S Φ2)) V next, (d2)
(176)
(Ila) (1Ib)
(w = next A (w - S (2)) (w F next, (02))
(17p)
ind. hyp.
(wwo - ( à 2z))) V (wo x2)
(17g)
(ig wo } Φ1 Sz.
(17r)
B.2 PROOF OF LEM. B.2
Lemma B.2. There a transformation prefix from formulas of TL(O) to formulas of TL[O] such that for any formula o TL(O) and for all u E Σ",
F prefix(o) + there exists v E Σ* such that uo - ②b
(18)
16

---

Published as a conference paper at ICLR 2026
Proof. Given formula @ of TL(O), let cl()) be the set of all subformulas of (including & itself).
Construct DFA Ma (2cl(a), L d, F), where
{x E cl( c x
(19)
F = V S cl(
/ E }
(20)
8 0) fx cl(0) v 4
(21)
where the relation v 3 X. which intuitively means that if string satisfies exactly the formulas in Vr then wo satisfies X. is defined as follows:
V - o' iffo=d
(22a)
V XI X2 iff X1 and v 9 X2
(22b)
V 4 - iff not v +x x
(22c)
V 4 if
(22d)
v - Hx ift Hx V and v 9 x
(22e)
- X1 X2 iff (x X2 E & and S x1) or - X2-
(22f)
Claim B.3. For any E E" if (x cl(e) w = then v 3 X = wa F X-
Proof. By induction on the structure of x. Note by definition that E v + w |
V -
(22g)
we } o'.
V 9 X1
V _ X1 and L 2 X2
X2
ind. hyp
wa - X1 and wo - X2
wa - XI X2-
(22c)
not V + X
X
ind. hyp
not wo }
(1
wo } -X
V
- Yx
X E V
1 } X
(1le)
wa } Yx.
VT Hx
(22c)
Hx E v and v - X
ind. hyp.
+= Hx and wo } X
(110
wa } H.
V 4 X1
S X2
(220
(x1 S x2 E v and v S x1) or v S x2
hyp. (w - X1 S X2 and wo F X1) or wo } X2
(1ig)
wo } x1 S2.
Claim B.4. For any w. 8(1, w)
tx E cl()) w x
Proof. By induction on the length of w.
Base case: 5(1, = = l x).
Inductive step: Assume that 5(1, w) = {x w F x] = V. Then
5(1, w) = 5(5((, w),
5(V,o) σ)
= (xx | 10 - x}
(x wo x).
17

---

Published as a conference paper at ICLR 2026
Claim B.5. Mg defines the same language Ø.
Proof. ò(l, w) E F if and only if Φ E {x w x3 if and only if w } Φ.
Then make every co-accessible state (every state that has a path an accept state) into an accept state. Call this new DFA M' with accept states F`. This DFA recognizes the prefix language of Ma- Finally, construct the formula
(r)
V DEF
A XEW
Axa
x
A
X
xEcl(d)
Note that prefix never translates temporal operator into another temporal operator, so translates formulas of TL[O] into formulas of TL(O) for any O.
Claim B.6. The formula prcfix(o) defines the same language as M
Proof. Since we only changed non-accept states to accept states, Clm. B.4 still applies to M' and ø
L(M')
8(1, w) E F'
(x cl(0)
w w==xx F
Clm. B.4
for some V E F' v F
for some V E F F A
XA
A XEC((N)
X
xEW
- w
V DEF
Xm
XM
XEW
xEcl(e))
This completes the proof of Lem. B.2.
B.3 RELATIONSHIP BETWEEN CLASSIFIERS AND AUTOREGRESSORS
Theorem 5.6. For any set of operators O S H,,:
(a) For any nonempty language defined by Goolean-weighte TL(O) classifier, there exists Boolean-weighted TL(O) autoregressor defining the same language L.
(b) For any language L defined by a Boolean- weighted TL(O) autoregressor, there exists Boolean-weighted TL(O (Y, H}] classifier defining the same language L.
Proof. (a) A Boolean- TL(O) classifier is defined by tuple of formulas + (Ø11 dm) and an output function c: Bm - B. We may think of c as a Boolean combination of its arguments, and substitute the o; into it to obtain single formula c(h1.-.. ... Dm.). Then define trivial output function e' c(hh) = h, so that the classifier (ø) e') defines the same language as (Φ,c)
Define
6 next, (prefix(o))
for a E E
(23)
&EOS á.
(24)
Then the tuple of formulas sive output function
Φ' (Øo ) (Enss defines state encoder. We define the autoregres-
a: B - 11
(25)
a(h)(o) { hr if any entry of h is true if all entries of are false.
(26)
vector whose entries are all false is unreachable, so does not matter what we set a(h) to, but it must satisfy θ a())(a) = 1 (Eq. (7)), that is, the entries of a(h) cannot all be false.
18

---

Published as a conference paper at ICLR 2026
The autoregressor A (Φ', a) defines L, because for any L with length n, we have
Pra(w) = X
Pra(w; wes) @ PrA w)
(27)
1=1
A {w<r next (prefix(o)) A <I o}
(28)
A (wgi = prefix(o)) A (I + o}
(29)
i=1
I (wggv - o for some f) All = o}
(30)
==1
(31)
On the other hand, for any w & I, let the greatest integer such that w<x E T. for some u. (We know that k exists because I, is nonempty by assumption.) Then we have that
weR V next (prefix(o)). but wes -or nexty, (prefix(o)). So (ww w=*) = L, and therefore PLA Pra(w) = L.
remains to verify that A satisfies Eq. (6). For any u Σ*, we want to show that
|u]
- Pr u)
+
uv uv<)) (FAS uv) PrA
(32)
In the Boolean semiring, it suffices to show that at least one term of this summation is true.
If there e such that ue E L,, then the corresponding term of the summation is
A
I (uv F next,,, (prefix()))) A fuv } o}
(33)
[aa] Il (uoge } prefix(0)) A au
(34)
dad TI (unggw - Φ for some u/
AI [
(35)
(36)
If there is no such v. then for all a, we have uo ff prefix(o), so u H next, (prefixx))) moreover, f ø. Let h (u))) be the state after reading u. All entries of h are false, which makes (for example) (EOS) true, so the v e term of the summation in Eq. (32) is true.
(b) Let A = ( a) be a [L autoregressor, where & (o:)
Define
Φn = A + hi)
for E m
6. A (ón + a(h)(o))
for in EU (BOS).
Intuitively, da is true whenever the state encoder in state and do true whenever the state encoder is in state in which predicts
Then, define
0' = H V (Y ^o
sEEU(LoS}
and let c(h) h, so that the classifier
C (Ø), e) defines the same language A.
n
19

---

Published as a conference paper at ICLR 2026
B.4 PROOF OF PROP. 5.7
Proposition 5.7. (a) There does not exist a transformation prefix' such that prefix (6) is con- structible in polynomial time (in (b)) and satisfies Eq. (18) for every formula HH, Y). unless P = PSPACE.
(b) Similarly for H unless P NP.
(c) Similarly for ] unless NP.
Proof. (a) Suppose that prefix' exists. For any formula of TL(H, Y], we can whether ó is satisfiable by constructing prefix (6) in polynomial time (by assumption) and then testing whether c = prefix (6)), which can also be done in polynomial time, as shown by Fionda and Greco (2016, Thm. 8). (They assume formulas in negation normal form, but it is easy to generalize their result to formulas not negation normal form.) But satisfiability TL Y| PSPACE-complete (Giacomo and Vardi, 2013; Fionda and Greco, 2016), this would imply P PSPACE.
(b) Similarly, satisfiability in [L is -P-copllete (Fionda and Greco, 2016), so the existence of polynomial-time prefix' would imply P NP.
(c) Same as the previous case.
C NONDETERMINISTIC FINITE AUTOMATA
We give single definition of weighted NEAs instead of factoring them into unweighted NEAs and autoregressive output functions.
Definition C.1 (Weighted Nondeterministic Finite Automaton). weighted nondeterministic finite automaton is tuple M = (E., Q, (,),, where
V is an alphabet
Q is a finite set of states
8: Q x xxxx== + K is transition function
Q the initial state
Q K. is the accept function.
We extend 8 to 8" Qx Ex Xxx K.
8 (g (,) =
8* (0)
# g
(41, ow, 42)
+
8(g1, 0, q) @ 8" w. (2).
EEQ
Then M accepts with weight k iff
k:
(1, w. 92) & w(g2).
Definition C.2. We say that an NFA with transition function 8 is counter-free there exists some such that for all states qı, and all strings w, we have 8 (q1, w²,q2) .22)) = (q1, kk++1 -2)).
The equivalence between counter-free free NFAs and DFAs well-known (e.g. McNaughton and Papert, 1971, Chapter 5, Exercise 15), but we spell out the proof here using our definitions.
Proposition C.1. With Boolean weights, counter-free NFAs and counter-free DFAs are equivalent.
Proof. First, any Boolean-wee Boolean-weightee counter free NEA M = (E, Q, l, (. can be converted into equivalent counter-free DFA M' (,, Q' (2,8',)) together with classifier output function
20

---

Published as a conference paper at ICLR 2026
w': Q' - B. This is done by the standard construction (Sipser, 2013), letting Q' 2 and defining (q. w) = {r q E 9.8* w; = 1), L' = {c), and w (q) + qEq w(q). Then
8 (7, w²) {r 3q E q.O" (g, w", ,r) 1 {r 3g q.6" (q. wht .)) 1] 8 (7, w 2)). Thus, M' is also counter-free. The other direction trivial.
A weighted NFA determinizable every pair states which are siblings (can be reached by the same string) are also twins (all cycles by the same string have the same weight) (Mohri, 1997). The automaton Fig. 2c is counter-free, but not determinizable, because 91 and 92 are siblings (both a/2
reachable by a) but not twins (the a-labeled cycles a/2, 41 and 92 42 on the two states have different weights).
D INEXPRESSIBILITY OF (aab)*
Proposition 5.9. The language (aab)* not definable by any TL(H) classifter or autoregressor.
We actually prove a slightly stronger statement. Define the Y-depth of formula be the number of nested Y operators in Φ. Then we will prove that (aab)* is not definable by any formula of TLJH, Y] with Y-depth 1. Since the conversion from an autoregressor to a classifier (Thm. 5.6(b)) adds a single Y, we will conclude that (aab)" is not definable by any TL(H] autoregressor.
Lemma D.1. For any language (w2, Wa) ... (Wa-1, w,) [Wn, BOS) w L}. á a formula of TL[H, YJ with Y- depth 1, then there is a formula noy (0) of TL(H] over (EU {BOS)) x (E {EOS}) such that [(noy(o)) n Bigram(E") (E*) Bigram(
over Σ, define Bigram(L) = {(BOS, (1os,w1) (w1, w2)
Proof. Define the transformation noy, which pushes Y down to the atomic formulas, then modifies the atomic formulas to operate on bigrams.
noy(=p) -noy(v)
noy ((())) -noy(Y
(ty(th A 2/2) = noy(4/) A noy(v2)
Y (th A v22)) = noy( (Y))) A noy (Y))))
noy (Hw) (n))((W))
noy Y (H))) H((oy(( YT))
noy(o) V
(d'
noy(Yo)
V
(a,
(BoS)
d'EDU(EOS}
noy(BoS) = BOS
noy(Y BOS) =
V
(BOS, o').
Then, to prove that (aab)* is not definable TL(H, YJ with Yddepth suppose definable by 6. By Lem. D.I, there is formula noy( of [H] such that
(BOS, a) (a, (a, (6, EOS) E [(noy(d) n Bigram(E*). But (o)) must be stutter-invarian (Peled and Wilke, 1997), so we also have
(Bos,a) (a, a) (a, a) (a, (b, BOS) L(noy(o)) Bigram(E") But this is not in Bigram((aab)" which is contradiction.
21


Reviews:
[{"review_id": "fpKZ0TOj6r", "reviewer": "Reviewer_uL8H", "summary": "This paper presents a number of theoretical results concerning the expressivity of Transformer models, in particular in relation with counter-free, weighted Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA). The central innovation consists in considering a setup that is closer to real-world usage of transformer models. In fact, while the results are still largely limited to Unique Hard Attention Transformers (UHAT), but the authors consider their use a autoregressive token generator (language models), rather than just a Boolean classifier (for language recognition). The proof techniques rely on establishing a mapping between UHAT and Linear Temporal Logic, and then proving results for LTL. The paper shows that, while some equivalences established for the Boolean classifier setting extend to the autoregressive one, other equivalences instead break.", "questions": "* How challenging would it be, in your estimate, to adapt your analysis to SMATs?\n* The subsets of LTL that cause the equivalence to break appear to be linked to specific operators: does that provide insights in terms of either expressiveness of complexity?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I should start by cautioning that my expertise with the topics discussed here is limited, though I agree that understanding the expressivity of transformer models is an important research direction, given their role in powering LLMs and other modern AI advancements, even close to a decade after their initial introduction.\n\nIn my opinion, the strongest merit of the work is that of showing how results obtained in the Boolean classifier setup do not necessarily port to the autoregressive setup, which is indeed closer to how transformers are used, at least in LLMs. A natural next step would consist in applying the same treatment to SoftMax Attention Transformers.", "weaknesses": "While the main result is in my opinion that of showing a discrepancy between the Boolean classifier and autoregressive setup, most of the paper is devoted to proving that many equivalence results hold in both setting, thus somewhat reducing the novelty of most contributions in the work. The broke equivalence also seems to apply rather peculiar configurations (subsets of LTL).\n\nAdditionally, while considering the autoregressive setup is a step toward making the analysis more practically relevant, the work still introduces several simplifications over transformers as they are actually employed in the real world.\n\nA few minor points:\n\n* Some acronyms are introduced considerably later than when they are used, which decreases readability\n* At lines 119-124, it would be worth point out the connection between normalized weighted languages and discrete probability distributions\n* While definition 4.2 considers multiple possible suffixes, several sections in the paper appear to focus on estimating just the next token distribution, which creates confusion while reading", "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": "", "extra_scores": {}}, {"review_id": "YRZwADWByv", "reviewer": "Reviewer_A2Nv", "summary": "This work studies the expressive capacity of Transformers when used as probabilistic language models rather than classifiers. To do so, the authors analyze models along 2 axes: 1) Classifiers vs Autoregressors 2) Boolean weights vs (positive) Real-valued weights. The authors show the following:\n- UHATs, LTL and cfDFAs have equivalent state encoders (Thm 6.1) They use this to show that UHATs, LTLs and cfDFAs as classifiers (or autoregressors) define the same weighted language (Corollary 6.1)\n- LTL classifiers can only output finitely many distinct weight values (Prop 6.1). This implies that LTL classifiers cannot express the language $(\\frac{1}{2} a)^*$, which can be expressed by autoregressors (Corollary 6.2).\n- LTL classifiers and autoregressors are equivalent (for the right subsets of operators) (Thm 6.2)\n- In the case of autoregressors, cfNFAs are more expressive than cfDFAs (Prop 6.2)\n- Boolean autoregressors are more expressive than classifiers when key operators are missing (Prop. 6.3)\n- The expressivity gain of autoregression is limited; $(aab)^*$ is not definable by an LTL regressor (Prop 6.4 & Thm 6.3)\n\nI think this is a good paper with solid theoretical contributions. However, I find the style in which it is written makes it hard to quickly extract the main insights and results. I have given a 6 and will increase my score to an 8 if the authors address points 3, 4 and 7 in the Questions/Comments section.", "questions": "1. [1] and [2] are highly relevant and are not cited in the related works. They investigate related topics namely how Transformers can express weighted/probabilistic automata/grammars. The latter paper also works on a notion quite similar to what you define as \"State Encoders\" through a notion they define as \"Simulation\".\n2. Do the authors see any relationship between their work and work on \"Generation in the limit\"[3]? This could equally be an interesting direction for discussion.\n3. Could the authors put a section \"Contributions\" with bullet points or something similar in the introduction? It was hard to parse what was done in the paper vs previous work when reading.\n4. It would be beneficial to clarity to add brief proof sketches in the main text for (at least) the most technical theorems instead of simply deferring to the appendix.\n5. I quite like Figure 1 and think it does a good job summarizing the results. However, the upwards arrows are hard to parse in terms of direction of inclusion, it was not immediately obvious for me what it meant. I feel putting a $\\subseteq$ or similar might be clearer.\n6. I think it could also be helpful to have a table summarizing the main results based on assumptions made, e.g. with columns \"Thm/Prop number\" \"Semiring\" \"Model Type\" \"Main Finding\"\n7. Could the authors add a section discussing implications of their results to practice and to specific task families (as mentioned in the \"Weaknesses\" section)?\n\n\n[1] Zhao, H., Panigrahi, A., Ge, R., & Arora, S. (2023). Do transformers parse while predicting the masked word?. arXiv preprint arXiv:2303.08117.\n\n[2] Rizvi-Martel, M., Lizaire, M., Lacroce, C., & Rabusseau, G. (2024, April). Simulating weighted automata over sequences and trees with transformers. In International Conference on Artificial Intelligence and Statistics (pp. 2368-2376). PMLR.\n\n[3] Kleinberg, J., & Mullainathan, S. (2024). Language generation in the limit. Advances in Neural Information Processing Systems, 37, 66058-66079.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Angle is novel and interesting. I agree with the authors that there is a lack of literature on the topic of language *modelling* with Transformers.\n- This work improves our understanding of the interplay of expressive power between i) Boolean and Real-valued models and ii) classifier and autoregressive models. Given the equivalencies drawn by the authors, the theoretical results have deep implications about many families of models.\n- The authors provide extremely rigorous proofs and reductions. From a technical perspective. The theoretical approach taken is non-trivial and is in itself a significant contribution to theoretical research. Although I am knowledgeable about the Transformer expressivity literature, I am not well-versed in temporal logic, thus I was not able to fully check all the proofs pertaining to this in detail.", "weaknesses": "- Although complete and precise in its writing style, I find the paper is very dense and not written in a way where key insights are easy to find/extract. See comments for actionable feedback.\n- The paper has no experimental validation of theoretical claims it makes. It would be nice to at least have minimal experiments to support the results.\n- This work makes few connections to practical settings, such as how their claims might account for empirical shortcomings of LLMs, and it does not discuss the implications of their results for well-known algorithmic tasks. Stronger statements of the form “UHAT Autoregressors belong to class X and therefore cannot perform task Y from a broader class” could improve the paper.", "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": "", "extra_scores": {}}, {"review_id": "HwfZoTbKBE", "reviewer": "Reviewer_DAYT", "summary": "This paper studies the expressive power of transformers as probabilistic autoregressive models in the context of formal language theory. Existing theoretical work mostly focuses on transformers as language recognizers (Boolean setting). Here, the authors analyze the probability distributions computed by hard-attention transformers when used as language models, providing equivalence results and separation results between Boolean classifiers, probabilistic classifiers, and probabilistic autoregressors. The study also connects these models with temporal logics and weighted automata, clarifying how expressivity shifts across these settings.\nThe paper is rigorous, well-structured, and contributes to closing a gap in theoretical understanding of transformer expressivity in autoregressive scenarios.", "questions": "I do not have any particular questions for the authors.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Tightly written theoretical work with clear formal contributions.\n* Addresses a meaningful gap in theory: expressive power of transformers as generative language models.\n* Strong formal rigor, with proofs and precise definitions throughout the paper.", "weaknesses": "* **Purely theoretical:** While the theoretical contributions are solid, there are no experimental results nor concrete applied examples to illustrate relevance for real-world transformer LMs. Given the conference venue, this limits perceived impact.\n* **Accessibility:** The paper assumes familiarity with temporal logics, weighted automata, and semirings. This is appropriate for a specialized logic or theoretical CS audience, but is demanding for the general machine-learning readership at ICLR.\n\nMinor Comments:\n* There are small repetitions in early sections (e.g., “we then” in lines ~77-82, “language” in lines ~90-93) that make the text slightly repetitive.\n* The notion of “state” is only clarified around Section 4-5. Since “state encoder” is central, I suggest introducing more intuitively what a “state” represents earlier in the introduction.\n* Typo in Section 6.1: $\\tau_1$ should be $\\tau_2$.", "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": "", "extra_scores": {}}, {"review_id": "kUqIHeBukk", "reviewer": "Reviewer_hwiM", "summary": "The paper advances the theoretical study of the expressivity of transformer language models beyond Boolean recognizers, by characterizing their expressivity as probabilistic, autoregressors. The paper focuses on Unique-Hard Attention Transformers (UHATs) and connects them with Linear Temporal Logic (LTL) and counter-free Deterministic Finite Automata (cfDFA) paradigms. Overall, the paper proposes several expressivity results for these paradigms, characterizing when different modeling choices (classifier vs. autoregressive paradigms, Boolean vs. real semirings) do or do not change the set of weighted languages a model can represent.", "questions": "1. Which results extend to soft attention? Similarly, which are the implications of positional embeddings? I would recommend a discussion on these matters.\n\n\n2. Related to my previous point, recent works show that hard attention can be simulated using soft attention through temperature scaling, e.g., see (Yang et al, 2024). Based on this, will some of your results hold under soft attention? Can these findings bridge the results from this paper to soft-attention regimes?\n\n3. The Related Work section seems shallow in its current state. This is mostly because most of the closest works are described in Section 1. I would encourage the authors to reorganize Sections 1 and 2.\n\n\n4. Furthermore, some recent works are missing in the literature review (e.g., see the list below). Some of these missing works address similar scenarios or goals. For example, (Yang et al, 2024) also examines several subclasses of languages recognized by hard-attention transformers, which can be defined in variants of linear temporal logic. Please clarify the similarities or differences with these works.\n \n- Yang, A., Strobl, L., Chiang, D., & Angluin, D. (2024). Simulating hard attention using soft attention. arXiv preprint arXiv:2412.09925.\n\n\n- Hao, Y., Angluin, D., & Frank, R. (2022). Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10, 800-810.\n\n- Barceló, P., Kozachinskiy, A., Lin, A. W., & Podolskii, V. (2023). Logical languages accepted by transformer encoders with hard attention. ICLR 2024.\n\n\n\n\n5. Please define the acronym UHAT as “unique-hard attention transformers” in Page 1, for the sake of clarity to non-familiar readers.\n\n\n6. Relevant results from these works focus on counter-free automata. I wonder whether this limits impact on certain cases that exhibit periodicity. A brief discussion of what is left outside the counter-free setting and whether partial extensions or approximations are possible would be helpful.\n\n\n7. While the paper focuses on expressivity results, can something be said about “learnability” (i.e., sample complexity, efficiency…)?  \n\n\n8. Sections 6.2 and 6.3 lack explicit UHAT results. I believe that the paper might benefit from a more clear discussion on how those results contribute to the study of UHAT expressivity.\n\n\n9. Please include a forward-looking discussion of open problems and next steps.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The theoretical results are meaningful and timely, which advance the theoretical understanding of the expressivity of transformer-based models. \n\n\n2. In my view, the main strength of the paper is its focus on the probabilistic autoregressive regime, which is more aligned with how language models are used in practice, and thus represents a more meaningful case of study in comparison to previous works.  \n\n\n3. The paper characterizes equivalences in terms of language recognition of UHATs with known classic models (LTL, DFA…). Furthermore, describe different levels of expressivity under different scenarios or configurations.", "weaknesses": "1. These results hold for unique-hard attention with no position embeddings. This diverges from common configurations of language models (which include soft attention and positional encodings). Furthermore, previous works such as (Li and Cotterell, 2025) focus on soft attention, resulting in a less-idealized setup (closer to real-world transformers). I believe the paper would significantly benefit from a discussion on which results will hold or not (and why) under these assumptions.\n\n\n2. Some results are somewhat incremental, based mostly on the results of (Yang et al., 2024) or (Li and Cotterell, 2025). While I value the theoretical results, I believe that this limits the contribution of this particular work. \n\n\n3. While the paper adequately describes its goals in Section 1, its novelty and the main contributions are unclear or hard to follow. I would recommend the authors to reinforce this part, in order to emphasize which are the novel results / extensions of this particular work (with respect to previous related works), and the relevance of its contributions.\n\n\n4. The paper lacks a discussion of potential future research directions building on these findings.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)