# Convex Bounds on the Softmax Function with Applications to Robustness Verification

arXiv: https://arxiv.org/abs/2303.01713 · HTML: https://mlsanity.com/paper/2303.01713/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 58 references that are in the map.
- First posted on arXiv 3 Mar 2023.

## Builds on (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Safety Verification of Deep Neural Networks](https://mlsanity.com/paper/1610.06940/) (2016)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers](https://mlsanity.com/paper/2011.13824/) (2020)
- [Formal Security Analysis of Neural Networks using Symbolic Intervals](https://mlsanity.com/paper/1804.10829/) (2018)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Uncertainty Quantification and Deep Ensembles](https://mlsanity.com/paper/2007.08792/) (2020)
- [Branch and Bound for Piecewise Linear Neural Network Verification](https://mlsanity.com/paper/1909.06588/) (2019)
- [A Dual Approach to Scalable Verification of Deep Networks](https://mlsanity.com/paper/1803.06567/) (2018)
- [A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks](https://mlsanity.com/paper/1902.08722/) (2019)
- [Output Reachable Set Estimation and Verification for Multi-Layer Neural Networks](https://mlsanity.com/paper/1708.03322/) (2017)
- [Robustness Verification for Transformers](https://mlsanity.com/paper/2002.06622/) (2020)
- [Verification of Deep Convolutional Neural Networks Using ImageStars](https://mlsanity.com/paper/2004.05511/) (2020)
- [CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networks](https://mlsanity.com/paper/1811.12395/) (2018)
- [The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification](https://mlsanity.com/paper/2006.14076/) (2020)
- [Optimization and Abstraction: A Synergistic Approach for Analyzing Neural Network Robustness](https://mlsanity.com/paper/1904.09959/) (2019)
- [Reachable Polyhedral Marching (RPM): A Safety Verification Algorithm for Robotic Systems with Deep Neural Network Components](https://mlsanity.com/paper/2011.11609/) (2020)
- [A Game-Based Approximate Verification of Deep Neural Networks with Provable Guarantees](https://mlsanity.com/paper/1807.03571/) (2018)
- [Efficient Neural Network Analysis with Sum-of-Infeasibilities](https://mlsanity.com/paper/2203.11201/) (2022)
- [Fast Geometric Projections for Local Robustness Certification](https://mlsanity.com/paper/2002.04742/) (2020)

## Built on by (most cited first, 19 of 19)

- [Neural Network Verification with Branch-and-Bound for General Nonlinearities](https://mlsanity.com/paper/2405.21063/) (2024)
- [Certified Robustness to Data Poisoning in Gradient-Based Training](https://mlsanity.com/paper/2406.05670/) (2024)
- [Rectified SpaAttn: Revisiting Attention Sparsity for Efficient Video Generation](https://mlsanity.com/paper/2511.19835/) (2025)
- [Certifying Robustness of Learning-Based Keypoint Detection and Pose Estimation Methods](https://mlsanity.com/paper/2408.00117/) (2024)
- [On the Robustness of Text Vectorizers](https://mlsanity.com/paper/2303.07203/) (2023)
- [Achieving the Tightest Relaxation of Sigmoids for Formal Verification](https://mlsanity.com/paper/2408.10491/) (2024)
- [Vertex-Softmax: Tight Transformer Verification via Exact Softmax Optimization](https://mlsanity.com/paper/2605.10974/) (2026)
- [ZonoGPT: Towards An Abstract Domain for Verifying Large GPT Models](https://mlsanity.com/paper/2609.34457/) (2026)
- [STR-Cert: Robustness Certification for Deep Text Recognition on Deep Learning Pipelines and Vision Transformers](https://mlsanity.com/paper/2401.05338/) (2023)
- [Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activations](https://mlsanity.com/paper/2410.23362/) (2024)
- [Language Models That Walk the Talk: A Framework for Formal Fairness Certificates](https://mlsanity.com/paper/2505.12767/) (2025)
- [Influence-Guided Concolic Testing of Transformer Robustness](https://mlsanity.com/paper/2509.23806/) (2025)
- [Formal Reasoning About Confidence and Automated Verification of Neural Networks](https://mlsanity.com/paper/2511.07293/) (2025)
- [The Luna Bound Propagator for Formal Analysis of Neural Networks](https://mlsanity.com/paper/2603.23878/) (2026)
- [Analyzing Symbolic Properties for DRL Agents in Systems and Networking](https://mlsanity.com/paper/2604.04914/) (2026)
- [Towards Verified and Targeted Explanations through Formal Methods](https://mlsanity.com/paper/2604.14209/) (2026)
- [Precise Verification of Transformers through ReLU-Catalyzed Abstraction Refinement](https://mlsanity.com/paper/2605.14294/) (2026)
- [Neural Network Verification using Partial Multi-Neuron Relaxation](https://mlsanity.com/paper/2605.30155/) (2026)
- [Mining Verdict Boundaries for Neural Network Verification](https://mlsanity.com/paper/2607.28954/) (2026)

## Abstract (arXiv)

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. We derive bounds using both a natural exponential-reciprocal decomposition of the softmax as well as an alternative decomposition in terms of the log-sum-exp function. The new bounds are provably and/or numerically tighter than linear bounds obtained in previous work on robustness verification of transformers. As illustrations of the utility of the bounds, we apply them to verification of transformers as well as of the robustness of predictive uncertainty estimates of deep ensembles.