4 ms·

Hasn’t it been shown that the complexity class of a transformer outputting a single token is TC^0 ? So, you can’t really expect it to directly output what some

by drdeca 2y ago

Hasn’t it been shown that the complexity class of a transformer outputting a single token is TC^0 ? So, you can’t really expect it to directly output what some input code would output without allowing it extra computation steps by letting it output some other tokens first? Edit: err… I guess what has been shown is more, a variation on transformers where the attention attends only to the ones that would be tied for first, evenly distributed among those, rather than distributed more generally among all the previous tokens, but I wouldn’t be surprised if the same is true with normal attention

dartos 2y ago
> So, you can’t really expect it to directly output what some input code would output without allowing it extra computation steps by letting it output some other tokens first? These commercial LLMs are trained to be conversational. That’s why they don’t just output the code’s result. ChatGPT and Claude also randomize the seed for each convo (or each message, not sure) and include things like the current date in the prompt. It’s very difficult to tell if something is reproducible or just a lucky (or unlucky) output.
- drdeca 2y ago
  They may do that for that reason, and it might also happen to help them produce the right output code. My point is just that (aiui), for any transformer model, holding the network constant but increasing the length of the code that is the input, at some point they will be unable to produce the output of the code without first preceding it with other output tokens first. Of course, this statement is kind of trivial as applied to current transformer models because they have a limited context length anyway (they don’t properly generalize to ~arbitrary context lengths, but I imagine there is a way to fix that… idk how though). And, also, “output the tokens for the output of the code immediately, without other tokens first” is I think a bit restrictive. That they are limited in this way when required to produce the output immediately is, to my mind, not that significant of a limitation. Just wrap the model in a simpler (designed by hand) program which has the model produce whatever tokens it needs to produce to get the answer, and then extract the answer from that and yield that as the output. (Though, while it seems likely to me that there is a possible transformer model that would be capable of serving this role inside such a wrapper, obtaining such a model through training seems more complicated.)
  - dartos 2y ago
    Just some thoughts: > they don’t properly generalize to ~arbitrary context lengths, but I imagine there is a way to fix that… idk how though There’s no way to fix that for transformers architectures as the limited context length is inherent in their attention mechanisms (it’s a big reason they are so efficient at inference time,) but RNN architectures like RWKV have no such limitation, but haven’t seen success at a large scale yet. > They may do that for that reason, and it might also happen to help them produce the right output code We can only really spitball at this, but I’m poverty confident that it’s a result of how they’re trained. You could train a model that just takes natural language and outputs only code, with no conversion. Those models would be less general, and less interesting to non Technical people, which is why we don’t see them as much (imo.)
    - drdeca 2y ago
      > You could train a model that just takes natural language and outputs only code, with no conversion. Those models would be less general, and less interesting to non Technical people, which is why we don’t see them as much (imo.) Right, I’m not saying “the reason they output other text first is because they need to in order to produce the correct output.”. I agree that the reason they put the other text first is due to how they were trained. I’m just saying that if they didn’t do that, that this would limit the theoretical maximum average performance they could achieve at the “producing the output of some long code” task. But, I don’t expect that this was part of the motivation that led to them being trained in the way they have been. > There’s no way to fix that for transformers architectures as the limited context length is inherent in their attention mechanisms Hmm… the paper showing that transformers can recognize TC^0 has a definition for attention that is a bit different from the usual attention, and seems a bit restricted.., it seemed to me that the paper involved the idea that this could be applied to arbitrary length sequences, but I could be mistaken.
      - dartos 2y ago
        Oh? Do you have a link to that paper? I’m no linalg expert, but it was my understanding that attention worked (very basically) because each token attends to all other tokens in the sequence, but you can’t do that with an unbounded sequence length
DannyBee 2y ago
Sure, there are models and variations whose power is not good enough to approximate the problems we are talking about here - most of them trading speed for power on purpose because of the enormous costs involved. This is actually one of the reasons i think the author's claim is so silly. They don't claim it will never be practical, they claim it will never be. For the purposes of this discussion, I don't claim you can make a practical LLM that understands code or simulates it. Only that you can make one at all :) I actually do think you can make a practical and useful one for a simple reason - while all the edge cases are fun to come up with, and the amount/kinds of code one could write is clearly infinite, code is closer to literary works or musical compositions in how that plays out - daily WTF aside, we don't actually write all possible code, and even to the degree you do, you don't really have to handle it all to be practical or useful. IE The set of music that you can create and books you can write is similarly infinite. However, the set of music that "sounds right" (go with me) and books that "read right" is not anywhere near as huge in practice. This isn't just semantics/syntax. Code is similar - while the possibility is infinite, you don't need to handle any possible thing to be very useful - you just need to be able to handle some part of the spectrum from "worlds shittiest code or most broken code" to "worlds highest quality or most elegant code". To me, this is a much more tractable approximation problem than "handle anything anyone ever throws at you" The same way i think it's a more tractable approximation problem to say "make something that sounds good to the average pop music listener" vs "make an original and unique composition of music that sounds good to everyone who hears it" or whatever. (I'm not being super precise, but i expect you get the point :P)

by drdeca 2y ago

dartos 2y ago

> So, you can’t really expect it to directly output what some input code would output without allowing it extra computation steps by letting it output some other tokens first? These commercial LLMs are trained to be conversational. That’s why they don’t just output the code’s result. ChatGPT and Claude also randomize the seed for each convo (or each message, not sure) and include things like the current date in the prompt. It’s very difficult to tell if something is reproducible or just a lucky (or unlucky) output.

drdeca 2y ago
They may do that for that reason, and it might also happen to help them produce the right output code. My point is just that (aiui), for any transformer model, holding the network constant but increasing the length of the code that is the input, at some point they will be unable to produce the output of the code without first preceding it with other output tokens first. Of course, this statement is kind of trivial as applied to current transformer models because they have a limited context length anyway (they don’t properly generalize to ~arbitrary context lengths, but I imagine there is a way to fix that… idk how though). And, also, “output the tokens for the output of the code immediately, without other tokens first” is I think a bit restrictive. That they are limited in this way when required to produce the output immediately is, to my mind, not that significant of a limitation. Just wrap the model in a simpler (designed by hand) program which has the model produce whatever tokens it needs to produce to get the answer, and then extract the answer from that and yield that as the output. (Though, while it seems likely to me that there is a possible transformer model that would be capable of serving this role inside such a wrapper, obtaining such a model through training seems more complicated.)
- dartos 2y ago
  Just some thoughts: > they don’t properly generalize to ~arbitrary context lengths, but I imagine there is a way to fix that… idk how though There’s no way to fix that for transformers architectures as the limited context length is inherent in their attention mechanisms (it’s a big reason they are so efficient at inference time,) but RNN architectures like RWKV have no such limitation, but haven’t seen success at a large scale yet. > They may do that for that reason, and it might also happen to help them produce the right output code We can only really spitball at this, but I’m poverty confident that it’s a result of how they’re trained. You could train a model that just takes natural language and outputs only code, with no conversion. Those models would be less general, and less interesting to non Technical people, which is why we don’t see them as much (imo.)
  - drdeca 2y ago
    > You could train a model that just takes natural language and outputs only code, with no conversion. Those models would be less general, and less interesting to non Technical people, which is why we don’t see them as much (imo.) Right, I’m not saying “the reason they output other text first is because they need to in order to produce the correct output.”. I agree that the reason they put the other text first is due to how they were trained. I’m just saying that if they didn’t do that, that this would limit the theoretical maximum average performance they could achieve at the “producing the output of some long code” task. But, I don’t expect that this was part of the motivation that led to them being trained in the way they have been. > There’s no way to fix that for transformers architectures as the limited context length is inherent in their attention mechanisms Hmm… the paper showing that transformers can recognize TC^0 has a definition for attention that is a bit different from the usual attention, and seems a bit restricted.., it seemed to me that the paper involved the idea that this could be applied to arbitrary length sequences, but I could be mistaken.
    - dartos 2y ago
      Oh? Do you have a link to that paper? I’m no linalg expert, but it was my understanding that attention worked (very basically) because each token attends to all other tokens in the sequence, but you can’t do that with an unbounded sequence length

DannyBee 2y ago

Sure, there are models and variations whose power is not good enough to approximate the problems we are talking about here - most of them trading speed for power on purpose because of the enormous costs involved. This is actually one of the reasons i think the author's claim is so silly. They don't claim it will never be practical, they claim it will never be. For the purposes of this discussion, I don't claim you can make a practical LLM that understands code or simulates it. Only that you can make one at all :) I actually do think you can make a practical and useful one for a simple reason - while all the edge cases are fun to come up with, and the amount/kinds of code one could write is clearly infinite, code is closer to literary works or musical compositions in how that plays out - daily WTF aside, we don't actually write all possible code, and even to the degree you do, you don't really have to handle it all to be practical or useful. IE The set of music that you can create and books you can write is similarly infinite. However, the set of music that "sounds right" (go with me) and books that "read right" is not anywhere near as huge in practice. This isn't just semantics/syntax. Code is similar - while the possibility is infinite, you don't need to handle any possible thing to be very useful - you just need to be able to handle some part of the spectrum from "worlds shittiest code or most broken code" to "worlds highest quality or most elegant code". To me, this is a much more tractable approximation problem than "handle anything anyone ever throws at you" The same way i think it's a more tractable approximation problem to say "make something that sounds good to the average pop music listener" vs "make an original and unique composition of music that sounds good to everyone who hears it" or whatever. (I'm not being super precise, but i expect you get the point :P)