# SoftSort: A Continuous Relaxation for the argsort Operator

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

## Key facts

- Cited by 66 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2020.

## Built on by (most cited first, 30 of 66)

- [Git Re-Basin: Merging Models modulo Permutation Symmetries](https://mlsanity.com/paper/2209.04836/) (2022)
- [SPViT: Enabling Faster Vision Transformers via Soft Token Pruning](https://mlsanity.com/paper/2112.13890/) (2021)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [GrooMeD-NMS: Grouped Mathematically Differentiable NMS for Monocular 3D Object Detection](https://mlsanity.com/paper/2103.17202/) (2021)
- [On the Symmetries of Deep Learning Models and their Internal Representations](https://mlsanity.com/paper/2205.14258/) (2022)
- [Differentiable DAG Sampling](https://mlsanity.com/paper/2203.08509/) (2022)
- [HeatViT: Hardware-Efficient Adaptive Token Pruning for Vision Transformers](https://mlsanity.com/paper/2211.08110/) (2022)
- [Learning with Noisy Labels via Sparse Regularization](https://mlsanity.com/paper/2108.00192/) (2021)
- [Unsupervised Learning of Group Invariant and Equivariant Representations](https://mlsanity.com/paper/2202.07559/) (2022)
- [TransFlow: Transformer as Flow Learner](https://mlsanity.com/paper/2304.11523/) (2023)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [Learning Probabilistic Symmetrization for Architecture Agnostic Equivariance](https://mlsanity.com/paper/2306.02866/) (2023)
- [Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning](https://mlsanity.com/paper/2104.09856/) (2021)
- [Differentiable Top-k Classification Learning](https://mlsanity.com/paper/2206.07290/) (2022)
- [Learned Thresholds Token Merging and Pruning for Vision Transformers](https://mlsanity.com/paper/2307.10780/) (2023)
- [Learning to Evict from Key-Value Cache](https://mlsanity.com/paper/2602.10238/) (2026)
- [Learning by Sorting: Self-supervised Learning with Group Ordering Constraints](https://mlsanity.com/paper/2301.02009/) (2023)
- [LapSum -- One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection](https://mlsanity.com/paper/2503.06242/) (2025)
- [InfiGFusion: Graph-on-Logits Distillation via Efficient Gromov-Wasserstein for Model Fusion](https://mlsanity.com/paper/2505.13893/) (2025)
- [VisionSelector: End-to-End Learnable Visual Token Compression for Efficient Multimodal LLMs](https://mlsanity.com/paper/2510.16598/) (2025)
- [ESPFormer: Doubly-Stochastic Attention with Expected Sliced Transport Plans](https://mlsanity.com/paper/2502.07962/) (2025)
- [DAG Learning on the Permutahedron](https://mlsanity.com/paper/2301.11898/) (2023)
- [Learning to Hash Naturally Sorts](https://mlsanity.com/paper/2201.13322/) (2022)
- [Permutation-based Inference for Variational Learning of Directed Acyclic Graphs](https://mlsanity.com/paper/2402.02644/) (2024)
- [Generalizing Stochastic Smoothing for Differentiation and Gradient Estimation](https://mlsanity.com/paper/2410.08125/) (2024)
- [Efficient Token Compression for Vision Transformer with Spatial Information Preserved](https://mlsanity.com/paper/2503.23455/) (2025)
- [Differentiable Random Partition Models](https://mlsanity.com/paper/2305.16841/) (2023)
- [Fast Slate Policy Optimization: Going Beyond Plackett-Luce](https://mlsanity.com/paper/2308.01566/) (2023)
- [Learning Classifiers That Induce Markets](https://mlsanity.com/paper/2502.20012/) (2025)
- [Differentiable Fast Top-K Selection for Large-Scale Recommendation](https://mlsanity.com/paper/2510.11472/) (2025)

## Abstract (arXiv)

While sorting is an important procedure in computer science, the argsort operator - which takes as input a vector and returns its sorting permutation - has a discrete image and thus zero gradients almost everywhere. This prohibits end-to-end, gradient-based learning of models that rely on the argsort operator. A natural way to overcome this problem is to replace the argsort operator with a continuous relaxation. Recent work has shown a number of ways to do this, but the relaxations proposed so far are computationally complex. In this work we propose a simple continuous relaxation for the argsort operator which has the following qualities: it can be implemented in three lines of code, achieves state-of-the-art performance, is easy to reason about mathematically - substantially simplifying proofs - and is faster than competing approaches. We open source the code to reproduce all of the experiments and results.