# Encoder-Decoder Transformers: Logical Characterizations and Periodicity

arXiv: https://arxiv.org/abs/2605.07705 · HTML: https://mlsanity.com/paper/2605.07705/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 32 references that are in the map.
- First posted on arXiv 8 May 2026.

## Builds on (most cited first, 18 of 18)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Open-Sora: Democratizing Efficient Video Production for All](https://mlsanity.com/paper/2412.20404/) (2024)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)
- [Canary-1B-v2 & Parakeet-TDT-0.6B-v3: Efficient and High-Performance Models for Multilingual ASR and AST](https://mlsanity.com/paper/2509.14128/) (2025)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers](https://mlsanity.com/paper/2404.04393/) (2024)
- [Logical Languages Accepted by Transformer Encoders with Hard Attention](https://mlsanity.com/paper/2310.03817/) (2023)
- [Characterizing the Expressivity of Fixed-Precision Transformer Language Models](https://mlsanity.com/paper/2505.23623/) (2025)
- [Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats](https://mlsanity.com/paper/2405.14606/) (2024)
- [Knee-Deep in C-RASP: A Transformer Depth Hierarchy](https://mlsanity.com/paper/2506.16055/) (2025)
- [Unique Hard Attention: A Tale of Two Sides](https://mlsanity.com/paper/2503.14615/) (2025)
- [Expressive Power of Graph Transformers via Logic](https://mlsanity.com/paper/2508.01067/) (2025)
- [Probability Distributions Computed by Autoregressive Transformers](https://mlsanity.com/paper/2510.27118/) (2025)

## Abstract (arXiv)

We give logical characterizations of encoder-decoder transformers, the foundational architecture for LLMs that also sees use in various settings that benefit from cross-attention, in the practical setting of floating-point numbers and soft attention. First, we characterize such transformers via a new temporal logic that extends propositional logic with a counting global modality over the encoder input and a past modality over the decoder input, as well as via a type of distributed automata. We consider three frameworks: with and without a final softmax step in the transformer, and in the setting where each model generates tokens via autoregression. Second, we show that both autoregressive transformers and sentences of counting propositional logic - the fragment of the previous logic obtained by omitting the past modality - recognize exactly the commutative star-free languages. Finally, we find that the sequences of tokens the transformers generate are ultimately periodic (and each token appears in the period at most once). This allows us to characterize autoregressive transformers via sentences of counting propositional logic that generate tokens without autoregression, i.e., we can effectively eliminate recursion from the transformers.