title: On Computational Limits and Provably Efficient Criteria of Visual
    Autoregressive Models: A Fine-Grained Complexity Analysis
summary: Recently, Visual Autoregressive (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.
  However, the state-of-the-art algorithm of VAR models in [Tian,
  Jiang, Yuan, Peng and Wang, NeurIPS 2024] takes O(n^4) time, which is
  computationally inefficient. In this work, we analyze the computational limits
  and efficiency criteria of VAR Models through a fine-grained
  complexity lens. Our key contribution is identifying the conditions under which
  VAR computations can achieve sub-quadratic time complexity.
  Specifically, we establish a critical threshold for the norm of input matrices
  used in VAR attention mechanisms. Above this threshold, assuming the
  Strong Exponential Time Hypothesis (SETH) from fine-grained
  complexity theory, a sub-quartic time algorithm for 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
  VAR model from a theoretical perspective. Our technique will shed
  light on advancing scalable and efficient image generation in VAR
  frameworks.
paper_authors._id: 6780a7fdaf887f31d643cb55
paper_authors.name: Yekun Ke
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-01-10T08:26:56.992Z
paper_authors._id: 6600cb94e95908a2a60f3abd
paper_authors.avatarUrl: /avatars/82cdb1ef4ab4caacfa8d9f4c4f538222.svg
paper_authors.fullname: keyekun
paper_authors.type: user
paper_authors.user: keyekun
paper_authors._id: 6780a7fdaf887f31d643cb56
paper_authors.name: Xiaoyu Li
paper_authors._id: 6780a7fdaf887f31d643cb57
paper_authors.name: Yingyu Liang
paper_authors._id: 6780a7fdaf887f31d643cb58
paper_authors.name: Zhizhou Sha
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-01-10T08:26:20.704Z
paper_authors._id: 6335604ea01bd734f72316b0
paper_authors.avatarUrl: /avatars/4c6611dabd492106ffb2e82fd680d983.svg
paper_authors.fullname: Zhizhou Sha
paper_authors.type: user
paper_authors.user: JamesSand
paper_authors._id: 6780a7fdaf887f31d643cb59
paper_authors.name: Zhenmei Shi
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2025-01-10T08:26:12.739Z
paper_authors._id: 64b769d7fa7eabaae5fb7f2f
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/64b769d7fa7eabaae5fb7f2f/AbxVphanApZDfj3cOI1tb.jpeg
paper_authors.fullname: Zhenmei Shi
paper_authors.type: user
paper_authors.user: Zhenmei
paper_authors._id: 6780a7fdaf887f31d643cb5a
paper_authors.name: Zhao Song
paper_title: On Computational Limits and Provably Efficient Criteria of Visual
    Autoregressive Models: A Fine-Grained Complexity Analysis
paper_summary: Recently, Visual Autoregressive (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.
  However, the state-of-the-art algorithm of VAR models in [Tian,
  Jiang, Yuan, Peng and Wang, NeurIPS 2024] takes O(n^4) time, which is
  computationally inefficient. In this work, we analyze the computational limits
  and efficiency criteria of VAR Models through a fine-grained
  complexity lens. Our key contribution is identifying the conditions under which
  VAR computations can achieve sub-quadratic time complexity.
  Specifically, we establish a critical threshold for the norm of input matrices
  used in VAR attention mechanisms. Above this threshold, assuming the
  Strong Exponential Time Hypothesis (SETH) from fine-grained
  complexity theory, a sub-quartic time algorithm for 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
  VAR model from a theoretical perspective. Our technique will shed
  light on advancing scalable and efficient image generation in VAR
  frameworks.
paper_ai_summary: Analysis of Visual Autoregressive (VAR) models identifies conditions for sub-quadratic time complexity and presents efficient constructions using low-rank approximations, advancing scalable image generation.
paper_ai_keywords: Visual Autoregressive VAR next-scale prediction quadratic time Strong Exponential Time Hypothesis SETH fine-grained complexity low-rank approximations