# Circuit Complexity Bounds for Visual Autoregressive Model

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

## Key facts

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

## Builds on (most cited first, 30 of 45)

- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Generative Modeling by Estimating Gradients of the Data Distribution](https://mlsanity.com/paper/1907.05600/) (2019)
- [Taming Transformers for High-Resolution Image Synthesis](https://mlsanity.com/paper/2012.09841/) (2020)
- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [Generating Diverse High-Fidelity Images with VQ-VAE-2](https://mlsanity.com/paper/1906.00446/) (2019)
- [Visual Autoregressive Modeling: Scalable Image Generation via Next-Scale Prediction](https://mlsanity.com/paper/2404.02905/) (2024)
- [Conditional Image Generation with PixelCNN Decoders](https://mlsanity.com/paper/1606.05328/) (2016)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [Autoregressive Image Generation using Residual Quantization](https://mlsanity.com/paper/2203.01941/) (2022)
- [CogView: Mastering Text-to-Image Generation via Transformers](https://mlsanity.com/paper/2105.13290/) (2021)
- [All are Worth Words: A ViT Backbone for Diffusion Models](https://mlsanity.com/paper/2209.12152/) (2022)
- [Tutorial on Variational Autoencoders](https://mlsanity.com/paper/1606.05908/) (2016)
- [MambaIR: A Simple Baseline for Image Restoration with State-Space Model](https://mlsanity.com/paper/2402.15648/) (2024)
- [Learning Deep Transformer Models for Machine Translation](https://mlsanity.com/paper/1906.01787/) (2019)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [U-KAN Makes Strong Backbone for Medical Image Segmentation and Generation](https://mlsanity.com/paper/2406.02918/) (2024)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [PixelSNAIL: An Improved Autoregressive Generative Model](https://mlsanity.com/paper/1712.09763/) (2017)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [Is A Picture Worth A Thousand Words? Delving Into Spatial Reasoning for Vision Language Models](https://mlsanity.com/paper/2406.14852/) (2024)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Advances in Medical Image Analysis with Vision Transformers: A Comprehensive Review](https://mlsanity.com/paper/2301.03505/) (2023)
- [On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysis](https://mlsanity.com/paper/2402.04520/) (2024)
- [TokenCompose: Text-to-Image Diffusion with Token-level Supervision](https://mlsanity.com/paper/2312.03626/) (2023)
- [On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)](https://mlsanity.com/paper/2407.01079/) (2024)

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

- [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)
- [Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria](https://mlsanity.com/paper/2508.07102/) (2025)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questions](https://mlsanity.com/paper/2508.13214/) (2025)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Can Video World Models Track Unobserved World States?](https://mlsanity.com/paper/2608.30692/) (2026)
- [Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective](https://mlsanity.com/paper/2510.05494/) (2025)

## 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.