Conic Certification of Transformer Attention：注意力认证的锥规划理论
Conic Certification of Transformer Attention
理论向的硬核论文：讲清楚了为什么注意力认证这么难，还给出可计算的界，GPT-2 上验证有效。
一篇 arXiv 论文提出基于锥规划的 Transformer 注意力认证理论。作者证明认证难点不在 softmax，而在 query 与 keys 的双线性交互，这一交互使 box 约束下的认证成为 NP-hard 且不可近似。论文用指数锥 moment relaxation 给出误差按扰动半径二次增长的认证界，并证明该阶无法改进。在 GPT-2 上的实验显示，该认证达到预测的二阶精度，且在每个注意力头上都比线性 bound propagation 更紧。
Conic Certification of Transformer Attention
Attention is the computational core of large language models, yet the verifiers that bound how far an attention head's output can move under input perturbations give no guarantee on how loose their bounds are. A weak certificate therefore cannot be told apart from a fragile model. We develop a conic programming theory of attention certification that supplies this guarantee. We prove that the difficulty lies not in the softmax but in the bilinear interaction of a varying query with the keys. This interaction makes certification NP-hard over boxes and inapproximable once the attention logits can move by a constant amount. A fixed query or listed token substitutions, by contrast, make the exact worst case efficiently computable. An exponential cone moment relaxation then certifies a head with an error bounded quadratically in the perturbation radius by computable quantities, an order that cannot be improved. We also show that relaxations that treat a network one operation at a time, linear bound propagation among them, pay on second-order terms a sum of per-operation maxima instead of one coupled maximum. Computational results on GPT-2 indicate that the theory carries over to a trained model. Against exact worst cases with the query fixed, the certificate attains the predicted second-order accuracy. It is tighter than linear bound propagation on every head, and the looseness of bound propagation tracks the predicted per-operation excess.
