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

Visual Autoregressive (VAR) models have emerged as a powerful tool for image generation, but their high computational complexity (O(n^4)) limits their scalability. This paper delves into the computational limits and efficiency criteria of VAR models by performing a fine-grained complexity analysis. The analysis reveals a critical relationship between the computational complexity of VAR models and the norm (magnitude) of the input matrices used in their attention mechanisms.

The study establishes both positive and negative results. On the positive side, it identifies conditions under which efficient algorithms that approximate VAR model outputs in almost quadratic time are possible. On the negative side, it rigorously shows that under the Strong Exponential Time Hypothesis (SETH), truly sub-quartic time algorithms are impossible if the input matrix norm exceeds a critical threshold. The findings highlight the importance of controlling input matrix norm for efficient VAR model computation and could influence the design of future, more efficient models for image generation and other applications.