acceptodds
Under review as a conference paper at ICLR 2027

Percolation Dynamics in Optimization: Variance Cascades and Nested Symmetry

Abstract

We study the dynamics of Stochastic Gradient Descent (SGD), which is known to steer deep neural networks toward invariant sets that correspond to simpler subnetworks. How this steering unfolds over time remains poorly understood. We answer this by modeling the stochastic gradient flow (SGF) as a percolation process, in which nested architectural symmetries force subnetworks to merge in discrete blocks rather than by single-edge attachment. These structural transitions register as variance spikes in a macroscopic order parameter echoing physical phase transitions. We further state sufficient conditions under which the trapping argument carries over to Adam and AdamW under heavy-tailed gradient noise and measure them on a trained Transformer.

Primary area:
learning theory
Keywords:
SGD, Adam, Stochastic collapse, Percolation, Phase transitions

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_sdJMOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This is a very beautiful paper with deep mathematics and corresponding empirical validation discussing how over time SGD successively encourages neural networks to become simpler and simpler by merging blocks of identical neurons (identical incoming and outgoing weights) into larger blocks of identical neurons. They identify order parameters (such as variance across runs) and when and why this variance will spike due to merger of blocks and their block size. They connect this to the important idea of delayed generalization and grokking because of the time it takes to merge and simplify the network. They perform empirical validations on both toy network and transformers.

Critical strengths

Beautiful theory about the timing and implications of mergers of blocks of similar neurons. Wonderful and relevant empirical validation of the results (e.g. the empirical observed variance peaks in Fig. 11 and earlier figures are very nice).

Critical weaknesses

They use the phrase topological phase transitions. I am not sure why - what is topological about the transition - it is just more neurons becoming similar to each other (i.e. projecting onto a subspace in weight space). Would be nice to clarify this language.

Questions for authors

Just the question about the use of the word topological in this paper.

2 comments
AuthorsOpenReview ↗

Our response

We thank the reviewer for the generous assessment and the question on terminology.

The term "topological". We use the term for changes in how the subnetworks of a network connect to each other as training moves through parameter space. This motion matters because trained weights are known to keep moving after the training loss has stabilized and to approach an approximate invariant measure instead of a stationary point (Zhang et al., 2022). Which solution is learnt then depends on the path that training takes. Studies of mechanistic interpretability (Nanda et al., 2023) and of low-rank biases (Huh et al., 2023) lead us to postulate that this path consists of discrete events. In our formalism such an event is a symmetric subnetwork collapsing into the set of parameters in which its interchangeable units coincide. Because swapping these units leaves the loss unchanged, gradient updates keep this set invariant while stochastic attractivity (Chen et al., 2023) draws training into it. In the parameters a collapse thus appears as neurons becoming identical, as Chen et al. (2023) observed empirically during training.

The topology enters once we record which subnetworks have collapsed together. We treat each subnetwork as a node and join two nodes by an edge while their parameters lie closer than the link distance of Definition 3.3. A collapse then adds an edge to this network of subnetworks and its reversal removes it. Because an edge forms exactly when the neighborhoods of half the link distance around two nodes overlap in parameter space, the components of the network match the connected parts of the region these neighborhoods cover. This is the construction by which topological data analysis turns point clouds into complexes (Edelsbrunner & Harer, 2008). Adding or removing an edge therefore changes how this region of parameter space is connected, even though the parameters themselves move continuously. Following these changes through training gives the Reeb graph of Section 3. Its branches join at condensations and split at fragmentations, the two topological transitions of Theorem 3.4.

During phases in which training collapses neurons toward a simpler solution, Proposition 4.4 reduces the Reeb graph to a percolation process. In percolation the components of a graph grow as edges are added to it. When each new edge joins two randomly chosen nodes (Erdős–Rényi percolation), the largest component grows continuously with the number of edges. Deep networks add their edges along nested symmetry instead, since units can be permuted within a block and whole blocks can be permuted with each other as the two subtrees of a binary tree can. Two blocks whose units have each become identical can then become identical themselves in a single event that joins all their units at once. The largest component therefore grows in discrete jumps (Proposition 4.5). The revision will state this construction in Section 3 and use the term consistently.

References

  • Chen, Kunin, Yamamura & Ganguli. Stochastic collapse: how gradient noise attracts SGD dynamics towards simpler subnetworks. NeurIPS 2023.
  • Edelsbrunner & Harer. Persistent homology — a survey. Contemp. Math. 453, 2008.
  • Huh, Mobahi, Zhang, Cheung, Agrawal & Isola. The low-rank simplicity bias in deep networks. TMLR 2023.
  • Nanda, Chan, Lieberum, Smith & Steinhardt. Progress measures for grokking via mechanistic interpretability. ICLR 2023.
  • Zhang, Li, Sra & Jadbabaie. Neural network weights do not converge to stationary points: an invariant measure perspective. ICML 2022.

Thank you for the clarification.

Reviewer_dtpxOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the transient dynamics of stochastic optimization and proposes a percolation-based framework for understanding how neural network parameters evolve toward simpler structures induced by architectural symmetries. The authors model subnetworks as nodes in a graph and interpret their convergence toward shared invariant sets as the formation of links and the merging of connected components. On the theoretical side, the paper establishes local stochastic trapping conditions using a super-martingale argument. Under additional assumptions on the coalescence kernel, dynamical scaling, and balanced block merges, the authors derive predictions for discontinuities in a macroscopic order parameter, the heights and locations of relative-variance peaks, and geometric scaling of transition times. They also provide a conditional extension of the trapping and cascade arguments to Adam and AdamW. Empirically, the authors first validate their framework in controlled toy settings and then investigate MLPs, vision benchmarks, and a Transformer trained on modular arithmetic. They report sequences of variance peaks associated with spectral effective-rank reduction, including a three-peak cascade preceding or accompanying the generalization transition in a grokking experiment.

Critical strengths
  • Theoretical framework. The paper focuses on the transient process through which optimization reaches simpler parameter configurations, rather than only characterizing the final solution. This perspective may provide useful insights into non-smooth training dynamics and delayed generalization. The combination of stochastic dynamics, invariant sets, Reeb graphs, percolation, and coalescence provides a potentially useful language for describing the formation and fragmentation of subnetworks.

  • Experiments. The authors study controlled toy systems as well as MLPs, vision tasks, and a Transformer. The inclusion of a negative control is valuable for assessing whether geometric peak patterns are sufficiently specific to support the proposed interpretation.

Critical weaknesses
  • The applicability of the theoretical assumptions to practical neural networks is not sufficiently established. The main results rely on local stochastic attractivity, non-increasing expected component counts, homogeneous coalescence kernels, and balanced block merges. It remains unclear how often these assumptions hold in practical training, over what time intervals they are valid, and how sensitive the predicted cascades are to their violations. The connection between the idealized merging process and continuous parameter dynamics needs further justification.

  • The empirical order parameter is not a direct measurement of the theoretical topological process. The theoretical analysis concerns connected components formed by parameter blocks approaching symmetry-induced invariant sets. In practical networks, the authors instead use spectral effective rank as a proxy. A decrease in effective rank can reflect spectral concentration or low-rank structure without implying that subnetworks have actually merged. More direct evidence connecting these two notions would strengthen the paper considerably.

  • The relationship between the cascades and grokking is correlational rather than causal. The reported peaks precede or accompany a generalization transition, but this temporal association does not establish that the cascade drives grokking. Intervention experiments are needed to distinguish a causal mechanism from a correlated consequence of weight decay, optimization dynamics, or another common factor.

Questions for authors
  • Can the authors quantitatively test the assumptions of homogeneous coalescence rates, balanced block merges, and non-increasing expected component counts in practical neural networks? If these assumptions hold only over short local windows, how sensitive are the predicted cascades to the duration of those windows?

  • Can the authors jointly measure parameter-block distances, proximity to symmetry-induced invariant sets, and spectral effective rank in the same trained network? Do these quantities exhibit consistent transitions at the same training stages?

4 comments
AuthorsOpenReview ↗

First part of our response

We thank the reviewer for proposing the joint measurement and the tests of our assumptions.

Critical Weakness 1 and Question 1: the assumptions in practice and the window. Because our assumptions are falsifiable, we test each one against a null.

The first assumption is that merges are memoryless on a short enough time scale. We test it in a new analysis of the flat layer of Appendix E.5, a layer of interchangeable units without nested symmetry (32 seeds). Let Δi\Delta_i be the time between merges i−1i-1 and ii and a bar the mean over the window. Before merge ii the components of this layer merge at the total rate Λi/N\Lambda_i/N with Λi=∑(ab)γK/2\Lambda_i=\sum(ab)^{\gamma_K/2} over all pairs of components of sizes aa and bb. This product kernel takes its degree γK=1.7\gamma_K=1.7 from the measured ratio 2γK2^{\gamma_K} of the link rates of size-2 and size-1 component pairs in the same layer. For memoryless merges Δi∼Exp(Λi/N)\Delta_i\sim\mathrm{Exp}(\Lambda_i/N) and hence ΛiΔi/N∼Exp(1)\Lambda_i\Delta_i/N\sim\mathrm{Exp}(1). Normalizing by the window mean as Wi=ΛiΔi/ΛΔ‾W_i=\Lambda_i\Delta_i/\overline{\Lambda\Delta} removes any slow change in the pace of training and lowers σ/μ\sigma/\mu slightly. As a null we therefore draw Exp(1)\mathrm{Exp}(1) waits with the same windows and counts and normalize them in the same way. We observe σ/μ=0.95\sigma/\mu=0.95–0.980.98 at width 32, inside the 95% range of the null in every window. At width 16 the value of 0.83–0.85 lies below that range and approaches it as the layer widens. Changing the window from 125 to 500 steps moves σ/μ\sigma/\mu by at most 0.03. The constant kernel γK=0\gamma_K=0 gives 0.93–0.99 at width 32. We therefore infer that merges in wide layers are memoryless on this time scale for any window in this range.

The second assumption is that training remains in each invariant set it enters for the rest of the condensation phase (Theorem 3.4). Because each slingshot spike of AdamW (Thilak et al., 2022) opens a new condensation phase, we treat each interval between spikes as one phase (Remark D.30). We test this assumption in a new measurement on the Transformer. Its 128 residual dimensions form interchangeable subnetworks because relabeling them consistently in every weight matrix leaves the network function intact. The kk-th column eke_k of the token embedding records what each token writes into dimension kk. With $m=\mathop{\mathrm{median}}\nolimits_j\Vert e_j\Vert $ the median norm of the 128 columns, we call two live columns (norm above 0.1m0.1 m) merged at epoch 12,000 when ∥ek−el∥<0.25m\Vert e_k-e_l\Vert< 0.25 m and unmerged otherwise. We follow both kinds of pairs for the next 4,000 epochs. As a null we take the unmerged pairs of the same runs. We observe that 73–87% of the merged pairs are still within 0.25m0.25 m at the end, while at most 0.5% of the unmerged pairs come that close in the same time (4 of 5 seeds; the fifth forms only 4 merged pairs). We therefore infer that merges persist within a phase.

The third assumption is that merges join components of equal size. Only the predicted ratio qni/qi=n1−γKq_{ni}/q_i=n^{1-\gamma_K} of the times qiq_i at which successive variance peaks occur depends on this assumption (Theorem 4.9). Theorem 4.6 instead fixes the height of each peak for any mix of merge sizes. A merge of two equal components larger than one unit makes whole blocks of units identical at once. We therefore hypothesize that such merges arise from nested symmetry, the symmetry that exchanges whole blocks of units. As a null we use the flat layer of Appendix E.5 with the units of the binary tree but without this symmetry. The binary tree doubles its largest component in 11–22% of the events that enlarge it and the flat layer in only 3–11% (Table 2). We therefore infer that merges of equal size arise mainly from nested symmetry. For our task, the 128 residual dimensions of the Transformer are interchangeable as a single group like the units of the flat layer. Sorting the merges of its token-embedding columns at the paper's link distance by component size, we find 155 single-column pairs among the 160 merges of equal-size components (5 seeds). Like the flat layer, the Transformer embedding thus merges components of equal size almost only when they are single columns. The revision will add these merge counts and the tests of the first two assumptions to Appendices E.5 and F.

Finally, Remark F.2 points out that the measured ratios treat training time as the clock of coalescence. If a pace of training r(t)r(t) multiplies every merge rate, it only replaces training time tt by τ(t)=∫0tr(s)ds\tau(t)=\int_0^t r(s) ds. The revision will therefore add this factor to Assumption 4.7 and state Theorem 4.9 in τ\tau so that the prediction holds however the clock r(t)r(t) varies.

References

  • Thilak, Littwin, Zhai, Saremi, Paiss & Susskind. The slingshot mechanism: an empirical study of adaptive optimizers and the grokking phenomenon. arXiv:2206.04817, 2022.
AuthorsOpenReview ↗

Second part of our response

Critical Weakness 2 and Question 2: distances, invariant sets and effective rank together. Definition 3.3 measures the proximity of two interchangeable subnetworks ii and jj to their shared invariant set $\lbrace\theta^{(i)}=\theta^{(j)}\rbrace $ by the squared transverse distance Y=12∥θ(i)−θ(j)∥2Y=\tfrac12\Vert\theta^{(i)}-\theta^{(j)}\Vert^2. The block distance between two such subnetworks is therefore a direct measure of their proximity to that set. Measuring this distance jointly with the effective rank needs a network whose interchangeable subnetworks can be compared pair by pair at every snapshot.

The modular-arithmetic Transformer is such a network. Each of its layers reads from and adds to a residual stream of 128 dimensions. The weights that write into or read from dimension kk form a subnetwork θ(k)\theta^{(k)}. Any permutation of the dimensions applied to these subnetworks leaves the network unchanged. In the token embedding E∈R18×128E\in\mathbb{R}^{18\times128} the subnetwork θ(k)\theta^{(k)} owns the column eke_k of entries that the 18 tokens write into dimension kk. The embedding part of YY for two dimensions kk and ll is then 12∥ek−el∥2\tfrac12\Vert e_k-e_l\Vert^2. We therefore link kk and ll when ∥ek−el∥<rm\Vert e_k-e_l\Vert< r m for a link radius rr with $m=\mathop{\mathrm{median}}\nolimits_j\Vert e_j\Vert $ and count the connected components of the resulting graph.

The effective rank exp⁡H(σ/∑kσk)\exp H(\sigma/\sum_k\sigma_k) of EE falls by a definite step whenever nn columns coincide (Proposition F.1). When merges always join components of equal size, its variance across runs therefore peaks at the same epochs as that of the relative size ∣Cmax⁡∣/N|C_{\max}|/N of the largest component (Appendix F). Because σk2=λk(EE⊤)\sigma_k^2=\lambda_k(EE^\top) and 1128EE⊤=Σ+eˉeˉ⊤\tfrac{1}{128}EE^\top=\Sigma+\bar e\bar e^\top for the mean eˉ\bar e and covariance Σ\Sigma of the columns, the singular values of EE depend on these two moments alone. Columns drawn from these two moments thus reproduce the effective rank up to sampling error while leaving open which pairs of them coincide. We therefore hypothesize that over the epochs of the variance peaks the trained columns form fewer components than columns with the same two moments.

As a null we draw Gaussian columns from the mean and covariance of the trained columns. We redraw the null at every saved snapshot of every run so that it evolves with the spectrum and the effective rank of the trained embedding. Because its columns are independent, any closeness between them arises by chance at the given radius. We link trained and null columns by the same rule at the same epochs.

Table A. Components per 100 embedding columns at the three variance peaks (15 seeds).

Epochr=0.14r=0.14: trained / nullr=0.5r=0.5: trained / nullEffective rank
4,500100 / 10075 / 9011.46
9,50098 / 10048 / 8911.41
20,00085 / 10031 / 8611.37

r=0.14r=0.14 is the link threshold 2ϵ\sqrt{2\epsilon} of the paper.

We observe in Table A that the trained columns merge through all three peaks while the null barely changes. At the paper's link threshold the first merges appear by the second peak. Every link radius between 0.14 and 0.6 keeps the trained count at or below the null. Over the same epochs the mean effective rank moves only from 11.46 to 11.37. We therefore infer that merges into invariant sets proceed through the stages marked by the variance peaks of the effective rank, far beyond what the spectrum explains. The revision will add Table A to Appendix F.

AuthorsOpenReview ↗

Third part of our response

Critical Weakness 3: cascade and grokking. We observe that validation accuracy reaches 0.9 by the first variance peak (epoch 4,500), before the cascade unfolds. We therefore infer that the cascade describes what training does after it has generalized. Over the cascade, the token embedding comes to use fewer distinct columns. Its column eke_k holds what each of the 18 tokens writes into dimension kk of the residual stream, the 128-dimensional sum that all layers read and update. To count distinct columns in a new measurement we link two embedding columns ek,ele_k,e_l when ∥ek−el∥<0.5m\Vert e_k-e_l\Vert< 0.5 m, with $m=\mathop{\mathrm{median}}\nolimits_j\Vert e_j\Vert $ the median norm of the 128 columns. By epoch 20,000 every 100 columns form 31 components of near-identical columns (15 seeds) while validation accuracy stays at 0.89–1.00 (3 seeds). Training thus continues to simplify the solution and solves the same task with about a third as many distinct embedding columns. Such simplification is consistent with prior observations of a cleanup of memorizing components driven by weight decay in the same task (Nanda et al., 2023), of a bias toward low-rank solutions (Huh et al., 2023) and of attraction toward simpler subnetworks (Chen et al., 2023). Our framework adds the order and timing in which the units condense. The revision will add this count to Section 6.2 and state there that the cascade follows generalization.

We note that a merge produced by attraction should reassert itself after a perturbation. Testing attraction as the cause of the merges thus requires a counterfactual intervention on the merges themselves. We call two live columns (norm above 0.1m0.1 m) merged when they lie closer than 0.25m0.25 m and unmerged otherwise. We therefore hypothesize that merged columns when pulled apart come back within 0.25m0.25 m of their partners more often than unmerged columns starting at the same distance come that close. We intervene at epoch 12,000 while the cascade is under way between the second and third variance peaks. From the same checkpoint and random state we continue each run twice, once undisturbed and once with its merged pairs pulled apart. The two continuations differ only in this intervention and thus form a counterfactual pair. At that epoch the radius of 0.25m0.25 m yields 22–46 merged pairs per seed, more than the paper's link threshold of 0.14m0.14 m. An independent random shift of expected norm about 0.25m0.25 m to each of their columns moves these pairs 0.38–0.41 mm apart. As a null we follow the unmerged pairs of the same runs whose distance right after the shift falls within the central 80% of the distances of the separated pairs. Training then continues for 4,000 epochs, long enough for the return yet short enough that at most 0.5% of all unmerged pairs come within 0.25m0.25 m by chance.

We observe that 61–82% of the separated pairs come back within 0.25m0.25 m of their former partner, most of them within 500 epochs. Over the same window only 12–29% of the null pairs come that close (4 of 5 seeds; the fifth forms only 4 merged pairs). In the undisturbed continuation 73–87% of the merged pairs stay within 0.25m0.25 m. The separated pairs thus return almost as reliably as their undisturbed counterparts stay together. We therefore infer that attraction restores the merges, as stochastic attractivity (Definition 2.3) predicts. The revision will add this experiment to Appendix F.

References

  • Chen, Kunin, Yamamura & Ganguli. Stochastic collapse: how gradient noise attracts SGD dynamics towards simpler subnetworks. NeurIPS 2023.
  • Huh, Mobahi, Zhang, Cheung, Agrawal & Isola. The low-rank simplicity bias in deep networks. TMLR 2023.
  • Nanda, Chan, Lieberum, Smith & Steinhardt. Progress measures for grokking via mechanistic interpretability. ICLR 2023.

I would like to thank the authors for their rebuttal. The responses have addressed my concerns. I will keep my positive score.

Reviewer_ZWr4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Prior works have studied “stochastic collapse”, a phenomenon where two neurons are attracted to the same location in weight space during stochastic gradient descent due to permutation symmetry in multi-layer perceptron (MLP). In this work, authors introduce a graph based theory to understand stochastic collapse as a percolation process, where groups of neurons merge in the training dynamics, potentially resulting in discontinuous jumps in the size of the largest connected component. Such jump induces large variance in relative size of connected components, when they are averaged across many training runs. The theory predicts that the peaks in the variance form a geometric cascade structure. Finally, the authors test the theoretical prediction by examining toy models ranging from (i) flag and binary trees, (ii) MLPs, and (iii) Transformer learning modular-arithmetic.

Critical strengths

The author introduces an interesting conceptual bridge between the percolation process and stochastic collapse phenomenon in the training dynamics of neural networks. As a result, the theory proposes an interesting variable, the variance of the connected component size (with normalization), and the heights at their peaks as well as the scaling of transition times. Authors then design and test those predictions with toy experiments.

Critical weaknesses

A central concern regarding the theoretical results is how they were derived by making assumptions about balanced merging and a homogeneous coalescence kernel instead of deriving those results directly from architectural symmetries and/or stochastic gradient flow. Thus, current results largely put together existing theories on stochastic collapse and percolation theory, and the novelty of the authors’ claim is not clear.

I have similar concerns in authors’ empirical tests. The theoretical predictions are only directly tested with toy graph setups, but not with neural networks, where authors use variance peaks of spectral effective rank as a proxy instead.

Thus, the connections between the proposed theory and training dynamics of actual neural networks is not clear.

Questions for authors

How can we best establish the notion of the largest connected component in the Transformer? Currently authors infers the exponent of the kernel based on observed peak spacing. Can you estimate the coalescence kernel independently and predict the ratio of DSI scaling?

4 comments
AuthorsOpenReview ↗

First part of our response

We thank the reviewer for the questions on our assumptions, the effective rank and the kernel.

Critical Weakness 1: assumptions and novelty. Most analyses of neural-network training under variants of gradient descent focus on convergence. Yet in practice the weights do not converge to stationary points even after the training loss has stabilized; their distribution instead approaches an approximate invariant measure (Zhang et al., 2022). Which class of solution is learnt therefore depends on the path the dynamics take. Approaches such as saddle-to-saddle dynamics (Saxe et al., 2013; Jacot et al., 2021), mean-field limits (Mei et al., 2018; Chizat & Bach, 2018) and averaged descriptions of the noise (Blanc et al., 2020; Li et al., 2022b) study a smoothed statistical picture of this path. We instead base our intuition on studies of mechanistic interpretability (Nanda et al., 2023) and of low-rank biases (Huh et al., 2023). These studies lead us to postulate that the dynamics fundamentally consist of discrete events, with a smoothed description appropriate at larger scales and for coarser behavior. To this end, we build a formalism on stochastic attractivity (Chen et al., 2023) for discrete units of the architecture. As a first step, the present work restricts these units to symmetric subnetworks. In this setting we show that the series of discrete events forms a percolation process (Proposition 4.4). A merge rate that grows more slowly than component size makes this process self-similar in time. When merges join nn components at a time, the time TnkT_{n^k} at which components first reach size nkn^k grows by a fixed ratio Tnk+1/TnkT_{n^{k+1}}/T_{n^k} (Theorem 4.9). This self-similarity offers a potential mechanism for smooth emergent phenomena such as scaling laws (Remark C.25).

In a discrete event a subnetwork collapses reversibly into an invariant set. The key to understanding it is to treat the individual units as vertices of a graph. As collapse proceeds, distinct vertices merge into a single joint one and thereby drive connectivity upward. Because collapse is fast compared with the drift between events (Remark C.7; Li et al., 2022b), each collapse acts as an instantaneous link. Proposition 4.4 then renormalizes the resulting graph into a well-defined percolation process indexed by the fraction of completed merges. This process lets us compare connectivity across runs. With O=∣Cmax⁡∣/NO=|C_{\max}|/N for the largest component Cmax⁡C_{\max} among NN units and Rv=Var(O)/E(O)2R_v=\mathrm{Var}(O)/\mathbb{E}(O)^2, each merge of nn components appears as a peak of RvR_v with height (n−1)2/(4n)(n-1)^2/(4n) when a fraction 1/(n+1)1/(n+1) of the runs has completed it (Theorem 4.6). In the binary tree of Appendix E.5 the measured peak of RvR_v is 0.125, matching the predicted 1/81/8.

References

  • Blanc, Gupta, Valiant & Valiant. Implicit regularization for deep neural networks driven by an Ornstein–Uhlenbeck like process. COLT 2020.
  • Chen, Kunin, Yamamura & Ganguli. Stochastic collapse: how gradient noise attracts SGD dynamics towards simpler subnetworks. NeurIPS 2023.
  • Chizat & Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. NeurIPS 2018.
  • Huh, Mobahi, Zhang, Cheung, Agrawal & Isola. The low-rank simplicity bias in deep networks. TMLR 2023.
  • Jacot, Ged, Şimşek, Hongler & Gabriel. Saddle-to-saddle dynamics in deep linear networks: small initialization training, symmetry, and sparsity. arXiv:2106.15933, 2021.
  • Li, Wang & Arora. What happens after SGD reaches zero loss? A mathematical framework. ICLR 2022.
  • Mei, Montanari & Nguyen. A mean field view of the landscape of two-layer neural networks. PNAS 115(33), 2018.
  • Nanda, Chan, Lieberum, Smith & Steinhardt. Progress measures for grokking via mechanistic interpretability. ICLR 2023.
  • Saxe, McClelland & Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv:1312.6120, 2013.
  • Zhang, Li, Sra & Jadbabaie. Neural network weights do not converge to stationary points: an invariant measure perspective. ICML 2022.
AuthorsOpenReview ↗

Second part of our response

Critical Weakness 1, continued: the coalescence assumption. Assumption 4.7 has two parts. The first part treats merges as memoryless on a short enough time scale. The second lets components of sizes aa and bb link at a rate K(a,b)/NK(a,b)/N with K(ca,cb)=cγKK(a,b)K(ca,cb)=c^{\gamma_K}K(a,b). The peak of Theorem 4.6 holds independently of both parts. We test both parts in new measurements on the flat layer of Appendix E.5. Its link counts give γK=1.7\gamma_K=1.7. Rescaled by their total merge rate Λ/N\Lambda/N with Λ=∑pairs(ab)γK/2\Lambda=\sum_{\text{pairs}}(ab)^{\gamma_K/2}, its waits Δ\Delta between merges have σ/μ=0.95\sigma/\mu=0.95–0.980.98 at width 32. These values lie inside the 95% range of Exp(1)\mathrm{Exp}(1) waits normalized in the same windows, as memoryless merges require. With an exponent above 1 the kernel forms in finite time a giant component that absorbs the others (gelation; Escobedo et al., 2002), whereas the self-similar growth behind Theorem 4.9 needs the γK<1\gamma_K<1 of Assumption 4.7 (Aldous, 1999). The flat layer thus serves as a control outside the cascade of Theorem 4.9, as its exact-doubling share of only 3–11% shows (Table 2). The revision will add both tests to Appendix E.5. Remark F.2 already notes that such measurements also see a link rate varying with training time. Because σ/μ\sigma/\mu of the rescaled waits varies by at most 0.03 across windows from 125 to 500 steps, any change in this rate is slow on that scale. The revision will add this time dependence to Assumption 4.7 as a clock factor r(t)r(t), with merges running in the time τ(t)=∫0tr(s) ds\tau(t)=\int_0^t r(s)\,ds. For instance, a clock r(t)∝1/tr(t)\propto 1/t gives τ=log⁡t\tau=\log t. The merge statistics after a waiting time twt_w then depend only on τ(t)−τ(tw)=log⁡(t/tw)\tau(t)-\tau(t_w)=\log(t/t_w), the aging-like dynamics observed in network training (Baity-Jesi et al., 2018). Larger networks may need more than one such clock because their architectural parts can run at different paces. Extending the framework to several clocks could build on the calculus on time scales (Bohner & Peterson, 2001), a formalism that unifies continuous and discrete time.

References

  • Aldous. Deterministic and stochastic models for coalescence (aggregation and coagulation): a review of the mean-field theory for probabilists. Bernoulli 5(1), 1999.
  • Baity-Jesi et al. Comparing dynamics: deep neural networks versus glassy systems. ICML 2018.
  • Bohner & Peterson. Dynamic Equations on Time Scales: An Introduction with Applications. Birkhäuser, 2001.
  • Escobedo, Mischler & Perthame. Gelation in coagulation and fragmentation models. Commun. Math. Phys. 231, 2002.
AuthorsOpenReview ↗

Third part of our response

Critical Weakness 2: the effective rank as a proxy. The connected components of the graph that links nearby subnetworks record which subnetworks have merged. Measuring them directly requires identifying the symmetric subnetworks and comparing every pair of them at every snapshot of every run. This task grows combinatorially with the size of the network, especially when symmetries are nested. Large networks therefore need coarser order parameters that track the same transitions. Building on the hitting laws of Theorem C.23, we show in Appendix F that any order parameter changing monotonically with each merge of two components records the same transitions as ∣Cmax⁡∣/N|C_{\max}|/N. The effective rank of Section 6.2 is such an order parameter for the matrix whose columns hold the parameters of the subnetworks. When nn of these columns coincide they span a single direction and lower the effective rank by a definite step (Proposition F.1). When merges always join components of equal size, the same merge involves a largest component and hence enlarges Cmax⁡C_{\max}. The variances across runs of both order parameters therefore peak at the same times. Only the heights of the variance peaks differ because Theorem 4.6 fixes the height (n−1)2/(4n)(n-1)^2/(4n) for ∣Cmax⁡∣/N|C_{\max}|/N alone.

In the modular-arithmetic Transformer, a direct measurement is still possible. Every layer of this model reads from and adds to a residual stream of 128 dimensions. The parameters of a residual dimension kk are all weights that write into it or read from it. Permuting the 128 dimensions together with these weights leaves the network function unchanged. The residual dimensions are therefore interchangeable subnetworks. Among their weights the token embedding E∈R18×128E\in\mathbb{R}^{18\times128} writes into dimension kk through its column eke_k with one entry per token. When training brings two dimensions into their invariant set, all their weights coincide and in particular ek=ele_k=e_l. The distance ∥ek−el∥\|e_k-e_l\| is thus the embedding part of their distance from that set. For a link radius rr we link dimensions kk and ll when ∥ek−el∥<r m\|e_k-e_l\|<r\,m, with m=median⁡j∥ej∥m=\operatorname{median}_j\|e_j\|. The components of the resulting graph are the sets of dimensions that training has brought together.

We note that 1128EE⊤=Σ+eˉeˉ⊤\tfrac{1}{128}EE^\top=\Sigma+\bar e\bar e^\top is the second-moment matrix of the columns, with mean eˉ=1128∑kek\bar e=\tfrac{1}{128}\sum_k e_k and covariance Σ\Sigma. Because the singular values of EE are the square roots of the eigenvalues of EE⊤EE^\top, they and the effective rank exp⁡H(σ/∑kσk)\exp H(\sigma/\sum_k\sigma_k) depend only on these two moments. The mean squared distance between columns 11282∑k,l∥ek−el∥2=2tr⁡Σ\tfrac{1}{128^2}\sum_{k,l}\|e_k-e_l\|^2=2\operatorname{tr}\Sigma is thus fixed by the moments while the distance of any particular pair is not. We therefore hypothesize that the number of components falls further than the two moments explain whenever training enters invariant sets.

As a null we use Gaussian columns with the same mean and covariance. At every saved snapshot of every run, we draw a fresh set of such columns from the moments of the trained columns at that moment. The null thus follows the spectrum of the trained embedding through training. Because its columns are drawn independently, no pair in it is attracted to coincide. Its components therefore reflect only chance closeness at the given radius. We count the components of the trained and the null columns at the same epochs with the same link rule.

We observe 75, 48 and 31 components per 100 trained columns at r=0.5r=0.5 over the three variance peaks. The null stays at 86–90 over the same epochs (15 seeds). At every link radius from 0.14 to 0.6 the trained count stays at or below the null. We therefore infer that the residual dimensions merge far beyond what the two moments produce. The revision will add this measurement to Appendix F.

AuthorsOpenReview ↗

Fourth part of our response

Question: the largest connected component and the kernel. A connected component of a graph is a maximal set of vertices joined by paths of edges. Theorem 4.6 takes as order parameter the relative size O=∣Cmax⁡∣/NO=|C_{\max}|/N of the largest such component Cmax⁡C_{\max} among NN vertices and shows that Rv=Var(O)/E(O)2R_v=\mathrm{Var}(O)/\mathbb{E}(O)^2 across runs peaks at each merge. In the Transformer the vertices are the 128 dimensions of the residual stream that every layer reads from and adds to. A permutation of these dimensions applied to all weights that read or write them leaves the network unchanged. The graph GtG_t of Definition 3.3 links two dimensions kk and ll while the transverse distance Ykl=12∣θ(k)−θ(l)∣2Y_{kl}=\tfrac12\\|\theta^{(k)}-\theta^{(l)}\\|^2 between their weights stays inside the tube. The token embedding E∈R18×128E\in\mathbb{R}^{18\times128} contributes its columns eke_k and ele_l to these weights. Because the embedding part 12∣ek−el∣2\tfrac12\\|e_k-e_l\\|^2 bounds YklY_{kl} from below, the graph that links columns with ∣ek−el∣<r,m\\|e_k-e_l\\| < r\\,m contains every link of GtG_t. Here rr is the link radius and m=median⁡j∣ej∣m=\operatorname{median}_j\\|e_j\\| the median column norm. The largest component of the embedding graph therefore bounds ∣Cmax⁡∣|C_{\max}| of GtG_t from above. At the paper's link distance it holds a single column until epochs 6,000–9,000 and at most 0.05 of the columns by epoch 20,000 (3 seeds). Over the same epochs the share of columns linked to at least one other rises from 0 to 0.22–0.30 while the moment-matched null stays at 0. The largest component thus stays at a few columns while pairs form across the embedding. The revision will add these curves to Appendix F.

The kernel K(a,b)K(a,b) of Assumption 4.7 sets the rate K(a,b)/NK(a,b)/N at which a component of size aa links to one of size bb among NN units. Because the kernel is homogeneous of degree γK\gamma_K, the ratio K(2,2)/K(1,1)=2γKK(2,2)/K(1,1)=2^{\gamma_K} fixes its exponent and with it the ratio qni/qi=n1−γKq_{ni}/q_i=n^{1-\gamma_K} between the times qiq_i of successive variance peaks (Theorem 4.9). We estimate K(2,2)/K(1,1)K(2,2)/K(1,1) independently of the variance peaks, from new link counts in the flat layer of Appendix E.5. Remark F.2 notes that a link rate varying with training time enters such measurements alongside the size dependence of the kernel. To remove it from the estimate we let every rate carry a common clock factor r(t)r(t), an extension the revision will add to Assumption 4.7. If DsD_s of the TsT_s pairs of size-ss components link within a short window [t,t+Δ][t,t+\Delta] under a clock r(t)r(t), then

E[Ds]=Ts,K(s,s)N∫tt+Δr(u),du⟹D2/T2D1/T1≈K(2,2)K(1,1)=2γK.\mathbb{E}[D_s]=T_s\\,\frac{K(s,s)}{N}\int_t^{t+\Delta}r(u)\\,du\quad\Longrightarrow\quad\frac{D_2/T_2}{D_1/T_1}\approx\frac{K(2,2)}{K(1,1)}=2^{\gamma_K}.

The clock cancels because pairs of both sizes share it. At the paper's link distance 2ϵ=0.14\sqrt{2\epsilon}=0.14 the estimator gives γ^K=1.7\hat\gamma_K=1.7 with 95% interval [1.3,2.1][1.3,2.1]. At link distances 0.077 and 0.045 it gives γ^K=2.0\hat\gamma_K=2.0 and 1.81.8, both inside that interval. The estimate thus does not depend on the link threshold. All three values agree with γK=2\gamma_K=2 of the multiplicative kernel K(a,b)=abK(a,b)=ab, under which every pair of units links independently at the same rate. This kernel describes the component sizes of the Erdős–Rényi random graph (Aldous, 1999). The value γ^K=1.7\hat\gamma_K=1.7 lies in the regime γK>1\gamma_K > 1 in which a giant component forms in finite time and absorbs the others (gelation; Escobedo et al., 2002). Because Theorem 4.9 needs the γK<1\gamma_K < 1 of Assumption 4.7, the flat layer lies outside its cascade with an exact-doubling share of only 3–11% (Table 2). However, we observe a different picture when we sort the merges of the Transformer's token-embedding columns at the same link distance by the sizes of the two components they join. Of the 160 merges between components of equal size, 155 pair two single columns (5 seeds). The largest component of this embedding graph meanwhile holds at most 0.05 of the columns, as the first paragraph shows. We therefore infer that in its token embedding the Transformer forms pairs without a giant component through epoch 20,000. The revision will add the estimate and this classification of merges to Remark F.2.

References

  • Aldous. Deterministic and stochastic models for coalescence (aggregation and coagulation): a review of the mean-field theory for probabilists. Bernoulli 5(1), 1999.
  • Escobedo, Mischler & Perthame. Gelation in coagulation and fragmentation models. Commun. Math. Phys. 231, 2002.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.