The Counting Power of Transformers

We study how transformers reason about the number of occurrences of tokens. We show that they can express counting conditions involving polynomial inequalities, and identify a class of softmax transformers that captures exactly these conditions. The resulting connection to Hilbert’s tenth problem also shows that verification is undecidable even for a simple model without positional encodings or masking.

An earlier preprint was titled NoPE: The Counting Power of Transformers with No Positional Encodings.