Approximation-Aware Hard-Core Routing

Integrate this mechanism as a routing layer in a mixture-of-experts MLP or as a sparse message-passing layer in a graph neural network. Create n experts or token slots with a fixed interaction graph of matched degree and compute routing logits r_v from the hidden state h. Convert logits to soft gates z_v = sigmoid(r_v divided by temperature tau). During training use the total loss L_task plus lambda times the sum of z_u z_v over graph edges, plus beta times the total activation mass. For exact feasibility at inference, replace soft gates with a greedy maximal-independent-set projection: sort vertices by gate score, accept a vertex, and reject all of its neighbors. The paper supplies the local incompatibility rule and the contrast between graph families; estimate alpha(G)/n, active fraction, effective Jacobian rank, routing collisions, and task loss empirically. The first cheap experiment should use 1,024 experts, degree-four graphs, and a two-layer MoE on CIFAR-10 or synthetic token classification. Compare a connected bipartite graph with a random regular graph while matching degree, parameter count, and optimizer. The falsifiable prediction is that the bipartite graph permits effective active dimension near 0.50, whereas the random graph falls between 0.20 and 0.45. The measured activation fraction or Jacobian-rank density should differ by at least 0.05. Increasing lambda should drive both systems toward their graph-dependent capacity bounds, and excessive lambda should produce a measurable task-loss kink when the desired active fraction exceeds the independent-set density.