On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis
Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song · 2025
Read On Computational Limits and Provably Efficient Criteria of Visual Autoregressive Models: A Fine-Grained Complexity Analysis by Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-04377.txt.
Description
Yekun Ke and five co-authors study the hard limits on speeding up visual autoregressive models, a new family of image generators. Their work appeared in twenty twenty-five. These models build images scale by scale, from coarse to fine, but the best known method runs slowly.
The authors ask when the core computation could run in well under the usual time. They prove that, under a standard hardness assumption in complexity theory, no method can break a certain time barrier. They also give conditions under which much faster running is possible. Low-rank shortcuts supply matching fast constructions. The work starts a theory of efficiency for these models, aimed at making large image generation practical.
Catalog record
| CREATOR | Yekun Ke, Xiaoyu Li, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-04377