acceptodds
Under review as a conference paper at ICLR 2027

Complexity-theoretic tradeoffs between precision and expressivity in transformers

Abstract

A common technique to accelerate inference and reduce the memory costs of transformers and related models is to restrict to low-precision weights and arithmetic. On the other hand, doing this could reduce the expressive power of the model, but the extent of this phenomenon remains poorly-understood. In this paper, we demonstrate a fine-grained theoretical tradeoff between expressivity and precision: For every we exhibit a function which tests equalities, and prove that a one-layer softmax transformer can compute , with bits of precision, but not with bits of precision. Equality testing arises, both explicitly and implicitly, in many tasks that transformers are expected to perform, and our results show it is particularly sensitive to model precision. Our proofs combine explicit finite-precision transformer constructions with communication-complexity lower bounds, yielding a tight “one-bit” threshold.

Primary area:
learning theory
Keywords:
precision, lower bounds, expressivity, communication complexity, transformers, quantization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_qBazOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies precision–expressivity tradeoffs in single-layer Transformers with one attention head and value dimension one, followed by a ReLU MLP, without residual connections, layer normalization, or CoT. Besides, primitive operations are rounded, accumulations are left-associated, and value projection precedes attention aggregation. Its main result establishes a tight pp-versus-p−1p-1 separation for p>2p>2 under this special setting.

Critical strengths

The paper presents a clean precision threshold, though under a quite special setting and for a quite special function.

Critical weaknesses

My main concern is thus the limited generality of the contribution, which limits the practical relevance/implication of these theoretical results.

Questions for authors

What is the generality of these techniques? Do they apply to broader setting?

4 comments

We thank the reviewer for their thoughtful comments regarding the generality, practical relevance, and architectural assumptions of our results. We address these concerns below.

Generality and practical relevance: Understanding the expressivity of a single attention layer is fundamental to identifying which computational capabilities are intrinsic to attention itself and which require deeper architectures. Furthermore, we have now generalized our results to arbitrary value dimension dvd_v and number of attention heads HH, establishing tight precision thresholds and substantially broadening the scope of our theoretical results.

Regarding practical relevance, empirical studies have already observed substantial performance degradation under aggressive quantization, including on reasoning tasks [1]. Our work provides a theoretical understanding of how precision-dependent expressivity limitations can arise, rather than claiming to fully characterize these practical settings.

Architectural assumptions and CoT: Chain-of-thought reasoning is a complementary approach that provides additional sequential computation. Our goal, however, is to understand the intrinsic expressive power of transformer architectures under bounded precision, independently of additional computation through CoT. We believe isolating these capabilities is an important step toward understanding how precision, width, and depth interact.

We hope these clarifications and our new generalizations address the reviewer's concerns and better highlight the significance of our theoretical contributions.

[1] Liu et al., "Do Emergent Abilities Exist in Quantized Large Language Models: An Empirical Study," 2023. https://arxiv.org/abs/2307.08072

Thanks for the responses. I remain concerned about the generality and practical relevance of the results. The analysis focuses on single-layer Transformers without CoT. It also relies on specific architectural/computational assumptions, such as no residual connections, no layer normalization, and applying value projection before attention aggregation. I keep my score.

Thank you for the follow-up. Our objective is to isolate the intrinsic expressivity of a single attention layer under bounded precision. Such isolation is widely studied in the literature, as we discussed in our introduction. We clarify the distinctions between the assumptions mentioned:

  • CoT and related strategies: CoT augments a model with additional inference-time computation; other examples include repeated model application/looping, beam search, etc. These strategies can be applied across different model architectures and are not specific to attention. They address how a model is used during inference, whereas our work isolates what a single attention layer can compute under bounded precision.

  • Residual connections: Residual connections are used empirically to improve gradient flow and stabilize training. This can be simulated within the attention-based framework using an additional attention-head [2].

  • Layer normalization: When applied after attention at the readout, tokenwise normalization is local post-processing and cannot bypass the same communication bottleneck. Preserving the matching upper-bound constructions under normalization is a separate question.

  • Operation order: Applying value projection before attention aggregation follows the original Transformer formulation [1]. Different evaluation orders can produce different results under finite-precision arithmetic, making an explicit computational model necessary for exact one-bit separations. Our results characterize the stated model.

Overall, these decoding and inference-time strategies can be applied across different architectures and are not specific to attention. They address how a model is used and what additional computation it receives. Our work addresses the complementary question of what a single attention layer can intrinsically compute under bounded precision.

[1] Vaswani et al., “Attention Is All You Need,” NeurIPS 2017, Section 3.2.2.

[2] Sanford, Hsu, and Telgarsky, “Representational Strengths and Limitations of Transformers,” NeurIPS 2023, Section 2.1.

Thank you for your responses. However, my main concerns largely remain. I keep my score.

Reviewer_WmsVOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies how expressivity of 1-layer 1-head transformers with value dimension 1 depends on the number of bits of precision p. For the fixed precision format, a version of the equality problem (where one strings is promised be equal to the other one or precede it in the lexicographic order, and some bits are repeated) is proved to be doable with p bits and not with p - 1 bits, thus obtaining a separation for the corresponding hierarchy.

For the floating-point format, a version of equality is given which is not doable by p -1 bits for the standard transformer, but doable with p bits of linear-attention transformer, and slightly with about log p more bits of the standard transformer.

Critical strengths

The first work where such tight bounds on precision have been obtained. Upper bounds for the simplified version of the separation – p - 2 vs p bits is nice and understandable. It comes from the idea that in the simulation of the transformer by a communication protocol, Alice sends p bits for the numerator of the softmax, and p bits for its denominator. This is not enough to check equality for of two 2p-bit strings. So when we are proving the upper bound for slightly shorter string, we should really utillze the fact that the numerator and denominator have to carry p bits of information. The idea is the make the value of the fraction maximal possible when strings are equal – numerator maximized when their first halves are equal, denominator is minimized when their second halves are equal. The additional assumption that one string does not exceed the other string in the lexicographic order comes into play here.

Critical weaknesses

Probably, the lack of a new technique that has the potential to advance lower bounds for transformers. The lower bounds are immediate and use the standard reduction to communication complexity. The main technical contribution of the paper is the upper bounds. They seem to work; I did not check all the final details. The trick is nice, but honestly, the technicality of a rigorous proof outweighs the importance and interestingness of the result.

Probably would be more fair to state in the informal versions of your theorems that there is a single head and value dimension is 1; it looks at the moment as trying to hide it to make the result look stronger.

In Lemma 6, has g been defined before? I understand you are talking about equality here.

Questions for authors

don't really have one at the moment

3 comments

We thank the reviewer for their constructive feedback. We clarify our main contributions and the assumptions underlying our theorems below.

W1. Our main novelties are as follows:

  • Matching upper and lower bounds. While communication-complexity techniques for proving lower bounds are well known, it was not previously established whether such bounds are tight. Our technical upper-bound constructions establish tight precision thresholds.

  • Fine-grained precision–expressivity tradeoffs. We identify functions that exhibit sharp precision–expressivity tradeoffs. In particular, it is not obvious that reducing precision from pp to p−1p-1 bits strictly reduces expressivity for every pp, even when all model parameters can be adjusted.

  • The role of softmax normalization. Our constructions show that the denominator of softmax attention is not merely a normalizing term. Both the numerator and denominator can be independently exploited to encode information, allowing us to achieve an exact one-bit separation.

  • Generality across numerical formats. We show that similar equality-based functions exhibit precision–expressivity tradeoffs under both fixed-point and floating-point arithmetic. This suggests a broader research direction: characterizing which functions and precision regimes admit such sharp expressivity thresholds.

  • Extension to multiple heads and higher dimensions. We have further extended our results to arbitrary value dimension dvd_v and number of heads HH, establishing tight thresholds beyond the original single-head, scalar-value setting.

W2. We agree that the architectural restrictions are important. The theorem statements in the introduction are intended to highlight the main results without introducing all the technical parameters, which are specified in the formal statements.

We believe both results are of independent interest. First, we show that a simple, natural input representation already yields a nearly tight (two-bit) separation. We then show that a more elaborate representation can sharpen this to an exact one-bit threshold. The first result demonstrates that the tradeoff arises naturally, while the second establishes the precise threshold, which requires additional technical ideas.

Minor correction. We thank the reviewer for pointing out the undefined notation gg in Lemma 6, which we have corrected to EQm\mathrm{EQ}_m.

We hope these clarifications and our new generalizations address the reviewer's concerns and better highlight the technical novelty of our contributions. We thank the reviewer again for their valuable feedback.

Thanks for the response. Yes, I think I'm buying your point about showing the tightness of the communication complexity lower bound as of the lower bound method. Please make a point about it in the revised version. I'm not sure about the conceptual value of the denominator trick, but it is indeed nice. I decided to raise my score to 4.

Regarding W2 -- still, I strongly suggest you reformulate it. I think mentioning value dimension and the number of attention heads would not be too technical even for general ai conference public these days. In the current form, it sets up expectations too high and does not look faithful compared to the actual result.

Thank you for the follow-up and for raising the score. We appreciate the suggestion regarding the informal theorem statements and recognize that explicitly stating the architectural assumptions would improve clarity. We have therefore revised the statements to specify the number of heads and value dimension, while also highlighting our new generalizations to arbitrary HH and dvd_v. We have alsoadded an emphasis on the tightness of the communication-complexity lower bounds in the revised paper.

Reviewer_5FJDOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this work, the authors analyze the tradeoff between numerical precisions and the expressiveness of transformers, which is a popular and important area to research in this field. The authors build the lower bounds and the upper bounds based on the precision required for one-layer transformers to compute equality-testing functions. The result is tight down to one bit, which is that for some certain input representation (specially constructed), a one-layer transformer can compute equality using pp bits of precision but cannot do it using (p-1) bits. The lower bounds are built using communication complexity arguments, and the upper bounds are build using transformer construction. The authors continue their analysis to floating-point.

Critical strengths
  • This work can separate one bit effect on expressiveness for fixed-point transformers, which is a novel angle to work on expressiveness. The matching upper and lower bound provide a very precise understanding of how numerical precision affects the expressiveness of one-layer transformers.

  • The way of construction the lower bound and upper bound in this paper are inspiring to the community, which allows us to extend to other settings as well.

Critical weaknesses
  • Practical Transformer have more complicated setups, such as multiple layers, attention heads, and dimensional representations, where I think there are still some gap between this work's theoretical results to the practical setting.

  • the input representations are specially constructed, which invovles duplicated bits, padding tokens, and promise conditions for equality testing. It poses questions on how these results generalize to the practical setting.

Questions for authors

Q1: If we have a deeper or wider transformer, what will the precision-expressiveness separation look like?

Q2: How sensitive are the result to the choice of input representations, and can we observe them empirically?

2 comments

We thank the reviewer for their thoughtful comments and for highlighting these important questions about the generality of our results and the role of input representations. We address both points below and describe the new theoretical results added in response:

W1 and Q1. Although practical transformers have multiple layers, understanding the expressivity of a single layer is fundamental: this helps clarify which capabilities are intrinsic to a single block and which truly require multiple layers.

More importantly, we have now extended our results to arbitrary value dimension dvd_v and number of heads HH, establishing tight precision thresholds. This substantially broadens the generality of our results beyond the original single-head, scalar-value setting.

Extending such separations to deeper transformers is an important open problem, potentially requiring more complex functions than equality. However, proving lower bounds for multi-layer transformer encoders remains a major theoretical challenge; existing techniques have only established a multi-layer lower bound for a restricted decoder-only architecture.

W2 and Q2. Input representations naturally affect expressivity. For example, interleaving the strings as x1,y1,x2,y2,…,xm,ymx_1,y_1,x_2,y_2,\ldots,x_m,y_m can make equality computable with constant precision, even as low as 1. Our communication-complexity lower bound instead requires the xx-dependent tokens to precede the yy-dependent tokens, preventing local comparison of corresponding bits.

Importantly, our simpler, natural representation (Theorem 3) already yields a near-tight (two-bit) separation using a simple input representation. The modified representation with duplicated bits and padding is only needed to sharpen this into an exact one-bit threshold for theoretical importance of a perfectly tight result.

Thank the authors very much for addressing my concerns and questions. After careful considerations, I decide to maintain my score of 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.