Unverified 2026

Higher-Order Coactivation Envelope

Implementation & benchmark of arXiv:2607.06545 — A Higher-Order Clique Density Theorem

Usefulness4/10
Difficulty5/10
Novelty7/10

Source paper: A Higher-Order Clique Density Theorem arXiv:2607.06545 ⓘ · analyzed Aug 30, 2026

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

Idea description

Convert an attention or MoE routing affinity matrix into a soft graph and constrain its K_r-density relative to its observed K_s-density. The regularizer penalizes pathological affinity patterns in which moderate s-way coactivation is accompanied by an implausibly low or unstable r-way coactivation.

Formulas

$$g_j(W)=\frac{1}{j!}\int_{\Omega^j}\prod_{1\le a<b\le j}W(x_a,x_b)\,d\mu(x_1)\cdots d\mu(x_j).$$
$$q_j^{(u)}(a)=\binom{u-1}{j}a^j+\binom{u-1}{j-1}a^{j-1}\bigl(1-(u-1)a\bigr),\qquad 0\le a\le \frac{1}{u-1}.$$
$$F_{s,r}\bigl(q_s^{(u)}(a)\bigr)=q_r^{(u)}(a),\qquad \mathcal{L}_{\mathrm{clique}}=\lambda\left[\max\left\{0,F_{s,r}(\hat g_s)-\hat g_r\right\}\right]^2.$$
$$\hat g_j=\frac{1}{j!M}\sum_{m=1}^{M}\prod_{1\le a<b\le j}W_{i_a^{(m)},i_b^{(m)}},\qquad i_1^{(m)},\ldots,i_j^{(m)}\text{ sampled without replacement}.$$

Mathematical statement

For a symmetric graphon W from the unit interval to [0,1], the paper defines the K_j-density as g_j(W) = 1/j! times the integral over j sampled vertices of the product of W over every unordered vertex pair. For a complete multipartite graphon with part masses p_1,...,p_u, this density is the elementary symmetric polynomial e_j(p) = sum over distinct indices i_1 < ... < i_j of p_{i_1}...p_{i_j}. On the extremal branch with u-1 equal parts of mass a and one residual part b = 1 - (u-1)a, the density is q_j^(u)(a) = binomial(u-1,j) a^j + binomial(u-1,j-1) a^(j-1)b, for 0 <= a <= 1/(u-1). For a prescribed s-clique density q, the theorem defines a lower envelope F_{s,r}(q) by selecting the relevant branch u, solving q_s^(u)(a) = q, and returning q_r^(u)(a). In a neural network, estimate g_s and g_r from sampled affinity subgraphs and penalize max(0, F_{s,r}(g_s) - g_r)^2. The theorem supplies the extremal envelope; finite-batch density estimates and interpolation of F are empirical approximations.

Implementation notes

Integrate the method at the attention-affinity or MoE-router level. For attention, compute A = sigmoid(QK^T divided by sqrt(d)) on selected sequence blocks, then symmetrize it as W = (A + A^T)/2. For MoE, define W_ij = sum_e p_ie p_je, where p_ie is token i's probability of selecting expert e. Start with s = 3 and r = 4. Before training, construct the envelope numerically: for every integer branch u from r through a chosen maximum U, evaluate q_s^(u)(a) and q_r^(u)(a) on a dense grid for a in [0, 1/(u-1)], retain the minimum valid q_r at each q_s, and store a monotone interpolant F. At each step, sample M tuples of distinct tokens, compute the Monte Carlo estimates of g_s and g_r using the displayed product formula, interpolate F(g_s), and add lambda times the squared hinge violation to the task loss. Warm lambda from zero, use independent samples for the two estimates or stop-gradient through F(g_s) to reduce noisy feedback, and average across heads or routing blocks. The first experiment should use a small six-layer transformer on WikiText-2, comparing the regularizer with ordinary attention at equal FLOPs and parameter count. Record validation perplexity, attention entropy, the envelope violation, and batch-to-batch variance of these statistics. For MoE, also measure expert-load variance. Success means lower variance or better perplexity at equal compute without attention collapse or increased routing imbalance.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.