Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Authors: Yifang Chen
Xiaoyu Li
Yingyu Liang
Zhenmei Shi
Zhao Song
Venue: ICML 2025 poster (2025)
Keywords: Universal Approximation
Visual AutoRegressive Transformers
Fundamental Limits
Primary area: deep_learning->algorithms

Abstract: We investigate the fundamental limits of transformer-based foundation models, extending our analysis to include Visual Autoregressive (VAR) transformers. VAR represents a big step toward generating images using a novel, scalable, coarse-to-fine ``next-scale prediction'' framework. These models set a new quality bar, outperforming all previous methods, including Diffusion Transformers, while having state-of-the-art performance for image synthesis tasks. Our primary contributions establish that, for single-head VAR transformers with a single self-attention layer and single interpolation layer, the VAR Transformer is universal. From the statistical perspective, we prove that such simple VAR transformers are universal approximators for any word-to-image Lipschitz functions. Furthermore, we demonstrate that flow-based autoregressive transformers inherit similar approximation capabilities. Our results provide important design principles for effective and computationally efficient VAR Transformer strategies that can be used to extend their utility to more sophisticated VAR models in image generation and other related areas.

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Yifang Chen
Xiaoyu Li
Yingyu Liang?
Zhenmei Shi Zhao Song
Abstract
The component in the transformer architecture is the mechanism, which captures long-range de- pendencies in data (Vaswani et al., 2017). A transformer- variants model, called the Visual Auto-regressive Trans- former (VAR) (Tian et al., 2024), utilizes the transformer architecture to structure image synthesis. VAR Transformer uses "next-scale prediction" method produce high quality images much more efficiently and outperform many stan- dard diffusion models (Song et al., 2021). The iterative generation process of VAR demonstrates powerful perfor- mance in large-scale visual tasks, but the previous work is solely empirical, where the theoretical understandings of why VAR Transformers architecture excel in the image synthesis tasks is missing.
We investigate the fundamental limits of transformer-based foundation models, extending our analysis to include Visual Autoregressive (VAR) transformers. VAR represents a big step toward generating images using a novel, scalable, coarse-to-fine "next-scale prediction" framework. These models set a new quality bar, outperform- ing all previous methods, including Diffusion Transformers, while having state-of-the-arl per- formance for image synthesis tasks. Our primary contributions establish that, for single-head VAR transformers with a single self-attention layer and single interpolation layer, the VAR Transformer is universal. From the statistical perspective, we prove that such simple VAR transformers uni- versal approximators for any word-to-image Lip- schitz functions. Furthermore, we demonstrate that flow-based autoregressive transformers in- herit similar approximation capabilities. Our re- sults provide important design principles for ef- fective and computationally efficient VAR Trans- former strategies that can be used extend their utility to more sophisticated VAR models in im- age generation and other related areas.
In addition to the VAR transfromer, flow-based generative methods (e.g., real-valued non-volume preserving (Real- NVP) and Glow) have also garnered attention for their abil- ity to generate high-fidelity samples in an invertible and tractable manner. Recent efforts have integrated autoregres- sive decompositions with flow-based designs, giving rise to Flow AutoRegressive (FlowAR) (Ren et al.. 2024) architec- tures. These models aim to blend the interpretability and stability of normalizing flows with the powerful represen- tation learning of autoregressive transformers, potentially yielding more robust and scalable training dynamics. Simi- lar to the studies on VAR transformers, the previous work on FlowAR focus on the empirical results but missing the theoretical understanding of why FlowAR excels other ar- chitetures.
1. Introduction
Transformer architectures have gained many attentions re- cently, and it has reshaped the landscape of modern ma- chine learning. Transformer-based models have shown the state-of-the-art performance in many tasks, such as natural language processing (e.g., GPT-ol (OpenAI, 2024), Llama 3.3 (Llama Team, 2024; AI, 2024), and Claude 3.5 (An- thropic, 2024)), computer vision, and generative modeling.
To provide the theoretical analysis of the transformer- architecture, the universal approximation theory is popular in recent studies Standard transformers are proved to be univeral sequence-to-sequeeee approximators, which means that transformer is capable of representing any continuous mapping between input and output sequences given suffi- cient width and depth (Yun et al., 2020; Kajitsuka & Sato, 2024). Therefore, given the lack of theoretical analysis of VAR transformer, it is natural to ask the question:
'The University of Chicago Uniivesiity of New South Wales 'The University of Hong Kong UUniversity of Wisconsin-Madison 4 University of California, Berkeley. Correspondence to: Zhao Song <magic.linuxkder gmail.com>.
Are VAR Transformers the universal approximators?
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In this work, we extend the unviersal approximation result from (Yun al., 2020; Kim et al., 2022; Kajitsuka & Sato,

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
2024; Hu et al., 2024b; Liu al., 2025; Hu et al., 2025a) to prove that the VAR Transformer and some other variants are universal approximators. Our contribution can be sum- marized as follows: The key contributions of this paper are as follows:
of conditions. PixeICNN (Van den Oord al., 2016) and PixeISNAIL. (Chen et al., 2018) generate one pixel a time, which can capture local dependencies with convolutional architectures. Recent work use discrete latent tokenization, which facilitate generation at high resolutions. For exam- ple (Esser et al., 2021) introduces VQ-GAN that utilizes vector quantization with a GPT decoder, and VQVAE-2 from (Razavi et al., 2019) and RQ--ransformer from (Lee et al., 2022) propose multi-scale hierachies capture coarse and fine-level structure. Based on these previous work, (Tian et al., 2024) designs the Visual AutoRegressive (VAR) Transformer which implement coase-to-fine "next-scale pre- diction" mechanism and combine transformer decoding with token representations. VAR Transformer achieves state-of-the thert performance in autoregressive im- age sythesis.
We formally establish that single-layer, single-head VAR Transformers are universal function approxima- tors for Lipschitz image-to-image mappings. extend- ing universality results to the VAR framework.
Our results elucidate the theoretical expressiveness of VAR Transformers, showing how their fundamental components, including self-attention and up-sampling. enable them to approximate arbitrary continuous trans- formations.
We provide insights into the broader implications of our findings for generative modeling, particularly in computer vision, where efficient and expressive archi- tectures are essential for high-quality image synthesis. Building on the universal approximation property es- tablished for VAR Transformers, we show that the guar- antee naturally extends other autoregressive models as well.
Diffusion Models. Diffusion models (Ho et al., 2020; Rombach et al., 2022) excel in generating high-resolution images by iteratively refining noise into coherent visuals. Prominent examples, such as DiT (Peebles & Xie, 2023) and U-ViT (Bao et al., 2023), leverage probabilistic frameworks to learn data distributions effectively. Recent progress in diffusion-basee image generation has focused on enhancing sampling techniques and training efficiency (Song & Ermon, 2019; Song ct al., 2021; Lu et al., 2022; Hu et al., 2024c; Chen et al., 2025a; Shen et al., 2025a), advancing latent- space learning (Rombach et al., 2022; Wang et al., b;;4d;b; Liu et al., 2024a), refining model architectures (Ho et al., 2022; Peebles & Xie, 2023; Gu et al., 2025; Wang et al., 2024a; Xue et al., 2024: Chen et al., 2025b), and exploring applications in 3D generation (Poole et al., 2022; Wang et al., 2024c; Xu et al., 2024b; Cao et al., 2025a).
Our theoretical contributions address two central gaps in the- oretical understandings of generative transformer architec- tures, and it provides more insights to design more flexible and efficient generative models. Furthermore, our results provide deeper understanding of why VAR and some other variants perform effectiivey in practice, such as even with the most minimal set up (single layer and single head), VAR transformer is capable of approximating complex functions.
2. Related Work
3. Preliminary
Universal Approximation of Transformer Transformer architectures are universal approximators, which means they have the capabilities to approximate arbitrary sequence-to- sequence functions under mild conditions. (Yun al., 2020) shows that deep transformers with stacked self-attention and feedforward layers can approximate any continuous mapping. (Jiang & Li, 2023) uses Kolmogorov-Amold rep- resentations to derive the same results. (Alberti et al., 2023) extend the universality results to non-standard attention mechanisms, and (Kajitsuka& & Sato, 2024; Hu et al., 2024b) explores the universality results in single-layer and single head transformers. Overall, these results build a strong foundations for the theoretical understandings the expres- siveness of transformer-basee architectures.
In this section, we introduce the fundamental definitions of our work. In Section 3.1, we introduce all related math notations used in this paper. In Section 3.2, we introduce the key transformer blocks. In Section 3.3, we introduce the components in phase one of the VAR Model. In Section 3.4, we mathematically detail the VAR Transformer blocks.
3.1. Notations
We denote the Ep norm of a vector x by || i.e. ||ا||| := Σx= [as]. ||=|| == (Ei,= maxie[ni | For vector E R" exp(xx) E R² denotes a vector where exp(x;; is exp(x;) for all i [m]. For > k for any matrix A E Bgnk we denote the spectral norm of A by |||], i.e., ||A||| == sup.ER* [AAx|2/||<<//2 We de- fine the function norm as Il == (X)) where ff is a function. For a matrix X E R2 xd we use X E TR X to denote its tensorization, and we only
and ||]||o ==
Auto-regressive Image Generation Models In image generation, regressgreesive models play a pivotal role by decomposing high-dimension distributions into a product
2

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
assume this for letters X and Y.
is the number of neurons
W Rexd W(2) Rdxe are weight matrices
3.2. Transformer Blocks
b(1) E R ((2) E Rd are bias vectors.
In this section, we define the components in the VAR Trans- former.
FFN R - RdxT
We first introduce the Softmax unit.
Then we define the FFN as follows:
Definition 3.1 (Softmax). Let R". We define Softmax
R + IR" satisfying
FFN = X., W ReLU(W
X.,K
b())
+
( dx1
exp(=) Softmax(z) := (exp(2), 1m)
dx1
dxc
ex1
ex1
3.3. VAR Phase One
Here, we define the attention matrix in the VAR Transformer as follows.
We first present Phase One of VAR model based on (Ke et al., 2025a).
Definition 3.2 (Attention Matrix). Let Wo: WK E Raxd denote the model weights. Let X E ixd denote the repre- sentation of the length-n input. Then, we define the attention matrix A E RR by, For i,j [n].
The VAR model uses the VAR Transformer to convert the initialized token map Xinit into a series of pyramid-shaped token maps. The VAR Transformer alternates between up sample blocks and attention layers to get the output.
Aig == exp( XI. We Wo W
Up Sample Blocks. The k-th up sample block takes as input the initial token map Xinit and the previous pyramid- shaped token maps XI...., Xk. sets Yi = Xinit and up samples each X, into new token map Y,-1, and outputs the new grramid-shaper token maps YI....,Ya Y
1xd axd dxd dx1
With the attention matrix, we now provide the definition for single layer of Attention.
Definition 3.3 (Single Attention Layer). Let X E Raxd denote the representation of the length-n sentence. Let Wv E Rddd denote the model weights. As in the usual attention mechanism, the final goal is to output an n x d size matrix where D == diag(A1m) E RR*x", Then, we define attention layer Attn as
The upsampling on each token map (r-rr E [Ki) uses inter- polation with bicubic spline kernel.
Definition 3.6 (Bicubic Spline Kernel, Definition 3.1 from (Ke et al., 2025a) on Page 5 5). A bicubic spline kernel is piecewise cubic function W R + R that satisfies w(x) E [0, 1] for all x E R.
Attn(X)= = =
We define the up-interpolation layer for one-step geometric series as follows.
Here we present the definition of the VAR Attention.
Definition 3.7 (Up-interpolation Layer for One-Step Ge- ometric Series, Definition 3.2 from (Ke et al., 2025a) on Page 5). We let 2 2 be an integer denoting the inter- polation level, and we let h W1- Ar, W, E N satisfy hy < h, and wy-1 < wy. We take d E N to denote the number of feature channels, and we define the input feature map E Bhr-1 X xd and the output feature map Y E Ed, x.d
Definition 3.4 (VAR Attention Layer). Let 2 1 be pos- itive integer. Let It,, w, be two positive integers. Let X E IR,, Xu, xd denote the representation of the input token map. Let Wy E I denote the model weights. As in the usual attention mechanism, the final goal is output size matrix where D == (tiag(A,)) E he, Xh,w, Then, we define attention layer Attn, B..,, xd Rhow, as
d
Attn, (X) = D AXWW.
Let W. : - R denote a bicubic spline kernel (see Defi- nition 3.6). The up-interpolation operation is defined by a function
We introduce the feed-forward layer in the VAR Transformer as follows.
pup.r : 1 X xd
Definition 3.5 (Single Feed-Forward Layer). If the follow- ing conditions hold:
such that Y (X). For each spatial index i E [/v]]. E [wr], and channel index I [d]. the output given by:
X E d
2 2 W(s)
YıjA= == Σ
Σ -=-
X 11 ts, 1- Ht, W(t).
h: E [n]
3

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
After defining the Up-Interpolation Layer for one-step geometric sequence, we construct Pyramid Up- Interpolation Layer, which applies multiple up-interpolation layers to generate token maps at different resolutions. Specifically, we can describe this Pyramid Up-Interpolation Layer through the following definition:
Now, are ready to introduce the VAR transformer.
Definition 3.11 (VAR Transformer, Definition 3.1 from (Ke et al., 2025a) on Page 5). If the following conditions hold:
Assume the VAR transformer has transformer layers.
Definition 3.8 (Pyramid Up-Interpolation Layer 2, Case, Definition 3.3 from (Ke al., 2025a) on Page 5). We let d N be a positive integer denoting the channel dimension, and we take Xinit IR 1xxxd to denote the initial token map.
At the i-th transformer layer, let yi denote components excluding the attention layer, such as the LN layer or MLP layer.
Let Pup.r denote the pyramid up-interpolation layer defined in Definition 3.9.
The pyramid up-interpolation operator at level 1 is defined as follows:
Let Attn; stand for the self-attention layer, which defined in Definition 3.3.
up,1 -lxxxd
IR 1x1xd
uup,1 (Xinit == Xinit-
Let Xinit 1 be input token map and Xinit R Ixd be its matrix version.
Definition 3,9 (Pyramid Up-Interpolation Layer Ob 2 2 Case). Let E N be the channel dimension, and let r 2 2 be the number of interpolation levels. Let Xinit. E R Ix denote the initial token map. Let
Let E h2W,
Pup.: T h xd
A xw.xd
Then we define a VAR transformer as the following
denote the up-interpolation operator at level i, as defined in Definition 3.7.
TF TF(Ximit) Im Attn 2 Pup.m 92 Attn, Pup.2
91 o Attn; upp (Xiit) Raad
We define the pyramid up-interpolation operator
In this expression, o stands for functional composition.
i up.r R= + Rh1 K xd
3.4. VAR Transformer Blocks
recursively as follows:
Recall we have defined Ộup RAxuxe - R xxxxxxxx in Definition 3.7. Since there is no non-linear operation in Φup- Pup is equivalent to a matrix multiplication operation, where the dimension of the matrix is I w/ hhw For simplicity, we view Ωup as R w' xhw dimension matrix in the following proofs.
Y1 Xinit:
Y, Pup.i-1(YY-2)) for ar i e r
Remark 3.12 (Applying Pup on X E Raxd Remark 4.8 from (Ke al., 2025a) on Page 8). The actual input of VAR Transformer Layer are input token maps, X1
Copy
Xinit
", E h. xd We denote them as X e Rhixw Xwi xd
Rexd where n. = Σ hyw, We denote Φup P E R" xd as applying dup each X; E B for E [r]. where n' = =I k/w..
X1
X2
Xma (X))
(Xp)
Then, we can combine multiple attention layers with other components (up-interpolation layers, multilayer perceptron layers, layer-wise normalization layers) create complete VAR Transformer architecture.
Figure 1. One Pyramid Up- Interpolation Layer Instance Pap.2. The Pyramid Up-Interpolation layer starts from 1 1 d token Xim and uses two bicubic up up-samninng steps to produce higher- resolution token maps X1 and X2. The concatenated tokens flattened, and their query-key dot products form the atlention ma- trix A that supplies context the transformer block.
Definition 3.13 (Single VAR Transformer Layer, Definition 4.9 from (Ke al., 2025a) on Page 9). If the following conditions hold:
Remark 3.10. We have crramid-shapee token maps of size hp++1 x 1|r+1] x To input this into the VAR Transformer, we merge the first two dimensions, transforming it into an input of size 5-1 haw;) d.
Assume the VAR transformer has m Transformer lay- ers.

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Let FFN denotes single Feed-forward Layer (see Definition 3.5).
Theorem 4.1 and Corollary jointly reveal that minimal in- stantiations of both VAR Transformers and FlowAR models already possess universal approximation power. This finding is striking for two reasons. First, it shows that the coarse-to- fine "next-scale prediction" schedule of VAR, when coupled with a single-head self-attention mechanism, suffices to match the expressiveness guarantees previously reserved for much deeper or wider transformer stacks. Second, the same argument extends seamlessly to FlowAR, indicating that invertible flow steps do not diminish expressivity and can even complement autoregressive attention by offering stable training dynamics, Practically, these results suggest that future work can focus on efficiency optimisations -uuch as weight sharing or low-rank adaptation without risking a loss of representational capacity.
Let Attn stands for a single self-attention layer (see Definition 3.3).
Then define VAR transformer block as the following.
(FV = FFN Attn Oup E Ruxd
In this expression, stands for functional composition.
Now, we present the VAR Transformer Network Function Class.
Definition 3.14 (VAR Transformer Network Function
Class). If the following conditions hold:
5. Any-Rank Single-Layer Attention is a Contextual Mapping Function
Assume the VAR transformer network has m layers.
for E [m], FFN; denotes the Feed-forward at i-th layer (see Definition 3.5), Attn, denotes the Attention at i-th layer (see Definition 3.3), and d. denotes the Up interpolation at i-th layer (see Definition 3.7).
In this section, we show that Attention is a contextual map- ping function. In Section 5.1, we give the definition of contextual mapping. In Section 5.2, introduce any-rank single-layer attention as a contextual mapping function.
Let To... denote the VAR transformer network func- tion class
5.1. Contextual Mapping
each function T E Th..s.c consists of VAR transformer blocks TF with heads of size and e MLP hidden neurons
Contextual Mapping. Let X,Y Raxd be the input embeddings and output label sequences, respectively. Let X; E IR be the i-th token of cach X embedding sequence. Definition 5.1 (Vocabulary, Definition 2.4 from (Hu et al., 2024b) on Page 8). We define the vocabulary.
Then we define VAR Transformer Network Function Class as follows:
T0,800 = (T: paxd gaxd
We define the i-th vocabulary set for i [N] by V(o)
TT= TFWAR
TF VAR o.... (FV)R(X))
Uke(m) x(() C Rd.
VAR
We define the whole vocabulary set V as V UsE(N p(a) c Rdd.
4. Main Results
In this section, we introduce our main results. We show that VAR Transformer and FlowAR models are universal approximators.
Note that while "vocabulary" typically refers to the tokens' codomain, here, it refers to the set of all tokens within single sequence. To facilitate our analysis, we introduce the idea of input token separation following (Kajitsuka & Sato, 2024; Kim et al., 2022; Yun et al., 2020).
We first present the result of the universal approximation property of VAR Transformer.
Theorem 4.1 (Universality of VAR Transformer, Informal Version of Theorem 6.6). For any word-to-image function SwordZing under some mild assumptions, there exists VAR Transformer TVAR which can approximate it.
Definition 5.2 (Tokenwise Separateness, Definition 2.5 from (Hu et al., 2024b) on Page 8). We define the tokenwise separateness as follows.
Let ( X Ra be embeddings.
Next, we extend the result of VAR Transformer to FlowAR models.
Let N be the number of sequences in the datasets.
Corollary 4.2 (Universality of FR, Informal Version of Corollary 7.2). For any word-to-image function fwordZimg under some mild assumptions, there exists FlowAR model TVAR which can approximate
Let be the length of sequence. i.c. ((1) E B
First, we state three conditions for ( ,..., (N)
5

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
For any i E [N] and E [m], x > "min holds.
Let 7 7max +
(ii) For any i E [ and E [m], x| 222 < 7max holds.
Let 8 = 11 log L)
(iii For any i,j E [N] and k / [n] if X + x then | 11 > d holds.
Let k= Timax/ /
Let W(O) E IRdx and Wv, WK, We E Rexd
Second, define three types of separateness follows,
Then, show
Part 1. If all conditions hold, then we call it tokenwise
I-layer, single-head attention mechanism serves as a (n, 0)-ontexxtual mapping for the embeddings X(1.. X(N) with weight matrices W(O) and Wv. WK, WQ-
(Tmin:: Tmax; 8) -epparatd
Part 2. If conditions (ii) and (iii) hold, then we denote
this as (7, seeaarttessss
Part 3. If only condition (iii) holds, then we denote it as (f)-separateness.
Lemma 5.4 indicates that any-rank self-attention function distinguishes input tokens x[[ x(3) such that v(A) * vo), In other words, it distinguishes two identical tokens within different context.
To clarify condition (iii), consider cases where there are repeated tokens between different input sequences. Next, we define contextual mapping. Contextual mapping describes a function's 's ability to capture the context of each input sequence as a whole and assign a unique ID to each input sequence.
5.3. Discussion
Hu et al. (2024c) rigorously studied the statistical and com- putational frontiers of prompt-tuning Transformers. They prove that even the minimal architecture- single-layer, single-head Transformer kept entirely frozen wrzzen-becomer universal approximator once a learnable soft-prompt is prepended, and they quantify the accompanying memoriza- tion cost by showing an exponential lower bound on the prompt length required for arbitrary sequence-to-sequenec datasets. Our study builds on this insight by exploring how the unversal approximation abilities of VAR Transformers.
Definition 5.3 ((7, 5) --Contextual Mapping, Definition 2.6 from (Hu et al., 2024b) on Page 8). A function q Ra Raxd is said to be (7, o)-ottetxtl mapping for set of embeddings (1). ...., XN(N E Raadd if the following conditions hold:
Contextual Sensitivity 7, For any i E [N] and k E [n]. (X)(()) )xl1a < holds.
Approximation Error 5. For any i,j [N] and 1 E [n] such that y(0) # vii or x( # x(")
6. Universality of VAR Transformer
(lx(X(0)) x(l holds.
In this section, present proof for the universality of the VAR Transformer. In Section 6.1, we used universality result from a previous work. In Section 6.2, we analyze how the error behaves when two consecutive layers in our composition are each replaced by their respective approxi- mations. In Section 6.3, we present the scenario when one of the composited layers got replaced by different func- tion. In Section 6.4, we present the scenario when all of the composited layers got replaced. In Section 6.5, we present our proof for the universality of the VAR Transformer.
In addition, Note that q (()) for i [N] is called context
ID of (
5.2. Any-Rank Single-Layer Attention is Contextual Mapping Function
Now present the result showing that softmax-basee 1- head, 1-layer attention block with any-rank weight matrices is a contextual mapping.
Lemma 5.4 (Any-Rank Attention as (7, d)-Cottelt Mapping, Lemma 2.2 from (Hu et al., 2024b) on Page 9). If the following conditions hold:
6.1. Universality of T.1.1.4 with ((1/e)daa) FFN Layers
We follow the line of the universal approximation tech- niques (Yun et al., 2020; Kim et al., 2022; Kajitsuka & Sato, 2024; Hu et al., 2024b; Liu et al., 2025; Hu et al., 2025a) and extend to the following result.
Let (()),... (NN E Raad be embeddings that are (Yimiu Timax: -tkeenneee separated, with the vocabu- lary set = USE(NI 100) C Rd.
Lemma 6.1 (T E TT)
1,1144 Transformer is Universal Img2Img Approximator, a Variation of Theorem 2.3 in Hu et al. (2024b) on Page 11). the
x()) # x(9) for any E [N] and k, E [T..
th following conditions hold:
6

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Let S < dc and 0.
For each E [r], let ga be K-Lipschitz function from 1 to R
Let a transformer with one self-attention layer defined as E TAA.
We assume that for each i E [r]. 9r can be approxi-
mated by some up interpolation function Pup.s-
Then, there exists a transformer T with single self-attention layer, such that for any fing2img E Fc there exists Jinging lla S
We assume that the target function sword2ing R Ixxxx Rh. xd satisfies
f fword2ing := fr gr fi og1
Proof. We provide sketch of the proof here, which mainly follows from Hu et al. (2024b)
With the Assumption 6.2, we present the two layers of perturbation as follows.
We start by quantizing the input and output do- main of fungzing Fcrr into quantized function I /ung2img : Gn.h.,,, + Go.A..a. where Gä.h.,w, {0, 6, 26...., 11.,,1,,,,,,,, Here, J fmgg2ing: Fcr, de- note the quantized function and function class. This is hasically performing piece-wer wesee constant approxima- tion with bounded error 5.
Lemma 6.3 (Two Layers Perturbation). Let Pup.i be the up interpolation functtoonionnunncionn defined in Definition 3.7. Let fr be r K K-Lipschitz functions from Assumption 6.2. Let gi be K-Lipschitz functions from Assumption 6.2. Let Ti be the one-layer transformer defined in Eq. 2.4 from (Hu el al., 2024b). If & uup:il S 61,5 from Assumption 6.2, | Till S E2 from Theorem 6.1, and each fo is KLS5 Lipschitz, then we have
Next, construct surrogate quantized image-to- image function
1lfe o gi - rj Pupill S K1,511, 62.
hingZimg go,(h.w.) - (h,,
Proof. We can show that
where G8.(h.w=) {0, 6, 28...., I 83 (Amww)))
[[ gi T; T upp.il
Here Ming2ing takes embeddings X as inputs. Cru- cially, its output approximates any J Jing2ing Fcr.
= II o 9. - Sa o t Dup. + J4 o 1 up.i T, T up.
I llfe o gi - fi o a uup, + [| o Pup.s T3 2 upp
Finally, we show that there exist a transformer E T1.1.1 approximating hangging to any precision. The formal construction is in Lemma C.I. By simple re-
Ilf, o (g. Pppa II + ll(f: 7;) uppill
< [[ʃa o (gi ppp ) + [lf [
Till
duction from MangZing, Fimg2img and fimgzing. we achieve the universality of prompt tuning on T with ((1/e)d(hh,wr)) FFN layers, where is the ap- proximation error.
S K1, + 62.i
where the first step follows from basic algebra, the second step follows from triangle inequality, the third and fourth steps follow from basic algebra, and the fifth step follows from our conditions.
Thus we complete the proof
6.3. Perturbation of Recursively Composting Functions that One Layer is Different
6.2. Two Layers Perturbation
In this section, we analyze how the error behaves when two consecutive layers in our composition are each replaced by their respective approximations. Specifically, we consider the composition f; 9: and replace 9; with an up interpo- lation function & Pup,i and fi with a one-layer transformer
In this section, we consider a scenario where we have a composition of many layers, but only one of the layers is replaced by different function. This setting helps us see how a single local perturbation can propagate through subsequent layers in a multi-layer composition. The lemma below quantifies this propagation by leveraging Lipschitz continuity.
T,. We show that under appropriate Lipschitz and approxi- mation assumptions, the overall error of the approximated two-layer composition can be controlled in terms of the individual approximation errors.
Lemma 6.4 (Perturbation of Recursively Composting Func- tions, One Layer is Different), if the following conditions hold
Assumption 6.2 (Target Function Class), We assume the following things:
Assume [lu,(w) ry(w)]l S ffrr any w.
Let fr be r K-Lipschitz functions from Rh,xw, xd to xd
v((x) S K2 ||-|||
7

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Fix j, we have
where the first step follows from adding intermediate terms, and the last step follows from the triangle inequality.
1=j-1 D4 o
n+1
o o00 uill S K2-
Thus, we complete the proof.
Proof. We define w as
6.5. The Universality of VAR Transformer
w = =
In this section, with the established error bounds for re- placing individual or multiple layers with alternative func- tions, we now prove the main universality result for the VAR Transformer. In essence, we show that properly constructed VAR Transformer can approximate the target function fwordZing (from Assumption 6.2) with arbitrarily small errors under suitable Lipschitz and approximation assumptions each layer.
We can show that for any
n+1 o E=-+ Di
o uz(z)) - of o o' (,(x)
o ntl
-=--1 (w) (
o 1=j+1 u(u, (w) - (w))l
< SKT
Theorem 6.6 (Universality of VAR Transformer, Formal Version of Theorem 4.1). For fwordZing satisfies Assump- tion 6.2, there exists a VAR Transformer TVAR such that
where the first step follows from basic algebra, the second step follows from linearity, and the third step follows from lemma assumptions.
TVAR fword2ing S O(c)
6.4. Perturbation of Recursively Composting Functions that All Layer are Different
Proof. Assume K2 > 2. We can show that
In this section, we extend the analysis to the most general scenario in which all layers in the composition are replaced by different functions. This captures the situation where each layer u, is approximated by some other function v;- We derive cumulative bound that sums the individual per- turbations introduced at each layer.
[VAR wword2ing || = || 1/ o.) - of o upp.)l
K2 K2 (K1,(1,, e2,1)
K₂ -1 (Ki,se,, + 62,)
Lemma 6.5 (Perturbation of Recursively Compositing Func- tions, All Layers are Different). If the following conditions hold:
< K3' (K,,t11s + E2,1)
Oc)).
Let oi = th, o .... o U1.
where the first step follows from Definition 14, the second step follows from Lemma 6.4, the third step follows from basic algebra, and the fourth step follows from the basic inequality, and the last step follows that (, C2 O(c) for all E [mx]
Let of 12 Un
Let uo(x) which is identity mapping.
Let Un+1 x which is identity mapping.
7. Universality of FlowAR and HOFAR
Then
In this section, we show that the universality results estab- lished for the VAR Transformer can be extended FlowAR model. Furthermore, we show that these results also hold for Higher-order FlowAR models (HOFAR) introduced by Liang et al. (2025b). In Section 7.1, we present the universality result of FlowAR. In Section 7.2, we extend the universality result to HOFAR.
1 1=
1=1 w:|
x+
Us o/
- - ofd will
1=f+1
j=1
Proof. We can show
|| - u - 12 1
7.1. Universality of FlowAR
n+ i=j+1 U. of U4 uu-
-0--0//-0 ou of uIll
The key observation is that the same local perturbation bounds and Lipschitz assumptions used the VAR Trans- former setting also apply to FlowAR, with only minor changes. Specifically, each FlowAR layer T aowwn, can be
a
<
Σ
a+1
i=j+1 U/ o u; - - ب will
1=1
8

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
analyzed in an analogous way to Pup.s. allowing us de- rive a bound on the overall error of the composed FlowAR model.
basic algebra, and the fourth step follows from the basic inequality, and the last step follows that <1,;, ', Oc)) for all E [rx]
Corollary 7.1. Let Pdown,s be the down interpolation func- tion of FlowAR (see Definition D.2). Let J be K- -ipischhitz functions from A Assumption 6.2. Let 9i be K K-Lipschitz func- tions from Assumption 6.2. Let T2 E 1.14 be the one-layer transformer. If llg. dll I 61.5 llf, - Tall S 62 and each Js is K1,--Lipschin then we have
The proof of Corollary 7.2 follows the same high-level struc- ture our universality results for the VAR Transformer (Theorem 6.6. By applying the local perturbation bound layer by layer and then summing the resulting errors, we ob- tain a global approximation guarantee that is O(c). Hence, FlowAR, just like the VAR Transformer, can universally approximate the target function fword2ing under the given Lipschitz and approximation assumptions.
IIfe o gi - o Ldown,ll S K1,t1, + 62,
Proof. We can show that
[ff 9i T; 2 dolwn,ill
7.2. Universality of HOFAR
I 9: - fi o & down, + f; Pdown,i - T; o 2 doown,ill
Furthermore, we can extend the result to HOFAR (Liang et al., 2025b). In the original VAR analysis, the attention module learns zeroth-order information (spatial positions). FlowAR upgrades this to first-order information by regress- ing the velocity field. HOFAR further extends the idea: one attention block predicts the velocity o(!), a second pre- dicts its time derivative y(2), and the two predictions are added-no concatenated- form the total velocity used for the flow update. Because each block is K K-Lipschitz, their individual errors add linearly. Hence, if each block is e- accurate, the combined model is 26-accurate, preserving the universal approximation guarantee enjoyed by single-order AR. Formally, we can obtain the following result.
S Il o 9: fi o & dowwn, || + Il.fss $ Pdown,i - T; o + Pdown,il
|[fe (g. $ down. )ll + |I(fs Tz) + &down,<ll
< |[fi (g. downn, Ill + Ilfs -Tal
< 11, - 22,5
where the first step follows from basic algebra, the second step follows from triangle inequality, the third and fourth steps follow from basic algebra, and the fifth step follows from our conditions.
The proof of this corollary mirrors the two-layer pertur- bation argument from the VAR Transformer, except each "up" interpolation function Pup.: replaced by the corre- sponding "down" interpolation function Pdown, The same Lipschitz and approximation assumptions allow us to bound the difference between f. 9i and T; dowwn,.
Corollary 7.3 (Universality of HOFAR). For fword2ing sat- isfies Assumption 6.2, there exists a HOFAR model THOFAR such that
Next, we can derive the universality of FRowAR models.
||THOAR Swoordingg
S ((t).
Corollary 7.2 (Universality of FlowAR, Informal Version of Corollary 4.2). For fword2ing satisfies Assumption 6.2 there exists a FlowAR model FlowAR such that
8. Conclusion
In this paper, we established that both VAR Transformers and FlowAR architectures serve as universal approximators for Lipschitz logueencett-seqqennce functions- in their most minimal configurations. By dissecting the roles of self-attention, multi-scale up-sampling, and invertible flow transformations, we showed how these components collec- tively endow the models with sufficient expressive power to capture arbitrary continuous mappings. Our results unify previous theoretical findings on transformer universality with the practical enhancements brought by VAR and flow- based designs, providing a deeper theoretical underpinning for their empirical successes in high-quality image gener- ation and structured prediction tasks. We hope that these findings inspire new explorations into more advanced archi- tectural variants and guide future work on balancing model efficiency, interpretability, and expressive power.
TFloWRR - Sworddimggl S O(e).
Proof. Assume K2 > 2. We can show that
|FlaWRR Sword2img || = 1/111
of o up
K2 k-- (KI,E1,1 + +22s)
KT (K e2,))
K₂
< K7 (K1,61,5 + 62,5)
= O(e).
where the first step follows from Definition 3.14, the second step follows from Lemma 6.4, the third step follows from

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Acknowledgements
Bian, S., Song, Z., and Yin, J. Federated empirical risk minimization via second-order method. arXiv preprint arXiv:2305 2023.
The author would like to thank the anonymous reviewer of ICML 2025 for their highly insightful suggestions.
Cao, Y. Sorsa: Singular values and orthonormal regular-
Impact Statement
ized singular vectors adaptation of large language models. arXiv preprint Sa0iv::40900005555 2024.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Cao, Y., Li, X., and Song, Z. Grams: Gradient de- scent with adaptive momentum scaling, arXiv preprint arXiv:2412. 17107, 2024.
Cao, Y., Gong, C., Li, X., Liang, Y., Sha, Z., Shi, Z., and Song, Z. Richspace: Enriching text-to-video prompt space via text embedding interpolation. In ICLR 2025 Workshop on Navigating and Addressing Data Problems for Foundation Models, 2025a.
References
Aggarwal, A. and Alman, J. Optimal-degree polynomial approximations for exponentials and gaussian kernel den- sity estimation. In Proceedings of the 37th Computational Complexity Conference, pp. 1-23, 2022.
Cao, Y., Li, X., Liang, Y., Sha, Z., Shi, Z., Song, Z., and Zhang, J. Dissecting submission limit in desk-rejections: A mathematical analysis of fairness in ai conference poli- cies. In Forty-second International Conference on Ma- chine Learning (ICML). PMLR, 2025b.
AI, M. Introducing meta Ilama 3: The most capable openly available Ilm to date, 2024. https://ai. meta. wwt.aacoooooo////...a..aaoooooct /mttaagm/ea-./// 1lama-3/.
Alberti, S., Dern, N., Thesing, L., and Kutyniok, G. Sum- former: Universal approximation for efficient transform- ers. In Topological, Algebraic and Geometric Learning Workshops 2023, pp. 72-86. PMLR, 2023.
Chen, B., Li, X., Liang, Y., Long, J., Shi, Z., and Song, Z. Circuit complexity bounds for rope- based transformer architecture. arXiv preprint arXiv:2411.0707 1.76022 2024a.
Chen, B., Gong, C., Li, X., Liang, Y., Sha, Z., Shi, Z., Song, Z., and Wan, M. High-order matching for one-step short- cut diffusion models. arXiv preprint arXiv:2502.000 00688, 2025a.
Alman, J. and Song, Z. Fast attention requires bounded tries. Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
Alman, J. and Song, Z. How to capture higher-order correla- tions? generalizing matrix softmax attention to kronecker computation. In The Twelfth International Conference on Learning Representations (ICLR), 2024a.
Chen, B.. Gong, C., Li, X., Liang, Y., Sha, Z., Shi, Z., Song, Z., Wan, M., and Ye, X. Nrflow: Towards noise- robust generative modeling via high-order mechanism. In Conference on Uncertainty in Artificial Intelligence (UAI), 2025b.
Alman, J. and Song, Z. gradient computation for training large language mod- els. In The Thirty-eighth Annual Conference Neural Information Processing Systems (NeurIPS), 2024b.
The fine-grained complexity of
Chen, B., Li, X., Liang, Y., Shi, 7., and Song, Z. Bypassing the exponential dependency: Looped transformers effi- ciently learn in-context by multi-step gradient descent. In The 28th International Conference on Artificial Intelli- gence and Statisties (AISTATS), 2025c.
Alman, J. and Song, Z. Fast rope attention: Combining the polynomial method and fast fourier transform. arxiv preprint arXiv:2505.1 / /892, 2025a.
Chen, B., Liang, Y., Sha, 7., Shi, Z.,, and Song, 7. Hsr- enhanced sparse attention acceleration. In The Second Conference Parsimony and Learning (CPAL) (Pro- ceedings Track), 2025d.
Alman, J. and Song, Z. Only large weights (and not skip connections) can prevent the perils of rank collapse. In arxiv preprint arXiv:2505.16284 2025b.
Anthropic. The claude model family: Opus, sonnet, haiku, 2024. https: http://wwwdott www. com/ cebba
Chen, X., Mishra, N., Rohaninejad, M., and Abbeel, P. Pixelsnail: An improved autoregressive generative model. In International conference on machine learning (ICML), pp. 864-872. PMLR, 2018
Model_ Cawuaaradddd______________ee pdf.
Bao, F., Nie, S., Xue, K., Cao, Y., Li, C., Su, H., and Zhu, J. All are worth words: vit backbone for diffusion models. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 22679, 2023.
Chen, X., Song, Z., Sun, B., Yin, J., and Zhuo, D. Query complexity of active learning for function fam- ily with nearly orthogonal basis. arXiv preprint MWXiv:330.003356 2023.
10

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Chen, Y., Huo, J., Li, X., Liang, Y., Shi, Z., and Song, Z. Fast gradient computation for rope attention in almost linear time. arXiv preprint arXiv:2412.17316 2024b.
In 2025 IEEE/CVF Winter Conference on Applications of Computer Vision ( (WACV), pp. 2342-2356. IEEE, 2025.
Gu, Y., Song, Z., Yin, J., and Zhang. Low rank matrix completion via robust alternating minimization in nearly linear time. In The Twelfth International Conference Learning Representations (ICLR), 2024.
Chen, Y. Li, X., Liang, Y., Shi, Z., and Song. Z. The com- putational limits of spate models and mamba via the lens of circuit complexity. In The Second Conference Parsimony and Learning (CPAL) (Proceedings Track), 2025e.
Ho, J., Jain, A., and Abbeel, P. Denoising diffusion proba- bilistic models. Advances in neural information process- ing systems (NeurIPS), 33:6840-688 6851, 2020.
Deng, Y., Song, Z., Wang, Y., and Yang, Y. A nearly optimal size coreset algorithm with nearly linear time. arXiv preprint arXiv:2210.08366 2022.
Ho, J., Saharia, C., Chan, W., Fleet, D. J., Norouzi, M., and Salimans, T. Cascaded diffusion models for high fidelity image generation. Journal of Machine Learning Research (JMLR), (3(47):1-33, 2022.
Deng, Y., Mahadevan, S., and Song. Z. Randomized and deterministic attention sparsification algorithms for over-parameteriin feature dimension. arXiv preprint arXiv:2304.04397, 2023a.
Hu, H., Song, Z., Tao, R., Xu, Z., Yin, J., and Zhuo, D. Sublinear time algorithm for online weighted bipartite matching. arXiv preprint arXiv:2208.03366 2022.
Deng, Y., Song, Z., and Yin, J. Faster robust ten- sor power method for arbitrary order. arXiv preprint arXiv:2306.00406, 2023b.
Hu, J. Y.C.., Lin, T., Song, Z., and Liu, H. On computational limits of modern hopfield models: A fine-grained com- plexity analysis. In Forty-first International Conference on Machine Learning (ICML), 2024a.
Deng, Y., Li, Z., Mahadevan, S., and Song, Z. Zero-th order algorithm for softmax attention optimization. In 2024 IEEE International Conference on Big Data (BigData),
Hu, J. Y.-C,, Wang. W.-P. Gilani, A., Li, C., Song, Z., and Liu, H. Fundamental limits of prompt tuning transform- ers: Universality, capacity and efficiency. arXiv preprint arXhv:4411.1655,, 2024b.
pp. 24-33. IEEE, 2024.
Esser, P., Rombach, R., and Ommer, B. Taming transformers for high-resolution image synthesis. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 12873-12883, 2021.
Hu, Y.-C., Wu, W., Lee, Y.-C., Huang, Y--C,, Chen, M., and Liu, H. On statistical rates of conditional diffusion transformers: Approximation, estimation and minimax optimality. arXiv preprint arXiv:2411.115222 2024c.
Gao, Y., Mahadevan, S., and Song. Z. An over- parameterized exponential regression. arXiv preprint arXiv:2303. 2023a.
Hu, Y.-C., Wu, W., Song. Z., and Liu, H. On statistical rates and provably efficient criteria of latent diffusion transformers (dits). arXiv preprint arXiv:2407.0107,, 2024d.
Gao, Y., Song, Z., and Xie, S. In-context learning for atten- tion scheme: from single softmax regression to multiple softmax regression via a tensor trick. arXiv preprint SXXv:2300.00449, 2023b.
Hu, Y.-C., Yang, D., Wu, D., Xu, C., Chen, B.-Y., and Liu, H. On sparse modern hopfield model. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024e.
Gao, Y., Song, Z., and Yin, J. Gradientcoin: A peer-to- peer decentralized large language models. arXiv preprint ar08. 10502, 2023c.
Hu, J. Y.C., Liu, H., Chen, H.-Y., Wu, W., and Liu, H. Universal approximation with softmax attention. arXiv preprint arXiv:2504. 15956, 2025a.
Gao, Y., Song, Z., Wang. W. and Yin, J. A fast optimization view: Reformulating single layer attention in Ilm based on tensor and svm trick, and solving it in matrix multi- plication time. In The 41st Conference on Uncertainty in Artificial Intelligence (UAI), 2025a.
Hu, J. Y.C.., Su, M., Kuo, E.J.,, Song, Z., and Liu, H. Computational limits of low-rank adaptation (LoRA) for transformer- models. In The Thirteenth Interna- tional Conference on Learning Representations (ICLR), 2025b.
Gao, Y., Song, Z., and Yin, J. An iterative algorithm for rescaled hyperbolic functions regression. In AISTATS. arXiv preprint arXiv:2305.0066
2025b.
Huang, B., Song, Z., Tao, R., Yin, J., Zhang, R., and Zhuo, D. Instahide's 's sample complexity when mixing two pri- vate images. arXiv preprint 2.X 2020.
Gu, J., Liang, Y., Sha, Z., Shi, Z., and Song, Z. Differential privacy mechanisms in neural tangent kernel regression.

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Huang, B., Song, Z., Weinstein, O., Yin, J., Zhang, H., and Zhang, R. A dynamic fast Gaussian transform. arXiv preprint arXiv:2202.12322 2022.
Li, X., Liang, Y., Shi, Z., Song, Z., Wang, W., and Zhang, J. On the computational capability of graph neural networks: A circuit complexity bound perspective. arXiv preprint arXiv:2501.0644 2025b.
Jiang, H. and Li, Q- Approximation theory of trans- former networks for sequence modeling, arXiv preprint arXiv:2305. 18475, 2023.
Li, Y. and Yang. L. On the model misspeciicciniinnioonnn in rein- forcement learning. In International Conference on Arti- ficial Intelligence and Statistics, pp. 2764-7762777 2772. PMLR, 2024.
Kajitsuka, T. and Sato, I. Are transformers with one layer self-attention using low-rank weight matrices universal approximators? In The Twelfth International Conference Learning Representations (ICI.R. 2024.
Li, Y. Wang, Y., Cheng, Y., and Yang. L. Low-switching policy gradient with exploration via online sensitivity sampling. International Conference on Machine Learn- ing (ICML), pp. -0094-20004. PMLR, 2023a.
Ke, Y., Li, X., Song, Z., and Zhou, T. Faster sampling algorithms for polytopes with small treewidth. In 2024 IEEE International Conference on Big Data (BigData), pp. 44-53. IEEE, 2024.
Li, Z., Song, Z., Wang, Z., and Yin, J. Local convergence of approximate newton method for two layer nonlinear regression. arXiv preprint arXiv:231 15390, 2023b.
Ke Y. Li, X., Liang, Y., Sha, Z., Shi, Z., and Song, Z. On computational limits and provably efficient criteria of visual autoregressive models: A fine grained complexity analysis. arXiv preprint arXiv:2501 25VV:2500.04377,, 2025a.
Li, Z.,, Song, Z., and Zhou, T. Solving regularized exp, cosh and sinh regression problems. arXiv preprint 1xXi::330311522, 2023c.
Ke, Y., Li, X., Liang, Y., Shi, Z., and Song, Z. Circuit complexity bounds for visual autoregressive model. arXiv preprint arXiv:2501.04290 04299, 2025b.
Li, Z., Song, Z., Wang, W., Yin, J., and Yu, Z. How to inverting the leverage score distribution? arXiv preprint arXiv:2404.0 13785, 2024e.
Kim, J., Kim, M., and Mozafari, B. Provable memorization capacity of transformers. In The Eleventh International Conference on Learning Representations, 2022.
Liang J., Sarkhel, S., Song. Z. Yin, C., Yin, J., and Zhuo, D. A faster k-means++ algorithm. arXiv preprint arXiv:221.115118, 2022a.
Lee, D., Kim, C., Kim. S., Cho, M., and Han, W.-S. Au- toregressive image generation using residual quantiza- tion. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 11523-11532, 2022.
Liang. J., Song, Z., Xu, Z. Yin, J., and Zhuo, D. Dynamic maintenance of kernel density estimation data structure: From practice to theory. arXiv preprint arXiv:2208.03915. 2022b.
Li, C., Song, Z., Xu, Z., and Yin, J. Inverting the leverage score gradient: An efficient approximate newton method. arXiv preprint arXiv:2408. /267, 2024a.
Liang, Y., Shi, Z., Song, Z., and Zhou, Y. Differential privacy of cross- cross-attention with provable guarantee. In Neurips Safe Generative A/ Workshop 2024.
Li, C., Liang. Y., Shi, Z.. Song, Z., and Zhou, Fourier circuits in neural networks and transformers: A case study of modular arithmetic with multiple inputs. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2025a.
Liang, Y., Liu, H., Shi, Z.,, Song, Z., and Yin, J. Conv- basis: A new paradigm for efficient attention inference and gradient computation in transformers. arXiv preprint arXiv:2405.0222 2024a.
Liang, Y., Sha, Z., Shi, Z., Song, Z., and Zhou, Y. Multi- layer transformers gradient can be approximated in al- most linear time. arXiv preprint 2rXiv:2408.1322 2024b.
Li, X., Liang, Y., Shi, Z., and Song, Z. A tighter complexity analysis of SparseGPT. arXiv preprint wxXiv:2408.12151. 2024b.
Li, X., Liang, Y. Shi, Z., Song, Z., and Wan, M. Theoretical constraints on the expressive power of rope-based tensor attention transformers. arXiv preprint 24X1::2412.18040 2024c.
Liang. Y., Shi, Z., Song, Z., and Zhou, Y. Tensor atten- tion training: Provably efficient learning of higher-order transformers. arXiv preprint arXiv:2405. 16411, 2024c.
Li, X., Long, J.. Song, Z., and Zhou, T. Fast second-order method for neural networks under small treewidth set- ting. In 2024 IEEE International Conference on Big Data (BigData), pp. 1039-1038. IEEE, 2024d.
Liang, Y., Long, J., Shi, Z., Song, Z., and Zhou, Y. Be- yond linear approximations: A novel pruning approach for attention matrix. In The Thirteenth International Con- ference on Learning Representations (ICLR), 2025a.
12

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Liang, Y., Sha, Z., Shi, Z., Song, Z., and Wan, M. Hofar: High-order augmentation of flow autoregressive trans- formers, arXiv preprint arXiv:2503.08032, 2025b.
Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF con- ference on computer vision and pattern recognition, pp. 10684-10695, 2022.
Liang, Y., Sha, Z., Shi, Z., Song, Z., and Zhou, Y. Looped relu mips may be all you need as programmable comput- ers. In The 28th International Conference on Artificial Intelligence and Statistics (AISTATS), 2025c.
Shen, X., Song, Z., Zhou, Y., Chen, B., Li, Y., Gong, Y., Zhang, K., Tan, H., Kuen, J., Ding, H., Shu, Z., Niu, W. Zhao, P., Wang. Y., and Gu, J. Lazydit: Lazy learning for the acceleration of diffusion transformers. In Proceedings of the AAAI Conference on Artificial Intelligence, 2025a.
Liu, C., Zhang, J., Wang, S., Fan, W., and Li, Q. Score-based generative diffusion models for social recommendations. arXiv preprint arXiv:2412.15573 2024a.
Shen, X., Song, Z.., Zhou, Y., Chen, B., Liu, J., Zhang, R., Rossi, R. A., Tan, H., Yu, T., Chen, X., Zhou, Y., Sun, T., Zhao, P., Wang, Y., and Gu, Numerical pruning for efficient autoregressive models. In Proceedings of the AAAI Conference on Artificial Intelligence, 2025b.
Liu, H., Hu, J. Y.-C., Song, Z., and Liu, H. Attention mech- anism, max-affine partition, and universal upproximation. arXiv preprint arXiv:2504. 19901, 2025.
Liu, J., Li, Y., Wang, R., and Yang, L. Uniform last-iterate guarantee for bandits and reinforcement learning. In The eiihty- Annual Conference Neural Information Processing Systems, 2024b.
Sinha, R., Song, Z., and Zhou, T. A mathematical ab- straction for balancing the trade-off between creativity and reality in large language models. arXiv preprint arXiv:2306.022: 02225,, 2023.
Liu, J., Li, Y., and Yang. L. Achieving near-optimal regret for bandit algorithms with uniform last-iterate guarantee. arXiv preprini arXiv:2402.12711, 2024c.
Song, J., Meng. C., and Ermon, S. Denoising diffusion implicit models. In International Conference on Learning Representations (ICLR), 2021.
Llama Team, A. M. The Ilama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.
Song, Y. and Ermon, S. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems (NeurIPS), 32, 2019.
Lu, C., Zhou, Y., Bao, F., Chen, J., Li, C., and Zhu, J. Dpm- solver: A fast ode solver for diffusion probabilistic model sampling in around 10 steps. Advances in Neural In- formation Processing Systems (NeurIPS), 35:5775-5787. 2022.
Song. Z. and Yang. C. An automatic learning rate schedule algorithm for achieving faster convergence and steeper descent. arXiv preprint arXiv:2310.11291, 2023.
OpenAl. Introducing openai ol-preview.
Song, Z., Wang, W., and Yin, J. unified scheme of resnet and softmax. arXiv preprint arXiv:2309 13482, 2023a.
https: openai. com/index/ introduc -nweeeciinno-paaaeee wol-prreepeeee 2024.
Accessed: September 12.
Song, Z., Xu, G., and Yin, J. The expressibility of polynomial based attention scheme. arXiv preprint arXiv:2310.2000 2023b.
Peebles, W. and Xie, S. Scalable diffusion models with transformers. In Proceedings of the IEEF/CVF Interna- tional Conference on Computer Vision, pp. 2023.
Song, Z., Ye, M., Yin, J., and Zhang, L. A nearly-optimal bound for fast regression with foc guarantee. In Inter- national Conference Machine Learning (ICML), pp. 32463-32482. PMLR, 2023c.
Poole, B., Jain, A., Barron, J. T., and Mildenhall, B. Dream- fusion: Text-to-3d using 2d diffusion. arXiv preprint arXiv:2209.1495 14988, 2022.
Song. Z., Yin, J., and Zhang, R. Revisiting quantum algorithms for linear regressions: Quadratic speedups without data-dependent parameters. arXiv preprint 1...2331..1822.. 2023d.
Razavi, A., Van den Oord, A., and Vinyals, O. Generating diverse high-fidelit images with 2q- Advances in neural information processing systems, 32, 2019.
Ren, S., Yu, Q. He, J.. Shen, X., Yuille, A., and Chen, L.- C. Flowar: Scale-wise autoregressive image generation meets flow matching. arXiv preprint 15225 2024.
Song, Z., Yin, J., and Zhang, L. Solving attention kernel regression problem via pre-conditioner. In International Conference on Artificial Intelligence and Statistics (AIS- TATS), pp. 208-216. PMLR, 2024a.
13

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Song, Z., Yin, J., Zhang, L.,, and Zhang, R. Fast dynamic sampling for determinantal point processes. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 252. PMLR, 2024b.
Xu, C., Huang, Y.-.., Hu, J. Y.-C., Li, W., Gilani, A., Goan, H.-S., and Liu, H. Bishop: Bi-directional cellular learning for tabular data with generalized sparse modern hopfield model. In Forty-first International Conference on Ma- chine Learning (ICMI), 2024a.
Song. Z., Wang, W., Yin, C., and Yin, J. Fast and effi- cient matching algorithm with deadline instances. In The Second Conference on Parsimony and Learning (CPAL) (Proceedings Track), 2025a.
Xu, H., Lei, Y., Chen, Z.., Zhang, X., Zhao, Y., Wang, Y., and Tu, Z. Bayesian diffusion models for 3d shape recon- struction. In Proceedings of the IEEE/CVF Conference on Computer Vision and Patlern Recognition (CVPR), pp. 10628-10638) 2024b.
Song, Z., Ye, M., Yin, J., and Zhang, L. Efficient alternating minimization with applications to weighted low rank ap- proximation. In The Thirteenth International Conference on Learning Representations (ICIR), 2025b.
Xue, Z., Song, G., Guo, Q., Liu, B., Zong. Z., Liu, Y., and Luo, P. Raphael: Text-to-image generation via large mix- ture of diffusion paths. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024.
Tian, K., Jiang, Y., Yuan, Z., Peng, B., and Wang. I.. Visual autoregressive modeling: Scalable image generation via next-scale prediction. Advances in neural information processing systems (NeurIPS), 2024.
Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S., and Kumar, S. Are transformers universal approximators of sequence-to-sqquence functions? In International Conference on Learning Representations (ICLR), 2020.
Van den Oord, A., Kalchbrenner, N., Espeholt, L., Vinyals, O., Graves, A., et al. Conditional image generation with pixelcnn decoders. Advances in neural information pro- cessing systems, 29, 2016.
Zhang, H., Peng, Z.,, Tang, J., Dong, M., Wang, K., and Li, W. A multi-layer extreme learning machine refined by sparrow search algorithm and weighted mean filter for short-term multi- wind speed forecasting. Sustainable Energy Technologies and Assessments, 50: 10169,8 2022.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones,
L., Gomez, A. N., Kaiser, Loss., and Polosukhin, I. At- tention is all you need. Advances in neural information processing systems (NeurIPS), 30, 2017.
Zhang. H., Chen, X., and Yang, L. F. Adaptive liquidity provision in uniswap v3 with deep reinforcement learning, arXiv preprint arXiv:2309. /0/29, 2023a.
Wang. Y., Chen, Z., Zhong, I.., Ding, Z., and Tu, Z. Dolfin: Diffusion layout transformers without autoencoder. In European Conference on Computer Vision (ECCV), pp. Springer, 2024a.
Zhang, H., Lin, X., Peng, S., Tang, J., Monti, A., al. Hurrogate-model-beee sequential algorithm for weather- dependent probabilistic power flow with high calculation efficiency. Authoea Preprints, 2023b.
Wang, Y., Xu, H., Zhang, X., Chen, Z., Sha, Z., Wang, Z., and Tu, Z. Omnicontrolnet: Dual-stage integration for conditional image generation. Proceedings of the IEEE/CVF Conference on Computer Vision and Pallern Recognition (CVPR), pp. 1436-7448, 2024b.
Zhang, 7.,, Chow, C.,, Zhang, Y., Sun, Y., Zhang, H., Jiang, E. H., Liu, H., Huang. F., Cui, Y., and Padilla, O. H. M. Statistical guarantees for lifelong reinforcement learning using pac-bayesian theory. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2025.
Wang, Z., Lu, C., Wang, Y., Bao, F., Li, C., Su, H., and Zhu, J. Prolificdreamer: High-fidelity and diverse text-to-3d generation with variational score distillation. Advances in Neural Information Processing Systems (NeurIPS), 36, 2024c.
Wang, Z., Sha, Z., Ding, Z.,, Wang, Y., and Tu, Z. To- kencompose: Text-to-in Text-to-image diffusion with token-level supervision. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pp. 2024d.
Wu, D., Hu, J. Y.C.., Li, W., Chen, B.-Y., and Liu, H. STanhop: Sparse tandem hopfield model for memory- enhanced time series prediction. In The Twelfth Interna- tional Conference on Learning Representations (ICLR), 2024.
14

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Appendix
Roadmap In Section A, we provide basic algebras that support our proofs. In Section B, we provide other phases of the VAR Model. In Section C, provide the transformer construction. In Section D, give the definitions for training the FlowAR Model. In Section E, give the definitions for the inference of the FlowAR Model. In Section F, we give the definitions for HOFAR. In Section G, we introduce more related work.
A. Preliminary
In this section, we introduce notations and basic facts that are used our work. We first list some basic facts of matrix norm properties.
A.1. Notations
We denote the l norm of vector x by ||>||p- i.e., || := Σi= |zs|. || == (Ei= x2)1/2 and ||>||>> := max [aa]- For vector æ E R", exp(z)= E IR" denotes a vector where exp(x), exp(x;) for all (n]. For >> for any matrix We define the function norm as
A E B denote the spectral norm of A by || i.., ||| SUPZER* ||Ax||2/|(xz where f is function. We use min (A) to denote the minimum singular value of A. Given two vectors E IR", we use (z. y) to denote E Ziy;- Given two vectors
|/ :- (a)((x))dxx)))
E R", we use o to denote a vector that its i-th entry is z,y; for all i E [n]. We use E, E R to denote a vector where i-th entry is 1, and all other entries are Let x E I2" be vector. We define diag(z) E Rax* as the diagonal matrix whose diagonal entries are given by diag(=)), = x; for 1,.... n, and all off-diagonal entries are zero. For a symmetric matrix A E RTxa, we say > (positive definite (PD)). if for all R" \ {0,). we have Ax 0. For symmetric matrix A Rux" we say (positive semidefinite (PSD)), if for all æ E R", we have T Ar 2 0. The Taylor Series for exp(x) is exp(x) Σ For a matrix X E Ru we use E R xnaxd to denote its tensorization, and we only assume this for letters X and Y.
A.2. Basic Algebra
In this section, we introduce the basic algebras used in our work. Fact A.I. Let A denote the matrix. For each we use A,, denote the i-th row of A. For j. we use Arj to denote the j-th column of A. We can show that
||A||| < ||A||E
||A||
||Ai,
||-|||
2 || la
Then, we introduce some useful inner product properties. Fact A.2. For vectors w E R We have
(u, u) (u o u. 1m)
(w w) = (wovow, w, 1n)
(u, v) = (c, u)
(u, v) u TT=vvl v
Now, we show more vector properties related to the hadamard products, inner products, and diagnoal matrices. Fact A.3. For any vectors u, v, w R",, we have
Euou=uu vou diag(u) u) v = diag(v)
Tu (T TT diag(v)w
15

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
(vow) o (wo w) w (u
u diag(v)w = T diag(u)us = ut diag(w)v
diag(u) diag(e) 1, di)
diag(u o v) diag(u) d
diag(u) + (1) = diag(u v)
B. VAR Transformer Blocks
B.1. Phase 2: Feature Map Reconstruction
In this section, we introduce the Phase Two of the VAR model.
Definition B.1 (Convolution Layer, Definition 3.9 from (Ke al., 2025a) Page 9). The Convolution Layer is defined follows:
Let h N denote the height of the input and output feature map.
Let w denote the width of the input and output feature map.
Let
N denote the number of channels of the input feature map.
Let Cout N denote the number of channels of the output feature map.
Let E R hxwxci denote the input feature map.
For / E [Cout], use K' 3x3xcmn denote the I-th convolution kernel.
Let p denote the padding of the convolution layer.
Let 8 denote the stride of the convolution kernel.
Let Y x denote the output feature map.
We use Φconv Rixuxen cx denote the convolution operation then we have Y Peonv (X). Specifically, for i [h].] E [w]. [Cout], we have
Yoss
Xi4m-15tn-le
Kt m.n.c +
172 12 cm
Remark B.2. Assumptions kernel size, padding of the convolution layer, and stride of the convolution kernel are based on specific implementation of (Tian et al., 2024).
B.2. Phase 3: VQ-VAE Decoder process
In this section, we introduce Phase Three of the VAR model.
VAR will use the VQ-VAE Decoder Module to reconstruct the feature map generated in Section B. into new image. The Decoder of VQ-VAE has the following main modules (Ke et al., 2025a): (1) Resnet Blocks; (2) Attention Blocks; (3) Up Sample Blocks. We recommend readers to (Ke et al., 2025a) for more details.
C. Construction of Transformers
In this Section, we show that how to construct E T1,1,4 such that can approximate any img-to-img function to any precision.
Lemma C.1 (Transformer Construction, a Variation of Lemma F.2 from (Hu et al., 2024b) on Page 45), If the following conditions hold:
16

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
for any given quantized sequence-to-sseqeence function
himgZing 98, (8.(hiow)) + G (hhrww
with w8, 20, -8(A,
Let transformer be T E T.l.lic
Let positional embedding be R(hhw.)xd
Then, there exists
a transformer T with positional embedding E
such that da (T,T,(()) $ 6/2.
Proof. First, we apply the positional encoding E E (R, on the input sequence E (R), so that each token of has a different domain. The positional encoding E is given as
0
1 2
W
2
E
W
We next use the first feed-forward layer FFN, to implement quantization map to quantize the input X + E into its discrete version E G8 Here, we define the grid
Go = 0 11th x [1 + : x ... W,, - 1 + 8 5::: 1,,,11
where (a e b] = {a, a + e, + .e.....u . e, b}. Note that the first column of + is [0, 1Jd, the second is in [1, 2] and so on. Here, we write the quantization mapping as
[0, 11dd x ... x w,o 1, 1,, 00:01 872 x ... x [,, - : 8 h,,,,,
where la : b] == {a, a 2e.....b b e- b}. Following (Kajitsuka & Sato, 2024), this quantization task is done by constructing the feed-forward layer as a 0-approximated step function. Consider real value piece-wise constant function (Step) IR + R, for any small 0 > 0, x E R, we have the 0-approximation as
(h (115-11
((Step) (x) lim
FRLLU(z/0-t6/0 - ReLU(x/0- -
8-+0
0,
if < 0;
ff
lim 8-40
(1)
W, hy $ x;;
which is series of small step functions, each beginning their rise at tō and ending at + t8. Here, show the first two
terms & = 0, for clarity. When t O, we have
0,
if x < 0; if < x <<
(ReLU(x/0) ReLU(x/0 1))8
z5/0,
8.
if <..
17

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
When = have
0, i
(ReLU(=/0- 5/0) -1100)) = zó/0, =
-
i
With Eq. (I), it is straightforward that we extend it to xd As a result, we have the first feed-forward layer FFN, as
FXN1 (1p+n)(1/6-1)
/0- ReLU(XX,, 1---100)
where i E [d],j E 1 + nn,00 0= < < and > O.
Taking the limit as 8 + O, we have
(I (1/61(116-11
lim 0
- - ReLU(X,,/0 1eLU(X,;00-1155/100 11t00011--000 = -](Stop)
(Xis):
With Eq. (2), we are able to quantize each sequence X + F. to quantized version M 98
Next, in order to utilize Lemma 5.4, we observe that the quantized input M from the previous step has no duplicate tokens, since each column has a unique domain. Also, we see that M token-wise (vd, vd(Lo 6), v vdo) separated where To Wr This is easily observed as we have, for any k E [y)
| 1 > Vd. |M 22 vd(h, ō),
| - L1l2 > Vd8.
As result, with Lemma 5.4, the single self-attention layer implements contextual mapping q w.) - (k we arrive at a (T, (J..))-cattettull mapping where
Vds 4 A (n
I va(Lo 8) vd(Lo 0.756),
Now we have successfully mapped each input sequence [P. + E to a unique context ID g(M) E ((hww))xd We next associate each unique embeddings to corresponding expected output of hangZing (+).
We associate each unique contextual embeddings the corresponding output of h(-) using the second feed-forward layer FFN2. As in Section A.5 of (Kajitsuka & Sato, 2024), this is achieved by constructing bump function foump IR (R.,,,))) xd + (h,, x for each possible output from the last step g(M()), E [1/8))((,,w))) Each bump function Soump realized by 3d(h,,r,)) MLP neurons. Therefore, we need (()(),,,,)))))))))))))))))))))) feed-forward layer FFN2, so that each contextual embedding is mapped to the expected output hangZing (+). A bump function foump for a quantized sequence A E G8 is written as:
MLP neurons to construct the
foump (Q) h(A)
Σ
(ReLU(K(Qrs - A..)) 1) ReLU(K(QL,s - A.))) + ReLU(K(Q Als) 1)),
d( d(
where E wd) is some context ID scalar K 0. Furthermore, we have the relation of quantization granularity 8 and function approximation enror C5(dh,w,)) e/2. We express the number of neurons in terms of as (e))))....)) = O(E O(e--((eee))) -d(h.w.)) where C is the Lipschitz constant and is from the -nom we use for measuring the approximation error.
As result, by choosing the appropriate step function approximation 0, we arrive at (himgggi (.), S c/2.
This completes the proof.
18

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
D. Training of FlowAR
In this section, we introduce the training FRowAR along with definitions based on (Ren et al., 2024).
In Section D.I, we introduce notation. Section D.2 covers sampling operations, Section D.3 expands them to linear ones. SectionD.4 details the VAE tokenizer, while Section D.5 specifies the transformer backbone. Section D.6 covers flow construction.
D.1. Notations
We first introduce notations used in FlowAR.
For matrix X E Reiraxd, we use X E R. Ruxxxxxe X to denote its tensorization, and we only assume this for letters X, X,Y,
D.2. Sample Function
In this section, we introduce the sample functions used in FlowAR.
We first introduce the up sample function.
Definition D.1 (Up Sample Function). If the following conditions hold:
Let h; N denote the height and weight of latent X hxxxxx
r > denote positive integer.
Then we define rp E I rxxwxx as the upsampling of latent X by factor r.
Then, we introduce the down sample function.
Definition D.2 (Down Sample Function). If the following conditions hold:
Let h, N denote the height and weight of latent X hxxex
Let > denote a positive integer.
Then define Down(X, r) E R x as the downsampling of latent X by factor
D.3. Linear Sample Function
In this section, we present the linear sample function in FlowAR.
We first present the linear up sample function.
Definition D.3 (Linear Up Sample Function). If the following conditions hold:
Let h, N denote the height and weight of latent X Axxxxx
Let r > denote positive integer.
Let T up
T (w be matrix.
Then we define the linear up sample function (.) as it computes == (xp(X. E grexruxe such that the matrix version of X and satisfies
Y 2 Pup E ((bbrw)xe
Then, define linear down sample function follows.
Definition D.4 (Linear Down Sample Function). If the following conditions hold:
19

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Let h, N denote the height and weight of latent X Rhxwxe
Let >
denote positive integer.
Let 4b down [(((//r)(((///)))x be a matrix.
Then define the linear down sample function @down (X, r) computes Y @down (X, E (B(1/)))((//))x such that the matrix version of X and Y satisfies
Y & downn X E (x)))
D.4. VAE Tokenizer
In this section, we show the VAE Tokenizer.
Definition D.5 (VAE Tokenizer). If the following conditions hold:
Let X hxwxe denote continuous latent representation generated by VAE.
Let denote the total number scales in FlowAR.
Let a be a positive integer.
For [K], let == K-t
For each E [K], let @doon,s(.s7)) (1) pxxxxe > (w/ denote the linear down sample function defined in Definition D.4.
For i E [K], we define the i-th token map generated by VAE Tokenizer be
== Odown, (X,r;) E (B(N/:))x(///))x
We define the output of VAE Tokenizer as follows:
Tokenizer(X) (Y), Y2 ,.... yk).
Remark D.6. In (Ren et al., 2024), they choose a = and hence for E [n]. re == 2 -i
D.5. Autoregressive Transformer
Firstly, we give the definition of a single attention layer.
Definition D.7 (Single Attention Layer). If the following conditions hold:
Let h, N denote the height and weight of latent X pxxxxx
Let Wo. WK. Wy e Rexe denote the weight matrix for query, key, and value, respectively.
Then we define the attention layer Attn(.) as it computes Y = Attn(X) E xxxxxe For the matrix version, we first need to compute the attention matrix E hhw
Arj == exp(X,, WoK. Wo J.), for for i,j e [hw].
Then, compute the output:
Y A-WW Rluxx
where diag(At (A1,) huwkww
To move on, we present the definition of multilayer perceptron.
20

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Definition D.8 (MLP layer). If the following conditions hold:
Let h, N denote the height and weight of latent X Rhxuxe
Let e denote the input dimension of latent IRxxuxe
Let d denote the dimension of the target output.
Let W Rexd denote weight matrix.
Let IR Ixd denote bias vector.
Then define mip layer it computes Y MLP(X, d) E Rhxxxd such that the matrix version of X and Y astisfies, for each j E [kw]],
Yj:- = X
b
1xc
oxd
1xd
We present the definition of layer-wise norm layer.
Definition D.9 (Layer-wise norm layer). Given latent X hxuxe, We define the layer-wise it computes LN(X) E Rxxuxe such that the matrix version of X and Y satisfies, for each j [hw]].
Xj: Py
Yjs-
where = Eisi X,.//C and Ei - -2)3//e
Definition D.10 (Autoregressive Transformer). If the following conditions hold:
Let X E bxxxxx denote a continuous latent representation generated by VAE.
Let K denote the total number of scales in FlowAR.
For i E [K], let Y; e ((//))x(w/n)xe be the i-th token map genereated by VAE Tokenizer defined in Definition D.5.
Let be a positive integer.
For E [K], let == K-1
For i E [ - 1), let Oup,i (,,)) ((/r)))(///)xxee R(//mss)(w//r:))x in Definition D.3.
be the linear up sample function defined
For E [K]. let Attn; (+) in Definition D.7.
w/r, R( w//r) be the i-th attention layer defined
w/r5)xe be the i-th feed forward network For i E [K], let (-) : RE M/r))) R Ei M/r)) defined Definition 3.5.
Let Zinit E (2hhm))x(//m)ixe be the initial input denoting the class condition.
Let Z = Zinit (M(//)))x(///x
For E [K] (1), Let Z be the reshape of the input sequence Zinit; Pup. 1 (Y) (Y,,a)...... ( a) into the tensor of size (E)=1 l/rr)) E w/r,) x
For i E [K], we define the Autoregressive transformer TF; as
TF, FFN, Attn, E W
We denote & as the i-th block of size (h/re) x (wr/rs) x e of the tensorization TF; (Z+).
21

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
D.6. Flow Matching
In this section, we introduce the flow matching definition.
Definition D.11 (Flow), If the following conditions hold:
Let X E kxxexe denote a continuous latent representation generated by VAB.
Let denote the total number scales in FlowAR.
For E [K], let Y; R(//r))) be the i-th token map genereated by VAE Tokenizer defined in Definition D.5.
For i [ let F (e( be matrix where each entry is sampled from the standard Gaussian N( 1).
We defined the interpolated input as follows:
F NY +1-
The velocity flow is defined as
dF; Yi
V = dt
Fo.
Here, we define the architecture of the flow matching model defined in (Ren al., 2024). Definition D.12 (Flow Matching Architecture). If the following conditions hold:
Let X E fxxxxx denote a continuous latent representation generated by VAE.
Let denote the total number scales in FlowAR.
For i E [K], let Y, E ((//))))(m/)xxx be the i-th token map genereated by VAE Tokenizer defined in Definition D.5.
Let E [K].
Let Y, ((//r))(m//)) be the i-th block of the output of Autoregressive Transformer defined in Definition D.10.
Let Fü be the interpolated input defined Definition D.11.
Let Attn:(-) [B(h/))X(///)))) + g( (x))))(ee/) be the i-th attention layer defined in Definition D.7.
Let MLP; (1, e, d) R(N)))((//)))) (xx) be the i-th attention layer defined in Definition D.8.
Let LN+(-) ((/))) + (m/r)))( be the i-th layer-wise norm layer defined in Definition D.9.
Let e [0, 1] denote time step.
Then define the i-th flow matching model NN, Y,,t,) ((//r))x(m//r))x x (M/r))((m/T))x x R +
(0//x)x(e/r)xxx, The tensor input needs to go through the following computational steps:
Step 1: Compute intermediate variables 01,, 022 31, 82, 71, 72. Specifically, have
an, 02 32, mi, 72 == MLP, (Y, +4 4 (//m))x((///)xx Gc)
Step 2: Compute intermediate variable
F
Specifically, we have
F = Attn; e LN((F) B1) 01
where denotes the element-vee wise product for tensors.
22

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Step 3: Compute final output Ft" Specifically, have
F = (7 LN(F,")
where o denotes the dlement-wise product for tensors.
Then, present training objective.
Definition D.13 (Loss of FlowAR). If the following conditions hold:
Let X E xxexe denote a continuous latent representation generated by VAE.
Let K denote the total number of scales in FlowAR.
For [K], let Y, ((/rra)(w//))x be the i-th token map genereated by VAE Tokenizer defined in Definition D.5.
For i E [K], let Y, E (R(M))((//:)xx) be the i-th block of the output of Autoregressive Transformer defined in Definition D.10.
For [K], let FÚ be the interpolated input defined in Definition D.11.
For i E [K], let V be the velocity flow defined in Definition D.11.
For i E [K]. let (N:(...)) (w/r)))((//)xxx x ((/))))((//xxx R R(M/))((w//)xx denote the i-th flow
matching network defined in Definition D.12.
The loss function of FR is
L(
[NN, 4,44) Vill?.
Unif
E. Inference of FlowAR
We define the architecture of FlowAR during the inference process as follows. Definition E.1 (FlowAR Architecture in the Inference Pipeline). If the following conditions hold:
Let denote the total number scales in FlowAR.
Let a be a positive integer.
For i [K], let a-
For i E [K - 1], let Auppil;s R(/nn)x(w/nxxxe__ [(//ss)x((//4ss)xx be the linear up sample function defined in Definition D.3.
For E [K] let Attn, (+) in Definition D.7.
w/ry)ee ((r) Xxe be the i-th attention layer defined
For i E [K]. let (-) : [E) (ry)) w/r/)xe Ei 4/rg) brr))(; w/r5)xx be the i-th feed forward network defined in Definition 3.5.
For i E [K]. let (N:(s:))) [((MT))x(=//xxx x ((//r))(///)xx K g(b/r)x(w//xxxx denote the i-th flow
matching network defined in Definition D.12.
For E [K], let f E [o, 1] denote the time steps.
For i E [K], let F; be the interpolated input defined in Definition D.I..
Let Zinit E ((/)))((u//)xxe denote the initial input denoting the class condition.
23

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
Let Zt = Ziit (R))
Then, we define the architecture of FlowAR in the inference pipeline as follows:
Layer 1: Given the initial token Z we compute
81 FFN, Attn (Z') [B()))((e/))x
$1 (F s1,t1)
-aaeer 2: Given the initial token Z and output of the first layer 81. Let Z2 be the reshape of the input sequence Zinit: Pup.1 ($1, a) into the tensor of size (Ei h/rr)) x (E w/r:) x c. Then we compute
$2 FFN Attn (Z²) M//n h/m.:/r:: w/r2.00.
$2 ( s2))2
Layer E [K])[ Given the initial token Z and the output of the first i 1 Bi..... , Let Z' be the reshape of the input sequence Zinit, (31) (ap.i-1(3;-1) into the tensor of size (E)=1 h/r;) x (Ej= w/r;) x c. Then we compute
8; FFN, o Attn, (Z" (2') Wr.Ej w/ry: 0/c
8F,,
Then the final output of FlowAR is šK.
24

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
F. High-Order Augmentation of Flow Autoregressive Transformers
In this section, we introduce High-Order Augmentation of Flow Autoregressive Transformers (HOFAR) from Liang et al. (2025b), which is a novel framework that embeds higher-order dynamies into flow-matching autoregressive generation, significantly strengthening the model's capacity to learn intricate, long-range dependencies.
In Section F.1, we introduce the training procedure of HOFAR. In Section F.2, we introduce the inference procedure of HOFAR.
E.1. Training Procedure of HOFAR
We present the algorithm for training HOFAR (Liang et al., 2025b) as follows.
Algorithm I High-Ordes FlowAR Training (Liang et al., 2025b)
1: procedure HOFARTRAININGGO, D)
2: 1 0 denotes the model parameters of TF, FMrrstt: FMsecond */
3: 8e D denotes the training dataset. */
4: while not converged do
5:
1 Sample an image from dataset. */
6:
Fing
/* Init loss as */
8:
8t 0
9:
1* Train the model on K pyramid layers. */
10:
for i = + K do
11:
1* Sample random noise. */
12:
F0 ~ IO
Sample a random timestep. */
t [0, 1]
15:
1 Calculate noisy input. */
16:
F noisy < OggTing +,,F0
17:
1t Calculate first-order ground-truth. */
18:
F first + d.Ting + 3
19:
Calculate second-orde order ground-truth truth. */
F Reccoud f- a²" Ting + 3
21:
1 Generate condition with Transformer.
22:
Y TF(Xing)
23:
1 Predict first-order with FM. */
24:
Fr.
fist + FMarst (Fi Y)
25:
Predict second-order with FM. #/
26:
Er
second +- FMsecood (Fi (Fi.isyy
noisy, Y)
27:
Caculate loss. #/
le
| firtt Firstt 112 F second
Ft
second
29:
30:
1+ Downsample Ting for next iteration. */
31:
Timg f- Ddown end for
32:
33:
1 Optimize parameter 0 with f. */
34:
+ VA l
end while
return 0 end procedure
37:
25

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
F.2. Inference Procedure of HOFAR
We present the algorithm for the inference of HOFAR (Liang et al., 2025b) as follows.
Algorithm 2 High-Order FRowAR Inference (I (Liang et al., 2025b)
1: procedure HOFAR INFERENCE(Cnput)
2: 7 Cipput denotes the condition embedding used for generation. */
3: /8 Init the Transformer input z with Cinput- */
4: x + Cinput
5: 1e Init the Zing with random noise. */
6: Jimg (O( I)
7: 1e Inference through K pyramid scales. */
8: for i = K do
9:
1* Pass through the Transformers TF. */
10:
Y TF(z)
11:
1 Extract last i tokens from Y as the condition embedding. *
12:
Zoond + [i...i++
13:
18 Generate first-order with FMaret- */
Vhirtt f- FMrt (Foond: Fimg)
14 Generate second-order with FMaecond. */
16:
Isccond 5Mseoodd (F (Feond, Zing)
17:
1 Apply first and second-order terms. */
18:
King &
Fing + Vfirst
At + 0.5 Bsecond (At)
19:
1* Upsample Ting- */
20:
Ting + Dup (Fimg)
21:
1 Concatenate upsampled Zing to the Transformer input. */
f- Concat(z, Fing)
23:
end for
24:
1" Return the final image */
25:
return Zimg
26: end procedure
26

---

Fundamental Limits of Visual Autoregressive Transformers: Universal Approximation Abilities
G. More Related Work
In this section, we introduce more related work.
Theoretical Machine Learning. Our work also takes inspiration from the following Machine Learning Theory work. Some works analyze the expressiveness of neural network using the theory of eircuit complexity (Li al., 2025b; Ke et al., 2025b; Li et al., 2024c; Chen al., 2025e; 2024a). Some works optimize the algorithms that can accelerate the training of a neural network (Li et al., 2024d; Ke et al., 2024; Deng et al., 2024; 2022; Zhang al., 2022; 2023b; Deng al., 2023a; Cao et al., 2025b; Song et al., 2025a; Liang et al., 2022a;b; Hu et al., 2022; Huang et al., 2020; Bian et al., 2023; Deng et al., 2023b; Song et al., 2025b; Gao et al., 2023c; 2025b; Gu et al., 2024; Gao et al., 2025a; Song et al., 2024b; Li et al., 2024e;a; Hu et al., 2024a). Some works incorporate fine-tuning to optimize neural networks (Huang et al., 2022; Hu et al., 2025b; Cao, 2024). Some works propose novel optimizers to accelerate the training neural networks (Song & Yang. 2023; Cao et al., 2024). Some works analyze neural networks via regressions (Chen et al., 2025c; Gao et al., 2023a; Li et al., 2023c; Gao al., 2023b; Sinha et al., 2023: Chen al., 2023; Song et al., 2023c; 2024a; 2023a;d; Li et al., 2025a). Some works use reinforcement learning to optimize the neural networks (Zhang et al., 2023a; 2025; Li et al., 2023a; Li & Yang, 2024; Liu et al., 2024c;b; Li et al., 2023b). Some works optimize the attention mechanisms (Song et al., 2023b; Liang et al., 2024a).
Accelerating Attention Mechanisms. The attention mechanism, with its quadratic computational complexity concerning context length, encounters increasing challenges as sequence lengths grow in modern large language models (OpenAI, 2024; AI, 2024; Anthropic, 2024). To address this limitation, polynomial kernel approximation methods (Aggarwal & Alman, 2022) have been introduced, leveraging low-rank approximations to efficiently approximate the attention matrix. These methods significantly enhance computation speed, allowing a single attention layer to perform both training and inference with nearly linear time complexity (Alman & Song, 2023; 2024b). Moreover, these techniques can be extended to advanced attention mechanisms, such as tensor attention, while retaining almost linear time complexity for both training and inference (Alman& & Song, 2024a). (Ke et al., 2025a) provides an almost linear time algorithm to accelerate the inference of VAR Transformer. Other innovations include RoPE-based attention mechanisms (Alman & Song, 2025a; Chen et al., 2024b) and differentially private cross-attention approaches (Liang et al.). Alternative strategies, such as the conv-basis method proposed in (Liang et al., 2024a), present additional opportunities to accelerate attention computations, offering complementary solutions to this critical bottleneck. Additionally, various studies explore pruning-based methods to expedite attention mechanisms (Liang et al., 2025a; Chen et al., 2025d: Li al., 2024b; Shen et al., 2025b;a; Hu al., 2024e; Wu et al., 2024; Xu et al., 2024a; Shen et al., 2025b). (Alman & Song, 2025b) studies the rank collapse property of self-attention network.
Gradient Approximation. The low-rank approximation is widely utilized approach for optimizing transformer training by reducing computational complexity (Liang et al., 2025c; 2024c; Alman & Song, 2024b; Hu et al., 2024d; Chen et al., 2025d; Liang et al., 2024b). Building on the low-rank framework introduced in (Alman & Song, 2023), which initially focused on forward attention computation, (Alman & Song, 2024b) extends this method to approximate attention gradients, effectively lowering the computational cost of gradient calculations. The study in (Liang et al., 2025c) further expands this low-rank gradient approximation to multi-layer transformers, showing that backward computations in such architectures can achieve nearly linear time complexity. Additionally, (Liang et al., 2024c) generalizes the approach of (Alman & Song, 2024b) to tensor-based attention models, utilizing forward computation results from (Alman & Song, 2024a) to enable efficient training of tensorized attention mechanisms. Lastly, (Hu et al., 2024d) applies low-rank approximation techniques during the training of Diffusion Transformers (DiTs), demonstrating the adaptability of these methods across various transformer- based architectures.
27


Reviews:
[{"review_id": "Y6M2QsKrIG", "reviewer": "Reviewer_1PzP", "summary": "This paper aims to understand transformer-based models in image generation focusing on Visual Autoregressive Transformers (VAR). Transformers have already been shown to be universal approximators in certain settings (e.g., language tasks via prompt tuning [1]), but it is not clear if its visual counterpart (VAR) can approximate any continuous image-to-image transformation. The paper proves that the simplest form of VAR transformer (single self-attention layer and a single interpolation layer) is a universal approximator for Lipschitz continuous functions. \n\n[1] Hu, Jerry Yao-Chieh, et al. \"Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency.\" _arXiv preprint arXiv:2411.16525_ (2024).", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer for these insightful comments, and we would like to address the reviewer’s concerns as follows. \n### Claims And Evidence: On the broader implications claim \nWe acknowledge that our claim regarding broader implications for CV could be better supported. Our intention was to highlight that understanding theoretical expressivity provides a foundation for more practical research on efficiency and quality. \n### Theoretical Claims & Essential References Not Discussed & Weakness 1: On the applicability of prompt tuning theory to VAR\nThis is an insightful question. While our proof builds on techniques from [1], we've carefully adapted them to the VAR setting. The universality result doesn't actually depend on the training method (prompt tuning vs. full fine-tuning) but rather on the architectural expressivity. The key insight is that if a model family can approximate any function when only a subset of parameters are tuned (prompt tuning), then it can certainly do so when all parameters are tunable (full training). The prompt tuning framework provides a convenient theoretical framework to establish lower bounds on expressivity.\n### Weakness 2: On single-layer architecture and up-scaling\nYou raised an important point about the relationship between the transformer layer and up-scaling steps. To clarify, Theorem 4.3 and 4.4 state that a single self-attention layer and a single interpolation layer are sufficient for universal approximation. This does not contradict VAR's hierarchical nature. The up-interpolation layer (Definition 3.6) can have multiple internal up-scaling steps while still being considered a single layer from the architectural perspective. Our proof shows that even with minimal architecture (single attention + single interpolation), the model class has universal approximation capabilities.\n### Other Comments Or Suggestions: On terminology inconsistency\nThank you for noting the inconsistent use of \"sequence-to-sequence\" and \"image-to-image.\" This was indeed a source of potential confusion. Since VAR operates on tokenized images, both terminologies are technically correct - images are processed as sequences of tokens. In our theoretical analysis, we view images as structured sequences. We should have been more explicit about this connection in our manuscript.\n\nWe appreciate your feedback and would be happy to address any follow-up questions you might have.", "claims_and_evidence": "The third claim regarding broader implication for CV community (`We provide insights into the broader implications of our findings for generative modeling, particularly in computer vision, where efficient and expressive architectures are essential for high-quality image synthesis.`) lacks support. The paper provides no theoretical analysis or empirical results of efficiency or generation quality. While VAR's empirical success is noted in prior work [2], this work focuses purely on universality. Without connecting approximation capacity to practical efficiency or image quality metrics, this claim remains speculative.\n\n[2] Tian, Keyu, et al. \"Visual autoregressive modeling: Scalable image generation via next-scale prediction.\" _Advances in neural information processing systems_ 37 (2024): 84839-84865.", "methods_and_evaluation_criteria": "Not applicable. This paper proposes a new theoretical understanding of VAR. No experiments are presented.", "theoretical_claims": "I found the core universality proof (Section 6) inherit assumption from Hu et al. [1], which analyzes prompt-tuned Transformers where base mode is frozen. However, VAR training typically updates all training parameters. I found this discrepancy raises questions about the proof's applicability.\n\n[1] Hu, Jerry Yao-Chieh, et al. \"Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency.\" _arXiv preprint arXiv:2411.16525_ (2024).", "experimental_designs_or_analyses": "Not applicable. This paper proposes a new theoretical understanding of VAR. No experiments are presented.", "relation_to_broader_scientific_literature": "Prior works have already shown transformers are universal approximates in certain settings. This paper extends that understanding to visual autoregressive models.", "essential_references_not_discussed": "This paper cites Hu et al. (2024) [1] but inadequately distinguishes its contributions. While Hu et al. focus on prompt tuning for language tasks, this work targets VAR’s image-to-image mapping. A deeper discussion is needed on why the universality of prompt-tuned models implies universality for fully trained VARs.\n\n[1] Hu, Jerry Yao-Chieh, et al. \"Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency.\" _arXiv preprint arXiv:2411.16525_ (2024).", "other_strengths_and_weaknesses": "Strengths: \nI found the question the authors aim to study is timely and underexplored. In terms of theory, the Transformer model is often studied in the context of language modeling. The setting of image generation is much less studied.\n\nWeakness: \n- **Overreliance on Prompt Tuning Theory**: The proposed theory heavily relies on Hu et al. (2024) [1]. However, Hu et al. assume the transformer is funetuned with prompt tuning. This contradicts the VAR setting, which updates all parameters.\n- **Single-Layer Architecture**: The conclusion states that one layer suffices for universality. However, VAR’s hierarchical up-scaling (Def. 3.6) implies multiple up-scaling steps. When the transformer layer is a single layer, does it imply we can achieve universality with one up-scaling step?", "other_comments_or_suggestions": "Terms like \"sequence-to-sequence\" and \"image-to-image\" are used interchangeably (e.g., Abstract vs. Section 4). This causes ambiguity. It would improve the clarity if the differences and similarities were discussed.", "questions_for_authors": "My main question to the authors is regarding how prompt tuning assumption affects the theoretical analysis of the VAR model.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YW1iHCmY2b", "reviewer": "Reviewer_QcLH", "summary": "The paper examines the fundamental limits of Visual Autoregressive (VAR) transformers, proving that single-head VAR transformers with a single self-attention layer and single interpolation layer are universal approximators. By adapting the established techniques in function approximation and neural network to VAR transformers, the authors demonstrate how a minimal VAR transformer is sufficient to approximate any Lipschitz sequence-to-sequence function with arbitrarily small error. The results provide insights into the theoretical expressiveness of VAR transformers, showing how VAR can be utilized as an efficient and expressive architectures for high-quality image synthesis", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive assessment of our paper. We appreciate your recognition of the theoretical contributions and clear organization of our work.\nRegarding your question about designing experiments to demonstrate VAR Transformers as universal approximators for image-to-image tasks: This is an excellent suggestion. While our current paper focuses on theoretical foundations, empirical validation would indeed enhance the practical value of our work.\nFor such an experiment, we envision the following design:\n1. Select diverse image-to-image transformation tasks (e.g., style transfer, super-resolution, colorization, and semantic transformations)\n2. Train minimalist VAR models (with single attention/interpolation layers) on these tasks\n3. Compare their performance against more complex architectures and theoretical bounds\n4. Measure approximation quality using metrics like PSNR, SSIM, and FID\n\nWe believe such experiments would demonstrate how even simple VAR architectures can approximate complex image transformations, providing empirical support for our theoretical claims. The experiments would also help identify practical limitations and the relationship between theoretical expressivity and sample efficiency.\n\nWe agree that including these experiments would strengthen our paper, and we're considering this direction for future work. Thank you for this valuable suggestion.", "claims_and_evidence": "The claims made in the submission is supported by theoretical proofs.", "methods_and_evaluation_criteria": "By investigating into a minimum VAR Transformer design the paper makes it clear why VAR Transformers are universal.", "theoretical_claims": "I checked the correctness of two theorems (Theorem 4.3 and Theorem 4.4) about the  universality of VAR Transformer.", "experimental_designs_or_analyses": "The paper does not contain any experiments.", "relation_to_broader_scientific_literature": "The key contributions of the paper that VAR Transformers are universal approximators provide a theoretical foundation that VAR architecture can be an efficient and expressive architectures for the image synthesis tasks.", "essential_references_not_discussed": "The paper cited/discussed essential related works.", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is well-organized and clearly written.\n2. The theoretical proof in the paper is sufficient.\n\nWeaknesses:\n\nThe paper has no experiments, limiting its practical value.", "other_comments_or_suggestions": "No, I have no other comments or suggestions.", "questions_for_authors": "Can you design an experiment with VAR Transformers to demonstrate how they can be universal approximator for image-to-image tasks?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y4X7I5iNZu", "reviewer": "Reviewer_FKqB", "summary": "This paper shows that single-head, single-layer VAR transformers are universal approximators for Lipschitz image-to-image mappings, enabling them to approximate continuous transformations. This establishes their theoretical expressiveness and sets a new image synthesis benchmark, outperforming methods like Diffusion Transformers. The findings highlight key design principles for efficient and scalable generative models in computer vision.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and recognition of our theoretical contributions. We appreciate your detailed feedback and would like to address the weaknesses you highlighted:\n### Weakness 1: On connecting theory to practical applications\nYou raise an important point about establishing a clearer connection between our universality results and practical applications in image generation. The universal approximation property theoretically guarantees that VAR Transformers can represent any continuous image transformation function given sufficient capacity. In practice, this explains why VAR models excel at diverse image generation tasks - they have the representational capacity to learn complex image distributions and transformations. The \"next-scale prediction\" framework leverages this flexibility by decomposing the generation process into a sequence of progressively refined predictions, each of which benefits from the universal approximation capability.\n### Weakness 2: Lack of experimental results\nWe acknowledge this limitation in our current paper. Our focus was on establishing the theoretical foundations, but we agree that empirical validation would strengthen our claims. In future work, we plan to conduct experiments demonstrating how the universal approximation capabilities translate to practical performance on image generation tasks, possibly showing how approximation quality scales with model complexity.\n### Weakness 3: Figure 1 caption\nThank you for noting this issue. You're right that the figure caption lacks necessary details. In the figure, $X_1$ and $X_2$ represent token maps at different resolutions, while $X_{init}$ represents the initial token. The diagram shows how a single token $(X_{init})$ is expanded to create token maps at progressively higher resolutions through the up-interpolation process.\n### Other Comments Or Suggestions: Redundancy between Section 3.2 and the supplementary material: \nWe appreciate your suggestion. This redundancy was inadvertently introduced to ensure the main paper was self-contained while providing additional details in the supplementary material. We agree that streamlining this content would improve the paper.\n\nThank you again for your constructive feedback. We believe addressing these points would strengthen our paper considerably.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes. This paper includes analysis, but no experiments are supplied.", "relation_to_broader_scientific_literature": "The paper's key contributions relate to the broader scientific literature by providing foundational design principles for VAR Transformers, advancing the understanding of efficient and scalable architectures for image generation or other related areas.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength: \nThis paper stands out for its theoretical novelty, proving the universality of simple VAR transformers and introducing a scalable \"next-scale prediction\" framework. It achieves state-of-the-art performance in image synthesis, outperforming existing methods like Diffusion Transformers, and provides practical design principles for efficient and effective model development, with broad applicability in generative modeling.\n\n\nWeakness:\n1. While VAR Transformers are widely popular and recognized for their power in various domains, e.g., image generation, the paper does not explicitly establish a clear connection between proving the universality of VAR Transformers as function approximators and their practical application in image generation. Exploring this connection would strengthen the relevance of the theoretical findings to real-world use cases.\n2. The paper focuses solely on theoretical analysis without providing experimental results. Including quantitative or qualitative evaluations would help validate the effectiveness of the proposed approach and provide a more comprehensive understanding of its performance.\n3. The caption of Figure 1 lacks sufficient detail to clarify the data flow of the Pyramid Up-Interpolation Layer. Specifically, it is unclear where $X_1$ and $X_2$ originate from, and the distinctions between $X_{1/2}$ and $X_{init}$ are not explained. Adding a clear description in the caption or main text would improve the paper's clarity and accessibility for readers.", "other_comments_or_suggestions": "The descriptions in Sec 3.2 of the main paper and in Fact A.1/2/3 of the supplementary material appear repetitive. I suggest removing one of them to eliminate redundancy.", "questions_for_authors": "See weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper investigates the fundamental limits of Visual Autoregressive transformers, providing theoretical evidence that single-head VAR transformers with only a single self-attention and interpolation layer are universal approximators for Lipschitz continuous image-to-image functions. The reviewers have some concerns regarding the lack of direct empirical experiments to bridge the theory-practice gap, but they generally agreed that the theoretical contributions are significant, novel, and well-articulated, providing important insights into the capabilities and design principles for VAR architectures.

Overall, I recommend acceptance of this paper.
Decision: Accept (poster)