arXiv:2501.04377v2 通告类型: replace-cross 摘要: 最近，视觉自回归（$\mathsf{VAR}$）模型在图像生成领域引入了一项革命性的进展，通过像素从粗到细的“下一尺度预测”范式提供了一种可扩展的方法。假设$n$表示$\mathsf{VAR}$模型生成的最后一个VQ码图的高度和宽度，目前最先进的算法在[NeurIPS 2024的Tian, Jiang, Yuan, Peng和Wang的研究]中需要$O(n^{4+o(1)})$的时间，这在计算上是低效的。在这项工作中，我们通过精细复杂度视角分析了$\mathsf{VAR}$模型的计算限制和效率标准。我们的主要贡献是确定了$\mathsf{VAR}$计算可以实现亚二次时间复杂度的条件。我们证明，在精细复杂度理论假设强指数时间假设（$\mathsf{SETH}$）的前提下，$\mathsf{VAR}$模型的亚四次时间算法是不可能的。为了证实我们的理论发现，我们提出了符合所推导标准的有效构造方法，利用低秩近似方法。这项工作从理论角度开始了对$\mathsf{VAR}$模型计算效率的研究。我们的技术将有助于推进$\mathsf{VAR}$框架中可扩展和高效的图像生成。