Sorting is a fundamental operation of all computer systems, having been a long-standing significant research topic. Beyond the problem formulation of traditional sorting algorithms, we consider sorting problems for more abstract yet expressive inputs, e.g., multi-digit images and image fragments, through a neural sorting network. To learn a mapping from a high-dimensional input to an ordinal variable, the differentiability of sorting networks needs to be guaranteed. In this paper we define a softening error by a differentiable swap function, and develop an error-free swap function that holds non-decreasing and differentiability conditions. Furthermore, a permutation-equivariant Transformer network with multi-head attention is adopted to capture dependency between given inputs and also leverage its model capacity with self-attention. Experiments on diverse sorting benchmarks show that our methods perform better than or comparable to baseline methods.

计算机系统中的排序是一项基础操作，这篇论文研究了排序问题的抽象输入和神经排序网络，通过差分排序网络的不同性实现高维输入到序数变量的映射，并采用多头注意力的置换等变转换网络来捕捉给定输入之间的依赖关系和提升模型准确性。实验结果表明，这些方法在不同的排序基准上表现优于或与基准方法相当。

具有无误差可微交换函数的广义神经排序网络