# q-Ary Influence Overlap Regularizer

- ID: 193
- Canonical URL: https://synthcore.org/idea/193/q-ary-influence-overlap-regularizer
- API JSON: https://synthcore.org/api/idea/193.json
- API Markdown: https://synthcore.org/api/idea/193.md
- Verification status: mechanism_failed
- Source: [arXiv:2608.26259](https://arxiv.org/abs/2608.26259)
- Category: regularization
- Solves: stability, generalization, accuracy
- ML areas: attention, moe-routing, graph-nn, regularization
- Math tags: probability, information-theory, combinatorics, functional-analysis
- Ratings: usefulness 6/10; difficulty 3/10; novelty 6/10

## Idea description

Use the paper's q-ary overlap inequality as a regularizer for categorical neural networks. Two independently sampled attention, routing, or message-passing supports should rarely overlap in many locations; penalizing the moment q^{|S\cap S'|} discourages redundant histories and correlated interference between heads or experts.

## Mathematical statement

Lemma 3.1 considers a finite set W and a random subset S\subseteq W. Conditional on S, variables on S may have any S-dependent law, while variables on W\setminus S are independent uniform samples from [q]. If 
u is the uniform product measure on [q]^W, \mu is the resulting distribution, and S' is an independent copy of S, then \|\mu-
u\|_{L^2(
u)}^2\leq\mathbb{E}[q^{|S\cap S'|}]-1. Here q is the number of categorical states, W is the token or feature index set, S and S' are independently sampled influence supports, and |S\cap S'| measures support collision. The moment q^{|S\cap S'|} grows exponentially with overlap, so it is more sensitive to severe collisions than a linear overlap penalty. We adapt it by defining S_h as the support selected by head or expert h and minimizing an empirical estimate of \mathbb{E}[q^{|S_h\cap S'_h|}]-1, together with a target support-size penalty.

## Key formulas

- $$\|\mu-\nu\|_{L^{2}(\nu)}^{2}\leq\mathbb{E}\left[q^{|S\cap S'|}\right]-1$$
- $$\mathcal{L}_{\mathrm{overlap}}=\frac{1}{H}\sum_{h=1}^{H}\left(\frac{1}{M}\sum_{m=1}^{M}q^{\left|S_{h}^{(m)}\cap \widetilde S_{h}^{(m)}\right|}-1\right)$$
- $$\mathcal{L}=\mathcal{L}_{\mathrm{task}}+\lambda\mathcal{L}_{\mathrm{overlap}}+\gamma\sum_{h=1}^{H}\left(\frac{|S_h|}{K}-1\right)^2$$

## Implementation notes

Apply the regularizer to sparse attention supports, MoE routing supports, or GNN neighborhoods. For each minibatch and head or expert h, obtain a support S_h from the actual routing probabilities. With Bernoulli or Gumbel-top-k sampling, draw a second independent support \widetilde S_h using fresh random noise. Compute overlap_count=(S_h and \widetilde S_h).sum(-1), then evaluate q^{overlap_count}=exp(log(q)*overlap_count) and average across tokens, heads, and M=2--8 resamples. Add this quantity minus one to the task loss, using a warm-up schedule for lambda. If numerical overflow occurs, clip overlap_count or calculate a log-moment. A straight-through estimator can be used for discrete top-k masks; the masks themselves remain the true masks used by the forward pass. The exact paper-derived statistic is the empirical estimator of E[q^{|S cap S'|}]-1. The uniform categorical reference distribution need not be sampled during training, although it can be used to evaluate calibration. First train a 12-layer, 8-head Transformer on WikiText-2 with top-8 sparse attention. Compare no regularizer, standard Jaccard diversity, and this q-ary moment for q in {2,4,8}. Measure validation perplexity, support-collision rate, gradient-noise scale, and performance after masking 10% of tokens. Success means lower severe-overlap frequency and gradient variance at equal sparsity, with unchanged or improved perplexity; an ablation should show that q-dependent weighting beats ordinary Jaccard for larger categorical dimensions.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built an exhaustive Lemma 3.1 verifier and a CUDA-capable toy sparse-routing experiment with straight-through Gumbel top-k supports. The inequality held for all tested q values, and q-ary regularization reduced severe overlap versus the linear control (q=2: 3.5% vs 5.1%; q=4: 2.75% vs 5.1%; q=8: 4.38% vs 5.1%), with the expected exponential sensitivity in the measured moment. It was not an overall win because the task objective degraded substantially relative to the unregularized baseline and no perplexity/generalization benefit was established.

### Mechanism check

- Verdict: Built an exhaustive Lemma 3.1 verifier and a CUDA-capable toy sparse-routing experiment with straight-through Gumbel top-k supports. The inequality held for all tested q values, and q-ary regularization reduced severe overlap versus the linear control (q=2: 3.5% vs 5.1%; q=4: 2.75% vs 5.1%; q=8: 4.38% vs 5.1%), with the expected exponential sensitivity in the measured moment. It was not an overall win because the task objective degraded substantially relative to the unregularized baseline and no perplexity/generalization benefit was established.
- Confidence: 8/10
- Limitations: This is a tiny synthetic routing optimization, not a Transformer, WikiText-2, MoE, or GNN benchmark. Only one fixed seed and one regularization weight were tested; perplexity, masking robustness, gradient-noise scale, FLOPs, and multi-seed statistical significance were not measured.

## Artifacts

- [qary_overlap_experiment.py](https://synthcore.org/code/1199/qary_overlap_experiment.py)
- [report.md](https://synthcore.org/code/1199/report.md)
- [results.json](https://synthcore.org/code/1199/results.json)
- [Download all files as ZIP](https://synthcore.org/download/1199)

## Disclaimer

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