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

arXiv: https://arxiv.org/abs/2501.04377 · HTML: https://mlsanity.com/paper/2501.04377/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2025.

## Built on by (most cited first, 14 of 14)

- [T2VWorldBench: A Benchmark for Evaluating World Knowledge in Text-to-Video Generation](https://mlsanity.com/paper/2507.18107/) (2025)
- [Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting](https://mlsanity.com/paper/2510.04401/) (2025)
- [High-Order Matching for One-Step Shortcut Diffusion Models](https://mlsanity.com/paper/2502.00688/) (2025)
- [Force Matching with Relativistic Constraints: A Physics-Inspired Approach to Stable and Efficient Generative Modeling](https://mlsanity.com/paper/2502.08150/) (2025)
- [On Computational Limits of FlowAR Models: Expressivity and Efficiency](https://mlsanity.com/paper/2502.16490/) (2025)
- [Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers](https://mlsanity.com/paper/2501.10688/) (2025)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [HOFAR: High-Order Augmentation of Flow Autoregressive Transformers](https://mlsanity.com/paper/2503.08032/) (2025)
- [Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questions](https://mlsanity.com/paper/2508.13214/) (2025)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)
- [Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective](https://mlsanity.com/paper/2510.05494/) (2025)
- [Depth Adaptive Efficient Visual Autoregressive Modeling](https://mlsanity.com/paper/2604.17286/) (2026)

## Abstract (arXiv)

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.