Transformers have emerged as a widely used neural network model for various
natural language processing tasks. Previous research explored their
relationship with constant-depth threshold circuits, making two assumptions:
average-hard attention and logarithmic precision for internal computations
relative to input length. Merrill et al. (2022) prove that average-hard
attention transformers recognize languages that fall within the complexity
class TC0, denoting the set of languages that can be recognized by
constant-depth polynomial-size threshold circuits. Likewise, Merrill and
Sabharwal (2023) show that log-precision transformers recognize languages
within the class of uniform TC0. This shows that both transformer models can be
simulated by constant-depth threshold circuits, with the latter being more
robust due to generating a uniform circuit family. Our paper shows that the
first result can be extended to yield uniform circuits as well.

该论文研究了 Transformers 模型在自然语言处理任务中的应用，并发现它们与常深度门电路之间的关系，通过两个假设（平均难度的注意力和对内部计算相对于输入长度的对数精度）。研究表明，平均难度的注意力 Transformers 可以识别属于复杂度类 TC0 的语言，而对数精度 Transformers 可以识别属于均匀 TC0 类的语言。此外，该论文还指出第一个结果可以扩展为生成均匀电路。