Chain of thought is a natural inference-time method for increasing the computational power of transformer-based large language models (LLMs), but comes at the cost of sequential decoding. Are there more efficient alternatives to expand a transformer's expressive power without adding parameters? We consider transformers with padding tokens as a form of parallelizable test-time compute. We show that averaging-hard-attention, masked-pre-norm transformers with polynomial padding recognize precisely the class $\mathsf{FO}$-uniform $\mathsf{TC}^0$ of extremely parallelizable problems. While the $\mathsf{TC}^0$ upper bound was known, proving a matching lower bound had been elusive. Further, our novel analysis reveals the precise expanded power of padded transformers when coupled with another form of inference-time compute, namely dynamically increasing depth via looping. Our core technical contribution is to show how padding helps bring the notions of complete problems and reductions, which have been a cornerstone of classical complexity theory, to the formal study of transformers. Armed with this new tool, we prove that padded transformers with $O(\log^d n)$ looping on inputs of length $n$ recognize exactly the class $\mathsf{FO}$-uniform $\mathsf{TC}^d$ of moderately parallelizable problems. Thus, padding and looping together systematically expand transformers' expressive power: with polylogarithmic looping, polynomially padded transformers recognize precisely the class $\mathsf{FO}$-uniform $\mathsf{NC}$, the best that could be expected without losing parallelism (unless $\mathsf{NC} = \mathsf{P}$). Our results thus motivate further exploration of padding and looping as parallelizable alternatives to chain of thought for test-time compute.

翻译：思维链是一种在推理阶段自然提升基于Transformer的大语言模型计算能力的常用方法，但需要付出顺序解码的代价。是否存在更高效的替代方案，在不增加参数的情况下扩展Transformer的表达能力？本文研究将填充标记作为可并行化的测试时计算形式。我们证明，采用平均硬注意力机制、掩码预归一化结构并引入多项式长度填充的Transformer，能够精确识别高度可并行化问题类——即$\mathsf{FO}$-均匀的$\mathsf{TC}^0$类。虽然$\mathsf{TC}^0$的上界已知，但匹配下界的证明一直存在困难。进一步地，我们通过新颖的分析揭示了当填充机制与另一种推理时计算形式（即通过循环动态增加深度）结合时，填充Transformer所扩展的精确能力。我们的核心理论贡献在于阐明了填充机制如何将经典计算复杂性理论中的核心概念——完全问题与归约——引入Transformer的形式化研究。借助这一新工具，我们证明：在长度为$n$的输入上执行$O(\log^d n)$次循环的填充Transformer，恰好能识别中等并行化问题类——即$\mathsf{FO}$-均匀的$\mathsf{TC}^d$类。因此，填充与循环机制共同系统地扩展了Transformer的表达能力：通过多对数次循环，多项式填充的Transformer可精确识别$\mathsf{FO}$-均匀的$\mathsf{NC}$类——这是在保持并行性的前提下所能达到的最优结果（除非$\mathsf{NC} = \mathsf{P}$）。我们的研究结果进一步激励了对填充与循环机制作为思维链的并行化替代方案进行深入探索，以增强测试时计算能力。