# PSD-Safe Learnable Similarity Kernel

- ID: 2377
- Canonical URL: https://synthcore.org/idea/2377/psd-safe-learnable-similarity-kernel
- API JSON: https://synthcore.org/api/idea/2377.json
- API Markdown: https://synthcore.org/api/idea/2377.md
- Verification status: unverified
- Source: [arXiv:2608.15904](https://arxiv.org/abs/2608.15904)
- Category: architecture
- Solves: accuracy, stability, generalization
- ML areas: attention, transformer, graph-nn
- Math tags: linear-algebra, convex-analysis, functional-analysis
- Ratings: usefulness 5/10; difficulty 6/10; novelty 6/10

## Idea description

Use the finite-order characterization to learn a nonlinear similarity function for token, patch, or graph-node Gram matrices while preserving PSD by construction or by a differentiable certificate loss. This creates a kernelized attention or graph-readout mechanism in which nonlinear affinity transformations cannot introduce indefinite similarity geometry.

## Mathematical statement

Given a positive similarity matrix A\in\mathbb{P}_n(I), the paper characterizes scalar functions f for which f[A] remains PSD. The required conditions are f^{(k)}(x)\geq0 for 0\leq k\leq n-1 and positive semidefiniteness of \mathcal{H}_n(f;x), whose (i,j) entry is \mathcal{E}^{i+j}f(x), with \mathcal{E}=x\frac{d}{dx}. The proposed attention kernel starts with positive feature vectors or a shifted Gram matrix, G=\phi(Q)\phi(K)^T+\delta\mathbf{1}\mathbf{1}^T, and transforms G entrywise by f_    heta. The theorem applies directly to symmetric self-attention where Q=K; for cross-attention, use the resulting matrix as a positive affinity but do not claim that it is a symmetric PSD matrix unless the query and key sets coincide.

## Key formulas

- $$\mathcal{H}_{n}(f;x)=\bigl[\mathcal{E}^{i+j}f(x)\bigr]_{i,j=0}^{n-1},\qquad \mathcal{E}=x\frac{d}{dx},$$
- $$f^{(k)}(x)\geq0\quad(0\leq k\leq n-1),\qquad \mathcal{H}_{n}(f;x)\succeq0,$$
- $$G=\phi(Q)\phi(Q)^{\mathsf T}+\delta\mathbf{1}\mathbf{1}^{\mathsf T},\qquad S_{ij}=f_\theta(G_{ij}),$$
- $$\operatorname{Attn}(V)=D^{-1}SV,\qquad D_{ii}=\sum_j S_{ij}+\eta$$

## Implementation notes

1. Integration point: modify the score path for a local self-attention block or graph transformer. Replace unconstrained logits QK^T/\sqrt d followed by softmax with a positive feature map \phi(Q)=\operatorname{softplus}(WQ+b), form G=\phi(Q)\phi(Q)^T+\delta\mathbf{1}\mathbf{1}^T, and apply the learned scalar function S_{ij}=f_    heta(G_{ij}) entrywise. Use row normalization D^{-1}S for value aggregation, with D_{ii}=\sum_jS_{ij}+\eta, and retain residual and output projection layers.

2. Parameterize f_    heta on a bounded score interval with a low-degree polynomial or spline. During training, sample x_r from the current score distribution and include a fixed dense grid. Compute f^{(k)} and Euler derivatives E_q recursively, then add L_{cert}=\alpha\sum_{r,k}[\max(0,-f^{(k)}(x_r))]^2+\beta\sum_r[\max(0,    au-\lambda_{\min}(H_r))]^2, where H_r[i,j]=E_{i+j}(x_r). Update grid bounds from detached running quantiles of G, while evaluating constraints on a wider validation interval to detect extrapolation failures.

3. The paper's mathematics supplies the finite-order PSD certificate. The implementation estimates derivatives with autodiff, minimum eigenvalues with eigvalsh, and score-range bounds from batch statistics. For self-attention, explicitly verify eigvalsh(S) on held-out batches. Compare against softmax attention and an unconstrained positive-kernel baseline; do not interpret row-normalization as preserving symmetry or PSD after normalization.

4. First cheap experiment: train a one- or two-layer ViT-Tiny on CIFAR-10, replacing one local self-attention block while keeping hidden size, sequence length, and FLOPs fixed. Compare softmax, cosine attention, unconstrained positive-kernel attention, and Euler-Hankel-constrained attention. Success is equal or improved validation accuracy, no negative eigenvalues in S beyond numerical tolerance, and reduced loss variance or fewer optimization instabilities at the same learning rate.

## Disclaimer

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