alf-load-balancing-theory

name	alf-load-balancing-theory
title	Auxiliary-Loss-Free Load Balancing: Theoretical Framework and Primal-Dual Analysis
version	0.0.2
engine	skillxiv-v0.0.2-claude-opus-4.6
license	MIT
url	https://arxiv.org/abs/2512.03915
keywords	["moe-training","load-balancing","optimization-theory","primal-dual-methods","stochastic-analysis"]
description	Rigorous theoretical framework reformulating DeepSeek's ALF-LB as single-step primal-dual method for assignment problem, proving monotonic Lagrangian improvement, approximate balancing guarantees, and logarithmic expected regret in stochastic settings.

Summary

Theoretical Framework for Auxiliary-Loss-Free Load Balancing establishes a rigorous mathematical foundation for DeepSeek's ALF-LB algorithm. The analysis reformulates the algorithm as a single-step primal-dual method for an assignment problem, proves monotonic Lagrangian improvement in deterministic case, extends to stochastic training with logarithmic regret bounds, and provides theoretical justification for practical effectiveness.

Core Technique

Primal-Dual Formulation: Reformulate expert load balancing as a constrained optimization problem:

Minimize: loss(weights)
Subject to: all experts equally loaded

Single-Step Update: ALF-LB performs one update step of the primal-dual method:

w_t+1 = w_t - α ∇_w loss(w_t) - β ∇_dual (loading_constraint)

Where the dual term encourages load balance.

Monotonic Improvement: Prove that each step monotonically improves the Lagrangian:

L(w_t+1, λ_t) <= L(w_t, λ_t)

This guarantees convergence toward balanced loading.

Implementation

Assignment problem formulation:

# Expert assignment can be viewed as solving:
# min ||routing_scores - average_score||²
# subject to: each token assigned to exactly one expert

def compute_optimal_assignment(routing_scores):
    """
    Optimal assignment minimizes deviation from average routing.
    ALF-LB approximately solves this via gradient descent on load variance.
    """
    avg_score = routing_scores.mean()
    load_variance = ((routing_scores - avg_score) ** 2).sum()
    return load_variance

Primal-dual update rule:

def alf_lb_update(routing_logits, expert_capacity, lambda_dual, learning_rate):
    # Primal: gradient on loss (LLM token prediction)
    loss = cross_entropy(routing_logits, target_tokens)
    grad_primal = torch.autograd.grad(loss, routing_logits)[0]

    # Dual: gradient on load balance constraint
    routing = softmax(routing_logits)
    loads = routing.(dim=)  
    load_imbalance = ((loads - expert_capacity) ** ).()
    grad_dual = torch.autograd.grad(load_imbalance, routing_logits)[]

    
    update = grad_primal + lambda_dual * grad_dual
    routing_logits = routing_logits - learning_rate * update

     routing_logits