acceptodds
Under review as a conference paper at ICLR 2027

Copying Under Repetition: From Prefix Matching to Position Hashing

Abstract

Frontier LLMs that copy random strings accurately can overrun or truncate long blocks of repeated characters. Repetition removes the local content cue that induction-style copying relies on, and what is left to resolve—which occurrence to continue from, and when to stop—is positional. Position can reach the output along two routes: through the attention weights a head places on value vectors it leaves unchanged, or through offsets written into those value vectors, which a later layer can read and retrieve with. We study this distinction in horizon-uniform copying, which requires one transformer to copy every string of length without parameters specialized to the realized length. Our value-side construction, VO-rotation with exact access to modular residues, copies every string of length for any fixed finite vocabulary and all sufficiently large , using two layers, prime-period heads, and -bit precision. The same retrieval rule selects the next source token and the end marker, handling arbitrary repetition and termination together. We also prove a width-independent saturation bound: in our finite-precision model, transformers whose only positional input is an eventually-constant additive attention bias fail on all-identical sources once their saturation threshold is . Across three training seeds, learned VO models copy beyond the training limit, with an accuracy transition near the product of their supplied periods, consistent with learned use of the modular representation. In contrast, standard positional encoding baselines lose accuracy under repetition near the training limit.

Primary area:
learning theory
Keywords:
Transformers, Positional Encoding, Copying, Finite-Precision Expressivity, Length Generalization

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ufb3OpenReview ↗
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 TVOT_{VO}, making the new introduced class vacuous from a theoretical standpoint. Finally, Theorem 3.8 shows a positive result for the new class TVOT_{VO}. 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

Thank you for your feedback. We address your comments below and describe the changes in the revised manuscript.

Related work

Can you please compare your work to those mentioned in the weaknesses?

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 NN.

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

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).

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 dd-coordinate state has up to 2pd2^{pd} 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 2p2^p possible values, the full state vector visits at most 2p2^p 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 tt attends one-hot to a delimiter at jj, ordinary attention returns the fixed value vj\mathbf v_j, while a VO head instead returns Rqt−jvjR_q^{t-j}\mathbf v_j 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 qq (using exact modular indices). With unrotated values, that same delimiter lookup returns only the same vj\mathbf v_j without the offset, and at VO's two layers and O(log⁡log⁡N)O(\log\log N)-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(log⁡log⁡N)O(\log \log N) precision and O(log⁡Nlog⁡log⁡N)O(\frac{\log N}{\log \log N}) width, so only O(log⁡N)O(\log N) bits in total for an offset up to NN -- 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.

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 nn-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 nn-gram tells the model where to look; hence, their Hard-ALiBi model uses "local content hashing". Once nn-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 ≤N\le N. 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.

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

This paper studies why copying fails on long runs of repeated tokens. In such runs, content matching cannot tell which occurrence to continue from or when to stop. The authors contrast two ways position can reach the output: through attention scores, as in RoPE and ALiBi, or through rotations of value vectors. They prove a lower bound for models whose only positional input is an attention bias that becomes constant at long distances, such as NoPE. Under finite-precision summation, these models cannot copy long all-identical strings and stop correctly regardless of width. They also build a two-layer model that rotates values with prime periods, called VO-rotation. It copies every string up to length NN with O(log⁡log⁡N)O(\log\log N) precision. In their experiments, standard baselines lose accuracy under repetition near the training length, and all of them fall below 0.7 on all-identical strings. Learned VO models can copy perfectly up to the training length and generalize to about 5000. Their accuracy drops after 5005, which is the product of the periods.

Critical strengths

The idea is simple and well motivated: writing each position's offset into the value vectors, so later layers know which occurrence was selected. The learned VO models give clear evidence that this works. All three seeds copy perfectly up to the training length of 2000 and stay above 0.95 mean accuracy through length 5000. Accuracy then drops sharply just after 5005, the product of the supplied periods, which is where the residues start to repeat. This matches the theory and suggests that the models really use the modular representation.

Critical weaknesses
  1. A major claim of the paper is that position reaching the output through value vectors works better than through attention scores for copying under repetition. However, this contrast is not fully established. The lower bound covers only attention biases that become constant at long distances, such as NoPE. It excludes RoPE and directly computed ALiBi, which are the main score-side examples in the paper. The most direct control would be a score-side encoding with the same prime periods as VO. The authors note that this comparison remains open, but I think without it, the contrast stays indirect.
Questions for authors
  1. The baseline models differ from VO in architecture, precision and training budget. ALiBi was trained for about 81k steps versus about 150k for VO. Could the authors train a score-side model, such as RoPE, with the same prime periods (5, 7, 11, 13), using the same backbone and training budget as VO? If it fails on repeated strings while VO succeeds, that would directly support the paper's central claim.

  2. (Clarification) The paper attributes score-side failure to identical value vectors across positions. But sinusoidal encodings still fail on all-identical strings while they already put position into the value vectors. How to explain this failure?

3 comments

Thank you for your feedback. We address your comments below.

Scope and same-prime comparison (W1, Q1)

Could the authors train a score-side model, such as RoPE, with the same prime periods (5, 7, 11, 13), using the same backbone and training budget as VO?

We ran the proposed control experiment by moving the Layer 1 rotations from V/O to Q/K. We kept the two-layer backbone, simulated FP8, rotary dimensions, training distribution, and periods 5,7,11,135,7,11,13 fixed. Both models trained on strings up to length 2,000. At that length, exact-copy accuracy was 100% for VO and 0% for Q/K in all three distributions and for all three seeds. We evaluated both models under teacher forcing.

Interestingly, on all-identical strings of length 2,000, Q/K predicted every copied token correctly on all 96 examples per seed but always missed EOS at the stopping step. In the length generalization tests (lengths from 2,008 to 5,000), Q/K still scored 0% in all three conditions. In contrast, VO averaged 98.0% on uniform-random, 99.6% on moderately repeated, and 99.8% on all-identical strings.

During training, Q/K did not reach the 10−410^{-4} smoothed-loss threshold, so cooldown began at the 150,000-update cap. Each Q/K seed completed 195,000 optimizer updates, compared with 148,200 to 158,200 for VO.

Standard RoPE and directly computed ALiBi fall outside the lower bound, as clarified in Section 3. The new control answers the placement question directly: with the backbone and periods fixed, Q/K did not match VO even with more training updates (Figure 4 and Appendix B).

Absolute sinusoidal embeddings (Q2)

sinusoidal encodings still fail on all-identical strings while they already put position into the value vectors. How to explain this failure?

Sinusoidal embeddings can give identical tokens different value vectors, so the identical-value argument does not apply. VO directly encodes the offset to the retrieved delimiter in the returned value. To use the same strategy with sinusoidal embeddings, the model would have to learn to recover that offset from absolute positions. That extra step may help explain why the sinusoidal baseline struggles under repetition.

Thank you for the new control and fig 4 shows a clear gap. But fig 5 and table 6 in appendix show that Q/K did not learn to copy.

Yes, as Figure 5 and Table 6 show, Q/K did not learn to copy reliably at the training limit, despite having the same backbone and prime periods and receiving more training steps. This supports our intuition that V/O makes the mechanism easier to learn. The V/O encoding also admits an explicit construction precisely because positional information enters the values directly. It is unclear whether a comparable construction is even possible with Q/K or, if it is, whether it can be learned with a comparable training budget.

We think there are two possibilities: either this is an inherent expressivity issue (as in NoPE), so that Q/K simply cannot solve the copying task at this scale with such a small model, or the correct way to use the encoding is much harder to learn in this setup. In any case, this gap already appears early in the training range, before length generalization can come into play.

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

The paper studies the theoretical question on how transformers are able to learn repetitions.

The question is set up motivated by current literature and the paper follows the literature by focusing on the positional encoding part. The paper formally distinguishes two types of transformers (i.e. ECB and VO) and formally proves that VO transformer well defined will not suffer from the vanishing signal effect in ECB and thus will have the capacity to achieve copy from repetition task with high accuracy.

In experiments, the paper studies whether the theoretical insights transform to learning scenarios. The paper shows that the VO transformer outputperforms not only ECB transformers but also other alternatives such as ROPE.

Critical strengths

By formally distinguishing different types of transformers, the paper proves the clear case that ECB is not able to copy arbitrary length of repetition strings. The paper also studies VO which seems a recent design that has better model capacity; the paper proves that this class of transformers mitigate such limitations.

The paper also presents convincing empirical studies to see if the theoretical capacity guarantee transfers into learning settings which further solidify the results.

Critical weaknesses

ROPE as a popular design does not fall into ECB or VO categories and I think the paper can make this more clear in the description (although it seems that the reasoning arguments (or maybe proof) can transfer into ROPE type of architectures as well).

Both the frequency setups as well as the value pathway seems to matter for VO model's success so it would be good to empirically see the ablations of the architectures.

Questions for authors

Compared to RoVE (García-Castellanos et al., 2026), are there archtectural difference for VO transformers?

2 comments

Thank you for your feedback. We address your comments below and describe the changes in the revised manuscript.

RoPE and proof transfer (W1)

it seems that the reasoning arguments (or maybe proof) can transfer into ROPE type of architectures as well

Neither the ECB lower bound nor the VO construction transfers directly. For the lower bound, Q/K rotation can make scores vary with distance even when the states before rotation are identical, so the proof's identical-addend step need not hold. For the construction, attending only to the same delimiter with unrotated values does not return the query's offset from it. Section 3 discusses RoPE outside the scope of the ECB lower bound and defines VO heads using unrotated Q/K scores and V/O rotation.

Pathway versus frequency (W2)

Both the frequency setups as well as the value pathway seems to matter for VO model's success so it would be good to empirically see the ablations of the architectures.

We moved the Layer 1 rotations from V/O to Q/K while keeping the two-layer backbone and periods 5,7,11,135,7,11,13 fixed. On strings of length 2,000, exact-copy accuracy was 100% for VO and 0% for Q/K in every distribution and seed. Q/K received more optimizer updates than VO. We gave the model the correct prefix at each step (teacher forcing). A copy counted as exact only if the model predicted every source token and the end marker at the right positions. Figure 4 shows the comparison. This tests where we apply the rotations, not what happens when we change the periods within V/O.

Comparison with RoVE (Q1)

Compared to RoVE (García-Castellanos et al., 2026), are there archtectural difference for VO transformers?

RoVE combines V/O rotation with Q/K RoPE in the same heads and uses the standard geometric RoPE frequencies in its GPT-2 models. Our first layer instead selects a delimiter with unrotated Q/K and uses one small prime period per VO head. What distinguishes our construction is that these integer periods turn the returned phases into an explicit residue code: each head encodes the query’s offset from the delimiter modulo its prime. The small periods keep the phases distinguishable with O(log⁡log⁡N)O(\log\log N) bits of precision. The second layer uses ordinary attention to match the residues and retrieve the next source token or the end marker.

Thanks for the authors to clairfy my concerns during the rebuttals. I don't have further questions on the paper. Although I don't have sufficient knowledge to judge the paper, I think the paper is technically sound with concrete contributions.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Scope of our results and new evidence

We thank the reviewers for their suggestions. In addition to our individual responses, we clarify the scope of our contributions and describe the changes in the revised PDF.

What the theory establishes. Our proposed horizon-uniform framework lies between length-specific circuits (where copying is trivial) and fixed-resource transformers over unbounded lengths (where copying is impossible). This is the only model of the three that is suitable to compare the expressiveness supplied by different positional encodings. We allow resources to grow with the design horizon NN, but one model TNT_N must handle every source length L≤NL\le N with the same parameters. In this setting, we prove the first set of separation results: negative result for ECB transformers, and positive result for prime-period VO transformers.

Our negative result shows that, under a standard finite-precision computational model (following Li et al., 2024), NoPE cannot copy and stop correctly on long all-identical strings within the design horizon even with arbitrary width, N0.01N^{0.01} (a small polynomial) layers, and 0.9log⁡2N0.9\log_2 N (near-logarithmic) bits, as stated in Corollary 3.5. Meanwhile, our positive result shows that using VO rotation and exact modular position indices, a small two-layer transformer can copy all strings of length ≤N\le N using O(log⁡log⁡N)O(\log\log N)-bit precision and O(log⁡Nlog⁡log⁡N)O(\frac{\log N}{\log\log N}) width. Its offset fingerprint uses O(log⁡N)O(\log N) bits, an essentially information-theoretically minimal bit budget for distinguishing NN offsets.

What the experiments add. The experiments go beyond the lower bound: standard RoPE, directly computed ALiBi, and sinusoidal embeddings all lose accuracy under repetition near the training limit; meanwhile, a smaller two-layer prime-period VO model achieves perfect accuracy at the evaluated training-range lengths and length-generalizes with almost perfect accuracy up to the theoretical limit set by the CRT period product (5,005).

After submission, we also tested replacing V/O rotations with Q/K rotations (RoPE-style) in Layer 1 while keeping the backbone and prime periods 5,7,11,135,7,11,13 fixed. At length 2,000, exact-copy accuracy was 100% for VO and 0% for Q/K in every distribution and seed, despite more optimizer updates for Q/K. We scored under teacher forcing and required both the full copy and the end marker. On all-identical inputs at that length, Q/K got every copied token right but missed the end marker; this resembles the failure pattern in frontier LLMs and what our theory predicts for the more restrictive ECB class.

Manuscript revisions. The revised experiments report three-seed baseline results and add the same-prime Q/K control (Figures 3–4 and Appendix B). We moved the expanded comparison table to Appendix B (Table 3). We revised the Introduction and Section 3 to clarify the horizon-uniform setup, the scope of the ECB lower bound, and the VO construction, and reorganized the proofs in Appendices C–D without changing the main guarantees. We also expanded Related Work, including comparisons with Barbero et al. and Meyer et al.

Dear Reviewers,

The authors have finished uploading their responses to reviewers, and the discussion phase is now underway. If you haven't already, please carefully review the authors' responses to understand their perspectives. Please engage in thoughtful and constructive discussions with the authors, and update your review or rating if necessary.

The discussion period lasts until November 18th AoE, which means you have less than five days left to interact with the authors. Please start engaging well before the period ends, so that the authors will have sufficient time to respond to any follow-up questions/comments.

Your active participation and contribution to the ongoing discussion are highly encouraged. Thank you very much for your contribution to ICLR.

Best regards,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.