On Computational Limits and Provably Efficient Criteria of Visual
  Autoregressive Models: A Fine-Grained Complexity Analysis
Authors: name: Yekun Ke, name: Xiaoyu Li, name: Yingyu Liang, name: Zhizhou Sha, name: Zhenmei Shi, name: Zhao Song

Recently, Visual Autoregressive (VAR) Models introduced a
groundbreaking advancement in the field of image generation, offering a
scalable approach through a coarse-to-fine "next-scale prediction" paradigm.
However, the state-of-the-art algorithm of VAR models in [Tian,
Jiang, Yuan, Peng and Wang, NeurIPS 2024] takes O(n^4) time, which is
computationally inefficient. In this work, we analyze the computational limits
and efficiency criteria of VAR Models through a fine-grained
complexity lens. Our key contribution is identifying the conditions under which
VAR computations can achieve sub-quadratic time complexity.
Specifically, we establish a critical threshold for the norm of input matrices
used in VAR attention mechanisms. Above this threshold, assuming the
Strong Exponential Time Hypothesis (SETH) from fine-grained
complexity theory, a sub-quartic time algorithm for VAR models is
impossible. To substantiate our theoretical findings, we present efficient
constructions leveraging low-rank approximations that align with the derived
criteria. This work initiates the study of the computational efficiency of the
VAR model from a theoretical perspective. Our technique will shed
light on advancing scalable and efficient image generation in VAR
frameworks.