Transformers are Inherently Succinct

Transformer 天生具备简洁性

Pascal Bergsträßer Affiliation:  RPTU Kaiserslautern-Landau Affiliation:  Kaiserslautern, Germany Email:  bergstraesser@cs.uni-kl.de    Ryan Cotterell Affiliation:  ETH Zürich Affiliation:  Zürich, Switzerland Email:  ryan.cotterell@inf.ethz.ch    Anthony W. Lin Affiliation:  RPTU Kaiserslautern-Landau and MPI-SWS Affiliation:  Kaiserslautern, Germany Email:  lin@cs.uni-kl.de

Abstract

摘要

We propose succinctness as a measure of the expressive power of a transformer in describing a concept. To this end, we prove that transformers are highly expressive in that they can represent formal languages substantially more succinctly than standard representations of formal languages like finite automata and Linear Temporal Logic (LTL) formulas. As a by-product of this expressivity, we show that verifying properties of transformers is provably intractable (i.e. EXPSPACE-complete).

我们把简洁性（succinctness）当作衡量 Transformer 表达力的尺度。为此我们证明：Transformer 的表达力很强，描述形式语言时可以比有限自动机和线性时序逻辑（LTL）公式这类标准表示简洁得多。作为这种表达力的副产品，我们证明验证 Transformer 的性质是可证明难解的（即 ${\mathsf{EXPSPACE}}$-完全）。

1 Introduction

1 引言

Transformers (Vaswani et al. 2017) are the underlying model behind the recent success of Large Language Models (LLMs). The past few years saw a large amount of theoretical development explaining the expressive power of transformers (Strobl et al. 2024; Barceló et al. 2024; Yang et al. 2024; Hahn 2020; Pérez et al. 2021; Chiang & Cholak 2022; Jerad et al. 2025), their trainability and length generalizability (Zhou et al. 2024; Huang et al. 2025; Chiang & Cholak 2022), and the extent to which one can formally verify them (Sälzer et al. 2025). Interestingly, it is known that transformers with fixed (finite) precision (Yang et al. 2024; Barceló et al. 2024; Jerad et al. 2025; Li & Cotterell 2025) recognize a well-known subclass of regular languages called star-free languages. Fixed-precision transformers are especially pertinent to real-world transformers, which are implemented on hardware with fixed (finite) precision.

Transformer（Vaswani et al. 2017）是近年大语言模型（LLM）成功背后的基础模型。过去几年里，大量理论研究解释了 Transformer 的表达力（Strobl et al. 2024；Barceló et al. 2024；Yang et al. 2024；Hahn 2020；Pérez et al. 2021；Chiang & Cholak 2022；Jerad et al. 2025），它们的可训练性与长度泛化（Zhou et al. 2024；Huang et al. 2025；Chiang & Cholak 2022），以及在多大程度上可以对其做形式化验证（Sälzer et al. 2025）。一个有趣的事实是：固定（有限）精度的 Transformer（Yang et al. 2024；Barceló et al. 2024；Jerad et al. 2025；Li & Cotterell 2025）认出的是正则语言里一类著名的子类，即星自由语言（star-free languages）。固定精度的 Transformer 尤其贴近现实中的实现，因为真实硬件只用固定（有限）精度运算。

Star-free languages form a rather small subclass of regular languages. More precisely, a star-free regular expression allows the intersection and complementation operators instead of the Kleene star. For this reason, the regular language $a^{*}b^{*}$ is star-free because it can be defined as $\overline{\bar{\emptyset}.b.a.\bar{\emptyset}}$. On the other hand, it is known that regular languages like $(aa)^{*}$ are not star-free (cf. see (Straubing 1994)). This is in contrast to Recurrent Neural Networks (RNN), which can recognize all regular languages (Siegelmann & Sontag 1995; Merrill et al. 2020). Thus, expressivity as language recognizers per se is perhaps not the most useful criterion for an LLM architecture.

星自由语言只是正则语言里相当小的一块。更精确地说，星自由正则表达式用交与补取代克莱尼星号。因此正则语言 $a^{*}b^{*}$ 是星自由的，因为它可以写成 $\overline{\bar{\emptyset}.b.a.\bar{\emptyset}}$。另一方面，像 $(aa)^{*}$ 这样的正则语言已知不是星自由的（参见 Straubing 1994）。这与循环神经网络（RNN）形成对比：RNN 可以认出全部正则语言（Siegelmann & Sontag 1995；Merrill et al. 2020）。因此，单把“能充当怎样的语言识别器”当作标准，对 LLM 架构来说也许并不是最有用的尺度。

In this paper, we propose succinctness as an alternative angle in understanding the “expressivity” of transformers. More precisely, the succinctness of a language $L$ with respect to a class $\mathcal{C}$ of language recognizers (e.g. transformers, automata, etc.) measures the smallest (denotational) size of $T\in\mathcal{C}$ that recognizes $L$, i.e., how many symbols are used to describe $T$. Succinctness has been studied in logic in computer science (e.g. (Grohe & Schweikardt 2004; Stockmeyer 1974)) as an alternative (and more computational) measure of expressiveness, and has direct consequence in how computationally difficult it is to analyze a certain expression. For example, Linear Temporal Logic (LTL) (Pnueli 1977) is expressively equivalent to star-free regular languages (e.g. see (Libkin 2004)), as well as a subclass of deterministic finite automata called counter-free automata (McNaughton & Papert 1971). Despite this, it is known that LTL can be exponentially more succinct than finite automata (Sistla & Clarke 1985). In other words, certain concepts can be described considerably more succinctly by LTL formulas as by finite automata. This has various consequences, e.g., analyzing LTL formulas (e.g. checking whether they describe a trivial concept) is provably computationally more difficult than analyzing finite automata (Sistla & Clarke 1985).

本文提出用简洁性作为理解 Transformer“表达力”的另一条路径。更精确地说，语言 $L$ 相对于一类语言识别器 $\mathcal{C}$（例如 Transformer、自动机等）的简洁性，量的是认出 $L$ 的最小（指称）大小，也就是描述 $T\in\mathcal{C}$ 用了多少符号。简洁性在计算机科学的逻辑里已被研究过（例如 Grohe & Schweikardt 2004；Stockmeyer 1974），它是一种更偏计算的表达力尺度，并直接影响分析某个表达式有多难。例如，线性时序逻辑（LTL）（Pnueli 1977）在表达力上等价于星自由正则语言（参见 Libkin 2004），也等价于确定性有限自动机的一个子类，即无计数自动机（counter-free automata）（McNaughton & Papert 1971）。尽管如此，已知 LTL 可以比有限自动机指数级更简洁（Sistla & Clarke 1985）。换句话说，某些概念用 LTL 公式来写，可以比用有限自动机短得多。这会带来多种后果，例如分析 LTL 公式（比如判断它是否描述平凡概念）在计算上可证明比分析有限自动机更难（Sistla & Clarke 1985）。

Contributions.

Our main result can be summarized as follows:

贡献。

本文的主要结果可以概括如下：

Transformers can describe concepts extremely succinctly.

Transformer 能把概念写得极短。

More precisely, we show that transformers are exponentially more succinct than LTL and RNN (so including state-of-the-art State-Space Models (SSMs), e.g., see (Gu & Dao 2023; Merrill et al. 2024)), and doubly exponentially more succinct than finite automata. This means that, with the same descriptional size, transformers can encode complex patterns that require exponentially (resp. doubly exponentially) larger descriptional sizes for LTL and RNN (resp. automata). As a by-product of this expressivity, one may surmise that analyzing transformers must be computationally challenging. We show this to be the case. That is, verifying simple properties about transformers (e.g. whether it recognizes a trivial language) is computationally difficult: ${\mathsf{EXPSPACE}}$-complete. That is, with standard complexity-theoretic assumptions, this cannot be done in better than double exponential time.

更精确地说，我们证明 Transformer 比 LTL 和 RNN（因此也包括最先进的状态空间模型（SSM），例如参见 Gu & Dao 2023；Merrill et al. 2024）指数级更简洁，比有限自动机则双指数级更简洁。这意味着：在同样的描述大小下，Transformer 能编码的复杂模式，换成 LTL 和 RNN（或自动机）需要指数级（或双指数级）更大的描述。作为这种表达力的副产品，人们会猜想分析 Transformer 在计算上必然很有挑战。我们证明情况确实如此。也就是说，验证关于 Transformer 的简单性质（例如它是否认出平凡语言）在计算上是困难的：${\mathsf{EXPSPACE}}$-完全。在标准复杂性假设下，这做不到比双指数时间更好。

In fact, we also show matching upper bound on the succinctness gap for LTL (exponential) and automata (double exponential). That is, we provide a translation from fixed-precision transformers to exponential-sized LTL formulas. This significantly improves the previously shown doubly exponential translation by Yang et al. 2024. As a consequence, for any fixed-precision transformer, there is an LTL formula (resp. finite automaton) of (doubly) exponential size recognizing the same language.

事实上，我们也为相对于 LTL（指数）和自动机（双指数）的简洁性间隙给出了匹配的上界。也就是说，我们给出从固定精度 Transformer 到指数大小 LTL 公式的翻译。这显著改进了 Yang et al. 2024 先前给出的双指数翻译。因此，对任意固定精度 Transformer，都存在认出同一语言、大小为（双）指数的 LTL 公式（或有限自动机）。

In proving our succinctness results, we show how transformers can count from 0 up to $2^{2^{n}}$, i.e., the so-called “(doubly exponentially) large counters”. This requires a subtle encoding of large counters using attention. We then prove that the resulting languages using LTL and RNN (resp. finite automata) require exponentially (resp. doubly exponentially) larger description.

在证明简洁性结果的过程中，我们说明 Transformer 如何能从 0 数到 $2^{2^{n}}$，也就是所谓的“（双指数）大计数器”。这需要用注意力对大计数器做细致编码。随后我们证明，用 LTL 和 RNN（或有限自动机）表示由此得到的语言，需要指数级（或双指数级）更长的描述。

What assumptions do we use in our results? We assume that transformers and RNN are of a fixed (finite) precision. This assumption is faithful to real-world implementations, which use only fixed-precision arithmetics. We also use Unique-Hard Attention Transformers (UHAT), which are known to be expressively the weakest class of transformers (Hao et al. 2022), e.g., their languages are known to be in a very low complexity class $\text{AC}^{0}$, whereas other classes of transformers (e.g. average-hard attention or softmax) can recognize languages beyond $\text{AC}^{0}$ (e.g. majority). Additionally, UHATs have also been used as transformer models in theoretical works of transformers (cf. (Yang et al. 2024; Jerad et al. 2025; Strobl et al. 2024; Hao et al. 2022; Li & Cotterell 2025; Hahn 2020; Barceló et al. 2024; Bergsträßer et al. 2024)).

我们的结果用了哪些假设？我们假定 Transformer 和 RNN 都是固定（有限）精度的。这一假设忠实于现实实现，因为它们只用固定精度算术。我们还使用唯一硬注意力 Transformer（Unique-Hard Attention Transformers，UHAT），它已知是表达力最弱的一类 Transformer（Hao et al. 2022）：其语言落在很低的复杂度类 $\text{AC}^{0}$ 里，而其他类的 Transformer（例如平均硬注意力或 softmax）可以认出超出 $\text{AC}^{0}$ 的语言（例如多数）。此外，UHAT 也已被用作 Transformer 理论工作中的模型（参见 Yang et al. 2024；Jerad et al. 2025；Strobl et al. 2024；Hao et al. 2022；Li & Cotterell 2025；Hahn 2020；Barceló et al. 2024；Bergsträßer et al. 2024）。

Organization.

We recall some formal concepts (transformers, automata, and logic) in Section 2. We show in Section 3 how transformers can encode an exponential tiling problem. We show in Section 4 how this implies succinctness of UHATs relative to other representations. Applications of our results for reasoning about transformers are discussed in Section 5. We conclude the paper in Section 6.

结构安排。

我们在第 2 节回顾一些形式概念（Transformer、自动机和逻辑）。我们在第 3 节说明 Transformer 如何编码一个指数铺砖问题。我们在第 4 节说明这如何蕴含 UHAT 相对于其他表示的简洁性。关于用这些结果推理 Transformer 的应用见第 5 节。我们在第 6 节结束全文。

2 Preliminaries

2 预备知识

We often denote vectors by boldface letters and for a vector $\bm{v}=(v_{1},\dots,v_{d})$ we write $\bm{v}[i,j]:=(v_{i},\dots,v_{j})$ for all $1\leq i\leq j\leq d$ and if $i=j$, we simply write $\bm{v}(i)$. We also write $\bm{n}$ for a number $n$ to denote a vector $(n,\dots,n)$ of appropriate dimension.

我们常用粗体字母表示向量；对向量 $\bm{v}=(v_{1},\dots,v_{d})$，对所有 $1\leq i\leq j\leq d$ 写 $\bm{v}[i,j]:=(v_{i},\dots,v_{j})$；若 $i=j$，则简写为 $\bm{v}(i)$。我们也用粗体 $\bm{n}$ 表示由数字 $n$ 构成的、维数合适的常向量 $(n,\dots,n)$。

An alphabet is a finite set $\Sigma$ of symbols (a.k.a. tokens). We write $\Sigma^{*}$ for the set of all words (a.k.a. sequences, strings) of the form $a_{1}\dots a_{n}$, where $n\geq 0$ and $a_{i}\in\Sigma$ for all $i\in[1,n]$. A language is a subset $L\subseteq\Sigma^{*}$. We assume familiarity with basic concepts in formal language theory and complexity theory (see e.g. (Kozen 1997; Sipser 1997)). In particular, we will deal with finite automata. We will also use the following complexity classes:

字母表是由符号（也称token）组成的有限集 $\Sigma$。我们把形如 $a_{1}\dots a_{n}$ 的全部词（也称序列、字符串）记为 $\Sigma^{*}$，其中 $n\geq 0$ 且对所有 $i\in[1,n]$ 有 $a_{i}\in\Sigma$。语言是子集 $L\subseteq\Sigma^{*}$。我们假定读者熟悉形式语言理论与复杂性理论的基本概念（例如参见 Kozen 1997；Sipser 1997）。尤其会用到有限自动机。我们还会用到下列复杂性类：

$${\mathsf{P}}\subseteq{\mathsf{NP}}\subseteq{\mathsf{PSPACE}}\subseteq{\mathsf{EXP}}\subseteq{\mathsf{NEXP}}\subseteq{\mathsf{EXPSPACE}}.$$

The complexity classes ${\mathsf{P}}$ and ${\mathsf{NP}}$ correspond to problems solvable in polynomial (resp. nondeterminsitic polynomial) time, and are well-known. The complexity classes ${\mathsf{EXP}}$ and ${\mathsf{NEXP}}$ are similar to ${\mathsf{P}}$ and ${\mathsf{NP}}$, but we allow the algorithm to use exponential time. The complexity classes ${\mathsf{PSPACE}}$ and ${\mathsf{EXPSPACE}}$ correspond to problems solvable in polynomial (resp. exponential) space. The above inclusions are well-known (cf. (Sipser 1997)).

复杂性类 ${\mathsf{P}}$ 和 ${\mathsf{NP}}$ 分别对应可在多项式时间（或非确定性多项式时间）内求解的问题，它们广为人知。复杂性类 ${\mathsf{EXP}}$ 和 ${\mathsf{NEXP}}$ 与 ${\mathsf{P}}$ 和 ${\mathsf{NP}}$ 类似，但允许算法使用指数时间。复杂性类 ${\mathsf{PSPACE}}$ 和 ${\mathsf{EXPSPACE}}$ 分别对应可在多项式空间（或指数空间）内求解的问题。上述包含关系是熟知的（参见 Sipser 1997）。

2.1 Linear Temporal Logic

2.1 线性时序逻辑

A formula in Linear Temporal Logic (LTL) over the finite alphabet $\Sigma$ has the following syntax:

定义在有限字母表 $\Sigma$ 上的线性时序逻辑（LTL）公式，语法如下：

$$\varphi::=\top\mid\bot\mid Q_{a}(\text{for all }a\in\Sigma)\mid\varphi\wedge\varphi\mid\varphi\vee\varphi\mid\neg\varphi\mid\varphi\mathbin{\textbf{S}}\varphi\mid\varphi\mathbin{\textbf{U}}\varphi$$

We define satisfaction of an LTL formula $\varphi$ on a word $w=a_{1}\dots a_{n}\in\Sigma^{*}$ at position $i\in[1,n]$, written $w,i\models\varphi$, inductively (omitting $\top$ (true) and $\bot$ (false)):

我们归纳定义 LTL 公式 $\varphi$ 在词 $w=a_{1}\dots a_{n}\in\Sigma^{*}$ 的位置 $i\in[1,n]$ 上成立，写作 $w,i\models\varphi$（略去 $\top$（真）和 $\bot$（假））：

Moreover, we define the shortcuts

此外，我们定义以下缩写

$$\textbf{P}\varphi:=\top\mathbin{\textbf{S}}\varphi\qquad\textbf{F}\varphi:=\top\mathbin{\textbf{U}}\varphi\qquad\textbf{X}\varphi:=\bot\mathbin{\textbf{U}}\varphi\qquad\textbf{G}\varphi:=\varphi\wedge\neg\textbf{F}\neg\varphi.$$

An LTL formula recognizes the language $L(\varphi)$ of all words $w\in\Sigma^{*}$ such that $w,k\models\varphi$, where $k$ is either $1$ or $|w|$ depending on whether the first or last position is regarded the output position of $\varphi$.

一个 LTL 公式认出语言 $L(\varphi)$，它由所有满足 $w,k\models\varphi$ 的词 $w\in\Sigma^{*}$ 组成，其中 $k$ 是 $1$ 或 $|w|$，取决于把第一个还是最后一个位置看作 $\varphi$ 的输出位置。

Example 1.

The star-free language $(ab)^{}$ can be defined in LTL as*

例 1。

星自由语言 $(ab)^{}$ 可以用 LTL 定义为*

$$\textbf{G}(Q_{a}\to\textbf{X}Q_{b})\wedge\textbf{G}(Q_{b}\wedge\textbf{X}\top\to\textbf{X}Q_{a}).$$

In words, at any $a$-position, the next letter is $b$. At any $b$-position that has a successor, the next letter is $a$.

用话说：在任意 $a$-位置，下一个字母是 $b$。在任意有后继的 $b$-位置，下一个字母是 $a$。

2.2 Masked unique hard-attention transformers

2.2 带掩码的唯一硬注意力 Transformer

Let $\Sigma$ be a finite alphabet of tokens. A token embedding is a function $\mathit{emb}\colon\Sigma\to\mathbb{Q}^{d}$ for some $d>0$. A token embedding naturally extends to a homomorphism $\Sigma^{*}\to(\mathbb{Q}^{d})^{*}$, where $\mathit{emb}(a_{1}\dots a_{n})=\mathit{emb}(a_{1})\dots\mathit{emb}(a_{n})$ for $a_{1},\dots,a_{n}\in\Sigma$.

设 $\Sigma$ 是有限的 token 字母表。token 嵌入是某个 $d>0$ 上的函数 $\mathit{emb}\colon\Sigma\to\mathbb{Q}^{d}$。token 嵌入自然地延拓成同态 $\Sigma^{*}\to(\mathbb{Q}^{d})^{*}$，其中对 $a_{1},\dots,a_{n}\in\Sigma$ 有 $\mathit{emb}(a_{1}\dots a_{n})=\mathit{emb}(a_{1})\dots\mathit{emb}(a_{n})$。

Remark 2.

In the following we define transformers over arbitrary rational numbers since our upper bounds even hold in this setting. We remark that all of our results also hold for the special case of fixed-precision real numbers, i.e., with a constant number of bits for a fixed transformer regardless of the input length. In fact, the lower bounds already hold for integers of fixed precision.

注 2。

下文我们在任意有理数上定义 Transformer，因为我们的上界在这一设定下已经成立。我们指出，全部结果对固定精度实数这一特殊情形同样成立，也就是：对固定的 Transformer，无论输入多长，都只用常数个比特。事实上，下界在固定精度整数上已经成立。

Attention layer.

A masked unique hard-attention (UHA) layer of width $r>0$ is defined by

注意力层。

宽度为 $r>0$ 的带掩码唯一硬注意力（UHA）层由以下对象定义：

• • three affine transformations $A,B\colon\mathbb{Q}^{r}\to\mathbb{Q}^{r}$ and $C\colon\mathbb{Q}^{2r}\to\mathbb{Q}^{s}$ with rational valued coefficients (i.e., each is of the form $Q\bm{x}+\bm{b}$ where matrix $Q$ and vector $\bm{b}$ have only rational entries),

• • 三个仿射变换 $A,B\colon\mathbb{Q}^{r}\to\mathbb{Q}^{r}$ 和 $C\colon\mathbb{Q}^{2r}\to\mathbb{Q}^{s}$，系数取有理值（即每一个都形如 $Q\bm{x}+\bm{b}$，其中矩阵 $Q$ 和向量 $\bm{b}$ 的条目都是有理数），

• • a mask predicate $M\colon\mathbb{N}\times\mathbb{N}\to\{\top,\bot\}$, which is defined by $M(i,j):=\top$ (no masking), $M(i,j):=(j<i)$ (strict future masking), or $M(i,j):=(j>i)$ (strict past masking), and

• • 一个掩码谓词 $M\colon\mathbb{N}\times\mathbb{N}\to\{\top,\bot\}$，定义为 $M(i,j):=\top$（不掩码）、$M(i,j):=(j<i)$（严格未来掩码），或 $M(i,j):=(j>i)$（严格过去掩码），以及

• • a tie-breaking function $\tau$ selecting one element of a finite non-empty subset of $\mathbb{N}$, which is either defined as $\min$ (leftmost tie-breaking) or $\max$ (rightmost tie-breaking).

• • 一个平局打破函数 $\tau$，它从 $\mathbb{N}$ 的非空有限子集中选出一个元素，定义为 $\min$（最左平局打破）或 $\max$（最右平局打破）。

We now show how a UHA layer works on a sequence $\bm{v}_{1},\dots,\bm{v}_{n}\in\mathbb{Q}^{r}$ with $n\geq 1$. The score function is defined as the dot product $S(\bm{v}_{i},\bm{v}_{j}):=\langle A(\bm{v}_{i}),B(\bm{v}_{j})\rangle$ for all $i,j\in[1,n]$. For $i\in[1,n]$ let $U_{i}:=\{j\in[1,n]\mid M(i,j)\}$ be the set of unmasked positions and $B_{i}:=\{j\in U_{i}\mid\forall j^{\prime}\in U_{i}\colon S(\bm{v}_{i},\bm{v}_{j})\geq S(\bm{v}_{i},\bm{v}_{j^{\prime}})\}$ be the set of unmasked positions that maximize the score function. We define the attention vector at position $i\in[1,n]$ as $\bm{a}_{i}:=\bm{v}_{\tau(B_{i})}$ if $U_{i}\neq\emptyset$ and $\bm{a}_{i}:=\bm{0}$ otherwise. The layer outputs the sequence $C(\bm{v}_{1},\bm{a}_{1}),\dots,C(\bm{v}_{n},\bm{a}_{n})$.

现在说明 UHA 层如何作用在序列 $\bm{v}_{1},\dots,\bm{v}_{n}\in\mathbb{Q}^{r}$（$n\geq 1$）上。分数函数定义为点积 $S(\bm{v}_{i},\bm{v}_{j}):=\langle A(\bm{v}_{i}),B(\bm{v}_{j})\rangle$，对所有 $i,j\in[1,n]$。对 $i\in[1,n]$，令 $U_{i}:=\{j\in[1,n]\mid M(i,j)\}$ 为未掩码位置的集合，并令 $B_{i}:=\{j\in U_{i}\mid\forall j^{\prime}\in U_{i}\colon S(\bm{v}_{i},\bm{v}_{j})\geq S(\bm{v}_{i},\bm{v}_{j^{\prime}})\}$ 为使分数函数取最大的那些未掩码位置。我们把位置 $i\in[1,n]$ 处的注意力向量定义为：若 $U_{i}\neq\emptyset$ 则 $\bm{a}_{i}:=\bm{v}_{\tau(B_{i})}$，否则 $\bm{a}_{i}:=\bm{0}$。该层输出序列 $C(\bm{v}_{1},\bm{a}_{1}),\dots,C(\bm{v}_{n},\bm{a}_{n})$。

ReLU layer.

A ReLU layer of width $r>0$ on input $\bm{v}_{1},\dots,\bm{v}_{n}\in\mathbb{Q}^{r}$ applies for some $k\in[1,r]$ the ReLU function to the $k$-th coordinate of each $\bm{v}_{i}$, i.e., it outputs the sequence $\bm{v}^{\prime}_{1},\dots,\bm{v}^{\prime}_{n}$ where $\bm{v}^{\prime}_{i}:=(\bm{v}_{i}[1,k-1],\max\{0,\bm{v}_{i}(k)\},\bm{v}_{i}[k+1,n])$. [Equivalently, one could instead allow a feed-forward network at the end of an encoder layer (see (Hao et al. 2022; Barceló et al. 2024)).]

ReLU 层。

宽度为 $r>0$ 的 ReLU 层在输入 $\bm{v}_{1},\dots,\bm{v}_{n}\in\mathbb{Q}^{r}$ 上，对某个 $k\in[1,r]$，把 ReLU 函数作用到每个 $\bm{v}_{i}$ 的第 $k$ 个坐标，即输出序列 $\bm{v}^{\prime}_{1},\dots,\bm{v}^{\prime}_{n}$，其中 $\bm{v}^{\prime}_{i}:=(\bm{v}_{i}[1,k-1],\max\{0,\bm{v}_{i}(k)\},\bm{v}_{i}[k+1,n])$。[等价地，也可以在编码器层末尾允许一个前馈网络（参见 Hao et al. 2022；Barceló et al. 2024）。]

Transformer.

A masked unique hard-attention transformer (UHAT) is a length-preserving function $\mathcal{T}\colon\Sigma^{*}\to(\mathbb{Q}^{s})^{*}$ defined by application of a token embedding followed by application of a fixed sequence of UHA layers and ReLU layers of matching width.

Transformer。

带掩码的唯一硬注意力 Transformer（UHAT）是一个保长函数 $\mathcal{T}\colon\Sigma^{*}\to(\mathbb{Q}^{s})^{*}$，由先做 token 嵌入、再依次应用一串宽度匹配的 UHA 层和 ReLU 层来定义。

Languages accepted by UHATs.

To view a UHAT $\mathcal{T}\colon\Sigma^{*}\to(\mathbb{Q}^{s})^{*}$ as a language recognizer, we assume that $\mathcal{T}$ is given together with an acceptance vector $\bm{t}\in\mathbb{Q}^{s}$. The recognized language $L(\mathcal{T})$ is then the set of words on which $\mathcal{T}$ outputs a sequence $\bm{v}_{1},\dots,\bm{v}_{n}\in\mathbb{Q}^{s}$ with $\langle\bm{t},\bm{v}_{k}\rangle>0$, where $k\in[1,n]$ is either 1 or $n$ depending on whether the fist or last position is regarded the output position of $\mathcal{T}$.

UHAT 接受的语言。

要把 UHAT $\mathcal{T}\colon\Sigma^{*}\to(\mathbb{Q}^{s})^{*}$ 看成语言识别器，我们假定 $\mathcal{T}$ 还配有一个接受向量 $\bm{t}\in\mathbb{Q}^{s}$。认出的语言 $L(\mathcal{T})$ 就是那些使 $\mathcal{T}$ 输出序列 $\bm{v}_{1},\dots,\bm{v}_{n}\in\mathbb{Q}^{s}$ 且 $\langle\bm{t},\bm{v}_{k}\rangle>0$ 的词，其中 $k\in[1,n]$ 是 $1$ 或 $n$，取决于把第一个还是最后一个位置看作 $\mathcal{T}$ 的输出位置。

2.3 Boolean RASP

2.3 布尔 RASP

As an intermediate step to prove ${\mathsf{EXPSPACE}}$-hardness for UHATs, we use Boolean RASP (B-RASP) as introduced by Yang et al. 2024, who showed that B-RASP is expressively equivalent to UHATs. A B-RASP program is defined as follows. Let $w=a_{1}\dots a_{n}\in\Sigma^{*}$ with $n\geq 1$ be an input word. For every $a\in\Sigma$ there is an initial Boolean vector $Q_{a}\in\{0,1\}^{n}$ with $Q_{a}(i)=1$ iff $a_{i}=a$ for all $i\in[1,n]$. We number the initial vectors and call them $P_{1},\dots,P_{|\Sigma|}$. We now describe how vector $P_{t+1}$ can be defined from vectors $P_{1},\dots,P_{t}$ for $t\geq|\Sigma|$.

作为证明 UHAT 的 ${\mathsf{EXPSPACE}}$-困难性的中间步骤，我们使用 Yang et al. 2024 引入的布尔 RASP（B-RASP）；他们证明 B-RASP 在表达力上等价于 UHAT。B-RASP 程序定义如下。设输入词为 $w=a_{1}\dots a_{n}\in\Sigma^{*}$ 且 $n\geq 1$。对每个 $a\in\Sigma$，都有一个初始布尔向量 $Q_{a}\in\{0,1\}^{n}$，使得对所有 $i\in[1,n]$，$Q_{a}(i)=1$ 当且仅当 $a_{i}=a$。我们给这些初始向量编号，并称之为 $P_{1},\dots,P_{|\Sigma|}$。下面说明对 $t\geq|\Sigma|$，如何由向量 $P_{1},\dots,P_{t}$ 定义向量 $P_{t+1}$。

Position-wise operation.

The vector $P_{t+1}$ can be defined by $P_{t+1}(i):=R(i)$ for some Boolean combination $R(i)$ of $\{P_{1}(i),\dots,P_{t}(i)\}$.

逐位置运算。

向量 $P_{t+1}$ 可以由 $P_{t+1}(i):=R(i)$ 定义，其中 $R(i)$ 是 $\{P_{1}(i),\dots,P_{t}(i)\}$ 的某个布尔组合。

Attention operation.

The vector $P_{t+1}$ can be defined by either of

注意力运算。

向量 $P_{t+1}$ 可以由下列二者之一定义

$$\displaystyle P_{t+1}(i):=\ \blacktriangleleft_{j}[M(i,j),S(i,j)]\ V(i,j):D(i) \\ \displaystyle P_{t+1}(i):=\ \blacktriangleright_{j}[M(i,j),S(i,j)]\ V(i,j):D(i)$$

where

其中

• • $M(i,j)$ is a mask predicate as in the definition of a UHAT,

• • $M(i,j)$ 是与 UHAT 定义中相同的掩码谓词，

• • $S(i,j)$ and $V(i,j)$ are Boolean combinations of $\{P_{1}(i),\dots,P_{t}(i)\}\cup\{P_{1}(j),\dots,P_{t}(j)\}$, called score predicate and value predicate, respectively,

• • $S(i,j)$ 和 $V(i,j)$ 是 $\{P_{1}(i),\dots,P_{t}(i),P_{1}(j),\dots,P_{t}(j)\}$ 的布尔组合，分别称为分数谓词和值谓词，

• • $D(i)$ is a Boolean combination of $\{P_{1}(i),\dots,P_{t}(i)\}$, called default value predicate.

• • $D(i)$ 是 $\{P_{1}(i),\dots,P_{t}(i)\}$ 的布尔组合，称为默认值谓词。

The semantics of an attention operation is as follows. For every $i\in[1,n]$, let

注意力运算的语义如下。对每个 $i\in[1,n]$，令

$$j_{i}:=\begin{cases}\min{j\in[1,n]\mid M(i,j)\text{ and }S(i,j)=1},&\text{for }\blacktriangleleft\
\max{j\in[1,n]\mid M(i,j)\text{ and }S(i,j)=1},&\text{for }\blacktriangleright.\end{cases}$$

We then define $P_{t+1}(i):=V(i,j_{i})$ if $j_{i}$ exists and $P_{t+1}(i):=D(i)$ otherwise. Observe that $\blacktriangleleft$ (resp. $\blacktriangleright$) corresponds to leftmost (resp. rightmost) tie-breaking in UHATs.

然后我们定义：若 $j_{i}$ 存在则 $P_{t+1}(i):=V(i,j_{i})$，否则 $P_{t+1}(i):=D(i)$。注意 $\blacktriangleleft$（或 $\blacktriangleright$）分别对应 UHAT 中的最左（或最右）平局打破。

A B-RASP program is given by an alphabet $\Sigma$ and a sequence of position-wise and attention operations. We can view a B-RASP program as a language recognizer by designating one Boolean vector $Y$ as the output vector and either the first or last position as the output position. Then an input word $w=a_{1}\dots a_{n}$ is accepted if and only if $Y(k)=1$, where $k$ is the output position, i.e., $k=1$ or $k=n$.

一个 B-RASP 程序由字母表 $\Sigma$ 以及一串逐位置运算和注意力运算给出。我们可以把 B-RASP 程序看成语言识别器：指定某个布尔向量 $Y$ 为输出向量，并把第一个或最后一个位置指定为输出位置。于是输入词 $w=a_{1}\dots a_{n}$ 被接受，当且仅当 $Y(k)=1$，其中 $k$ 是输出位置，即 $k=1$ 或 $k=n$。

2.4 Recurrent Neural Networks (RNN)

2.4 循环神经网络（RNN）

We use RNN as language acceptors, as in the work of Merrill et al. 2020; Weiss et al. 2024; Weiss et al. 2018. In particular, a Recurrent Neural Network (RNN) $M$ can be viewed as a function $g:(\mathbb{R}^{d}\times\Sigma)\to\mathbb{R}^{d}$. As in the case of transformers, $\Sigma$ is also mapped into $\mathbb{R}^{k}$ (for some $k$) through a token embedding function $\mathit{emb}$ (e.g. one-hot encoding) and the function $g$ actually has domain $\mathbb{R}^{d}\times\mathbb{R}^{k}$. We have an input vector $\bar{x}_{0}\in\mathbb{R}^{d}$ and a final function $f:\mathbb{R}^{d}\to\{Acc,Rej\}$, to decide whether a vector $\bar{x}\in\mathbb{R}^{d}$ is accepting. The semantics of acceptance is the same as that of automata, i.e., given $w=a_{1}\cdots a_{n}\in\Sigma^{*}$, we compute $d$-vectors $\bar{x}_{1},\ldots,\bar{x}_{n}$ such that $g(\bar{x}_{i},a_{i+1})=\bar{x}_{i+1}$ for each $i=0,\ldots,n-1$. The string $w$ is accepted by $M$ if $f(a_{n})=Acc$.

我们把 RNN 当作语言接受器来用，做法与 Merrill et al. 2020；Weiss et al. 2024；Weiss et al. 2018 一致。具体地说，一个循环神经网络（RNN） $M$ 可以看成函数 $g:(\mathbb{R}^{d}\times\Sigma)\to\mathbb{R}^{d}$。与 Transformer 的情形一样，$\Sigma$ 也通过 token 嵌入函数 $\mathit{emb}$（例如独热编码）映射到 $\mathbb{R}^{k}$（对某个 $k$），因而函数 $g$ 的实际定义域是 $\mathbb{R}^{d}\times\mathbb{R}^{k}$。我们有输入向量 $\bar{x}_{0}\in\mathbb{R}^{d}$，以及最终函数 $f:\mathbb{R}^{d}\to\{Acc,Rej\}$，用来判定向量 $\bar{x}\in\mathbb{R}^{d}$ 是否接受。接受语义与自动机相同：给定 $w=a_{1}\cdots a_{n}\in\Sigma^{*}$，我们计算 $d$ 维向量 $\bar{x}_{1},\ldots,\bar{x}_{n}$，使得对每个 $i=0,\ldots,n-1$ 有 $g(\bar{x}_{i},a_{i+1})=\bar{x}_{i+1}$。若 $f(a_{n})=Acc$，则称 $M$ 接受字符串 $w$。

As a computational model, it is realistic to assume RNNs with a fixed precision, i.e., computation is always done over real numbers that can be represented with a constant $k$ number of bits. The details of the actual representation are not important for our analysis. Therefore, the state-space $Q$ of the above RNN can be mapped to $d$-vectors over $\{0,1\}^{k}$ (instead of $\mathbb{R}$). The following proposition is now immediate.

作为计算模型，假定 RNN 具有固定精度是现实的，也就是计算始终在能用常数 $k$ 个比特表示的实数上进行。具体表示细节对我们的分析并不重要。因此，上述 RNN 的状态空间 $Q$ 可以映射到 $\{0,1\}^{k}$ 上的 $d$ 维向量（而不是 $\mathbb{R}$）。下面的命题现在是直接的。

Proposition 3.

An RNN $g:(\mathbb{R}^{d}\times\Sigma)\to\mathbb{R}^{d}$ with fixed precision $k$ can be represented by a finite automaton with $2^{kd}$ many states.

命题 3。

固定精度为 $k$ 的 RNN $g:(\mathbb{R}^{d}\times\Sigma)\to\mathbb{R}^{d}$ 可以用一个具有 $2^{kd}$ 个状态的有限自动机来表示。

2.5 Size measures and succinctness

2.5 大小度量与简洁性

Let $\mathcal{R}$ be a finite representation of a language, i.e., in our case a UHAT, LTL formula, finite automaton, RNN, or B-RASP program. We define the size of $\mathcal{R}$, denoted by $|\mathcal{R}|$, as the length of its usual binary encoding. In measuring succinctness of RNN, we put the precision $k$ in unary also as part of the size measure; since we do not want to compare a transformer that uses a fixed precision $k$ and allow an RNN that uses a fixed precision $2^{k}$. Let $\mathcal{C}_{1},\mathcal{C}_{2}$ be classes of finite representations of languages. We say that $\mathcal{C}_{1}$ can be exponentially more succinct than $\mathcal{C}_{2}$ if for every function $f\in 2^{o(n)}$ there is an $\mathcal{R}_{1}\in\mathcal{C}_{1}$ such that any $\mathcal{R}_{2}\in\mathcal{C}_{2}$ representing the same language as $\mathcal{R}_{1}$ has size $|\mathcal{R}_{2}|>f(|\mathcal{R}_{1}|)$. Similarly, we define doubly exponentially more succinct using functions $f\in 2^{2^{o(n)}}$ instead. Intuitively, this means that any translation from $\mathcal{C}_{1}$ to $\mathcal{C}_{2}$ incurs, in the worst-case, an (doubly) exponential increase in size.

设 $\mathcal{R}$ 是语言的一个有限表示，在我们这里也就是 UHAT、LTL 公式、有限自动机、RNN 或 B-RASP 程序。我们把 $\mathcal{R}$ 的大小记为 $|\mathcal{R}|$，定义为它通常的二进制编码长度。在度量 RNN 的简洁性时，我们把精度 $k$ 以一元方式也计入大小，因为我们不想拿一个使用固定精度 $k$ 的 Transformer，去和一个使用固定精度 $2^{k}$ 的 RNN 相比。设 $\mathcal{C}_{1},\mathcal{C}_{2}$ 是语言有限表示的类。我们说 $\mathcal{C}_{1}$ 可以比 $\mathcal{C}_{2}$ 指数级更简洁，如果对每个函数 $f\in 2^{o(n)}$，都存在 $\mathcal{R}_{1}\in\mathcal{C}_{1}$，使得任何表示同一语言的 $\mathcal{R}_{2}\in\mathcal{C}_{2}$ 都满足 $|\mathcal{R}_{2}|>f(|\mathcal{R}_{1}|)$。类似地，把函数改成 $f\in 2^{2^{o(n)}}$，就定义了双指数级更简洁。直观上，这意味着从 $\mathcal{C}_{1}$ 到 $\mathcal{C}_{2}$ 的任何翻译，在最坏情形下都会带来（双）指数的大小增长。

3 Size of smallest witness via non-emptiness problem

3 通过非空性问题看最短见证的大小

In this section we consider the problem of checking whether the language recognized by a UHAT or B-RASP program is non-empty. In particular, the technique is essentially a simulation of a Turing machine with an $2^{O(n)}$-sized tape (for a given $n$). As we will see later, there are Turing machines such that the smallest (i.e. shortest) accepted string by the constructed UHAT is of length at least $2^{2^{\Omega(n)}}$.

本节考虑判断 UHAT 或 B-RASP 程序所认语言是否非空的问题。所用技术本质上是模拟一台磁带大小为 $2^{O(n)}$ 的图灵机（对给定的 $n$）。后面会看到，存在一些图灵机，使得构造出的 UHAT 所接受的最短字符串长度至少为 $2^{2^{\Omega(n)}}$。

Example 4.

To illustrate the idea, we describe a B-RASP program that accepts strings of the form

例 4。

为说明想法，我们描述一个接受如下形式字符串的 B-RASP 程序

$$0000a_{1}\#0001a_{2}\#0010a_{3}\#\dots\#1111a_{2^{4}}\#$$

where $a_{i}\in\{a,b,c\}$ such that $(a_{j},a_{j+1})\in H$ for all $1\leq j<2^{4}$. Here, $H:=\{(a,b),(b,c),(b,a),(c,b)\}$ is a set of constraints specifying which symbols can be next to each other. For simplicity, we concentrate on the two main conditions: (i) checking that the bit counter is incremented and (ii) checking that the successive symbols are in $H$. To check (i), we use the following attention operation:

其中 $a_{i}\in\{a,b,c\}$，并且对所有 $1\leq j<2^{4}$ 有 $(a_{j},a_{j+1})\in H$。这里 $H:=\{(a,b),(b,c),(b,a),(c,b)\}$ 是一组约束，规定哪些符号可以相邻。为简单起见，我们集中看两个主要条件：(i) 检查比特计数器是否递增；(ii) 检查相继符号是否属于 $H$。为检查 (i)，我们使用如下注意力运算：

$$C_{+1}(i):=\ \blacktriangleright_{j}[j<i,Q_{#}(j)]\ \bigvee_{k=1}^{4}\big(\bigwedge_{r=1}^{k-1}\neg C_{r}(i)\wedge C_{r}(j)\big)\wedge C_{k}(i)\wedge\neg C_{k}(j)\ \wedge\
\ \big(\bigwedge_{r=k+1}^{4}C_{r}(i)\leftrightarrow C_{r}(j)\big):1$$

Assume $i$ is a $\#$-position. Attention selects the rightmost $\#$-position $j$ left of position $i$. Let $b_{1}^{i}\dots b_{4}^{i}$ and $b_{1}^{j}\dots b_{4}^{j}$ be the bit strings directly left of position $i$ and $j$, respectively. We assume that we already defined $C_{k}(i)=b_{k}^{i}$ and $C_{k}(j)=b_{k}^{j}$ for all $k\in[1,4]$. Then the above value predicate checks that the binary number $b_{1}^{i}\dots b_{4}^{i}$ is the number $b_{1}^{j}\dots b_{4}^{j}$ incremented by 1. To check (ii), we can use the attention operation

假定 $i$ 是一个 $\#$-位置。注意力选出 $i$ 左侧最右的 $\#$-位置 $j$。设 $b_{1}^{i}\dots b_{4}^{i}$ 和 $b_{1}^{j}\dots b_{4}^{j}$ 分别是紧挨在位置 $i$ 和 $j$ 左侧的比特串。我们假定已经对所有 $k\in[1,4]$ 定义了 $C_{k}(i)=b_{k}^{i}$ 和 $C_{k}(j)=b_{k}^{j}$。于是上述值谓词检查二进制数 $b_{1}^{i}\dots b_{4}^{i}$ 是否恰为 $b_{1}^{j}\dots b_{4}^{j}$ 加 1。为检查 (ii)，可以使用注意力运算

$$M_{\leftarrow}(i):=\ \blacktriangleright_{j}[j<i,Q_{a}(j)\vee Q_{b}(j)\vee Q_{c}(j)]\ \bigvee_{(h,h^{\prime})\in H}Q_{h}(j)\wedge Q_{h^{\prime}}(i):1.$$

If $i$ is a position of a symbol $a_{i}$, attention picks the rightmost position $j$ of a symbol $a_{j}$ to the left of $i$ and checks with the value predicate that $(a_{j},a_{i})\in H$.

若 $i$ 是某个符号 $a_{i}$ 的位置，注意力会选出 $i$ 左侧最右的符号位置 $j$（对应符号 $a_{j}$），并用值谓词检查 $(a_{j},a_{i})\in H$。

This allows us to succinctly recognize a language whose smallest string has length exponential in the number of bits of the binary counter. By stacking multiple such strings vertically and introducing vertical constraints in addition to the horizontal constraints $H$, we can even succinctly recognize languages whose smallest string has doubly exponential length.

这样我们就能简洁地认出一门语言，其最短字符串的长度对二进制计数器的比特数是指数级的。把多条这样的字符串纵向叠起来，并在水平约束 $H$ 之外再引入竖直约束，我们甚至能简洁地认出最短字符串长度为双指数的语言。

We prove the following precise complexity bounds:

我们证明下列精确的复杂性界：

Theorem 5.

The non-emptiness problem for UHATs and B-RASP programs is ${\mathsf{EXPSPACE}}$-complete.

定理 5。

UHAT 与 B-RASP 程序的非空性问题是 ${\mathsf{EXPSPACE}}$-完全的。

We start with the lower bound and show it first for B-RASP programs.

我们从下界开始，并先对 B-RASP 程序给出证明。

Proposition 6.

The non-emptiness problem for B-RASP programs is ${\mathsf{EXPSPACE}}$-hard.

命题 6。

B-RASP 程序的非空性问题是 ${\mathsf{EXPSPACE}}$-难的。

For the proof we use the techniques illustrated in Example 4 and reduce from a so-called tiling problem. A tile is a quadruple $t\in\mathbb{N}_{0}^{4}$, where we write $t=\langle\mathit{left}(t),\mathit{up}(t),\mathit{right}(t),\mathit{down}(t)\rangle$. The $2^{n}$-tiling problem is defined as follows:

证明使用例 4 中展示的技术，并从所谓的铺砖问题做规约。一块砖是四元组 $t\in\mathbb{N}_{0}^{4}$，我们写成 $t=\langle\mathit{left}(t),\mathit{up}(t),\mathit{right}(t),\mathit{down}(t)\rangle$。$2^{n}$-铺砖问题定义如下：

An integer $n>0$ in unary, a finite set $T$ of tiles, and a tile $t_{\mathit{fin}}\in T$

一个用一元写出的整数 $n>0$、一个有限砖集 $T$，以及一块砖 $t_{\mathit{fin}}\in T$

Do there exist $m>0$ and a function $\tau\colon\{1,\dots,2^{n}\}\times\{1,\dots,m\}\to T$ such that

是否存在 $m>0$ 和函数 $\tau\colon\{1,\dots,2^{n}\}\times\{1,\dots,m\}\to T$，使得

1. $\tau(2^{n},m)=t_{\mathit{fin}}$,

1. $\tau(2^{n},m)=t_{\mathit{fin}}$，

2. $\mathit{down}(\tau(i,1))=\mathit{up}(\tau(i,m))=0$ for all $1\leq i\leq 2^{n}$,

2. 对所有 $1\leq i\leq 2^{n}$，$\mathit{down}(\tau(i,1))=\mathit{up}(\tau(i,m))=0$，

3. $\mathit{left}(\tau(1,j))=\mathit{right}(\tau(2^{n},j))=0$ for all $1\leq j\leq m$,

3. 对所有 $1\leq j\leq m$，$\mathit{left}(\tau(1,j))=\mathit{right}(\tau(2^{n},j))=0$，

4. $\mathit{right}(\tau(i,j))=\mathit{left}(\tau(i+1,j))$ for all $1\leq i<2^{n}$ and $1\leq j\leq m$, and

4. 对所有 $1\leq i<2^{n}$ 和 $1\leq j\leq m$，$\mathit{right}(\tau(i,j))=\mathit{left}(\tau(i+1,j))$，并且

5. $\mathit{up}(\tau(i,j))=\mathit{down}(\tau(i,j+1))$ for all $1\leq i\leq 2^{n}$ and $1\leq j<m$?

5. 对所有 $1\leq i\leq 2^{n}$ 和 $1\leq j<m$，$\mathit{up}(\tau(i,j))=\mathit{down}(\tau(i,j+1))$？

The following is shown in (Schwarzentruber 2019):

下列结果见（Schwarzentruber 2019）：

Proposition 7.

The $2^{n}$-tiling problem is ${\mathsf{EXPSPACE}}$-complete.

命题 7。

$2^{n}$-铺砖问题是 ${\mathsf{EXPSPACE}}$-完全的。

The reduction to B-RASP uses an encoding of the function $\tau$ as a sequence of strings which are of a similar form as in Example 4, but is substantially more involved. The key observation is that strict future masking with rightmost tie-breaking enables us to check conditions between successive tiles (condition 4) but also between the current tile and the tile at the most recent past occurrence of the same counter value (condition 5). The full proof can be found in Appendix A.

到 B-RASP 的规约把函数 $\tau$ 编码成一串与例 4 形式相近的字符串，但要复杂得多。关键观察是：带最右平局打破的严格未来掩码，既能检查相继砖块之间的条件（条件 4），也能检查当前砖与“上一次出现同一计数器取值”处的砖之间的条件（条件 5）。完整证明见附录 A。

We observe that the B-RASP program constructed in the proof of Proposition 6 can easily be converted to UHAT, which yields the ${\mathsf{EXPSPACE}}$ lower bound also for UHAT.

我们观察到，命题 6 证明中构造的 B-RASP 程序可以容易地转成 UHAT，从而也对 UHAT 给出 ${\mathsf{EXPSPACE}}$ 下界。

Proposition 8.

The non-emptiness problem for UHAT is ${\mathsf{EXPSPACE}}$-hard.

命题 8。

UHAT 的非空性问题是 ${\mathsf{EXPSPACE}}$-难的。

Proof sketch.

We show that the B-RASP program constructed in the proof of Proposition 6 can be converted to a UHAT in polynomial time. To this end, note that Boolean operations can easily be simulated using affine transformations and ReLU. For the attention operations we use an attention layer. The value predicates $V(i,j)$ can be simulated by copying the required components of the $j$-th vector, that was selected by attention, to the $i$-th vector using the affine transformation whose result is forwarded and computing the result of the Boolean combination with additional ReLU layers. For the score predicates $S(i,j)$ we note that they either only depend on $j$ or they check whether some binary numbers at positions $i$ and $j$ are equal. The former can be simulated using an additional preliminary layer that already computes the result of $S(j)$ for every position $j$. For the latter we use Lemma 9. ∎

证明概要。

我们说明命题 6 证明中构造的 B-RASP 程序可以在多项式时间内转成 UHAT。为此注意，布尔运算很容易用仿射变换和 ReLU 来模拟。对注意力运算，我们使用一层注意力。值谓词 $V(i,j)$ 可以这样模拟：用其结果会被向前传递的仿射变换，把注意力选出的第 $j$ 个向量中所需分量复制到第 $i$ 个向量，再用额外的 ReLU 层计算布尔组合的结果。对分数谓词 $S(i,j)$，我们注意到它们要么只依赖于 $j$，要么检查位置 $i$ 和 $j$ 处的某些二进制数是否相等。前者可以用一个额外的预备层来模拟，该层已经为每个位置 $j$ 算出 $S(j)$ 的结果。后者我们使用引理 9。∎

The proof of the following Lemma can be found in Appendix A.

下列引理的证明见附录 A。

Lemma 9.

Given a mask predicate $M$ and tie-breaking function $\tau$, there is an attention layer using $M$ and $\tau$ that on every sequence $\bm{v}_{1},\dots,\bm{v}_{n}\in\{0,1\}^{2d}$ with $\bm{v}_{k}=(b_{k,1},1-b_{k,1},\dots,b_{k,d},1-b_{k,d})$ for all $k\in[1,n]$ and for every $i\in[1,n]$ picks attention vector $\bm{a}_{i}=\bm{v}_{j}$ such that $b_{i,r}=b_{j,r}$ for all $r\in[1,d]$ if such an unmasked position $j$ exists.

引理 9。

给定掩码谓词 $M$ 和平局打破函数 $\tau$，存在使用 $M$ 和 $\tau$ 的注意力层，使得在每个序列 $\bm{v}_{1},\dots,\bm{v}_{n}\in\{0,1\}^{2d}$（对所有 $k\in[1,n]$ 有 $\bm{v}_{k}=(b_{k,1},1-b_{k,1},\dots,b_{k,d},1-b_{k,d})$）上，对每个 $i\in[1,n]$，若存在这样的未掩码位置 $j$，则选出注意力向量 $\bm{a}_{i}=\bm{v}_{j}$，满足对所有 $r\in[1,d]$ 有 $b_{i,r}=b_{j,r}$。