Vertex-Softmax: Tight Transformer Verification via Exact Softmax Optimization

• URL: http://arxiv.org/abs/2605.10974v1
• Date: Fri, 08 May 2026 20:22:06 GMT
• Title: Vertex-Softmax: Tight Transformer Verification via Exact Softmax Optimization
• Abstract summary: We show that the exact optimum of a softmax function over interval constraints lies among only linearly many candidates.<n> integrated into a CROWN Convex Relaxation based Optimization for Worst-case Neurons.<n>We consistently match or outperforming alpha-CROWN and branch-and-bound baselines at a fraction of their cost.
• Score: 2.102532345063307
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Certified verification of transformer attention requires bounding the softmax function over interval constraints on the pre-softmax scores. Existing verifiers relax softmax ndependently of the downstream objective, leaving avoidable slack. We prove that the exact optimum of this score-box problem is attained at a vertex of the constraint box, and establish a threshold structure theorem showing that, after sorting the objective coefficients, the optimum lies among only linearly many candidates, yielding the Vertex-Softmax primitive with log-linear complexity in the sequence length. We further prove a formal optimality result showing that Vertex-Softmax is the tightest sound bound obtainable from score intervals alone, characterizing precisely what additional structure (score correlations, score-value coupling) is needed for further improvement. Integrated into a CROWN Convex Relaxation based Optimization for Worst-case Neurons)-style verifier with a formal soundness guarantee, Vertex-Softmax significantly improves certified rates and substantially tightens lower bounds across MNIST, Fashion-MNIST, and CIFAR-10 attention models, while consistently matching or outperforming alpha-CROWN and branch-and-bound baselines at a fraction of their cost.

Related papers

• The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization [50.59470683896735]
  min-max optimization has attracted increasing attention due to its applications in modern machine learning.<n>We provide a comprehensive theoretical of gradient descent (SGDA)<n>We develop new clipping-free algorithms, i.e., Stoc-GDAM and Stoc-TRmax, and they both can achieve the optimal dependence on the target accuracy without using gradient clipping.
  arXiv  Detail & Related papers  (2026-09-05T12:49:28Z)
• First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints [9.141425189503794]
  We propose a novel first-order Softmax-Weighted Switching Gradient method tailored for federated learning.<n>Under full client participation, our algorithm achieves the standard $mathcalO(-4)$ oracle complexity.<n>We provide a unified error decomposition and establish a sharp $mathcalO(logfrac1)$ high-probability convergence guarantee.
  arXiv  Detail & Related papers  (2026-03-06T00:14:46Z)
• Statistical Advantage of Softmax Attention: Insights from Single-Location Regression [0.0]
  We study the dominance of softmax over alternatives in large language models.<n>We show that softmax achieves the Bayes risk, whereas linear attention fundamentally falls short.<n>We discuss the connection with optimization by gradient-based algorithms.
  arXiv  Detail & Related papers  (2025-09-26T06:21:30Z)
• Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization [66.51747366239299]
  We propose a smooth variant of the min-max problem based on the augmented Lagrangian.<n>The proposed algorithm scales better with the number of objectives than subgradient-based strategies.
  arXiv  Detail & Related papers  (2025-03-16T11:05:51Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach.<n>Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Convex Bounds on the Softmax Function with Applications to Robustness Verification [69.09991317119679]
  The softmax function is a ubiquitous component at the output of neural networks and increasingly in intermediate layers as well. This paper provides convex lower bounds and concave upper bounds on the softmax function, which are compatible with convex optimization formulations for characterizing neural networks and other ML models.
  arXiv  Detail & Related papers  (2023-03-03T05:07:02Z)
• Spectral Aware Softmax for Visible-Infrared Person Re-Identification [123.69049942659285]
  Visible-infrared person re-identification (VI-ReID) aims to match specific pedestrian images from different modalities. Existing methods still follow the softmax loss training paradigm, which is widely used in single-modality classification tasks. We propose the spectral-aware softmax (SA-Softmax) loss, which can fully explore the embedding space with the modality information.
  arXiv  Detail & Related papers  (2023-02-03T02:57:18Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  We propose a new first-order optimization algorithm -- AcceleratedGradient-OptimisticGradient (AG-OG) Ascent. We show that AG-OG achieves the optimal convergence rate (up to a constant) for a variety of settings. We extend our algorithm to extend the setting and achieve the optimal convergence rate in both bi-SC-SC and bi-C-SC settings.
  arXiv  Detail & Related papers  (2022-10-31T17:59:29Z)
• Sparse-softmax: A Simpler and Faster Alternative Softmax Transformation [2.3813678058429626]
  The softmax function is widely used in artificial neural networks for the multiclass classification problems. In this paper, we provide an empirical study on a simple and concise softmax variant, namely sparse-softmax, to alleviate the problem that occurred in traditional softmax in terms of high-dimensional classification problems.
  arXiv  Detail & Related papers  (2021-12-23T09:53:38Z)
• Breaking the Softmax Bottleneck for Sequential Recommender Systems with Dropout and Decoupling [0.0]
  We show that there are more aspects to the Softmax bottleneck in SBRSs. We propose a simple yet effective method, Dropout and Decoupling (D&D), to alleviate these problems. Our method significantly improves the accuracy of a variety of Softmax-based SBRS algorithms.
  arXiv  Detail & Related papers  (2021-10-11T16:52:23Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.