Skip to content
The methodOpen data
Back to the collection

The Parallelism Tradeoff: Limitations of Log-Precision Transformers

William Merrill, Ashish Sabharwal

2022 · arXiv

Language modelsAlgorithms
Read the paper
HN score
0
Mentions
6
Readers
4
Months
4
What’s in a score?

From the abstract

Despite their omnipresence in modern NLP, characterizing the computational power of transformer neural nets remains an interesting open question. We prove that transformers whose arithmetic precision is logarithmic in the number of input tokens (and whose feedforward nets are computable using space linear in their input) can be simulated by constant-depth logspace-uniform threshold circuits. This provides insight on the power of transformers using known results in complexity theory. For example, if $\mathsf L \neq \mathsf P$ (i.e., not all poly-time problems can be solved using logarithmic space), then transformers cannot even accurately solve linear equalities or check membership in an arbitrary context-free grammar with empty productions. Our result intuitively emerges from the transformer architecture's high parallelizability. We thus speculatively introduce the idea of a fundamental parallelism tradeoff: any model architecture as parallelizable as the transformer will obey limitations similar to it. Since parallelism is key to training models at massive scale, this suggests a potential inherent weakness of the scaling paradigm.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

6 selected excerpts · 6 total mentions

nyrikki
Neutral mention · rule
FFT is easy fairly easy for transformers to find as a pattern. Note that OpenAI admits that pre-training (pattern finding and matching) is where the abilities on professional tests comes from. Even proofs in presburger arithmetic have an upper bound on the second level of the polynomial hierarchy, which is way beyond the computational power of any LLM https://arxiv.org/abs/2207.00729 >The model’s capabilities on exams appear to stem primarily from the pre-training process and are not significantly affected by RLHF. On multiple choice questions, both the base GPT-4 model and the RLHF model perform equally well on average across the exams we…
Read the full comment
tested https://arxiv.org/abs/2303.08774 To practically scale, parallelism is required, and the ability to find algorithms within the L or TC0 complexity classes is limited. Remember that individual ANNs as used in transformers are just binary linear classifiers. Which you can do a lot with, but probably limited to P assuming we don't find out L or TC0 are larger than we think now. Presburger arithmetic, or first order logic with (+,=), or (*,=) is the strongest FoL that is both complete and consistent. move up to Peano arithmetic and you start to hit the limits from Gödel, Church, and Turing. There will be instances that an LLM can learn with CoT, zero shot etc... But most of those will be due to luck or parallel patterns in the training set. LLMs simplicity bias is great for plausible answers to our of distribution questions, but puts limits on what can be learned as far as 'algorithms' go. They will work for 'there exists' problems far better than for any 'for all' or 'for most' problems unless they have learnable patterns in the training set.
Original comment “Emergent” abilities in LLMs actually develop gradually and predictably – study
lambdaviking
Neutral mention · rule
Good question! A key use for this type of analysis is that it acts as an upper bound on transformers, rather just demonstrating "transformers are like logic". That is, it allows us to fairly easily identify problems that transformers cannot solve. Some examples are graph connectivity, linear programming, various forms of state tracking, etc. Definitely finding negative results like this is tough by just doing experiments, since it could be that the model might have succeeded if you had just trained it for more time/made it bigger/etc. Our prior paper discusses how this works more in depth: https://arxiv.org/abs/2207.00729
Original comment A Logic for Expressing Transformers
shawntan
Neutral mention · rule
But "don't try to codify 'insight' into the process" seems to suggest "don't try different approaches". I'm not sure how people can at once trot out the "Bitter Lesson" and interpret it as it is written, but still say "We're not saying not to think about new approaches". Is the idea then to work only on methods that allow for faster compute of more data? FWIW, the Transformer works faster on current methods of parallelisation, allowing for dramatic scaling that RNNs will find hard to compete on. But we do pay for that in terms of what can be computed (https://arxiv.org/pdf/2207.00729.pdf - TL;DR: Transformers are limited in the types of programs/functions it can compute because of parallelism). Scaling, ironically, does seem to be the 'direction of steepest descent' in terms of what will bring the best performance (for now). Gradient descent does find pleasant local optima that may keep us happy for a while.
Original comment The Alan Turing Institute has failed to develop modern AI in the UK
logicchains
Neutral mention · rule
>How would that be remarkable, when it is exactly what he Universal Approximation Theorem already states Only with infinite precision, which is highly unrealistic. Under realistic assumptions, fixed depth transformer without chain-of-thought are very limited in what they can express: https://arxiv.org/abs/2207.00729 . Chain of thought increases the class of problems which fixed depth transformers can solve: https://arxiv.org/abs/2310.07923
Original comment Chain of Thought empowers transformers to solve inherently serial problems
logicchains
Neutral mention · rule
If you read the rest of the paper it's clear what they mean. SSMs are theoretically no more powerful than transformers, meaning without chain of thought they can't efficiently solve state-tracking problems, unlike RNNs: https://arxiv.org/abs/2207.00729 .
Original comment The illusion of state in state-space models

Keep following the thread.

More in Language models

More from the same topics.