Dyck-Polytope Sparse Routing

1. Integrate the constraint into a sparse MoE feed-forward block or sparse attention layer. Let each candidate interaction be indexed by a coordinate \(e\): for MoE, \(e=(token,expert)\); for attention, \(e=(head,key-group)\). Construct a fixed directed root-style interaction graph with coordinates \(s_e\), and enumerate a small set of paths \(\mathcal P\) representing hierarchical routes, such as token-to-layer-to-expert paths or coarse-to-fine attention groups. Split coordinates into continuous coordinates and bounded cross-group coordinates. 2. Pseudocode: compute logits \(z_e\); set \(q_e=\operatorname{softplus}(z_e)\); for each path \(p\), compute \(c_p=\sum_{e\in p}q_e\); enforce budgets with \(L_{path}=\sum_{p\in\mathcal P}\operatorname{ReLU}(c_p-b_p)^2\), where \(b_p\) is \(\lambda_i-\lambda_j\) or \(\lambda_r\); for bounded coordinates use \(q_e=\operatorname{sigmoid}(z_e)\) and add \(L_{bin}=\sum_e q_e(1-q_e)\). Normalize feasible scores by \(g_e=q_e/\max(1,\max_{p\ni e}c_p/b_p)\), select the largest \(k\) feasible gates, and execute only selected experts or keys. 3. The paper supplies the path-sum structure and binary bounds; estimate budgets \(b_p\) from the desired per-layer capacity, and estimate path violations empirically. A stronger variant uses one or two projected-gradient steps on \(\min_{s\ge0}\|s-q\|_2^2\) subject to all path inequalities before top-k selection. 4. First experiment: train a 6-layer, 8-expert-per-layer Transformer on WikiText-103 or a synthetic hierarchical routing task, comparing ordinary top-2 routing, random fixed sparsity, and Dyck-polytope routing at identical active expert FLOPs. Measure validation perplexity, maximum path-capacity violation, expert-load coefficient of variation, peak activation memory, and loss variance. Success is lower perplexity or fewer routing collapses at equal FLOPs, with at least 10% lower peak memory or a visibly more balanced expert-load distribution.