4 ms·

Depending on your starting assumptions, Transformers, RNNs and LSTMS can either be a) Turing-complete, in which case they can all match unbounded brackets, or

Depending on your starting assumptions, Transformers, RNNs and LSTMS can either be a) Turing-complete, in which case they can all match unbounded brackets, or b) they are all not Turing-complete, LSTMs might be able to match unbounded brackets (if there is only one type of bracket), while RNNs and Transformers can't.

canjobear 3y ago
For Transformers you would need an infinite number of self-attention layers. For RNN/LSTM all you need is enough neurons to implement a counter.
- KMag 3y ago
  > For RNN/LSTM all you need is enough neurons to implement a counter. For an arbitrary depth, that would need to be an infinitely sized counter. (I presume you know this, but this is why a push-down automaton can always close parens, but a finite state machine can only close parens up to a finite nesting depth.) So, "all you need is enough neurons" for an RNN/LSTM is equivalent to just saying you just need to scale the LMM state large enough to handle your use case. In reality, ignoring rdrand (and other quantum noise instructions) and ignoring using I/O for external storage, all of our computers are (gigantic) finite state machines. Technically, our programming languages might be Turing complete, but our near-infinite memory implementations are actually finite state machines, not Turing-complete. Though, you only run into the difference when you fill the whole machine's memory. So, I think a more important question is how efficiently different finite state machines make use of their state sizes for a given problem. How many neurons would it take to match parens to a maximum depth of 2^40 for an RNN/LSTM vs. an LLM?
  - canjobear 3y ago
    An RNN with infinite-precision rational weights can implement a counter with a bounded number of neurons. With finite precision the number of neurons scales linearly in your desired depth of matching brackets: https://arxiv.org/pdf/2010.07515.pdf https://arxiv.org/pdf/2010.07515.pdf For a Transformer you need to add a new layer of self-attention to increase bracket matching depth by 1. https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00306/43545/Theoretical-Limitations-of-Self-Attention-in https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00306... Transformers are formally a lot weaker than RNNs/LSTMs.

canjobear 3y ago

For Transformers you would need an infinite number of self-attention layers. For RNN/LSTM all you need is enough neurons to implement a counter.

KMag 3y ago
> For RNN/LSTM all you need is enough neurons to implement a counter. For an arbitrary depth, that would need to be an infinitely sized counter. (I presume you know this, but this is why a push-down automaton can always close parens, but a finite state machine can only close parens up to a finite nesting depth.) So, "all you need is enough neurons" for an RNN/LSTM is equivalent to just saying you just need to scale the LMM state large enough to handle your use case. In reality, ignoring rdrand (and other quantum noise instructions) and ignoring using I/O for external storage, all of our computers are (gigantic) finite state machines. Technically, our programming languages might be Turing complete, but our near-infinite memory implementations are actually finite state machines, not Turing-complete. Though, you only run into the difference when you fill the whole machine's memory. So, I think a more important question is how efficiently different finite state machines make use of their state sizes for a given problem. How many neurons would it take to match parens to a maximum depth of 2^40 for an RNN/LSTM vs. an LLM?
- canjobear 3y ago
  An RNN with infinite-precision rational weights can implement a counter with a bounded number of neurons. With finite precision the number of neurons scales linearly in your desired depth of matching brackets: https://arxiv.org/pdf/2010.07515.pdf https://arxiv.org/pdf/2010.07515.pdf For a Transformer you need to add a new layer of self-attention to increase bracket matching depth by 1. https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00306/43545/Theoretical-Limitations-of-Self-Attention-in https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00306... Transformers are formally a lot weaker than RNNs/LSTMs.