Technical Summary: Mixing Times of Glauber Dynamics on Masked Language Models

Problem Statement

Masked Language Models (MLMs), such as BERT, define local conditional distributions over tokens but do not inherently correspond to a consistent joint distribution over sequences. While these models are widely used for natural language understanding (NLU), their global stochastic behavior when used iteratively for generation remains poorly characterized. Existing interpretability methods, such as static embedding probes or pseudo-log-likelihood scoring, fail to capture global structural properties, such as model biases, structural attractors, or temporal phenomena like metastable semantic traps.

The central question addressed is: What global distributional behavior is induced when MLM conditionals are used iteratively for generation? Specifically, the authors investigate the mixing properties of the Markov chain formed by repeatedly masking and resampling tokens, a process modeled as Glauber dynamics.

Methodology

The authors model iterative masked-token resampling as a Glauber dynamics Markov chain on the discrete space of token sequences ($X = V^n$).

1. Glauber Dynamics Formulation:

   • At each step, a token position $i$ is selected uniformly at random.
   • The token $x_i$ is resampled from the temperature-scaled conditional distribution $p_{\theta, \tau}(\cdot | x_{-i})$ provided by the MLM.
   • The temperature parameter $\tau$ controls the sharpness of the conditional distribution.

2. Incompatibility Detection (The Rectangle Test):

   • To determine if the local conditionals correspond to a valid joint distribution, the authors introduce a "rectangle test."
   • For a sequence with two positions $i$ and $j$, they compare the log-probability ratios of swapping tokens along two different paths (e.g., $x \to y \to z$ vs. $x \to w \to z$).
   • If a compatible joint distribution exists, the sum of log-ratios along any path must telescope to the same value, resulting in an incompatibility metric $\delta = 0$.
   • $\delta \neq 0$ certifies that the conditionals are intrinsically incompatible with any joint distribution.

3. Theoretical Analysis of Mixing:

   • High-Temperature Regime: The authors define influence coefficients $c_{ij}(\tau)$ measuring how much changing token $j$ affects the conditional distribution at token $i$. They establish a contraction condition $\alpha(\tau) < 1$ (where $\alpha$ is the maximum sum of influences). Under this condition, they prove an $O(n \log n)$ upper bound on mixing time.
   • Low-Temperature Regime: They analyze "metastable basins" where the chain gets trapped. Using a "uniform local margin" assumption (where the score of the current token significantly exceeds alternatives), they prove that the escape probability from such basins is exponentially small in $1/\tau$, leading to exponentially slow mixing.

4. Empirical Validation:

   • Experiments were conducted on BERT-base, RoBERTa, and ModernBERT using MS MARCO passages as initial states.
   • Mixing was measured via semantic drift (cosine distance in Jina Embeddings space) and coupling times (time for two chains to agree).
   • Semantic Trajectories: Long-run dynamics were tracked using PCA on sentence embeddings to visualize "semantic basins" and "traps." Political content was used as a measurable case study for recurrent semantic regions.

Key Contributions

1. Incompatibility of MLM Conditionals

The paper demonstrates that MLM conditionals are fundamentally incompatible with any joint distribution.

• Rectangle Test Results: Empirical testing on BERT, RoBERTa, and ModernBERT reveals significant incompatibility ($\delta \in [0.64, 0.80]$), whereas autoregressive models like GPT-2 yield $\delta = 0$.
• Implication: This incompatibility is an intrinsic artifact of the pseudo-log-likelihood training objective and persists across model sizes. Consequently, the stationary distribution $\mu_\tau$ of the Glauber chain is an emergent object that cannot be directly inferred from local conditionals.

2. Theoretical Mixing Bounds

The authors provide provable sufficient conditions for both fast and slow mixing regimes:

• Fast Mixing: Under bounded cross-token influence (high temperature), the mixing time is $O(n \log n)$.
• Slow Mixing: Under a uniform local margin condition (low temperature), the chain exhibits metastability with exponentially slow escape times from semantic basins.
• Empirical Certification: The authors identify specific "slow-mixing basins" (e.g., sequences with high counts of specific tokens like '!') where drift conditions confirm slow mixing empirically.

3. Phase Transitions in Mixing Behavior

Empirical results validate a phase transition in mixing time dependent on temperature ($\tau$) and sequence length ($n$):

• High Temperature ($\tau \gtrsim 1$): Mixing is fast, with hitting times scaling as $C(\tau) n \log n$, consistent with the contraction theorem.
• Low Temperature: Mixing slows dramatically. Chains become trapped in metastable states for thousands of steps.
• Transition Boundary: The crossover from slow to fast mixing occurs around $\tau \approx 1.5\text{--}2$, shifting to higher temperatures as sequence length increases.

4. Characterization of the Semantic Landscape

Long-run Glauber dynamics reveal a landscape of metastable semantic basins:

• Chains often lose their initial semantic identity and wander through coherent regions of text space.
• Semantic Traps: The authors identify "traps" where chains remain for hundreds to thousands of steps. These include:
  • Perfect traps: Factually specific or grammatically coherent sequences where every token is the model's argmax (e.g., "it has been used as the theme song for jesus christ superstar").
  • Approximate traps: Semantically incoherent but locally stable sequences where collective token reinforcement maintains metastability.
• Recurrent Basins: Using political content as a case study, the authors show that chains initialized from diverse topics (health, sports, food) frequently drift into and revisit political semantic regions, even if they do not end there. This suggests political content acts as a recurrent attractor in the induced dynamics.

Significance and Claims

The paper claims to offer a new framework for understanding the global stochastic geometry of masked language models, distinct from static embedding analysis or single-step generation quality.

• Beyond Interpretability: The findings are significant for understanding biases and structural attractors in MLMs, which are increasingly used in discrete diffusion models for text generation. The energy landscape of the underlying MLM is inherited by these generative processes; thus, understanding the mixing behavior and metastable basins is crucial for predicting the output of diffusion-based text generators.
• Theoretical Rigor: The work bridges statistical physics (Glauber dynamics, Ising models) and NLP, providing rigorous mixing time bounds and identifying structural incompatibilities in standard MLM training objectives.
• Empirical Reality: The study highlights that while MLMs are not designed for generation, their iterative application creates a complex dynamical system characterized by phase transitions, metastability, and recurrent semantic biases (specifically political content) that are invisible to static probing methods.

The authors remain modest regarding the tightness of their theoretical bounds, noting that empirical mixing often occurs faster than the worst-case theoretical predictions suggest, likely because typical chain configurations are less coherent than the adversarial contexts used to derive the bounds. They also note that a complete characterization of the stationary distribution $\mu_\tau$ remains an open problem.