I struggle heavily with complexity theory, and in particular struggle to follow the definitions, assumptions, and proofs. It can be very hard for me to decide whether to invest in the time and effort needed to decode a paper like this.
Here we have a number of assumptions, and very short proofs, which makes me a little worried that the CoT complexity class might not be useful for understanding the expressive power of actually existing transformers like LLMs - especially ones with hidden weights and architectures.
Can someone with a better understanding remark on this?
Some questions:
1. Does this paper let us better reason about trained hidden weight llms like gpt3.5/gpt4?
2. Does this paper imply that we can always exploit some linear CoT blowup factor to faithfully simulate an automaton, even on a very small transformers, like a 1.5B LLM instance?
3. Does this result attain for untrained or minimally trained transformers? Assuming that's not the case, what assumptions do we make about the network's training?
4. How would we bound the automaton simulation blow up factor for a given llm instance? Can we confirm bounds empirically by benchmarking transformer instances against a corpus of automaton specifications of arbitrary size?
Feedback from a expert on this subject would be really awesome!
1 comment
[ 2.9 ms ] story [ 10.4 ms ] threadHere we have a number of assumptions, and very short proofs, which makes me a little worried that the CoT complexity class might not be useful for understanding the expressive power of actually existing transformers like LLMs - especially ones with hidden weights and architectures.
Can someone with a better understanding remark on this?
Some questions:
1. Does this paper let us better reason about trained hidden weight llms like gpt3.5/gpt4?
2. Does this paper imply that we can always exploit some linear CoT blowup factor to faithfully simulate an automaton, even on a very small transformers, like a 1.5B LLM instance?
3. Does this result attain for untrained or minimally trained transformers? Assuming that's not the case, what assumptions do we make about the network's training?
4. How would we bound the automaton simulation blow up factor for a given llm instance? Can we confirm bounds empirically by benchmarking transformer instances against a corpus of automaton specifications of arbitrary size?
Feedback from a expert on this subject would be really awesome!