🔢 mathematics

Sign compression for Muon: SignMuon, MuonSign, and the Limits of Error Feedback

This paper introduces SignMuon, a one-bit compression method for the Muon optimizer that, despite theoretical divergence and the failure of error feedback to fix it, empirically outperforms provably convergent variants across various benchmarks, highlighting a significant gap between theoretical guarantees and practical performance in low-bit optimization.

Original authors: Maria Smirnova, Alexey Kravatskiy

Published 2026-08-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Maria Smirnova, Alexey Kravatskiy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a giant, super-smart robot how to recognize cats in photos. To do this, the robot has to learn from millions of pictures, and every time it makes a guess, it sends a message back to a central brain to say, "I think I need to adjust my thinking this way." The problem is, these messages are huge. They are like sending a full encyclopedia every time you want to say "yes" or "no." If you have to send these massive encyclopedias over a slow internet connection, the whole learning process grinds to a halt, waiting for the data to arrive.

To fix this, scientists invented a trick called "compression." Instead of sending the whole encyclopedia, you just send the most important word: the sign. Is the adjustment positive (up) or negative (down)? That's it. Just one bit of information. It's like shouting "UP!" or "DOWN!" instead of sending a detailed map. This saves a ton of bandwidth and lets the robot learn much faster. But there's a catch: sometimes, when you throw away all the details and only keep the direction, you accidentally mess up the math. The robot might start walking in circles or even walking backward, thinking it's going forward. This paper is about finding the perfect way to shout "UP!" or "DOWN!" so the robot actually learns, without getting lost.

The Great Sign-Compression Experiment

In the world of training artificial intelligence, there is a popular method called Muon. Think of Muon as a very sophisticated GPS for our robot. Unlike older methods that treat every part of the robot's brain as a separate, isolated item, Muon looks at the whole picture. It understands that the robot's brain is made of grids of numbers (matrices), and it uses a special geometric rule to figure out the best path forward. It's like a GPS that knows the terrain is a mountain range and picks a path that respects the shape of the hills, rather than just trying to walk in a straight line.

However, Muon is heavy. It sends full, detailed maps (32 bits of data) for every single step. When you try to use it with the "shout UP or DOWN" trick (sign compression) to save bandwidth, things get weird. The authors of this paper, Maria Smirnova and Alexey Kravatskiy, decided to test three different ways to combine Muon's smart GPS with the simple "UP/DOWN" shout.

The Three Ways to Shout

They set up three different strategies, like three different teams trying to navigate a maze:

SignMuon (The "Shout After" Team): First, Muon calculates the perfect, detailed path. Then, they look at that path and shout "UP!" or "DOWN!" for every single step. This seems the most logical: get the smart direction first, then simplify it.
MuonUSign (The "Shout Before" Team): First, they shout "UP!" or "DOWN!" at the raw data before Muon does its smart math. Then, Muon tries to figure out the best path based on those simple shouts.
MuonSign (The "Shout Both Ways" Team): They shout before and after. They shout at the raw data, let Muon do its thing, and then shout again at the result. This is the most extreme compression, sending only "UP" or "DOWN" in both directions.

The Shocking Discovery: Logic vs. Reality

Here is where the story gets twisty. The authors did some rigorous math (proving it with theorems) and found something surprising: None of these three methods are guaranteed to work.

In fact, they proved that on certain simple, straight-line problems, all three methods can actually make the robot walk backward. Imagine a robot trying to walk down a straight hallway. Instead of walking forward, the math gets confused, and the "UP/DOWN" shout makes it take a step backward every single time. The robot gets further and further from the goal, no matter how small the steps are.

The authors even built specific, tiny examples (like a 4x4 or 5x5 grid) where they could show this happening. They proved that if you try to fix this by keeping a "memory" of the mistakes (a technique called error feedback), it doesn't help the "Shout After" team (SignMuon). The robot still gets stuck walking backward.

The "Magic" Fix That Works (But Isn't the Best)

So, if the obvious ways fail, what works? The authors found that if you change what you compress, you can save the day.

Instead of compressing the final direction, they compress the raw data before Muon does its magic, and they use a special "memory" system to fix the mistakes. They created two new methods: EF21-MuonUSign and EF21-MuonSign.

These methods do work mathematically. The authors proved that they will eventually find the goal, even on difficult, non-linear problems. They are the "safe" choices that won't make the robot walk backward forever.

The Plot Twist: Theory vs. Reality

If the "safe" methods are the only ones that work mathematically, you'd expect them to be the champions in the real world, right? Wrong.

The authors ran massive experiments on real-world tasks:

Teaching a robot to recognize cats and dogs (CIFAR-10).
Training a robot to write like a human (nanoGPT).

And the results were the exact opposite of the math. The "safe" methods (the ones with the guarantees) were slower and less accurate. The method that the math said was broken—the "Shout After" method (SignMuon)—was actually the winner.

In every single test, SignMuon performed the best. It learned faster and got higher scores than the "safe" methods, even though the authors had proven it should fail on simple problems.

Why Does This Happen?

The paper suggests that the "broken" math only happens in very specific, weird situations that don't usually occur in real life. The "Shout After" method (SignMuon) seems to have a hidden superpower that the math proofs didn't catch. It turns out that in the messy, complex world of real data, the simple act of compressing the final direction works better than the complex, "safe" error-correction systems.

The authors conclude that while they can prove the "safe" methods will work, the "risky" method (SignMuon) is the one that actually gets the job done. It's a reminder that in the wild world of AI, sometimes the heuristic (the rule of thumb) beats the guarantee. The "Shout After" team wins the race, even though the referee (the math) said they shouldn't be allowed to run.

The Takeaway

This paper is a story about the tension between theory and practice.

Theory says: "Don't use SignMuon; it can make the robot walk backward."
Practice says: "SignMuon is the fastest and best."

The authors didn't solve the mystery of why the theory fails in practice, but they documented it clearly. They showed us that while we can build a robot that is mathematically guaranteed to never fall off a cliff, the robot that takes a few risky jumps might actually reach the finish line first. For anyone building AI systems, the lesson is clear: trust the math to keep you safe, but trust the experiments to tell you what actually works.

Technical Summary: Sign Compression for Muon

Problem Statement
Training deep neural networks across distributed clients or under bandwidth constraints requires compressing the updates transmitted between workers and servers. While SignSGD offers an extreme compression ratio of one bit per coordinate, it flattens weight matrices into vectors, discarding the matrix structure that advanced optimizers like Muon exploit. Muon utilizes a Linear Minimization Oracle (LMO) based on the spectral norm to orthogonalize momentum matrices, yielding superior performance in various settings. However, Muon transmits dense, full-precision matrices (32 bits per parameter), creating a bottleneck. The central problem is to combine Muon's matrix-aware geometry with a one-bit communication budget without losing the descent property or convergence guarantees.

Methodology
The paper investigates three natural placements of the sign compression operator relative to the Muon LMO:

SignMuon: Signs the output of the LMO ( $\text{sign}(\text{LMO}(\cdot))$ ). This is the most direct approach, emitting a $\pm 1$ matrix.
MuonUSign: Signs the input to the LMO ( $\text{LMO}(\text{sign}(\cdot))$ ).
MuonSign: Signs both the input and the output ( $\text{sign}(\text{LMO}(\text{sign}(\cdot)))$ ).

The authors analyze these methods theoretically on linear objectives and smooth non-convex problems. They also introduce error-feedback variants (EF21) to address the bias introduced by sign compression:

EF21-SignMuon: Applies error feedback to the LMO output (the polar factor).
EF21-MuonUSign: Applies error feedback to the gradient before the LMO.
EF21-MuonSign: Applies error feedback to both the gradient (uplink) and the model update (downlink).

A key implementation detail is the "unit-gain heuristic" for per-layer step sizes, which scales the learning rate based on layer dimensions to ensure consistent root-mean-square (RMS) gain across layers of varying shapes, a necessity when mixing LMO-based steps (norm $\sqrt{r}$ ) and sign-based steps (norm $\sqrt{mn}$ ).

Key Contributions

Divergence of Direct Combinations: The paper proves that none of the three direct sign placements (SignMuon, MuonUSign, MuonSign) guarantee descent in general. Specifically, the authors construct explicit, small-scale counterexamples (4x4 and 5x5 matrices) where each method ascends on a linear objective for any step size and momentum coefficient. The composition of the sign operator and the spectral-norm LMO is shown to be an LMO for no norm, destroying the descent guarantee.
Failure of Error Feedback on the Oracle Output: The authors demonstrate that applying standard error feedback (EF21) to the LMO output (EF21-SignMuon) does not repair the divergence. They construct a smooth, bounded-below function where EF21-SignMuon diverges for every smoothness constant, step size, and momentum setting. The polar factor can move by a constant amount regardless of step size, preventing the error feedback estimator from tracking it.
Convergence of Gradient-Based Error Feedback: In contrast, applying error feedback to the gradient (before the LMO) restores convergence.
- EF21-MuonUSign achieves the standard $O(T^{-1/2})$ rate for the squared gradient norm on smooth non-convex problems with a one-bit uplink.
- EF21-MuonSign extends this to one bit in both directions (uplink and downlink) by adding a second error-feedback loop on the model, maintaining the same convergence rate.
Empirical Reversal of Theory: Despite the theoretical divergence of SignMuon, experimental results across centralized CIFAR-10, federated CIFAR-10, and a nanoGPT speedrun consistently show that SignMuon (the sign-after placement) is the strongest compressed method. It outperforms the theoretically convergent variants (EF21-MuonUSign, EF21-MuonSign) and matches full-precision Muon in many cases. The theoretically "safe" methods trail SignMuon by several seed spreads.

Results

Theoretical: The paper establishes that the "sign-after" placement is unrepairable by error feedback applied to the oracle output, while "sign-before" and "both-sides" placements with error feedback on the gradient are provably convergent.
Experimental:
- On Centralized CIFAR-10 (ResNet-18), SignMuon achieves 94.60% accuracy, matching full-precision Muon (94.35%) and significantly outperforming SignSGD (93.37%). The error-feedback variants (EF21-SignMuon) perform slightly worse than SignMuon.
- On Federated CIFAR-10 (N=11), SignMuon reaches 85.72% accuracy, trailing Muon (85.98%) by less than one standard deviation but exceeding SignSGD by 4.3 points. The ordering remains: SignMuon > MuonUSign > MuonSign. The convergent variants (EF21-MuonUSign/Sign) lag behind.
- On nanoGPT, SignMuon and EF21-SignMuon are indistinguishable and achieve validation losses within 0.01 of full-precision Muon, outperforming all other compressed methods.
Counterexamples: The constructed divergence instances are worst-case scenarios. On random quadratic problems, the alignment between the gradient and the step remains positive for all three placements, suggesting that ordinary data does not trigger the theoretical divergence.

Significance and Claims
The paper documents a tension between theoretical guarantees and practical performance in compressed optimization. It claims that while the "sign-after" placement (SignMuon) is theoretically unrepairable and can diverge on specific linear instances, it is the most effective heuristic in practice across diverse architectures and scales. The authors do not claim to resolve this tension but rather to characterize it: the counterexamples preclude a guarantee covering every problem in the class, but they do not preclude convergence under conditions satisfied by ordinary data.

The paper concludes that at current scales, the heuristic benefit of compressing after the LMO outweighs the lack of a theoretical guarantee. It identifies the main open question as identifying the specific conditions under which the "sign-after" placement converges, alongside investigating convergence rates for compressed downlinks and whether any one-bit compressor contracts in a layer norm. The work also clarifies that a concurrent proposal for SignMuon (Mishra et al., 2026) provides a guarantee for a different method (gradient-sign oracle) rather than the SignMuon update itself.