We sincerely thank the reviewer for their thoughtful and constructive feedback. We greatly appreciate your careful reading and insightful suggestions, which have helped us clarify key aspects of the paper. Below, we respond point by point to the concerns raised.

Weaknesses

1. Inprecision of definition of Transformer, unclear symbol in definitions

• We acknowledge that our definitions of Transformer components, as well as our explanations for some symbols (e.g., $\sigma$, <sep>), were insufficient. We appreciate the reviewer pointing this out, and we will revise all relevant parts of the manuscript to provide more precise and consistent definitions throughout.

2. The validity and importance of Assumption 5.1

• validity
  • We agree that Assumption 5.1 may not always hold—particularly in low-bit settings. However, our intention was to model more typical settings found in practical scale models such as BERT or LLaMA, where floating-point precision (e.g., FP16 or FP32) is generally sufficient.
  • In cases where precision is severely limited, we expect this assumption to break down, which is precisely why we chose to state it explicitly as an assumption.
• importance
  • The reviewer notes that a Transformer without positional encodings and with fixed-precision arithmetic yielding only finite or cofinite languages may appear somewhat expected. However, this outcome does not follow from those conditions alone. As shown in Table 1, even under fixed precision and NoPE, the expressivity exceeds FinCofin unless Assumption 5.1 is also imposed. With this assumption, the expressivity becomes exactly FinCofin, both as an upper and lower bound.
  • In this sense, Assumption 5.1 plays a critical role in identifying a tight boundary on expressivity. We view our contribution as providing a theoretical grounding for how fixed-precision constraints shape the model’s representational limits and establishing FinCofin as the precise limit under minimal yet meaningful assumptions.

Question for Authors

1. (Clarification) Absolute positional embeddings

• In our setting, we treat APE as a function of the form $\mathrm{APE}: \mathbb{N} \to D_p^d$ which maps each position to a $d$-dimensional vector in fixed-precision float. This encoding is added element-wise to the token embedding before being passed into the Transformer block.
  • Note that under this definition, learnable positional embedding, such as those used in GPT-2—are considered a subclass of APE. We will revise the manuscript to clearly include this definition.

2. (Clarification) Transformers which contribute to the lower bound

• We describe the architecture used to establish the lower bound in Section 4.4. This includes the model’s structure and computational setting. (please ignore "and attention head" in line 189)
• If there are specific aspects that were unclear or insufficiently detailed, we would greatly appreciate your guidance on which parts should be clarified. We are happy to revise the manuscript accordingly.

3. Theorem 6.1 will be exclued

• We sincerely thank the reviewer for raising this important issue. We agree that the current proof sketch for Theorem 6.1 lacks sufficient formal detail, and that the argument, as presented across Section 6.1, does not aid comprehension.
  • Due to time constraints during the submission process, we included only a high-level idea without a fully formalized proof.
  • We found that the lower bound for APE is, in fact, no stronger than that for NoPE under our current assumptions. While a tighter lower bound may exist, it likely requires a different construction and falls outside the scope of this work.
• Accordingly, we plan to exclude Section 6.1 entirely from the final version. We will instead mention this direction briefly as a possible avenue for future research. We believe this change will improve the overall clarity and integrity of the paper.

Summary

• Once again, we are grateful for your detailed review and recognition of the core contributions of our work. We believe the revisions we plan to make based on the comments. Particularly regarding the clarity of definitions, the role of key assumptions, and the exclusion of Section 6.1.
• Please feel free to let us know if there are further points that would benefit from clarification.

Thank you very much for your detailed and thoughtful review. We are encouraged by the recognition of key strength and we appreciate the thoughtful suggestions for improvement. We greatly appreciate your recognition of the strengths of our work, as well as your thoughtful suggestions for improvement.

Weaknesses

1. On the lack of explanation for FOC[+; MOD] and related language classes:

• We agree with the reviewer that Table 1 refers to FOC[+; MOD], but the manuscript does not include even a brief explanation. This is an important oversight, especially for non-experts. We will revise the paper to include concise definitions and necessary backgrounds so that the impact of our results can be better understood. Thank you for pointing this out.

2. On the applicability of our results to more realistic Transformer architectures (e.g., with learnable PE or RoPE):

• We address this concern in more detail under the “Questions for Authors” section below.

3. On the practical relevance of our conclusions, especially with respect to generalization and emergent capabilities:

• As also noted in our response to Reviewer Je32, we acknowledge that the term “lookup table” was overstated. While valid in a theoretical sense under fixed precision, it does not fully capture a model’s generalization capacity. We view expressivity and generalization as distinct: even under strict constraints, a model can still generalize within its representable class.
• Although our results do not directly explain emergent behaviors in large-scale Transformers, they provide a foundation for understanding expressivity under resource constraints—an important step toward formalizing learnability. We hope our simplified framework helps clarify how architectural choices affect expressivity and contributes to bridging theory and practice.

Other Comments Or Suggestions

• We also thank the reviewer for pointing out minor typos and expressions a lot that could be improved.

• l.165: Given that GPTs use causal attention, should it be "Since decoder-only Transformer" instead of "Since encoder-only Transformer"?

  • As noted in our response to Reviewer Je32, our intention was indeed to contrast the decoder-only setup with encoder-based models, but the sentence as written was confusing. We will revise the text to clarify our intended meaning.

Questions For Authors

1. The effects of positional encodings for the permutation-invariance of attention modules

In practice, most transformers make use of positional encoding, either deterministic or learnable or more complex ones (ROPE). How would the insights translate to such a model given that they can mitigate the permutation-invariance of attention modules?

• We appreciate this important question regarding the extension to more realistic positional encoding schemes. In fact, learnable positional encodings were implicitly treated in our framework as a form of absolute positional encoding (APE). In the manuscript, we focused on periodic APE as a representative idealized case.
• As for RoPE, it introduces a structurally distinct behavior compared to NoPE and APE. Although a detailed analysis of RoPE is outside the scope of this work and would require separate treatment, we are also interested in this direction and plan to investigate RoPE-based architectures in future work.

2. Decoder-Only Transformers and Expressivity

Same question for transformers used in practice, notably in language tasks, that use causal attention in decoder-only blocks.

• Regarding decoder-only architectures, our setting assumes $\Omega(1)$ decoding steps. Therefore, our results apply to any number of decoding steps that scale with the input length.
  • Importantly, our results show that in fixed-precision settings, the number of decoding steps does not affect the model’s expressivity.
  • In this context, causal attention enables NoPE Transformers to infer the relative positions of input tokens, partially compensating for the lack of explicit positional encodings.
• That said, we recognize that generalizing our results to broader architectural variations remains a challenging and important direction. In future work, we hope to extend the framework to cover other types of positional encodings and as well as additional architectural features such as sparse attention or grouped-query attention.

Summary

• We again thank the reviewer for their thoughtful feedback—including the helpful identification of typos, and kind recognition of our work’s strengths. Your comments have helped us improve both the clarity and positioning of our contributions.

• While our setting is simplified, we believe it offers a useful foundation for understanding expressivity under resource constraints, and we will revise the manuscript to better explain technical details and clarify connections to practical models.

We are grateful to the reviewer for the constructive and insightful feedback.

Weaknesses:

We thank the reviewer for pointing out the apparent contradiction between our claim ("fixed-precision Transformers behave as efficient lookup tables") and the observed generalization in experiments. We acknowledge that the phrase "lookup table" in the abstract may have been misleading. Our intent was to highlight theoretical limitations under fixed precision, not to imply literal memorization. Our analysis suggests that when precision is insufficient, fixed-precision Transformers cannot approximate the infinite-precision behavior seen in prior work. While we did not fully address what constitutes "sufficient" precision in the current manuscript, we plan to explore this in future work, as the reviewer helpfully suggested.

Although it may seem trivial, our contribution is to understand how architectural choices within the Transformer family influence the classes of languages that can be represented—even under the same finite-precision assumptions as a boundary analysis that explicitly identifies how changes—such as removing or adding architectural components—impact expressivity.

Clarifications

We thank the reviewer for these helpful clarification requests. Below, we address each of the reviewer's questions in turn.

1. Line 142 - Special values in floating-point numbers:

   • Any other special values except $+\infty$ and $-\infty$?
     • In our manuscript, we only intended to refer to the explicitly mentioned values: $+\infty$, $-\infty$, and $\mathrm{nan}$.
   • Within the scope of our theoretical setting, NaNs arising from division in the softmax are excluded by Assumption 5.1. However, we acknowledge that other operations (e.g., $0 + \infty$, $0 \times \infty$) may also result in NaNs and should be mentioned explicitly. We thank the reviewer for bringing this to our attention.

2. Line 140 - Clarification of the phrase, "there is no intersection to alphabet in this study":

   • What we intended here is the condition $\Sigma \cap \mathbb{V} = \emptyset$, meaning that the set of special tokens does not intersect with the standard alphabet.
     • This restriction was made for clarity: special tokens have distinct roles — e.g., <eos> as an acceptance marker, <sep> as a separator—and keeping them disjoint from the alphabet avoids ambiguity in our definitions.

3. Line 231 - Assumption 5.1 “holds for most trained transformer models” – why “most” and not “all”:

   • This statement refers specifically to the inner product $q(x)k(y)^\mathsf{T}$ for all token pairs $x, y$. While $q(x)$ and $k(y)$ are practically finite in real-world models, it is difficult to make a definitive claim about all possible products.
     • Categorically asserting this assumption would require making claims about learned parameters, and we cannot theoretically rule out the possibility that training may produce pathological configurations.
   • Furthermore, violations of this assumption could lead to degenerate behaviors such as attention masking or unique hard attention. In contrast to soft attention—where weights are smoothly distributed—hard attention focuses all weight on a single token. Given prior literature, we believe it is important to distinguish soft attention from such extreme cases.

Question For Authors

Does your result subsume the results on C-RASP or AC0? Or is the formalism different?

• We thank the reviewer for this insightful question, which touches on the relationship between our results and prior work on formal characterizations of Transformer expressivity, particularly in the context of C-RASP and AC0.

  • Regarding C-RASP, we are aware that the class FOC[+; MOD] is strictly weaker than C-RASP, as discussed in [5]. As we mentioned at table 1, FOC[+; MOD] is one of the upper bound of the expressivity of fixed-precision Transformer models with Absolute PE ([7] Theorem 2, [5] Lemma 6.1, Theorem 7.1)
    • Therefore, while our formalism differs, we believe our focus on the weakest setting are complementary.

• As for AC0, we thank the reviewer for introducing [6], which we were not previously aware of.

  • Their framework, CoT[T(n), d(n), s(n)], characterize expressivity based on decoding steps, embedding size, and precision. While they analyze cases like CoT[log n, poly(n), 1] $\subseteq$ AC0 (Theorem 3.1), our setting corresponds to CoT[T(n), 1, 1], which is not covered in [6]. We show that this setting has expressivity exactly FinCofin — likely strictly weaker upper bound than the classes discussed in their work. Importantly, we also provide a lower bound, which they do not.

Summary

We thank the reviewer again for their insightful feedback, which has helped improve the clarity and focus of our work. We hope our responses adequately address the concerns, and we will incorporate the necessary revisions in the final version.

We greatly appreciate the valuable comments provided by reviewer Je32.

Weakness: rigorous of proofs

We agree with the reviewer’s concern regarding the rigor of our proofs. In the current manuscript, we prioritized clarity of explanations. However, we also acknowledge that the proofs are not sufficiently rigorous in the current form. Thus, we fully intend to include additional proof details and supplementary lemmas —particularly in Section 6— in the final version. These additions will ensure that the mathematical rigor meets the standards expected by the community.

Questions For Authors

1. Line 165 – Mention of Encoder-Only Transformers:

Line 165: why mention encoder only transformers here, which are not the object you study (decoder only transformers)?

• Our intention in mentioning encoder-only Transformers was to highlight that even in a decoder-only setting (particularly when using NoPE), positional information is implicitly captured through causal masking [1]. The contrast with encoder-based models was intended to underscore our motivation for adopting NoPE.
• We will therefore revise the text to explicitly clarify our rationale. We sincerely thank the reviewer for bringing this to our attention.

2. $\sigma$ in Definition 4.2:

Is sigma the input in definition 4.2? If so, should it have a time superscript?

• We acknowledge that we omitted an explicit statement clarifying that $\sigma \in \Sigma$. We thank the reviewer for pointing out this oversight and will clearly specify it in the revised manuscript.

• Regarding the suggestion to use a time superscript, we apologize but did not fully understand the reviewer's intent. If the reviewer was referring to a notation like $\sigma_{1:t}$, we would like to clarify that our current definition is intentionally formulated so that such notation is unnecessary, as the autoregressive nature of the definition implicitly encodes this temporal dependency. However, if we have misunderstood the reviewer's suggestion, we would greatly appreciate further clarification.

3. Assumption 5.1 vs. Lemma 5.3:

Assumption 5.1 mentions plus or minus infinity cannot be reached, but the proof of Lemma 5.3 mentions that positive infinity is reached, and it uses Assumption 5.1. This seems contradictory, maybe it's a typo in the assumption.

• Assumption 5.1 asserts that $qK \neq \pm \mathrm{inf}$. Thus, the divergence of the sum $\sum \exp(qK)$ to positive infinity does not contradict this assumption.

4. Lemma 5.3 - the final token's contribution:

In Lemma 5.3, if “the final token’s contribution vanishes”, then why is it important to have the same final character for w and w’?

• The phrase “the final token’s contribution vanishes” was indeed a misstatement. Our intended claim was that the contributions of all tokens except the final token vanish. We sincerely thank the reviewer for highlighting this error, and we will correct the statement in the revised manuscript.

5. Line 328 - mistake:

Line 328: I think “lower” not “upper” bound is meant.

• We agree with the reviewer’s observation that “lower bound” is the appropriate term. This error will be corrected in the revised version. We appreciate the reviewer pointing this out.

Summary

Overall, while the current manuscript prioritizes clarity and simplicity in its presentation, we will carefully incorporate the reviewer’s suggestions, including the mentioned clarifications and additional proof details, to enhance the rigor of our work. We sincerely thank the reviewer once again for these insightful and constructive comments, which have significantly helped us improve the quality of the paper.

We hope that our responses sufficiently address the reviewer’s concerns and clarify the contributions of our work. Please let us know if any further details or clarifications would be helpful.