Transformers Are Inherently Succinct(openreview.net) This paper is being published at ICLR 2026 (top AI conference), and was selected as one of three outstanding papers. |
Transformers Are Inherently Succinct(openreview.net) This paper is being published at ICLR 2026 (top AI conference), and was selected as one of three outstanding papers. |
> As a consequence of this succinctness, we show that basic verification problems for transformers, such as emptiness and equivalence, are provably intractable: specifically, EXPSPACE-complete.
If you were hoping to formally prove the correctness of a large transformer, it turns out that you're going to need an exponentially larger amount of space to do your verification, more than you could possibly afford.
It's exactly as related to real models as computer science is to real computers.
Transformers Are Inherently Succinct (2025) - https://news.ycombinator.com/item?id=48014197 - May 2026 (9 comments)