The Exact Expressive Power of Fixed-Precision Looped Padded Transformers

We establish the exact expressivity of fixed-precision looped padded transformers. With O(log N) width, log^d N depth, and poly(N) padding (in input length N), they are equivalent to L-uniform AC^d circuits. This extends recent results showing the equivalence of transformers with O(log N) precision, log^d N depth, and poly(N) padding to FO-uniform TC^d. Our result exposes fixed precisions expressivity cost: A drop from TC^d to AC^d due to inability to compute threshold functions.

Download the paper here

Citation BibTeX:

@article{svete-et-al-2025-exact-fp-lpt,
    title = "The Exact Expressive Power of Fixed-Precision Looped Padded Transformers",
    author = "Svete, Anej  and
      Merrill, William  and
      Sabharwal, Ashish",
    month = oct,
    year = "2025",
    url = "http://anejsvete.github.io/files/fp-lpt.pdf",
}