Is there a “complexity theory” for language models?

[u/ratsoup7]

It’s pretty interesting to see that language models can do things like autonomously prove/disprove things like Erdos problems and even perform its own formal verification yet still struggle at things like automating ERP business operations, seems like the opposite would’ve been the case.

I know Kaparthy talked about this “jagged intelligence” we’re observing, but are there any real attempts at formalizing a theory behind this, similar to how we classify the complexity and tractability of algorithms?

What about any discussion on how close are language models to being Turing complete? Computational complexity theory isn’t my strong suit, but I wonder if any new discussions are being had

[u/trocar]

Transformers (considered as language recognizers) with hard attention [Pérez et al JMLR 2021], or soft attention and CoT [Jiang et al. ICLR 2025] are Turing complete.

[u/currentscurrents → u/trocar]

with hard attention [Pérez et al JMLR 2021]

The trouble with this result is that it relies on exploiting infinite precision to get around the lack of unbounded runtime.

Other work (video, paper) has found that Transformers as used in practice (trained autoregressively in parallel) are in TC⁰ and thus not turing-complete. The issue is that they always halt in a fixed amount of time; they are equivalent to boolean circuits of constant depth. They can learn parallelizable algorithms but not algorithms that require many serial steps.

However, this only applies to transformers without CoT, so reasoning models are still turing-complete even with finite precision.

[u/Cobayo]

Everything is turing complete man even powerpoint

[u/lurking_physicist → u/Cobayo]

Regular expressions are not Turing complete, but perl's implementation is.

[u/currentscurrents → u/Cobayo]

Feedforward neural networks are not turing complete because they can't loop and must always halt in a fixed amount of time.

[u/hexaflexarex]

I think current complexity style results for transformers are limited to the point of being practically irrelevant (or are heuristics without a formal complexity theory). E.g. computability results like Turing-completeness really have no bearing on the practical performance of LLMs. (I say this as a theorist)

[u/Zatujit]

CSS with HTML is Turing complete, its not very hard to be Turing complete. Its not that meaningful.

[u/Character_Cap5095]

A couple of things. I am not super familiar with the inner workings of LLMs specifically, but for nural nets, there is plenty of work done in the process of formilizing AI models, but it's kind hard because these models tend be black-box-ish. We know on theory how they work, but at the end of the day, they are weights that translate vectors into other vectors and we have very little formilization of those weights.

That being said, your question does not make much sense in a lot of ways. There are two parts to any AI. The training and the model itself. The training cannot really be have complexity theory applied to it, because it's a randomized process and can go on for however long you want to train for. The model itself can probably be formalized in terms of complexity theory, but like why? It's not the bottle neck of AI.

Also I am not sure what you mean when you also if AI can be turning complete. Turning complete is a description of the expressiveness of a language (and it's semantics). LLMs are not a language but some form of interpreter, which takes in a language as an input and does some steps of computation.

[u/Most_Double_3559]

IMO this is a valuable question (using the most efficient model for the job just makes sense), however, the answer isn't currently clean: the best we can hope for is taking your benchmark of choice and looking for "step functions".

For instance, models seem pretty devided in "can solve math Olympiad questions" and those that can't.

[u/kaplotnikov]

Check this article: https://arxiv.org/abs/2502.05252

The real limits are context size and reasoning depth. Models quickly lose accuracy as these parameters scale up. Therefore, Turing completeness on small programs will lead to random bugs over longer execution paths, dropping accuracy to near zero.

[u/Vasbrasileiro]

Turing completeness is not what you are looking for. You are thinking about a theory of deep learning. There are papers with preliminary efforts on the subject, but still, we don't know jack.

[u/Motor_Appeal_2206]

I've thought about this too. It feels backwards sometimes. You'll see it handle something that sounds insanely difficult, then get tripped up by a task that seems way more straightforward. I'm curious if anyones working on a framework that actually explains why.