Percolation Dynamics in Optimization : Variance Cascades and Discrete Scale Invariance

Sai Niranjan Ramachandran, Suvrit Sra

Deep learning optimization collapses via a symmetry-induced percolation process that exhibits discrete scale invariance.

Why does SGD optimization exhibit discrete, scale-invariant "jumps" in variance during training, and how do these relate to the topological collapse of the model's parameter space?

Deep neural networks often exhibit "grokking," where models suddenly transition from memorizing data to generalizing after long periods of training. The mechanism behind this abrupt shift remains poorly understood, as classical optimization theory typically assumes smooth, continuous convergence. The authors model stochastic gradient flow as a percolation process where architectural symmetries force subnetworks to merge in discrete, simultaneous blocks. This topological condensation creates a "Reeb graph" of parameter states that renormalizes into a macroscopic percolation graph. Training trajectories exhibit a geometrically scaling cascade of these discrete merges, which the authors identify as Discrete Scale Invariance (DSI). This framework predicts the global structural collapse of the network and extends to adaptive optimizers like Adam and AdamW.

Paper Primer

The core move is mapping the optimization trajectory to a Reeb graph, which tracks how independent subnetwork path measures fuse into equivalence classes. This graph is then renormalized into a percolation process where architectural symmetries—such as neuron permutation—enforce discontinuous, multi-body block merges rather than single-edge attachments.

Optimization dynamics follow a geometrically scaling cascade of discrete topological transitions.

The authors derive that multi-body block merges break continuous scale invariance into a discrete subgroup, yielding a scaling relation where the ratio of distances to the critical connectivity threshold $p_c$ follows a power law $\lambda(n)^{-\sigma}$. In toy models, the predicted magnification factor $\lambda \approx 2.00$ matches empirical observations; in Transformers, a three-peak DSI cascade ($\lambda = 2.11$) precedes the performance spike.

The relative variance of the order parameter $R_v(p)$ serves as a diagnostic for structural microtransitions.

At a transition density $p_i$, the relative variance diverges proportionally to the squared jump amplitude $(\Delta O)^2$, signaling the moment of macroscopic component fusion. This divergence allows for the isolation of discrete merges that are otherwise obscured by stochastic noise in single-trajectory observations.

Why does this percolation framework matter for understanding "grokking"?

Grokking represents a delayed transition to a generalizing solution; by modeling this as a percolation process, the authors show that the transition is not a smooth relaxation but a series of discrete topological phase transitions that can be forecasted by the DSI cascade.

How does this approach differ from standard views of SGD as a low-rank manifold search?

Standard views focus on the final destination (the low-rank manifold), whereas this framework tracks the transient path to that manifold, treating the optimization as a non-equilibrium system where architectural symmetries dictate the specific sequence of topological merges.

Optimization is a sequence of discrete topological phase transitions; researchers can now use the divergence of relative variance to forecast structural collapse and potentially guide learning-rate scheduling.

Introduction: The Discrete Nature of SGD

We frame the core question: why does optimization proceed via abrupt topological jumps?

Deep‑learning optimization does not follow a smooth descent; instead it proceeds through abrupt, discrete topological transitions that we call percolative collapse. These events shrink the effective parameter space in scale‑invariant steps, producing observable variance spikes in a macroscopic order parameter.

Stochastic Collapse refers to the phenomenon where SGD drives a network toward invariant subnetworks, effectively pruning parameters and reducing rank. This process underlies the abrupt transitions we study.

Percolative Collapse is the collective merging of symmetric components in a network, triggered by architectural symmetries, that occurs in simultaneous blocks rather than one‑by‑one.

Step 1: Both units compute the same pre‑activation a = w·x.

Step 2: Gradient descent computes identical updates $\Delta$w for both units.

Step 3: After the update, w₁ ← w₁ + $\Delta$w and w₂ ← w₂ + $\Delta$w, so w₁ = w₂.

Step 4: The network now treats the two units as one, reducing the parameter count by one.

This simple merge illustrates a percolative collapse: a discrete, simultaneous reduction of the model’s effective dimensionality caused by symmetry.

Optimization is not a smooth descent.

Stochastic Collapse in SGD

Formalizes stochastic collapse as invariant‑set trapping in SGD dynamics.

We formalize stochastic collapse as the trapping of SGD trajectories in invariant affine subspaces when deterministic drift dominates diminishing batch noise.

When parameters approach an affine invariant set, the batch‑gradient noise shrinks, letting the deterministic gradient pull pull the trajectory onto the set in discrete, scale‑invariant steps.

How does stochastic collapse differ from ordinary convergence of SGD?

Ordinary convergence assumes the gradient drift alone drives parameters to a local minimum, while stochastic collapse relies on a shrinking noise term that makes an invariant affine subspace act like an attractor, causing the trajectory to “snap” onto that subspace in discrete jumps rather than a smooth approach.

If a subset A ⊆ ℝ^d forms an affine invariant set of the discrete SGD process and the sample gradients are L‑Lipschitz and bounded, then A also forms an invariant set of the continuous stochastic gradient flow.

Initialize at $\theta$₀ = (1, 0.4). Compute the full‑batch gradient ∇L = (1, 0.4).

SGD update: $\theta$₁ = $\theta$₀ − $\eta$∇L ≈ (0.9, 0.36).

Noise term: $\eta$$\Sigma$($\theta$₀) ≈ 0.1·diag(0.02, 0.02) → small perturbation that shrinks as $\theta$₂ decreases.

After several iterations, $\theta$₂ approaches 0 while $\theta$₁ continues to decay, keeping the trajectory on the line $\theta$₂ ≈ 0.

When $\theta$₂ ≤ 0.01, the noise magnitude becomes negligible, and the deterministic drift forces the state onto the exact invariant line A.

The example shows how diminishing noise in the transverse direction forces the trajectory onto the affine invariant set, illustrating stochastic collapse in a concrete toy system.

Topological Dynamics and Attractors

Formalizes how subnetworks bind via attractor equivalence and topological transitions.

We first partition the global parameter vector $\theta$ into $K$ disjoint subnetworks $\theta^{(1)},\dots,\theta^{(K)}$, each evolving in its own function space $C([0,\infty),\mathbb{R}^{d_i})$.

Assumption 3.2 (Block‑Diagonal Dominance) posits that for any two distinct subnetworks the off‑diagonal block of the diffusion matrix satisfies $\|\Sigma_{ij}(\theta)\|_2 \le \delta$ with a small $\delta>0$, effectively decoupling their stochastic dynamics.

A topological attractor is a region in parameter space toward which stochastic trajectories converge and remain trapped, despite random fluctuations.

How does a topological attractor differ from a simple local minimum?

In a local minimum the gradient vanishes but stochastic noise can still push the iterate out; a topological attractor guarantees inward drift that overwhelms the noise, making escape exponentially unlikely without a large deviation.

The Reeb graph collapses a high‑dimensional space into a one‑dimensional skeleton by identifying points that share the same value of a chosen scalar function.

Why use a Reeb graph instead of tracking pairwise distances directly?

Pairwise distances grow quadratically with the number of subnetworks, while the Reeb graph abstracts the same information into a linear structure that captures only the qualitative merging and fragmentation events.

Given a stochastically attractive invariant set $A$, there exists a local basin $N(A,\varepsilon)$ such that the stopped transverse process $Y_i(t\wedge\tau_\varepsilon)$ is a non‑negative local supermartingale, where $\tau_\varepsilon=\inf\{t\ge t_0 : Y_i(t)\ge\varepsilon\}$.

At $t=0$, $Y=0.2$.

Euler step $\Delta t=0.1$: $Y \leftarrow Y -\alpha Y\Delta t + \sigma\sqrt{\Delta t}\, \xi$, with $\xi\sim\mathcal{N}(0,1)$. Sample $\xi=0.3$ gives $Y\approx0.2-0.02+0.003=0.183$.

Repeated steps keep $Y$ decreasing on average; after 10 steps $Y\approx0.12<\varepsilon$, so $\tau_\varepsilon$ has not been triggered.

The process remains non‑negative and bounded by $\varepsilon$, satisfying the supermartingale condition.

The example shows how inward drift dominates diffusion, guaranteeing that the stopped process cannot exceed the basin radius without a large stochastic kick.

For any stochastically attractive invariant set $A$, the probability that a trajectory starting at $\theta_0$ escapes the $\varepsilon$‑neighbourhood is bounded above by the initial transverse distance $Y_i(t_0)$.

The relation $\sim_A$ defines a time‑parameterized equivalence class over restricted path measures, conditioned on the survival of $\tau_\varepsilon$.

Since $Y_i,Y_j<\varepsilon$, $\tau_i^\varepsilon=\tau_j^\varepsilon=\infty$.

Because $Y_k<\varepsilon$ as well, $\tau_k^\varepsilon=\infty$; thus all three survive.

By definition of $\sim_A$, $i\sim_A j$, $j\sim_A k$, and $i\sim_A k$, establishing transitivity.

The example illustrates that once all transverse distances stay below the basin radius, the subnetworks become mutually equivalent under $\sim_A$.

The Reeb graph $R$ encodes topological transitions via condensation ($\cup$) when transverse drift vanishes, and fragmentation ($\emptyset$) when a variance deviation triggers $\tau_\varepsilon$.

Before injection, $\text{link}_{1,2}(t)\approx1$, so $[1]_t=[2]_t$ and the Reeb graph has a single merged node.

After injection, $Y_2>\varepsilon$, so $\tau_\varepsilon$ triggers for subnetwork 2, breaking $\sim_A$.

The Reeb graph fragments: the merged node splits into two separate branches, reflecting the loss of equivalence.

This illustrates how a large deviation causes fragmentation, while the absence of such deviations leads to condensation.

Two subnetworks are attractor‑equivalent at time $t$ if their trajectories never leave the shared basin, i.e., their transverse distances stay below $\varepsilon$ forever.

Both $Y_i$ and $Y_j$ remain below $\varepsilon$, so $\tau_i^\varepsilon=\tau_j^\varepsilon=\infty$.

The link probability $\text{link}(t)=1$ for all $t$, establishing $i\sim_A j$.

If later a spike raises $Y_j$ to $0.12$, $\tau_j^\varepsilon$ becomes finite, breaking the equivalence.

The example shows that attractor equivalence persists as long as transverse distances stay within the basin, and it can be broken by a single large deviation.

Percolative Collapse and DSI

Formalizing the percolative collapse mechanism and its discrete scale invariance.

We now formalize the mechanisms that drive the percolative collapse observed during training.

During training the effective parameter space contracts in abrupt, scale‑invariant jumps, like a network of pipes that suddenly snaps shut in groups, reducing connectivity.

How does percolative collapse differ from a smooth continuous phase transition?

In a smooth transition components grow one edge at a time, while percolative collapse merges whole groups simultaneously, causing a finite jump in the order parameter rather than an infinitesimal change.

DSI means the system repeats its statistical pattern only at specific, multiplicative scales, like a fractal that looks similar only when zoomed by powers of two.

Why is the scaling discrete rather than continuous?

The topological constraint $S_n$ forces component growth to happen in fixed multiples (e.g., doubling), so the system can only rescale by those allowed integer factors, breaking the continuous dilation symmetry.

If the loss $L$ exhibits approximate $Q$‑symmetry around an affine subspace $A$, deterministic gradient drift is confined to $A$ and the transverse stochastic distance $Y_t=d(\theta_t,A)$ evolves as a curvature‑free diffusion process.

Applying a temporal renormalization operator over the slow timescale $\tau_{\text{slow}}$ collapses microscopic Brownian fluctuations, converting the transient Reeb graph $R_t$ into a monotonic macroscopic percolation graph $G_{\tau}=(V,E_{\tau})$ governed by the continuous expected edge density $p\in[0,1]$.

Symmetry‑induced percolation forces simultaneous group‑wise edge additions, causing a jump $\Delta O(p)=\frac{(n-1)i}{N}$ in the order parameter whenever components of size $i$ merge.

At a structural microtransition the relative variance $R_v(p)$ diverges proportionally to the squared jump amplitude $(\Delta O)^{2}$, signaling an imminent global connectivity threshold $p_c$.

The $S_n$ topological constraint forces component growth to follow the discrete mapping $C_1\to n C_1$, producing a geometric cascade of critical densities that obey $\frac{p_c-p_{n i}}{p_c-p_i}= \lambda(n)^{-\sigma}$ with $\lambda(n)=n^{\sigma}$.

Compute the jump: $\Delta O(p)=\frac{(2-1)\cdot 2}{8}=0.25$, so the order parameter drops from $0.75$ to $0.50$.

Next transition density $p_{2i}$ satisfies $\frac{p_c-p_{2i}}{p_c-p_i}=2^{-\sigma}$. With $\sigma=1$ and $p_c=0.5$, we get $p_{2i}=0.5-2^{-1}(0.5-0.30)=0.40$.

The second jump again reduces $O(p)$ by $0.25$, reaching $0.25$ at $p_{2i}=0.40$.

This toy example shows how discrete scaling produces equally spaced log‑periodic transition points and fixed‑size jumps in the order parameter.

**Figure 1.** **Topological Condensation and Fragmentation:** (Top) Kinematic verification of the theoretical $\lambda = 2$ DSI baseline. (Middle &amp; Bottom) Empirical SGD dynamics. The condensation phase ($t < 3000$) exhibits sequential DSI variance peaks ($p_1, p_2$) with a log-linear progression close to $\lambda \approx 2.00$ (fit through two points; see main text). The task shift at $t = 3000$ reverses the stability inequality and is followed by a reactive fragmentation peak ($p_3$). Zoom for clarity.

Extension to Adam and AdamW

Extends the percolation mechanism to Adam and AdamW under explicit conditions.

We now adapt the percolation and DSI framework, originally formulated for SGD, to the Adam and AdamW optimizers.

Adam and AdamW keep three coupled states—parameters, first‑moment estimate, and second‑moment estimate—so the percolation analysis must track all three simultaneously.

How does this extension differ from the standard Adam update?

Standard Adam treats each coordinate independently, but the extension explicitly tracks the symmetry group $P_{\pi}$, ensuring that permutation‑invariant blocks remain invariant under the optimizer’s dynamics.

Assumption 5.1 introduces heavy‑tailed gradient noise, a condition required for the variance cascade.

Assumption 5.2 defines a low‑correlation stopping time based on the autocovariance of the squared truncated gradients.

Assumption 5.3 guarantees non‑degeneracy of the second‑moment estimate and a macroscopic scaling of permutation‑symmetric blocks.

Suppose the set $A$ is stochastically attractive for the rescaled drift $c(\theta)\nabla L(\theta)$ and the drift margin dominates the residual $R_t$. Then $Y_i$ is a non‑negative local supermartingale.

Compute gradient $g_0 = \nabla L(\theta_0) = (1, -1)$.

Truncate: $\hat{g}_0 = g_0$ because $|g_0|<\tau_0$ (choose $\tau_0=2$).

Update first moment: $m_1 = \beta_1 m_0 + (1-\beta_1)\hat{g}_0 = 0.1\,(1,-1) = (0.1,-0.1)$.

Update second moment: $v_1 = \beta_2 v_0 + (1-\beta_2)\hat{g}_0^{2} = 0.999\cdot1 + 0.001\cdot(1,1) = (1,1)$.

Compute step size $\eta = 0.01$ and bias‑corrected moments $\hat{m}_1 = m_1/(1-\beta_1) = (1,-1)$, $\hat{v}_1 = v_1/(1-\beta_2) = (1,1)$. Update parameters: $\theta_1 = \theta_0 - \eta \hat{m}_1 / (\sqrt{\hat{v}_1}+ \epsilon) \approx (0.99, -0.99)$.

Residual $R_0 = O(b_0 + L_m \tau_2 \Delta_{\max} + L \tau_0 \epsilon)$ is negligible because $b_0=0$, $L_m$, $\tau_2$, $\Delta_{\max}$ are all $O(1)$ and $\epsilon$ is $10^{-8}$.

The example shows that with the chosen parameters the residual term remains tiny, so the drift term $c(\theta)\nabla L(\theta)$ dominates and the supermartingale condition holds.

Under Assumption 5.3 and the heavy‑tailed noise model, the Adam‑trained trajectory admits a percolation graph satisfying Generalized Discrete Scale Invariance with magnification factor $\lambda(n)=n^{\sigma}$.

At level 3, variance of the truncated gradient is $V_3$.

When the block merges to level 2, the variance scales by $\lambda(2)$, giving $V_2 = \lambda(2) V_3$.

Similarly, merging from level 2 to level 1 scales variance by $\lambda(2)$ again, yielding $V_1 = \lambda(2) V_2 = \lambda(2)^2 V_3$.

Because $\lambda(2)>1$, each merge amplifies variance, reproducing the discrete scale‑invariant cascade described in Theorem 4.7.

This toy cascade demonstrates that the same magnification factor appears unchanged under Adam’s scalar $c(\theta)$, preserving the DSI structure.

Empirical Validation and Results

We empirically confirm percolative collapse and DSI cascades across multiple architectures.

Recall that optimization proceeds via discrete topological transitions—percolative collapse—where the model’s effective parameter space shrinks in scale‑invariant steps.

Define the macroscopic order parameter $O(t)=\text{variance}(\nabla L(\theta_t))$.

When a percolative collapse occurs, $O(t)$ exhibits a sharp spike.

Detrended variance fluctuations $R_v(t)$ isolate these spikes as discrete peaks.

Both constrained $K=3$ and unconstrained $K=6$ SGD runs achieve magnification $\lambda\approx2.00$, matching the pairwise subnetwork‑merge prediction.

Observed $\lambda$ values from variance divergence peaks align with the theoretical prediction.

In the modular‑arithmetic Transformer, a three‑peak DSI cascade with scaling factor $\lambda=2.11$ precedes the grokking performance spike.

Detrended variance $R_v(t)$ shows three distinct peaks at epochs corresponding to the cascade.

**Figure 2.** **Universality and Empirical Generalization: (a) Transformer Grokking (Modular Arithmetic):** Delayed generalization co-occurring with continuous dimensionality collapse and a log-linear DSI cascade. **(b, c) UCI Heart Disease and FMNIST:** DSI variance cascades in tabular regression (b) and image classification (c). Extended evaluations are in Appendix F.

**Figure 4.** **Abalone:** The macroscopic continuous decay of effective rank (a) is underscored by a highly structured 6-peak DSI cascade yielding a strong log-linear fit of $R^2 = 0.97$ with a fractional scaling factor $\lambda = 1.28$ (b). The collapse is driven by a dominant top singular value (c).

**Figure 5.** Digits: Variance fluctuations dynamically map the topological condensation of the network during early-stage SGD optimization.

**Figure 6.** **German Credit:** The network exhibits a 4-peak cascade ($\lambda = 1.99, R^2 = 0.86$), but yields a spectral null False Positive Rate of 80.2%, acting as a negative control.

**Figure 7.** **Heart Disease:** Dimensionality collapse (c) is mirrored by a sequential 4-peak variance divergence ($\lambda = 1.71, R^2 = 0.98, \text{FPR} = 4.9\%$) mapping the internal topological constraints.

**Figure 10.** **MNIST (Vision):** Variance fluctuations produce a 2-peak sequence ($p_1, p_2$) dynamically mapping the topological condensation of the network during early-stage SGD optimization.

**Figure 11.** FashionMNIST (Vision): Detection of consecutive variance peaks highlighting the discretized nature of capacity reduction ($\lambda = 1.57, R^2 = 1.00, \text{FPR} = 10.7\%$).

**Figure 12.** **Modular Arithmetic (Grokking):** A Shallow Transformer trained with AdamW experiences a delayed topological collapse. The macroscopic decay of the attention embeddings’ effective rank is composed of a perfectly log-linear 3-peak DSI cascade ($\lambda = 2.11, R^2 = 1.00, \text{FPR} = 0.1\%$).

DSI cascades are observed across diverse architectures, from tabular to vision to modular arithmetic tasks.

Mechanics of Topological Transitions

Isolating subnetwork dynamics via transverse distance and supermartingale trapping.

This section extracts the local stochastic dynamics of each subnetwork by projecting onto a transverse distance process, then shows how the stopped process forms a non‑negative supermartingale that guarantees confinement within a basin around the invariant manifold.

The transverse distance measures how far a subnetwork’s parameters stray from the invariant manifold A, squared, giving a scalar that quantifies deviation.

How does this transverse distance differ from a plain Euclidean distance used in standard gradient analysis?

Because we square the norm, the process penalizes larger deviations more heavily and guarantees non‑negativity, which is essential for establishing supermartingale properties. A plain distance could become negative after stochastic fluctuations, breaking the martingale argument.

When we stop the process at the first time it reaches the $\epsilon$‑boundary, the distance never exceeds $\epsilon$, ensuring the subnetwork stays inside the tubular neighborhood.

Why introduce a stopping time $\tau$_$\epsilon$ instead of analyzing the unrestricted process?

Stopping isolates the region where the drift dominates diffusion. Without stopping, the process could wander arbitrarily far, breaking the supermartingale bound needed for the escape probability analysis.

Within the $\epsilon$‑neighborhood, the deterministic drift pulls the parameters toward the manifold faster than diffusion can push them out, making the stopped transverse distance a supermartingale that can only decrease in expectation.

What is the practical difference between a supermartingale and a martingale in this context?

A martingale has zero expected drift, while a supermartingale has non‑positive drift, meaning the process tends to move toward smaller values on average. This bias is what guarantees confinement within the basin.

Doob’s maximal inequality applied to the supermartingale gives a simple bound: the chance of ever leaving the $\epsilon$‑neighborhood is at most the initial distance divided by $\epsilon$.

Why does the bound involve the expectation of $Y^{(i)}_{t_0}$ rather than a deterministic value?

Because the initial transverse distance is itself a random variable (depending on the random initialization), the bound must reflect its average magnitude across possible starts.

The link probability measures the chance that two subnetworks never leave the shared basin, i.e., they stay jointly trapped near the same invariant manifold.

How should we interpret a link probability that is strictly between 0 and 1?

It means there is a non‑zero chance that one or both subnetworks will eventually escape the basin, so they cannot be declared equivalent under the strict definition.

Doob’s inequality gives a concrete lower bound on the survival probability of a single subnetwork based on its current transverse distance.

Two subnetworks are attractor‑equivalent when their transverse drifts vanish so that their joint link probability becomes 1, and their expected distance difference converges to 0.

How does attractor equivalence differ from the stricter t‑tail equivalence defined earlier?

t‑tail equivalence requires exact equality of the full future law, which is unrealistic under stochastic noise. Attractor equivalence relaxes this to equality of expectations and guaranteed joint survival, making it attainable in practice.

Under the bounded drift and diffusion conditions, the attractor‑equivalence relation satisfies reflexivity, symmetry, and transitivity, thus forming an equivalence class over subnetworks that remain trapped together.

Together, these constructions provide a rigorous probabilistic framework for describing how subnetworks collapse onto shared invariant manifolds through discrete topological transitions.

Constructing the Reeb Topology

We formalize percolation dynamics and discrete scale invariance in deep learning optimization.

This appendix formalizes the topological machinery underlying percolative collapse and introduces the discrete scale invariance that emerges from architectural symmetries.

A snapshot of the network’s connectivity at a given training time, built by linking nodes whose parameters are equivalent under the adjacency relation.

A topological object that glues together the instantaneous networks over time, identifying nodes that stay connected across training.

The Reeb graph $R$ dynamically maps the structural phase transitions of the stochastic differential equation via two strict topological mechanisms: condensation ($\cup$) merges trajectories into a single node, while fragmentation ($\emptyset$) deletes edges, splitting a node into decoupled branches.

We now turn to the geometric symmetries of deep networks that give rise to percolative collapse and discrete scale invariance.

Read the original paper

Open the simplified reader on Paperglide

Browse all simplified papers