Hall-Certified Sparse Attention Masks

Integrate this at the sparse-attention mask construction stage, before attention logits are normalized. Let M in {0,1}^{n x m} be the proposed query-key mask, L the corresponding attention logits, and mu, nu the desired row and column masses; for ordinary attention use uniform masses mu_i=1/n and nu_j=1/m when n=m. First run a maximum-flow feasibility check on the bipartite graph: create source-to-query capacity mu_i, query-to-key edges with capacity INF when M_ij=1, and key-to-sink capacity nu_j. If max-flow is below 1, extract the minimum cut and its query-side set U; this provides a concrete Hall witness with deficit delta=mu(U)-nu(N(U)). Repair only the witness by adding the cheapest absent edges according to logits L_ij, or fall back to a dense connection for one node in U, and repeat until flow equals 1. Then compute attention using masked Sinkhorn iterations: initialize K=exp(L)*M, alternate u=mu/(K v) and v=nu/(K^T u), and return A=diag(u)Kdiag(v), with epsilon added to denominators. The paper supplies the exact combinatorial feasibility condition; max-flow and Sinkhorn are engineering implementations, while the edge-addition cost and number of repairs are empirical choices. The first experiment should use a small transformer on CIFAR-10 or a language-model copy task with local-plus-random sparse masks, comparing unvalidated masks against Hall-certified masks at equal sparsity. Measure NaNs, fraction of zero-output queries or keys, Sinkhorn iterations, training loss, and validation accuracy. Success is zero infeasible batches and no dead rows or columns, with equal or better accuracy at two to four times fewer attention edges.