Conic Programming Provides Rigorous Certification for Transformer Attention

The Blind Spot in Attention Verification: Weak Certificates and Fragile Models Are Indistinguishable

The core computational unit of large language models is the attention mechanism, but existing verifiers can only provide an upper bound on the change in attention head output under input perturbations, without guaranteeing how tight that bound is. As pointed out in the paper "Conic Certification of Transformer Attention," a loose certificate and a fragile model are observationally indistinguishable—when you see a verifier report a large upper bound, you cannot tell whether the model itself is unstable or the verification method is too coarse.

This blind spot directly affects the credibility of model robustness assessments. If the certificate itself lacks tightness guarantees, then any "model safety" conclusion based on it is built on sand. The goal of this research is precisely to establish a conic programming theory for attention certification, thereby providing provable guarantees for the tightness of the bounds.

The Root of Certification Difficulty: Bilinear Interactions, Not Softmax

The paper proves a key conclusion: the computational difficulty of attention certification does not come from the softmax normalization, but rather from the bilinear interaction between varying queries and keys. This interaction leads to two consequences: under box constraints, the certification problem is NP-hard; and once the attention logits can shift by a constant magnitude, the problem becomes inapproximable.

This finding corrects the previous intuition that might have attributed the difficulty to softmax. The research further points out that if the query is fixed, or if listed token substitutions are considered, the exact worst case can actually be computed efficiently. This contrast clearly delineates the difficulty boundary of the certification problem: the difficulty lies in the coupled variation of queries and keys, not in the nonlinear normalization itself.

NP-hardness and inapproximability are two levels in computational complexity theory that describe the inherent difficulty of a problem. NP-hardness means that no known polynomial-time exact algorithm exists (unless P=NP), while inapproximability is stronger: it shows that even if approximate solutions are allowed, the problem remains NP-hard as long as the approximation ratio reaches a certain constant. The paper points out that once the attention logits can shift by a constant magnitude, the problem becomes inapproximable, meaning that no polynomial-time constant-factor approximation algorithm exists—this gives a stricter limitation than mere NP-hardness. Understanding this helps grasp the essence of the certification difficulty: it is not only hard to solve exactly, but even a "good enough" approximate solution is hard to guarantee.

Box constraint refers to imposing per-dimension lower and upper bounds on input perturbations, i.e., each input feature is constrained within an interval. This is the most common perturbation model in adversarial robustness verification, corresponding to the perturbation ball under the L∞ norm. Under box constraints, each component of the query and key can vary independently, and this flexibility makes finding the worst case combinatorially explosive, leading to NP-hardness. If the query is fixed, then only the key varies, and the problem reduces to linear programming or convex optimization, which can be solved efficiently.

Exponential Cone Moment Relaxation: Second-Order Tightness Guarantee

To address the above difficulties, the authors propose the exponential cone moment relaxation method. This method can provide certification for a single attention head, with its error bounded by the square of the perturbation radius, and all quantities in the bound are computable. The paper emphasizes that this order cannot be improved—the second order is the optimal tightness order achievable by this method.

According to the paper, the significance of this result is that the looseness of the certificate now has a quantifiable theoretical prediction, rather than being an unknown quantity. For practitioners, this means it is possible to distinguish between "the model itself is robust" and "the verification method is too loose."

Moment relaxation is a convex relaxation technique whose core idea is to introduce auxiliary variables to represent the original nonlinear terms (such as quadratic terms) and impose constraints that these moment variables must satisfy (such as positive semidefiniteness), thereby relaxing the non-convex problem into a convex one. In attention certification, the bilinear interaction causes the objective function to contain product terms of queries and keys, making direct optimization difficult. Moment relaxation replaces the product terms with moment variables and uses exponential cone constraints to characterize the relationships among these moment variables, obtaining a computable convex upper bound.

Exponential cone is a special class of convex cones, defined as ({(x,y,z): y>0, y e^{x/y} \le z}), which can exactly represent nonlinear relationships such as exponential functions and relative entropy. In attention mechanisms, softmax involves exponential operations, and the bilinear interaction couples the exponential terms with the quadratic terms. The reason exponential cone moment relaxation can provide second-order tightness is that it can simultaneously capture the structure of the exponential nonlinearity and the bilinear interaction, whereas linear relaxation can only give linear bounds. Second-order tightness means that the certificate's error grows with the square of the perturbation radius, while the error of linear bound propagation grows linearly with the radius—when the perturbation is small, the quadratic error is much smaller than the linear error, thus providing a tighter certificate.

The Cost of Operation-by-Operation Relaxation: Summation over Second-Order Terms and Coupling

The paper also analyzes another common approach—operation-by-operation relaxation, including linear bound propagation. This type of method processes the network one operation at a time, and what it pays on second-order terms is the sum of the maxima of each operation, rather than a coupled maximum.

This structural difference leads to a loss of tightness. Computational results show that on GPT-2, the moment relaxation certificate is tighter than linear bound propagation on every attention head, and the looseness of bound propagation exactly matches the theoretically predicted per-operation excess. This provides a quantitative explanation for the limitations of linear bound propagation.

Linear bound propagation is a classic neural network verification method that propagates input interval bounds layer by layer: for each operation (such as affine transformation, ReLU), it computes the lower and upper bounds of the output interval and passes these bounds to the next layer. This method is computationally efficient but accumulates relaxation error, because each step independently takes the maximum possible value and ignores the correlations between different operations.

The core difference pointed out by the paper lies in the aggregation of second-order terms: operation-by-operation relaxation computes the upper bound of the second-order term as the sum of the maxima of each operation, i.e., (\sum_i \max(\cdot)), while coupled relaxation computes the joint maximum, i.e., (\max(\sum_i \cdot)). Since (\sum_i \max(\cdot) \ge \max(\sum_i \cdot)), operation-by-operation relaxation is necessarily looser, and the degree of looseness exactly equals the sum of the "per-operation excess." This structural difference explains why linear bound propagation is always looser than moment relaxation on attention heads, and the excess amount can be precisely predicted theoretically.

GPT-2 Experiments: Theory Validated on a Trained Model

The paper conducts computational experiments on GPT-2, showing that the theory can be transferred to trained models. In the exact worst-case comparison with fixed queries, the certificate achieves the theoretically predicted second-order accuracy. This is an end-to-end test of the theoretical framework: from the NP-hardness proof to the exponential cone relaxation to the numerical performance on actual models, the logical chain remains intact.

The experiments also validate the comparison conclusion with linear bound propagation—the moment relaxation is tighter on all tested attention heads, and the gap is consistent with the theoretical prediction of per-operation excess. This cross-validation enhances the credibility of the conclusion: the theory not only explains why moment relaxation is better, but also predicts by how much.

Implications for Robustness Verification Practice

This work provides a framework with tightness guarantees for attention certification. Its core contribution is not proposing yet another tighter bound, but establishing a theoretical connection between the tightness of the bound and computable quantities, making "how loose the certificate is" itself a predictable and analyzable object.

From an engineering perspective, this means that when designing verifiers in the future, one can use conic programming theory to determine whether a certain relaxation is fundamentally incapable of achieving a tighter bound. For processes that rely on attention verification to assess model safety, this theory provides a tool to distinguish between methodological limitations and model defects.

One-line Summary

The paper proves that attention certification difficulty stems from query-key bilinear interactions, and proposes exponential cone moment relaxation to achieve second-order tightness guarantees.

Paragraph Summary

This research addresses the blind spot of missing certificate tightness in verifying attention mechanisms of large language models by establishing a conic programming certification theory. The paper first proves that the NP-hardness of attention certification stems from the bilinear interaction between queries and keys rather than softmax, and that the problem is inapproximable when logits can shift by a constant magnitude; if the query is fixed, it can be solved efficiently. To this end, it proposes the exponential cone moment relaxation method, which provides certificates for individual attention heads with error bounded by the square of the perturbation radius, and this order cannot be improved. Further analysis shows that operation-by-operation relaxation (such as linear bound propagation) pays on second-order terms the sum of the maxima of each operation rather than the coupled maximum, leading to a structural loss of tightness. GPT-2 experiments verify that the moment relaxation certificate is tighter on every attention head, and the gap with linear bound propagation exactly matches the theoretically predicted per-operation excess, thereby achieving end-to-end validation from theory to trained models.