On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis
Journal:
arXiv
Published Date:
Jan 8, 2025
Abstract
Recently, Visual Autoregressive ($\mathsf{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.
Suppose that $n$ represents the height and width of the last VQ code map
generated by $\mathsf{VAR}$ models, the state-of-the-art algorithm in [Tian,
Jiang, Yuan, Peng and Wang, NeurIPS 2024] takes $O(n^{4+o(1)})$ time, which is
computationally inefficient. In this work, we analyze the computational limits
and efficiency criteria of $\mathsf{VAR}$ Models through a fine-grained
complexity lens. Our key contribution is identifying the conditions under which
$\mathsf{VAR}$ computations can achieve sub-quadratic time complexity. We have
proved that assuming the Strong Exponential Time Hypothesis ($\mathsf{SETH}$)
from fine-grained complexity theory, a sub-quartic time algorithm for
$\mathsf{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 $\mathsf{VAR}$ model from a theoretical
perspective. Our technique will shed light on advancing scalable and efficient
image generation in $\mathsf{VAR}$ frameworks.
