Skip to content
Book Open access

Gradient Interaction Graph Optimization

Nov 2026 · Proceedings of the 35th ACM International Conference on Information and Knowledge Management · 0 citations · 44 references

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.

Read PDF

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.