Mixing Times of Glauber Dynamics on Masked Language Models

# Mixing Times of Glauber Dynamics on Masked Language Models
Source: [https://arxiv.org/html/2605.16378](https://arxiv.org/html/2605.16378)
Suvadip Sana Department of Statistics and Data Science Cornell University ss2776@cornell\.edu &Sami Wolf11footnotemark:1 Cornell University smw362@cornell\.edu&Neer Mehta11footnotemark:1 Cornell University nmm229@cornell\.edu&Alina Shah11footnotemark:1 Cornell University ams877@cornell\.edu&Aitzaz Shaikh11footnotemark:1 Cornell University ams845@cornell\.edu&Janna Goodman11footnotemark:1 Cornell University jsg344@cornell\.edu&Lionel Levine22footnotemark:2 Department of Mathematics Cornell University levine@math\.cornell\.edu

###### Abstract

Masked language models \(MLMs\) define local conditional distributions over tokens but do not, in general, correspond to any consistent joint distribution over sequences\. This raises a fundamental question:what global distributional behavior is induced when such conditionals are used iteratively for generation?We address this question by modeling iterative masked\-token resampling as a Glauber dynamics Markov chain on the discrete space of token sequences\. We first show that MLM conditionals are intrinsically incompatible: we introduce a rectangle test that certifies this incompatibility and empirically verify its prevalence across modern MLMs\. We then provide a theoretical analysis of the induced Markov chain\. Under bounded cross\-token influence, we establish a high\-temperature contraction result implyingO​\(n​log⁡n\)O\(n\\log n\)mixing time wherennis the sequence length\. In contrast, we prove that under a uniform local margin condition, the chain exhibits metastability, with exponentially slow escape from semantic basins at low temperatures\. Empirically, we demonstrate a phase transition in mixing behavior as a function of temperature and sequence length, consistent with the theoretical predictions\. We further characterize the induced stationary behavior through semantic trajectories, identifying persistent structures such as long\-lived traps and recurrent semantic basins, with political content serving as a measurable case study\.

## 1Introduction

Masked language models \(MLMs\) such as BERT\[[4](https://arxiv.org/html/2605.16378#bib.bib2)\]are commonly used for natural language understanding \(NLU\) tasks such as generating semantically meaningful embeddings\[[4](https://arxiv.org/html/2605.16378#bib.bib2)\], Machine translation\[[3](https://arxiv.org/html/2605.16378#bib.bib28)\]sentiment analysis\[[19](https://arxiv.org/html/2605.16378#bib.bib29)\], and named entity recognition\[[4](https://arxiv.org/html/2605.16378#bib.bib2)\]\. However, the global properties of MLMs, such as model biases and structural attractors, have not been completely characterized\. Existing methods for interpreting MLMs fall short of capturing global structure\. Single\-token masked predictions ignore multi\-token dependencies\. Pseudo\-Log\-Likelihood scoring\[[17](https://arxiv.org/html/2605.16378#bib.bib30)\]is widely used as if conditionals define a joint distribution; we show this is unjustified\. Linear probes on static embeddings\[[10](https://arxiv.org/html/2605.16378#bib.bib31),[20](https://arxiv.org/html/2605.16378#bib.bib32)\]miss temporal phenomena entirely, such as the metastable semantic traps we document in this work\.

![Refer to caption](https://arxiv.org/html/2605.16378v1/image1.png)Figure 1:Glauber dynamics on BERT exhibits metastable semantic basins\.PCA projection of sentence\-embedding trajectories over 10,000 resampling steps, colored from warm \(early\) to cool \(late\)\. Tight clusters correspond to traps — configurations where the chain remains for hundreds to thousands of steps before escaping \(§[B\.6](https://arxiv.org/html/2605.16378#A2.SS6)\)\.Initial:“The overnight train rattled through the mountains as thunder echoed across the empty valley\.”Final:“Greenville police say 2 sexual predators creeped on patients at Trinity Medical Center”Mapping this landscape is necessary for reasons beyond interpretability\. While MLMs are not historically used for standalone text generation,\[[21](https://arxiv.org/html/2605.16378#bib.bib9)\]showed that Gibbs sampling from these models can produce fluent text, and many modern discrete diffusion models involve MLMs during denoising\[[11](https://arxiv.org/html/2605.16378#bib.bib33)\]\. The energy landscape of the employed MLM is partially inherited by the generation process, raising the question of whether semantic biases in the MLM propagate to the outputs of these systems\. As development of text\-generating diffusion models continues to accelerate, understanding the hidden structure of these models will become increasingly important for fluent generation\.

Glauber dynamics, a single\-site Markov Chain Monte\-Carlo \(MCMC\) method introduced to study the Ising model\[[6](https://arxiv.org/html/2605.16378#bib.bib7)\], provides the natural framework for this investigation: at each step, a random token position is masked and resampled from the MLM’s conditional distribution\. Iterative resampling reveals two striking phenomena \(Figs\.[1](https://arxiv.org/html/2605.16378#S1.F1),[2](https://arxiv.org/html/2605.16378#S1.F2)\): chains become trapped in metastable semantic basins for thousands of steps, and the time to forget the initial state undergoes a temperature\-dependent transition\. We make four contributions:

1. 1\.Incompatibility\.We develop a “rectangle test” to measure the incompatibility of MLM conditionals by comparing thepath\-dependenceof multi\-token swaps\. We demonstrate that incompatibility is an intrinsic structural artifact of the pseudo\-likelihood training objective: it persists across model sizes and is amplified by inter\-token semantic influence\.
2. 2\.Mixing theory\.We establish provable, sufficient conditions for both fast and slow mixing parameterized by token influence functions\. Specifically, when cross\-site influence is bounded at high temperatures, we prove anO​\(n​log⁡n\)O\(n\\log n\)upper bound on mixing time\. Conversely, at low temperatures, we establish an exponentially slow lower bound in temperature, driven by uniform local score margins that trap the chain in metastable basins\. We provide an empirically certified slow\-mixing basin using a drift condition\.
3. 3\.Phase transitions\.We empirically characterize how the boundary between fast and slow mixing depends on temperature and sequence length, validating the theoretical predictions on BERT\.
4. 4\.Semantic landscape\.We probe the landscape induced by long\-term dynamics to reveal semantic traps and recurrent basins\. Using sentence embeddings, we track semantic trajectories to visualize metastable behavior\. We analyze political content as a measurable case study of semantic recurrence across diverse chain initializations\. We validate our approach by comparing the Glauber dynamics induced by several MLMs, including BERT\[[4](https://arxiv.org/html/2605.16378#bib.bib2)\], RoBERTa\[[12](https://arxiv.org/html/2605.16378#bib.bib12)\], and ModernBERT\[[22](https://arxiv.org/html/2605.16378#bib.bib34)\]\.

![Refer to caption](https://arxiv.org/html/2605.16378v1/Coupling_Phase__Diagram.png)

Figure 2:A temperature\-length phase transition in mixing time\.Two chains initialized from independent MS MARCO passages on RoBERTa\-base are evolved under maximal coupling\. Color: median steps to coupling within a10410^\{4\}\-step budget\. Black: no coupling within budget\. The slow\-to\-fast boundary nearτ≈\\tau\\approx1\.5\-2 matches the regimes characterized in §[5](https://arxiv.org/html/2605.16378#S5), §[6\.1](https://arxiv.org/html/2605.16378#S6.SS1)\.

## 2Related Work

##### Glauber dynamics and mixing in high\-dimensional systems\.

Glauber dynamics was originally introduced in statistical physics as a stochastic single\-site update process for sampling from Gibbs distributions, particularly in the Ising model\[[6](https://arxiv.org/html/2605.16378#bib.bib7)\]\. At each step, one coordinate is selected and resampled conditioned on the remaining variables, producing a Markov chain whose stationary distribution corresponds to the target Gibbs measure\. Theoretical analysis of Glauber dynamics and mixing times has played a central role in probability theory, statistical physics, and Markov Chain Monte Carlo methods\[[9](https://arxiv.org/html/2605.16378#bib.bib4)\]\.

##### Discrete diffusion and iterative denoising language models\.

Recent years have seen growing interest in diffusion and denoising approaches for discrete text generation\. Structured discrete diffusion models\[[1](https://arxiv.org/html/2605.16378#bib.bib18)\]generalized denoising diffusion probabilistic models to discrete state spaces through categorical corruption processes\. Diffusion\-LM\[[11](https://arxiv.org/html/2605.16378#bib.bib33)\]demonstrated controllable text generation using diffusion dynamics in continuous latent spaces, while DiffuSeq\[[7](https://arxiv.org/html/2605.16378#bib.bib35)\]extended diffusion methods to sequence\-to\-sequence generation tasks\. Several recent works established stronger connections between diffusion modeling and masked language modeling\. DiffusionBERT\[[8](https://arxiv.org/html/2605.16378#bib.bib36)\]integrated diffusion\-style denoising with MLM objectives, while SEDD\[[13](https://arxiv.org/html/2605.16378#bib.bib37)\]proposed ratio\-based discrete diffusion modeling for text generation\. Most closely related to our setting, masked diffusion language models\[[16](https://arxiv.org/html/2605.16378#bib.bib20)\]showed that iterative masked denoising objectives can serve as effective generative mechanisms for language modeling\. Collectively, these works suggest that iterative local token refinement may serve as a viable alternative to autoregressive generation\. Our work differs from prior diffusion\-based language modeling research in that we focus not on generation quality or controllability, but on the global stochastic geometry induced by MLM conditionals\. In particular, we study how repeated masked\-token updates give rise to metastable semantic regions, topic persistence, and transition dynamics across sequence space\.

##### Biases, probing, and representation analysis in language models\.

A large body of work investigates social biases and internal representations in language models\. Early studies examined demographic and stereotypical biases in generated text by conditioning prompts on demographic identities and analyzing downstream sentiment or toxicity\[[18](https://arxiv.org/html/2605.16378#bib.bib3)\]\. Subsequent benchmarks such as CrowS\-Pairs\[[15](https://arxiv.org/html/2605.16378#bib.bib38)\], StereoSet\[[14](https://arxiv.org/html/2605.16378#bib.bib39)\], and RealToxicityPrompts\[[5](https://arxiv.org/html/2605.16378#bib.bib40)\]evaluated stereotypical associations and harmful generation behaviors in pretrained language models\. Other lines of work focused on probing the internal structure of neural representations\[[2](https://arxiv.org/html/2605.16378#bib.bib41)\]\. Our work differs from existing probing methodologies in two important ways\. First, rather than studying static embeddings or one\-step generations, we analyze the long\-run stochastic dynamics induced by repeated masked\-token updates\. Second, instead of measuring isolated stereotypes or toxicity scores, we investigate global semantic behavior through topic\-level metastability and transition structure in the induced Markov chain\. This dynamical systems perspective connects language modeling with statistical physics and Markov chain theory, offering a new framework for understanding global structure and biases in masked language models\.

## 3Method: Text Glauber Dynamics

### 3\.1State space and temperature\-scaled local conditionals

Let𝑽\\bm\{V\}be a finite vocabulary and let𝑿n:=𝑽n\{\\bm\{X\}\}\_\{n\}:=\\bm\{V\}^\{n\}denote the set of token sequences of lengthnn\. Since𝑽\\bm\{V\}is finite,𝑿n\{\\bm\{X\}\}\_\{n\}is finite with\|𝑿n\|=\|𝑽\|n\|\{\\bm\{X\}\}\_\{n\}\|=\|\\bm\{V\}\|^\{n\}\. Whennnis fixed we write𝑿\{\\bm\{X\}\}\. Forx=\(x1,…,xn\)∈𝑿x=\(x\_\{1\},\\dots,x\_\{n\}\)\\in\{\\bm\{X\}\}andi∈\[n\]:=\{1,…,n\}i\\in\[n\]:=\\\{1,\\dots,n\\\}, writex−i:=\(x1,…,xi−1,xi\+1,…,xn\)\.x\_\{\-i\}:=\(x\_\{1\},\\dots,x\_\{i\-1\},x\_\{i\+1\},\\dots,x\_\{n\}\)\.\. We assume the masked language model induces, for each siteiiand contextx−ix\_\{\-i\}, a strictly positive conditional distributionpθ\(⋅∣x−i\)∈Δ\(𝑽\)\.p\_\{\\theta\}\(\\cdot\\mid x\_\{\-i\}\)\\in\\Delta\(\\bm\{V\}\)\.Given the temperatureτ\>0\\tau\>0, we assume there exist local scoressi​\(a;x−i\)∈ℝ,a∈𝑽,s\_\{i\}\(a;x\_\{\-i\}\)\\in\\mathbb\{R\},a\\in\\bm\{V\},that induce temperature\-scaled conditionals

pθ,τ​\(a∣x−i\):=exp⁡\(si​\(a;x−i\)/τ\)∑b∈𝑽exp⁡\(si​\(b;x−i\)/τ\)\.p\_\{\\theta,\\tau\}\(a\\mid x\_\{\-i\}\):=\\frac\{\\exp\(s\_\{i\}\(a;x\_\{\-i\}\)/\\tau\)\}\{\\sum\_\{b\\in\\bm\{V\}\}\\exp\(s\_\{i\}\(b;x\_\{\-i\}\)/\\tau\)\}\.

### 3\.2The Glauber Dynamics Chain

Givenx∈𝑿x\\in\{\\bm\{X\}\}, define the single\-site update chain with transition kernel

Pτ​\(x,x′\)=1n​∑i=1n𝟏x−i=x−i′​pθ,τ​\(xi′∣x−i\)\.P\_\{\\tau\}\(x,x^\{\\prime\}\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\_\{x\_\{\-i\}=x^\{\\prime\}\_\{\-i\}\}\\,p\_\{\\theta,\\tau\}\(x\_\{i\}^\{\\prime\}\\mid x\_\{\-i\}\)\.
Equivalently, fromxxwe choose a siteiiuniformly from\[n\]\[n\]and resamplexix\_\{i\}frompθ,τ\(⋅∣x−i\)p\_\{\\theta,\\tau\}\(\\cdot\\mid x\_\{\-i\}\)\.

###### Proposition 1\.

For eachτ\>0\\tau\>0,PτP\_\{\\tau\}is a Markov kernel on𝐗\{\\bm\{X\}\}\. Ifpθ,τ​\(a∣x−i\)\>0p\_\{\\theta,\\tau\}\(a\\mid x\_\{\-i\}\)\>0for alli,x−i,ai,x\_\{\-i\},a, thenPτP\_\{\\tau\}is irreducible and aperiodic\.

Detailed proofs for all Propositions, Lemmas, and Theorems are deferred to Appendix[E](https://arxiv.org/html/2605.16378#A5)\.

###### Corollary 2\.

Ifpθ,τ​\(a∣x−i\)\>0p\_\{\\theta,\\tau\}\(a\\mid x\_\{\-i\}\)\>0for alli,x−i,ai,x\_\{\-i\},a, then there exists a unique stationary distributionμτ\\mu\_\{\\tau\}on𝐗\{\\bm\{X\}\}, and for everyx∈𝐗x\\in\{\\bm\{X\}\},

Pτt​\(x,⋅\)→μτas​t→∞\.P\_\{\\tau\}^\{t\}\(x,\\cdot\)\\to\\mu\_\{\\tau\}\\quad\\text\{as \}t\\to\\infty\.

## 4Incompatibility of MLM Conditionals

We motivate Glauber dynamics as a probe for MLM structure by showing that the relative probability of two sampling outcomes given the same context need not match their relative prominence in the stationary distributionμτ\\mu\_\{\\tau\}\.

###### Definition 1\.

A distributionπ\\pion𝐗\{\\bm\{X\}\}is*compatible*with the local conditionals if, for everyii, every contextx−ix\_\{\-i\}, and everya∈𝐕a\\in\\bm\{V\}withπ​\(X−i=x−i\)\>0\\pi\(X\_\{\-i\}=x\_\{\-i\}\)\>0,

π​\(Xi=a∣X−i=x−i\)=pθ,τ​\(a∣x−i\)\.\\pi\(X\_\{i\}=a\\mid X\_\{\-i\}=x\_\{\-i\}\)=p\_\{\\theta,\\tau\}\(a\\mid x\_\{\-i\}\)\.

###### Theorem 3\.

If a compatible distributionπ\\piexists, thenπ\\piis stationary forPτP\_\{\\tau\}andPτP\_\{\\tau\}is reversible with respect toπ\\pi\.

Compatibility implies single\-mask probes read off stationary ratios directly: forxa=\(x−i,a\)x\_\{a\}=\(x\_\{\-i\},a\)andxb=\(x−i,b\)x\_\{b\}=\(x\_\{\-i\},b\),

pθ,τ​\(a∣x−i\)pθ,τ​\(b∣x−i\)=π​\(xa\)π​\(xb\)\.\\displaystyle\\frac\{p\_\{\\theta,\\tau\}\(a\\mid x\_\{\-i\}\)\}\{p\_\{\\theta,\\tau\}\(b\\mid x\_\{\-i\}\)\}=\\frac\{\\pi\(x\_\{a\}\)\}\{\\pi\(x\_\{b\}\)\}\.\(4\.1\)Without compatibility, the biases revealed by single\-mask probing may differ from those exhibited under iterative generation\. We now show no compatible distribution exists for MLMs trained with a pseudo\-log\-likelihood objective\.

##### The rectangle test\.

Fix a sequence𝒙\{\\bm\{x\}\}and two positionsi≠ji\\neq j, with current tokensA=xiA=x\_\{i\},B=xjB=x\_\{j\}and replacementsA′,B′A^\{\\prime\},B^\{\\prime\}\. Define four states differing only at positionsiiand/orjj:

𝒙=\(…,A,…,B,…\),𝐲=\(…,A′,…,B,…\),𝐰=\(…,A,…,B′,…\),𝐳=\(…,A′,…,B′,…\)\.\{\\bm\{x\}\}=\(\\ldots,A,\\ldots,B,\\ldots\),\\;\\;\\mathbf\{y\}=\(\\ldots,A^\{\\prime\},\\ldots,B,\\ldots\),\\;\\;\\mathbf\{w\}=\(\\ldots,A,\\ldots,B^\{\\prime\},\\ldots\),\\;\\;\\mathbf\{z\}=\(\\ldots,A^\{\\prime\},\\ldots,B^\{\\prime\},\\ldots\)\.Each edge has a log\-probability ratio from the MLM, e\.g\.s𝒙→𝐲=log⁡pθ,τ​\(A′∣𝒙−i\)−log⁡pθ,τ​\(A∣𝒙−i\)s\_\{\{\\bm\{x\}\}\\to\\mathbf\{y\}\}=\\log p\_\{\\theta,\\tau\}\(A^\{\\prime\}\\mid\{\\bm\{x\}\}\_\{\-i\}\)\-\\log p\_\{\\theta,\\tau\}\(A\\mid\{\\bm\{x\}\}\_\{\-i\}\)\. We define therectangle incompatibilityδ=\(s𝒙→𝐲\+s𝐲→𝐳\)−\(s𝒙→𝐰\+s𝐰→𝐳\)\\delta=\(s\_\{\{\\bm\{x\}\}\\to\\mathbf\{y\}\}\+s\_\{\\mathbf\{y\}\\to\\mathbf\{z\}\}\)\-\(s\_\{\{\\bm\{x\}\}\\to\\mathbf\{w\}\}\+s\_\{\\mathbf\{w\}\\to\\mathbf\{z\}\}\)\.

###### Proposition 4\.

If the conditionals admit a compatible distribution, thenδ=0\\delta=0for every rectangle\.

This must hold because each edge log\-ratio equals a log\-ratio ofπ\\pi\. Both paths from𝒙\{\\bm\{x\}\}to𝐳\\mathbf\{z\}telescope tolog⁡π​\(𝐳\)/π​\(𝒙\)\\log\\pi\(\\mathbf\{z\}\)/\\pi\(\{\\bm\{x\}\}\), soδ=0\\delta=0\. Anyδ≠0\\delta\\neq 0is therefore a certificate of incompatibility\.

##### Results\.

We sample 300 random rectangles per model from MS MARCO text, with replacement tokens drawn from each model’s own top\-50 predictions\. As a control, we run the same test on GPT\-2: since it defines a joint distribution, each edge log\-ratio is a difference of joint log\-probabilities, andδ=0\\delta=0by telescoping\.

Table 1:Rectangle incompatibility across models\. All MLMs show significant incompatibility \(p<10−14p<10^\{\-14\}\); GPT\-2 givesδ=0\\delta=0exactly\.All five MLMs show incompatibility in the range0\.640\.64–0\.800\.80, persisting across architectures and model sizes\. We show in Appendix[D](https://arxiv.org/html/2605.16378#A4)that incompatibility\|δ\|\|\\delta\|has a broad distribution, proving it is the rule, not the exception \(Figure[5](https://arxiv.org/html/2605.16378#A4.F5)\) and that it is amplified by inter\-token semantic influence \(Figure[6](https://arxiv.org/html/2605.16378#A4.F6)\.\) Since no compatible distribution exists, the stationary distributionμτ\\mu\_\{\\tau\}is an emergent object whose properties cannot be directly inferred from the local conditionals alone\. We characterizeμτ\\mu\_\{\\tau\}through its mixing behavior in the following sections\.

## 5Mixing Bounds for Glauber Dynamics

To characterize the long\-term behavior of text\-space Glauber dynamics, we prove that there exists an exponential\-time slow\-mixing regime at low temperatures and anO​\(n​log⁡n\)O\(n\\log n\)fast\-mixing regime at high temperatures\. In this section, we parametrize each regime with token influence functions and MLM\-assigned score differences, then show an empirically certified slow\-mixing basin using a drift condition\.

### 5\.1High\-temperature rapid mixing

We now prove a sufficient condition for rapid mixing\. For probability measuresν,ν′\\nu,\\nu^\{\\prime\}on𝑽\\bm\{V\}, write

‖ν−ν′‖TV:=12​∑a∈𝑽\|ν​\(a\)−ν′​\(a\)\|\.\\\|\\nu\-\\nu^\{\\prime\}\\\|\_\{\\mathrm\{TV\}\}:=\\frac\{1\}\{2\}\\sum\_\{a\\in\\bm\{V\}\}\|\\nu\(a\)\-\\nu^\{\\prime\}\(a\)\|\.
###### Definition 2\(Influence coefficients\)\.

Fori≠ji\\neq j, define

ci​j\(τ\):=sup\{∥pθ,τ\(⋅∣x−i\)−pθ,τ\(⋅∣y−i\)∥TV:x,y∈𝑿,xk=yk∀k≠j\}\.c\_\{ij\}\(\\tau\):=\\sup\\left\\\{\\\|p\_\{\\theta,\\tau\}\(\\cdot\\mid x\_\{\-i\}\)\-p\_\{\\theta,\\tau\}\(\\cdot\\mid y\_\{\-i\}\)\\\|\_\{\\mathrm\{TV\}\}:x,y\\in\{\\bm\{X\}\},\\;x\_\{k\}=y\_\{k\}\\ \\forall k\\neq j\\right\\\}\.Let

α​\(τ\):=maxi∈\[n\]​∑j≠ici​j​\(τ\)\.\\alpha\(\\tau\):=\\max\_\{i\\in\[n\]\}\\sum\_\{j\\neq i\}c\_\{ij\}\(\\tau\)\.

###### Theorem 5\(High\-temperature contraction\)\.

Assumeα​\(τ\)<1\\alpha\(\\tau\)<1\. Then for the Hamming metric

dH​\(x,y\):=∑i=1n𝟏xi≠yi,d\_\{H\}\(x,y\):=\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\_\{x\_\{i\}\\neq y\_\{i\}\},there exists a coupling of the chain such that for allx,y∈𝐗x,y\\in\{\\bm\{X\}\},

𝔼​\[dH​\(X1,Y1\)∣X0=x,Y0=y\]≤\(1−1−α​\(τ\)n\)​dH​\(x,y\)\.\\mathbb\{E\}\[d\_\{H\}\(X\_\{1\},Y\_\{1\}\)\\mid X\_\{0\}=x,Y\_\{0\}=y\]\\leq\\left\(1\-\\frac\{1\-\\alpha\(\\tau\)\}\{n\}\\right\)d\_\{H\}\(x,y\)\.Consequently,

tmix​\(ε\)≤n1−α​\(τ\)​\(log⁡n\+log⁡1ε\),t\_\{\\mathrm\{mix\}\}\(\\varepsilon\)\\leq\\frac\{n\}\{1\-\\alpha\(\\tau\)\}\\left\(\\log n\+\\log\\frac\{1\}\{\\varepsilon\}\\right\),wheretmix​\(ε\)t\_\{\\mathrm\{mix\}\}\(\\varepsilon\)denotes total\-variation mixing time\.

### 5\.2A sufficient high\-temperature criterion in terms of score oscillation

The previous theorem is stated in terms of influence coefficients\. We now relate those coefficients to temperature\.

Fori≠ji\\neq j, define the cross\-site score oscillation

Δi​j:=supx,y∈𝑿xk=yk,∀k≠j\[maxa∈𝑽⁡\(si​\(a;x−i\)−si​\(a;y−i\)\)−mina∈𝑽⁡\(si​\(a;x−i\)−si​\(a;y−i\)\)\]\.\\Delta\_\{ij\}:=\\sup\_\{\\begin\{subarray\}\{c\}x,y\\in\{\\bm\{X\}\}\\\\ x\_\{k\}=y\_\{k\},\\ \\forall k\\neq j\\end\{subarray\}\}\\left\[\\max\_\{a\\in\\bm\{V\}\}\\bigl\(s\_\{i\}\(a;x\_\{\-i\}\)\-s\_\{i\}\(a;y\_\{\-i\}\)\\bigr\)\-\\min\_\{a\\in\\bm\{V\}\}\\bigl\(s\_\{i\}\(a;x\_\{\-i\}\)\-s\_\{i\}\(a;y\_\{\-i\}\)\\bigr\)\\right\]\.
###### Lemma 6\.

For alli≠ji\\neq jandτ\>0\\tau\>0,

ci​j​\(τ\)≤Δi​j4​τ\.c\_\{ij\}\(\\tau\)\\leq\\frac\{\\Delta\_\{ij\}\}\{4\\tau\}\.

###### Corollary 7\.

If

maxi​∑j≠iΔi​j<4​τ,\\max\_\{i\}\\sum\_\{j\\neq i\}\\Delta\_\{ij\}<4\\tau,thenα​\(τ\)<1\\alpha\(\\tau\)<1and hence

tmix​\(ε\)≤n1−α​\(τ\)​\(log⁡n\+log⁡1ε\)\.t\_\{\\mathrm\{mix\}\}\(\\varepsilon\)\\leq\\frac\{n\}\{1\-\\alpha\(\\tau\)\}\\left\(\\log n\+\\log\\frac\{1\}\{\\varepsilon\}\\right\)\.

##### On tightness\.

The contraction theorem requiresα​\(τ\)<1\\alpha\(\\tau\)<1, a worst\-case condition over both contexts and update sites, dominated by adversarial coherent contexts where BERT’s conditionals are sharply peaked\. Direct estimation ofα​\(τ\)\\alpha\(\\tau\)on BERT \(Appendix A\.1\) givesα​\(10\)≈1\.04\\alpha\(10\)\\approx 1\.04andα​\(11\)≈0\.94\\alpha\(11\)\\approx 0\.94, so the sufficient condition requires at leastτ\>10\\tau\>10\. This is an order of magnitude above where BERT produces coherent text and where empirical mixing is fast \(§6\.1\)\. The contraction argument is therefore not tight at natural temperatures\.

### 5\.3Low\-temperature metastability and slow mixing

We now give a rigorous slow\-mixing theorem under a local stability assumption\.

For each siteiiand contextx−ix\_\{\-i\}, let

mi​\(x−i\)∈arg⁡maxa∈𝑽⁡si​\(a;x−i\)m\_\{i\}\(x\_\{\-i\}\)\\in\\arg\\max\_\{a\\in\\bm\{V\}\}s\_\{i\}\(a;x\_\{\-i\}\)be a choice of score maximizer\.

LetB⊆𝑿B\\subseteq\{\\bm\{X\}\}be a set of states, to be interpreted as a metastable basin\.

###### Assumption 1\(Uniform local margin on a basin\)\.

There existsΔ⋆\>0\\Delta\_\{\\star\}\>0such that for everyx∈Bx\\in Band every siteiifor which changingxix\_\{i\}would move the chain outsideBB, one has:

xi=mi​\(x−i\),x\_\{i\}=m\_\{i\}\(x\_\{\-i\}\),and

si​\(xi;x−i\)−si​\(a;x−i\)≥Δ⋆for all​a≠xi​with​x\(i→a\)∉B\.s\_\{i\}\(x\_\{i\};x\_\{\-i\}\)\-s\_\{i\}\(a;x\_\{\-i\}\)\\geq\\Delta\_\{\\star\}\\qquad\\text\{for all \}a\\neq x\_\{i\}\\text\{ with \}x^\{\(i\\to a\)\}\\notin B\.Herex\(i→a\)x^\{\(i\\to a\)\}denotes the sequence obtained fromxxby replacing coordinateiibyaa\.

###### Theorem 8\(Low\-temperature exponentially small escape\)\.

Assume the uniform local margin condition on a basinBB\. Then for everyx∈Bx\\in B,

Pτ​\(x,Bc\)≤\|𝑽\|​e−Δ⋆/τ\.P\_\{\\tau\}\(x,B^\{c\}\)\\leq\|\\bm\{V\}\|e^\{\-\\Delta\_\{\\star\}/\\tau\}\.Consequently the conductance ofBBsatisfies

Φτ\(B\):=∑x∈Bμτ​\(x\)​Pτ​\(x,Bc\)μτ​\(B\)≤\|𝑽\|e−Δ⋆/τ\.\\Phi\_\{\\tau\}\(B\):=\\frac\{\\sum\_\{x\\in B\}\\mu\_\{\\tau\}\(x\)P\_\{\\tau\}\(x,B^\{c\}\)\}\{\\mu\_\{\\tau\}\(B\)\}\\leq\|\\bm\{V\}\|e^\{\-\\Delta\_\{\\star\}/\\tau\}\.If additionallyμτ​\(B\)≤12\\mu\_\{\\tau\}\(B\)\\leq\\frac\{1\}\{2\}, then

tmix​\(1/4\)≥14​\|𝑽\|​eΔ⋆/τ\.t\_\{\\mathrm\{mix\}\}\(1/4\)\\geq\\frac\{1\}\{4\|\\bm\{V\}\|\}e^\{\\Delta\_\{\\star\}/\\tau\}\.

Note that ifΔ⋆=O​\(n\)\\Delta\_\{\\star\}=O\(n\), then we will have exponential mixing innnwherennis the length of the sequence\. These are structural theorems about the induced text\-space dynamics\. Whether a specific masked language model such as BERT satisfies the hypotheses at a given temperature is an empirical question that we defer to Appendix[A\.1](https://arxiv.org/html/2605.16378#A1.SS1)\.

### 5\.4An empirically certified slow\-mixing basin

Theorem[8](https://arxiv.org/html/2605.16378#Thmconj8)certifies slow mixing under a uniform local score\-margin hypothesis\. We now exhibit a concrete basin for which a related but distinct condition, positive drift on the boundary, can be verified empirically, providing an alternative slow\-mixing certificate\.

DefineB=\{x:\#​\{i:xi=‘\!’\}≥0\.9​N\}B=\\\{x:\\\#\\\{i:x\_\{i\}=\\text\{\`\!'\}\\\}\\geq 0\.9N\\\}forN=100N=100\. We sample 200 states with exactly0\.9​N0\.9N‘\!’ tokens in random positions and compute the expected one\-step change in ‘\!’\-count under the Glauber kernel,

δτ​\(x\):=1N​\[∑i:xi≠‘\!’pθ,τ​\(‘\!’∣x−i\)−∑i:xi=‘\!’\(1−pθ,τ​\(‘\!’∣x−i\)\)\]\.\\delta\_\{\\tau\}\(x\)\\;:=\\;\\frac\{1\}\{N\}\\\!\\left\[\\sum\_\{i:\\,x\_\{i\}\\neq\\text\{\`\!'\}\}p\_\{\\theta,\\tau\}\(\\text\{\`\!'\}\\mid x\_\{\-i\}\)\\;\-\\;\\sum\_\{i:\\,x\_\{i\}=\\text\{\`\!'\}\}\\bigl\(1\-p\_\{\\theta,\\tau\}\(\\text\{\`\!'\}\\mid x\_\{\-i\}\)\\bigr\)\\right\]\.A positiveδτ​\(x\)\\delta\_\{\\tau\}\(x\)indicates the ‘\!’\-count process is, in expectation, pulled deeper intoBBatxx\.

Table 2:Minimum and median one\-step ‘\!’\-count driftδτ\\delta\_\{\\tau\}across 200 boundary samples ofBB\.All 200 samples exhibit strictly positive drift at both temperatures\. Since the countXt=\#​\{i:xt,i=‘\!’\}X\_\{t\}=\\\#\\\{i:x\_\{t,i\}=\\text\{\`\!'\}\\\}changes by at most one per Glauber step,XtX\_\{t\}is a strict submartingale at the boundary ofBB, and a standard drift argument yields escape times exponential inNN, certifying slow mixing for this basin\. This is a drift\-based certificate, separate from the conductance\-based bound of Theorem[8](https://arxiv.org/html/2605.16378#Thmconj8)which requires a uniform local score margin\.

## 6Results

### 6\.1Mixing\-Time Crossover

We assess how mixing behavior depends on temperature and sequence length using two complementary diagnostics\. At high temperatures, we run Glauber dynamics on BERT\-base\-uncased starting from MS MARCO passages and measure semantic drift via cosine distanced​\(xt,x0\)=1−cos⁡\(ϕ​\(xt\),ϕ​\(x0\)\)d\(x\_\{t\},x\_\{0\}\)=1\-\\cos\(\\phi\(x\_\{t\}\),\\phi\(x\_\{0\}\)\)in Jina Embeddings v4 space \(Appendix[B](https://arxiv.org/html/2605.16378#A2)\); we use the hitting time tod=1\.0d=1\.0as our mixing diagnostic\. The threshold1\.01\.0sits below saturation in the fast\-mixing regime \(Figure[3](https://arxiv.org/html/2605.16378#S6.F3)a\) and is rarely reached at low temperatures within our step budget; the qualitative shape of the results is robust to threshold choice in\[0\.4,1\.0\]\[0\.4,1\.0\]\.

At sufficiently high temperatures \(τ≳1\\tau\\gtrsim 1\), embedding distance grows logarithmically with sequence length at fixed time, and hitting times scale asC​\(τ\)​n​log⁡nC\(\\tau\)\\,n\\log n— consistent with the contraction theorem \(Theorem[5](https://arxiv.org/html/2605.16378#Thmconj5)\)\. Figure[3](https://arxiv.org/html/2605.16378#S6.F3)documents this scaling atτ=1\.0\\tau=1\.0\(left, embedding saturation\) andτ=1\.4\\tau=1\.4\(right,n​log⁡nn\\log nfit to hitting times\)\. The empirical fast\-mixing boundary sits below the contraction threshold; see[5\.2](https://arxiv.org/html/2605.16378#S5.SS2)\.

![Refer to caption](https://arxiv.org/html/2605.16378v1/Screenshot_PM.png)\(a\)Embedding distanced​\(xT,x0\)d\(x\_\{T\},x\_\{0\}\)vs\. sequence length atτ=1\.0\\tau=1\.0,T=104T=10^\{4\}steps \(100 trials per length\)\. Distance saturates logarithmically, consistent with fast mixing\.
![Refer to caption](https://arxiv.org/html/2605.16378v1/1.4_fit.png)\(b\)C​\(τ\)​n​log⁡nC\(\\tau\)\\,n\\log nfit to median hitting times atτ=1\.4\\tau=1\.4\(50 trials per length, cutoff 1000 steps\)\. The fit is tight across all tested lengths\.

Figure 3:Evidence forC​\(τ\)​n​log⁡nC\(\\tau\)\\,n\\log nmixing at high temperature on BERT\-base\-uncased\.We further probe the mixing\-time dependence on temperature and sequence length with a coupling mechanism\. For each pair\(τ,n\)\(\\tau,n\)two chains initialized from independent MS MARCO passages are evolved under a maximal coupling at the same site, and we record the first step at which they agree\. The transition from no\-coupling\-within\-budget to fast coupling is centered aroundτ≈1\.5\\tau\\approx 1\.5–22, with the boundary shifting to higherτ\\tauasnngrows\. The mixing\-time crossover qualitatively matches the regimes characterized in Section[5](https://arxiv.org/html/2605.16378#S5)\. However, the complex interactions of natural language induced by the MLM create a smoother transition boundary than exists in the physical Ising model for highnn; see Section[7](https://arxiv.org/html/2605.16378#S7)\.

### 6\.2Recurrent Semantic Basins in Long\-Run Dynamics

Long Glauber trajectories reveal a recurring phenomenon: chains often lose their initial semantic identity and move through multiple semantically coherent regions of text space\. We refer to these regions as semantic basins\. Some basins are short\-lived, while others persist for many updates or are revisited repeatedly\.

In this section, we use political content as a case study of such a basin\. This lets us ask whether long\-run masked\-token dynamics merely diffuse away from the initial prompt, or whether they repeatedly enter recognizable semantic regions\.

#### 6\.2\.1Politics as a Recurrent Basin in BERT

We ran 50 Glauber chains onbert\-base\-uncased\(5 topics×\\times10 seeds\) for 10,000 steps atτ=1\.0\\tau=1\.0, recording topic scores every 200 steps with thefacebook/bart\-large\-mnlizero\-shot classifier over nine candidate labels\. We report mean politics scores and original seed\-topic scores, which measure recurrence into a political semantic region and loss of initialization\-topic identity, respectively\. The uniform\-label baseline is1/9≈0\.1111/9\\approx 0\.111\.

Table 3:BERT political\-topic recurrence and loss of initialization\-topic identity\. Left: mean politics score at step 0 vs\. step 10,000\. Right: politics score compared with the original seed\-topic score\. Baseline=0\.111=0\.111\.\(a\) Politics score

\(b\) Politics vs\. seed topic

Every topic shows an increase in mean politics score\. Food is the only topic whose endpoint mean crosses the baseline, driven by two chains ending in strongly political regions with scores0\.8760\.876and0\.4970\.497\. However, endpoint scores understate the recurrence effect: 46 of 50 chains cross the politics baseline at least once, with transient peaks as high as0\.9790\.979\.

As a robustness check, DeBERTa\-v3 scoring gives the same qualitative pattern: politics scores increase for all five topics, and 48 of 50 chains visit above\-baseline political regions\. Meanwhile, seed\-topic scores fall sharply in every case, showing that chains lose their initial topical identity rather than remaining near the starting semantic class\.

We also compare endpoint political\-content recurrence acrossbert\-base\-uncased,roberta\-base, andModernBERT\-base; full endpoint values are reported in Appendix[B\.5](https://arxiv.org/html/2605.16378#A2.SS5)\. RoBERTa shows the strongest endpoint recurrence in this preliminary comparison, with two topics crossing the baseline, while ModernBERT shows the weakest endpoint recurrence, with no topics crossing the baseline\. The observed long\-lived content also differs by model: RoBERTa chains tend to settle into news\-like or multilingual political fragments, while ModernBERT chains more often enter instruction\-style prompts or code\-like regions\.

#### 6\.2\.2Interpretation

These results are best understood as evidence for metastable semantic basins rather than directed movement toward politics\. Once chains lose their initial topical identity, they explore multiple basins in the model\-induced text space\. Political content is one interpretable basin that is often reached, but it is not an absorbing endpoint of the dynamics\.

Persistence depends on a basin’s effective depth: regions with larger local score margins or fewer likely escape moves are harder to leave\. Thus, high transient politics scores and occasional political endpoints suggest recurrent entry into a political semantic region\. More broadly, Glauber dynamics serves as a diagnostic for the semantic basin structure induced by masked language models\.

## 7Discussion, Conclusion and Limitations

##### Conclusion\.

We have studied the Markov chain induced by iterative masked\-token resampling in masked language models through the lens of Glauber dynamics\. The rectangle test certifies that MLM conditionals are fundamentally incompatible with any joint distribution, a structural consequence of pseudo\-log\-likelihood training that persists across architectures and scales\. Under bounded cross\-token influence we establish anO​\(n​log⁡n\)O\(n\\log n\)mixing time upper bound; under a uniform local margin condition we establish an exponentially slow lower bound, and both regimes are empirically supported on BERT and RoBERTa\. Long\-run chains exhibit metastable trap states lasting hundreds to thousands of steps and recurrent entry into semantic basins, with political content serving as a measurable case study of such recurrence\. Unlike single\-mask probing or pseudo\-log\-likelihood scoring, the dynamical framework exposes global semantic structure that is invisible to existing methods, providing a new framework for understanding global structure and biases in masked language models\.

##### Limitations and Future Work

Empirically, BERT mixes faster than the bound established in[5](https://arxiv.org/html/2605.16378#Thmconj5)predicts\. We conjecture this is because the chain rapidly leaves coherent attractors and spends most of its time in incoherent configurations where typical pairwise influence is much smaller thanα​\(τ\)\\alpha\(\\tau\)\. A complete characterization — for instance via a context\-averaged argument that integrates over the stationary distribution rather than taking worst\-case suprema — is left to future work\. Relatedly, the cross\-over from slow to fast mixing does not seem to sharpen asnnincreases\. Fully explaining this discrepancy would require further mechanistic analysis\.

We do not experimentally analyze how incompatibility translates to deviation between the empirical stationary distribution and pseudo\-likelihood scores\. Additionally, our characterization of recurrent basins relies on zero\-shot topic classifiers; finer\-grained semantic analysis is left to future work\. Finally, we do not provide a closed\-form characterization ofμτ\\mu\_\{\\tau\}; preliminary Lyapunov\-function approximations rank sequences by occurrence probability but do not matchμτ\\mu\_\{\\tau\}quantitatively\.

## References

- \[1\]J\. Austin, D\. D\. Johnson, J\. Ho, D\. Tarlow, and R\. van den Berg\(2021\)Structured denoising diffusion models in discrete state\-spaces\.InAdvances in Neural Information Processing Systems,Vol\.34,pp\. 17981–17993\.Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px2.p1.1)\.
- \[2\]Y\. Belinkov\(2022\)Probing classifiers: promises, shortcomings, and advances\.Computational Linguistics48\(1\),pp\. 207–219\.Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px3.p1.1)\.
- \[3\]A\. Conneau and G\. Lample\(2019\)Cross\-lingual language model pretraining\.Advances in neural information processing systems32\.Cited by:[§1](https://arxiv.org/html/2605.16378#S1.p1.1)\.
- \[4\]J\. Devlin, M\. Chang, K\. Lee, and K\. Toutanova\(2019\)BERT: pre\-training of deep bidirectional transformers for language understanding\.InProceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,pp\. 4171–4186\.Cited by:[item 4](https://arxiv.org/html/2605.16378#S1.I1.i4.p1.1),[§1](https://arxiv.org/html/2605.16378#S1.p1.1)\.
- \[5\]S\. Gehman, S\. Gururangan, M\. Sap, Y\. Choi, and N\. A\. Smith\(2020\)Realtoxicityprompts: evaluating neural toxic degeneration in language models\.InFindings of the association for computational linguistics: EMNLP 2020,pp\. 3356–3369\.Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px3.p1.1)\.
- \[6\]R\. J\. Glauber\(1963\)Time\-dependent statistics of the ising model\.Journal of Mathematical Physics4\(2\),pp\. 294–307\.Cited by:[§1](https://arxiv.org/html/2605.16378#S1.p3.1),[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px1.p1.1)\.
- \[7\]S\. Gong, M\. Li, J\. Feng, Z\. Wu, and L\. Kong\(2022\)Diffuseq: sequence to sequence text generation with diffusion models\.arXiv preprint arXiv:2210\.08933\.Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px2.p1.1)\.
- \[8\]Z\. He, T\. Sun, Q\. Tang, K\. Wang, X\. Huang, and X\. Qiu\(2023\)Diffusionbert: improving generative masked language models with diffusion models\.InProceedings of the 61st annual meeting of the association for computational linguistics \(volume 1: Long papers\),pp\. 4521–4534\.Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px2.p1.1)\.
- \[9\]D\. A\. Levin, Y\. Peres, and E\. L\. Wilmer\(2017\)Markov chains and mixing times\.2nd edition,American Mathematical Society\.Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px1.p1.1)\.
- \[10\]J\. Li, X\. Chen, E\. Hovy, and D\. Jurafsky\(2016\)Visualizing and understanding neural models in nlp\.InProceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,pp\. 681–691\.Cited by:[§1](https://arxiv.org/html/2605.16378#S1.p1.1)\.
- \[11\]X\. Li, J\. Thickstun, I\. Gulrajani, P\. S\. Liang, and T\. B\. Hashimoto\(2022\)Diffusion\-lm improves controllable text generation\.Advances in neural information processing systems35,pp\. 4328–4343\.Cited by:[§1](https://arxiv.org/html/2605.16378#S1.p2.1),[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px2.p1.1)\.
- \[12\]Y\. Liu, M\. Ott, N\. Goyal, J\. Du, M\. Joshi, D\. Chen, O\. Levy, M\. Lewis, L\. Zettlemoyer, and V\. Stoyanov\(2019\)RoBERTa: a robustly optimized bert pretraining approach\.arXiv preprint arXiv:1907\.11692\.Cited by:[item 4](https://arxiv.org/html/2605.16378#S1.I1.i4.p1.1)\.
- \[13\]A\. Lou, C\. Meng, and S\. Ermon\(2023\)Discrete diffusion modeling by estimating the ratios of the data distribution\.arXiv preprint arXiv:2310\.16834\.Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px2.p1.1)\.
- \[14\]M\. Nadeem, A\. Bethke, and S\. Reddy\(2021\)StereoSet: measuring stereotypical bias in pretrained language models\.InProceedings of the 59th annual meeting of the association for computational linguistics and the 11th international joint conference on natural language processing \(volume 1: long papers\),pp\. 5356–5371\.Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px3.p1.1)\.
- \[15\]N\. Nangia, C\. Vania, R\. Bhalerao, and S\. Bowman\(2020\)CrowS\-pairs: a challenge dataset for measuring social biases in masked language models\.InProceedings of the 2020 conference on empirical methods in natural language processing \(EMNLP\),pp\. 1953–1967\.Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px3.p1.1)\.
- \[16\]S\. S\. Sahoo, M\. Arriola, A\. Gokaslan, E\. M\. Marroquin, A\. M\. Rush, Y\. Schiff, J\. T\. Chiu, and V\. Kuleshov\(2024\)Simple and effective masked diffusion language models\.InAdvances in Neural Information Processing Systems,Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px2.p1.1)\.
- \[17\]J\. Salazar, D\. Liang, T\. Q\. Nguyen, and K\. Kirchhoff\(2020\)Masked language model scoring\.InProceedings of the 58th annual meeting of the association for computational linguistics,pp\. 2699–2712\.Cited by:[§1](https://arxiv.org/html/2605.16378#S1.p1.1)\.
- \[18\]E\. Sheng, K\. Chang, P\. Natarajan, and N\. Peng\(2019\)The woman worked as a babysitter: on biases in language generation\.InProceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing,pp\. 3407–3412\.Cited by:[§2](https://arxiv.org/html/2605.16378#S2.SS0.SSS0.Px3.p1.1)\.
- \[19\]C\. Sun, X\. Qiu, Y\. Xu, and X\. Huang\(2019\)How to fine\-tune bert for text classification?\.InChina national conference on Chinese computational linguistics,pp\. 194–206\.Cited by:[§1](https://arxiv.org/html/2605.16378#S1.p1.1)\.
- \[20\]I\. Tenney, P\. Xia, B\. Chen, A\. Wang, A\. Poliak, R\. T\. McCoy, N\. Kim, B\. Van Durme, S\. R\. Bowman, D\. Das,et al\.\(2019\)What do you learn from context? probing for sentence structure in contextualized word representations\.arXiv preprint arXiv:1905\.06316\.Cited by:[§1](https://arxiv.org/html/2605.16378#S1.p1.1)\.
- \[21\]A\. Wang and K\. Cho\(2019\)BERT has a mouth, and it must speak: bert as a markov random field language model\.InProceedings of the Workshop on Methods for Optimizing and Evaluating Neural Language Generation,pp\. 30–36\.Cited by:[§1](https://arxiv.org/html/2605.16378#S1.p2.1)\.
- \[22\]B\. Warner, A\. Chaffin, B\. Clavié, O\. Weller, O\. Hallström, S\. Taghadouini, A\. Gallagher, R\. Biswas, F\. Ladhak, T\. Aarsen,et al\.\(2025\)Smarter, better, faster, longer: a modern bidirectional encoder for fast, memory efficient, and long context finetuning and inference\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 2526–2547\.Cited by:[item 4](https://arxiv.org/html/2605.16378#S1.I1.i4.p1.1)\.

## Appendix ATechnical appendices and supplementary material

Technical appendices with additional results, figures, graphs, and proofs may be submitted with the paper submission before the full submission deadline \(see above\)\. You can upload a ZIP file for videos or code, but do not upload a separate PDF file for the appendix\. There is no page limit for the technical appendices\. Note: Think of the appendix as “optional reading” for reviewers\. The paper must be able to stand alone without the appendix; for example, adding critical experiments that support the main claims to an appendix is inappropriate\.

### A\.1Measuring Token Influence Functions and Score Margins

Theorems[5](https://arxiv.org/html/2605.16378#Thmconj5)and[8](https://arxiv.org/html/2605.16378#Thmconj8)are structural: they apply to any chain satisfying their respective hypotheses\. We now empirically estimate temperature conditions such that BERT operates in the parameter regimes these theorems describe\.

##### Influence coefficients and the fast\-mixing threshold\.

We estimateα​\(τ\)=maxi​∑j≠ici​j​\(τ\)\\alpha\(\\tau\)=\\max\_\{i\}\\sum\_\{j\\neq i\}c\_\{ij\}\(\\tau\)directly by computing TV distances between conditionals at siteiias we vary the token at sitejj, averaged over multiple base contexts on a 14\-token seed sentence\. The empirical estimate is a lower bound on eachci​j​\(τ\)c\_\{ij\}\(\\tau\), and hence onα​\(τ\)\\alpha\(\\tau\)\. We obtainα​\(10\)≳1\.04\\alpha\(10\)\\gtrsim 1\.04andα​\(11\)≳0\.94\\alpha\(11\)\\gtrsim 0\.94, so the contraction sufficient conditionα​\(τ\)<1\\alpha\(\\tau\)<1requires at leastτ\>10\\tau\>10, roughly an order of magnitude above the empirical fast\-mixing boundaryτ≈1\.5\\tau\\approx 1\.5\(Section[6\.1](https://arxiv.org/html/2605.16378#S6.SS1)\)\. The gap reflects thatα​\(τ\)\\alpha\(\\tau\)is a supremum over both contexts and update sites, dominated by coherent contexts where BERT’s conditionals are sharply peaked; typical chain configurations are less coherent and exhibit smaller effective pairwise influence\.

##### Score margins and trap verification\.

Theorem[8](https://arxiv.org/html/2605.16378#Thmconj8)requires a metastable basinBBsatisfying the uniform local margin condition \(Assumption[1](https://arxiv.org/html/2605.16378#Thmass1)\)\. We verify this directly by running 30 Glauber chains of10,00010\{,\}000steps atτ=1\.0\\tau=1\.0, detecting traps via a rolling embedding\-distance criterion \(flagging windows where the 300\-step mean cosine drift falls below 0\.12\), and then measuring the per\-position score gapΔi​\(x\)=si​\(xi;x−i\)−maxa≠xi⁡si​\(a;x−i\)\\Delta\_\{i\}\(x\)=s\_\{i\}\(x\_\{i\};\\,x\_\{\-i\}\)\-\\max\_\{a\\neq x\_\{i\}\}s\_\{i\}\(a;\\,x\_\{\-i\}\)for each detected trap state\. We find 17 trap states \(mean duration 671 steps, range 150–4,950\), which partition into two types\.Perfect traps\(4 of 17\) satisfy Assumption[1](https://arxiv.org/html/2605.16378#Thmass1)exactly:every token is BERT’s argmax withΔ∗\>0\\Delta^\{\*\}\>0\.The extreme case is a 15\-token string of periods \(\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\),withΔ¯=9\.14\\bar\{\\Delta\}=9\.14,Δ∗=7\.46\\Delta^\{\*\}=7\.46, andP​\(current token\)≥0\.997P\(\\text\{current token\}\)\\geq 0\.997at every position; this trap persisted for 4,950 of 10,000 steps\. A semantically richer example, “it has been used as the theme song for jesus christ superstar,” achievesΔ∗=0\.56\\Delta^\{\*\}=0\.56and held for 650 steps\. We hypothesize that factual specificity creates strong traps because training data nearly uniquely determines each token given the rest\.Approximate traps\(13 of 17\) have at least one position whereΔi<0\\Delta\_\{i\}<0and thus do not satisfy the sufficient conditions, yet persist for 150–1,200 steps\. The mechanism is collective stability: strongly\-locked surrounding structure maintains metastability even when individual tokens are locally suboptimal\. A recurring example is the family of scoring sentences \(winners were awarded 2 points, while losers would be awarded 1 point”\), where while” \(Δ=−1\.06\\Delta=\-1\.06\) and would” \(Δ=−0\.39\\Delta=\-0\.39\) are not argmax choices, yetΔ¯=4\.12\\bar\{\\Delta\}=4\.12across the full sentence\. Similarly, four traps in a single chain share the Wikipedia template the population density was \(…\) \[number\] per square mile,” cycling within this family for over 3,000 combined steps\. This suggests the energy landscape contains basin*neighborhoods*— clusters of related metastable states — rather than isolated fixed points\.

Table 4:Representative trap states detected across 30 chains \(τ=1\.0\\tau=1\.0,10,00010\{,\}000steps each\)\. Duration in Glauber steps\.Δ¯\\bar\{\\Delta\}= mean score gap;Δ∗\\Delta^\{\*\}= minimum\. Perfect traps satisfy Assumption[1](https://arxiv.org/html/2605.16378#Thmass1); approximate traps are metastable despite violating it\.
##### Tightness of the slow\-mixing bound\.

For perfect traps, Theorem[8](https://arxiv.org/html/2605.16378#Thmconj8)predictstmix​\(1/4\)≥14​\|V\|​eΔ∗/τt\_\{\\mathrm\{mix\}\}\(1/4\)\\geq\\tfrac\{1\}\{4\|V\|\}\\,e^\{\\Delta\_\{\*\}/\\tau\}\. BecauseΔ∗/τ<ln⁡\|V\|≈10\.3\\Delta\_\{\*\}/\\tau<\\ln\|V\|\\approx 10\.3for all observed traps, the predicted bound falls below one step \(Trap 1: predicted≈0\.014\\approx 0\.014, observed4,9504\{,\}950\), so the bound confirms positive escape time but is not quantitatively informative at these gap sizes\. The\|V\|\|V\|prefactor and the worst\-case minimum\-gap definition ofΔ∗\\Delta\_\{\*\}are the main sources of looseness; the mean gapΔ¯\\bar\{\\Delta\}correlates better with observed duration empirically but lacks a corresponding rigorous bound\.

## Appendix BAdditional Experimental Details

### B\.1Experimental Setup

##### Model\.

We use BERT\-base\-uncased \(Devlin et al\., 2019\) accessed via the HuggingFace Transformers library\.

##### Seed texts\.

Unless otherwise specified, initial sequencesx0x\_\{0\}are drawn from the MS MARCO passage dataset truncated to a specified number of tokensnn\.

##### Embedding model\.

For measuring semantic drift, we use Sentence Transformers\.

##### Classifiers\.

For topic and sentiment analysis, we use Hugging Face pipelines\. For sentiment we use the sentiment pipeline, initialized with pipeline\("sentiment\-analysis"\) and for topics we use the classifier pipeline pipeline\("zero\-shot\-classification", model="facebook/bart\-large\-mnli"\), for a list of candidate topics :’politics’, ’health’, ’pop culture’, ’sport’, ’food’, ’science’, ’technology’, ’finance’, ’education’, ’environment’, and ’art’\.

##### Hardware\.

Experiments were conducted on Google Colab using T4 and A100 GPUs\.

##### Experimental protocols\.

We use two main protocols for studying mixing time:

- •Version 1 \(fixed time\):FixTTsteps, measured​\(xT,x0\)d\(x\_\{T\},x\_\{0\}\)as a function of sequence lengthnn\.
- •Version 2 \(hitting time\):Fix target distanceRR, measure the hitting timeTR=min⁡\{t:d​\(xt,x0\)≥R\}T\_\{R\}=\\min\\\{t:d\(x\_\{t\},x\_\{0\}\)\\geq R\\\}as a function ofnn\.

### B\.2Hyperparameters

Unless otherwise specified:

- •Temperature:τ=1\.0\\tau=1\.0
- •Steps:T=104T=10^\{4\}
- •Seed text length: 20 tokens
- •Trials per condition: 100

### B\.3Embedding Model Details

We use Jina Embeddings v4, accessed via the HuggingFace sentence\-transformers library\. The model produces 768\-dimensional embeddings optimized for semantic similarity\.

### B\.4Measuring Mixing via Embeddings

We measure drift and mixing using text embeddings\. We use a pretrained sentence embedding modelϕ:𝒳→ℝd\\phi:\\mathcal\{X\}\\to\\mathbb\{R\}^\{d\}\(Jina Embeddings v4 withd=768d=768\) to project sequences into a continuous semantic space\. We define the*embedding distance*from the initial state as:

d​\(xt,x0\)=1−cos⁡\(ϕ​\(xt\),ϕ​\(x0\)\)d\(x\_\{t\},x\_\{0\}\)=1\-\\cos\(\\phi\(x\_\{t\}\),\\phi\(x\_\{0\}\)\)\(B\.1\)wherecos⁡\(⋅,⋅\)\\cos\(\\cdot,\\cdot\)denotes cosine similarity\. This embedding technique quantifies the drift from the original meaning, which we call semantic mixing\.

### B\.5Endpoint Cross\-Model Political\-Content Recurrence

Table 5:Preliminary endpoint cross\-model comparison using BART\-MNLI\. BERT values use the expanded 10\-seed\-per\-topic experiment; RoBERTa and ModernBERT values use 5 seeds per topic\. Values are mean politics scores at step 10,000\.✓\\checkmarkmarks topics crossing the baseline of0\.1110\.111\.
### B\.6PCA Analysis and Trajectory Visualization

We applied two\-dimensional PCA to sentence embeddings from theSentenceTransformermodel to visualize the temporal evolution of generated sequences, with points colored from warm \(early\) to cool \(late\) steps and sequential points connected by lines\. The resulting trajectories \(Figures[1](https://arxiv.org/html/2605.16378#S1.F1)and[4](https://arxiv.org/html/2605.16378#A4.F4)\) reveal clear point clusters corresponding to repeated identical sentences, which we interpret as traps in the projected space; note, however, that additional traps may exist in the remaining 766 dimensions not visible in this projection\.

## Appendix CExtended Example Trajectories

The examples in this appendix illustrate the qualitative behaviors predicted by the theoretical results of Section 5\. Sections[C\.1](https://arxiv.org/html/2605.16378#A3.SS1)and[C\.3](https://arxiv.org/html/2605.16378#A3.SS3)ground the trap and metastability phenomena in concrete outputs\. Section[C\.4](https://arxiv.org/html/2605.16378#A3.SS4)documents how fixed prefixes create strong semantic attractors, accelerating the drift described quantitatively in Section 6\.3\.

### C\.1Characterization of Trap States

A striking phenomenon at moderate\-to\-low temperatures is the emergence oftrap states: configurations where the chain remains stuck for thousands of steps\. Formally, a trap corresponds to a metastable basinBBsatisfying the local margin condition of Assumption 1; see Table 5 for the full catalogue of traps detected across 30 chains, including their mean and minimum score gapsΔ¯\\bar\{\\Delta\}andΔ∗\\Delta^\{\*\}\.

### C\.2Examples of Trap States

We document two categories of traps\. In both cases the chain enters the trap gradually: embedding distance from the initial state stops growing and the 300\-step cosine drift falls below 0\.12 \(the detection threshold of Appendix A\.1\), where it remains until an escape event, typically triggered by a low\-probability token substitution at the weakest\-scoring position\.

##### Semantically coherent traps\.

Some traps are grammatically correct and semantically meaningful\. These tend to be*perfect traps*in the sense of Table 5: every token is BERT’s argmax given its context, producing large positiveΔ∗\\Delta^\{\*\}\. We hypothesize, consistent with Appendix A\.1, that factual or topical specificity is the key driver: when the surrounding context nearly uniquely determines each token in the training distribution, the resulting score margins are large and the basin is deep\.

> \[‘‘guacamole’’ trap, steps 2k\-\-10k\]In 20th century England, ornamental guacamole was made by filling wooden sauce jars with vegetables, and served with boiled cigars\.

> \[‘‘Brett Kavanaugh’’ trap from step 8k\]Donald Trump said that he would support Brett Kavanaugh for the Supreme Court, though he will think about future judicial nominations\. But for now, Brett Kavanaugh is in fact dead\.

Note that both of these traps are factually wrong or internally contradictory, yet locally stable: BERT’s conditional distributions are shaped by co\-occurrence statistics in training data, not by global factual consistency\.

> \[‘‘kissing modern European men’’ trap, steps 6k\-\-10k\]The fool always says, don’t be jealous of kissing modern European men, but that’s a nonsense statement\. You were never meant to be jealous of kissing modern European men\.

> \[‘‘Night of the Living Dead’’ trap from step 8k\]It’s a shame that Night of the Living Dead featured so many creepy aliens we never knew existed, so who can blame us for asking? What are your two favorite characters?

##### Nonsensical traps\.

Other traps are grammatically broken yet locally stable — an instance of the*approximate trap*regime of Table 5, where collective stability across the sentence maintains metastability even when individual positions are not argmax choices\. The mechanism is mutual reinforcement: each token is assigned high conditional probability by the others, even though no coherent global interpretation exists\.

> \[step 8k\]It can be caused by one or more of the three coathoses, the voltage on top of the trap used to control movement of the contents from one part of the wall to another\.

> \[step 10k\]The spin is defined in one or more of the following ways: by decreasing the periodic table so that no sufficiently large spike exists, or by increasing the periodic table again through time until a sufficiently large spike is observed\.

### C\.3Temperature Regimes and Sentence Coherence

At low temperatures \(τ≤0\.5\\tau\\leq 0\.5\), we observe dramatically slower mixing, consistent with the slow\-mixing regime of Figure 2\. The chain frequently becomes trapped in metastable states for extended periods, and embedding distance from the initial state \(Equation B\.1\) grows far more slowly than theC​\(τ\)​n​log⁡nC\(\\tau\)n\\log ntrend observed at high temperature\.

For example, atτ=0\.1\\tau=0\.1, chains initialized with a rabies passage remained within cosine distance≈0\.05\{\\approx\}0\.05of the initial embedding for thousands of steps, and the text preserved much of the original meaning:

> \[temp 0\.1, steps 3k–8k\]:Population control and vaccination campaigns have prevented the spread of rabies from spreading to a number of countries around the world\.

Atτ=0\.01\\tau=0\.01, the text barely changed over 10k steps \(cosine distance<0\.01<0\.01\):

> \[temp 0\.01, step 1k to 10k\]:Birth control and vaccination programs have prevented the spread of rabies among children in a number of parts of the world\.

At very high temperatures \(τ\>2\\tau\>2\), the chain produces nonsensical output as token selection becomes nearly uniform, destroying all semantic structure:

> \[temp=10, step 10k\]Py specific CNBCagged guarantees easiest reeling coin Lung NATillusionteen torque KEY a speculateHon Keystone MaidenHideDay Dustin

> \[temp=100, step 10k\]HAHAHAHAexpected Downtownasin Company287 vetting vergeardless od iterationAllows Garage climaxstud oranges symptoms slots moveSTR Christoksovsky

### C\.4Prefix\-Conditioned Attractors

A fixed prefix constrains every resampling step: the tokens covered by the prefix are never updated, biasing the conditional distributions at all other positions\. This effectively narrows the reachable state space and can concentrate probability mass on a specific semantic basin, accelerating the drift discussed in Section 6\.3\. The following examples illustrate how the identity encoded in the prefix shapes the attractor the chain converges to\.

“Albert Einstein said that…”

- •…he never expressed his thoughts or feelings to his audience, but they always expressed their opinion: everyone needs to do as much good work as we can\.
- •…general relativity is an extremely tough problem\. Because it can’t be solved by quantum observation alone, it would be quite difficult to solve it more broadly\.

“Elvis Presley said that…”

- •…Bojangles had texted him right before the press conference, making it clear to him that they plan to spend as much time together as they can\.

“LeBron James said that…”

- •…with three and a half games to play, ‘I’ve got to be able to make the impact and get as much playing time as possible\.’

“The little kid said that…”

- •…the recordings could be used by more people to exploit the footage, and added that it might be used as a communications tool for terrorists planning another attack\.

The last example illustrates that prefix\-conditioned attractors are determined by training co\-occurrence, not semantic plausibility: “the little kid said that” shares syntactic structure with news\-report speech attributions, pulling the chain toward the same political and crime\-adjacent content as directly political prefixes\. This is the same mechanism responsible for the drift documented in Section 6\.3, and the “Donald Trump said that” prefix discussed there represents the extreme case: chains become political almost immediately, with the prefix providing essentially no barrier to the political attractor\.

## Appendix DSupplemental Figures

![Refer to caption](https://arxiv.org/html/2605.16378v1/pca3500.png)Figure 4:PCA projections of embedding trajectories at 3500 steps\. Warm colors indicate early steps, cool colors indicate later steps; clusters correspond to traps in the projected space\.Initial:“My favorite fruits are apples, but I like green apples more than red ones\.”Final:“But the papers from the Committee on Reconciliation are worth taking a look anyway\.”![Refer to caption](https://arxiv.org/html/2605.16378v1/inconsistency_distribution.png)Figure 5:Distribution of rectangle incompatibility with BERT; methodology described in Section[4](https://arxiv.org/html/2605.16378#S4)\.![Refer to caption](https://arxiv.org/html/2605.16378v1/inconsistency_influence.png)Figure 6:Token\-level Influence Amplifies Rectangle Incompatibility\.Influence​\(i,j\)\\text\{Influence\}\(i,j\)is measured by absolute change in the log\-probability of the token at positioniiwhen the token atjjis swapped; here we takemax⁡\(Influence​\(i,j\),Influence​\(j,i\)\)\.\\max\(\\text\{Influence\}\(i,j\),\\text\{Influence\}\(j,i\)\)\.![Refer to caption](https://arxiv.org/html/2605.16378v1/mixing_crossover.png)Figure 7:Fraction of 100 initialized chains achieving embedding distancedt≥\{0\.4,0\.7,1\.0\}d\_\{t\}\\geq\\\{0\.4,0\.7,1\.0\\\}from starting sequence as a function of temperature and sequence length\. Mini\-LM 384\-dimensional embeddings applied every 5 steps; cutoff at 5000 steps\.
## Appendix EDeferred Proofs

###### Proposition 9\.

For eachτ\>0\\tau\>0,PτP\_\{\\tau\}is a Markov kernel on𝐗\{\\bm\{X\}\}\. Ifpθ,τ​\(a∣x−i\)\>0p\_\{\\theta,\\tau\}\(a\\mid x\_\{\-i\}\)\>0for alli,x−i,ai,x\_\{\-i\},a, thenPτP\_\{\\tau\}is irreducible and aperiodic\.

###### Proof\.

Nonnegativity is immediate\. For fixedx∈𝑿x\\in\{\\bm\{X\}\},

∑x′∈𝑿Pτ​\(x,x′\)=1n​∑i=1n∑x′∈𝑿𝟏x−i=x−i′​pθ,τ​\(xi′∣x−i\)\.\\sum\_\{x^\{\\prime\}\\in\{\\bm\{X\}\}\}P\_\{\\tau\}\(x,x^\{\\prime\}\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\sum\_\{x^\{\\prime\}\\in\{\\bm\{X\}\}\}\\mathbf\{1\}\_\{x\_\{\-i\}=x^\{\\prime\}\_\{\-i\}\}p\_\{\\theta,\\tau\}\(x\_\{i\}^\{\\prime\}\\mid x\_\{\-i\}\)\.For fixedii, the constraintx−i′=x−ix^\{\\prime\}\_\{\-i\}=x\_\{\-i\}leaves only theii\-th coordinate free, so

∑x′∈𝑿𝟏x−i=x−i′​pθ,τ​\(xi′∣x−i\)=∑a∈𝑽pθ,τ​\(a∣x−i\)=1\.\\sum\_\{x^\{\\prime\}\\in\{\\bm\{X\}\}\}\\mathbf\{1\}\_\{x\_\{\-i\}=x^\{\\prime\}\_\{\-i\}\}p\_\{\\theta,\\tau\}\(x\_\{i\}^\{\\prime\}\\mid x\_\{\-i\}\)=\\sum\_\{a\\in\\bm\{V\}\}p\_\{\\theta,\\tau\}\(a\\mid x\_\{\-i\}\)=1\.Hence

∑x′∈𝑿Pτ​\(x,x′\)=1n​∑i=1n1=1\.\\sum\_\{x^\{\\prime\}\\in\{\\bm\{X\}\}\}P\_\{\\tau\}\(x,x^\{\\prime\}\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}1=1\.Irreducibility: for anyx,y∈𝑿x,y\\in\{\\bm\{X\}\}, change the coordinates ofxxone by one to matchyy\. Each prescribed single\-site change has positive probability\.Aperiodicity: for everyx∈𝑿x\\in\{\\bm\{X\}\},

Pτ​\(x,x\)=1n​∑i=1npθ,τ​\(xi∣x−i\)\>0\.P\_\{\\tau\}\(x,x\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}p\_\{\\theta,\\tau\}\(x\_\{i\}\\mid x\_\{\-i\}\)\>0\.Thus every state has a self\-loop\.∎

###### Theorem 10\(High\-temperature contraction\)\.

Assumeα​\(τ\)<1\\alpha\(\\tau\)<1\. Then for the Hamming metric

dH​\(x,y\):=∑i=1n𝟏xi≠yi,d\_\{H\}\(x,y\):=\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\_\{x\_\{i\}\\neq y\_\{i\}\},there exists a coupling of the chain such that for allx,y∈𝐗x,y\\in\{\\bm\{X\}\},

𝔼​\[dH​\(X1,Y1\)∣X0=x,Y0=y\]≤\(1−1−α​\(τ\)n\)​dH​\(x,y\)\.\\mathbb\{E\}\[d\_\{H\}\(X\_\{1\},Y\_\{1\}\)\\mid X\_\{0\}=x,Y\_\{0\}=y\]\\leq\\left\(1\-\\frac\{1\-\\alpha\(\\tau\)\}\{n\}\\right\)d\_\{H\}\(x,y\)\.Consequently,

tmix​\(ε\)≤n1−α​\(τ\)​\(log⁡n\+log⁡1ε\),t\_\{\\mathrm\{mix\}\}\(\\varepsilon\)\\leq\\frac\{n\}\{1\-\\alpha\(\\tau\)\}\\left\(\\log n\+\\log\\frac\{1\}\{\\varepsilon\}\\right\),wheretmix​\(ε\)t\_\{\\mathrm\{mix\}\}\(\\varepsilon\)denotes total\-variation mixing time\.

###### Proof\.

Fixx,y∈𝑿x,y\\in\{\\bm\{X\}\}\. We couple one step as follows: choose the same update siteI∼Unif​\[n\]I\\sim\\mathrm\{Unif\}\[n\]in both chains\. Conditional onI=iI=i, couple the two resampled tokens using a maximal coupling of

pθ,τ\(⋅∣x−i\)andpθ,τ\(⋅∣y−i\)\.p\_\{\\theta,\\tau\}\(\\cdot\\mid x\_\{\-i\}\)\\quad\\text\{and\}\\quad p\_\{\\theta,\\tau\}\(\\cdot\\mid y\_\{\-i\}\)\.Under a maximal coupling, the probability of disagreement at the updated site is exactly the total variation distance between these two measures\.It suffices to analyze the casedH​\(x,y\)=1d\_\{H\}\(x,y\)=1by path coupling\. Letx,yx,ydiffer only at sitejj\.IfI=jI=j, thenx−j=y−jx\_\{\-j\}=y\_\{\-j\}, so the two conditional distributions are identical\. Hence under the coupling, the resampled tokens agree almost surely and therefore

dH​\(X1,Y1\)=0\.d\_\{H\}\(X\_\{1\},Y\_\{1\}\)=0\.IfI=i≠jI=i\\neq j, then all coordinates except possiblyiiremain unchanged\. Sincexxandyydiffer only at sitejj, we have

ℙ\(X1i≠Y1i∣I=i\)=∥pθ,τ\(⋅∣x−i\)−pθ,τ\(⋅∣y−i\)∥TV≤ci​j\(τ\)\.\\mathbb\{P\}\(X\_\{1\}^\{i\}\\neq Y\_\{1\}^\{i\}\\mid I=i\)=\\\|p\_\{\\theta,\\tau\}\(\\cdot\\mid x\_\{\-i\}\)\-p\_\{\\theta,\\tau\}\(\\cdot\\mid y\_\{\-i\}\)\\\|\_\{\\mathrm\{TV\}\}\\leq c\_\{ij\}\(\\tau\)\.The original disagreement at sitejjpersists because sitejjis not updated\. Thus

𝔼​\[dH​\(X1,Y1\)∣I=i\]≤1\+ci​j​\(τ\)\.\\mathbb\{E\}\[d\_\{H\}\(X\_\{1\},Y\_\{1\}\)\\mid I=i\]\\leq 1\+c\_\{ij\}\(\\tau\)\.Averaging over the update site,

𝔼​\[dH​\(X1,Y1\)\]≤1n⋅0\+1n​∑i≠j\(1\+ci​j​\(τ\)\)=1−1n\+1n​∑i≠jci​j​\(τ\)≤1−1−α​\(τ\)n\.\\mathbb\{E\}\[d\_\{H\}\(X\_\{1\},Y\_\{1\}\)\]\\leq\\frac\{1\}\{n\}\\cdot 0\+\\frac\{1\}\{n\}\\sum\_\{i\\neq j\}\(1\+c\_\{ij\}\(\\tau\)\)=1\-\\frac\{1\}\{n\}\+\\frac\{1\}\{n\}\\sum\_\{i\\neq j\}c\_\{ij\}\(\\tau\)\\leq 1\-\\frac\{1\-\\alpha\(\\tau\)\}\{n\}\.So the expected distance contracts by this factor for adjacent pairs\. By the Bubley–Dyer path coupling theorem, the same contraction extends to arbitrary pairs:

𝔼​\[dH​\(Xt,Yt\)\]≤\(1−1−α​\(τ\)n\)t​dH​\(x,y\)\.\\mathbb\{E\}\[d\_\{H\}\(X\_\{t\},Y\_\{t\}\)\]\\leq\\left\(1\-\\frac\{1\-\\alpha\(\\tau\)\}\{n\}\\right\)^\{t\}d\_\{H\}\(x,y\)\.Since total variation distance between two laws is bounded by the coupling disagreement probability, and disagreement probability is bounded by expected Hamming distance,

‖Pτt​\(x,⋅\)−Pτt​\(y,⋅\)‖TV≤ℙ​\(Xt≠Yt\)≤𝔼​\[dH​\(Xt,Yt\)\]\.\\\|P\_\{\\tau\}^\{t\}\(x,\\cdot\)\-P\_\{\\tau\}^\{t\}\(y,\\cdot\)\\\|\_\{\\mathrm\{TV\}\}\\leq\\mathbb\{P\}\(X\_\{t\}\\neq Y\_\{t\}\)\\leq\\mathbb\{E\}\[d\_\{H\}\(X\_\{t\},Y\_\{t\}\)\]\.Choosingyydistributed from stationarity and usingmaxx⁡dH​\(x,y\)≤n\\max\_\{x\}d\_\{H\}\(x,y\)\\leq n, we obtain

supx‖Pτt​\(x,⋅\)−μτ‖TV≤n​\(1−1−α​\(τ\)n\)t≤n​exp⁡\(−1−α​\(τ\)n​t\)\.\\sup\_\{x\}\\\|P\_\{\\tau\}^\{t\}\(x,\\cdot\)\-\\mu\_\{\\tau\}\\\|\_\{\\mathrm\{TV\}\}\\leq n\\left\(1\-\\frac\{1\-\\alpha\(\\tau\)\}\{n\}\\right\)^\{t\}\\leq n\\exp\\left\(\-\\frac\{1\-\\alpha\(\\tau\)\}\{n\}t\\right\)\.Thus it suffices to take

t≥n1−α​\(τ\)​\(log⁡n\+log⁡1ε\)\.t\\geq\\frac\{n\}\{1\-\\alpha\(\\tau\)\}\\left\(\\log n\+\\log\\frac\{1\}\{\\varepsilon\}\\right\)\.∎

###### Lemma 11\.

For alli≠ji\\neq jandτ\>0\\tau\>0,

ci​j​\(τ\)≤Δi​j4​τ\.c\_\{ij\}\(\\tau\)\\leq\\frac\{\\Delta\_\{ij\}\}\{4\\tau\}\.

###### Proof\.

Fix contextsx−i,y−ix\_\{\-i\},y\_\{\-i\}differing only at sitejj, and write

ua:=si​\(a;x−i\)/τ,va:=si​\(a;y−i\)/τ\.u\_\{a\}:=s\_\{i\}\(a;x\_\{\-i\}\)/\\tau,\\qquad v\_\{a\}:=s\_\{i\}\(a;y\_\{\-i\}\)/\\tau\.Letσ​\(u\),σ​\(v\)∈Δ​\(𝑽\)\\sigma\(u\),\\sigma\(v\)\\in\\Delta\(\\bm\{V\}\)denote the corresponding softmax distributions\. A standard softmax Lipschitz estimate with respect toℓ∞\\ell\_\{\\infty\}perturbations modulo additive constants gives

‖σ​\(u\)−σ​\(v\)‖TV≤14​\(maxa⁡\(ua−va\)−mina⁡\(ua−va\)\)\.\\\|\\sigma\(u\)\-\\sigma\(v\)\\\|\_\{\\mathrm\{TV\}\}\\leq\\frac\{1\}\{4\}\\left\(\\max\_\{a\}\(u\_\{a\}\-v\_\{a\}\)\-\\min\_\{a\}\(u\_\{a\}\-v\_\{a\}\)\\right\)\.Multiplying through by1/τ1/\\tauyields

∥pθ,τ\(⋅∣x−i\)−pθ,τ\(⋅∣y−i\)∥TV≤Δi​j4​τ\.\\\|p\_\{\\theta,\\tau\}\(\\cdot\\mid x\_\{\-i\}\)\-p\_\{\\theta,\\tau\}\(\\cdot\\mid y\_\{\-i\}\)\\\|\_\{\\mathrm\{TV\}\}\\leq\\frac\{\\Delta\_\{ij\}\}\{4\\tau\}\.Taking the supremum proves the claim\.∎

###### Theorem 12\(Low\-temperature exponentially small escape\)\.

Assume the uniform local margin condition on a basinBB\. Then for everyx∈Bx\\in B,

Pτ​\(x,Bc\)≤\|𝑽\|​e−Δ⋆/τ\.P\_\{\\tau\}\(x,B^\{c\}\)\\leq\|\\bm\{V\}\|e^\{\-\\Delta\_\{\\star\}/\\tau\}\.Consequently the conductance ofBBsatisfies

Φτ​\(B\):=∑x∈Bμτ​\(x\)​Pτ​\(x,Bc\)μτ​\(B\)≤\|𝑽\|​e−Δ⋆/τ\.\\Phi\_\{\\tau\}\(B\):=\\frac\{\\sum\_\{x\\in B\}\\mu\_\{\\tau\}\(x\)P\_\{\\tau\}\(x,B^\{c\}\)\}\{\\mu\_\{\\tau\}\(B\)\}\\leq\|\\bm\{V\}\|e^\{\-\\Delta\_\{\\star\}/\\tau\}\.If additionallyμτ​\(B\)≤12\\mu\_\{\\tau\}\(B\)\\leq\\frac\{1\}\{2\}, then

tmix​\(1/4\)≥14​\|𝑽\|​eΔ⋆/τ\.t\_\{\\mathrm\{mix\}\}\(1/4\)\\geq\\frac\{1\}\{4\|\\bm\{V\}\|\}e^\{\\Delta\_\{\\star\}/\\tau\}\.

###### Proof\.

Fixx∈Bx\\in B\. We first bound the probability of exitingBBin one step\. A transition can leaveBBonly if the updated siteiiis one whose change may exitBB, and then one must sample a tokena≠xia\\neq x\_\{i\}such thatx\(i→a\)∉Bx^\{\(i\\to a\)\}\\notin B\.For such a siteii, by the local margin assumption,

si​\(a;x−i\)≤si​\(xi;x−i\)−Δ⋆for all exit\-causing​a\.s\_\{i\}\(a;x\_\{\-i\}\)\\leq s\_\{i\}\(x\_\{i\};x\_\{\-i\}\)\-\\Delta\_\{\\star\}\\qquad\\text\{for all exit\-causing \}a\.Therefore

pθ,τ​\(a∣x−i\)=esi​\(a;x−i\)/τ∑b∈𝑽esi​\(b;x−i\)/τ≤e\(si​\(xi;x−i\)−Δ⋆\)/τesi​\(xi;x−i\)/τ=e−Δ⋆/τ\.p\_\{\\theta,\\tau\}\(a\\mid x\_\{\-i\}\)=\\frac\{e^\{s\_\{i\}\(a;x\_\{\-i\}\)/\\tau\}\}\{\\sum\_\{b\\in\\bm\{V\}\}e^\{s\_\{i\}\(b;x\_\{\-i\}\)/\\tau\}\}\\leq\\frac\{e^\{\(s\_\{i\}\(x\_\{i\};x\_\{\-i\}\)\-\\Delta\_\{\\star\}\)/\\tau\}\}\{e^\{s\_\{i\}\(x\_\{i\};x\_\{\-i\}\)/\\tau\}\}=e^\{\-\\Delta\_\{\\star\}/\\tau\}\.Summing over at most\|𝑽\|−1\|\\bm\{V\}\|\-1exit\-causing symbols and over the choice of site yields

Pτ​\(x,Bc\)≤1n​∑i=1n\(\|𝑽\|−1\)​e−Δ⋆/τ≤\|𝑽\|​e−Δ⋆/τ\.P\_\{\\tau\}\(x,B^\{c\}\)\\leq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\(\|\\bm\{V\}\|\-1\)e^\{\-\\Delta\_\{\\star\}/\\tau\}\\leq\|\\bm\{V\}\|e^\{\-\\Delta\_\{\\star\}/\\tau\}\.Now average with respect toμτ\\mu\_\{\\tau\}restricted toBB:

Φτ​\(B\)=1μτ​\(B\)​∑x∈Bμτ​\(x\)​Pτ​\(x,Bc\)≤\|𝑽\|​e−Δ⋆/τ\.\\Phi\_\{\\tau\}\(B\)=\\frac\{1\}\{\\mu\_\{\\tau\}\(B\)\}\\sum\_\{x\\in B\}\\mu\_\{\\tau\}\(x\)P\_\{\\tau\}\(x,B^\{c\}\)\\leq\|\\bm\{V\}\|e^\{\-\\Delta\_\{\\star\}/\\tau\}\.Finally, by the standard conductance lower bound on mixing time for finite Markov chains, ifμτ​\(B\)≤1/2\\mu\_\{\\tau\}\(B\)\\leq 1/2then

tmix​\(1/4\)≥14​Φτ​\(B\)\.t\_\{\\mathrm\{mix\}\}\(1/4\)\\geq\\frac\{1\}\{4\\Phi\_\{\\tau\}\(B\)\}\.Substituting the conductance estimate gives

tmix​\(1/4\)≥14​\|𝑽\|​eΔ⋆/τ\.t\_\{\\mathrm\{mix\}\}\(1/4\)\\geq\\frac\{1\}\{4\|\\bm\{V\}\|\}e^\{\\Delta\_\{\\star\}/\\tau\}\.∎