Skip to main content

hyprstream_inference/training/
muon.rs

1//! Muon optimizer: MomentUm Orthogonalized by Newton-Schulz.
2//!
3//! Designed for 2D weight matrices (LoRA A/B). Orthogonalizes gradient
4//! updates so all singular values → 1, making each step maximally effective.
5//!
6//! Reference: https://github.com/vukrosic/muon-optimizer-guide
7//! Algorithm: Nesterov momentum + Newton-Schulz (Polar Express variant)
8
9use std::collections::HashMap;
10use tch::{Kind, Tensor};
11
12/// Polar Express coefficients for Newton-Schulz iteration.
13/// Pre-optimized for fast convergence in bfloat16; also converge
14/// acceptably in float16 and float32.
15const POLAR_EXPRESS_COEFFS: [(f64, f64, f64); 5] = [
16    (8.156554524902461, -22.48329292557795, 15.878769915207462),
17    (4.042929935166739, -2.808917465908714, 0.5000178451051316),
18    (3.8916678022926607, -2.772484153217685, 0.5060648178503393),
19    (3.285753657755655, -2.3681294933425376, 0.46449024233003106),
20    (2.3465413258596377, -1.7097828382687081, 0.42323551169305323),
21];
22
23/// Choose the best compute dtype for Newton-Schulz based on input dtype.
24///
25/// - **BFloat16/Float16**: Stay native (coefficients tuned for bf16, good GPU throughput)
26/// - **Float32/Float64**: Use Float32 (CPU path or GPUs without bf16 support)
27/// - **Float8/other**: Upcast to Float32 (too few mantissa bits for NS convergence)
28fn ns_compute_kind(input_kind: Kind) -> Kind {
29    match input_kind {
30        Kind::BFloat16 => Kind::BFloat16,
31        Kind::Half => Kind::Half,
32        // Float32, Float64, FP8, and all other types: use Float32.
33        // FP8 has only 3-4 mantissa bits; NS iteration diverges without upcast.
34        _ => Kind::Float,
35    }
36}
37
38/// Newton-Schulz iteration for matrix orthogonalization.
39///
40/// Maps G → UV^T (its orthogonal factor) by converging all singular values
41/// to 1, without ever computing an expensive SVD.
42///
43/// Uses the Polar Express variant with pre-optimized coefficients for
44/// stable bfloat16 computation. Compute dtype is chosen adaptively:
45/// bf16/fp16 stay native for GPU throughput, fp8 is upcasted to float32.
46///
47/// # Arguments
48/// * `g` - 2D gradient matrix [rows, cols]
49/// * `steps` - Number of Newton-Schulz iterations (default: 5)
50pub fn newton_schulz_orthogonalize(g: &Tensor, steps: usize) -> Tensor {
51    let _guard = tch::no_grad_guard();
52    assert!(
53        g.dim() == 2,
54        "Newton-Schulz requires 2D matrix, got {}D",
55        g.dim()
56    );
57    assert!(steps <= POLAR_EXPRESS_COEFFS.len());
58
59    let compute_kind = ns_compute_kind(g.kind());
60    let mut x = g.to_kind(compute_kind);
61
62    // Algorithm assumes wide (rows ≤ cols) matrices — transpose tall ones
63    let transposed = x.size()[0] > x.size()[1];
64    if transposed {
65        x = x.tr();
66    }
67
68    // Normalize so largest singular value starts near 1
69    let norm = x.norm_scalaropt_dim(2i64, &[-2i64, -1i64][..], true);
70    x = &x / (&norm * 1.01 + 1e-7);
71
72    // Newton-Schulz iterations — converge singular values to 1
73    for &(a, b, c) in &POLAR_EXPRESS_COEFFS[..steps] {
74        let a_mat = x.matmul(&x.tr()); // A = X @ X^T (small: [min_dim, min_dim])
75        x = a * &x + (b * &a_mat + c * a_mat.matmul(&a_mat)).matmul(&x);
76    }
77
78    if transposed {
79        x.tr()
80    } else {
81        x
82    }
83}
84
85/// Muon optimizer configuration.
86#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
87pub struct MuonConfig {
88    /// Learning rate (default: 0.02 — much larger than AdamW's 3e-4)
89    #[serde(default = "default_muon_lr")]
90    pub lr: f64,
91    /// Nesterov momentum coefficient (default: 0.95)
92    #[serde(default = "default_muon_momentum")]
93    pub momentum: f64,
94    /// Weight decay (default: 0.0 — rarely needed for Muon-optimized params)
95    #[serde(default)]
96    pub weight_decay: f64,
97    /// Number of Newton-Schulz iterations (default: 5)
98    #[serde(default = "default_ns_steps")]
99    pub ns_steps: usize,
100}
101
102fn default_muon_lr() -> f64 {
103    0.02
104}
105pub(crate) fn default_muon_momentum() -> f64 {
106    0.95
107}
108fn default_ns_steps() -> usize {
109    5
110}
111
112impl Default for MuonConfig {
113    fn default() -> Self {
114        Self {
115            lr: default_muon_lr(),
116            momentum: default_muon_momentum(),
117            weight_decay: 0.0,
118            ns_steps: default_ns_steps(),
119        }
120    }
121}
122
123/// Per-parameter state for Muon optimizer.
124#[derive(Debug, Default)]
125pub struct MuonState {
126    pub momentum_buffer: Option<Tensor>,
127}
128
129impl MuonState {
130    pub fn new() -> Self {
131        Self {
132            momentum_buffer: None,
133        }
134    }
135}
136
137/// Perform a single Muon optimization step on a 2D parameter.
138///
139/// Algorithm:
140/// 1. Nesterov momentum: buf = lerp(buf, grad, 1-momentum); g = lerp(grad, buf, momentum)
141/// 2. Orthogonalize: g = newton_schulz(g) → UV^T (all SVs = 1)
142/// 3. Weight decay: p *= (1 - lr * wd)
143/// 4. Scale for rectangularity: scale = sqrt(max(1, rows/cols))
144/// 5. Update: p -= lr * scale * g
145pub fn muon_step(param: &Tensor, state: &mut MuonState, config: &MuonConfig) {
146    let _guard = tch::no_grad_guard();
147    let grad = param.grad();
148    if !grad.defined() {
149        return;
150    }
151
152    // 1. Nesterov momentum
153    let buf = state
154        .momentum_buffer
155        .get_or_insert_with(|| Tensor::zeros_like(&grad));
156    let _ = buf.lerp_(&grad, 1.0 - config.momentum);
157    let g = grad.lerp(buf, config.momentum);
158
159    // 2. Orthogonalize
160    let g_flat = g.view([g.size()[0], -1]);
161    let g_orth = newton_schulz_orthogonalize(&g_flat, config.ns_steps);
162    let g_orth = g_orth.view_as(&g).to_kind(param.kind());
163
164    // 3. Weight decay (decoupled) + 4. Scale for rectangularity + 5. Update
165    // Combined into a single fused operation to minimize tensor allocations.
166    let (rows, cols) = (param.size()[0] as f64, param.size()[1] as f64);
167    let scale = (1.0f64.max(rows / cols)).sqrt();
168    let decay = 1.0 - config.lr * config.weight_decay; // 1.0 when weight_decay=0
169                                                       // p = p * decay - lr * scale * g_orth
170    let updated = &param.data() * decay - &g_orth * (config.lr * scale);
171    param.data().copy_(&updated);
172}
173
174/// Snapshot all Muon momentum buffers for rollback.
175pub fn snapshot_muon_states(states: &HashMap<String, MuonState>) -> HashMap<String, Tensor> {
176    let _guard = tch::no_grad_guard();
177    states
178        .iter()
179        .filter_map(|(k, s)| s.momentum_buffer.as_ref().map(|b| (k.clone(), b.copy())))
180        .collect()
181}
182
183/// Restore Muon momentum buffers from a snapshot.
184pub fn restore_muon_states(
185    states: &mut HashMap<String, MuonState>,
186    snapshot: &HashMap<String, Tensor>,
187) {
188    let _guard = tch::no_grad_guard();
189    for (k, snap_buf) in snapshot {
190        if let Some(state) = states.get_mut(k) {
191            if let Some(ref mut buf) = state.momentum_buffer {
192                buf.copy_(snap_buf);
193            } else {
194                state.momentum_buffer = Some(snap_buf.copy());
195            }
196        }
197    }
198}
199
200#[cfg(test)]
201#[allow(clippy::expect_used, clippy::unwrap_used)]
202mod tests {
203    use super::*;
204
205    /// Create a well-conditioned test matrix with controlled singular values.
206    /// Uses an outer product construction: U @ diag(sigma) @ V^T where U, V
207    /// are simple orthogonal-ish matrices from sequential values.
208    fn well_conditioned_matrix(rows: i64, cols: i64) -> Tensor {
209        // Use arange-based construction (deterministic, no random state)
210        let a = Tensor::arange(rows * cols, (Kind::Float, tch::Device::Cpu)).reshape([rows, cols]);
211        // Add identity-like structure to improve conditioning
212        let min_dim = rows.min(cols);
213        let eye = Tensor::eye(min_dim, (Kind::Float, tch::Device::Cpu));
214        let padded = Tensor::zeros([rows, cols], (Kind::Float, tch::Device::Cpu));
215        // Narrow view into padded to place eye
216        let mut narrow_r = padded.narrow(0, 0, min_dim).narrow(1, 0, min_dim);
217        narrow_r.copy_(&(&eye * 10.0));
218        &a + padded
219    }
220
221    #[test]
222    fn test_newton_schulz_produces_orthogonal() {
223        let _guard = tch::no_grad_guard();
224        let g = well_conditioned_matrix(8, 64);
225        let q = newton_schulz_orthogonalize(&g, 5);
226        // Q should satisfy Q @ Q^T ≈ I (orthonormal rows)
227        let qqt = q.matmul(&q.tr());
228        let eye = Tensor::eye(8, (Kind::Float, tch::Device::Cpu));
229        let diff = (&qqt - &eye).abs().max().double_value(&[]);
230        // Polar Express coefficients are optimized for bfloat16; in float32
231        // convergence is slightly looser but still well-orthogonal
232        assert!(
233            diff < 0.2,
234            "Q@Q^T should be near identity, max diff = {diff}"
235        );
236    }
237
238    #[test]
239    fn test_newton_schulz_tall_matrix() {
240        let _guard = tch::no_grad_guard();
241        // Tall matrix [64, 8] — should transpose internally
242        let g = well_conditioned_matrix(64, 8);
243        let q = newton_schulz_orthogonalize(&g, 5);
244        assert_eq!(q.size(), &[64, 8]);
245        // Q^T @ Q ≈ I (orthonormal columns for tall)
246        let qtq = q.tr().matmul(&q);
247        let eye = Tensor::eye(8, (Kind::Float, tch::Device::Cpu));
248        let diff = (&qtq - &eye).abs().max().double_value(&[]);
249        assert!(
250            diff < 0.3,
251            "Q^T@Q should be near identity, max diff = {diff}"
252        );
253    }
254
255    #[test]
256    fn test_muon_step_updates_params() {
257        let p = Tensor::randn([8, 64], (Kind::Float, tch::Device::Cpu)).set_requires_grad(true);
258        let p_orig = p.data().copy();
259
260        // Generate gradient via backward
261        let loss = p.sum(Kind::Float);
262        loss.backward();
263
264        let mut state = MuonState::new();
265        let config = MuonConfig::default();
266        muon_step(&p, &mut state, &config);
267
268        let diff = (&p.data() - &p_orig)
269            .abs()
270            .sum(Kind::Double)
271            .double_value(&[]);
272        assert!(diff > 0.0, "Parameter should have been updated");
273    }
274
275    #[test]
276    fn test_muon_momentum_accumulates() {
277        let p = Tensor::randn([8, 64], (Kind::Float, tch::Device::Cpu)).set_requires_grad(true);
278        let config = MuonConfig::default();
279        let mut state = MuonState::new();
280
281        // Step 1
282        let loss1 = p.sum(Kind::Float);
283        loss1.backward();
284        muon_step(&p, &mut state, &config);
285        assert!(state.momentum_buffer.is_some());
286
287        // Step 2 — use different gradient
288        let _ = p.grad().zero_();
289        let loss2 = (&p * 2.0).sum(Kind::Float);
290        loss2.backward();
291        let buf_before = state.momentum_buffer.as_ref().unwrap().copy();
292        muon_step(&p, &mut state, &config);
293        let buf_after = state.momentum_buffer.as_ref().unwrap();
294        let diff = (&buf_before - buf_after)
295            .abs()
296            .sum(Kind::Double)
297            .double_value(&[]);
298        assert!(diff > 0.0, "Momentum buffer should change across steps");
299    }
300
301    #[test]
302    fn test_muon_config_defaults() {
303        let config = MuonConfig::default();
304        assert!((config.lr - 0.02).abs() < 1e-9);
305        assert!((config.momentum - 0.95).abs() < 1e-9);
306        assert_eq!(config.ns_steps, 5);
307    }
308
309    #[test]
310    fn test_muon_weight_decay() {
311        let p = Tensor::ones([4, 8], (Kind::Float, tch::Device::Cpu)).set_requires_grad(true);
312
313        // Create gradient, then zero it — only weight decay should take effect
314        let loss = p.sum(Kind::Float);
315        loss.backward();
316        let _ = p.grad().zero_();
317
318        let config = MuonConfig {
319            weight_decay: 0.1,
320            ..Default::default()
321        };
322        let mut state = MuonState::new();
323        muon_step(&p, &mut state, &config);
324
325        // With zero grad and weight decay, parameter should shrink
326        let max_val = p.data().max().double_value(&[]);
327        assert!(max_val < 1.0, "Weight decay should shrink parameters");
328    }
329}