Mind the Mask: A Succinctness Hierarchy for Attention and Recurrence

How large must a recurrent model become to reproduce an attention model's decisions? We study exact replacement on every finite nonempty sequence for unique hard-attention transformers without positional encodings and with exact rational evaluation. The recurrent target has fixed finite state and explicitly represented Boolean update and readout circuits. We show that the replacement cost depends sharply on the attention masks. For fully unmasked attention, we prove an exact characterization by the first- and last-occurrence orders of input symbols, with polynomial conversions to profile predicate circuits and polynomial-size recurrent replacement. For mixed masks, we construct dictionary recognizers over a four-symbol alphabet, of description size polynomial in $n$, for which every exact recurrent replacement requires at least $2^{2^n}$ persistent bits. One unmasked retrieval between causal stages makes dictionary representations depend on the later query; causal operations then compare complete blocks. Together with inherited bounds, these results give polynomial, single-exponential, and double-exponential replacement regimes for unmasked, causal, and mixed attention. A direct causal compiler further quantifies the role of retrieval depth, and classical information bounds show that, under a specified dense dictionary distribution, any fixed average error below one half still requires a constant fraction of these bits.