PaperlayerView exact revision on arXiv

Source-linked AI summary

The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks

Ziqian Zhong, Ziming Liu, Max Tegmark, Jacob Andreas

arXiv:2306.17844v2cs.LG

TL;DR

The paper asks whether neural networks trained on simple algorithmic tasks reliably rediscover known algorithms. Using modular addition, it analyzes learned implementations across models and training conditions, finding Clock, Pizza, and more complex procedures. The results motivate characterizing neural-network behavior across algorithmic phase spaces.

  • Problem

    The paper examines whether neural networks reliably rediscover familiar algorithms when trained on well-understood algorithmic tasks.

  • Method

    The authors train and analyze neural networks on modular addition using interpretability techniques that distinguish Clock, Pizza, and other algorithmic implementations.

  • Results

    Networks trained on modular addition implement the Clock algorithm, a Pizza algorithm, or more complex procedures, with different phases arising across architectures, hyperparameters, and seeds.

  • Takeaways & Limitations

    Algorithm-level interpretability should characterize algorithmic phase spaces rather than focus only on single algorithmic solutions.

  • Takeaways & Limitations

    The study focuses on a single learning problem, modular addition, and further work is needed to scale its techniques to more complex real-world models.

Abstract

from arXiv · show

Do neural networks, trained on well-understood algorithmic tasks, reliably rediscover known algorithms for solving those tasks? Several recent studies, on tasks ranging from group arithmetic to in-context linear regression, have suggested that the answer is yes. Using modular addition as a prototypical problem, we show that algorithm discovery in neural networks is sometimes more complex. Small changes to model hyperparameters and initializations can induce the discovery of qualitatively different algorithms from a fixed training set, and even parallel implementations of multiple such algorithms. Some networks trained to perform modular addition implement a familiar Clock algorithm; others implement a previously undescribed, less intuitive, but comprehensible procedure which we term the Pizza algorithm, or a variety of even more complex procedures. Our results show that even simple learning problems can admit a surprising diversity of solutions, motivating the development of new tools for characterizing the behavior of neural networks across their algorithmic phase space.

1 Introduction

The paper asks whether neural networks reliably rediscover familiar algorithms and finds that modular addition can produce multiple qualitatively different solutions. These results motivate characterizing algorithmic phase spaces rather than isolated algorithmic solutions.

  • The paper investigates whether neural networks reliably rediscover familiar algorithmic solutions across tasks such as modular arithmetic.
  • Networks trained on modular addition can implement the familiar Clock algorithm, the qualitatively different Pizza algorithm, or more complex procedures.
  • Changes in width and attention strength can produce sharp transitions between Clock, Pizza, and other algorithmic phases.
  • The results support studying algorithmic phase spaces, not just single solutions, in algorithm-level interpretability.
  • The paper examines these behaviors through reviews, empirical deviations, alternative algorithmic explanations, and metrics distinguishing algorithmic phases.

2 Modular Arithmetic and the Clock Algorithm

The paper studies neural implementations of modular addition, including the Clock algorithm and evidence that networks can deviate from it. It compares architectures, embeddings, gradients, logits, and tabulated algorithmic forms to characterize these differences.

  • Setup: The experiments train Model A, a constant-attention one-layer ReLU transformer, and Model B, a standard one-layer ReLU transformer, on modular addition with p = 59.
  • Setup: Both models usually represent integers as circular embeddings in the plane spanned by the first two principal components.
  • The Clock Algorithm: The Clock algorithm embeds inputs as 2D vectors, adds their polar angles, and extracts the modular sum using trigonometric identities.
  • Clock violations: The Clock algorithm relies on attention to perform multiplication, motivating tests of deviations in the attention-free Model A.
  • Gradient evidence: Model A exhibits gradient symmetry, whereas the Clock algorithm generically has asymmetric gradients under argument permutation.
  • Logit evidence: Model A’s correct logits depend clearly on a −b, unlike Model B’s, indicating that the models implement different algorithms.

3 An Alternative Solution: the Pizza Algorithm

The Pizza algorithm is an alternative to Clock: it classifies sums using points inside the embedding circle, producing logits that depend on input differences. Circle isolation and variance analysis support this interpretation, while accompanying pizzas mitigate antipodal failures.

  • Pizza mechanism: The Pizza algorithm averages input embeddings inside the circle and assigns labels according to which radial lines their midpoint lies closest to.For each fixed output c, inputs satisfying a + b = c form a line through the origin; nearby points define mirrored pizza slices.
  • Pizza mechanism: Unlike Clock, Pizza requires absolute values rather than input multiplication, making it naturally compatible with ReLU layers.Clock uses multiplication in its second step, whereas Pizza uses absolute value computation.
  • Logit evidence: Pizza logits include an extra factor based on a −b, so correct-logit strength varies with the distance between the two inputs.The factor |cos(w_k(a −b)/2)| reflects the length of the averaged embedding vector.
  • Logit evidence: Circle isolation preserves interpretable algorithmic behavior: Model A loses accuracy at particular a −b values, whereas Model B remains invariant to a −b.Using two principal components gives Model A 32.8% accuracy; using six gives 91.4%, while Model B achieves 100% after isolation.
  • Logit evidence: The Pizza formula explains substantially more variance in Model A’s isolated logits than the Clock formula.Table 2 compares normalized formula outputs with all Model A output logits after circle isolation.
  • Error correction: Antipodal input pairs remain the Pizza algorithm’s Achilles’ heel because their midpoints collapse to the origin despite having different labels.Approximately antipodal pairs are also more likely to be misclassified when p is odd.
  • Error correction: Accompanying pizzas compensate for antipodal weaknesses, but the accompanying components contribute little to final predictions after training.Accompanied pizzas reach 99.7% accuracy, compared with 16.7% for accompanying pizzas.

4 The Algorithmic Phase Space

The paper characterizes Clock and Pizza with two metrics and finds representational phase transitions as attention rate and model width vary. Circular models mostly implement one of these algorithms, while deeper or other settings can yield non-circular or hybrid solutions.

  • Metrics: Gradient symmetricity and distance irrelevance are proposed as quantitative metrics for distinguishing Pizza from Clock.Pizza has symmetric gradients and low distance irrelevance, whereas Clock has asymmetric gradients and higher distance irrelevance.
  • Metrics: Model A and Model B have gradient symmetricity values of 99.37% and 33.36%, respectively.The metric is computed from cosine similarities between gradients for swapped inputs.
  • Metrics: Model A and Model B have distance irrelevance values of 0.17 and 0.85, respectively.Typical Pizza values range from 0 to 0.4, while typical Clock values range from 0.4 to 1.
  • Metrics: Distance irrelevance is treated as decisive for identifying Pizza, while gradient symmetricity can rule out Clock; low distance irrelevance usually coincides with symmetric gradients.The two metrics can conflict, but the authors assign them these complementary diagnostic roles.
  • Algorithmic phases: Circular models predominantly implement either Clock, marked by low gradient symmetricity, or Pizza, marked by low distance irrelevance.The study also reports other algorithmic solutions outside this dominant circular pattern.
  • Algorithmic phases: The transition from Pizza to Clock is sharp and approximately linear in attention rate and layer width.The attention-rate transition point increases as the model becomes wider.
  • Algorithmic phases: Clock dominates above the phase-change point, whereas Pizza dominates below it; the authors associate this split with attention versus linear-layer prominence.Higher attention rates favor Clock, while lower rates favor Pizza.
  • Algorithmic phases: Increasing model width raises the phase-change point because wider linear layers become more capable relative to attention outputs.The authors explain that attention outputs remain scalar while linear-layer outputs become wider vectors.

5 Related Work

The paper situates its analysis within mechanistic interpretability, mathematical-task benchmarks, studies of algorithmic phase transitions, and work on emergent abilities and learned circuits.

  • Mechanistic interpretability: Mechanistic interpretability reverse-engineers neural networks through patterns in weights, activations, neurons, modules, and circuits.The cited approaches include single-neuron analyses and grouped circuit-level analyses.
  • Mathematical tasks: Mathematical tasks serve as useful interpretability benchmarks because their underlying structures are well understood.Prior work studies arithmetic, geometry, knot theory, group theory, images, embeddings, and numerical inputs.
  • Algorithmic phase transitions: Algorithmic phase transitions usually describe sharp performance changes as parameters such as data or capacity vary.This paper instead studies representational transitions between equally accurate internal algorithms.
  • Algorithmic phase transitions: The paper’s phase transitions differ because Clock and Pizza can both achieve perfect accuracy while using different internal computations.The authors characterize these model-internal transitions as closer to representational changes than ordinary performance transitions.
  • Algorithm learning: Work on emergent abilities links changing capabilities to model scale, metric choice, and potentially the formation of modular circuits.The paper places its algorithm-learning analysis alongside this broader literature on learned capabilities.

6 Conclusions

The paper finds that modular addition networks do not inevitably rediscover the Clock algorithm: qualitatively different solutions, including Pizza and more complex procedures, are prevalent. This motivates characterizing algorithmic phase spaces, while the study remains limited to one learning problem and does not yet scale to more complex real-world models.

  • Conclusions: Qualitatively different algorithms emerge across architectures and random seeds, including the Clock algorithm, the Pizza algorithm, and more complicated procedures.The paper presents these behaviors as evidence that algorithmic discovery is not inevitable in modular arithmetic.
  • Limitations: The study focuses on a single learning problem, modular addition, limiting the demonstrated scope of its conclusions.
  • Limitations: The authors state that substantial additional work is needed to extend these techniques to the more complex models used in real-world tasks.

A Mathematical Analysis and An Example of Pizza Algorithm

The Pizza algorithm arises from circular embeddings whose midpoint representations produce logits with a difference-dependent factor. The analysis also motivates circularity as a filter because trained networks can instead use non-circular embedding geometries.

  • Pizza derivation: The approximation |cos(t)| − |sin(t)| ≈ cos(2t) supplies the trigonometric step underlying the Pizza output pattern.
  • Pizza algorithm: The construction uses circular embeddings, computes a midpoint-related representation, and obtains the output through a dot product.The derived logits are approximately |cos(w_k(a −b)/2)| cos(w_k(a + b −c)).
  • Pizza derivation: The Pizza algorithm generalizes symmetric trigonometric combinations into a difference-dependent factor multiplied by a function of the input sum.A lemma states that symmetric linear combinations of sine and cosine terms can be written as cos((x − y)/2)g(x + y).
  • Algorithmic signature: The Pizza algorithm is identified by its |cos(w_k(a −b)/2)| output factor rather than by one specific computation circuit.
  • Non-circular algorithms: Non-circular embeddings, including line-like and three-dimensional Lissajous-like patterns, complicate the analysis and are left for future study.Circularity is therefore proposed as a filtering metric for the paper’s primary focus on circular algorithms.
  • Circularity: Circularity reaches 1 when the first four principal components align with Fourier waves, and Models A and B measure around 99.8%.The study treats models with circularity ≥99.5% as circular.

C More Results from the Main Experiments

Additional experiments show that circular solutions occur across one- to four-layer transformers, while Pizza behavior is accompanied by a concrete near-antipodal failure mode and compensatory circles. Model A nevertheless reaches 100% accuracy when six circles are included.

  • Experiment coverage: Unfiltered non-circular networks add noise to the training-result plots, while multi-layer transformers provide results for 2–4 layers.
  • Circular solutions: 34.31% of trained 1-layer transformers with fixed width 128 are circular.
  • Pizza limitations: Near-antipodal inputs make the midpoint norm small and the Pizza result noise-sensitive, creating a concrete weakness of the algorithm.Strict antipodal pairs collapse to the origin, where different labels cannot be distinguished reliably.
  • Accompanying pizzas: An accompanying pizza changes the spacing between adjacent circle points so formerly near-antipodal pairs become easier to classify.For the construction described, the adjacent-number difference changes from 2k to k modulo p.
  • Accompanying pizzas: Model A reaches 100% accuracy when the six pizza and accompanying-pizza circles are included in its embedding.
  • Circular solutions: Among 2-, 3-, and 4-layer transformers, respectively 9.95%, 11.55%, and 6.08% are circular.

E Results in Other Linear Architectures

Small architectural changes produce qualitatively different modular-addition solutions, including Pizza-like, Clock-like, and non-circular behaviors. These results show that induction biases and hyperparameters shape the algorithmic solutions discovered from the same task.

  • Comparing linear models: Models α, β, and δ produced radically different results, while β and γ were more Pizza-like than α.β and γ had lower distance irrelevancy and higher circularity than α.
  • Comparing linear models: Concatenating embeddings instead of adding them made one-layer Model δ more likely to be non-circular and highly distance-irrelevant.Model δ differed sharply from Model α despite both being one-layer linear models.
  • Interpreting learned algorithms: Models β and δ implemented Pizza-like procedures observable through circle-isolated correct-logit patterns, although δ remained distinct from the Clock pattern.The study leaves the detailed analysis of these models for future work.
  • Setup variations: A width-1024 transformer with normal attention produced a circular Pizza model with distance irrelevance 0.156 and gradient symmetricity 0.995.These values fit the paper’s definition of Pizza.
  • Setup variations: GeLU activations, differently embedded tokens, and an added equal sign preserved very similar training-result patterns across the tested one-layer transformer variations.With different token embeddings, the embeddings were often aligned to implement Pizza and Clock algorithms.

J Pizza Occurs Early in the Clock Training

Pizza-like structure can appear early during training of a model that ultimately develops Clock-like behavior, then gradually disappear. This pattern persists across several one-layer transformer setup variations.

  • Training dynamics: Pizza-like correct-logit patterns appeared early in attention-model training but gradually disappeared during the run.The progression was visualized through principal-component isolations at multiple training states.
  • Setup variations: GeLU activation produced training results very similar to those obtained with ReLU.Each plotted point represented a run reaching 100% validation accuracy.
  • Setup variations: Using different embeddings for the two tokens also produced similar results, while aligned embeddings often implemented Pizza or Clock.The resulting correct-logit pattern shifted because the two token embeddings did not exactly align.
  • Setup variations: Adding an equal-sign token likewise yielded very similar training results.Circularity was not used to filter this variation because it was no longer well-defined.

K Accompanying Pizza Occurs Early in the Pizza Training

Accompanying Pizza structure emerges early in some training runs and contributes to accuracy, while weight and representation analyses explain how multiple Pizza circuits operate in parallel.

  • Early accompanying Pizza: Without attention, an accompanying-Pizza pattern emerged early, and removing its circle reduced accuracy from 99.7% to 97.9%.The accompanying pizzas were less helpful later in the trained network.
  • Representation structure: Embedding and unembedding matrices formed matching circles with the same gap between adjacent entries.This matching structure provides the principal-component basis for analyzing Pizza circuits.
  • Pizza mechanism: Each Pizza circuit embeds inputs on a circle, adds the embeddings, applies piecewise-linear transformations, and maps the result to output logits.The added embeddings encode a factor depending on a − b and a direction depending on a + b.
  • Weight analysis: Removing the second-layer ReLU preserved 100% accuracy while reducing cross-entropy loss from 6.20 × 10^-7 to 5.89 × 10^-7.This supports treating that ReLU as non-functional in the analyzed model.
  • Parallel Pizza circuits: Aligned weight matrices showed a domino-like pattern in which most dimensions corresponded to one matching-circle pair, allowing pizzas to operate with limited interference.Each immediate dimension served exactly one Pizza circuit.
  • Pizza mechanism: The learned two-dimensional function approximated 8 cos(2t + 2), yielding the Pizza logit form after substituting t = w_k(a + b)/2.Ignoring phase and scaling gives the factorized form described for the circuit.
Loading 2306.17844v2…