CS Paper Radar

A Conditional No-Hair Theorem for Transformers: How Language Models Forget Their Prompt

Shuyang Xiang

cs.AI ·submitted 2026-10-16 19:03 UTC · v1
theory

Abstract

We ask how much an autoregressive transformer retains of its prompt after generating $t$ tokens. Consider two different prompts followed by the same continuation text, so that any difference in their hidden states comes from the prompt alone, and we find that the distance between their hidden states decays approximately as a power law $t^{-α}$, where $α=1$ is the rate at which a fixed prompt's share of uniform attention shrinks and smaller values mean longer memory. Trained models forget fast ($α\approx0.55$--$0.7$), untrained ones slowly ($α\approx0.2$--$0.5$). We prove that this offset is $O\big(P(\log t)^{L-1}/t\big)$ for a prompt of length $P$ and depth $L$. The bound holds for finite-depth pre-LN softmax transformers with bounded attention logits, under one additional condition: the pre-norm activations stay away from zero. The mechanism is geometric: the prompt's direct influence is diluted as the context grows, and \emph{relay} --- continuation tokens passing on what earlier tokens read from the prompt --- can only add logarithmic factors. This is what we call the \emph{conditional no-hair theorem}: given the text generated so far, the prompt's influence on the next token vanishes as $t$ grows, so any property of the prompt that survives, such as its language, must be carried by the text itself. An exactly solvable linear relay model shows that the bound cannot be improved and reproduces the rise of the local exponent towards $1$ seen in untrained networks. Cancelling the dilution with a logit bias stops the decay early in training and reverses it after, so dilution is necessary for the forgetting we measure; untrained networks and the solvable model show it is also sufficient.

Closest papers

Nearest neighbours by meaning across the whole index.

Copying Under Repetition: From Prefix Matching to Position Hashing

cs.LG cs.CL ·2026-10-19 ·Anxin Guo, Tianlong Huang, Chenxiao Yang, Zhiyuan Li
theory similarity 0.60
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.

0.14

Exact-Solution Volume and Length Generalization in Transformers

cs.LG cs.AI ·2026-10-06 ·Yijia Jessica Zhu, David Chiang
similarity 0.59
Abstract · 26 pages, 2 figures

Research on transformer expressivity shows whether a transformer is capable of solving a given task, but gives little indication of whether the solution, if learned, is generalizable to longer input lengths. We study this question through normalized exact-solution volume (NESV): the fraction of a bounded parameter region that achieves an exact solution on every input of length $n$. For fixed-width, single-layer transformers with $\log n$-scaled attention, we establish asymptotic bounds on NESV for four tasks: FIRST ($Θ(1)$), MAJORITY ($Θ(1/(n\log n))$), INDEX ($Θ(1/n^3)$), and PARITY ($0$). These results are consistent with previous empirical results: the faster the exact-solution volume decays with input length, the harder it is to length-generalize on that task. Looking deeper into INDEX, our volume analysis reveals two error sources that grow with $n$. Consequently, we study a transformer model that would structurally eliminate one of the terms, theoretically improving the NESV bound to $Θ(n^{-1})$, and empirically achieving 85% accuracy when tested at $10\times$ the training length, compared with the 60% accuracy of the original model. We conclude that volume analysis may be a useful approach to identify concrete sources of length sensitivity and thus provide insights into task-specific model refinements.

0.23

An equality condition for the Dobrushin bound on attention rollout and how often it holds in trained transformers

cs.LG math.PR ·2026-10-04 ·Przemysław Rola
similarity 0.58
Abstract · 19 pages, 4 figures, 4 tables

The Dobrushin coefficient of each attention-rollout factor satisfies $κ(\frac12(I+A))\le\frac12(1+κ(A))$, and multiplying these inequalities over layers bounds the coefficient of the whole rollout. We characterise exactly when the layerwise bound is tight: equality holds if and only if some token pair attaining $κ(A)$ is mutually self-dominant - each of the two attends to itself at least as strongly as the other attends to it. The condition is far from automatic: uniformly random stochastic matrices satisfy it only 24-30% of the time. When tested on the head-averaged attention of each individual input and restricted to content tokens - image patches, words or tabular features, excluding cls, register and separator tokens - the condition holds for essentially every input at every layer of DINOv2 (three model sizes), RoBERTa and DistilBERT. In the supervised models DeiT-B and ViT-B/16 it holds for 91% and 64% of input-layer pairs respectively, with all failures occurring late in depth. In FT-Transformer trained on two standard tabular benchmarks it holds for only 11-44% of input-layer pairs. The special tokens account for almost all failures in DINOv2 and the language models: when they are included, the condition holds for only 82-97% of input-layer pairs.

0.31

Asymptotic Behavior of Transformers

cs.LG cs.AImath.ST ·2026-10-14 ·Katy Blumer, Da-Cheng Juan, Jon Kleinberg, Ravi Kumar, Cyrus Rashtchian +1 more
hot direction similarity 0.57
Abstract · 24 pages, 3 figures

In this paper we study the behavior of transformer networks generating text over long periods of time. We show that even a three-token, single-layer attention-only transformer can fail to converge. We then study a rich class of transformers with arbitrary finite depth, layer normalization, MLPs, RoPE encodings, and an arbitrary mix of local and global layers. Every transformer in this class has a softmax temperature threshold above which its empirical cache distribution converges to a unique limit, independent of initial conditions. We show further that, while each transformer has a temperature threshold, the supremum of this set is infinite, so there is no global minimal temperature that forces all transformers to converge.

0.35

A First-Order Entropy Law for Canonical T-Complexity of Finite-Alphabet i.i.d. Sources

cs.IT math.ST ·2026-08-18 ·Thomas Schürmann
theory similarity 0.57
Abstract · 10 pages, no figures

Let $W_N$ be an exact length-$N$ block from a strictly positive i.i.d. source $\mathbf p$ on a fixed finite alphabet. We prove that the canonical T-complexity $c_T$ satisfies \[ \frac{c_T(W_N)}{e^{-γ}h(\mathbf p) N/\log N}\longrightarrow1 \] in probability and in $L^r$ for every fixed $1\le r<\infty$, where $h(\mathbf p)$ is the source entropy in nats and $γ$ is the Euler-Mascheroni constant. The proof combines an exact length budget for canonical recovery, a critical-scale $E_1$ estimate for an ideal backward chain, and an exact finite-block boundary representation. An exact Doob-transform identity expresses the finite-boundary law relative to the ideal law conditioned at each step to avoid the current history-dependent successor codeword. A history-uniform renewal estimate then makes the telescoping endpoint density uniformly asymptotic to one, so no one-step approximation errors accumulate.

0.40

Length Generalization for Transformers via Compression

cs.LG cs.FLcs.LO ·2026-09-08 ·Georg Zetzsche, Hongjian Jiang, Andy Yang, Pascal Bergsträßer, Marco Sälzer +2 more
similarity 0.57
Abstract

Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particular, the C-RASP hypothesis (a formalized version of the so-called RASP-l conjecture) posits that transformers length-generalize on a task if and only if a solution is expressible in the C-RASP language. While this hypothesis has strong empirical validation, theoretical problems arise from the fact that no computable length generalization bounds exist for C-RASP, alongside the discovery of seemingly contradictory experiments. To address these problems, we refine the C-RASP hypothesis utilizing the recently-proposed fragments C-RASP+ and C-RASP1. These fragments have computable length generalization bounds, though in the worst case requiring an extremely large (double exponential) sample size. It is an open question whether these sample size bounds are tight. In this paper, we resolve this open question by providing an exponentially tighter bound. In doing so, we show a polynomial length generalization bound for transformers if we adopt compressed strings, via a novel connection to power words. As an application, we show how this yields a fine-grained analysis of the C-RASP conjecture that resolves contradicting experimental evidence against it.

0.08

Internalizing Chain-of-thought into Looped Transformers

cs.CC cs.DScs.LG ·2026-10-19 ·Kehang Zhou, Pinyan Lu
similarity 0.57
Abstract · 20 pages, 1 figure

Chain-of-thought (CoT) enables constant-bit-size transformers to perform general-purpose computation through generated tokens (Li and Wang, 2025a), whereas looped transformers carry out the same computation by recurrence in hidden states (latent thought). We construct a family of constant-bit-size looped transformers that interpolates between CoT and latent thought. For a prescribed loop count $L=L(n)$ and a fixed integer $k\ge1$ satisfying $s(n)^{1/k}=Ω(L)$, our transformer simulates a time-$t(n)$, space-$s(n)$ Turing machine using a context window of $O(s(n)/L)$ and $O(t(n)s(n)^{1/k}/L)$ generated tokens, reducing both resources by a factor of $L$ relative to the corresponding unlooped queue-machine simulation. The construction also holds with softmax attention at constant bit-size, under the finite-precision kernel specified in this paper.

0.20

Emergent One-Third Scaling Law as Attention Tries to Concentrate

cs.LG cs.AIstat.ML ·2026-09-26 ·Yizhou Liu, Sara Kangaslahti, Jeff Gore
hot direction similarity 0.57
Abstract · 32 pages, 16 figures

The neural scaling law relating longer training to better performance through a power law is central to today's large language models (LLMs), yet its origin remains debated. One recent proposal is that power laws can emerge from the strong non-linearity of a single softmax head learning peaked distributions. What happens with multiple softmax functions, as in LLMs, is unclear. Here, we show through toy models that any softmax learning peaked distributions, regardless of its position in the model, can develop logit magnitudes that grow in a power law with exponent $1/3$, becoming a training bottleneck whose loss contribution decays as a power law with the same exponent $1/3$. The overall loss therefore obeys $1/3$ scaling whenever at least one softmax learns peaked distributions. We confirm that many softmax functions in LLMs learn peaked distributions and that LLM loss scaling matches this $1/3$ prediction. Moreover, logit growth dynamics reveal that attention heads, rather than the language modeling head, are the bottleneck likely driving the $1/3$ loss scaling in LLMs. Attention trying to concentrate on specific information, which is the heart of Transformers, may therefore also be the heart of the neural scaling law of training.

0.41