Cycle-certified nonnegative rank-one attention
Implementation & benchmark of arXiv:2607.16796 — Tight Conic Relaxations for Rank-one Doubly Nonnegative Matrix Completion
Source paper: Tight Conic Relaxations for Rank-one Doubly Nonnegative Matrix Completion arXiv:2607.16796 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Represent a nonnegative attention or routing score matrix by two nonnegative vectors, X = uv^T, and learn only entries on a sparse bipartite graph of important query-key or token-expert interactions. Complete the remaining entries multiplicatively and monitor cycle residuals as a certificate of whether the sparse representation is compatible with rank one. Use local ratio violations to trigger additional edges or relax the rank-one approximation only where needed.
Formulas
Mathematical statement
The paper formulates rank-one nonnegative completion as finding X in R^{m x n} such that X_{ij}=A_{ij} for (i,j) in Omega and rank(X) <= 1, with Omega represented by a bipartite graph whose edges are specified entries. A rank-one nonnegative completion has X_{ij}=u_i v_j with u_i,v_j >= 0. Thus every bipartite cycle obeys multiplicative consistency; for a four-cycle (i_1,j_1,i_2,j_2), X_{i_1j_1}X_{i_2j_2}=X_{i_1j_2}X_{i_2j_1}. The extracted paper explicitly assumes local ratio bounds z^*_{n+j}/z^*_i in [1,1+delta] for every specified edge (i,j), where z^* is the nonnegative rank-one QCQP solution, delta > 0 is a tolerance, and n is the number of columns. Its Lemma 4.7 gives -1 + sum_{i=1}^n (z_i^*)^2 - sum_{i=1}^n (z_{n+i}^*)^2 = sum_{j=1}^n alpha_{1,j} z_{n+j}^*, where alpha_{1,j} are dual variables associated with cycle constraints. We use the cycle identity as the implementation constraint and the local ratio spread as a conditioning signal: large spread predicts fragile completion, while adding an edge that closes a violated cycle supplies a targeted correction.
Implementation notes
Integrate this into a low-rank attention or MoE-router score matrix. For a batch, let Q be the query or token index set of size m and K be the key or expert index set of size n. Maintain nonnegative factors u in R_+^m and v in R_+^n, generated by softplus projections from the corresponding hidden states, and define the score X_ij = u_i v_j. At training time choose a sparse edge set Omega containing top-k query-key or query-expert interactions from a frozen dense baseline, plus enough edges to close short four-cycles. Use this pseudocode: u=softplus(U(h_q))+eps; v=softplus(V(h_k))+eps; X=u[:,None]*v[None,:]; observe=A[Omega]; loss_fit=mean((X[Omega]-A[Omega])**2); for (i1,j1,i2,j2) in cycles: r=X[i1,j1]*X[i2,j2]-X[i1,j2]*X[i2,j1]; loss_cycle += r*r/(X[i1,j1]*X[i2,j2]+eps); ratio=(v[j]+eps)/(u[i]+eps); loss_ratio=relu(ratio-(1+delta))^2+relu(1-ratio)^2; loss=task_loss+lambda_fit*loss_fit+lambda_cycle*loss_cycle+lambda_ratio*loss_ratio; backprop(loss). The paper's rank-one completion equation supplies the factorized parameterization, while the four-cycle equation is the directly evaluated certificate. Estimate the local ratio distribution empirically over Omega and set delta to its 95th percentile or a fixed target such as 0.1. Every few hundred steps, identify the largest cycle residuals and add one missing edge from each offending cycle to Omega, or split the matrix into two rank-one components if residuals remain high. First test on CIFAR-100 or WikiText-2 with a small Transformer, comparing dense scores, standard top-k sparsity, and this factorized sparse version at equal validation accuracy. Measure parameter count, activation memory, score-matrix FLOPs, cycle residual, and perplexity or accuracy. Success means at least 2x lower score-matrix memory or FLOPs with less than 0.5 percentage-point accuracy loss and more stable training than an unconstrained rank-one factorization.
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.