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.

本研究证明了计算精度对数与输入标记数量相关的 transformer 神经网络可以通过常深度对数空间均匀阈值电路进行模拟，并且从复杂性理论的角度提供了关于 transformer 网络计算力的见解，这表明如果 L≠P，那么 transformer 神经网络甚至无法精确解决线性等式或检查产生空符号的任意上下文无关语法的成员身份，因此研究也推测性地引入了一种基本的并行性权衡观念：与 transformer 一样并行化的任何模型体系结构都将遵守类似的限制，这暗示了放大模型范式的潜在固有弱点。