论文标题： Transformers are Inherently Succinct

中文理解： Transformer 天然具有简洁表示能力

主题： Transformer 理论、形式语言、无星语言、线性时序逻辑、有限自动机、循环神经网络、模型验证复杂度

核心观点： Transformer 的理论优势不一定体现在“能表达更多语言”，而可能体现在“能用更短的模型描述复杂语言”。

总结

这篇文章提出用 简洁性 衡量 Transformer 的表达能力。作者证明，即使固定精度 Transformer 在可识别语言类别上并不比循环神经网络更强，它仍然可以比线性时序逻辑、循环神经网络和有限自动机更加简洁地描述某些形式语言。

更具体地说：

• Transformer 比线性时序逻辑和循环神经网络 指数级更简洁；
• Transformer 比有限自动机 双指数级更简洁；
• 这种简洁性会导致 Transformer 的形式验证问题非常困难，达到 指数空间完全问题。

1. 论文想解决的问题

过去很多 Transformer 理论工作关注的是：

Transformer 能识别哪些形式语言？

也就是说，把 Transformer 看成一个语言识别器，判断某个字符串是否属于某个语言。

但是这个视角有一个问题：在固定精度设定下，Transformer 能识别的是 无星语言，而无星语言只是正则语言的一个子类。相比之下，固定精度循环神经网络可以识别所有正则语言。

所以，如果只看“能不能识别某类语言”，Transformer 似乎不一定比循环神经网络更强。

本文因此换了一个角度：

不只问 Transformer 能不能表达某个语言，而是问它表达这个语言需要多大的模型。