# Regular Hypergraph Masks for Balanced Sparse Attention

- ID: 1328
- Canonical URL: https://synthcore.org/idea/1328/regular-hypergraph-masks-for-balanced-sparse-attention
- API JSON: https://synthcore.org/api/idea/1328.json
- API Markdown: https://synthcore.org/api/idea/1328.md
- Verification status: unverified
- Source: [arXiv:2607.23641](https://arxiv.org/abs/2607.23641)
- Category: architecture
- Solves: scalability, memory, stability
- ML areas: attention, transformer, memory, inference-speedup
- Math tags: combinatorics, graph-theory, linear-algebra
- Ratings: usefulness 6/10; difficulty 6/10; novelty 6/10

## Idea description

Construct sparse attention masks as regular or almost-regular hypergraphs: every query selects exactly w keys, while every key receives nearly equal incidence within each score or locality class. This preserves a fixed sparsity budget while removing systematic positional and head-level load imbalance that can cause hot keys, uneven memory traffic, and unstable gradients.

## Mathematical statement

The paper represents fixed-weight configurations as edges of a complete w-uniform multihypergraph L K_M^(w), containing L copies of every w-element subset of M positions. Color k is assigned to an edge copy, with prescribed color-class sizes c_{w,k} satisfying sum_{k=0}^N c_{w,k}=L binom(M,w) (Eq. 109). A color class is regular when every vertex has equal degree and almost regular when any two vertex degrees differ by at most one. For attention, vertices are keys or heads, a hyperedge is the set of w keys selected by one query, and colors are score, distance, or confidence bins. The construction gives a static combinatorial target for equal incidence while retaining exactly w nonzeros per query. The shell-balance condition sum_{x:x_alpha=1} n_{x,k}=sum_{x:x_gamma=1} n_{x,k} can additionally enforce equal key marginals inside every class.

## Key formulas

- $$\sum_{k=0}^{N}c_{w,k}=L\binom{M}{w}$$
- $$\deg_k(v)=\#\{e\text{ in color class }k:v\in e\},\qquad |\deg_k(u)-\deg_k(v)|\leq 1\ \text{(almost regular)}$$
- $$\sum_{x:\,x_\alpha=1}n_{x,k}=\sum_{x:\,x_\gamma=1}n_{x,k}\qquad\text{for all positions }\alpha,\gamma\text{ and class }k$$
- $$\sum_{j=1}^{S}A_{ij}=w,\qquad \sum_{i=1}^{Q}A_{ij}\in\left\{\left\lfloor\frac{Qw}{S}\right\rfloor,\left\lceil\frac{Qw}{S}\right\rceil\right\}$$

## Implementation notes

Integrate this at the sparse-attention mask generator, either during training for block-sparse attention or at inference for a fixed routing pattern. Let Q queries select w of S keys each, represented by a binary matrix A in {0,1}^{Q times S}. Partition queries into K score or locality classes using their current top-w attention scores. Repair each class so key incidences are regular or almost regular. The simplest method sorts queries by preferred key lists, maintains key deficits d_j, and replaces the least costly selected key whenever a key exceeds its target incidence. A stronger method solves a min-cost bipartite b-matching: each query has degree w, each key has degree floor(Q_k w/S) or ceil(Q_k w/S), and edge cost is -q_i^T k_j/sqrt(d) plus a locality penalty. Keep the repaired binary mask for the forward pass; use original attention scores only to calculate reassignment costs, and update masks every few steps. The hypergraph equation determines total incidences and the almost-regular degree targets. Begin with Longformer-style local-plus-global attention on a small Transformer using S=1024, w=64, and 8 heads. Compare learned top-w, random, and balanced masks at equal nonzeros. Measure maximum key fan-in, activation-memory peaks, kernel occupancy, throughput, and validation perplexity. Success is lower fan-in variance and memory spikes with equal or better perplexity at identical attention FLOPs.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.