Matching-safe sparse layers

Integrate this at the mask-construction stage of a sparse MLP, grouped linear layer, or MoE expert/router, before forward training begins. Partition the input and output channels into groups; create a bipartite graph whose left vertices are input groups and whose right vertices are output groups, with an edge whenever the proposed layer mask contains at least one connection between the groups. Compute a maximum-cardinality matching using Hopcroft–Karp. Mark all matched groups as safe. For each unmatched output group, add one edge to an unmatched or highest-degree input group, choosing the candidate that maximizes the resulting minimum degree; alternatively add a dense residual projection from the nearest matched input group. Pseudocode: inputs are mask M, group maps g_in and g_out, and repair mode; form S[a,b]=1 if any M[u,v]=1 for groups a,b; run matching M*; while an output group is unmatched, select a candidate input b minimizing added FLOPs subject to increasing matching size, set S[a,b]=1 and materialize one learned connection; instantiate weights with fan-in scaling after repair. Recompute the graph every router update if experts are dynamically pruned. The matching number and Hall violations come from exact graph computation; the link between them and optimization stability must be tested empirically. First experiment: compare a 50%-sparse two-layer MLP and a top-2 MoE on CIFAR-10 or WikiText-2 against the same unmodified random mask at equal parameter count and FLOPs. Sweep hidden width through the interpolation region and measure training-loss spikes, gradient norm, validation loss, dead-output groups, and Jacobian condition estimates. Success is fewer or smaller descent peaks, lower gradient variance, and improved validation accuracy at equal sparsity; also report the extra repair edges and FLOP overhead.