Hacker News
points by GuB-42 3 days ago | 0 comments
I wonder if there are proofs regarding what neural networks like the transformer can solve. Because fundamentally, Astra is just a bunch of matrix multiplications and a few well defined non-linear functions.

Anyways, most of the times, SAT can be solved quickly, but not always, so getting the answer from Astra in polynomial time doesn't prove much unless you can also prove that it always does, no matter the input.

[–] ViscountPenguin 3 days ago
Iirc, there's a big difference between the computational complexity of what a transformer can solve and what it can solve in practice; what it can solve in practice tends to come from things like singular learning theory (which describes the forms of generalizations that a given ML algorithm can make), but I think (iirc) that transformers can compute a pretty broad class of O(N^2) functions?
[–] anon291 3 days ago
For the umpteenth time a transformer is an arbitrary turning machine due to the fact that it has a theoretically limitless tape (the context).

A single transformer step is simply O(1) (for a particular parameter size), but it applied a potentially infinite number of times.

Thus while a single transformer cannot solve any problem, a transformer system applied in the normal way can solve any computable problem.

[–] geraneum 3 days ago
The context acting as a "theoretically limitless tape" while simultaneously the step being O(1) are contradictory. You cannot have it both.
[–] GuB-42 2 days ago
It depends on what you say is O(1). A theoretical Turing machine has an infinite tape that can be accessed in O(1), but in real life, it would require a machine of an infinite size.

Same idea for that transformer, it needs an infinite context, and it is an infinitely big machine, but with that level of abstraction, it processes a token in O(1).

In practice, there is no such thing as O(1) on arbitrarily sized data, there is no such thing as infinity either, it is just an abstraction.

[–] geraneum 2 days ago
> Same idea for that transformer

It’s not the same for transformers, especially not with the theoretical infinite context. It simply doesn’t process tokens in O(1) in your given setup.

In practice, with frontier LLMs, it’s of course more complicated, and also they don’t reveal how they do lookups, but still the theoretical limit applies regardless.

Do you mind elaborating or perhaps providing some reference as to why you think transformers should be similar to a Turing machine on this specific criteria?

[–] vidarh 3 days ago
The context can change each time. To implement a UTM only requires 2 states and 3 symbols or the reverse.

So if you use the context not as a tape in itself, but as an io channel to read/write an infinite tape, the context for any given step can remain fixed in size, and so the step itself can be O(1).

[–] geraneum 2 days ago
Any basic lookup table is turing complete if you bolt an external infinite tape and read/write head onto it. But then that’s moving the goal post since the context wouldn’t be the “limitless tape” and it’s not a transformer “in the normal way” because turing completeness would be coming from external io and not from auto regressive self attention. Different topic.
[–] vidarh 2 days ago
The point is that the discussion is essentially entirely meaningless, as it's pretty much hard to implement any simple construct that can make deterministic decisions based on a data stream and wrap it in a loop without ending up with a UTM.

The consequence of that is that the original question GuB-42 raised is pretty pointless too. An "inert" transformer effectively has limitations, but as typically used it trivially becomes Turing complete, and so the class of problems it can solve is the exact same class of problems almost any of our other computational devices can solve.

And if you want to point out that this externalises all of what actually matters if we are talking about e.g. intelligence, then yes, it does. But by extension you can trade complexity of the tape for complexity of the machine, and so you can internalise any part of the problem that can be solved with a finite section of tape as a single state transition (trivial proof: For a given machine M with finite state, you can make your machine N execute those steps as a single state transition by having N run M on a state transition.)

To extend that to where I assume they'd want to go in the first place: A transformer wrapped in a loop with access to "just" a "tape head" can "only" be limited from being theoretically able to get all the way to human level intelligence if human brains depend on computations that exceed the Turing computable. But that is no different from any other Turing complete device.

Of course that says nothing of whether it's a practical way of getting there.

[–] anon291 3 days ago
It's not contradictory at all. The dfa at each step of the turing machine model is also o(1).
[–] geraneum 3 days ago
Of course it is. You’re conflating a turing machine with a transformer. Transformers don’t have a local read/write head. The [self] attention is over the whole context, which makes each step O(N) at best (with caching) and O(N^2) w/o.
[–] anon291 2 days ago
of course it has a read write head. In fact it has N read / write heads equal to the size of the context since each latent state is updated with the results of the cross attention mechanism at each step.

Alternatively, you can view the '<unknown>' token that is dynamically driven to the embedding of the output token to be the write head. Either way, the simple truth is that you can train a transformer system (i.e., an iteratively applied transformer) to simulate an arbitrary turing machine.

[–] geraneum 2 days ago
There’s no such thing as a read/write head in transformers. You can use it as a metaphor but that’s a leaky metaphor, hence all these misunderstandings.

> In fact it has N read / write heads equal to the size of the context

And what is the asymptotic notation when computation scales linearly with the size of context?

> Either way, the simple truth is that you can train a transformer system

Which still doesn’t mean they have a read/write head or have O(1) complexity for token computation with “infinite context”.

[–] anon291 1 day ago
> There’s no such thing as a read/write head in transformers. You can use it as a metaphor but that’s a leaky metaphor, hence all these misunderstandings.

The input to a transformer is a list of embeddings. The output is a list of embeddings of the same length. At the end of the day, you can represent the entirety of the transformer's matrix multiplies and such as a DFA (IEEE 754 float multiplication and addition is a simple DFA, and you're just scaling this up that many times). Thus, you take a list of embeddings (i.e., the tape) and output another, modified, list of embeddings. You have successfully read (ingested) and written (the transformer output) N positions on a tape.