Unverified 2026

Entropy-Certified Interaction Supports

Implementation & benchmark of arXiv:2607.29490 — Slice and Partition Rank Criteria for Polynomial Zero-Avoidance

Usefulness5/10

Difficulty5/10

Novelty7/10

Architecture Memory Speedup Generalization Mlp Transformer Pruning Information theory Linear algebra Combinatorics Tensor decomposition

Source paper: Slice and Partition Rank Criteria for Polynomial Zero-Avoidance arXiv:2607.29490 ⓘ · analyzed Aug 31, 2026

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

Idea description

Replace a dense third-order channel-interaction tensor by a fixed sparse support selected through the paper's uniform-marginal infeasibility certificate. Supports with a large dual margin have an effective entropy base below the channel alphabet size, suggesting fewer independent interaction slices and cheaper contractions. Use the certificate either during architecture search or as a pruning score for an already-trained tensorized layer.

Formulas

$$e_2(x,y,z)=xy+yz+zx$$

$$p_s\ge 0,\qquad \sum_{s\in S}p_s=1,\qquad \sum_{s\in S:s_i=a}p_s=\frac1q\quad(i=1,\ldots,d,\ a\in[q])$$

$$\sum_{i=1}^{d}u_{i,s_i}\ge 1\quad\forall s\in S,\qquad \frac1q\sum_{i=1}^{d}\sum_{a=1}^{q}u_{i,a}=1-\gamma<1$$

$$H(p)=-\sum_{s\in S}p_s\log p_s\ \le\ d\log q-\Delta(\gamma),\qquad \Delta(\gamma)>0$$

Mathematical statement

The paper studies a coefficient support S contained in [q]^d and asks whether there exists a probability distribution p=(p_s)_{s\in S} with uniform one-coordinate marginals: p_s\ge 0, \sum_{s\in S}p_s=1, and \sum_{s\in S:s_i=a}p_s=1/q for every coordinate i\in\{1,\ldots,d\} and symbol a\in[q]. If this finite linear feasibility problem has no solution, a separating-hyperplane/Farkas certificate consists of numbers u_{i,a} such that \sum_{i=1}^{d}u_{i,s_i}\ge 1 for every s\in S, while the uniform average satisfies q^{-1}\sum_{i=1}^{d}\sum_{a=1}^{q}u_{i,a}<1. The positive margin is \gamma=1-q^{-1}\sum_{i,a}u_{i,a}. The associated support-entropy quantity is H(p)=-\sum_{s\in S}p_s\log p_s; the uniform-marginal obstruction implies an upper bound H(p)\le d\log q-\Delta(\gamma), with an explicit positive entropy gap \Delta determined by the certificate and the information-theoretic inequality used in the paper. For a neural tensor layer, q is the number of channel groups, d is interaction order, and S is the retained index support. The paper's concrete motivating polynomial is e_2(x,y,z)=xy+yz+zx over characteristic-three fields, showing that algebraically structured supports can have analytically certifiable gaps rather than requiring a new LP for every field size.

Implementation notes

Integrate this at the interaction tensor of a tensorized MLP or a lightweight transformer feed-forward block, not at the dense linear projections. Partition the input and output channels into q groups and define a d-way support S over group indices; for d=3, an interaction is y_c += T_{a,b,c} x^{(1)}_a x^{(2)}_b x^{(3)}_c only when (a,b,c)\in S. First generate candidate supports by structured pruning, random sparsification, or a family such as the nonzero-support pattern of e_2. For each candidate S, solve the finite feasibility LP for p: enforce nonnegativity, total mass one, and uniform marginals 1/q. If infeasible, solve the dual LP maximizing gamma subject to sum_i u[i,s_i] >= 1 for all support tuples and q^{-1} sum_{i,a}u[i,a] = 1-gamma. Rank supports by gamma divided by |S| or by the estimated contraction FLOPs. Pseudocode is: for S in candidates: solve primal; if infeasible: solve dual u; gamma=1-mean(u); score=gamma/(cost(S)+eps); choose top S. During training, store only T entries indexed by S and contract by gathering the corresponding channel groups; optionally allow a small dense residual branch. The LP-derived quantities are S, u, gamma, and the support cost; Delta(gamma) need not be computed exactly for the MVP, although it can be estimated by maximizing entropy under the marginal constraints and comparing it with d log q. The first experiment should use q=8 or 16, d=3, a CIFAR-10 MLP or a small language-model FFN, comparing dense tensor, random equal-size support, magnitude pruning, and certificate-selected support at equal parameter count. Measure validation accuracy, training loss at equal FLOPs, peak activation memory, and contraction throughput. Success would be lower memory and faster loss descent than random or magnitude supports at the same sparsity, with no more than a small accuracy loss; a useful secondary signal is that larger certified gamma predicts better accuracy/FLOP tradeoffs.

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.