PSD-Safe Learnable Similarity Kernel

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.