The last line of the abstract has the most important takeaway.<p>> 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.<p>If you were hoping to formally prove the correctness of a large transformer, it turns out that you're going to need an exponentially <i>larger</i> amount of space to do your verification, more than you could possibly afford.
Paper went over my head but is this in any way related to my experience of Claude Opus 4.8 using increasingly terse language with very short, overloaded words? Lately I've been having trouble parsing the things it writes about my own code, it's using the kind of compressed language that you see typically in git commit message subject lines but relentless, always on.
Not just me then.
No, this is in the same ballpark as ideas like big-O notation. The paper is saying that transformers can recognize a language with exponentially fewer symbols than other kinds of systems, i.e. they're more <i>succinct</i>.<p>It's exactly as related to real models as computer science is to real computers.
Discussed (a bit) here:<p><i>Transformers Are Inherently Succinct (2025)</i> - <a href="https://news.ycombinator.com/item?id=48014197">https://news.ycombinator.com/item?id=48014197</a> - May 2026 (9 comments)
I had no idea that LLMs (or the transformer architecture) were within reach of complexity theory. But if transformers "can be" exponentially more succinct than RNNs, doesn't that mean we're approaching optimality?
What about the other direction? What languages are expressible w/ RNNs & LTLs that require exponential blowup for transformers?
This paper is being published at ICLR 2026 (top AI conference), and was selected as one of three outstanding papers.