Circuit Complexity Bounds for Visual Autoregressive Model

Introduction

Visual generation has seen widespread applications across various domains, including image restoration , augmented reality , medical imaging , and creative industries such as game development . By generating realistic and diverse images from textual descriptions or other forms of input, visual generation models are transforming how machines perceive and produce visual content. Among the most popular models for visual generation are Variational AutoEncoders (VAE) , Generative Adversarial Networks (GAN) , Diffusion models , and Flow-based models . These models have made notable progress in producing high-quality, high-resolution, and diverse images, expanding the potential of visual generation through improvements in realism, diversity, and fidelity.

However, the introduction of the Visual AutoRegressive model (VAR) represents a significant shift in the paradigm in this field. Instead of the traditional “next-token prediction”, the VAR model adopts a coarse-to-fine “next-scale prediction” approach. Through this innovative approach, the VAR model is able to capture visual distributions more effectively, exceeding the performance of diffusion transformers in image generation tasks. Additionally, VAR’s zero-shot generalization capability spans multiple tasks, including image inpainting and manipulation. These results suggest that VAR offers a promising direction for autoregressive models in visual generation.

As the VAR model demonstrates its impressive performance, it is crucial to explore the limitations of the expressiveness of the VAR model. Up to now, the expressiveness from a circuit complexity perspective of the VAR model remains underexplored. This gap raises an important question:

What are the limitations of the expressive power of the VAR model in terms of circuit complexity?

To explore this issue, we apply circuit complexity theory, which offers valuable tools for analyzing the computational resources needed for specific tasks. By representing the VAR model as complexity circuits, we can systematically evaluate their capabilities and determine the lower bounds of the problems they can address.

In this work, we present a comprehensive theoretical investigation into the circuit complexity bounds of the VAR models. Our approach involves analyzing and formulating the architecture of the VAR model and analyzing the computational complexity of its components, such as up-interpolation layers, convolution layers, transformer blocks, etc. Finally, we show that uniform $\mathsf{TC}^{0}$ circuits can efficiently simulate these models.

The primary contributions of our work are summarized below:

As far as we know, this is the first paper to present a mathematical formulation of the Visual AutoRegressive model (Section 4).

We prove that $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ circuit family can simulate any Visual AutoRegressive model with $O(1)$ depth, $\operatorname{poly}(n)$ size, and $\operatorname{poly}(n)$ precision (Theorem 5.11).

Roadmap. Section 2 offers a summary of the related works. Section 3 introduces the necessary notations and definitions for the subsequent analysis. In Section 4, we present the mathematical formulation of the VAR model. Section 5 details the circuit complexity results for the VAR model. Section 6 presents the conclusions of our work.

Related Work

In computational theory, circuit complexity refers to the classification and analysis of computational problems based on the size and depth of Boolean circuits required to solve them, aiming to understand the inherent difficulty of problems in terms of circuit resources. Crucial to the study of computational complexity is the class $\mathsf{AC}^{0}$, which consists of decision problems solvable by constant-depth Boolean circuits with unbounded fan-in and the logic gates $\mathsf{AND}$, $\mathsf{OR}$, and $\mathsf{NOT}$; $\mathsf{TC}^{0}$, which extends $\mathsf{AC}^{0}$ by incorporating $\mathsf{MAJORITY}$ gates; $\mathsf{NC}^{1}$ represents the class of problems solvable in parallel by circuits with a depth of $O(\log(n))$, where the gate arity is bounded. These three complexity classes form a hierarchical structure: $\mathsf{AC}^{0}\subset\mathsf{TC}^{0}\subseteq\mathsf{NC}^{1}$ . However, the question of whether $\mathsf{TC}^{0}=\mathsf{NC}^{0}$ remains unresolved.

Circuit Complexity has important applications in understanding the capabilities of deep learning models . Specifically, investigates the computational boundaries of self-attention, demonstrating that, despite its effectiveness in NLP tasks, it has difficulty modeling periodic finite-state languages and hierarchical structures without scaling up the number of layers or attention heads. delves into the theoretical underpinnings of Chain-of-Thought (CoT) within LLMs, demonstrating its ability to solve complex tasks like arithmetic and dynamic programming through sequential reasoning process, despite the limitations of bounded-depth Transformers. Recently, shows that Mamba and State-space Models (SSMs) have the same computational limits as Transformers, residing within the $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ complexity class.

To the best of our knowledge, circuit complexity theory has not yet been used to analyze the computational constraints of Visual AutoRegressive models.

2 Limitation of Transformer Architecture

Transformer Architecture has shown remarkable success in various fields, particularly in natural language processing, reinforcement learning, and computer vision. By leveraging self-attention mechanisms to capture long-range dependencies, the Transformer has become the architecture of choice for applications such as machine translation and image generation . Recently, a series of studies have shed insight into the reasoning limitations of Transformer Architecture . Specifically, showed that a generalized form of hard attention can recognize languages that go beyond what the $\mathsf{AC}^{0}$ class can compute, with the $\mathsf{TC}^{0}$ class serving as an upper bound for the formal languages it can identify. The study by established that softmax-transformers (SMATs) are included in the non-uniform $\mathsf{TC}^{0}$ class. As a next step, demonstrated that SMATs belong to $\mathsf{L}$-uniform $\mathsf{TC}^{0}$ class. Recently, demonstrated that average-hard attention transformers (AHATs), without approximation, and SMATs with floating-point precision of $O(\operatorname{poly}(n))$ bits, as well as SMATs with at most $2^{-O(\operatorname{poly}(n)}$ absolute error, can all be classified in the $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ class.

3 Visual Generation Models

Visual generation models have seen significant progress over the past few years, with key advancements in the following mainstream architecture:

AutoRegressive models for visual generation require the encoding of 2D images into 1D token sequences. Early works in this area, such as PixelCNN and Pixelsnail , demonstrated the ability to generate pixels in a row-by-row, raster-scan fashion. More later, there are many works that generate image tokens in the raster-scan order, like . Specifically, VQ-GAN uses a GPT-2 decoder-only transformer for image generation. VQVAE-2 and RQ-Transformer also adopt this raster-scan approach but incorporate additional scales or stacked codes. Recently, proposed Visual AutoRegressive (VAR) modeling, a new approach to autoregressive image generation, which redefines the process by predicting the next scale in a coarse-to-fine manner. The VAR model not only improves upon traditional methods but also surpasses diffusion transformers in terms of scalability, inference speed, and image quality.

Diffusion Models.

Diffusion Models have earned recognition for generating high-resolution images by gradually removing noise, exemplified by models such as DiT and U-ViT . Typically, these models apply a series of diffusion stages to transform random noise into a coherent image, learning the underlying data distribution through a probabilistic framework. Recent advancements in diffusion-based image generation have focused on improving learning and sampling , latent learning and architecture .

Preliminary

The notations used in this paper are introduced in Section 3.1. Section 3.2 explains the basics of circuit complexity classes. Section 3.3 introduces key simulations of floating-point operations, which will be used in later sections for the proofs.

2 Key Concepts in Circuit Complexity

We discuss several circuit complexity classes, starting with the concept of a boolean circuit.

Therefore, we can proceed to define the languages recognizable by certain families of Boolean circuits, considering their structural constraints, gate types, and depth. These factors determine the computational power of the circuits in each family.

Let $L\subseteq\{0,1\}^{*}$ denote a language. $L$ can be recognized by a Boolean circuits family $\mathcal{C}$ if, for every string $x\in\{0,1\}^{*}$, a Boolean circuit $C_{|x|}\in\mathcal{C}$ exists, which takes $x$ as input. This circuit has an input length of $|x|$, and $x\in L$ if and only if $C_{|x|}(x)=1$ holds.

Next, the concept of complexity classes will be given, which categorizes computational problems based on their inherent difficulty, determined by the resources—such as time or space—required to solve them. In this context, different complexity classes impose constraints on the resources of Boolean circuits, which can be further characterized by factors such as circuit size, depth, number of fan-in, and gate types. We introduce the complexity classes as the following

A language belongs to $\mathsf{NC}^{i}$ class if it can be decided by a $\operatorname{poly}(n)$ size, $O(\log^{i}(n))$ depth boolean circuits equipped with restricted fan-in basic gates $\mathsf{AND}$, $\mathsf{OR}$ and $\mathsf{NOT}$ gates.

A language belongs to $\mathsf{AC}^{i}$ class if it can be decided by a $\operatorname{poly}(n)$ size, $O(\log^{i}(n))$ depth boolean circuits equipped with no-limit fan-in basic gates $\mathsf{AND}$, $\mathsf{OR}$ and $\mathsf{NOT}$ gates.

A language belongs to $\mathsf{TC}^{i}$ class if it can be decided by a $\operatorname{poly}(n)$ size, $O(\log^{i}(n))$ depth boolean circuits equipped with no-limit fan-in basic gates $\mathsf{AND}$, $\mathsf{OR}$, $\mathsf{NOT}$ and $\mathsf{MAJORITY}$ gates.

A language belongs to $\mathsf{P}$ class if it can be decided by a deterministic Turing machine in polynomial time with respect to its input size

Note that the question of whether $\mathsf{TC}^{0}\subsetneq\mathsf{NC}^{1}$ remains an open problem in circuit complexity.

In theoretical computer science, the uniformity of a complexity class refers to whether the circuit family in question can be constructed by a uniform algorithm, i.e., an algorithm that outputs a description of the circuit for any input size. Specifically, $\mathsf{L}$-uniformty requires a Turing machine that uses $O(\log(n))$ space to output a circuit $C$ which can recognize a given language $L\subseteq\{0,1\}^{*}$. Moreover, $\mathsf{DLOGTIME}$-uniformity stipulates that a random access Turing machine must produce a circuit $C$ that recognizes a given language $L\subseteq\{0,1\}^{*}$. Except in the case of small circuit complexity classes, where circuits are incapable of simulating the machines that create them, $\mathsf{DLOGTIME}$-uniformity is the same as $\mathsf{L}$-uniformity. For further discussion on various notions of uniformity, see .

Throughout this work, any reference to a uniform $\mathsf{TC}^{0}$ should be understood as referring to a $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$.

3 Basic Tools

In this section, we first define floating-point numbers and then illustrate a series of operations involving them. Finally, we analyze the circuit complexity associated with these operations, which is essential in the later proof.

Then, we move forward to define the round operation of float point numbers.

Given a floating point number $x$, we use $\operatorname{round}_{p}(x)$ to denote the nearest number to $x$ which is $p$-bit floating-point.

For the definitions of addition, multiplication, division, comparison, and floor operations on floating-point numbers as outlined in Definition 3.3, refer to . In this paper, we introduce the corresponding circuit complexity classes to which these operations belong.

Assume the precision $p\leq\operatorname{poly}(n)$. Then we have:

Part 1. Given two $p$-bits float point numbers $x_{1}$ and $x_{2}$. Let the addition, division, and multiplication operations of $x_{1}$ and $x_{2}$ be outlined in . Then, these operations can be simulated by a size bounded by $\operatorname{poly}(n)$ and constant depth bounded by $d_{\rm std}$ $\mathsf{DLOGTIME}$-uniform threshold circuit.

Part 2. Given $n$ $p$-bits float point number $x_{1},\dots,x_{n}$. The iterated multiplication of $x_{1},x_{2}\dots,x_{n}$ can be simulated by a size bounded by $\operatorname{poly}(n)$ and constant depth bounded by $d_{\otimes}$ $\mathsf{DLOGTIME}$-uniform threshold circuit.

Part 3. Given $n$ $p$-bits float point number $x_{1},\dots,x_{n}$. The iterated addition of $x_{1},x_{2}\dots,x_{n}$ can be simulated by a size bounded by $\operatorname{poly}(n)$ and constant depth bounded by $d_{\oplus}$ $\mathsf{DLOGTIME}$-uniform threshold circuit. To be noticed, there is a rounding operation after the the summation is completed.

Then, we show a lemma stating that we can use a $\mathsf{TC}^{0}$ circuit to simulate the approximated exponential function.

Assume the precision $p\leq\operatorname{poly}(n)$. Given any number $x$ with $p$-bit float point, the $\exp(x)$ function can be approximated by a uniform threshold circuit. This circuit has a size bounded by $\operatorname{poly}(n)$ and a constant depth $d_{\rm exp}$, and it guarantees a relative error of at most $2^{-p}$.

Finally, we present a lemma stating that we can use a $\mathsf{TC}^{0}$ circuit to simulate the approximated square root operation.

Model Formulation

Section 4.1 provides the definitions related to the VAR model. In Section 4.2, we present the mathematical formulation of the components involved in the token map generation phase of the VAR model. In Section 4.3, we present the mathematical formulation of the components involved in the feature map reconstruction phase of the VAR model. In Section 4.4, we present the mathematical formulation of the components involved in the VQ-VAE Decoder phase of the VAR model.

We give the following notations in our setting.

$c_{\rm vae}$ is the number of vectors in the Codebook (i.e., the size of the Codebook),

$d_{\rm vae}$ is the dimensionality of each vector.

2 Phase 1: VAR Transformer

VAR uses the VAR Transformer to convert the initial tokens of the generated image into several pyramid-shaped token maps. And in the token maps generation phase, the token maps for the next scale, $M_{k+1}$, are generated based on the previous $k$ token maps ${M_{1},\dots,M_{k}}$. This phase has the main modules as the following:

VAR performs an upsampling operation on the $(i)$-th token map, adjusting its size to that of the $(i+1)$-th token map, before feeding the $k$ token maps into the VAR Transformer. Specifically, VAR employs an upsampling method using interpolation for the image. Here, we define the up-interpolation blocks:

The Up-Interpolation layer is defined as follows:

Let $W:\mathsf{F}_{p}^{h\times w\times c}\to\mathsf{F}_{p}^{h\times w\times c}$ be a bicubic spline kernel as defined in 4.2.

We use $\phi_{\rm up}:\mathsf{F}_{p}^{h\times w\times c}\to\mathsf{F}_{p}^{h^{\prime}\times w^{\prime}\times c}$ to denote the up-interpolation operation then we have $Y=\phi_{\rm up}(X)$. Specifically, for $i\in[h^{\prime}],j\in[w^{\prime}],l\in[c]$, we have

Transformer Blocks.

After the up-sample process, the generated token maps above will be input into the Transformer to predict the next token map. Here, we define several blocks for the VAR Transformer.

Then, we can move forward to define the attention matrix.

In the next step, we proceed to define the single attention layer.

Then, we move forward to define the multilayer perceptron layer.

Given an input matrix $X\in\mathsf{F}_{p}^{n\times d}$. Let $i\in[n]$. We use $g^{\rm MLP}$ to denote the MLP layer. Specifically, we have

We then proceed to define the layer-wise normalization layer.

Given an input matrix $X\in\mathsf{F}_{p}^{n\times d}$. Let $i\in[n]$. We use $g^{\rm LN}$ to denote the LN layer. Specifically, we have

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

Then, we can combine multiple attention layers with other components (up-interpolation layers, multilayer perceptron layers, layer-wise normalization layers) to create a complete VAR Transformer architecture.

In this expression, $\circ$ stands for functional composition.

3 Phase 2: Feature Map Reconstruction

In phase 2, VAR will transform the generated token maps into feature maps. This phase has the following main modules:

The VAR performs upsampling on token maps of different sizes, scaling them to the size of the final output feature map. In this process, VAR will use the up-interpolation blocks defined in Definition 4.3. To mitigate information loss during token map up-scaling, VAR employs convolution blocks to post-process the up-scaled token maps. We define the convolution blocks as the following:

where $Y$ is the output feature map of the convolution layer, and $b$ is the bias term of the kernel.

4 Phase 3: VQ-VAE Decoder process

VAR will use the VQ-VAE Decoder Module to reconstruct the feature map generated in Section 4.3 into a new image. The Decoder of VQ-VAE has the following main modules:

In the VQVAE decoder, the ResNet block, which includes two (or more) convolution blocks, plays a crucial role in improving the model’s ability to reconstruct high-quality outputs. The convolution blocks help capture spatial hierarchies and patterns in the data, while the residual connections facilitate better gradient flow and allow the model to focus on learning the residuals (differences) between the input and output. The definition of convolution block is given in Definition 4.10.

Attention Blocks.

The Attention block helps the Decoder fuse information from different locations during the generation process, which can significantly improve the clarity and detail of the generated images. When applied to a feature map, the attention mechanism computes attention scores for all pairs of pixels, capturing their pairwise relationships and dependencies. The definitions of blocks in attention are given in Section 4.2.

Up Sample Blocks.

The VQ-VAE decoder uses Up-Sample Blocks to progressively increase the spatial resolution of the latent representation. The Up-Sample Blocks in VQVAE combine up-interpolation and convolution blocks to restore the spatial dimensions of the feature maps, facilitating the reconstruction of the high-resolution output image. The convolution block has already been defined in Definition 4.10, and the up-interpolation block has already been defined in Definition 4.3.

Complexity of VAR Models

We present the critical findings on the circuit complexity of crucial operations in the computation of VAR models. In Section 5.1, we analyze the up-interpolation blocks. In Section 5.2, we examine the matrix operations. In Section 5.3, we proceed to study the single attention layer. In Section 5.4, we move forward to compute the MLP layer and LN layer. In Section 5.5, we study the convolution layer computation. In Section 5.6, We show that we can use a uniform $\mathsf{TC}^{0}$ circuit to model the VAR Transformer. In Section 5.7, we show that we can use a uniform $\mathsf{TC}^{0}$ circuit to model the feature map reconstruction layer. In Section 5.8, we show that we can use a uniform $\mathsf{TC}^{0}$ circuit to model the VQ-VAE Decoder. Finally, we show our main result in Section 5.9.

In this section, we can show that the up-interpolation layers can be computed in $\mathsf{TC}^{0}$.

Firstly, we begin to compute every entry in the targeted feature map $Y$. For $i\in[h^{\prime}],j\in[w^{\prime}],l\in[c]$, we have

By using the result of Part 1 of Lemma 3.5, we can apply a constant depth $2d_{\rm std}$ uniform threshold circuit to compute each product $W(s)\cdot X_{\frac{ih}{h^{\prime}}+s,\frac{jw}{w^{\prime}}+t,q}\cdot W(t)$. Since the products for different $s$ and $t$ can be parallel computed, the uniform threshold circuit’s depth for all products $W(u)\cdot X_{\frac{ih}{h^{\prime}}+s,\frac{jw}{w^{\prime}}+t,q}$ stays $2d_{\rm std}$.

Then, by using the result of Part 3 in Lemma 3.5, we can use a $d_{\oplus}$ depth uniform threshold circuit to model the sum operation:

2 Computing Attention Matrix

Let us begin by recalling that the matrix multiplication of two matrices belongs to $\mathsf{TC}^{0}$.

3 Computing Single Attention Layer

Subsequently, matrix operations can be applied to compute the attention matrix.

Assume the precision $p\leq\operatorname{poly}(n)$, then we can use a size bounded by $\operatorname{poly}(n)$ and constant depth $3(d_{\rm std}+d_{\oplus})+d_{\rm exp}$ uniform threshold circuit to compute the attention matrix $A$ defined in Definition 4.4.

Based on Lemma 5.2, we can compute the matrix product $W_{Q}W_{K}^{\top}$ by using a size bounded by $\operatorname{poly}(n)$ and constant depth $d_{\rm std}+d_{\oplus}$ uniform threshold circuit.

Then, we move forward to compute the scalar product, which is

And by using the result of Lemma 5.2, we can compute $t_{i,j}$ by applying a uniform threshold circuit, where the circuit has a polynomial-size bounded by $\operatorname{poly}(n)$ and constant depth $2(d_{\rm std}+d_{\oplus})$.

In the next step, from Lemma 3.6, we can compute the exponential function $A_{i,j}=\exp(t_{i,j})$ by applying a size bounded by $\operatorname{poly}(n)$ and constant depth $d_{\rm exp}$ uniform threshold circuit.

After combining depths from all steps, the total depth of the circuit for computing $A_{i,j}$ is

Since we can parallel compute all entries in $A_{i,j}$ for $i,j\in[n]$, the circuit depth remains $3(d_{\rm std}+d_{\oplus})+d_{\rm exp}$ and size bounded by $\operatorname{poly}(n)$.

4 Computing Common Components Layers

This section outlines the MLP layer circuit complexity.

Next, we examine the layer-normalization (LN) layer circuit complexity.

5 Computing Convolution Blocks

We prove in this section that the convolution layers can be computed within $\mathsf{TC}^{0}$.

Under the premise that the following conditions apply:

Assume the padding in the convolution process is .

Assume the stride in the convolution process is $1$.

For $i\in[h-h_{k}+1]$ and $j\in[w-w_{k}+1]$.

Then, we can apply a size bounded by $\operatorname{poly}(n)$ and $O(1)$ depth uniform threshold circuit to simulate one kernel convolution process.

For each $i\in[h-h_{k}+1]$ and $j\in[w-w_{k}+1]$, we know

By using the result of Part 1 in Lemma 3.5, we can use a size bounded by $\operatorname{poly}(n)$ and $O(1)$ depth uniform threshold circuit to compute each product $X_{i+m-1,j+n-1,q}\cdot K_{m,n,q}$. Furthermore, the computation of $X_{i+m-1,j+n-1,q}\cdot K_{m,n,q}$ can be performed in parallel for all $m\in[h_{k}]$, $n\in[w_{k}]$ and $q\in[c]$. Therefore, the total depth of the circuit remains $O(1)$, and its size stays $\operatorname{poly}(n)$, since $h_{k}\times w_{k}\times c\leq n$.

Then, we proceed to compute the sum $\sum_{m=1}^{h_{k}}\sum_{n=1}^{w_{k}}\sum_{q=1}^{c}X_{i+m-1,j+n-1,q}\cdot K_{m,n,q}+b$. Using the result from Lemma 3.5, we can use a size bounded by $\operatorname{poly}(n)$ and $O(1)$ depth uniform threshold circuit to compute the sum. By computing $Y_{i,j}$ for all $i\in[h-h_{k}+1],j\in[w-w_{k}+1]$ in parallel, we maintain the uniform threshold circuit with $O(1)$ depth and size bounded by $\operatorname{poly}(n)$ which is due to $h,w\leq\operatorname{poly}(n)$.

Thus, we can apply a size bounded by $\operatorname{poly}(n)$ and $O(1)$ depth uniform threshold circuit to simulate the one kernel convolution process. ∎

6 Computing Phase 1: VAR Transformer

In this part, we establish that the VAR Transformer defined in Definition 4.9 is within the computational power of $\mathsf{TC}^{0}$

Assume the number of transformer layers $m=O(1)$. Assume the precision $p\leq\operatorname{poly}(n)$. Then, we can apply a uniform threshold circuit to simulate the VAR Transformer $\mathsf{TF}$ defined in Definition 4.9. The circuit has size $\operatorname{poly}(n)$ and $O(1)$ depth.

By using the result of Lemma 5.1, we can apply a uniform threshold circuit of size bounded by $\operatorname{poly}(n)$ and $O(1)$ depth to simulate up -interpolation layer $\phi_{\rm up}$ defined in Definition 4.3.

By using the result of Lemma 5.4 and Lemma 5.5, we can apply a size bounded by $\operatorname{poly}(n)$ and $O(1)$ depth uniform threshold circuit to simulate $g_{i}$, for each $i\in[m]$.

By using the result of Lemma 5.3, we can apply a size bounded by $\operatorname{poly}(n)$ and $O(1)$ depth uniform threshold circuit to simulate $\mathsf{Attn}_{i}$ defined in Definition 4.5.

To compute $\mathsf{TF}(X)$, we must compute $g_{1},\dots,g_{m}$ ,$\mathsf{Attn}_{1},\dots,\mathsf{Attn}_{m}$ and $m$ up-interpolation layers. Then, we can have that the size of the uniform threshold circuit is bounded by $\operatorname{poly}(n)$, and the total depth of the circuit is $O(1)$, which is due to $m=O(1)$.

7 Computing Phase 2: Feature Map Reconstruction

In this section, we show that the feature map reconstruction is within the computational power of $\mathsf{TC}^{0}$.

Assume the feature map reconstruction needs $k$ convolution kernel. Assume $k\leq\operatorname{poly}(n)$. Assuming the precision $p\leq\operatorname{poly}(n)$, then we can apply a uniform threshold circuit to simulate the feature map reconstruction operations. The circuit has size $\operatorname{poly}(n)$ and $O(1)$ depth.

This can be easily derived from Proposition 5.7. ∎

8 Computing Phase 3: VQ-VAE Decoder process

In this section, we show that the VQ-VAE Decoder is within the computational power of $\mathsf{TC}^{0}$

Assume the precision $p\leq\operatorname{poly}(n)$. Then, we can apply a uniform threshold circuit to simulate the VQ-VAE decoder process. The circuit has size $\operatorname{poly}(n)$ and $O(1)$ depth.

Firstly, by using the result of Proposition 5.7 and Lemma 3.5, we can simulate the ResNet blocks by using a size $\operatorname{poly}(n)$ and $O(1)$ depth uniform threshold circuit.

Then, by using the result of Lemma 5.8, we can simulate the attention blocks by using a size $\operatorname{poly}(n)$ and $O(1)$ depth uniform threshold circuit.

And, by using the result of Lemma 5.1, we can simulate the Up Sample Blocks by using a size $\operatorname{poly}(n)$ and depth $O(1)$ uniform threshold circuit.

By combing the result above, we have that a size $\operatorname{poly}(n)$ and $O(1)$ depth uniform threshold circuit can be applied to simulate the VQ-VAE decoder process. ∎

9 Main Result

We present our main result, which derives the circuit complexity limits for the VAR model.

Assuming precision $p\leq\operatorname{poly}(n)$, then we can apply a uniform threshold circuit to simulate the VAR model, where the circuit has size $\operatorname{poly}(n)$ and $O(1)$ depth.

This result directly comes from Lemma 5.8, Lemma 5.9 and Lemma 5.10. ∎

Conclusion

This study provides a comprehensive theoretical analysis of VAR models, deriving key limits on their computational abilities. Our approach centers on examining the circuit complexity of various components of VAR models, from the up-interpolation layers and the convolution layers to the attention mechanism. Furthermore, we show that VAR can be expressed as uniform $\mathsf{TC^{0}}$ circuits. This finding is important because it exposes inherent constraints in the expressiveness of VAR models, despite their empirical effectiveness in visual generation.

References