揭示视觉自回归模型的计算极限，提出高效生成的理论条件。
On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis
- 从细粒度复杂度分析出发，揭示模型计算瓶颈
- 证明在SETH假设下无法实现亚四次方时间算法
- 基于低秩近似提出可满足条件的高效构造
最近，视觉自回归（VAR）模型通过粗到精的‘下一尺度预测’范式，在图像生成领域实现了突破性进展，具备可扩展性。假设由VAR模型生成的最后一个VQ码图尺寸为n×n，当前最优算法耗时O(n^{4+o(1)})，计算效率低下。本文从细粒度复杂度视角分析VAR模型的计算极限与效率准则。关键贡献是识别出使VAR计算达到亚二次时间复杂度的条件。我们证明：在强指数时间假设（SETH）下，VAR模型的亚四次方时间算法不可能存在。为验证理论结论，我们提出了符合推导条件的高效构造方法，利用低秩近似实现加速。本工作首次从理论角度系统研究了VAR模型的计算效率问题，其技术路径将推动可扩展、高效的图像生成发展。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。