Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Transformers are inherently succinct

openreview.net

Post reply on HN
Print view View original

11–20 of 46 posts

Re: Transformers are inherently succinct

#11

Post by thesz »

My comment in the previous discussion of that paper: https://news.ycombinator.com/item?id=48014197

Authors used LTL (linear temporal logic) to express, basically, non-reduced non-ordered binary decision diagrams. Or just binary decision diagrams, BDDs.

BDDs are almost guaranteed to have exponential size because they do not employ reduction (sharing of common expressions). Reduced BDDs are more succinct and reduced ordered BDDs are even more succinct.

Also, transformers in the paper are constructed, not trained. Training any model to express some truth table is very hard. They also did not perform comparison with, say, Kolmogorov-Arnold representation, which is also universal approximator.

So this paper is not as deep as one may think it is.

Re: Transformers are inherently succinct

#12

Post by yorwba »

measurablefunc wrote: post #6

What about the other direction? What languages are expressible w/ RNNs & LTLs that require exponential blowup for transformers?

Proposition 16. UHATs have polynomially bounded expansion over LTL. In particular, given an LTL formula φ, one can construct in polynomial time a UHAT T such that L(T) = L(φ).

i.e. the blowup is only exponential in one direction.

Re: Transformers are inherently succinct

#14

Post by thesz »

lkm0 wrote: post #5

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?

  > doesn't that mean we're approaching optimality?
No.

Transformers are Markov chains [1]. Somewhere around this fascinating site [2] I read that stateful models have an advantage. Author provided an example, a state machine with two states A and B, where at state A transitions are to state A (output 0) and to state B (output 1) with equal probability and at state B the transition is always to state A and output is always 1.

For this state machine just one bit of memory can make an optimal prediction that ones always go in pairs, whereas Markov chain will approximate this prediction and never reach optimality.

  [1] https://arxiv.org/abs/2410.02724
  [2] https://bactra.org/

Re: Transformers are inherently succinct

#15

Post by nightshift1 »

dontwannahearit wrote: post #10
parasti wrote: post #7

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.

i noticed that with 4.7. i tried to add instructions in claude.md to unpack meaning when communicating to me but it did not work.

Re: Transformers are inherently succinct

#17

Post by measurablefunc »

yorwba wrote: post #12
measurablefunc wrote: post #6

What about the other direction? What languages are expressible w/ RNNs & LTLs that require exponential blowup for transformers?

Proposition 16. UHATs have polynomially bounded expansion over LTL. In particular, given an LTL formula φ, one can construct in polynomial time a UHAT T such that L(T) = L(φ). i.e. the blowup is only exponential in one direction.

That says every LTL formula can be compiled into UHAT w/ polynomial overhead. It doesn't say that all languages recognizable w/ UHATs necessarily do not have succinct recgonizers in LTLs or RNNs.

Edit: Actually nevermind. If UHAT could be compiled into LTL w/ polynomial overhead then that would also work for the languages that have exponential overhead in LTL but since they don't there is a strict separation.

Re: Transformers are inherently succinct

#18

Post by pafoster »

thesz wrote: post #14
lkm0 wrote: post #5

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?

> doesn't that mean we're approaching optimality? No. Transformers are Markov chains [1]. Somewhere around this fascinating site [2] I read that stateful models have an advantage. Author provided an example, a state machine with two states A and B, where at state A transitions are to state A (output 0) and to state B (output 1) with equal probability and at state B the transition is always to state A and output is al…

Markov chains are themselves a kind of state machine, namely a probabilistic deterministic finite automaton (PDFA), albeit where state is solely governed by the N most recent symbols. (Deterministic means that given a sequence, we can always infer the associated state transitions unambiguously). I believe the example in the reference you provide represents the more general case of PDFA, which is not representable as a finite order Markov processs.

Re: Transformers are inherently succinct

#19

Post by doug_durham »

This is a truly important paper. It formalizes the intuition that many in the field have. We can stop wasting time doing formal analysis of LLMs. If you have a problem that requires formal verification, don't use an LLM. You can use an LLM to help you build such a system, but the LLM can't be the system.

Re: Transformers are inherently succinct

#20

Post by aesthesia »

measurablefunc wrote: post #6

What about the other direction? What languages are expressible w/ RNNs & LTLs that require exponential blowup for transformers?

Not quite an answer to your question, but you might find this interesting. The Olmo Hybrid paper has some results on relative complexity of problems that can be solved by transformers and RNNs. They don't look at size, just solvability, and find that the sets of problems solvable by the two architectures are incomparable. They actually use these results to inform their architecture design, which includes both attention and state space layers. (Specifically, they choose gated delta-nets with negative eigenvalues, which they show have greater expressivity than those without.)

https://arxiv.org/abs/2604.03444

Post reply on HN