logoalt Hacker News

measurablefuncyesterday at 8:18 PM2 repliesview on HN

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


Replies

aesthesiayesterday at 9:38 PM

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

yorwbayesterday at 8:37 PM

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.

show 1 reply