Submodular Budget Router

Integrate this at the MoE router immediately after the router network produces token-expert logits W in R^{B x E}, where B is the token count and E is the number of experts. For an MVP, use a monotone submodular function z(S)=c(|S|), with c(0)=0 and c(r)=C(1-exp(-r/tau)); tau controls diminishing returns and C sets total routing mass. For a richer version, use z(S)=sum_h a_h min(r_h, |S intersect G_h|), where a_h>=0, r_h>=0, and G_h are expert groups. For each token, sort logits w_e in descending order, compute delta_j=z(S_j)-z(S_{j-1}), set x[i_j]=relu(delta_j), retain the first k positive assignments, and normalize x to sum to one. Dispatch token features using x. To enforce hardware capacity, rank candidate assignments by w_be*x_be, retain the highest-priority assignments for each expert up to capacity, then renormalize surviving weights; optionally add an auxiliary loss on expert loads. Pseudocode: logits=W[b]; order=argsort_desc(logits); S=empty; for e in order: delta=z(S union {e})-z(S); x[e]=relu(delta); S.add(e); x=normalize(top_k(x,k)); dispatch(x). The mathematical quantities are the submodular increments and greedy vertex; learnable quantities are logits, tau, group weights, and optionally z. Begin with an 8-expert Switch-Transformer-style model on Wikitext-103 or CIFAR-100, comparing against top-1 and top-2 routing at equal expert FLOPs and capacity factor. Measure validation loss or accuracy, dropped-token rate, expert-load coefficient of variation, routing entropy, and throughput. Success means fewer dropped tokens and better load balance at equal compute, or faster loss descent and lower perplexity than top-k routing.