Berezinskii--Kosterlitz--Thouless transition in a context-sensitive random language model

Technical Summary: Berezinskii–Kosterlitz–Thouless Transition in a Context-Sensitive Random Language Model

Problem Statement
Natural languages exhibit statistical regularities, such as Zipf's law and power-law decay in information distance, which resemble scaling properties of physical systems near phase transitions. While large language models (LLMs) have recently demonstrated emergent scaling laws, specific instances of generative language models that exhibit mathematically rigorous phase transitions (as defined in statistical physics) remain lacking. Previous investigations into probabilistic context-free grammars (CFGs) have failed to conclusively demonstrate true phase transitions in standard thermodynamic limits. Furthermore, while the Berezinskii–Kosterlitz–Thouless (BKT) transition explains robust scaling laws in physical systems, it is traditionally associated with two-dimensional systems with continuous symmetries. The authors address the question of whether a one-dimensional language model, which naturally possesses discrete degrees of freedom, can exhibit a BKT transition without requiring fine-tuning to a specific critical point.

Methodology
The authors construct a context-sensitive random language model (CS-RLM), a probabilistic model falling under the class of context-sensitive grammars (CSGs). The model is inspired by the one-dimensional long-range Potts model and operates through three interacting processes:

1. Growth: Non-terminal symbols expand via rules (e.g., $X \to YZ$), increasing string length to allow for a thermodynamic limit ($N \to \infty$).
2. Context-Sensitive Rewrites: Substrings are rewritten based on surrounding context ($\alpha_- X \alpha_+ \to \alpha_- Y \alpha_+$) with acceptance probabilities governed by a Metropolis-Hastings algorithm. The energy change $\Delta E$ is calculated using a long-range interaction kernel $|i-j|^{-(1+s)}$, coupling symbol pairs at distance $|i-j|$.
3. Termination: Non-terminal symbols transition to terminal symbols (neglected in the primary analysis to facilitate the thermodynamic limit).

The study focuses on the case where the alphabet size $K=2$ (analogous to the Ising model) and the branching rule is $X \to YZ$. The authors analyze the system using standard statistical physics observables:

• Order Parameter (Magnetization, $M$): Defined as the magnitude of the vector sum of symbol frequencies, capturing biases in symbol generation.
• Susceptibility ($\chi$): Measures the variance of the order parameter.
• Binder Parameter ($U$): The normalized kurtosis of the order parameter, used to distinguish between disordered, ordered, and critical phases.
• Correlation Functions: Analyzed to detect power-law versus exponential decay.

The authors employ finite-size scaling methods on Monte Carlo simulations (varying sentence lengths $N$ from 16 to 4096) to extrapolate behavior in the thermodynamic limit.

Key Results

1. Existence of Phase Transition: The numerical simulations demonstrate a clear phase transition where the order parameter (magnetization) shifts from strictly zero (disordered) to strictly non-zero (ordered) as the temperature parameter $k_B T$ is tuned.
2. Identification of BKT Transition: The system exhibits characteristics of a BKT transition rather than a standard second-order transition:
   • Extended Criticality: The susceptibility diverges not just at a single critical point but across an entire low-temperature phase, indicating that the system remains critical over a finite parameter range.
   • Binder Parameter Behavior: The Binder parameter shows a crossing point for different system sizes and takes non-trivial values (between 0 and 1) in the critical regime, consistent with BKT behavior.
   • Correlation Decay: In the critical regime, correlation functions exhibit polynomial (power-law) decay rather than exponential decay.
3. Robustness to Parameters: The BKT transition is observed even when the decay exponent of the interaction kernel is $s=0.9$, a value distinct from the $s=1$ typically required for BKT transitions in standard one-dimensional long-range Potts models. The transition persists for multi-level spins ($K>2$) as well.
4. Critical Exponents: The authors determine critical exponents $\nu$ and $\gamma$ via finite-size scaling. They find that while $\gamma$ remains constant across different branching rules ($X \to YZ$ vs. $X \to XX$), both exponents depend on the growth rate parameter $q$ and the alphabet size $K$.

Significance and Claims
The paper claims to provide the first unambiguous demonstration of a BKT transition within a natural language model framework. The significance of this finding is threefold:

• Theoretical Novelty: It captures a rare phenomenon (BKT phase) in a one-dimensional system with discrete degrees of freedom, challenging the conventional view that such phases require two-dimensional continuous symmetries.
• Explanation of Scaling Laws: The results suggest that the robust scaling laws observed in natural languages and LLMs (which do not require fine-tuning to a specific critical point) may be generically explained by the underlying connection between language structures and BKT phases. In a BKT phase, scale-invariant behavior persists across a finite region, unlike standard critical points.
• Role of Grammar: The study highlights that context-sensitive mechanisms (long-range dependencies and expansion dynamics) are sufficient to induce non-trivial phase transitions, distinguishing CSGs from CFGs. The authors posit that the "growth" mechanism inherent in language generation modifies the effective dimensionality of the system, enabling this unconventional criticality.

The authors conclude that while their model is a simplification, it offers a principled explanation for why language models exhibit emergent abilities and scaling laws without external tuning, attributing this to the intrinsic statistical mechanics of context-sensitive generative processes.