On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis

Recently, Visual Autoregressive (mathsfVAR) 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 mathsfVAR models, the state-of-the-art algorithm in [Tian, Jiang, Yuan, Peng and Wang, NeurIPS 2024] takes O(n4+o(1)) time, which is computationally inefficient. In this work, we analyze the computational limits and efficiency criteria of mathsfVAR Models through a fine-grained complexity lens. Our key contribution is identifying the conditions under which mathsfVAR computations can achieve sub-quadratic time complexity. We have proved that assuming the Strong Exponential Time Hypothesis (mathsfSETH) from fine-grained complexity theory, a sub-quartic time algorithm for mathsfVAR 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 mathsfVAR model from a theoretical perspective. Our technique will shed light on advancing scalable and efficient image generation in mathsfVAR frameworks.