Tighter Bounds on the Expressivity of Transformer Encoders

David ChiangPeter CholakAnand Pillay

article2023ICML93 citations

Establishes tight expressivity bounds for transformer encoders by proving that a specific variant of first-order logic with counting quantifiers acts simultaneously as an upper bound for fixed-precision encoders and a lower bound for standard encoders.

Listen

Modern natural language processing relies heavily on transformer neural networks, yet theoretical understanding of what these architectures can and cannot compute remains incomplete. Prior research established broad outer bounds, showing that transformer encoders can simulate simple counting mechanisms while being constrained within general circuit complexity classes. However, these boundaries left a significant gap, making it difficult for researchers and practitioners to predict the fundamental capabilities and algorithmic limitations of transformer-based systems.

The article establishes tight, counterbalance mathematical bounds on the expressivity of transformer encoders by mapping their computing capabilities directly to a specific formal system: first-order logic with counting quantifiers and modular position predicates, designated as FOC[+; MOD]. The authors demonstrate that this logic serves simultaneously as an upper bound for practical, fixed-precision transformer encoders and as a lower bound for general transformer encoders.

To establish these bounds, the authors employed formal mathematical and theoretical computer science methods. They proved a normal form theorem for FOC[+; MOD] that separates position properties from arithmetic counts. For the upper bound, they simulated the components of fixed-precision transformers—such as word embeddings, periodic positional encodings, feed-forward networks, and self-attention averaging—directly within the logic. For the lower bound, they constructed explicit transformer encoders with rational weights that evaluate positional predicates, aggregate occurrences using uniform self-attention, and verify linear constraints via feed-forward layers, extending the proof to accommodate standard layer normalization.

The analysis yielded three core findings. First, practical fixed-precision transformer encoders are strictly bounded by FOC[+; MOD], demonstrating that they are less powerful than previously conjectured and cannot recognize certain structured patterns (such as strings of identical counts of zeros followed by ones). Second, standard transformer encoders can express any property formulable in FOC[+; MOD], proving that this logic contains no non-transformer-like behavior. Third, this logical framework strictly refines prior work, providing a strictly tighter upper bound than general circuit complexity classes (uniform TC0) and a strictly tighter lower bound than simplified stateless counter machines.

These findings imply that transformer encoders excel primarily at computing global aggregate counts and periodic positional patterns, but they possess inherent structural limitations when resolving strict sequential orderings without causal masking or specialized positional mechanisms. For engineering and AI architecture teams, this formalization clarifies which sequence-processing tasks can be reliably solved by standard transformer encoders without requiring empirical trial-and-error, thereby mitigating the risk of misapplying standard encoders to fundamentally incompatible tasks.

Moving forward, researchers and system designers should investigate architectural extensions—such as relative or rational-position representations (e.g., position-to-length ratios)—that bridge the gap between counting and sequential order. Furthermore, research should focus on obtaining an exact, complete characterization of unrestricted rational-weight transformers and extending this formal logical framework to include causal masking and full encoder-decoder architectures.

These conclusions are established with high theoretical confidence under explicit formal conditions: the upper bound assumes fixed-precision numerical representations with bounded activations, while the lower bound assumes rational-frequency positional encodings and rational network weights. Readers should exercise caution when extrapolating these results to generative autoregressive decoders or multi-step reasoning systems, as unmasked encoders represent single-step classification capabilities rather than iterative computation.

University of Notre Dame encoders encoder-decoder transformer encoders expressivity bounds monadic first-order logic

arXiv: 2301.10743

Paper: Attention Is All You Need, Ashish Vaswani et al. (2017). Introduces the foundational self-attention and Transformer encoder architecture whose theoretical expressivity and circuit complexity bounds are characterized in the source.
Paper: Deep Sets, Manzil Zaheer et al. (2017). Provides the foundational theoretical framework for permutation-equivariant and permutation-invariant operations on sets that underlies formal analysis of attention mechanisms.

Paper: The Topological Trouble With Transformers, Michael C. Mozer et al. (2026). Investigates how the expressivity constraints of feedforward Transformer encoders manifest as topological state-tracking limitations over multi-step tasks.
Paper: Fixed-Point Reasoners: Stable and Adaptive Deep Looped Transformers, Sajad Movahedi et al. (2026). Extends standard bounded-depth Transformer expressivity to arbitrary multi-step reasoning by incorporating adaptive looping and fixed-point state iterations.

Cover for Tighter Bounds on the Expressivity of Transformer Encoders

Abstract

Characterizing neural networks in terms of better-understood formal systems has the potential to yield new insights into the power and limitations of these networks. Doing so for transformers remains an active area of research. Bhattamishra and others have shown that transformer encoders are at least as expressive as a certain kind of counter machine, while Merrill and Sabharwal have shown that fixed-precision transformer encoders recognize only languages in uniform TC0. We connect and strengthen these results by identifying a variant of first-order logic with counting quantifiers that is simultaneously an upper bound for fixed-precision transformer encoders and a lower bound for transformer encoders. This brings us much closer than before to an exact characterization of the languages that transformer encoders recognize.

Topics

encoders encoder-decoder

Keywords

transformer encoders expressivity bounds monadic first-order logic uniform AC0 uniform TC0 stateless counter machines positional encoding transformer classifiers finite automata layer normalization

1. Introduction
2. Preliminaries
3. Transformers
3.1. Input layer
3.2. Hidden layers
3.3. Stacks, encoders and classifiers
4. First-Order Logic with Counting Quantifiers
4.1. Examples
4.2. Definition
4.3. Normal form
5. From Transformers to FOC[≥,;,MOD[2]]
5.1. Representing numbers
5.2. Input layer
5.3. Hidden layers
5.4. Output layer
5.5. Complexity analysis
5.6. Relationship to uniform TC0
6. From FOC[≥,;,MOD[2]] to Transformers
6.1. Computing the k-th attention head
6.2. Counting quantifiers
6.3. Computing j
6.4. Relationship to counter machines
7. Related Work
7.1. Upper bounds
7.2. Lower bounds
8. Discussion
8.1. Relationship with other complexity classes
8.2. Transformer variants
8.3. Next steps
Acknowledgements
References
A. Proof of Theorem 1
B. Expressing averages in FOC[≥,;,MOD[2]]
C. Proofs for Section 6 (From FOC[≥,;,MOD[2]] to Transformers)
C.1. Proof of Lemma 7
C.2. Proof of Lemma 6
C.3. Proof of Lemma 8
D. Layer Normalization
D.1. Definition
D.2. Modified proof of Theorem 2
D.3. Modified proof of Theorem 5

Knowls

Knowl 1 — Upper Bound on the Expressivity of Fixed-Precision Transformer Encoders
theoretical result
Every formal language recognizable by a fixed-precision transformer encoder classifier is definable by a sentence of the first-order logic $\text{FOC}[+; \text{MOD}]$ .

In this setting, a fixed-precision transformer uses real values represented in fixed-point format with a fixed number of integer bits $r$ and fractional bits $s$ (belonging to $\mathbb{F}_{r,s} = \{ i / 2^s \mid -2^{r+s} \le i < 2^{r+s}, i \in \mathbb{Z} \}$ ), sinusoidal positional encodings with rational frequencies, standard multi-head self-attention with softmax, position-wise ReLU feed-forward layers, residual connections, and an optional layer normalization. The translation accommodates rounding schemes where attention context averages are computed and rounded into fixed-point representations.
Knowl 2 — Lower Bound on the Expressivity of Transformer Encoders
theoretical result
Every formal language definable by a sentence in $\text{FOC}[+; \text{MOD}]$ is recognizable by an arbitrary-precision transformer encoder classifier.

The construction builds a transformer classifier consisting of:
1. Lower layers that evaluate quantifier-free positional formulas $\psi_i(p)$ at each position $p$ using sinusoidal positional encodings with rational frequencies and ReLU feed-forward networks (FFNs);
2. An attention layer using uniform self-attention weights to compute normalized counts $\frac{x_i}{n'}$ of the positions satisfying each $\psi_i(p)$ , where $n' = n + 1$ is the input length including the special $\text{CLS}$ token;
3. Upper feed-forward layers that compute the truth value of a quantifier-free linear constraint formula $\chi(x_1, \dots, x_k)$ on the counts, mapped to a final classification output at the $\text{CLS}$ token position.
This construction holds both for transformers with and without layer normalization.
Knowl 3 — Normal Form for FOC[+; MOD] Formulas
theoretical result
Every formula $\phi$ in the logic $\text{FOC}[+; \text{MOD}]$ is logically equivalent to a formula of the normal form:

$\phi' = \exists x_1 \dots \exists x_k \left( \bigwedge_{i=1}^k \exists^{=x_i} p.\, \psi_i(p) \land \chi(x_1, \dots, x_k) \right)$

where:
- Each $\psi_i(p)$ is a quantifier-free formula whose only free variable is the position variable $p$ , containing no free count variables.
- $\chi(x_1, \dots, x_k)$ is a quantifier-free formula over the rational count variables $x_1, \dots, x_k$ , containing no position variables.
- $\exists^{=x_i} p.\, \psi_i(p)$ is a counting quantifier asserting that the number of positions $p \in \{1, \dots, n\}$ for which $\psi_i(p)$ holds is exactly $x_i$ .
Knowl 4 — First-Order Logic with Counting Quantifiers and Modular Predicates (FOC[+; MOD])
definition
Given a finite alphabet $\Sigma$ , $\text{FOC}[+; \text{MOD}]$ is a two-sorted first-order logic evaluated over finite strings $w = w_1 \dots w_n \in \Sigma^*$ of length $n$ :
1. Sort of positions: Variables $p, q, \dots$ range over string indices $\{1, \dots, n\}$ .
2. Sort of counts: Variables $x, y, z, \dots$ range over rational numbers $\mathbb{Q}$ . Count terms have the form $c_0 + c_1 x_1 + \dots + c_k x_k$ with $c_i \in \mathbb{Q}$ .
Formulas of $\text{FOC}[+; \text{MOD}]$ are defined inductively:
- Atomic constants $\top$ (true) and $\bot$ (false).
- Symbol predicate $Q_a(p)$ for $a \in \Sigma$ , true iff $w_p = a$ .
- Modular predicate $\text{MOD}_m^r(p)$ for integers $r \ge 0$ and $m > 0$ , true iff $p \equiv r \pmod m$ .
- Linear comparisons $t_1 = t_2$ and $t_1 < t_2$ between count terms $t_1, t_2$ .
- Standard Boolean connectives: $\phi_1 \land \phi_2$ , $\phi_1 \lor \phi_2$ , $\neg \phi_1$ .
- Count quantification: $\exists x.\, \phi$ and $\forall x.\, \phi$ for count variable $x$ .
- Counting quantifier: $\exists^{=x} p.\, \phi$ , which binds the position variable $p$ and is true iff the number of positions $p \in \{1, \dots, n\}$ making $\phi$ true is exactly $x$ (leaving $x$ free).
Knowl 5 — Strict Containment of FOC[+; MOD] in Uniform TC^0
theoretical result
The class of languages definable in $\text{FOC}[+; \text{MOD}]$ is strictly contained in uniform $\text{TC}^0$ .

While every language definable in $\text{FOC}[+; \text{MOD}]$ belongs to uniform $\text{TC}^0$ , the language $L = \{0^n 1^n \mid n \ge 0\}$ is in uniform $\text{TC}^0$ but cannot be defined in $\text{FOC}[+; \text{MOD}]$ .

Because $\text{FOC}[+; \text{MOD}]$ lacks order predicates $p < q$ on positions and only provides modular predicates $\text{MOD}_m^r(p)$ , any sentence in $\text{FOC}[+; \text{MOD}]$ with maximum modulus product $M$ cannot distinguish the string $w = 0^M 1^M$ from $w' = 10^{M-1} 0 1^{M-1}$ , preventing it from enforcing ordering constraints.
Knowl 6 — Expressive Subsumption and Separation of Simplified Stateless Counter Machines
theoretical result
Every language recognized by a simplified stateless $k$ -counter machine ( $k$ -SSCM) is definable by a sentence in $\text{FOC}[+; \text{MOD}]$ , and $\text{FOC}[+; \text{MOD}]$ is strictly more expressive than SSCMs.

Specifically, the regular language $(01)^*$ is definable in $\text{FOC}[+; \text{MOD}]$ via the sentence: $\exists x.\, \left( \exists^{=x} p.\, Q_0(p) \land \exists^{=x} p.\, Q_1(p) \land \forall p.\, (\text{MOD}_2^1(p) \leftrightarrow Q_0(p)) \right)$ However, $(01)^*$ cannot be recognized by any SSCM because SSCM counter updates depend solely on symbol identities and are therefore permutation-invariant, making an SSCM incapable of distinguishing $(01)^n$ from $0^n 1^n$ .
Knowl 7 — Incomparability of FOC[+; MOD] with Regular Languages and Uniform AC^0
theoretical result
The class of languages definable in $\text{FOC}[+; \text{MOD}]$ is incomparable with both the class of regular languages and the class of languages in uniform $\text{AC}^0$ :
1. Incomparability with Regular Languages:
  - The language $\text{MAJORITY} = \{w \in \{0, 1\}^* \mid |w|_1 > |w|_0\}$ is definable in $\text{FOC}[+; \text{MOD}]$ by $\exists x. \exists y.\, (\exists^{=x} p.\, Q_0(p) \land \exists^{=y} p.\, Q_1(p) \land y > x)$ , but is not regular.
  - The language $0^*1^*$ is regular, but cannot be defined in $\text{FOC}[+; \text{MOD}]$ .
2. Incomparability with Uniform $\text{AC}^0$ :
  - $\text{MAJORITY}$ is definable in $\text{FOC}[+; \text{MOD}]$ but does not belong to $\text{AC}^0$ .
  - $0^*1^*$ is definable in uniform $\text{AC}^0$ (via first-order logic with BIT and order) but is not definable in $\text{FOC}[+; \text{MOD}]$ .
Knowl 8 — Transformer Encoder Classifier Architecture
model/method
A transformer encoder classifier maps an input string $w = w_1 \dots w_n \in \Sigma^*$ to an acceptance probability using width $d$ , key dimension $d_K$ , hidden dimension $d_{\text{FF}}$ , and $L$ layers:
1. Input Encoding: Prepends a special token $w_0 = \text{CLS}$ to yield sequence length $n' = n + 1$ . The activation matrix $A^{(0)} \in \mathbb{R}^{d \times n'}$ has columns: $A^{(0)}_{*,p} = \text{WE}(w_p) + \text{PE}(p)$ where $\text{WE}: \Sigma \cup \{\text{CLS}\} \to \mathbb{R}^d$ and $\text{PE}(p) \in \mathbb{R}^d$ contains sinusoidal components $(\sin 2\pi \xi_i p, \cos 2\pi \xi_i p)^{\top}$ with rational frequencies $\xi_i \in \mathbb{Q}$ .
2. Self-Attention Sublayer: Maps activations $A \in \mathbb{R}^{d \times n'}$ to $A' \in \mathbb{R}^{d \times n'}$ with heads $h \in \{1, \dots, H\}$ : $S_{q, p} = \frac{(W^{(Q)} A_{*,q}) \cdot (W^{(K)} A_{*,p})}{\sqrt{d_K}}, \quad C_{*,q} = \frac{\sum_{p=0}^n (\exp S_{q,p}) W^{(V)} A_{*,p}}{\sum_{p=0}^n \exp S_{q,p}}$ where $W^{(Q)}, W^{(K)} \in \mathbb{R}^{d \times d_K}$ and $W^{(V)} \in \mathbb{R}^{d \times d}$ .
3. Feed-Forward Sublayer: Operates column-wise: $\text{FF}(x) = W^{(2)} \max\left(0, W^{(1)} x + b^{(1)}\right) + b^{(2)}$ with $W^{(1)} \in \mathbb{R}^{d_{\text{FF}} \times d}$ , $b^{(1)} \in \mathbb{R}^{d_{\text{FF}}}$ , $W^{(2)} \in \mathbb{R}^{d \times d_{\text{FF}}}$ , $b^{(2)} \in \mathbb{R}^d$ .
4. Layer Composition and Residuals: $A' = \sum_{h=1}^H \text{SA}^{(h)}(A) + A, \quad A'' = \text{FF}(A') + A'$
5. Classification Decision: Using encoder output $A^{(L)} = \text{Enc}(w)$ , the model computes: $\text{Cls}(w) = \text{sigmoid}\left( W [\text{Enc}(w)]_{*,0} + b \right)$ and accepts the string $w$ if and only if $\text{Cls}(w) \ge \frac{1}{2}$ .
Knowl 9 — Fixed-Precision Activation Bounds for Transformers
definition
A fixed-precision number with $r$ integer bits and $s$ fractional bits is an element of the set:

$\mathbb{F}_{r,s} = \left\{ \frac{i}{2^s} \;\middle|\; -2^{r+s} \le i < 2^{r+s}, \, i \in \mathbb{Z} \right\}$

Activations in a transformer classifier are bounded independently of sequence length $n$ under Lipschitz continuous sublayer operations, or under layer normalization $\text{LN}(x)_i = \gamma_i \frac{x_i - \bar{x}}{\sqrt{\text{Var}(x) + \epsilon}} + \beta_i$ . Even when $\epsilon = 0$ , for any vector $x \in \mathbb{R}^d$ , the normalized component satisfies:

$\left| \frac{x_i - \bar{x}}{\sqrt{\text{Var}(x)}} \right| \le \sqrt{d}$

ensuring that activations at layer $\ell$ satisfy $|A^{(\ell)}_{i, p}| < 2^r$ for a fixed constant integer bound $r$ .
Knowl 10 — Simplified Stateless Counter Machine (SSCM)
definition
A simplified stateless $k$ -counter machine ( $k$ -SSCM) is a tuple $M = (\Sigma, u, F)$ where:
- $\Sigma$ is a finite alphabet.
- $u: \Sigma \to \mathbb{Z}^k$ is a counter update function mapping symbols to integer update vectors.
- $F \in \{0, 1\}^k$ is an acceptance mask.
Given an input string $w = w_1 \dots w_n \in \Sigma^*$ , the machine computes counter configurations $c_0, c_1, \dots, c_n \in \mathbb{Z}^k$ defined by: $c_0 = \mathbf{0}, \quad c_i = c_{i-1} + u(w_i) \quad \text{for } i \in \{1, \dots, n\}$

$M$ accepts $w$ if and only if for all counter indices $j \in \{1, \dots, k\}$ : $[c_n]_j = 0 \iff F_j = 0$

Coverage note — None was omitted; all central theorems, logic characterizations, comparisons to formal classes (TC0, SSCM, regular, AC0), and definitions were captured.

References

1.Ba, J. L., Kiros, J. R., and Hinton, G. E. Layer normalization. In NIPS 2016 Deep Learning Symposium, 2016. URL https://arxiv.org/abs/1607.06450.
2.Barceló, P., Kostylev, E. V., Monet, M., Pérez, J., Reutter, J., and Silva, J.-P. The logical expressiveness of graph neural networks. In Proc. ICLR, 2020. URL https://openreview.net/pdf?id=r1lZ7AEKvB.
3.Barrington, D. A. M., Immerman, N., and Straubing, H. On uniformity within $\mathrm{NC}^{1}$ . J. Computer and System Sciences, 41(3), 1990. doi: 10.1016/0022-0000(90)90022-D.
4.Bhattamishra, S., Ahuja, K., and Goyal, N. On the ability and limitations of Transformers to recognize formal languages. In Proc. EMNLP, 2020. doi: 10.18653/v1/2020.emnlp-main.576.
5.Boolos, G. S., Burgess, J. P., and Jeffrey, R. C. Computability and Logic. Cambridge Univ. Press, 5th edition, 2007.
6.Büchi, J. R. Weak second-order arithmetic and finite automata. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 6, 1960. doi: 10.1002/malq.19600060105.
7.Chen, Y., Gilroy, S., Knight, K., and May, J. Recurrent neural networks as weighted language recognizers, 2017. URL https://arxiv.org/abs/1711.05408v1. arXiv:1711.05408v1. Earlier version of a paper presented at NAACL HLT 2018.
8.Chiang, D. and Cholak, P. Overcoming a theoretical limitation of self-attention. In Proc. ACL, 2022. doi: 10.18653/v1/2022.acl-long.527.
9.Ferrante, J. and Rackoff, C. A decision procedure for the first order theory of real addition with order. SIAM J. Computing, 4(1), March 1975. doi: 10.1137/0204006.
10.Forcada, M. L. and Carrasco, R. C. Finite-state computation in analog neural networks: Steps towards biologically plausible models? In Wermter, S., Austin, J., and Willshaw, D. (eds.), Emergent Neural Computational Architectures Based on Neuroscience: Towards Neuroscience-Inspired Computing. Springer, 2001. doi: 10.1007/3-540-44597-8_34.
11.Furst, M., Saxe, J. B., and Sipser, M. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17:13–27, 1984. doi: 10.1007/BF01744431.
12.Hahn, M. Theoretical limitations of self-attention in neural sequence models. Trans. ACL, 8, 2020. doi: 10.1162/tacl_a_00306.
13.Hao, Y., Angluin, D., and Frank, R. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Trans. ACL, 10, 2022. doi: 10.1162/tacl_a_00490.
14.Immerman, N. Descriptive Complexity. Springer, 1999.
15.Kleene, S. C. Representation of events in nerve nets and finite automata. In Shannon, C. E. and McCarthy, J. (eds.), Automata Studies, number 34 in Annals of Mathematics Studies. Princeton Univ. Press, 1956. doi: 10.1515/9781400882618-002.
16.Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. In Proc. NeurIPS, pp. 22199–22213, 2022. URL https://arxiv.org/pdf/2207.00729.pdf.
17.McCulloch, W. and Pitts, W. A logical calculus of ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5, 1943. doi: 10.1007/BF02478259.
18.Merrill, W. On the linguistic capacity of real-time counter automata, 2020. URL https://arxiv.org/abs/2004.06866. arXiv:2004.06866.
19.Merrill, W. and Sabharwal, A. Transformers can be translated to first-order logic with majority quantifiers, 2022. URL https://arxiv.org/abs/2210.02671v3. arXiv:2210.02671v3.
20.Merrill, W. and Sabharwal, A. The parallelism tradeoff: Limitations of log-precision transformers. Trans. ACL, 2023. URL https://arxiv.org/pdf/2207.00729.pdf. To appear.
21.Merrill, W., Sabharwal, A., and Smith, N. A. Saturated transformers are constant-depth threshold circuits. Trans. ACL, 10, 2022. doi: 10.1162/tacl_a_00493.
22.Nguyen, T. Q. and Salazar, J. Transformers without tears: Improving the normalization of self-attention. In Proc. International Workshop on Spoken Language Translation (IWSLT), 2019. doi: 10.5281/zenodo.3525484.
23.Pérez, J., Barceló, P., and Marinkovic, J. Attention is Turing-complete. J. Machine Learning Research, 22(75), 2021. URL https://jmlr.org/papers/v22/20-302.html.
24.Robinson, A. and Zakon, E. Elementary properties of ordered abelian groups. Trans. AMS, 96, 1960. doi: 10.1090/S0002-9947-1960-0114855-0.
25.Schwartz, R., Thomson, S., and Smith, N. A. Bridging CNNs, RNNs, and weighted finite-state machines. In Proc. ACL, 2018. doi: 10.18653/v1/P18-1028.
26.Siegelmann, H. and Sontag, E. On the computational power of neural nets. J. Computer and System Sciences, 50(1), 1995. doi: 10.1006/jcss.1995.1013.
27.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. In Proc. NeurIPS, 2017. URL https://papers.nips.cc/paper/7181-attention-is-all-you-need.
28.Wang, Q., Li, B., Xiao, T., Zhu, J., Li, C., Wong, D. F., and Chao, L. S. Learning deep Transformer models for machine translation. In Proc. ACL, 2019. doi: 10.18653/v1/P19-1176.
29.Weiss, G., Goldberg, Y., and Yahav, E. Thinking like Transformers. In Proc. ICML, 2021. URL https://proceedings.mlr.press/v139/weiss21a.html.
30.Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. Are Transformers universal approximators of sequence-to-sequence functions? In Proc. ICLR, 2020. URL https://openreview.net/pdf?id=ByxRM0Ntvr.

Citation

MLA

Chiang, D., et al. “Tighter Bounds on the Expressivity of Transformer Encoders”. International Conference on Machine Learning, vol. 202, 2023, pp. 5544–62, https://proceedings.mlr.press/v202/chiang23a.html.

APA

Chiang, D., Cholak, P., & Pillay, A. (2023). Tighter Bounds on the Expressivity of Transformer Encoders. International Conference on Machine Learning, 202, 5544–5562. https://proceedings.mlr.press/v202/chiang23a.html

Chicago

Chiang, D., P. Cholak, and A. Pillay. 2023. “Tighter Bounds on the Expressivity of Transformer Encoders”. International Conference on Machine Learning 202: 5544–62. https://proceedings.mlr.press/v202/chiang23a.html.

Harvard

Chiang, D., Cholak, P. and Pillay, A. (2023) “Tighter Bounds on the Expressivity of Transformer Encoders”, International Conference on Machine Learning. PMLR, pp. 5544–5562. Available at: https://proceedings.mlr.press/v202/chiang23a.html.

Vancouver

1. Chiang D, Cholak P, Pillay A (2023) Tighter Bounds on the Expressivity of Transformer Encoders. In: International Conference on Machine Learning. PMLR, pp 5544–5562

BibTeX

@InProceedings{pmlr-v202-chiang23a,
  title = 	 {Tighter Bounds on the Expressivity of Transformer Encoders},
  author =       {Chiang, David and Cholak, Peter and Pillay, Anand},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {5544--5562},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/chiang23a/chiang23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/chiang23a.html},
  abstract = 	 {Characterizing neural networks in terms of better-understood formal systems has the potential to yield new insights into the power and limitations of these networks. Doing so for transformers remains an active area of research. Bhattamishra and others have shown that transformer encoders are at least as expressive as a certain kind of counter machine, while Merrill and Sabharwal have shown that fixed-precision transformer encoders recognize only languages in uniform $TC^0$. We connect and strengthen these results by identifying a variant of first-order logic with counting quantifiers that is simultaneously an upper bound for fixed-precision transformer encoders and a lower bound for transformer encoders. This brings us much closer than before to an exact characterization of the languages that transformer encoders recognize.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Tighter Bounds on the Expressivity of Transformer Encoders

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Upper Bound on the Expressivity of Fixed-Precision Transformer Encoders

Knowl 2 — Lower Bound on the Expressivity of Transformer Encoders

Knowl 3 — Normal Form for FOC[+; MOD] Formulas

Knowl 4 — First-Order Logic with Counting Quantifiers and Modular Predicates (FOC[+; MOD])

Knowl 5 — Strict Containment of FOC[+; MOD] in Uniform TC^0

Knowl 6 — Expressive Subsumption and Separation of Simplified Stateless Counter Machines

Knowl 7 — Incomparability of FOC[+; MOD] with Regular Languages and Uniform AC^0

Knowl 8 — Transformer Encoder Classifier Architecture

Knowl 9 — Fixed-Precision Activation Bounds for Transformers

Knowl 10 — Simplified Stateless Counter Machine (SSCM)

References

Citation

BibTeX

Access the Paper