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

SignMuon compresses the Muon update to one bit per parameter by signing the oracle's output. It beats SignSGD in practice, yet it can ascend on a linear function. Signing before the oracle does not repair this: one small explicit instance makes sign-before (MuonUSign) and sign-on-both-sides (MuonSign) ascend as well, so no placement of the sign around the Linear Minimization Oracle (LMO) descends in general. Error feedback does not repair sign-after either. Applied to the oracle's output it fails for every smoothness constant, step size and momentum. Applied to the gradient it works: EF21-MuonUSign and EF21-MuonSign attain the standard $\mathcal{O}(T^{-1/2})$ rate. Experiment then reverses the ordering. On CIFAR-10 and on the nanoGPT speedrun the strongest compressed method is sign-after-the-LMO, precisely the placement we prove divergent.