# Locally-PSD Similarity Bias

- ID: 2350
- Canonical URL: https://synthcore.org/idea/2350/locally-psd-similarity-bias
- API JSON: https://synthcore.org/api/idea/2350.json
- API Markdown: https://synthcore.org/api/idea/2350.md
- Verification status: unverified
- Source: [arXiv:2608.15444](https://arxiv.org/abs/2608.15444)
- Category: regularization
- Solves: stability, memory, speedup
- ML areas: attention, regularization, graph-nn
- Math tags: convex-analysis, linear-algebra, spectral-theory
- Ratings: usefulness 5/10; difficulty 4/10; novelty 7/10

## 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.

## 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.

## Key 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}.$$

## 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.

## Disclaimer

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