Gradient Interaction Graph Optimization
Abstract
Training large Transformer language models is dominated by the cost of synchronous parameter updates: every block of weights is moved at every step using a gradient computed before any block has moved. The resulting trajectory is wasteful, because per-block updates are evaluated on a frozen snapshot of the rest of the network that the next step will already invalidate. Second-order methods such as Shampoo and K-FAC address this spatially through preconditioning, and sharpness-aware methods such as SAM trade compute for sharper minima, but both leave the temporal coupling between blocks untouched. We introduce Gradient Interaction Graph Optimization (GIGO), a meta-optimizer that estimates a sparse directed graph of cross-block gradient dependencies online, partitions each step into contiguous sequential stages along this graph, and refreshes downstream gradients using a stale-activation approximation. The framework wraps any base optimizer, adds one cached boundary activation per stage (~32 MB at Tseq= 1024, scaling linearly with sequence length), and is compatible with mixed precision and data parallelism. On GPT-2 Small through XL (124M-1.5B), GIGO-Adam reaches the same OpenWebText/C4 perplexity in 32.0-34.0% fewer optimizer steps than synchronous AdamW --- a lead of 8-22 percentage points over the strongest 2024-vintage baselines (SOAP, Muon, Sophia, Lion, GaLore) on the Small comparison cohort --- with a per-step overhead of 32-38% and a net wall-clock benefit ranging from +5.2% (Small) to +16.2% (XL) across the four sizes tested. The benefit vanishes or reverses where the method's preconditions do not hold: a synthetic block-diagonal control (SRR=0.0%), the overhead-dominated Penn Treebank stress test (-18.5% wall-clock), and a weak-coupling small-vision-Transformer diagnostic (-12.4% wall-clock on CIFAR-100). Ablations decompose the mechanism: the partial-re-forward refresh primitive alone (random partition) accounts for 9.4% SRR, the interaction-graph schedule contributes a further ~22pp, and the layer-contiguity constraint controls overhead. Our convergence theorem matches the standard Adam O(T-1/4) rate uniformly in graph-estimation quality, providing a safety guarantee; the empirical step-reduction is reported as an empirical regularity not formally predicted by the theory.