Home/Tools/AI Coding Bridge/Mixture of Experts (MoE) Top-K Gating & Token Dispatch
⟵Back to Dual-Track Interactive Graph
⚡ AI Coding Bridge · Algorithmic Foundation & LLM Systems3 Paired Kernels · 5 LeetCode Problems

Mixture of Experts (MoE) Top-K Gating & Token Dispatch ⟷ Sorting & Divide-and-Conquer (Partitioning)

💻 LLM Subsystem:Mixture of Experts (MoE) Top-K Gating & Token Dispatch
🌿 LeetCode Root:Sorting & Divide-and-Conquer (Partitioning)
📖

First-Principles Executive Synthesis

Direct algorithmic bridge linking algorithmic primitives to LLM system architectures.

Production Kernels & LeetCode Foundation Matrix

Left pane specifies the LLM kernel engineering contract; Right pane details the isomorphic LeetCode pattern; Full solution follows.
3 Kernels
💻 Industrial LLM Kernel #1Hard

MoE Top-K Gating Routing & Sparse Expert Dispatch

💻LLM Industrial Kernel Contract
Function Signature
def moe_topk_routing(hidden_states: torch.Tensor, gating_weights: torch.Tensor, top_k: int = 2) -> tuple[torch.Tensor, torch.Tensor]
In Mixture of Experts (MoE) architectures (such as Mixtral, DeepSeek-V3), each token is dispatched only to top-K expert networks. Implement the router forward pass: project token embeddings to expert logits, compute top-K indices, renormalize softmax routing probabilities across the selected experts, and return the dispatch weights.
🌿Mapped LeetCode Foundation
1 Problems
LC 75Sort Colors(Sorting & Divide-and-Conquer (Partitioning))
leetcode.com ↗
💡 Core Isomorphism: Dutch National Flag algorithm performs in-place three-way partitioning in a single pass.
🚀 Production Target: Dispatches tokens into expert memory buckets in-place for MoE layers without allocating auxiliary GPU tensor buffers.
Complete Python / PyTorch Reference Solution & Verification
import torch
import torch.nn.functional as F

def moe_topk_routing(
    hidden_states: torch.Tensor,
    router_weight: torch.Tensor,
    top_k: int = 2
) -> tuple[torch.Tensor, torch.Tensor]:
    """
    Computes top-k sparse gating weights and expert indices.
    
    Args:
      hidden_states: (B, S, D) or (TotalTokens, D)
      router_weight: (D, num_experts)
      top_k: number of experts to activate per token
    """
    orig_shape = hidden_states.shape
    D = orig_shape[-1]
    flat_states = hidden_states.reshape(-1, D) # (N, D)

    # 1. Compute router logits: (N, D) @ (D, E) -> (N, E)
    logits = torch.matmul(flat_states, router_weight)

    # 2. Select top-k experts per token
    topk_logits, topk_indices = torch.topk(logits, k=top_k, dim=-1) # (N, k)

    # 3. Softmax across top-k experts only (renormalization)
    topk_weights = F.softmax(topk_logits, dim=-1) # (N, k)

    return topk_indices, topk_weights

def moe_dispatch_and_combine(
    hidden_states: torch.Tensor,
    experts: list[torch.nn.Module],
    topk_indices: torch.Tensor,
    topk_weights: torch.Tensor
) -> torch.Tensor:
    """Executes dispatch to selected experts and aggregates weighted outputs."""
    N, D = hidden_states.reshape(-1, hidden_states.shape[-1]).shape
    flat_states = hidden_states.reshape(-1, D)
    final_output = torch.zeros_like(flat_states)
    top_k = topk_indices.shape[-1]

    # Aggregate contributions from top-k choices
    for k in range(top_k):
        expert_idx = topk_indices[:, k] # (N,)
        weight = topk_weights[:, k].unsqueeze(-1) # (N, 1)

        # For each expert, evaluate tokens assigned to it
        for e_id, expert in enumerate(experts):
            mask = (expert_idx == e_id)
            if mask.any():
                expert_out = expert(flat_states[mask])
                final_output[mask] += weight[mask] * expert_out

    return final_output.reshape(hidden_states.shape)

# --- Verification & Test Case ---
if __name__ == "__main__":
    B, S, D, E = 2, 4, 16, 8
    x = torch.randn(B, S, D)
    W_g = torch.randn(D, E)
    indices, weights = moe_topk_routing(x, W_g, top_k=2)

    assert indices.shape == (B * S, 2)
    assert weights.shape == (B * S, 2)
    assert torch.allclose(weights.sum(dim=-1), torch.ones(B * S), atol=1e-5)
    print("MoE top-k router verified successfully!")
💻 Industrial LLM Kernel #2Medium

MoE Load Balancing Auxiliary Loss

💻LLM Industrial Kernel Contract
Function Signature
def moe_auxiliary_loss(router_probs: torch.Tensor, expert_indices: torch.Tensor, num_experts: int) -> torch.Tensor
Without regularization, MoE models suffer from expert collapse where a handful of experts receive all tokens while the rest remain idle. Implement the Switch Transformer load-balancing auxiliary loss: L_aux = alpha * num_experts * sum_i(f_i * P_i), where f_i is the fraction of tokens dispatched to expert i, and P_i is the average routing probability assigned to expert i.
🌿Mapped LeetCode Foundation
1 Problems
LC 75Sort Colors(Sorting & Divide-and-Conquer (Partitioning))
leetcode.com ↗
💡 Core Isomorphism: Dutch National Flag algorithm performs in-place three-way partitioning in a single pass.
🚀 Production Target: Dispatches tokens into expert memory buckets in-place for MoE layers without allocating auxiliary GPU tensor buffers.
Complete Python / PyTorch Reference Solution & Verification
import torch

def moe_auxiliary_loss(
    router_probs: torch.Tensor,
    topk_indices: torch.Tensor,
    num_experts: int,
    alpha: float = 0.01
) -> torch.Tensor:
    """
    Computes Switch Transformer style auxiliary load balancing loss.
    L_aux = alpha * num_experts * sum(f_i * P_i)
    
    Args:
      router_probs: Full softmax probabilities across all experts (N, E)
      topk_indices: Indices of selected experts (N, top_k)
      num_experts: Total number of experts (E)
    """
    N = router_probs.shape[0]
    top_k = topk_indices.shape[1]

    # 1. Compute f_i: fraction of tokens routed to expert i
    # One-hot encode chosen indices: (N, top_k, E) -> sum over top_k -> (N, E)
    mask = torch.zeros(N, num_experts, device=router_probs.device)
    for k in range(top_k):
        mask.scatter_add_(1, topk_indices[:, k:k+1], torch.ones(N, 1, device=router_probs.device))
    
    # f_i is the fraction of total assignments to expert i
    f = mask.sum(dim=0) / (N * top_k) # (E,)

    # 2. Compute P_i: average routing probability for expert i
    P = router_probs.mean(dim=0) # (E,)

    # 3. Auxiliary loss encourages uniform distribution
    aux_loss = alpha * num_experts * torch.sum(f * P)
    return aux_loss

# --- Verification & Test Case ---
if __name__ == "__main__":
    N, E = 100, 8
    probs = torch.softmax(torch.randn(N, E), dim=-1)
    _, indices = torch.topk(probs, k=2, dim=-1)
    loss = moe_auxiliary_loss(probs, indices, E)
    assert loss.ndim == 0 and loss.item() > 0
    print("MoE load balancing auxiliary loss computed successfully:", loss.item())
💻 Industrial LLM Kernel #3Medium

Top-K and Top-P (Nucleus) Sampling

💻LLM Industrial Kernel Contract
Function Signature
def sample_top_k_top_p(logits: torch.Tensor, top_k: int = 0, top_p: float = 1.0, temperature: float = 1.0) -> int
Implement Top-K and Top-P (Nucleus) sampling for LLM text generation. The sampler scales logits by temperature, applies Top-K filtering to retain only the K largest values, applies Top-P filtering by accumulating probabilities and zeroing out values outside the top-P cumulative probability mass, and finally samples from the categorical distribution.
🌿Mapped LeetCode Foundation
1 Problems
LC 75Sort Colors(Sorting & Divide-and-Conquer (Partitioning))
leetcode.com ↗
💡 Core Isomorphism: Dutch National Flag algorithm performs in-place three-way partitioning in a single pass.
🚀 Production Target: Dispatches tokens into expert memory buckets in-place for MoE layers without allocating auxiliary GPU tensor buffers.
Complete Python / PyTorch Reference Solution & Verification
import torch

def sample_top_k_top_p(
    logits: torch.Tensor,
    top_k: int = 0,
    top_p: float = 1.0,
    temperature: float = 1.0
) -> int:
    """
    Filters logits using Top-K and Top-P (nucleus) thresholds, then samples a token.
    """
    # 1. Temperature scaling
    if temperature > 0:
        logits = logits / temperature
    else:
        return torch.argmax(logits).item()

    # 2. Top-K filtering
    if top_k > 0:
        k = min(top_k, logits.size(-1))
        k_values, _ = torch.topk(logits, k)
        min_k_val = k_values[-1]
        logits = torch.where(logits < min_k_val, torch.full_like(logits, -float('inf')), logits)

    # 3. Top-P (Nucleus) filtering
    if top_p < 1.0:
        sorted_logits, sorted_indices = torch.sort(logits, descending=True)
        sorted_probs = torch.softmax(sorted_logits, dim=-1)
        cumulative_probs = torch.cumsum(sorted_probs, dim=-1)

        # Remove tokens with cumulative probability above top_p (shift by 1 to keep first token above threshold)
        sorted_indices_to_remove = cumulative_probs > top_p
        sorted_indices_to_remove[..., 1:] = sorted_indices_to_remove[..., :-1].clone()
        sorted_indices_to_remove[..., 0] = False

        indices_to_remove = sorted_indices[sorted_indices_to_remove]
        logits[indices_to_remove] = -float('inf')

    # 4. Softmax and Categorical sampling
    probs = torch.softmax(logits, dim=-1)
    sampled_id = torch.multinomial(probs, num_samples=1).item()
    return sampled_id

# --- Verification & Test Case ---
if __name__ == "__main__":
    logits = torch.tensor([1.0, 5.0, 2.0, 0.5, 4.8])
    sample = sample_top_k_top_p(logits, top_k=2, top_p=0.9, temperature=0.7)
    assert sample in [1, 4]  # Top 2 indices
    print("Top-K and Top-P sampling completed successfully. Sampled ID:", sample)

🌿 All LeetCode Problems in Sorting & Divide-and-Conquer (Partitioning) (5 Problems)

Three-way quicksort partitioning and divide-and-conquer merges. Partitions sequences in-place around pivot values into three segments in O(N) linear time, underpinning high-throughput memory rearranging without extra allocations.
Full Bank Access
LC 75Sort Colors
↗
LC 148Sort List
↗
LC 315Count of Smaller Numbers After Self
↗
LC 493Reverse Pairs
↗
LC 912Sort an Array
↗

🔗 Related Algorithmic Bridges

🤖 Generative AI Systems FAQ & Engineering Principles

Q: Why do frontier AI labs test Sorting & Divide-and-Conquer (Partitioning) in LLM system engineering interviews?
Frontier LLM system engineering requires rigorous mastery over memory bandwidth and compute complexity. In Mixture of Experts (MoE) Top-K Gating & Token Dispatch, Direct algorithmic bridge linking algorithmic primitives to LLM system architectures. Understanding the foundational algorithmic roots is mandatory to reason about production engines like vLLM, FlashAttention, and SGLang.
Q: How does this algorithm transfer to real-world inference/training clusters?
Review the production PyTorch implementation provided above, focusing on batch dimension reductions, memory layout alignment, and edge assertions before porting to high-performance Triton or CUDA kernels.