Unverified 2026

Locally-PSD Similarity Bias

Implementation & benchmark of arXiv:2608.15444 — Eigenvalues of locally positive semidefinite matrices: Non-convexity and Geometry

Usefulness5/10

Difficulty4/10

Novelty7/10

Regularization Stability Memory Speedup Attention Regularization Graph nn Convex analysis Linear algebra Spectral theory

Source paper: Eigenvalues of locally positive semidefinite matrices: Non-convexity and Geometry arXiv:2608.15444 ⓘ · analyzed Sep 1, 2026

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

Idea description

Replace a costly global PSD constraint on a learned symmetric similarity or covariance matrix with the paper's 2-local PSD constraint. Every 2-by-2 principal submatrix is guaranteed valid, preventing excessively large pairwise correlations while avoiding eigendecomposition or Cholesky factorization of the full matrix.

Formulas

$$\mathcal{S}^{n,1}\supsetneq\mathcal{S}^{n,2}\supsetneq\cdots\supsetneq\mathcal{S}^{n,n},\qquad \mathcal{S}^{n,n}=\mathcal{S}^{n}_{+}.$$

$$\mathcal{S}^{n,d}=\left\{X\in\operatorname{Sym}_{n}:X[I,I]\succeq 0\ \text{for every }I\subseteq\{1,\ldots,n\},\ |I|=d\right\}.$$

$$\begin{pmatrix}S_{ii}&S_{ij}\\S_{ij}&S_{jj}\end{pmatrix}\succeq0\quad\Longleftrightarrow\quad S_{ii}\ge0,\ S_{jj}\ge0,\ S_{ii}S_{jj}-S_{ij}^{2}\ge0.$$

$$S_{ii}=\operatorname{softplus}(a_i)+\epsilon,\qquad S_{ij}=\tanh(u_{ij})\sqrt{S_{ii}S_{jj}}\quad(i<j),\qquad S_{ji}=S_{ij}.$$

Mathematical statement

The paper defines the cone of d-locally positive semidefinite matrices as $\mathcal{S}^{n,d}=\{X\in\operatorname{Sym}_n:X[I,I]\succeq0\text{ for every }I\subseteq\{1,\ldots,n\}, |I|=d\}$, with the nested hierarchy $\mathcal{S}^{n,1}\supsetneq\mathcal{S}^{n,2}\supsetneq\cdots\supsetneq\mathcal{S}^{n,n}=\mathcal{S}^n_+$. Here $\operatorname{Sym}_n$ is the set of real symmetric $n\times n$ matrices, $X[I,I]$ is the principal submatrix indexed by $I$, and $\mathcal{S}^n_+$ is the globally positive-semidefinite cone. For $d=2$, a symmetric matrix $S$ is locally PSD exactly when $S_{ii}\ge0$ and every pair satisfies $S_{ii}S_{jj}-S_{ij}^2\ge0$, equivalently $|S_{ij}|\le\sqrt{S_{ii}S_{jj}}$. The adapted neural parameterization uses $S_{ii}=\operatorname{softplus}(a_i)+\epsilon$ and $S_{ij}=\rho_{ij}\sqrt{S_{ii}S_{jj}}$, where $\rho_{ij}=\tanh(u_{ij})$, guaranteeing every 2-by-2 principal submatrix is PSD. This does not guarantee global PSD, which should be measured rather than assumed.

Implementation notes

(1) Integration point: add this construction to a module that produces a symmetric pairwise matrix, such as an attention-bias matrix, learned token-similarity matrix, graph-NN edge-affinity matrix, or block optimizer preconditioner. Start with a learned attention-bias matrix $S\in\mathbb{R}^{L\times L}$, rather than modifying raw nonsymmetric query-key logits. Store one unconstrained diagonal parameter $a_i$ and one unconstrained pair parameter $u_{ij}$ for every $i<j$.

(2) Pseudocode: inputs are $a$, $u$, numerical floor $\epsilon$, downstream logits $B$, and scale $\alpha$. Compute $d_i=\operatorname{softplus}(a_i)+\epsilon$. Set $S_{ii}=d_i$. For every $i<j$, compute $S_{ij}=S_{ji}=\tanh(u_{ij})\sqrt{d_i d_j}$. Form modified logits $L_{ij}=B_{ij}+\alpha S_{ij}$, then apply the usual row-wise softmax. As a second variant, produce a free symmetric $S$ and add $\lambda\sum_{i<j}[\max(0,S_{ij}^{2}-S_{ii}S_{jj})]^2+\lambda\sum_i[\max(0,-S_{ii})]^2$ to the training loss.

(3) Computed from the paper's mathematics: the determinant inequalities and exact local-PSD parameterization are guaranteed analytically. Estimated empirically: the smallest eigenvalue of the full $S$, attention entropy, gradient-norm spikes, optimization loss, and task accuracy. Compare the quadratic-time pairwise construction with projection onto the global PSD cone by eigendecomposition, which is cubic in $L$ and requires storing or manipulating a dense spectral decomposition.

(4) First cheap experiment: train a 4-layer, 8-head Transformer on a small language-model corpus with sequence lengths 128 and 512. Compare ordinary learned attention bias, globally PSD bias using eigendecomposition projection, and the 2-local PSD parameterization. Measure validation perplexity, training loss versus wall-clock time, peak memory, gradient-norm spikes, attention entropy, full-matrix minimum eigenvalue, and constraint-update time. A positive result is fewer instability spikes and equal-or-better perplexity than the unconstrained baseline, with at least 1.5x faster constraint updates and lower memory than global PSD projection. A negative result—especially degraded perplexity accompanied by highly negative full-matrix eigenvalues—would test whether pairwise validity is insufficient for this architecture.

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.