Pith. sign in

REVIEW 4 major objections 5 minor 3 cited by

Universal Approximation of Visual Autoregressive Transformers

T0 review · 4 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that even a minimal Visual Autoregressive Transformer with one attention head, one self-attention layer, and one interpolation layer can approximate any Lipschitz image-to-image map, and that FlowAR inherits this…

desk verdict The central universality claim is false for the architecture as defined: a 1×1 input produces constant images at every scale, and the proof has invalid steps. read the letter →

arxiv 2502.06167 v1 pith:QFHX73ZY submitted 2025-02-10 cs.LG cs.AIcs.CLcs.CV

Yifang Chen , Xiaoyu Li , Yingyu Liang , Zhenmei Shi , Zhao Song This is my paper · ORCID
classification cs.LGcs.AIcs.CLcs.CV MSC 68T07
keywords visualautoregressivetransformeruniversalapproximationLipschitzfunctionsnext-scalepredictionself-attentioncontextualmappingflowmatchingup-interpolationlayer
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper is trying to establish that minimal Visual Autoregressive transformers are universal approximators: a VAR transformer with a single attention head, a single self-attention layer, and a single interpolation layer per block can approximate any Lipschitz map from images to images to arbitrary precision. If true, this would mean that expressiveness does not require scale, and even the smallest version of the architecture can in principle represent complex image transformations. The same perturbation argument is extended to FlowAR, a flow-matching autoregressive variant, to show it inherits the universality property. The theorem's scope is the class of target maps that decompose into Lipschitz scale-to-scale factors, each approximable by the fixed bicubic up-sampling kernel used by the model.

What carries the argument

The load-bearing object is the pyramid up-interpolation layer $\Phi_{\mathrm{up},r}$: a fixed bicubic-spline operator that linearly raises each token map to the next resolution, so it can be treated as a matrix. Around it the paper composes VAR blocks $\mathrm{TF}_{\mathrm{var}} = \mathrm{FFN} \circ \mathrm{Attn} \circ \phi_{\mathrm{up}}$, where $\mathrm{Attn}$ is a single-head self-attention layer. Two prior ingredients carry the argument: any-rank single-layer attention acts as a $(\gamma,\delta)$-contextual mapping, assigning distinct context IDs to distinct input sequences even when individual tokens coincide, and a single-self-attention-layer transformer from the class $T^{1,1,4}_A$ is already a universal sequence-to-sequence approximator. The perturbation lemmas then measure what happens when each target factor $g_i$ is replaced by $\phi_{\mathrm{up},i}$ and each $f_i$ by its transformer approximation $\tau_i$; the total error is a sum of per-layer errors weighted by powers of the Lipschitz constant $K_2$, and Theorem 5.6 closes the sum into a geometric bound.

What would settle it

Choose a Lipschitz image-to-image map whose coarse-to-fine stages are far from bicubic interpolation—for instance, each stage translates a high-frequency pattern by a different amount—and check whether the minimal VAR transformer of Theorem 5.6 can approximate it with error below $\epsilon$ for arbitrarily small $\epsilon$; a positive lower bound on the achievable error would show the universality claim fails outside the kernel-aligned class.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that universality survives the pyramid up-sampling structure. For any target map $f_{\mathrm{word2img}} = f_r \circ g_r \circ \cdots \circ f_1 \circ g_1$ whose factors are $K$-Lipschitz and whose scale transitions $g_i$ can be approximated by the model's up-interpolation layers $\phi_{\mathrm{up},i}$, Theorem 5.6 constructs a VAR transformer $\tau_{\mathrm{VAR}} = (\mathrm{FFN} \circ \mathrm{Attn} \circ \phi_{\mathrm{up}})^r$ with error bounded by $K_2^n(K_{1,i}\epsilon_{1,i}+\epsilon_{2,i})$, which can be made arbitrarily small. The argument shows that each replaced stage contributes error only through its Lipschitz constant, so attention, interpolation, and feed-forward layers compose without amplifying error beyond a geometric factor. Corollaries 6.1 and 6.2 transfer the same bound to FlowAR by swapping up-interpolation for down-interpolation. The paper therefore claims that approximation power is not a reason to prefer deep or many-headed VAR models over minimal ones.

Load-bearing premise

The proof rests on Assumption 5.2, which requires each scale-transition map of the target to be approximable by the fixed bicubic up-sampling layer, so the claimed universality covers arbitrary Lipschitz maps only if their coarse-to-fine steps look like that interpolation kernel.

Editorial extensions

If this is right

  • Minimal VAR transformers—one head, one self-attention layer, one interpolation layer per block—can represent any Lipschitz image-to-image map in the Assumption 5.2 class to arbitrary precision, so additional depth or heads are not needed for representational completeness.
  • FlowAR inherits the same universality result, so flow matching and autoregressive attention can be combined without losing approximation guarantees.
  • The composition error is governed by a per-layer budget: each scale transition contributes $K_{1,i}\epsilon_{1,i}+\epsilon_{2,i}$ to the final error, scaled by a power of the Lipschitz constant $K_2$.
  • The theorem gives a design principle: keeping each coarse-to-fine transition close to the model's interpolation operator keeps the target within the representable class at every resolution.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The authors leave implicit that the proof only needs $\phi_{\mathrm{up}}$ to be a fixed linear map, so the same argument should hold for any fixed linear resampling kernel, not just bicubic.
  • The $K_2^n$ factor means the guarantee is qualitative: at many scales or large Lipschitz constants, the bound is too loose to predict practical accuracy, so explaining empirical performance needs a sharper scale-aware bound.
  • A testable extension is to train a single-head, single-layer VAR transformer on synthetic image-to-image targets with known Lipschitz constants and verify that the error follows the per-layer decomposition of Lemma 5.3.
  • The perturbation technique should transfer to other hierarchical tokenizers with linear scale transitions, such as residual-quantization or patch-pyramid image models.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper claims to prove that minimal single-head, single-attention-layer, single-interpolation-layer Visual Autoregressive (VAR) transformers are universal approximators for any image-to-image Lipschitz function, and that FlowAR inherits this property. The proof strategy is to import the contextual-mapping transformer universality theorem of Hu et al. (HWG+24), model the target as a composition of Lipschitz functions and up-interpolation operators (Assumption 5.2), and derive perturbation lemmas (Lemmas 5.3–5.5) bounding the error when each target layer is replaced by a VAR block. The main universality result is Theorem 5.6; Section 6 states analogous FlowAR results. The paper is written as a theory contribution with no experiments and no code.

Significance. The intended result would be significant: universality for an extremely simple hierarchical transformer would help explain why next-scale prediction models are expressive and would align VAR and flow-based architectures with known universality results for plain transformers. The paper also usefully sets out explicit definitions of the VAR transformer block and identifies a perturbation framework that such a proof would need. However, the significance is conditional on the proof, and the proof has a decisive expressivity flaw: the defined architecture maps every 1x1 input to a constant image. In addition, the perturbation argument relies on a linearity step that is false for Lipschitz maps, and the target class in Assumption 5.2 is a restrictive subclass rather than the full Lipschitz class claimed in the abstract. These issues concern the central claim and are not local presentation defects.

major comments (4)
  1. [§5.3, Lemma 5.4] The proof of Lemma 5.4 is invalid. After defining w = (◦_{i=0}^{j-1} u_i)(x), the proof claims ∥◦_{i=j+1}^{n+1} v_i(u_j(w)) − ◦_{i=j}^n v_i(v_j(w))∥ = ∥◦_{i=j+1}^{n+1} v_i(u_j(w) − v_j(w))∥ and justifies this 'by linearity.' The maps v_i are only assumed to satisfy v_i(x) ≤ K_2∥x∥, not to be linear; Lipschitz or sublinear functions are not linear, and composition of such maps is not a linear operator. The bound ∥...∥ ≤ K_2^{n-j}ϵ therefore does not follow. Since Lemma 5.4 is the engine that turns per-layer approximations into the global error bound of Theorem 5.6, the main theorem is unsupported. A related invalid step appears in Lemma 5.3, where ∥f_i◦g_i − f_i◦Φ_up,i∥ is replaced by ∥f_i◦(g_i−Φ_up,i)∥; this identity holds only for affine f_i.
  2. [§3.2–3.3, Definitions 3.2, 3.4, 3.6, 3.8] The architecture as defined cannot produce a non-constant spatial output from a 1x1 input, regardless of Assumption 5.2. Φ_up,1(X_init)=X_init, and the first up-interpolation creates a block of tokens all equal to the single input token. Attention (Definition B.3) has no positional encoding or token-specific bias, so identical tokens have identical query, key, and value vectors, making the attention output identical for all tokens; the per-token FFN (Definition B.5) with shared weights and biases preserves equality. Inductively, every scale is a constant image, so TF(X_init) is constant. The model therefore cannot approximate even the Lipschitz map f(x)=(x,0,0,0) from R^{1×1×1} to R^{2×2×1} whose 2x2 output has distinct pixels. This contradicts the abstract's universality claim and holds independently of Assumption 5.2. It also means that the upsampled inputs violate the tokenwise-separateness condition required by Lemma 4.4 and Lemma 5.1.
  3. [Assumption 5.2 and Theorem 5.6] Assumption 5.2 restricts the target to functions f_word2img = f_r◦g_r◦...◦f_1◦g_1 in which each g_i 'can be approximated by some up interpolation function φ_up,i.' Since φ_up,i is the fixed bicubic-spline upsampling operator from Definition 3.2, the theorem covers only targets whose scale transitions lie near that fixed operator, not arbitrary Lipschitz image-to-image maps. The abstract's statement that the result holds 'for any image-to-image Lipschitz functions' is therefore not established. In addition, the dimensions in Assumption 5.2 are inconsistent: f_1,...,f_r are all stated as maps from R^{h_r×w_r×d} to itself, but in the composition each f_i must act at an intermediate scale R^{h_i×w_i×d}. Finally, the error bound in Theorem 5.6 depends on K_2 and n, while Assumption 5.2 defines only K and K_{1,i}, and the composition has r scales; as written, the bound is not well formed.
  4. [Section 6, Corollaries 6.1 and 6.2] The FlowAR results are asserted rather than proved. Corollary 6.1 says the proof 'mirrors' the two-layer perturbation argument, but that argument inherits the invalid linearity step of Lemma 5.4. Corollary 6.2 states that ∥τ_FlowAR − f_word2img∥ ≤ O(ϵ) with no construction of τ_FlowAR, no specification of ϵ, no norm in which the error is measured, and no dependence on depth or Lipschitz constants. This is not a proof that FlowAR inherits universality.
minor comments (5)
  1. [§5.4, Lemma 5.5] The statement contains a dangling 'Let ◦i=1' and the indices in the proof are unclear; the lemma should be restated with a well-formed composition and consistent use of n and r.
  2. [§3.3, Remark 3.7 and Definition 3.8] The reference to 'Definition 4.9 from [KLL+25a]' does not match the numbering in this manuscript, where the relevant object is Definition 3.8.
  3. [§5.1, Lemma 5.1] The function class FC is never defined, and the expression ∥τ(·), L∥_α appears to be a typo for ∥τ(·) − L∥_α; please clarify the norm and the quantifiers.
  4. [Abstract and Theorem 5.6] The abstract claims a 'single self-attention layer and single interpolation layer,' but Theorem 5.6 concerns m composed VAR blocks, each with its own attention and upsampling; the parameterization of the minimal model should be stated precisely.
  5. [Definition 3.2] The up-interpolation formula evaluates X at coordinates such as i·h_{r−1}/h_r + s that are not integers; the manuscript should state how out-of-range or fractional indices are defined.

Circularity Check

2 steps flagged · score 6.0 of 10

The paper's universality claim is conditional on Assumption 5.2, which defines the target class using the model's own bicubic upsampling operator; the remaining approximation engine is imported from a same-group preprint.

  1. self definitional [Section 5.2, Assumption 5.2; Section 5.5, Theorem 5.6]
    "For each i ∈ [r], let gi be a K-Lipschitz function from Rhi−1×wi−1×d to Rhi×wi×d. We assume that for each i ∈ [r], gi can be approximated by some up interpolation function ϕup,i. We assume that the target function fword2img : R1×1×d → Rhr×wr×d satisfies fword2img := fr ◦ gr · · · ◦f1 ◦ g1."

    The target function class is defined by requiring every scale-transition map gi to be close to the fixed bicubic up-interpolation ϕup,i, which is exactly the operation the VAR architecture uses. Theorem 5.6 then bounds ∥τVAR − fword2img∥ by Kn2(K1,iϵ1,i + ϵ2,i); making this error arbitrarily small requires each gi to coincide with Φup,i up to ϵ. Thus the claimed 'universal approximator for any image-to-image Lipschitz functions' is not derived: the theorem applies only to functions whose scale transitions are already aligned with the model's upsampling layer. Arbitrary Lipschitz maps need not satisfy this, so the abstract's universality statement reduces to the assumption that the target lies in the model's own generative class.

  2. self citation load bearing [Section 5.1, Lemma 5.1; Section 5.5, Theorem 5.6]
    "We used a universality result from [HWG+24]. Lemma 5.1 (τ ∈ T1,1,4 A Transformer is Universal Seq2Seq Approximator, Theorem 2.3 in [HWG+24] on Page 11) ... Then, there exists a transformer τ with single self-attention layer, such that for any L ∈ FC there exists ∥τ (·), L∥α ≤ ϵ."

    [HWG+24] shares author Zhao Song with this paper. This lemma is the only source of the approximating transformers τi for each fi; Theorem 5.6 merely composes these τi with the upsampling maps. If the self-cited preprint's universality theorem is not accepted, the present paper supplies no independent existence proof for the τi components. Because the cited result is an unreviewed arXiv preprint from the same group rather than a machine-checked or externally reproduced theorem, the central VAR universality argument is load-bearing on a self-citation.

full rationale

The main theorem is honestly stated as conditional on Assumption 5.2, and its proof would be a legitimate perturbation argument if that assumption held for arbitrary Lipschitz maps; it does not. The abstract's unconditional claim for 'any image-to-image Lipschitz functions' is therefore unsupported: the ϵ1,i term in the bound is nonzero for generic Lipschitz scale transitions. Separately, the architecture starts from a 1×1 token map with no positional encoding, so all upsampled tokens are identical and the final output is constant; this is a serious correctness defect, but it is an expressivity failure rather than a circularity, so I do not add it to the circularity score. The two circularity-relevant features are the self-definitional target class and the load-bearing self-citation of [HWG+24]. These justify a score of 6 rather than 0-2: the central universality claim partially reduces to its own assumptions and to a same-group preprint, though the theorem as formally stated still has some conditional content.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The proof rests on three pillars: the imported single-attention-layer universality theorem from HWG+24, the assumption that target scale maps are close to the fixed upsampling operator, and Lipschitz perturbation bounds. The first is a black box from overlapping authors; the second restricts the target class so severely that the advertised universality is not achieved; the third contains an invalid linearity step. There are no invented physical entities or fitted constants in the usual sense.

free parameters (1)
  • per-layer approximation errors epsilon_1,i and epsilon_2,i
    Assumption 5.2 and Theorem 5.1 require each scale-transition map g_i to be within epsilon_1,i of the fixed upsampling operator and each internal map f_i to be within epsilon_2,i of a one-layer transformer. These errors are assumed small, but the paper gives no construction or bound that would make them small for arbitrary Lipschitz targets.
assumptions (4)
  • ad hoc to paper The target f_word2img factorizes as f_r composed with g_r composed with ... composed with f_1 composed with g_1, and each g_i is approximable by the fixed bicubic up-interpolation operator within epsilon_1,i.
    Assumption 5.2. This is the key restriction that makes the theorem work, but arbitrary Lipschitz image-to-image functions do not generally satisfy it.
  • standard math The cited theorem from HWG+24 that a single-attention-layer transformer T^{1,1,4}_A with O((1/epsilon)^{dn}) feed-forward layers is a universal sequence-to-sequence approximator.
    Lemma 5.1 imports this result as a black box. The paper does not re-prove it, and HWG+24 is authored by an overlapping group.
  • domain assumption All functions f_i and g_i are K-Lipschitz, each f_i is K_{1,i}-Lipschitz, and the composition uses K_2 > 2.
    Assumption 5.2 and Theorem 5.6. These constants enter the exponential error bound, and no attempt is made to control their growth with the number of scales.
  • standard math The up-interpolation layer is a linear operator, so phi_up can be viewed as a matrix.
    Section 3.3 and Remark 3.7 use the linearity of bicubic interpolation to treat upsampling as matrix multiplication when composing model blocks.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Universal Approximation of Visual Autoregressive Transformers." pith.science (2026). https://pith.science/paper/QFHX73ZY

@misc{pith2026250206167,
  author       = {Pith},
  title        = {Pith review of: Universal Approximation of Visual Autoregressive Transformers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QFHX73ZY}},
  note         = {Machine review of arXiv:2502.06167}
}
read the original 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 image-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.

Figures

Figures reproduced from arXiv: 2502.06167 by the authors.

Figure 1
Figure 1. One Pyramid Up-Interpolation Layer Instance Φ [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. CoVE: Compressed Vocabulary Expansion Makes Better LLM-based Recommender Systems

    cs.IR 2025-06 conditional novelty 6.0 of 10

    CoVE assigns each item a unique token ID, tunes item embeddings and the LM head, and predicts the next item from logits, beating finetune-and-retrieval baselines by up to 62 percent with a 16x compressed embedding table.

  2. Reasoning Like an Economist: Post-Training on Economic Problems Induces Strategic Generalization in LLMs

    cs.AI 2025-05 conditional novelty 6.0 of 10

    Post-training an LLM on economic reasoning problems improves accuracy on economic benchmarks and, without game-specific training, raises its Nash equilibrium frequency and win rates in strategic games.

  3. Force Matching with Relativistic Constraints: A Physics-Inspired Approach to Stable and Efficient Generative Modeling

    cs.LG 2025-02 reject novelty 4.0 of 10

    Force Matching replaces velocity matching in flow-based generative models with a relativistic force objective, but the toy experiments are designed so the model class matches the data generator exactly.

Reference graph

Works this paper leans on

63 extracted references · 19 canonical work pages · cited by 3 Pith papers

  1. [3]

    Richspace: Enriching text-to-video prompt space via text embedding interpolation

    [CGL+25a] Yuefan Cao, Chengyue Gong, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. Richspace: Enriching text-to-video prompt space via text embedding interpolation. arXiv preprint arXiv:2501.09982 ,

    arXiv

  2. [5]

    Fast gradient computation for rope attention in almost linear time

    [CHL+24] Yifang Chen, Jiayan Huo, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, and Zhao Song. Fast gradient computation for rope attention in almost linear time. arXiv preprint arXiv:2412.17316,

    arXiv

  3. [7]

    Bypassing the exponential dependency: Looped transformers efficiently learn in-context by multi- step gradient descent

    [CLL+24b] Bo Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, and Zhao Song. Bypassing the exponential dependency: Looped transformers efficiently learn in-context by multi- step gradient descent. arXiv preprint arXiv:2410.11268 ,

    arXiv

  4. [8]

    The compu- tational limits of state-space models and mamba via the lens of circuit complexity

    [CLL+24c] Yifang Chen, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, and Zhao Song. The compu- tational limits of state-space models and mamba via the lens of circuit complexity. arXiv preprint arXiv:2412.06148 ,

    arXiv

  5. [9]

    Dissecting submission limit in desk-rejections: A mathematical analysis of fairness in ai conference policies

    [CLL+25] Yuefan Cao, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, and Ji- ahao Zhang. Dissecting submission limit in desk-rejections: A mathematical analysis of fairness in ai conference policies. arXiv preprint arXiv:2502.00690 ,

    arXiv

  6. [10]

    Hsr-enhanced sparse attention acceleration

    [CLS+24] Bo Chen, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. Hsr-enhanced sparse attention acceleration. arXiv preprint arXiv:2410.10165 ,

    arXiv

  7. [12]

    Zero-th order al- gorithm for softmax attention optimization

    [DLMS24] Yichuan Deng, Zhihang Li, Sridhar Mahadevan, and Zhao Song. Zero-th order al- gorithm for softmax attention optimization. In 2024 IEEE International Conference on Big Data (BigData) , pages 24–33. IEEE,

    work page 2024

  8. [13]

    Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension

    25 [DMS23] Yichuan Deng, Sridhar Mahadevan, and Zhao Song. Randomized and deterministic attention sparsification algorithms for over-parameterized feature dimension. arXiv preprint arXiv:2304.04397,

    work page Pith review arXiv

Show all 63 references
  1. [14]

    A nearly optimal size coreset algorithm with nearly linear time

    [DSWY22] Yichuan Deng, Zhao Song, Yitan Wang, and Yuanyuan Yang. A nearly optimal size coreset algorithm with nearly linear time. arXiv preprint arXiv:2210.08361 ,

    arXiv

  2. [15]

    Faster robust tensor power method for arbitrary order

    [DSY23] Yichuan Deng, Zhao Song, and Junze Yin. Faster robust tensor power method for arbitrary order. arXiv preprint arXiv:2306.00406 ,

    arXiv

  3. [17]

    A fast optimization view: Reformulating single layer attention in llm based on tensor and svm trick, and solving it in matrix multiplication time

    [GSWY23] Yeqi Gao, Zhao Song, Weixin Wang, and Junze Yin. A fast optimization view: Reformulating single layer attention in llm based on tensor and svm trick, and solving it in matrix multiplication time. arXiv preprint arXiv:2309.07418 ,

    arXiv

  4. [18]

    In-context learning for attention scheme: from single softmax regression to multiple softmax regression via a tensor trick.arXiv preprint arXiv:2307.02419,

    [GSX23] Yeqi Gao, Zhao Song, and Shenghao Xie. In-context learning for attention scheme: from single softmax regression to multiple softmax regression via a tensor trick.arXiv preprint arXiv:2307.02419,

    arXiv

  5. [19]

    Gradientcoin: A peer-to-peer decentralized large language models

    [GSY23a] Yeqi Gao, Zhao Song, and Junze Yin. Gradientcoin: A peer-to-peer decentralized large language models. arXiv preprint arXiv:2308.10502 ,

    arXiv

  6. [20]

    An iterative algorithm for rescaled hyperbolic functions regression

    [GSY23b] Yeqi Gao, Zhao Song, and Junze Yin. An iterative algorithm for rescaled hyperbolic functions regression. arXiv preprint arXiv:2305.00660 ,

    arXiv

  7. [21]

    Com- putational limits of low-rank adaptation (lora) for transformer-based models

    [HSK+24] Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu. Com- putational limits of low-rank adaptation (lora) for transformer-based models. arXiv preprint arXiv:2406.03136,

    arXiv

  8. [22]

    Instahide’s sample complexity when mixing two private images.arXiv preprint arXiv:2011.11877,

    [HST+20] Baihe Huang, Zhao Song, Runzhou Tao, Junze Yin, Ruizhe Zhang, and Danyang Zhuo. Instahide’s sample complexity when mixing two private images.arXiv preprint arXiv:2011.11877,

    2011 arXiv

  9. [24]

    A dynamic fast gaussian transform

    [HSW+22] Baihe Huang, Zhao Song, Omri Weinstein, Junze Yin, Hengjie Zhang, and Ruizhe Zhang. A dynamic fast gaussian transform. arXiv preprint arXiv:2202.12329 ,

    arXiv

  10. [25]

    Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency

    [HWG+24] Jerry Yao-Chieh Hu, Wei-Po Wang, Ammar Gilani, Chenyang Li, Zhao Song, and Han Liu. Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency. arXiv preprint arXiv:2411.16525 ,

    arXiv

  11. [26]

    On statistical rates of conditional diffusion transformers: Approximation, estimation and minimax optimality

    [HWL+24] Jerry Yao-Chieh Hu, Weimin Wu, Yi-Chen Lee, Yu-Chao Huang, Minshuo Chen, and Han Liu. On statistical rates of conditional diffusion transformers: Approximation, estimation and minimax optimality. arXiv preprint arXiv:2411.17522 ,

    arXiv

  12. [27]

    On statistical rates and provably efficient criteria of latent diffusion transformers (dits)

    [HWSL24] Jerry Yao-Chieh Hu, Weimin Wu, Zhao Song, and Han Liu. On statistical rates and provably efficient criteria of latent diffusion transformers (dits). arXiv preprint arXiv:2407.01079,

    arXiv

  13. [28]

    Approximation theory of transformer networks for sequence modeling

    [JL23] Haotian Jiang and Qianxiao Li. Approximation theory of transformer networks for sequence modeling. arXiv preprint arXiv:2305.18475 ,

    arXiv

  14. [29]

    On computational limits and provably efficient criteria of visual autoregressive models: A fine grained complexity analysis

    [KLL+25a] Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. On computational limits and provably efficient criteria of visual autoregressive models: A fine grained complexity analysis. arXiv preprint arXiv:2501.04377 ,

    arXiv

  15. [30]

    Circuit complexity bounds for visual autoregressive model

    [KLL+25b] Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhenmei Shi, and Zhao Song. Circuit complexity bounds for visual autoregressive model. arXiv preprint arXiv:2501.04299 ,

    arXiv

  16. [31]

    Faster sampling algorithms for polytopes with small treewidth

    27 [KLSZ24] Yekun Ke, Xiaoyu Li, Zhao Song, and Tianyi Zhou. Faster sampling algorithms for polytopes with small treewidth. In 2024 IEEE International Conference on Big Data (BigData), pages 44–53. IEEE,

    2024

  17. [32]

    Neural algorithmic reasoning for hypergraphs with looped transformers

    [LLL+25] Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, and Zhen Zhuang. Neural algorithmic reasoning for hypergraphs with looped transformers. arXiv preprint arXiv:2501.10688 ,

  18. [33]

    Theoreti- cal constraints on the expressive power of rope-based tensor attention transformers

    [LLS+24a] Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, and Mingda Wan. Theoreti- cal constraints on the expressive power of rope-based tensor attention transformers. arXiv preprint arXiv:2412.18040 ,

    arXiv

  19. [34]

    Conv-basis: A new paradigm for efficient attention inference and gradient computation in trans- formers

    [LLS+24b] Yingyu Liang, Heshan Liu, Zhenmei Shi, Zhao Song, and Junze Yin. Conv-basis: A new paradigm for efficient attention inference and gradient computation in trans- formers. arXiv preprint arXiv:2405.05219 ,

    arXiv

  20. [35]

    Beyond linear approximations: A novel pruning approach for attention matrix.arXiv preprint arXiv:2410.11261,

    [LLS+24c] Yingyu Liang, Jiangxuan Long, Zhenmei Shi, Zhao Song, and Yufa Zhou. Beyond linear approximations: A novel pruning approach for attention matrix.arXiv preprint arXiv:2410.11261,

    arXiv

  21. [36]

    On the computational capability of graph neural networks: A circuit complexity bound perspective

    [LLS+25b] Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song, Wei Wang, and Jiahao Zhang. On the computational capability of graph neural networks: A circuit complexity bound perspective. arXiv preprint arXiv:2501.06444 ,

    arXiv

  22. [37]

    A tighter complexity analysis of sparsegpt

    [LLSS24] Xiaoyu Li, Yingyu Liang, Zhenmei Shi, and Zhao Song. A tighter complexity analysis of sparsegpt. arXiv preprint arXiv:2408.12151 ,

    arXiv

  23. [38]

    Fast second-order method for neural networks under small treewidth setting

    [LLSZ24] Xiaoyu Li, Jiangxuan Long, Zhao Song, and Tianyi Zhou. Fast second-order method for neural networks under small treewidth setting. In 2024 IEEE International Con- ference on Big Data (BigData) , pages 1029–1038. IEEE,

    2024

  24. [39]

    Achieving near-optimal regret for bandit algorithms with uniform last-iterate guarantee

    [LLY24] Junyan Liu, Yunfan Li, and Lin Yang. Achieving near-optimal regret for bandit algorithms with uniform last-iterate guarantee. arXiv preprint arXiv:2402.12711 ,

    arXiv

  25. [40]

    A faster k-means++ algorithm

    28 [LSS+22] Jiehao Liang, Somdeb Sarkhel, Zhao Song, Chenbo Yin, Junze Yin, and Danyang Zhuo. A faster k-means++ algorithm. arXiv preprint arXiv:2211.15118 ,

    arXiv

  26. [41]

    Looped relu mlps may be all you need as practical programmable computers

    [LSS+24a] Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, and Yufa Zhou. Looped relu mlps may be all you need as practical programmable computers. arXiv preprint arXiv:2410.09375,

    arXiv

  27. [42]

    Multi-layer transformers gradient can be approximated in almost linear time

    [LSS+24b] Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, and Yufa Zhou. Multi-layer transformers gradient can be approximated in almost linear time. arXiv preprint arXiv:2408.13233,

    arXiv

  28. [43]

    Differential privacy mech- anisms in neural tangent kernel regression

    [LSSS24] Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. Differential privacy mech- anisms in neural tangent kernel regression. arXiv preprint arXiv:2407.13621 ,

    arXiv

  29. [44]

    Differential privacy of cross-attention with provable guarantee

    [LSSZ24a] Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Differential privacy of cross-attention with provable guarantee. arXiv preprint arXiv:2407.14717 ,

  30. [45]

    Tensor attention train- ing: Provably efficient learning of higher-order transformers

    [LSSZ24b] Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Tensor attention train- ing: Provably efficient learning of higher-order transformers. arXiv preprint arXiv:2405.16411,

  31. [46]

    How to inverting the leverage score distribution? arXiv preprint arXiv:2404.13785 ,

    [LSW+24] Zhihang Li, Zhao Song, Weixin Wang, Junze Yin, and Zheng Yu. How to inverting the leverage score distribution? arXiv preprint arXiv:2404.13785 ,

    arXiv

  32. [47]

    Local convergence of ap- proximate newton method for two layer nonlinear regression

    [LSWY23] Zhihang Li, Zhao Song, Zifan Wang, and Junze Yin. Local convergence of ap- proximate newton method for two layer nonlinear regression. arXiv preprint arXiv:2311.15390,

    arXiv

  33. [48]

    Dynamic maintenance of kernel density estimation data structure: From practice to theory

    [LSX+22] Jiehao Liang, Zhao Song, Zhaozhuo Xu, Junze Yin, and Danyang Zhuo. Dynamic maintenance of kernel density estimation data structure: From practice to theory. arXiv preprint arXiv:2208.03915 ,

    arXiv

  34. [49]

    Inverting the leverage score gradient: An efficient approximate newton method

    [LSXY24] Chenyang Li, Zhao Song, Zhaoxing Xu, and Junze Yin. Inverting the leverage score gradient: An efficient approximate newton method. arXiv preprint arXiv:2408.11267,

    arXiv

  35. [50]

    Solving regularized exp, cosh and sinh regression problems

    [LSZ23] Zhihang Li, Zhao Song, and Tianyi Zhou. Solving regularized exp, cosh and sinh regression problems. arXiv preprint arXiv:2303.15725 ,

    arXiv

  36. [51]

    The llama 3 herd of models

    [LT24] AI @ Meta Llama Team. The llama 3 herd of models. arXiv preprint arXiv:2407.21783,

    arXiv

  37. [52]

    Score-based gener- ative diffusion models for social recommendations

    29 [LZW+24] Chengyi Liu, Jiahao Zhang, Shijie Wang, Wenqi Fan, and Qing Li. Score-based gener- ative diffusion models for social recommendations. arXiv preprint arXiv:2412.15579,

    arXiv

  38. [53]

    Dreamfusion: Text- to-3d using 2d diffusion

    [PJBM22] Ben Poole, Ajay Jain, Jonathan T Barron, and Ben Mildenhall. Dreamfusion: Text- to-3d using 2d diffusion. arXiv preprint arXiv:2209.14988 ,

    arXiv

  39. [55]

    Denoising diffusion implicit mod- els

    [SME20] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit mod- els. arXiv preprint arXiv:2010.02502 ,

    2010 arXiv

  40. [56]

    A mathematical abstraction for balancing the trade-off between creativity and reality in large language models

    [SSZ23] Ritwik Sinha, Zhao Song, and Tianyi Zhou. A mathematical abstraction for balancing the trade-off between creativity and reality in large language models. arXiv preprint arXiv:2306.02295,

    arXiv

  41. [57]

    A unified scheme of resnet and softmax

    [SWY23] Zhao Song, Weixin Wang, and Junze Yin. A unified scheme of resnet and softmax. arXiv preprint arXiv:2309.13482 ,

    arXiv

  42. [58]

    Fast and efficient matching algorithm with deadline instances

    [SWYY23] Zhao Song, Weixin Wang, Chenbo Yin, and Junze Yin. Fast and efficient matching algorithm with deadline instances. arXiv preprint arXiv:2305.08353 ,

    arXiv

  43. [59]

    The expressibility of polynomial based attention scheme

    30 [SXY23] Zhao Song, Guangyi Xu, and Junze Yin. The expressibility of polynomial based attention scheme. arXiv preprint arXiv:2310.20051 ,

    arXiv

  44. [60]

    An automatic learning rate schedule algorithm for achieving faster convergence and steeper descent

    [SY23] Zhao Song and Chiwun Yang. An automatic learning rate schedule algorithm for achieving faster convergence and steeper descent. arXiv preprint arXiv:2310.11291 ,

    arXiv

  45. [61]

    Revisiting quantum algorithms for linear regressions: Quadratic speedups without data-dependent parameters

    [SYZ23] Zhao Song, Junze Yin, and Ruizhe Zhang. Revisiting quantum algorithms for linear regressions: Quadratic speedups without data-dependent parameters. arXiv preprint arXiv:2311.14823,

    arXiv

  46. [63]

    Adaptive liquidity provision in uniswap v3 with deep reinforcement learning

    [ZCY23] Haochen Zhang, Xi Chen, and Lin F Yang. Adaptive liquidity provision in uniswap v3 with deep reinforcement learning. arXiv preprint arXiv:2309.10129 ,

    arXiv

  47. [2017]

    Dolfin: Diffusion layout transformers without autoencoder

    [WCZ+23] Yilin Wang, Zeyuan Chen, Liangjun Zhong, Zheng Ding, Zhizhou Sha, and Zhuowen Tu. Dolfin: Diffusion layout transformers without autoencoder. arXiv preprint arXiv:2310.16305,

    arXiv

  48. [2018]

    Query complexity of active learning for function family with nearly orthogonal basis

    [CSS+23] Xiang Chen, Zhao Song, Baocheng Sun, Junze Yin, and Danyang Zhuo. Query complexity of active learning for function family with nearly orthogonal basis. arXiv preprint arXiv:2306.03356,

    arXiv

  49. [2019]

    Flowar: Scale-wise autoregressive image generation meets flow matching

    [RYH+24] Sucheng Ren, Qihang Yu, Ju He, Xiaohui Shen, Alan Yuille, and Liang-Chieh Chen. Flowar: Scale-wise autoregressive image generation meets flow matching. arXiv preprint arXiv:2412.15205,

    arXiv

  50. [2020]

    Sublinear time algorithm for online weighted bipartite matching

    [HST+22] Hang Hu, Zhao Song, Runzhou Tao, Zhaozhuo Xu, Junze Yin, and Danyang Zhuo. Sublinear time algorithm for online weighted bipartite matching. arXiv preprint arXiv:2208.03367,

    arXiv

  51. [2021]

    An over-parameterized exponential regression

    [GMS23] Yeqi Gao, Sridhar Mahadevan, and Zhao Song. An over-parameterized exponential regression. arXiv preprint arXiv:2303.16504 ,

    arXiv

  52. [2022]

    Sumformer: Univer- sal approximation for efficient transformers

    [ADTK23] Silas Alberti, Niclas Dern, Laura Thesing, and Gitta Kutyniok. Sumformer: Univer- sal approximation for efficient transformers. In Topological, Algebraic and Geometric Learning Workshops 2023 , pages 72–86. PMLR,

    2023

  53. [2023]

    Federated empirical risk minimization via second-order method

    [BSY23] Song Bian, Zhao Song, and Junze Yin. Federated empirical risk minimization via second-order method. arXiv preprint arXiv:2305.17482 ,

    arXiv

  54. [2024]

    Circuit complexity bounds for rope-based transformer architecture

    [CLL+24a] Bo Chen, Xiaoyu Li, Yingyu Liang, Jiangxuan Long, Zhenmei Shi, and Zhao Song. Circuit complexity bounds for rope-based transformer architecture. arXiv preprint arXiv:2411.07602,

    arXiv

  55. [2025]

    High-order matching for one-step shortcut diffusion models

    [CGL+25b] Bo Chen, Chengyue Gong, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song, and Mingda Wan. High-order matching for one-step shortcut diffusion models. arXiv preprint arXiv:2502.00688 ,

    arXiv

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.