mlsanityData to 7 Oct 2026

Circuit Complexity Bounds for Visual Autoregressive Model

arXiv 2501.04299 ↗First posted 8 Jan 2025stat.ML cs.AI cs.CCcited by 10

Not on the map. Why?

Abstract (arXiv)

Understanding the expressive ability of a specific model is essential for grasping its capacity limitations. Recently, several studies have established circuit complexity bounds for Transformer architecture. Besides, the Visual AutoRegressive (VAR) model has risen to be a prominent method in the field of image generation, outperforming previous techniques, such as Diffusion Transformers, in generating high-quality images. We investigate the circuit complexity of the VAR model and establish a bound in this study. Our primary result demonstrates that the VAR model is equivalent to a simulation by a uniform mathsfTC0 threshold circuit with hidden dimension d ≤ O(n) and poly(n) precision. This is the first study to rigorously highlight the limitations in the expressive power of VAR models despite their impressive performance. We believe our findings will offer valuable insights into the inherent constraints of these models and guide the development of more efficient and expressive architectures in the future.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 45 of its 60 references that are in the map. First posted on arXiv 8 Jan 2025.

Builds on

45 of 60 references.

References · 45

  1. 2015Deep Unsupervised Learning using Nonequilibrium Thermodynamicscited by 7,005
  2. 2022Generative Adversarial Networkscited by 5,603
  3. 2019Generative Modeling by Estimating Gradients of the Data Distributioncited by 4,067
  4. 2020Taming Transformers for High-Resolution Image Synthesiscited by 3,229
  5. 2018Glow: Generative Flow with Invertible 1x1 Convolutionscited by 1,539
  6. 2019Generating Diverse High-Fidelity Images with VQ-VAE-2cited by 1,376
  7. 2024Visual Autoregressive Modeling: Scalable Image Generation via Next-Scale Predictioncited by 1,005
  8. 2016Conditional Image Generation with PixelCNN Decoderscited by 859
  9. 2018Image Transformercited by 770
  10. 2022Autoregressive Image Generation using Residual Quantizationcited by 706
  11. 2021CogView: Mastering Text-to-Image Generation via Transformerscited by 691
  12. 2022All are Worth Words: A ViT Backbone for Diffusion Modelscited by 498
33 more
  1. 2016Tutorial on Variational Autoencoderscited by 404
  2. 2024MambaIR: A Simple Baseline for Image Restoration with State-Space Modelcited by 349
  3. 2019Learning Deep Transformer Models for Machine Translationcited by 309
  4. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  5. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  6. 2022Transformers Learn Shortcuts to Automatacited by 260
  7. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  8. 2024U-KAN Makes Strong Backbone for Medical Image Segmentation and Generationcited by 176
  9. 2017PixelSNAIL: An Improved Autoregressive Generative Modelcited by 137
  10. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  11. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  12. 2024Is A Picture Worth A Thousand Words? Delving Into Spatial Reasoning for Vision Language Modelscited by 111
  13. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 92
  14. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  15. 2023Advances in Medical Image Analysis with Vision Transformers: A Comprehensive Reviewcited by 62
  16. 2024On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysiscited by 41
  17. 2023TokenCompose: Text-to-Image Diffusion with Token-level Supervisioncited by 40
  18. 2024On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)cited by 39
  19. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 35
  20. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  21. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  22. 2024OmniControlNet: Dual-stage Integration for Conditional Image Generationcited by 24
  23. 2023Dolfin: Diffusion Layout Transformers without Autoencodercited by 23
  24. 2024Score-based Generative Diffusion Models for Social Recommendationscited by 23
  25. 2024Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiencycited by 21
  26. 2024On Statistical Rates of Conditional Diffusion Transformers: Approximation, Estimation and Minimax Optimalitycited by 21
  27. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  28. 2024Looped ReLU MLPs May Be All You Need as Practical Programmable Computerscited by 19
  29. 2024Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codescited by 19
  30. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  31. 2024Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problemscited by 9
  32. 2024Curse of Attention: A Kernel-Based Perspective for Why Transformers Fail to Generalize on Time Series Forecasting and Beyondcited by 8
  33. 2020crea.blender: A Neural Network-Based Image Generation Game to Assess Creativitycited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 9; 2026: 1.

10 papers.

  1. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 17
  2. 2025High-Order Matching for One-Step Shortcut Diffusion Modelscited by 15
  3. 2025Force Matching with Relativistic Constraints: A Physics-Inspired Approach to Stable and Efficient Generative Modelingcited by 12
  4. 2025On Computational Limits of FlowAR Models: Expressivity and Efficiencycited by 10
  5. 2025Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteriacited by 5
  6. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  7. 2025Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questionscited by 4
  8. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  9. 2026Can Video World Models Track Unobserved World States?cited by 1
  10. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Universal Approximation of Visual Autoregressive Transformers
  2. 2025Scale-Wise VAR is Secretly Discrete Diffusion
  3. 2024Revisiting Non-Autoregressive Transformers for Efficient Image Synthesis
  4. 2025FREE: Uncertainty-Aware Autoregression for Parallel Diffusion Transformers
  5. 2024A Spark of Vision-Language Intelligence: 2-Dimensional Autoregressive Transformer for Efficient Finegrained Image Generation
  6. 2025HOFAR: High-Order Augmentation of Flow Autoregressive Transformers
  7. 2022Scalable Diffusion Models with Transformers
  8. 2026Circuit Fine-Tuning for Compute-Efficient Transformer Adaptation