Newest papers

Copying Under Repetition: From Prefix Matching to Position Hashing

Anxin Guo, Tianlong Huang, Chenxiao Yang, Zhiyuan Li · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.26722 · cited by 0 works (OpenAlex) · open-access PDF

Portuguese

Em cadeias repetidas, o correspondente conteúdo local não mais identifica de forma confiável onde a cópia deve continuar ou quando deve parar. No entanto, mostramos que um transformador de duas camadas com valores de atenção e outputs (VO-rotations) de estilo RoPE com períodos primos de precisão $O(\log\log N)$-bit e $O(\log N/\log N)$-bit de precisão pode copiar cada cadeia até um horizonte de design escolhido $N$ e terminar corretamente sob repetição arbitrária. No entanto, usamos rotas de duas camadas de valores de atenção e saídas (VO-rotations) com períodos primos pequenos para codificar distâncias de anquiladores de transtorno e $O(\log N/log\log N)$-bit de largura. Pelo

Machine translation (Meta M2M100); the English original follows.

Abstract

Frontier LLMs can copy random text almost flawlessly, yet they often overrun or truncate long blocks of repeated characters. In repeated strings, matching local content no longer reliably identifies where copying should continue or when it should stop. Nevertheless, we show that a two-layer transformer with $O(\log\log N)$-bit precision and $O(\log N/\log\log N)$ width can copy every string up to a chosen design horizon $N$ and terminate correctly under arbitrary repetition. We use RoPE-style rotations of attention values and outputs (VO-rotations) with small prime periods to encode distances from delimiter anchors modulo those primes. By the Chinese Remainder Theorem, these periodic encodings jointly distinguish all required distances, allowing one retrieval rule to select either the next source token or the end marker. In contrast, we prove a width-independent impossibility result for copying under sequential finite-precision softmax accumulation. It applies to transformers whose only positional input is an additive attention bias that eventually becomes constant, including NoPE and a recursive implementation of ALiBi. Once an identical-token run exceeds the resulting saturation threshold, further repetitions leave the logits unchanged. If this threshold grows sublinearly with $N$, these models cannot both complete a long all-identical copy and stop correctly, a pattern resembling the termination errors of frontier LLMs. In synthetic copying experiments, baseline transformer models fail on long repeated strings even within the training range. Trained VO models, by contrast, generalize beyond the training lengths with near-perfect accuracy up to length $\approx5005$, the selected primes' period product.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Prefix, Security token, Copying, Computer science, Algorithm, Suffix

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange