Transformers are inherently succinct • Hacker News Board

layer8 wrote: post #44

spacebacon wrote: post #43

Earlier quoted context omitted.

For the downvote. Computational semiotics is empirically proven. Read more.

Your comments are too succinct. Write more.

You clearly have not read all of my words. Read more.

Re: Transformers are inherently succinct

#46

Post by ebiederm » Sat, Jun 06, 2026, 10:06 PM UTC

dfabulich wrote: post #9

The last line of the abstract has the most important takeaway. > 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 y…

How does it follow that there is no point in trying for formal correctness? In many problems there is an interesting subset that is quickly solvable even when the general case is not.

SAT solvers in practice are quick on just about everything.

SAT solvers being programs that solve the original NP-compete problem.