Characterizing the Expressivity of Fixed-Precision Transformer Language Models

We thank the reviewer for engaging deeply with the paper. Below, we respond to the main concerns point by point.

The paper does not formally define "fixed precision"... depending on assumptions, fixed precision can effectively turn into logarithmic precision. Hence, fixed precision has to be carefully defined.

We define fixed precision by assuming the existence of a finite set $\\mathbb{F}$ of representable numbers, under which the transformer operates. We do not make assumptions about specific rounding rules, or rationality of values, or closeness to ideal real-valued outputs. Instead, we rely on three minimal and realistic properties:

1. Overflow: There is a maximum representable number; any computation exceeding it yields overflow.
2. Underflow: There is a smallest positive number; values below it round to zero.
3. Exponential cutoff: There exists a sufficiently negative number $x$ such that $\\exp(x) = 0$.

All of these are satisfied by standard numerical libraries (e.g., NumPy, PyTorch, JAX).

We appreciate the reviewer’s request for precision and will clarify this definition explicitly in the final version, if given the opportunity.

I have a ''counter-example'' to the main result... Apprxoimate Majority...

Approximate Majority is not recognizable in our idealization, precisely because uniform attention (and thus averaging inputs) is not always feasible for all input lengths. Therefore, it does not constitute a counterexample.

I believe that fixed-precision assumption does not make sense for the case of softmax transformers.

Why let the input length go to infinity? Practical models use 32-bit precision and finite inputs.

Our experiments show that transformers fail to generalize well before the theoretical precision limit. Specifically, under standard 32-bit precision, models fail to generalize on tasks that log-precision models would handle at sequence lengths below 500, far short of $2^{32}$. Notably, length 500 is not large by practical standards either.

Why real-world models fail so early and appear empirically weaker than log-precision theoretical predictions remains an open question and an exciting direction for future work.

By contrast, our results align exactly with the fixed-precision model: languages inside $\**PFO**^2[<]$ can be trained to $100\\%$ accuracy, while those outside cannot. This suggests that fixed precision provides a realistic and informative lower bound on the class of languages transformers can express reliably and without error, and studying it is far from pointless.

Additionally, the fixed-precision setting becomes even more relevant as quantized models are increasingly popular in practice. These models operate at significantly lower precision (e.g., 8-bit or 4-bit), making precision constraints even more immediate and our theoretical framework directly applicable.

In summary, we see the study of fixed precision as complementary to other settings, such as logarithmic precision, or mixed precision (e.g., Yang and Chiang, 2024, where attention uses rational arithmetic but other operations remain fixed-precision).

We again thank the reviewer for their time and effort. We hope these clarifications have helped convey the scope and motivation of our work, and we will revise the paper accordingly should we have the chance.

–-

References

• Yang and Chiang. (2024). Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers.

We thank the reviewer for their thoughtful and positive review. We are especially grateful for the recognition of the novelty and significance of our theoretical results, the strength of the proofs, the clarity of the writing, and the potential interest to the broader research community. Below, we address the specific comments and questions raised.

In the title and elsewhere, this paper seems to imply its results hold for all transformer language models, while in reality it characterizes one specific formal model... I would prefer if the title was precise about this fact via inclusion of the term fixed precision.

We agree and appreciate the suggestion. While we refer to "fixed precision" throughout the paper, the title and introduction could indeed better reflect the specific model we analyze. We will revise the title and refine the introductory language to make it clear that our results pertain specifically to fixed-precision transformer models.

What precision do you use in your experiments?

We use the default 32-bit floating point precision provided by the standard JAX library for both training and inference.

What evidence do you have for this? Usually in practice precision is greater than log₂n, so log precision seems reasonable.

Our empirical results suggest that with 32-bit precision, transformers fail to generalize at input lengths below $500$ on languages outside $\**PFO**^2[<]$, many orders of magnitude smaller than the theoretical bound of $2^{32}$. This suggests that log precision may overestimate real-world transformer capabilities, and motivates our focus on strict fixed precision.

Regarding the claim that the LTL[past] results perfectly predict length generalization, C-RASP... also seems to have strong theory/experiment match... How do you reconcile your claims with theirs?

C-RASP retains fixed precision outside attention but allows arbitrary precision within attention. This effectively augments $\**PFO**^2[<]$ with counting.

Experimentally, the two studies adopt different definitions of success. Our evaluation requires perfect generalization across all input lengths, consistent with formal models such as logic and automata. Huang et al. (2025) adopts a more relaxed criterion, focusing on strong but not perfect generalization. We view the two results as complementary: C-RASP highlights what transformers may learn approximately and generalize well in practice, while our work characterizes what they can reliably and provably generalize without error.

Is it possible that the transformers are less sample efficient than LSTMs and are just under-trained?

We believe this is unlikely. Prior work (Deletang et al., 2023) shows that 1M training steps are sufficient for learning a wide range of formal languages. In our experiments, convergence typically occurs well before this point. Additionally, we find that minor architectural changes (e.g., constraining some attention heads to look only at the previous token) enable the same training setup to achieve perfect generalization on certain tasks outside $\\text{PFO}^2[<]$.

Why do you only consider 3 languages for the language modeling experiment? Especially because the "failing" language still achieves 98.3% accuracy

We focus on language recognition (LR) because it is a strict subtask of language modeling (LM): to correctly predict the next token, a model must first determine which language the prefix belongs to. Therefore, failure on LR already implies failure on LM. Our LM experiments primarily serve to demonstrate that transformers can correctly track the state of the prefix and generate only permissible symbols.

Since transformers have already been shown to fail at recognizing languages outside $\**PFO**^2[<]$, we do not expect them to model such languages either. Accordingly, we choose the simplest such language, RDP-1, as a counter-example.

Note that some languages, such as $\\Sigma^*b$, are unsuitable for language modeling because any next token is valid at any step, making next-token prediction uninformative.

As for the seemingly high accuracy ($98.3\\%$), this is due to the structure of the languages. For instance, in RDP-1 $(\\Sigma\\setminus\\{b\\})^* a (\\Sigma\\setminus\\{a,c\\})^*$, any symbol except $b$ is correct before the critical $a$ appears. This allows the model to make many "easy" correct predictions, inflating its token-level accuracy. However, as with LR, any accuracy short of $100\\%$ indicates failure. The key failure mode is clearer when analyzing the model's internal states: on RDP-1, the prefix states are not distinguishable by their representations, in contrast to LDP-1 and LDP-2, where transformers successfully track the DFA states.

The PFO2 upper bound proof makes sense... but I'd like more detail on the following: "it reduces to a sum of a bounded number of terms..." The proof needs more detail.

The key is that fixed precision limits the number of non-zero attention weights. This puts a bound on the number of summed terms. Moreover, since each of these terms is drawn from a finite set $\\mathbb{F}$, the total number of possible combinations and their resulting sums is also finite. For example, if at most two values from $\\mathbb{F} = \{1,2\}$ are summed, the possible sums are $1$, $2$, $1+1$, $1+2$, $2+2$, with the last two exceeding the representable range and causing overflow.

"Uniformly attend to positions m < n where [...]" We cannot uniformly attend to all $m < n$ satisfying a condition when too many positions satisfy it under fixed precision. This is why we need two attention layers in Lemma B.11.

We again thank the reviewer for their careful reading, constructive questions, and generous evaluation. We will incorporate all suggested clarifications to strengthen the presentation and position the work more precisely within the broader landscape.

References

• Huang et al. (2025). A Formal Framework for Understanding Length Generalization in Transformers.
• Deletang et al. (2023). Neural Networks and the Chomsky Hierarchy.

We thank the reviewer for their thoughtful and encouraging feedback. We are especially grateful for the recognition of the clarity of our writing, the strength of our theoretical characterization, and the value of the empirical results.

We agree that both positional encodings and CoT reasoning are important and exciting directions for future work. We believe that our results on barebones transformer models provide a solid foundation for pursuing these lines of research.

Regarding the reviewer's question about positional encodings: Yes, the separation results do hold even when positional encodings are included. In our preliminary experiments, we explored both absolute (sinusoidal) and relative (rotary) positional encodings. We found that neither variant improved performance on the languages outside $\**PFO**^2[<]$.

We thank the reviewer for their thoughtful and constructive feedback, and for their positive assessment of the technical contributions, clarity of exposition, and the paper’s overall value. We are particularly grateful for the recognition of our novel characterization, the simulation of the past operator, and the experimental validation through length generalization. Below, we respond point-by-point to the reviewer’s comments and suggestions.

While I agree with the authors' claim that this work is a step closer to the formalization of real-world transformers..., the current introduction wording has the feel that the formal model used here has closed that gap.

We agree that there is still a gap between our formal model and real-world systems. That’s why we describe our model as an idealization. We thank the reviewer for pointing out that our wording may be misleading. In the final version, we will soften the language to clarify this point.

It does appear odd for a position to not pay attention to itself... Position encodings are always used... layer normalization discussion is partial... no mention of residual stream...

These are valuable observations. We respond to each below:

• Strict masking: Due to the residual connections, the current token still has access to itself through the residual stream. This offers intuition for why strict masking does not remove information.

• Positional encoding: Together with prior work, we establish that positional encodings largely play the role of numerical predicates in formal logic. Nevertheless, we agree this connection is not sufficient on its own, and we hope to investigate more precisely what numerical predicates commonly used positional encodings correspond to in future work.

• Residual connection: Residual connections are present in our model and used critically in the proofs in Appendix B.3. They ensure that earlier logical dimensions are preserved across layers, which is key to simulating complex formulas. We will make this clearer in the main text.

• Layer normalization: We now provide a more concrete example to support Proposition B.12:

  Suppose we have two dimensions, encoding $\\pi_a$, $\\pi_b$, and $\\mathbf{P} \\pi_a$, respectively. Inputting the string "ab" produces: \\begin{matrix} 1 & 0 \\\\ 0 & 1 \\\\ 0 & 1 \\end{matrix}

  These column vectors have different means and variances, and applying LN would distort their encoding. To neutralize this, we introduce a mirror dimension for each original dimension, giving: \\begin{matrix} 1 & 0 \\\\ 0 & 1 \\\\ 0 & 1 \\\\ 0 & 1 \\\\ 1 & 0 \\\\ 1 & 0 \\end{matrix} where the last three rows are mirror dimensions. Now, each position (column vector) has mean $0.5$ and variance $0.25$. By setting $\gamma = \\sqrt{0.25 + \\epsilon}$ and $\\beta = 0.5$, we cancel out LN entirely. This trick ensures that LN is an identity function and has no effect on the content.

  In the reverse direction, simulating transformers using logic, fixed precision makes the simulation of any positionwise deterministic function straightforward: we simply enumerate all possible inputs and outputs. Both layer normalization and residual connections fall under this class.

UHA more powerful than soft or average attention is counter-intuitive; average-hard and soft attention being essentially identical is also counter-intuitive.

We agree this may seem counterintuitive. However, there is empirical evidence supporting these theoretical findings:

• On UHA, Selim et al. (2025) show that it is specifically rightmost UHA that is more expressive than soft attention. This aligns with prior empirical efforts to inject recency bias, where the rightmost token is preferred in case of tie scores, using special attention mechanisms (Alon et al., 2024) or relative positional encodings (Su et al., 2021).

• On AHA vs. SA, our preliminary experiments show that if a transformer is trained with SA and annealing, and then tested with AHA, performance often matches or exceeds the performance of models trained and tested with SA. This supports the theoretical equivalence between SA and AHA.

... it is possible -- in principle -- that your trained transformer models... need to run on larger hardware / higher precision chips in order to solve inputs of size 500.

In fact, if you take any classic textbook algorithm and implement it on a fixed-precision hardware, it will likely fail... Should we then conclude that the textbook algorithm... is not solving the problem?

Our theory shows that for any language definable in $\**PFO**^2[<]$, we can construct a transformer (textbook algorithm) that computes the correct classification for every input length, under fixed precision. In contrast, no such transformer exists for languages outside this class. Our work thus identifies an exact boundary of what can be reliably encoded and generalized within a fixed‑precision transformer, distinct from cases where success depends on increasing precision.

That said, we fully acknowledge that different implementations, precision, or hardware architectures may yield different empirical outcomes. Our results do not preclude the possibility that one could train a transformer to generalize up to length 500. Nevertheless, we find it encouraging that models trained under the standard framework and hyperparameters from Deletang et al. (2023) and Butoi et al. (2025), without any special tuning, task-specific adaptation, or architectural modifications, exhibit generalization behavior that aligns closely with our theoretical predictions.

I don't particularly see an issue with ... the model could have access to higher precision arithmetic, or something that scales with input size.

Models are trained and deployed under fixed precision, and it is infeasible in practice to dynamically increase numerical precision at inference time when longer inputs are encountered. That said, we agree that logarithmic precision or any growing precision is a worthwhile setting to explore. It offers insights into what transformers can recognize when input lengths are constrained, which is often the case in real-world applications. However, interpreting log-precision results in this way implicitly relies on uniformity assumptions that a single set of parameters should work for all input lengths below a certain bound. To our knowledge, these questions remain under-explored and represent an exciting direction for future research.

We thank the reviewer again for the helpful suggestions and positive evaluation. We will revise the introduction, clarify our assumptions, expand the discussion on residuals and normalization, and incorporate further context to strengthen the positioning of our results. We appreciate the opportunity to improve the paper and clarify its contributions, and we are encouraged by the reviewer’s support for publication.

References

• Selim et al. (2025). Unique Hard Attention: A Tale of Two Sides.
• Alon et al. (2024). Scaling Stick-Breaking Attention: An Efficient Implementation and In-depth Study.
• Su et al. (2021). RoFormer: Enhanced Transformer with Rotary Position Embedding.
• Deletang et al. (2023). Neural Networks and the Chomsky Hierarchy.
• Butoi et al. (2025). Training Neural Networks as Recognizers of Formal Languages.