- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper shows theoretically that regular transformer eventually fail on the copying task as the length of the sentence to copy increases. This is especially true when the sequence to copy has repeated strings of characters. They introduce a new form of positional encoding, which seems to perform better empirically on the copying task.
Critical strengths
Copying has been a topic of interest in the past years, with several papers addressing the capability of transformers on this task. As such, the chosen topic is relevant for the community.
Critical weaknesses
One main weakness is the lack of discussion of related works. Both [1,2] for instance already discuss the limitations of fixed precision transformers on the copying task, with [1] focusing on repeated strings of characters which is precisely what is done in this paper. I would encourage the authors to distinguish their work from those previous works.
Second, the proof of Theorem 3.4 seems straightforward: If positional encoding has bounded outputs with finite precision, it can only have finitely many values. As such, when the sentence length becomes too long, a transformer cannot distinguish between similar sentences. The current presentation makes the proof appear much more complicated than it actually is. Notably, this proof seems to also directly apply to the class , making the new introduced class vacuous from a theoretical standpoint. Finally, Theorem 3.8 shows a positive result for the new class . However, it is not clear why this positive result would not hold for regular transformers as well.
In conclusion, the paper provides no justification for the novelty of its work nor the relevance of its theorems, and the proof strategy seems quite straightforward.
[1] Transformers need glasses! Information over-squashing in language tasks, Barbero et al, NeurIPS 2024
[2] How Many Different Outputs Can a Transformer Generate?, Meyer et al, ICML 2026
Questions for authors
Can you please compare your work to those mentioned in the weaknesses?
Am I correct in my description of the proof strategy? And if yes, why couldn't theorem 1 apply to T_{VO} and conversely theorem 2 apply to regular transformers? (I understand the precise bounds might change when changing class, but the same type of result should be recoverable).
3 comments
I apologize to the authors for my initial review, which is harsher than the paper deserves.
The authors have two results.
Regarding the positive result: There is already a positive result from Jelassi et al, where the required size of the transformer depends on both the longest n-gram and the size of the sentence to copy. As far as I understand, the main contribution of the authors is to remove the dependency on the size of the longest n-gram (and maybe tighten the size of the transformer?)
Regarding the negative result: As I understand it, the result from Barbero et al could be extended to a negative result with the same flavour as that in this paper: if they show that a transformer with fixed depth D and precision p fails at copying sequences of length f(D,p), couldn't you easily transform this in failure for sequences of length N if both depth and precision do not scale quickly enough? The main difference of the negative result of this paper is that it is stronger. However, this may not be that interesting to the community as a failure on copying remains a failure on copying, and how bad this failure is might not be of much interest.
I feel like the connection to both those previous work in particular is still under-discussed in the paper. I look forward to seeing the authors response.
Thank you for taking another look at the paper. We address your follow-up questions:
Positive result and scope of contribution. Yes, removing the restriction on repeated -grams is a central conclusion, but not our only contribution. This regime is much more challenging, as allowing arbitrary repetition fundamentally changes what the model has to do. In Jelassi et al., a unique -gram tells the model where to look; hence, their Hard-ALiBi model uses "local content hashing". Once -grams repeat, such a hash does not uniquely identify the next token. On all-identical strings, the model can't even decide when to stop, leading to the failure patterns seen in frontier LLMs and the baseline PEs in synthetic experiments.
Both our theoretical results are really motivated by this separation between content hashing and our proposed position hashing. The negative result formalizes the hardness beyond Hard-ALiBi, to all ECB models including both Hard-ALiBi and NoPE. And by identifying the two-layer VO construction, we also formalize how position hashing can actually be expressed through a transformer architecture in a practical (similar to RoPE / RoVE), learnable, and even length-generalizable sense.
Prior work also corroborated (under different models) that allowing repetition does qualitatively change the hardness of copying: for example, Huang et al. (2025) showed periodic and local Limit Transformers can express what they call "unique copy", but cannot copy arbitrary strings. We would describe our contribution as formally characterizing the source of this difficulty under a suitable expressivity model, and presenting a viable workaround, not only the construction itself.
Negative result. We agree that our result, on a fixed model when letting input length grow, is indeed similar to the conclusion of Barbero et al.. But their result does not give a uniform failure criterion, as needed for negative results in expressivity: e.g., to show copying is hard for ECB models, one would show no such model can correctly copy all source lengths . In particular, one needs to rule out all models of different parameter weights simultaneously, for the same architecture and the same bound on precision and depth (since we go further and show that width also does not matter). This makes the scale of our negative result quite different from Barbero et al.
Moreover, our result is more quantitative. The point is not how badly copying fails; it is that ECB models fail even with arbitrary width, small polynomial depth, and near-logarithmic precision (Corollary 3.5). This quantitative dependency is important to our understanding of the problem. Since real-world models run on very low precision and practitioners need to balance the different resources, a quantitative result can help us understand what the fundamental dependency on each resource (width, depth, precision, etc.) for this task is. This is similar to how people give space / time complexity analysis for algorithms separately and quantitatively, and indeed the dependencies are often different depending on the type of resource, as we also show.
Finally, a quantitative negative result can also contrast sharply with what is actually needed for copying, as shown in the VO rotation construction. This also demonstrates the power and limitations of certain positional encodings in a more concrete way.
Thank you for the questions, and we will make the connection to both prior works more explicit in our next revision.
Thank you for your feedback. We address your comments below and describe the changes in the revised manuscript.
Related work
We added both comparisons to Related Work in the revised manuscript. Barbero et al. (2024) study copying and counting under repetition and prove, for a fixed model under positional decay, that appending another copy of the final token makes arbitrarily little difference to the last-token representation as length grows. We instead prove exact bit-for-bit equality above an explicit, width-independent threshold under rounded left-to-right accumulation, allowing depth and precision to grow with N.
Meyer et al. (2026) count targets reachable by a fixed model from some prompt, and one of their arbitrary-prompt-length bounds (Appendix E) assumes stability to limited token deletions and duplications. We derive invariance to extending a terminal run from the attention computation and use it to show a termination failure on the prescribed copying prompt.
Clarification of proof strategy and scope for both theorems
Sorry for the confusion. Our argument is not a simple application of the pigeonhole principle. This is precisely why we have a negative result for ECB but a positive one for VO, even though the former is allowed arbitrary width and much higher depth and precision.
Finitely many values alone might give only repetition, not saturation; for example, finitely many positional values can keep cycling, while still being able to distinguish adjacent tokens. In our saturation argument, however, we claim that appending an additional identical token after a certain point makes no difference to the next-token logits of an ECB model. On the same prompt, the last copy step and the stop step get bit-identical logits, so the model cannot tell whether to keep copying the same token or output EOS instead.
A naive counting argument, which counts the entire token states, can only give a bound that grows with width, since a d-coordinate state has up to 2pd possible encodings. In contrast, our impossibility theorem applies to ECB models with arbitrary width. Once the run is long enough, one more copy of the token adds another copy of the same term to each attention sum. Consider a coordinate that takes the most additions to stop changing. It takes on a new value at every step until the whole vector stops changing. Since that coordinate has at most 2p possible values, the full state vector visits at most 2p distinct states, regardless of width. In a word, this is a uniform upper bound for all embedding dimensions, arising from the fact that the dimensions cannot be used together in a clever way in ECB models.
The other side of the story explains why this negative result does not carry over to VO models, and why we have a positive result instead. If a query at t attends one-hot to a delimiter at j, ordinary attention returns the fixed value vj, while a VO head instead returns Rqt−jvj in exact arithmetic. This allows us to explicitly encode different, well-defined information across coordinate pairs. Concretely, in our construction, each prime-period VO head uses a pair of value coordinates to encode the delimiter-relative offset of a token modulo its prime q (using exact modular indices). With unrotated values, that same delimiter lookup returns only the same vj without the offset, and at VO's two layers and O(loglogN)-bit precision, Corollary 3.5 rules out any NoPE copier at any width.
Meanwhile, the VO heads can encode this offset information with near-optimal efficiency, using O(loglogN) precision and O(loglogNlogN) width, so only O(logN) bits in total for an offset up to N -- maybe this inherent limit is closer to what a naive counting argument would predict. In short, VO uses the embedding dimensions near-optimally, while ECB essentially fails to exploit a wider embedding space.
Contributions in addition to theory.
On top of our theoretical contributions, our synthetic experiments also show that trained models can exploit the same prime-period VO encoding we constructed. They achieved perfect exact-copy accuracy at the evaluated training lengths and length-generalized with near-perfect accuracy up to the CRT period product. Larger transformers with standard positional encodings still lost accuracy under repetition. After submission, we ran a new control with the same backbone and periods. Q/K scored 0% on teacher-forced exact copying at length 2,000, versus 100% for VO, despite receiving more optimizer updates.