证明了多种注意力机制在严格精度下仍属于TC⁰复杂度类。
Transformers in Uniform TC$^0$
- 在无近似、高精度浮点数下，注意力模型可被统一归入TC⁰
- SMAT在多项式位数精度或指数级误差下仍属DLOGTIME-uniform TC⁰
- 为神经网络的计算复杂性提供了更紧的理论边界，适合理论研究者
先前研究表明，平均硬注意力变换器（AHAT）和Softmax注意力变换器（SMAT）所识别的语言属于电路复杂度类TC⁰。但这些结果依赖于低精度算术：使用O(log n)位浮点数（n为输入长度）。Strobl证明了AHAT可在L-一致TC⁰中近似；Merrill与Sabharwal证明了SMAT可在DLOGTIME-一致TC⁰中近似。本文改进此结果，证明：无近似要求的AHAT、使用O(poly(n))位浮点精度的SMAT，以及绝对误差不超过2⁻ᴼ⁽ᵖᵒˡʸ⁽ⁿ⁾⁾的SMAT，均属于DLOGTIME-一致TC⁰。
原文摘要 · Abstract (English)
Previous work has shown that the languages recognized by average-hard attention transformers (AHATs) and softmax-attention transformers (SMATs) are within the circuit complexity class TC$^0$. However, these results assume limited-precision arithmetic: using floating-point numbers with O(log n) bits (where n is the length of the input string), Strobl showed that AHATs can be approximated in L-uniform TC$^0$, and Merrill and Sabharwal showed that SMATs can be approximated in DLOGTIME-uniform TC$^0$. Here, we improve these results, showing that AHATs with no approximation, SMATs with O(poly(n)) bits of floating-point precision, and SMATs with at most $2^{-O(poly(n))}$ absolute error are all in DLOGTIME-uniform TC$^0$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。