What the Exponential Adds: Softmax, Hard Attention, and Exact Counting

Hard-attention models simplify the study of transformer expressivity, but their conclusions need not transfer directly to softmax. Averaging hard attention (AHAT) averages values at the highest-scoring positions. Without positional encodings or masking, its rational-parameter version recognizes exactly the counting properties defined by Boolean combinations of polynomial inequalities with rational coefficients. Softmax recognizes strictly more. Two layers decide whether $\#a>\#c{e}^{\#b/(n+1)}$, where $n$ excludes one appended end marker: the first averages the $b$ indicator, and the second uses this average as the score for $c$. No semialgebraic description captures this property. The same network works when each position attends to itself and earlier positions, answering an open question. More generally, replace $e^u$ by a continuous positive function on a fixed closed interval containing all scores, keeping the remaining operations semialgebraic. Unmasked networks can recognize a nonsemialgebraic counting property exactly when this function is nonsemialgebraic on that interval; polynomial replacements therefore cannot recognize our example. Masking provides another route: three layers attending equally to earlier positions compare a count with $1+1/2+\cdots +1/(n-1)$, a property no unmasked softmax network built from affine maps and ReLUs recognizes. Finally, replacing $e^u$ by one polynomial keeps outputs of a fixed network with bounded inputs, affine/ReLU updates and an affine readout within any prescribed tolerance at every length. Preserving every decision of even our two-layer network at length $n$ requires degree at least $(1-o(1))\log n/\log \log n$. Among positive count triples of length $n$, the degree-ten Taylor replacement's disagreement fraction tends to about $3\times 10^{-11}$, yet it flips a length-$1080$ decision.