aiqbench analysis
The paper gives formal bounds on how much a transformer attention head's output can shift under input perturbations, and shows that the hard part is the bilinear interaction between a varying query and the keys, not the softmax. Exact worst-case certification is NP-hard in general, so the proposed conic relaxation trades looseness for tractability. For readers, the practical takeaway is that tighter, provably scaled certificates on GPT-2 suggest linear bound propagation can understate how loose its bounds are, though results on one model don't establish broader robustness.
Conic Certification of Transformer Attention
arXiv:2611.00585v1 Announce Type: cross Abstract: 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.
Abstract: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.
56 pages, 5 figures, 6 tables. Code and data: this https URL
Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computation and Language (cs.CL); Optimization and Control (math.OC)
arXiv:2611.00585 [cs.LG]
(or arXiv:2611.00585v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2611.00585 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 343 words
Related coverage
No Judgment Without a Reason: Counterfactual Receipts for Versioned AI Evaluators
arXiv · Aug 24, 2026
Certified Mechanistic Interpretability: Lifting Single-Input Findings to Bounded Neighbourhoods
arXiv · Sep 24, 2026
On the disintegration of the stochastic majority vote: From PAC-Bayesian bounds to a self-bounding algorithm
arXiv · Sep 16, 2026
Sharp Bounds on Ground State Energy of the SYK Model
arXiv · Jul 30, 2026