💬 NLP

Probability Distributions Computed by Autoregressive Transformers

This paper characterizes the probability distributions expressible by autoregressive transformer language models, demonstrating that their autoregressive and probabilistic nature can increase expressivity and break equivalences found in non-probabilistic language recognizers.

Original authors: Andy Yang, Anej Svete, Jiaoda Li, Anthony Widjaja Lin, Jonathan Rawski, Ryan Cotterell, David Chiang

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andy Yang, Anej Svete, Jiaoda Li, Anthony Widjaja Lin, Jonathan Rawski, Ryan Cotterell, David Chiang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a Transformer (the AI model behind tools like ChatGPT) as a very smart, but slightly rigid, robot librarian. For years, researchers have studied this librarian by asking it a simple "Yes or No" question: "Does this specific book belong in the 'Science Fiction' section?" If the robot says "Yes," the book is accepted; if "No," it's rejected. This is what the paper calls a Classifier.

However, in the real world, we don't just ask the librarian to sort books. We ask it to write a story. We give it the first few words, and it guesses the next word, then the next, and the next, creating a probability distribution (a guess about what comes next). This is what the paper calls an Autoregressor.

The paper asks a fundamental question: Is the robot better at writing stories than it is at sorting books? Or, conversely, does its ability to sort books tell us everything we need to know about its ability to write?

Here is the breakdown of their findings using simple analogies:

1. The Two Ways of Thinking

The authors realized that most previous research treated the Transformer like a Judge (Classifier), while the actual AI we use acts like a Storyteller (Autoregressor).

The Judge: Looks at a whole sentence and says, "True" or "False."
The Storyteller: Looks at a sentence so far and says, "There is a 90% chance the next word is 'cat' and a 10% chance it is 'dog'."

2. The "Boolean" World (The Simple Case)

Imagine a world where the robot only deals in black and white (True/False).

The Finding: In this simple world, the Judge and the Storyteller are essentially the same person. If the robot can sort a book correctly, it can also write a story that follows the same rules, and vice versa.
The Catch: While they are equally powerful, the Storyteller sometimes needs a much more complicated internal "instruction manual" (logic) to do the same job as the Judge. It's like the Judge can spot a pattern instantly, but the Storyteller has to write a long, complex recipe to generate that same pattern word-by-word.

3. The "Real-Weighted" World (The Complex Case)

Now, imagine the robot deals in shades of gray (probabilities, like 0.5, 0.9, etc.). This is how real AI works.

The Finding: Here, the Judge and the Storyteller are not the same. They have different superpowers.
- The Storyteller is more flexible: It can generate certain types of probability patterns that the Judge simply cannot recognize.
- The Judge is more rigid: There are specific probability patterns the Judge can identify that the Storyteller cannot generate because the Storyteller has to follow strict rules to ensure its probabilities always add up to 100%.
The Analogy: Think of the Judge as a security guard who can spot a fake ID instantly. The Storyteller is a forger trying to create a fake ID. Sometimes the forger can create a fake ID that the guard can't spot (because the guard only checks against a specific list). But sometimes, the forger is so bound by the rules of paper and ink that they can't create a specific type of fake ID that the guard can easily spot.

4. The "Time Travel" Logic

The paper uses a special kind of logic called "Linear Temporal Logic" (LTL) to describe what these robots can do. It's like a set of rules for time travel:

"Yesterday" (Y): Looking back at the previous word.
"Historically" (H): Looking back at all previous words.
"Since" (S): Looking back from a specific point.

The authors found that:

If the robot has access to "Yesterday" and "Historically" (looking back), the Judge and Storyteller are equal.
If the robot is restricted (e.g., it can only look back a few steps or only uses "Historically"), the Storyteller becomes strictly more powerful than the Judge. The Storyteller can handle patterns that the restricted Judge cannot.

5. The "Counting" Problem

The paper also looked at robots that are good at counting (like counting how many 'a's are in a string).

Previous research showed that as Judges, these robots could only count up to a certain limit based on their size.
However, as Storytellers, they could actually handle slightly more complex counting tasks. The act of predicting the next word step-by-step gave them a tiny bit more "brainpower" than just judging the whole string at once.

Summary

The main takeaway is that we cannot assume that what a Transformer can do as a "Judge" (recognizing patterns) is exactly the same as what it can do as a "Storyteller" (generating text).

In simple, black-and-white scenarios, they are mostly the same.
In the complex, real-world scenario of probabilities, the "Storyteller" has unique abilities that the "Judge" doesn't have, and vice versa.

This means that when scientists test AI capabilities, they need to be careful. Just because a robot fails a "sorting test" doesn't mean it will fail at "writing a story," and a robot that is great at sorting might struggle with the specific rules of generating a story. The paper provides a map to understand exactly where these differences lie.

Technical Summary: Probability Distributions Computed by Autoregressive Transformers

Problem Statement

Existing theoretical work on transformer expressivity predominantly treats transformers as language recognizers (classifiers), where the input is a complete string and the output is a binary classification (accept/reject). However, the primary practical application of transformers is as language models (autoregressors), which generate strings token-by-token by predicting a probability distribution over the next symbol given a prefix.

This paper addresses a fundamental gap: it is unclear which theoretical results regarding transformer expressivity in the recognition setting carry over to the language modeling setting. Specifically, the authors investigate whether the equivalence classes established for transformers as Boolean classifiers (e.g., equivalence to Linear Temporal Logic or counter-free automata) hold when transformers are used as real-weighted or Boolean autoregressors.

Methodology

The authors develop a formal framework to compare transformers as classifiers versus autoregressors across two weight domains:

Boolean Semiring ( $\mathbb{B}$ ): Weights are $\{0, 1\}$ (False/True).
Real Semiring ( $\mathbb{R}_{\geq 0}$ ): Weights are non-negative real numbers (probabilities).

They define a state encoder as a function mapping a string prefix to a sequence of states, where the state at position $i$ depends only on the prefix $w_{\leq i}$ . Using this abstraction, they analyze four specific configurations:

Boolean Classifiers: Map a full string to a Boolean value.
Boolean Autoregressors: Map a prefix to a distribution over the next token (Boolean weights).
Real Classifiers: Map a full string to a real weight.
Real Autoregressors: Map a prefix to a probability distribution over the next token.

The study focuses on Unique Hard Attention Transformers (UHATs) and Softmax Attention Transformers (SMATs) with fixed precision. These are compared against:

Linear Temporal Logic (LTL) and its fragments (e.g., $TL[P]$, $TL[H]$).
Counter-free Deterministic Finite Automata (cfDFAs) and Counter-free Nondeterministic Finite Automata (cfNFAs).

The core methodology involves constructing reductions between these formalisms to determine if one can simulate the other in both classifier and autoregressive modes.

Key Contributions and Results

1. Equivalence in Boolean Classifiers vs. Autoregressors

Full LTL: In the Boolean semiring, LTL classifiers and LTL autoregressors are equivalent. A transformer acting as a Boolean autoregressor can define the same languages as one acting as a classifier, provided the logic includes the "Yesterday" ( $Y$ ) and "Historically" ( $H$ ) operators.
Complexity of Conversion: While equivalent, converting an autoregressor to a classifier (specifically removing the $Y$ operator) can require exponential blowup in formula size. The paper proves that constructing a polynomial-time equivalent transformation for certain fragments is unlikely unless $P = PSPACE$ or $P = NP$.

2. Divergence in Restricted Fragments (Boolean)

When restricting the set of temporal operators (e.g., to $TL[H]$ or $TL[P]$ without $Y$ ), autoregressors become strictly more expressive than classifiers.

Example: The language $(ab)^*$ is definable by a Boolean $TL[\emptyset]$ autoregressor but cannot be defined by any $TL[H]$ or $TL[Y]$ classifier.
Implication: Transformers with specific attention mechanisms (like leftmost UHATs or fixed-precision SMATs, which correspond to these fragments) can recognize languages as autoregressors that they cannot recognize as classifiers.

3. Divergence in Real-Weighted Settings

In the real semiring, the expressivity landscape changes significantly:

Classifiers vs. Autoregressors: They are incomparable.
- There are weighted languages expressible by real autoregressors but not real classifiers (e.g., $(\frac{1}{2}a)^*$ , which requires infinite distinct weights).
- There are weighted languages expressible by real classifiers but not real autoregressors (e.g., $(1a)^*$ , which is not a normalized probability distribution).
UHATs and cfDFAs: In the real setting, UHATs (and LTL) as autoregressors are equivalent to counter-free DFAs. However, they are strictly less expressive than weighted counter-free NFAs.
- The paper demonstrates a counter-free weighted NFA that is not determinizable (cannot be converted to an equivalent weighted DFA), showing that the non-determinism in the real-weighted setting adds expressivity that transformers (modeled as deterministic state encoders) cannot capture.

4. Impact of Counting Operators

The paper revisits results regarding transformers with counting capabilities (e.g., SMATs with arbitrary precision inside attention, equivalent to $TL[\#]$ ).

Previous work showed these transformers recognize specific languages as classifiers.
This paper shows that as autoregressors, these models are slightly more powerful, capable of recognizing languages (like $L_{k+2}$ ) that they cannot recognize as classifiers (limited to $L_k$ ). This explains discrepancies between theoretical recognition bounds and empirical symbol-prediction performance in prior literature.

Significance and Claims

The paper claims to provide a principled way to interpret existing experiments on transformer expressivity.

Validation: In many cases (specifically full Boolean LTL), results from the language recognition literature do transfer to language models. For instance, since UHATs cannot recognize PARITY as classifiers, they cannot do so as autoregressors either.
Caveats: The authors emphasize that one cannot blindly assume recognition results apply to generation.
- Real Weights: The shift from Boolean to real weights breaks equivalences found in the Boolean case (e.g., between DFAs and NFAs).
- Autoregression vs. Classification: Autoregression can strictly increase expressivity in restricted logical fragments (Boolean) and changes the class of expressible weighted languages (Real).
Future Directions: The authors suggest that future work should extend these results to log-precision softmax attention, positional encodings, and "chain of thought" reasoning in real-weighted settings, noting that current techniques for proving inexpressibility in autoregressors are limited.

In summary, the paper establishes that while transformers as language models share much of their theoretical foundation with transformers as recognizers, the shift to autoregression and real-valued probabilities introduces subtle but critical differences in computational expressivity, particularly regarding the power of non-determinism and the specific temporal operators available.