Theoretical Constraints on the Expressive Power of $\mathsf{RoPE}$-based Tensor Attention Transformers

Introduction

Large Language Models (LLMs), such as OpenAI’s ChatGPT , Google’s Gemini , Anthropic’s Claude 3.5 , and Meta’s LLaMA 3.3 have reshaped a wide range of fields by demonstrating unprecedented advancements. These advancements are primarily due to their capability to efficiently process long-context inputs, a crucial feature for tasks like summarizing lengthy documents (e.g., medical reports, legal analyses, technical briefs), enabling superior reasoning and problem-solving performance at a level comparable to expert human analysis. At the core of these advancements lies the Transformer architecture , driven by its self-attention mechanism. Understanding computational primitives that Transformer components enable is pivotal for principled interpretations and exposing limitations in Transformer-based systems.

Previous research has investigated these questions by analyzing the expressiveness of Transformers. As an illustration, the work in showed that constant-depth threshold circuit families can effectively emulate Transformers with precision $c\log n$ and depth-$d$. This holds true in both non-uniform and $\mathsf{L}$-uniform computational models. This result highlights Transformers’ computational efficiency and structural adaptability when analyzed through circuit complexity theory’s lens. Expanding on these results, showed that Transformers with $O(\log n)$ precision belong to $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$, even when the absolute error is bounded by $2^{-O(\operatorname{poly}(n))}$.

To augment the capabilities of Transformers, innovations such as Rotation Position Embedding ($\mathsf{RoPE}$) have been proposed. Through the rotation matrices, $\mathsf{RoPE}$ improves the sequence length adaptability while enhancing the efficacy of attention mechanisms. Meanwhile, multi-view approaches are increasingly recognized for capturing high-order correlations in diverse data types, including mathematical data , graph structures , and multi-modality datasets . Models like GPT-4o and Google’s Project Astra exemplify this trend, integrating reasoning across multi-modality in real-time. Despite these advancements, classical attention mechanisms face representational limitations. Specifically, demonstrated that matrix attention can only capture pairwise correlations, falling short in modeling triple-wise or higher-order interactions. Addressing such limitations typically requires multiple layers or carefully designed architectures, complicating the integration of multi-view information.

To overcome these constraints, and proposed Tensor Attention, a higher-order extension of matrix attention. Tensor Attention intrinsically captures high-order correlations, defined as $\mathsf{Softmax}(Q(K_{1}\oslash K_{2})^{\top})(V_{1}\oslash V_{2})$ (see Definition 3.30), where $\oslash$ denotes the column-wise Kronecker product (see Definition 3.21). Here, $Q$, $K_{1}/V_{1}$, and $K_{2}/V_{2}$ represent inputs from different views or modalities. This raises a natural question:

Does the $\mathsf{RoPE}$ and tensor attention enhance the expressiveness of the $\mathsf{RoPE}$-based tensor attention Transformer?

This work addresses this question through the lens of circuit complexity, advancing the theoretical understanding of tensor attention and $\mathsf{RoPE}$-based tensor attention mechanisms.

We present a rigorous analysis of tensor attention Transformers and $\mathsf{RoPE}$-based tensor attention Transformers, delineating their intrinsic computational limitations. Our approach methodically evaluates the circuit complexity of each architectural component, ranging from basic trigonometric operations to the comprehensive $\mathsf{RoPE}$-based tensor attention Transformers. Specifically, it is demonstrated that uniform $\mathsf{TC}^{0}$ circuits are amenable to simulating the components mentioned above. Furthermore, it is proven that, unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$, tensor attention Transformers, as well as $\mathsf{RoPE}$-enhanced tensor attention Transformers with $O(1)$ layers, $\operatorname{poly}(n)$-precision, and a feature dimension $d=O(n)$ are incapable of solving fixed membership problems or $(A_{F,r})^{*}$ closure problems. This finding underscores fundamental expressivity constraints inherent to tensor attention and $\mathsf{RoPE}$-based tensor attention architectures.

The summary of our contributions to the theoretical understanding of these architectures and their computational boundaries, rooted in circuit complexity theory, showed as follows:

Unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$, we demonstrate that a $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ circuit family can simulate a tensor attention Transformer or a $\mathsf{RoPE}$-based tensor attention Transformer, with constant depth, $\operatorname{poly}(n)$ size, and $\operatorname{poly}(n)$ precision (Based on Theorem 4.7 and Theorem 5.7).

We demonstrate that, unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$, a tensor attention Transformer or a $\mathsf{RoPE}$-based tensor attention Transformer with $O(1)$ layers, $\operatorname{poly}(n)$ precision, and a feature dimension $d=O(n)$ are incapable of accomplishing the fixed membership problems (Based on Theorem 6.6 and Theorem 6.7).

We demonstrate that, unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$, a tensor attention Transformer or a $\mathsf{RoPE}$-based tensor attention Transformer with $O(1)$ layers, $\operatorname{poly}(n)$ precision, and a feature dimension $d=O(n)$ are incapable of accomplishing the $(A_{F,r})^{*}$ closure problems (Based on Theorem 6.8 and Theorem 6.9).

Related Work

Circuit complexity, a specialized domain within computational complexity theory, investigates the properties of circuit families as computational models. Numerous circuit complexity classes are relevant to the study of machine learning, with $\mathsf{AC}^{0}$ characterizing problems solvable by highly parallel circuits utilizing elementary logic gates. The class $\mathsf{TC}^{0}$ generalizes this concept by incorporating circuits that feature threshold gates, while $\mathsf{NC}^{1}$ encompasses problems solvable by circuits with a depth of $O(\log n)$ and bounded gate arity . It is well-established that $\mathsf{AC}^{0}\subset\mathsf{TC}^{0}\subseteq\mathsf{NC}^{1}$, although the question of whether $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$ remains unresolved. Assuming this inequality holds, demonstrates that, when simulating certain non-solvable semiautomata, the depth of Transformers must necessarily increase with the input sequence length. The circuit complexity is also used to measure some other popular architectures such us Mamba and Hopfield networks .

Computation of Transformers.

Transformers have undeniably revolutionized the field of natural language processing, yet their performance significantly deteriorates when tasked with mathematical computations . This observation has led to a surge in research aimed at identifying the computational boundaries of Transformer models, particularly in two distinct categories: (1) average-head attention Transformers, which assign a value of 1 to the highest probability in the vector while setting all other probabilities to 0, and (2) softmax-attention Transformers, which utilize the softmax function. Merrill, Sabharwal, and Smith demonstrate that average-head attention Transformers are capable of recognizing languages that surpass the computational power of the $\mathsf{AC}^{0}$ class, yet they remain simulable by threshold circuits with constant-depth, belonging to non-uniform $\mathsf{TC}^{0}$ complexity class. In a similar vein, establish that softmax-attention Transformers also belong to the non-uniform $\mathsf{TC}^{0}$ class. Subsequent work by builds upon these findings by introducing a similarity function to demonstrate that softmax-attention Transformers fall within the $\mathsf{L}$-uniform $\mathsf{TC}^{0}$ class. Further advancements by employ first-order logic and $\mathsf{MAJORITY}$ quantifiers to show that $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ circuits can simulate the behavior of these Transformers. In the context of practical applications, such as arithmetic operations and decision-making tasks, establish that unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$, Transformers with log-precision cannot efficiently solve arithmetic problems, equation-solving tasks, or context-free grammar (CFG) membership testing . These results underscore the limitations that Transformers face when applied to mathematical problems. However, recent efforts have aimed to overcome these constraints, introducing innovations such as looper Transformers , acceleration techniques , and other related approaches . These contributions aim to address some of the foundational limitations of Transformer architectures, allowing them to handle increasingly complex and mathematically intensive tasks.

Tensor Computation for High-order Representation.

Tensors outperform matrices in capturing higher-order relationships within data. Computing low-rank factorizations or approximations of tensors is critical in various computer science applications, including natural language processing , computer vision , computer graphics , security , and data mining . Tensors also play a key role in numerous machine learning tasks and other diverse domains .

Roadmap.

In Section 3, we introduce essential computational techniques and key definitions of Transformers that serve as the foundation for the discussions in the following sections. Section 4 discusses the computational complexity of conventional tensor attention Transformers. Section 5 provides a detailed $\mathsf{RoPE}$-based tensor attention circuit complexity analysis. Section 6 presents the hardness of tensor attention Transformers and $\mathsf{RoPE}$-based tensor attention Transformers derived from our study. We conclude in Section 7.

Preliminary

This section establishes the essential concepts and definitions. Section 3.1 introduces the fundamental notations that form the basis of analysis. Section 3.2 provides an in-depth exploration of float point number computation. Section 3.3 offers a comprehensive overview of computational complexity classes. Then, Section 3.4 presents essential techniques employed in tensor operations. Finally, Section 3.5 explores the fundamental components that constitute the $\mathsf{RoPE}$-based tensor attention Transformers.

2 Float Point Operations

We present basic concepts of the computational foundation. Initially, the exact definitions of float point numbers and the corresponding operations are outlined, which are indispensable in efficient tensor attention computations.

Given any real number or float point value $x$, the notation $\operatorname{round}_{p}(x)$ denotes the $p$-bit float point number closest to $x$. In cases where we have different numbers equidistant from $x$, the tie-breaking convention dictates that $\operatorname{round}_{p}(x)$ will be the even significand one.

Based on the foundational concepts mentioned above, we now introduce the key operations involved in tensor attention.

Let $x$ and $y$ represent two integers, then $x\oslash y$ defined as follows:

Let $\langle r_{1},k_{1}\rangle$ and $\langle r_{2},k_{2}\rangle$ all denoted as $p$-bit float points, then we have:

The operations mentioned above are capable of efficient hardware implementation, as demonstrated by the following lemmas:

If integer $0<p\leq\operatorname{poly}(n)$, then we say the conditions below are satisfied:

Part 2. We can execute $n$ $p$-bit float point numbers repeated multiplication using a constant depth $\operatorname{poly}(n)$ size uniform threshold circuit. The required depth for this iterated multiplication process is denoted as $d_{\otimes}$.

Part 3. We can approximate $n$ $p$-bit float point numbers sequential addition and rounding using a constant depth $\operatorname{poly}(n)$ size uniform threshold circuit. The depth needed for iterated addition is represented by $d_{\oplus}$.

For any integer $0<p\leq\operatorname{poly}(n)$ and any $p$-bit float point number $x$, it is computable to approximate most $2^{-p}$ relative error $\exp(x)$ using $\operatorname{poly}(n)$ size constant depth uniform threshold circuit. The depth required for this computation is denoted by $d_{\exp}$.

3 Circuit Complexity

In computational theory, a Boolean circuit, constructed using basic gates such as $\mathsf{AND}$, $\mathsf{OR}$, and $\mathsf{NOT}$, represents a core model of computation. A precise mathematical definition of this structure comes below.

An $n$ variables Boolean circuit is defined as $C_{n}:\{0,1\}^{n}\to\{0,1\}$ and is depicted by a directed acyclic graph (DAG). In this representation, logical gates such as $\mathsf{AND}$, $\mathsf{OR}$, and $\mathsf{NOT}$ correspond to the vertices of the graph. The input vertices, each linked to one of the $n$ Boolean variables, have an in-degree of 0, whereas non-input vertices derive their values from the outputs of preceding gates in the structure.

A Boolean circuit family $\mathcal{C}$ is said to recognize language $L\subseteq\{0,1\}^{*}$ if a Boolean circuit $C_{|z|}\in\mathcal{C}$ with $|z|$ variables exists, s.t., $C_{|z|}(z)=1$, iff $z\in L$, for every string $z\in\{0,1\}^{*}$.

The class $\mathsf{NC}^{i}$ is defined as the set of languages that are recognizable using Boolean circuits of size $O(\operatorname{poly}(n))$ and depth $O((\log n)^{i})$, with logical gates of bounded fan-in, including $\mathsf{NOT}$, $\mathsf{OR}$, and $\mathsf{AND}$ gates.

When Boolean circuits are permitted to incorporate gates such as $\mathsf{AND}$ and $\mathsf{OR}$ with unbounded fan-in, their ability to process languages becomes significantly enhanced. This development leads to the introduction of the complexity class $\mathsf{AC^{i}}$.

Languages which can be computed by the Boolean circuit of depth $O((\log n)^{i})$, size $O(\operatorname{poly}(n))$, unbounded fan-in gates, including $\mathsf{AND}$, $\mathsf{OR}$, $\mathsf{NOT}$, are contained in the class $\mathsf{AC}^{i}$.

The $\mathsf{MAJORITY}$ gates can simulate $\mathsf{AND}$, $\mathsf{NOT}$, $\mathsf{OR}$ gates, which yield an output of 1 if the majority of inputs are 1, and 0 otherwise. By incorporating $\mathsf{MAJORITY}$ gates, one can define a broader complexity class known as $\mathsf{TC}^{i}$.

If we have languages are recognizable by $O(\operatorname{poly}(n))$ size Boolean circuits of $O((\log n)^{i})$ depth, and unbounded fan-in gates, including $\mathsf{MAJORITY}$, $\mathsf{NOT}$, $\mathsf{OR}$, and $\mathsf{AND}$ gates. If half of the inputs are 1, the $\mathsf{MAJORITY}$ gate will output 1.

The class $\mathsf{TC}^{i}$ contains languages that are recognizable by Boolean circuits of size $O(\operatorname{poly}(n))$, depth $O((\log n)^{i})$, and gates with unbounded fan-in, including $\mathsf{NOT}$, $\mathsf{OR}$, $\mathsf{AND}$, and $\mathsf{MAJORITY}$ gates. A $\mathsf{MAJORITY}$ gate outputs one if more than half of its inputs are one.

As Definition 3.12 shows, $\mathsf{MOD}$ or $\mathsf{THRESHOLD}$ gates (for prime moduli) can replace $\mathsf{MAJORITY}$ gates. Boolean circuits employing such gates are collectively referred to as threshold circuits.

Next, we formally introduce the class $\mathsf{P}$.

A language is considered to be in $\mathsf{P}$ if it can be decided by a deterministic Turing machine within polynomial time of input size.

The hierarchical relationships among certain circuit families are encapsulated in the following well-known result.

Non-uniform circuit families, characterized by their lack of consistent structural design across varying input sizes, are theoretically capable of addressing undecidable problems. Nevertheless, their impracticality arises from the infinite length required for their description. In contrast, uniform circuit families, which adhere to a systematic computational model, hold greater relevance in the study of complexity and formal language theory. We begin with the definition of $\mathsf{L}$-uniformity.

Then, the $\mathsf{DLOGTIME}$-uniformity and examine its correspond to $\mathsf{L}$-uniformity will be introduced.

The concept of $\mathsf{DLOGTIME}$-uniformity aligns with that of $\mathsf{L}$-uniformity, except in smaller circuit classes that do not have the capability to imitate the constructing machine. Further exploration of uniformity concepts can be found in . Within this paper, references to uniform $\mathsf{TC}^{0}$ pertain specifically to $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$.

4 Tensor Operation Analysis Techniques

We first define operations such as the Kronecker product, a matrix operation that takes two matrices of any size and produces a block matrix. Unlike standard matrix multiplication, it is useful for introducing and analyzing tensor attention. Then, we introduce some key techniques for applying tensor attention to RoPE.

Fact 3.23 indicates that the order of tensor operation and matrix multiplication can be swapped, enabling computation in the lower dimension first to reduce complexity.

For any $i_{1},i_{2}\in[n],j\in[d]$, we have

where the initial step involves the application of matrix multiplication, followed by the utilization of Definition 3.21 in the second step. Subsequently, the third step employs Definition 3.20, while the fourth step simplifies the expression through fundamental algebraic principles. The fifth step re-engages matrix multiplication, and the concluding step leverages Definition 3.21 once more. ∎

5 Transformer Block

With the mathematical foundation in place, this section outlines the key components of the $\mathsf{RoPE}$-based tensor attention Transformers architecture, starting with the softmax operation, a fundamental element of Transformer.

One of the pivotal advancements in contemporary Transformer architectures is $\mathsf{RoPE}$, which employs a rotation matrix as its foundation:

This fundamental rotation matrix is generalized to encode the relative positions within a sequence, facilitating the embedding of positional context.

Noted $j$ represents position index within input sequence and $i$ denotes token index. The relative rotation matrix is then expressed as:

where the angular frequencies $\theta_{1},\cdots,\theta_{d/2}$ are all predefined. More about selecting $\theta$, consult Equation (15) from .

Leveraging rotation matrices mentioned above, $\mathsf{RoPE}$-based tensor attention embeds positional relation intrinsically within the computational process of attention. Now, we are about to introduce the $\mathsf{RoPE}$-based tensor attention. First, we introduce the parameters and input.

Then, based on Definition 3.21, we define $\mathsf{RoPE}$-based tensor attention matrix in the following way.

by applying Fact 3.23, we finally define the $i$-th $\mathsf{RoPE}$ tensor attention layer $\mathsf{Attn}_{i}$ as

Then, we introduce a single tensor attention layer.

Next, we can also integrate multi-layer attention and the additional mechanism mentioned above to construct a comprehensive Transformer.

where $\circ$ denotes the composition of functions.

Subsequently, we define two categories of $g_{i}$ functions. Start with the layer normalization.

where $\mu_{i}:=\sum_{j=1}^{d}\frac{X_{i,j}}{d}$, and $\sigma_{i}^{2}:=\sum_{j=1}^{d}\frac{(X_{i,j}-\mu_{i})^{2}}{d}$.

The second category is the multilayer perceptron.

The foundation of modern Transformer is built upon these layered architectures, which integrate float point computations, attention, and rotation matrix to an exceptionally efficient framework for sequential computation.

Complexity of Tensor Attention Transformer

We now formally turn our attention to investigating the circuit complexity of the tensor attention layer and the multi-layer tensor attention Transformer, emphasizing their computability within the complexity class $\mathsf{TC}^{0}$. Section 4.1 delves into matrix operations. Section 4.2 addresses the computation of a single tensor attention layer. Section 4.3 provides an in-depth examination of the entire tensor attention mechanism. Lastly, Section 4.4 presents our principal findings regarding the circuit complexity bounds for the tensor attention Transformer. These results establish the foundation for the main theorem concerning Transformer expressiveness.

We demonstrate that fundamental matrix multiplication is efficiently evaluatable within $\mathsf{TC}^{0}$.

The circuit size is polynomial in $n$, as each operation uses a polynomial-sized circuit, and $n_{1},n_{2},d\leq\operatorname{poly}(n)$.

The circuit size remains polynomial in $n$ because $n_{1},n_{2},d\leq\operatorname{poly}(n)$ and every operation utilizes a polynomial-sized circuit.

The circuit size is polynomial in $n$ because $n_{1},n_{2},d\leq\operatorname{poly}(n)$, and each individual operation can be evaluated by a polynomial-sized circuit.

2 Single Tensor Attention Layer

Here, we examine the complexity of the single layer of the tensor attention.

As per Part 3 of Lemma 3.4, $D:=A{\bf{1}}n$ is evaluated with $\operatorname{poly}(n)$ size uniform threshold circuit of depth $d{\oplus}$.

The total depth required for computing $\mathsf{Attn}_{i}(X):=D^{-1}AV$ is therefore:

3 Multi-layer Tensor Attention

This section analyzes the computation of multi-layer tensor attention in a Transformer.

4 Circuit Complexity Bound of Tensor Attention

The subsequent discussion focuses on presenting the main result regarding the circuit complexity bound for tensor attention Transformers.

Assume that for every $i\in[m]$, the function $g_{i}$ in $\mathsf{TF}$ is evaluatable by $\operatorname{poly}(n)$ size uniform threshold circuit of constant $d_{g}$ depth. As described in Definition 3.31, we can approximate the $\mathsf{RoPE}$-based tensor attention Transformer $\mathsf{TF}$ by a uniform $\mathsf{TC}^{0}$ circuit family, when $d\leq O(n)$, $p\leq\operatorname{poly}(n)$, and $m\leq O(1)$.

With constant $m$, and Lemma 4.6, the depth of the circuit computing $\mathsf{TF}(X)$ is

and the $\operatorname{poly}(n)$ circuit size. Thus, a uniform $\mathsf{TC}^{0}$ circuit family can simulate this computation.

Above Theorem 4.7, we establish that, unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$, a constant depth tensor attention with $\operatorname{poly}(n)$ size, and $\operatorname{poly}(n)$-precision can be approximated by a $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ circuit family. While tensor attention Transformers exhibit strong empirical performance, this result indicates inherent limits in their expressivity when viewed through the framework of circuit complexity. These constraints are examined further in Section 6, in tandem with the analysis from Section 5.

Complexity of 𝖱𝗈𝖯𝖤𝖱𝗈𝖯𝖤\mathsf{RoPE}-based Tensor Attention Transformer

This section presents key results concerning the circuit complexity of fundamental operations within $\mathsf{RoPE}$-based tensor attention computations. Section 5.1 investigates trigonometric functions, which play a crucial role in rotary position embeddings, while Section 5.2 focuses on the $\mathsf{RoPE}$-based tensor attention matrix computation. Section 5.3 delves into the individual $\mathsf{RoPE}$-based tensor attention layer, whereas Section 5.4 explores other components beyond the attention layer. In Section 5.5, the complete $\mathsf{RoPE}$-based tensor attention mechanism is detailed. Finally, Section 5.6 presents the primary results regarding the circuit complexity bounds for $\mathsf{RoPE}$-based tensor attention, forming the foundation for the essential theorem on $\mathsf{RoPE}$-based Tensor Attention Transformer expressiveness.

Here, we outline the efficient calculation of fundamental trigonometric functions that are critical for $\mathsf{RoPE}$ embeddings via threshold circuits. The next lemma plays a central role:

For any $p\leq\operatorname{poly}(n)$, the values of $\sin(x)$ and $\cos(x)$ for a float point number $x$ of $p$ bits with a relative error bounded by $2^{-p}$ are evaluatable by $\operatorname{poly}(n)$ size uniform threshold circuit with constant depth. Let $d_{\triangle}$ denote the maximum depth required to calculate both $\cos(x)$ and $\sin(x)$.

2 𝖱𝗈𝖯𝖤𝖱𝗈𝖯𝖤\mathsf{RoPE}-based Tensor Attention Matrix

The following section builds on what we already know about the computation of the $\mathsf{RoPE}$-based tensor attention matrix.

For every $j_{1},j_{2},j_{3}\in[n]$, the matrix element $A_{j_{1},j_{2}+(j_{3}-1)d}$ is evaluated according to the formula in Definition 3.28.

As indicated by Lemma 5.1, the entries of $R_{j_{1}-j_{2}}$ are evaluatable by a size $\operatorname{poly}(n)$ depth $d_{\triangle}$ uniform threshold circuit. Since $n$ is polynomial, all entries of $R_{j_{1}-j_{2}}$ are evaluatable simultaneously with the same circuit size and depth. This holds true for $R_{j_{1}-j_{3}}$ and $R_{j_{1}-j_{2}}$ as well.

The exponential function $\exp()$ can be evaluated using Lemma 3.6 by a size $\operatorname{poly}n$ depth $d_{\exp}$ uniform threshold circuit.

Thus, the total required depth to compute the matrix $A$ is:

3 Single 𝖱𝗈𝖯𝖤𝖱𝗈𝖯𝖤\mathsf{RoPE}-based Tensor Attention Layer

This section provides a detailed examination of the $\mathsf{RoPE}$-based tensor attention layer, with an emphasis on tracking the circuit depth requirements throughout the computation process.

Because parallel operations can be conducted for each element, the attention operation $\mathsf{Attn}(X)$ can be evaluated by a uniform threshold circuit with the required depth and size.

4 Building Blocks other than 𝖱𝗈𝖯𝖤𝖱𝗈𝖯𝖤\mathsf{RoPE}-based Tensor Attention Layer

According to Definition 3.31, the definition of the Multi-layer $\mathsf{RoPE}$-based Transformer is provided, which integrates $\mathsf{RoPE}$-based self-attention layers together with supplementary components, such as layer normalization and MLP. This section subsequently addresses the circuit complexity associated with these mechanisms.

The analysis begins with an investigation of the complexity pertaining to the MLP layer.

Next, we will turn our attention to the complexity of the LN layer.

5 Multi-layer 𝖱𝗈𝖯𝖤𝖱𝗈𝖯𝖤\mathsf{RoPE}-based Tensor Attention

We now describe the computation of the multi-layer $\mathsf{RoPE}$-based tensor attention Transformer.

Under the given assumption, for every $i\in[m]$, $g_{i}$ can be evaluated by $\operatorname{poly}(n)$ size uniform threshold circuit having constant $d_{g}$ depth.

6 Circuit Complexity of 𝖱𝗈𝖯𝖤𝖱𝗈𝖯𝖤\mathsf{RoPE}-based Tensor Attention

Here, we present the central contribution of this paper, which establishes the circuit complexity for the $\mathsf{RoPE}$-based tensor attention.

Assume that $\forall i\in[m]$, $g_{i}$ in $\mathsf{TF}$ can be computed using $\operatorname{poly}(n)$ size uniform threshold circuit of constant depth $d_{g}$. The $\mathsf{RoPE}$-based tensor attention $\mathsf{TF}$, as defined in Definition 3.31, is simulatable by uniform $\mathsf{TC}^{0}$ circuit family when $d\leq O(n),p\leq\operatorname{poly}(n),$ and $m\leq O(1)$.

According to Lemma 5.6, we have $m=O(1)$, the $O(\operatorname{poly}(n))$ bounded circuit used to compute $\mathsf{TF}(X)$ has a depth given by

which bounded by $O(\operatorname{poly}(n))$. Thus, based on the definition of $\mathsf{TC}^{0}$, it follows that the uniform $\mathsf{TC}^{0}$ circuit family can approximate $\mathsf{RoPE}$-based tensor attention Transformer.

In Theorem 4.7 and Theorem 5.7, unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$, a $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ circuit family can emulate both tensor attention Transformers and $\mathsf{RoPE}$-based tensor attention Transformers, which are defined by constant depth, $\operatorname{poly}(n)$ precision, and $\operatorname{poly}(n)$ size. This finding suggests that, notwithstanding the empirical success of these models, their expressive capabilities are intrinsically constrained when analyzed through the lens of circuit complexity. The subsequent section will delve deeper into these limitations.

Hardness

This section delineates two fundamental problems, accompanied by their respective hardness results. The fixed membership problem is introduced in Section 6.1, while the closure problem is defined in Section 6.2. Section 6.3 presents the four principal hardness results.

The fixed membership problem, as originally formulated in , is thoroughly defined in this section. A formal exposition of its definition is provided as the foundation for subsequent analysis.

The fixed membership problem is defined as follows:

Input: A fixed morphism $h$: $A^{+}\to S$, a fixed set $P\subseteq F(S)$ and finite words $u,v\in A^{+}$

$F(S)$ denotes the collection of finite subsets of $S$.

The fixed membership problem for recognizing morphisms over finite words is $\mathsf{NC}^{1}$-complete.

In this section, attention is shifted to the $(A_{F,r})^{*}$ closure problem, as introduced in .

Let $L$ be a language, the kleene star of $L$, denoted by $L^{*}$, is the set of all finite concatenations of strings from $L$, defined as:

Let $(A,\circ)$ denote a finite monoid.For convenience, $(A,\circ)$ is abbreviated as $A$. A natural homomorphism $v:A^{*}\rightarrow A$ maps each word $w$ to its corresponding valuation $v(w)$ in the monoid $A$. Let $F\subseteq A$ and $r$ be a positive integer. The language $A_{F,r}\subseteq A^{*}$ is characterized by $A_{F,r}=\{w\in A^{*}\mid\|w\|\leq r,v(w)\in F\}$. The $(A_{F,r})^{*}$ closure problem refers to the decision problem aimed at determining whether a given string $s$ belongs to $(A_{F,r})^{*}$.

Assume that $A$ is a nonsolvable monoid. Then, there exists a group $F\subseteq A$ and a constant $r>0$ such that the $(A_{F,r})^{*}$ closure problem is $\mathsf{NC}^{1}$-complete.

3 Hardness Result

This part presents four crucial findings concerning tensor attention Transformers and $\mathsf{RoPE}$-based tensor attention Transformers.

If $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, $O(1)$ layers $\mathsf{RoPE}$-based tensor attention Transformer with $d\leq O(n)$ hidden dimension, $\operatorname{poly}(n)$ precision is incapable of solving the fixed membership problem.

The proof follows from the combination of Theorem 5.7, which provides a circuit complexity bound for $\mathsf{RoPE}$-based tensor attention Transformers, and Proposition 6.2, which establishes that the fixed membership problem for recognizing morphisms over finite words is $\mathsf{NC}^{1}$-complete. Additionally, Fact 3.15, which outlines the hierarchy of circuit families, is also applied here. This completes the proof. ∎

Unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$, it is not possible for a $O(1)$ layers tensor attention Transformer with $d\leq O(n)$ hidden dimension and $\operatorname{poly}(n)$ precision to address the fixed membership problem.

The result is derived by combining Theorem 4.7 (which provides the circuit complexity bound for tensor attention Transformers), Proposition 6.2 (demonstrating the $\mathsf{NC}^{1}$-completeness of the fixed membership problem), and Fact 3.15 (pertaining to the structure of circuit families). As a result, this proof is complete. ∎

Assuming $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, a $O(1)$ layers tensor attention Transformer with $d\leq O(n)$ hidden dimension, and $\operatorname{poly}(n)$ precision is not capable of solving the $(A_{F,r})^{*}$ closure problem.

This follows directly from Theorem 5.7, which establishes the circuit complexity bound for $\mathsf{RoPE}$-based tensor attention Transformers, and Theorem 6.5, which asserts that the $(A_{F,r})^{*}$ closure problem is $\mathsf{NC}^{1}$-complete. Additionally, Fact 3.15 concerning the hierarchy of circuit families is also utilized. Thus, the proof is complete. ∎

Unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$, it is not possible for a tensor attention Transformer with $O(1)$ layers, $\operatorname{poly}(n)$-precision, and $d\leq O(n)$ hidden dimension to solve the $(A_{F,r})^{*}$ closure problem.

Theorem 4.7 provides this result upon application, which provides the circuit complexity bound for tensor attention Transformers, Theorem 6.5, which proves the $\mathsf{NC}^{1}$-completeness of the $(A_{F,r})^{*}$ closure problem, and Fact 3.15, which discusses the hierarchy of circuit families. Therefore, the proof is concluded. ∎

Conclusion

It is important to note that our analysis is primarily confined to forward computations and assumes constant-depth nonlinear activation functions. This leaves the impact of training dynamics, alternative activation functions, and different formulations of tensor attention unexplored. Future work could expand on this analysis to investigate alternative positional encoding schemes, more advanced attention models, or different activation functions, potentially uncovering whether these complexity boundaries hold for other Transformer variants. Ultimately, the findings presented here reveal a fascinating discrepancy between tensor attention models’ theoretical limitations and their empirical performance. Understanding how these models achieve practical effectiveness despite their theoretical shortcomings could stimulate the development of new, theoretically robust design principles. Such insights are essential for advancing neural network architectures that maintain a balance between rigorous theoretical foundations and empirical success, fostering the creation of more scalable and powerful models.

References