Generalized Neural Sorting Networks with Error-Free Differentiable Swap Functions
Authors: Jungtaek Kim
Jeongbeen Yoon
Minsu Cho
Venue: ICLR 2024 poster (2024)
Keywords: Sorting networks
Neural sorting networks
Differentiable swap functions
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: 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 a non-decreasing condition and differentiability. 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.

Published as a conference paper at ICLR 2024
GENERALIZED NEURAL SORTING NETWORKS WITH ERROR-FREE DIFFERENTIABLE S SWAP FUNCTIONS
Jungtaek Kim
Jeongbeen Yoon?
Minsu Cho
University of Pittsburgh "POSTECH
bongtaak.kin@pitt..eemm kim@pitt.eddu {jeongbeen, mschoo ac.
ABSTRACT
Sorting a fundamental operation 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 neural sorting net- work. To learn a mapping from a high-dimensional input to an ordinal variable, the differentiability of sorting networks needs be guaranteed. In this paper we de- fine a softening error by differentiable swap function, and develop an error-free swap function that holds non-decreasing condition and differentiability. Further- more, a permutaaion--equiarinn Transformer network with multi-heade head attention is adopted 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 baseline methods.
INTRODUCTION
Traditional sorting algorithms (Cormen et al. 2022), e.g., bubble sort, insertion sort, and quick sort, are well-established approach to arranging given instances in computer science. Since such sorting algorithm is a basic component build diverse computer systems, it has been long- standing significant research area in science and engineering. Moreover, sorting networks (Knuth) 1998 Ajtai et al., 1983), which are structurally designed as an abstract device with fixed number of wires, have been widely used to perform sorting algorithm on computing hardware where each wire corresponds
connection for a single swap operation.
Given an unordered sequence of n elements [si,..., sn] E R", the problem of sorting is defned find permutation matrix E [0,1] that transforms s into an ordered sequence s.:
S, = P
(1)
where a sorting algorithm a function f of s that predicts a permutation matrix P:
P f().
We generalize the formulation of traditional sorting problems to handle more diverse and expressive
types of inputs, e.g., multi-digit images and image fragments, which can contain ordinal information semantically. To this end, we extend the sequence of scalars to the sequence of vectors X [x1....,x] E Bend where d > 1 is an input dimensionality, and consider the following:
x
(3)
where X. and X ordered and unordered inputs, respectively. This generalized sorting problem can be reduced to (I) we are given a proper mapping from an input x E IRd to an ordinal value R. Without such mapping g. predicting P in (3) remains more challenging than in (1) because x is often a highly implicative high-dimensional input. We address this generalized sorting problem by learning a neural sorting network together with a mapping g in an end-to-end manner, given training data ((X(),(f) gt ) The main challenge to make the whole network )x......... with mapping and sorting components differentiable in order to effectively train the network with gradient-based learning scheme, which is not the case in general. To tackle

---

Published as a conference paper at ICLR 2024
the differentiability issue for such composite function, there has been recent research (Grover et al. 2019 Cuturi et al. 2019 Blondel et al. 2020 Petersen et al. 2021 2022).
In this paper, following sorting network-based sorting algorithm with differentiable swap func- tions (DSFs) (Petersen et al. 202T; 2022). we first define a softening error by a sorting network, which indicates difference between original and smoothed elements. Then, we propose error- free DSF that resolves an error accumulation problem induced by a soft DSF; this allows us to guarantee zero error in mapping X proper ordinal values. Based on this, we develop the sorting network with error-free DSFs where we adopt permutation-equivariae with multi-head attention (Vaswani al. 2017) to capture dependency between -igh-dimensional inputs and also leverage the model capacity of the neural network with a self-attention scheme.
Transformer architecture
Our contributions can be summarized as follows: (i) We define a softening error that measures a difference between original and smoothed values; (ii) We propose an error-free DSF that resolves the error accumulation problem of conventional DSFs and is still differentiable; (iii) We adopt a permutation-eqquiariiie network with multi-head attention ables g(X), unlike g(x); (iv) We demonstrate that our proposed methods are effective in diverse sorting benchmarks, compared to existing baseline methods.
mapping from inputs to ordinal vari-
2 SORTING NETWORKS WITH DIFFERENTIABLE SWAP FUNCTIONS
Following traditional sorting algorithms such as bubble sort, quick sort, and merge sort (Cormen al.] 2022) and sorting networks that are constructed by a fixed number of wires (Knuth 1998 Ajtai et al. 1983), swap function is key ingredient of sorting algorithms and sorting networks:
(a', y²) swap(x, y),
(4)
where x' = min(x, v) and y max y), which makes the order of x and y correct. For example, if x > then x' = and y' = x. Without loss of generality, we can express min(-.)) and max(.,-) with the following equations:
min(2, (ain v) = x xL - x)1 + vlo(( - y)1 and max( v) = =[o(x - y)1 + tyloyy - =)1, (5)
where 1-1 rounds to the nearest integer and (-) E [0, transforms an input to a bounded value, i.e., a probability over inputs. Computing (5) is straightforward, but they are not differentiable. To enable us to differentiate a swap function, the soft versions of min and max can be defined:
min(x, v) zy x)- + yar -yy y) and max(ar,) y) = xo y) + yo xx). 2),
(6)
where (-) is differentiable. In addition to its differentiabilityy either (5) or (6) can be achieved with a sigmoid function a (x). i.e., a s-shaped function, which satisfies the following properties that (i) a (x) is non-decreasing, (ii) (xx) 1 if - c0, (iii) (I:) 0 if x + -O0, (iv) a0) 0.5, and (v) (x) = 1 - o(-x). Also, as discussed by Petersen et al. (2022). ). the choice of a affects the performance of neural network-bare based sorting network in theory as well as in practice. For example, an optimal monotonic sigmoid function, which is visualized in Figure is defined as the following:
Te (Bx)-1
if fx < <0.25,
(x = 1
16 (Bx)
if 3r > 0.25, otherwise,
Bx + 0.5
where is steepness; see the work (Petersen al. 2022) for the details of these numerical and theoretical analyses. Here, we would like to emphasize that the important point of such monotonic sigmoid functions is strict monotonicity. However, as will be discussed in Section 3 it induces an enror accumulation problem, which can degrade the performance of the sorting network.
By either (5) or (6). the permutation matrix P (henceforth, denoted as Phard and Psof for (5) and (6). respectively) is calculated by the following procedure of sorting network: (i) Building pre- defined sorting network with a fixed number of wires a wire is a component for comparing and swapping two elements; (ii) Feeding an unordered sequence s into the pre-defined sorting network and calculating a wire-wise permutation matrix P, for each wire iteratively; (iii) Calculating the permutation matrix P by multiplying all wire-wise permutation matrices.
As shown in Figure I a set of wires represents a set of swap operations that are operated simultane- ously, so that each set produces intermediate permutation matrix P; the ith step. Consequently,
2

---

Published as a conference paper at ICLR 2024
Japkec AlI
Tedgpvoal
Oyttzal
100
0.4
00
p 222
# $=000
ELI
P P4 P =
Figure Comparisons of diverse DSFs where swap function is applied once. After a single operation, two input values and y are softened while our error-free DSF does not change two values. If I - yl is small, softening be more significant.
Figure 1: A sorting network with 5 wire sets and their permutation matrices.
P P P. = (PP...PPPP.) where is the number of wire sets. For example, in Fig- ure k=
The doubly-stocharn matrix property of shown by the following proposition:
Proposition 1 (Modificatioon of Lemma in the work (Petersen al. 2022 ) A Aermutation matrix
E RRxx doubly-stochustic, which implies that ET= P/y and R [y=(P) = 1. In
particular, regardless of the definition of swap function with min, max, min, and max, hard and soft permutation matrices, i.e. Phard and P soft, are
Proof. The proof of Proposition is provided Section D
In Sections and we present an error-fre free DSF and a neural sorting network with error- error-free DSFs.
3 ERROR-FREE DIFFERENTIABLE SWAP FUNCTIONS
Before introducing our error-free DSF, we start by describing the motivation of the error-free DSF.
Due to the nature of min and max, which is descrihed in (6), the monotonic DSF changes original input values. For example, if x < y. then x < min(x, swap function. It can be serious problem because changes by the DSF are accumulated the DSF applies iteratively, called an error accumulation problem in this paper. The results of sigmoid func- tions such the logistic, logistic with ART, reciprocal, Cauchy, and optimal monotonie functions, and also our error- free DSF are presented in Figure where swap function is applied once; see the work (Petersen et al. 2022) for the respective sigmold functions. All DSFs except for our error-free DSF change two values, so that they can make two values not distinguishable. In particular, if difference between two values is small, the consequence of softening is more significant than case with large difference. Moreover, if apply swap function repeatedly, they eventually become identical; see Figure in Section B While swap function is not applied as many as tested in the synthetic example shown in Figure it can still cause the error accumulation problem with few operations. Here we formally define softening error, which has been mentioned in this paragraph:
(2in(2, y) and max(x, y) < after applying the
Definition 1. Suppose that we are given and y where x y. By (6), these values and y are softened by monotonic DSF and they satisfy the following inequalities:
< x' min(a, y) I y' max((x) y)
(8)
Therefore, we define a difference between the original and softened values, x' or
y- - y = max(x, u) = x' - x min (x., y) x > 0,
which is called a softening error in this paper. Without loss of generality, the softening error is min(x, y) min (x, y) or max(s, v) max (x. y) for any x. y-
3

---

Published as a conference paper at ICLR 2024
Note that (9) is satisfied by y max 2. y - oy 2)) - 2o( y) yor v) =(11- (y =)) min(x, (r, v) I. using (6) and a (x - y) = o x).
With Definition [ we are able to specify the seriousness of the error accumulation problem:
Proposition 2. Suppose that and y are given and DSF is applied k times. Assuming ex- treme scenario that & + oc, error accumulation becomes (max((r, y) min(2, v))/2, under the assumption that V V
Proof. The proof of this proposition can be found in Section
E
As mentioned in the proof of Proposition Sa and empirically shown in Figure 2 swap function with relatively large (2)(2) changes the original values æ, y significantly compared to swap function with relatively small (xr) they tend to become identical with the small number of operations in the case of large (z)()))
In addition to the error accumulation problem, such a DSF depends on the scale of [x y/ as shown in Figure 2 If x < y but æ and y are close enough, ay - x) between 0.5 and 1, which implies that the error can be induced by the scale of [z y| as well.
To tackle the aforementioned problem of error accumulation, we propose an error-free DSF:
(x', = (2
(10)
where
x'' (min y) min(2. (z, v)) min(2: y)
and y' (max(xx v) max (r, y)) mmx (z, y).
(11)
Note that indicates that gradients are stopped amid backward propagation, inspired by straight- through estimator (Bengio et al.) 2013). At a step for forward propagation, the error-free DSF produces x' = min(x. y) and y max( v). On the contrary, at step for backward propagation, the gradients of min and max are used to update learnable parameters. Consequently, our error-free DSF does not smooth the original elements as shown in Figure and our DSF shows 100% accuracy for acCem and acCow (see Section their definitions) as shown in Figure Compared to our DSF, the existing DSFs do not correspond the original elements to the elements that have been compared and fail to achieve reasonable performance as sequence length increases, in the cases of Figure 6
By 5 ( and 11, we obtain the following:
x' (oll =:] +tllllaaa v)1 (zo - x) yo -))) (woly tor y))
=x ((Lo(y x)] -y x)) to - x))+ (LL y)1 v)1-o(z +0 -)) (12)
y y== ((lo(x v)1 -a (x- v))ag to v)) +y ((ooy -=)] -())) to x)), (13)
which can be used to define permutation matrix with the error-free DSF. For example, if n 2, permutation matrix P over [z. y)
(Lo(y x)] oly - z))=s toy--2) (La(x - v) a( y))sg + + y) [[ - w)1 o(r y)ln + to - (Lo(y x) - a x))sgg + tol x)
P
(14)
To sum up. describe the following proposition on error-free DSF, swaperror-fred (-, Proposition 3. By 11 the softening error x' min(x, y) or max(x, y) 'f' for an error-free DSF
zero.
Proof. The proof of this proposition is presented in Section F
NEURAL SORTING NETWORKS WITH ERROR-FREE DIFFERENTIABLE SWAP FUNCTIONS
In this section we propose a generalized neural network-basee sorting network with an error-frec DSF and permutation--qquiariinn neural network, considering the properties covered in Section
4

---

Published as a conference paper at ICLR 2024
Soft Sorting Network
wift
2
3 2
3 7 3 1
82
Permutation
7
-Equivarlant Network
P Land
4 1 0
84
0
X
8
Hard Sorking Network
Figure 3: Illustration of neural sorting network with enro-frree DSFs. Given high-dimensional inputs X, a to be swapped using soft hard sorting network.
network produces a vector ordinal variables s, which used
First, we describe a procedure for transforming eigh-dimensional inputs to ordinal scores. Such a mapping 9 IRd R. which consists of set of learnable parameters, has to satisfy permutation- equivariant property:
[g(x
= T ([g(x))) ((e))))(xx)).....)))) ((x.)))))l))))))..
(15)
where = ( n])]i i vi E [n), for any permutation function Typically, an instance-
wise neural network, which is applied to each element in a sequence given, is permutation-
equivariant (Zaheer et al. 2017). Based on this property, instance-wise CNNs are employed in differentiable sorting al algorithms (Grover et al. 2019: Cuturi et al.) 2019 Petersen et al. 2021]22 2002).
However, such an instance- wise architecture limited since it is ineffective for capturing essential features from a sequence. Some types of neural networks such as long short-term memory (Hochre- iter & Schmidhuber 1997) and the standard Transformer architecture (Vaswani al.) 2017)
capable of modeling a sequence of instances, utilizing recurrent connections, scaled dor-product at- tention, or parameter sharing across elements. While they are powerful for modeling a sequence, they are not obviously permutation-equee equivariant. Instead of such permutation-sensee models, we adopt a robust Transformer-hased network that satisfies the cermutaaion-equivariie property, which is inspired by the recent work (Vaswani et al., 2017 Lee et al., 2019)).
To explain our network, we briefly introduce scaled dot-product attention and multi-hear attention:
QK
att(Q, K. V) = softmax
V
and mha(Q, K, V) = [head], head,. heads Wos
Vilm
(16)
& VW("), Q, V Raaxhd,,. w w(() and W, E h.d x hdm.. Similar the Transformer network. series of mha blocks is stacked with layer normalization (Ba et al. 2016) and residual connections (He et al., 2016). and in this pa- per X is processed by mha Z, Z. Z) where Z = g'( or Z the output of a previous layer; see Section forr the details of the architectures. Note that g' ((- is an instance-wise embedding layer, e.g., a simple fully-connected network or a simple CNN, Importantly, compared to the standard Transformer model, our network does not include a positional embedding, in order to satisfy the permutation-eqqiiaaiin property; mha ZZ Z, Z) satisfies (15) for the permutation of Z1, Z2. Zn where Z [21, .2.....5 Zn The output of network is followed by the last instance-wiss fully-connected layer. Finally, as shown in Figure 3 our sorting network is able to produce differ- entiable permutation matrices Note that P Phard and Pooft are doubly-stochastic by Proposition T In addition, the details of the permutation-equivate network with multi-head attention are briefly visualized in Figure 7
where head, (Q( kW(),
w ghdmnd...
&
s, i.e., Phard and P soott by utilizing (T1) and (6), respectively.
To learn the permutation-equivarii network g. we define both objectives for Psof and P Phard:
Lsoft
gt log P soft
P log(1 P soft ))is>
(17)
Lhard
[oo.hadd
X 11 T X 2
(18)

---

Published as a conference paper at ICLR 2024
Table 1: Results sorting the four-digit MNIST dataset. The results are measured in accem and aCCew (in parentheses). FLOPs is on the basis of a sequence length 3. All the values are averaged over runs with different seeds.
Sequence Length 9
Method
Model
FLOPs #t'aram.
NeuralSort
91.9 (94.5) 77.7 (90.1)
(8.2)
43.4
(71.6)
(38.8)
Sinkhorn Sort
92.8 (95.0) 81.1 (91.7) 65.6 (88.2) 49.7 (84.7)
(74.)
0.0 (41.2)
Sort Rank
(936(
(87.2) 49.7 (81.3) (75.2)
(60.9)
Logistic
92.0 77.2 (89.8) 54.8 (83.6) (7924) 4.7 (62.3)
0.0 (56.3) 130M
CNN
855K
Logistic ART
94.3 83.4 (92.6) (90.0) (86.7)
(79.4)
(64.9)
Diffsort
Reciprocal
94.4 (96. 85.0 (93.3)
60.8 (90.7
(81.9
1.0 (66.8)
Cauchy
94.2 (96.0) 84,9 (93.2) 73.3 (90.5) 63.8 (89.1) 31.1 (82.2)
0.8 (63.3)
Optimal
(96.3)
(93.3) 73.6 (90.7)
(88.5)
(82.3)
(67.9)
95.2 (96.7) 81.2 (94.2) 76.6 (91.6) 64.8 (89.2) 34.7 (85.3)
(69.2)
130M
855K
Ours
ErrerFrree DSFs
Transformer-S 95.9 (97.1) 94.8 (97.5) 90.8 (96.5) 86.9 (95.7) 74.3 (93.6)
37.8 (87.7)
130M
665K
Transformer-1. 1. (97.5) 95.4 (97.7) 92.9 (97.2) 90.1 (96.5) 82.5 (95.0) 46.2 (88.9)
137M
3.10M
where Pyt is ground-truth permutation matrix. Note that all the operations in Lsoft are entry-wise. Similar to (17). the objective (T8) for Phrd should be designed as the form of binary cross-entropy, which tends to be generally robust for training deep neural networks. However, we struggle to apply the binary cross-entropy for Phard into our problem formulation, due to discretized loss values. In particular, the form of cross-entropy for hard can be used to train the sorting network, but degrades its performance in our preliminary experiments. Thus, we choose the objective for P hard as |oooaadd - X.,gt 1 with the Frobenius norm, which helps to train the network more robustly.
In addition, using proposition on splitting Phrrd which is discussed in Section H the objective 18) for Phard can be modified by splitting Phard, Pgt, and X, which is able to reduce the number of possible permutations; see the associated section for details. Eventually, our network g trained by the combined loss L Laoft + hhaard, where À is a balancing hyperparameter, an analysis on can be found in the appendices. As mentioned above, a landscape of Lhard is not smooth due to the property of a straight-through estimator, even though we use haard. Thus, we combine both objectives the form of single loss, which is widely adopted the deep learning community.
5 EXPERIMENTS
We demonstrate experimental results to show the validity of our methods. Our neural network- based sorting network aims solve two benchmarks: sorting (i) multi-digit images and (ii) image fragments. Unless otherwise specified, an odd-even sorting network is used in the experiments. We measure the performance of each method in acCem and aCCow:
Ee 1 ([s(),, 13) and
N DE 1 ([B8)), = 1,)
acCem
acCew
N
Nn
(19)
where argsort returns indices to sort a given vector and 1(-) is an indicator function. Note that
( argsort
(P))T s(1)
and { argsort (p(3T s(1)
(20)
We attempt to match the capacities of the Transformer-ban based models to the conventional CNNs. As described in Tables and 3 the capacities of the Transformer-Se Small models are smaller than or similar to the capacities of the CNNs in terms of FLOPs and the number of parameters.
5.1 SORTING MULTI-DIGHT IMAGES
Datasets. As steadily utilized in the previous work (Grover et al. 2019: Cuturi et al. 2019 Blondel
et al. 2020 Petersen et al. 2021 2022) we create four-digit dataset by concatenating four images from the MNIST dataset (eeCun al. 1998); ; see Figure 3 for some examples of the dataset. On the other hand, the SVHN dataset (Netzer et al. 2011) contains multi-digit numbers extracted from street view images and is therefore suitable for sorting.

---

Published as a conference paper at ICLR 2024
Table 2: Results sorting the SVHN dataset. FL.PSs is computed on the basis of sequence length 3. All the values are averaged over 5 runs with different seeds.
Sequence Length
Method
Model
7
15
FLOPS
#Param.
Logistic
76.3 (83.2)
(72.7)
21.8 (63.9)
(61.7)
(45.9)
Lngistic w/ ART
83.2 (88.1)
64.1 (82.1)
(76.5)
24.2 (69.6)
2.4 (56.8)
Diffsort
Reciprocal
CNN
85.7 (89.8)
68.8 (84.2)
(80.0)
40.0 (76.3)
13.2 (66.0)
326M
1.226M
Canchy Optimal
85.5 (89.6)
68.5 (84.1)
52.9
39.9 (75.8)
13.7 (66.0)
86.0 (90.0)
67,5 (83.5)
53.1 (80.0)
39.1 (76.0)
13.2 (66.3)
CNN
86.8 (90.6)
68,9 (84.5)
(80.4)
40.0 40700
12.0 (65.3)
326M
1.226M
Ours
Error-Free DSPs
Transformer-S
86.6 (90.2)
72.6 (85.7)
62.5 (83.5)
48.6 (79.3)
19.3 (69.6)
210M
1.223M
Transformer-L
(91.2)
74.0 (86.3)
63.9 (83.8)
50.2 (80.1)
21.7
332M
3,475M
Table 3: Results on sorting image fragments of MNIST and CIFAR-10. 10. 2 x 2 and 3 indicate
the numbers of fragments, and 14 x 14, 9 x 9, 16 16, and 10 10 (in parentheses) indicate the sizes of image fragments. FLOPs is computed on the basis of the MNIST
2 (14 x 14) case and the CIFAR-10 x 2 (16 x 16) case. All the values are averaged over runs with different seeds.
MNIST
CIFAR-10 X
Method
Model
2
x
FLOPS #Param.
x 2
FLOPs #P'aram.
(14
(9 9)
(16 x 16)
(10
Logistic
98.5 (99.0)
(42.9)
(73.6)
(27.7)
Logistic w/ ART
98.4 (99.1)
5.4 (42.9)
56.7 (73.4)
0.7 (27.7)
Diffsort
Reciprocal Cauchy
CNN
98.4 (99.2)
(42.9)
84K
56.7 (73.4)
(27.8)
85K
98.4 (99.2)
5.3 (42.9)
(73.6)
(27.9)
Optimal
98.4 (99.1)
5.3 (43.0)
56.6 (73.4)
0.7 (27.7)
Ours
Eroor Free DSF'
Transformer
CNN
98.4 (99.2)
(99.2)
5.2 (42.6) 1.498M
(43.7)
84K
87K
56.9 (73.6)
58.1 (74.2)
0.8 (28.0) 1663M
(28.3)
85K
87K
Experimental Details. We conduct the experiments 5 times by varying random seeds to report the average of acCem and acCew, and use the optimal monotonic sigmoid function as DSFs. The perfor- mance of each model measured by test dataset. We use the AdamW optimizer (Loshchilov & Hutter 20088), and train each model for 200,000 steps on the four-digit MNIST dataset and 300,000 steps on the SVHN dataset. Unless otherwise noted, we follow the same settings of the work (Pe- tersen et al. 2022) for fair comparisons. Missing details are described in Section
Results. Tables [ and 2 show the results of the previous work such as NeuralSort (Grover et al.)
2019), Sinkhorn Sort (Cuturi et al. 2019), Fast Sort Rank (Blondel et al. 2020), and Diffsort (Pe- tersen et al.) 2021 2022), and our methods the MNIST and SVHN datasets, respectively. When equivariant network, our method shows better than
we use the conventional CNN as a permutation-cquivaraann comparable to the previous methods. As exploit more powerful models, i.c., the Transformer- Small and Transformer- Large wetpuuttttionuuvvariiae models, our approaches show better results compared to other existing methods including method with the conventional CNN
5.2 SORTING IMAGE FRAGMENTS
Datasets. For experiments on sorting image fragments, we use datasets: the MNIST dataset (LeCun et al. 1998) and the CIFAR-10 dataset (Krizhevsky & Hinton 2009). Similar to the work (Mena et al. 2018), we create multiple fragments or patches from a single-digit image of the MNIST dataset to utilize themselves as inputs for example, 4 fragments of size 14 x 14 or fragments of size 9 x 9 are created from single image. Similarly, the image included in the CIFAR-10 10 dataset, which contains one of various objects, e.g., birds and cats, is split to multiple patches, and then is used to the experiments on sorting image fragments. See Table for the details of the image fragments and their sizes.
'Thanks to many open-source projects, we can easily run the baseline methods. However, it is difficult to reproduce some results due to unknown random seeds. For this reason, bring the results from the work (Pc- tersen al. 2022). and use fixed random seeds, i.c., 42, 84, 126, 168, 210, for methods.

---

Published as a conference paper at ICLR 2024
Experimental Details. Similar to the experiments on sorting multi images, optimal mono- tonic sigmoid function is used as DSFs, Since the size of inputs is much smaller than the experiments on sorting multi-digit images, shown in Section 5.1. we modify the architectures of the CNNs and the Transformer-basee models. We reduce the kernel size of convolution layers from to 3 and make strides 2. Due to the small input sizes, omit the results by the Transformer-Large model for these experiments. Additionally. max-pooling operations are removed. Similar to the experiments in Section 5.1 we use the AdamW optimizer (Loshchilov & Hutter 2018). Moreover, each model is trained for 50,000 steps when the number of fragments is 2 x 2, Lee. when a sequence length is 4, and 100,000 steps for 3 x fragments, i.e., when a sequence length is 9. Additional information including the details of neural architectures can be found in Sections J
Results. Table 3 represents the experimental results on both datasets of image fragments, which are created from the MNIST and CIFAR-I0 datasets. Similar to the experiments on sorting multi- digit images, the more powerful architecture improves performance in this task.
According to the experimental results, we achieve satisfactory performance by applying the error- free DSFs, combined loss, and mannsformer-base models with multi-head attention. We provide detailed discussion on how they contribute to the performance gains in Section 7 and empirical studies steepness, learning rate, and balancing hyperparameter in Section 7 and the appendices.
RELATED WORK
Differentiable Sorting Algorithms. To allow us to differentiate a sorting algorithm, Grover et al. 2019) have proposed the continuous relaxation of argsort operator, which is named NeuralSort. In this work, the output of NeuralSort only satisfies the row-stochastic matrix property, although Grover al. (2019) attempt employ a gradient-based optimization strategy in learning neural sorting algorithm. Cuturi et al. (2019) propose a smoothed ranking and sorting operator using op- timal transport, which is the natural relaxation for assignments. To reduce the cost of the optimal transport, the Sinkhorn algorithm (Cuturi 2013) is used. Then, Blondel et al.] (2220) have proposed a differentiable sorting and ranking operator with On log n.) time and (m) space complexities, which is named Fast Rank & Sort, by constructing differentiable operators as projections mutahedron. PPetersen et al. (202T) have suggested a differentiable sorting network with relaxed conditional swap functions. Recently, the same authors analyze the characteristics of the relaxation of monotonic conditional swap functions, and propose several monotonic swap functions, e.g., the Cauchy and optimal monotonic functions (Petersen al. 2022)
per-
Ceanuutttio--qqivaatn Networks. A seminal architecture, long short-term memory (Hochre- iter & Schmidhuber] 1997) can be used in modeling a sequence without any difficulty, and a joquence-to-squeene model (Sutskever et al. (014) can be employed cope with sequence. However, as discussed in the work by Vinyals et al. (2016). an unordered sequence can have good orderings, by analyzing the effects of permutation thoroughly. Zaheer al. (017)) propose permutation-invarian or pernutation-eqquiarrin network, named Deep Sets, and prove the permu- tation invariance and permutation equivariance of the proposed models. By utilizing the Transformer network /aaswani et al. 2017), Lee et al. (2019) have proposed permutation coamutaaion-euuvariiann network.
DISCUSSION
Numerical Analysis on Our Methods and Their Hyperparameters. We carry out numerical analyses on the effects of our methods, compared to baseline method, i.e., Diffsort with the optimal monotonic sigmoid function. As reported Table we demonstrate that our methods better sorting performance compared to the baseline, which implies that our suggestions are effective in the sorting tasks. In these experiments, we follow the settings of the experiments described in Section 5.1 Moreover, present numerical analyses balancing hyperparameter, steepness, and learning rate in Sections K and
Analysis on Performance Gains. According to the results Sections 5 and 7 we can argue that the error-free DSFs, our proposed loss, and the Transformer-based models contribute to better
8

---

Published as a conference paper at ICLR 2024
Table 4: Study on comparisons of Diffsort with the optimal monotonic sigmoid function and methods in the experiments on sorting the four-digit MNIST dataset.
Sequence Length
Method
Model
15
32
Diffsort
CNN
(96.3)
(93.3)
(90.7)
(88.5)
(82.3)
(67.9)
Ours
95.2 (96.7)
87.2 (94.2)
76.6 (91.6)
64.8 (89.2)
34.7 (83.3)
2.1 (69.2)
Diflsort
Transfomeer
95.9 (97.1)
90.2 (95.4)
83.9 (94.2)
77.2 (92.9)
57.3 (89.7)
16.3 (81.7)
Ours
95.9 (97.1)
94.8 (97.5)
90.8 (96.5)
86.9 (95.7)
74.3 (93.6)
37.8 (87.7)
Dillsort
96.5 (97.5)
92.6 (96.4)
87.6 (95.3)
82.6 (94.3)
67.8 (92.0)
32.1 (85.7)
Transformer-L
Ours
96.5 (97.5)
95.4 (97.7)
92.9 (97.2)
90.1 (96.5)
82.5 (95.0)
46.2 (88.9)
performance considerably compared to the baseline methods. As shown in Tables [ and 4 the performance gains by the Transformer-based models are more substantial than the gains by the error- free DSFs and our loss, since multi-head attention is effective for capturing long-term dependency (or dependency between multiple instances in our case) and reducing inductive biases. However, as will be discussed in the following, the hard permutation matrices can be used in the case that does not allow to mix instances in X, e.g., sorting image fragments in Section 5.2
Utilization of Hard Permutation Matrices. While the of soft permutation matrix P soft makes given instances mixed, a hard permutation matrix Phard is instrumental in applying Phard in problem that requires swapping given instances exactly. More precisely, each row of P Poot X is linear combination of some column of ssoft and X, but of P hard X corresponds to an exact row in X. This property can be used to preserve input instances from sorting operations. The experiments in Section (.22ioo/552ee0 can be considered as one of such cases, and exhibits the strength of our method, not only the performance in aCCem and acCow-
Effects of Multi-Head Attention in the Problem 43) We follow the model architecture used in the previous work (Grover et al. 2019 Cuturi et al. 2019 petersen al. 2021 2022) for the CNNs. However, as shown in Tables mance. In particular, whereas the model capacity, i.e., FLOPs and the number of parameters, of the Transformer-Sin models is almost matched to or less than the capacity of the CNNs, the results by the Transformer-Shie
and the model is not enough to show the best perfor-
models outperform the results by the CNNs. presume that these per- formance gains are derived from a multi-head attention's ability capture long-term dependency and reduce inductive biases, as widely stated in many recent studies diverse fields such as natural language processing (Vaswani et al. 2017]] Devlin al. 2018 Brown et al.) (2020). computer vi- sion (Dosovitskiy et al., 2001 Liu et al. 2021), and 3D vision (Nahh et al.) 20ao et al. 2021) Especially, unlike the instance- wise CNNs, our permutation-equee -qquivvrrnai Transformer architecture utlizes self-attention for given instances, so that our model can productively compare instances in sequence and effectively learn the relative relationship between them.
Further Study of Differentiable Sorting Algorithms. Differentiable sorting encourages us to train a mapping from an abstract input to an ordinal score using supervision on permutation matrices. However, this line of studies is limited ordering information, e.g., multi- numbers. As the further study of differentiable sorting, we can expand this framework to sort more ambiguous data, which contains implicitly ordinal information.
sorting problem of high -igh-simensinaal data with clear
8 CONCLUSION
In this paper, we defined a softening error, induced by a monotonic DSF, and demonstrated several evidences of the error accumulation problem. To resolve the error accumulation problem, an error- free DSF is proposed, inspired by straight-through estimator. Moreover, we provided the simple theoretical and empirical analyses that our error-free DSF successfully achieves a zero error and also holds a non-decreasing condition and differentiability. By combining all components, we suggested a generalized neural sorting network with the enror-free DSF and multi seat- attention. Finally, we showed that our methods are better than comparable other algorithms in diverse benchmarks.

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENT
As discussed in Section 7 the hard permutation matrices produced by our methods allow to swap instances exactly, not the linear combination of instances. This characteristic is required when we are given the final outcomes of sorting supervision. This scenario is tested by the experiments presented in Section [.2] In these experiments, we are supposed that original images are provided as supervision. Building on the advantages of neural network-based sorting networks, we expand their practical significance to the cases that need hard permutation matrices. On the other hand, the nature of neural sorting networks may yield a potential negative societal impact. this line of research including approaches is employed to sort controversial -ighdiimessionll data such as beauty and intelligence, it can be considered as the unethical use cases of artificial intelligence.
ACKNOWLEDGMENTS
This work was supported by the IITP grants (2022-0-00290: Visual Intelligence for Space-Time Un- derstanding and Generation based on Multi-layered Visual Common Sense, 2022-0-00264: Compre- hensive Video Understanding and Generation with Knowledge- Deep Logic Neural Network) funded by Ministry of Science and ICT, Republic of Korea.
REFERENCES
M. Ajtai, J. Komlós, and E. Szemerédi. An O(n log sorting network. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pp. 1-9, Boston, Massachusetts, USA, 1983.
J. L. Ba, J. R. Kiros, and G. E. Hinton. Layer normalization. arXiv preprint arXiv:1607.06453 2016.
Y. Bengio, N. Léonard, and A. Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint 1308.33333 2013.
L. Berrada, A. Zisserman, and M. P. Mudigonda. Smooth loss functions for deep top-k classification. In Proceedings of the International Conference on Learning Representations (ICLR), Vancouver, British Columbia, Canada, 2018
M. Blondel, O. Teboul, Q Berthet, and J. Djolonga. Fast differentiable sorting and ranking. In Proceedings of the International Conference on Machine Learning (ICML), pp. 950-959, Virtual, 2020.
T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, Dhariwal, A. Neelakantan, Shyam, G. Sastry, A. Askell, S. Agarwal, A. Vourbert-Voss. G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS), vol- ume 33, pp. 1877-1901, Virtual, 2020.
Z. Cao, T. Qin, T.-. Liu, M.-F. Tsai, and H. Li. Learning rank: from pairwise approach to listwise approach. In Proceedings of the International Conference on Machine Learning (ICML), pp. 129-136, Corvallis, Oregon, USA, 2007.
H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT Press, edition, 2022.
M. Cuturi. Sinkhorn distances: lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems (NeurIPS), volume 26, pp. 2292-2300, Lake Tahoe, Nevada, USA, 2013.
M. Cuturi, O. Teboul, and J.PP. Vert. Differentiable ranking and sorting using optimal transport. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, Vancouver, British Columbia, Canada, 2019.
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: Pre-training of deep bidirectional trans- formers for language understanding. arXiv preprint 10/0.0:8//004400 2018
10

---

Published as a conference paper at ICLR 2024
A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenbom, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold. S. Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x 16 words: Transformers for image recognition at scale. In Proceedings of the International Conference Learning Representations (ICLR), Virtual, 2021.
A. Grover, E. Wang, A. Zweig, and S. Ermon. Stochastic optimization of sorting networks via con- tinuous relaxations. In Proceedings of the International Conference on Learning Representations (ICLR), New Orleans, Louisiana, USA, 2019.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), pp- 770-778, Las Vegas, Nevada, USA, 2016.
S. Hochreiter and Schmidhuber. Long short-term memory. Neural Computation, 983):1335- 1997.
D. E. Knuth. The art of computer programming, volume 3. Addison- Professional, 2 edition, 1998.
A. Krizhevsky and G. E. Hinton. Learning multiple layers of features from tiny images. Technical report, Computer Science Department, University of Toronto, 2009.
Y. LeCun, Cortes, and C. C. Burges. The MNIST database of handwritten digits. http: //yann. lecun. com/ /xdd///d////////////// / homts/mnis////// 1998.
Lee, Y. Lee. J. Kim, A. Kosiorek, S. Choi, and Y. W. Tch. Set Transformer: A framework for iieention-based permutation-invariian neural networks. In Proceedings of the International Conference on Machine Learning (ICML), pp. 3744-3753, Long Beach, California, USA, 2019.
T--Y. Liu. Learning to rank for information retrieval. Foundations and Trends@ in Information Retrieval, 3(3):225-333) 3311, 2009.
Z. Liu, Y. Lin, Y. Cao, H. Hu, Y. Wei, Z. Zhang, S. Lin, and B. Guo. Swin Transformer; Hierarchical vision transformer using shifted windows. In Proceedings of the International Conference on Computer Vision (ICCV), pp. 10012-10022, Virtual, 2021.
I. Loshchilov and Hutter. Decoupled weight decay regularization. In Proceedings of the Inter- national Conference on Learning Representations (ICLR), Vancouver, British Columbia, Canada, 2018.
G. E. Mena, D. Belanger, S. Linderman, and J. Snoek. Learning latent permutations with Gumbel- Sinkhorn networks. In Proceedings of the International Conference on Learning Representations (ICLR), Vancouver, British Columbia, Canada, 2018.
C. Nash, Y. Ganin, M. A. Eslami, and P. W. Battaglia. PolyGen: An autoregressive generative model of 3D meshes. In Proceedings of the International Conference on Machine Learning (ICML), pp. 7220-7229, Virtual, 2020.
Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng. Reading digits in natural images with unsupervised feature learning. In Neural Information Processing Systems Workshop on Deep Learning and Unsupervised Feature Learning, Granada, Spain, 2011.
Petersen, C. Borgelt, H. Kuehne, and O. Deussen. Differentiable sorting networks for scalable sorting and ranking supervision. In Proceedings of the International Conference Machine Learning (ICML), pp. 8546-8555. Virtual, 2021.
F. Petersen, C. Borgelt, H. Kuehne, and O. Deussen. Monotonic differentiable sorting networks. In Proceedings of the International Conference on Learning Representations (ICLR). Virtual, 2022.
I. Sutskever, O. Vinyals, and Q. V. Le. Sequence sequence learning with neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 27, Montreal, Quebec, Canada, 2014.
11

---

Published as a conference paper at ICLR 2024
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polo- sukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, pp.
Long Beach, California, USA, 2017.
O. Vinyals. S. Bengio, and M. Kudlur. Order matters: Sequence sequence for sets. In Proceedings of the International Conference on Learning Representations (ICLR), San Juan, Puerto Rico, 2016.
M. Zaheer, Kottur, S. Ravanbakhsh, B. Poczos, Salakhutdinov, and J. Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, pp. 3391-3401, Long Beach, California, USA, 2017.
H. Zhao, L. Jiang, J. Jia, Torr, and V. Koltun. Point transformer. In Proceedings of the Interna- tional Conference on Computer Vision (ICCV), pp. 16259-16228 Virtual, 2021.
12

---

Published as a conference paper at ICLR 2024
A OPTIMAL MONOTONIC SIGMOID FUNCTIONS
0.2
-30
-12
Figure 4: An optimal monotonic sigmoid function, which is presented in 7
We visualize an optimal monotonic sigmoid function in Figure
B
COMPARISONS OF DIFFERENTIABLE SWAP FUNCTIONS
Twin (or,0)
of
prine
mim (o.
maae (on. 30
10
300
110
350
200
#Ssspps
Swaaps
Figure 5: Comparisons of diverse DSFs in terms of the numbers of swap functions applied. Our error-fre free DSF does not change the original z and y, unlike other DSFs. We initially set = 4, for the left panel or x = 8, 0 for the right panel, where k #Swpps.
As depicted in Figure some sigmoid functions such as the logistic, logistic with ART, recipro- cal. Cauchy, and optimal monotonic functions suffer from the error accumulation problem; see the work (Petersen et al. 2022 for the details of such sigmoid functions. For the case of the Cauchy function, two values are close enough at the 9th step in the left panel of Figure (a and the 15th step in the right panel of Figure [5] we calculate the corresponding steps where difference between two values becomes smaller than 0.001.
C COMPARISONS OF DIFFERENT SORTING NETWORKS
Figure shows the comparisons of different sorting networks by varying sequence lengths. acCem and acCew are measured to assess the sorting networks.
D PROOF OF PROPOSITION 1
Proof. If two elements at indices i and j are swapped by a single swap function, [a = for k E [n]] (n). [P| where p is the output of sigmoid function, ie.. p = oly x) or = [o x) Since the multiplication of doubly-stochastie matrices is still doubly-stohasstic, Proposition iis true. n
0 for & # I, k. E fi. Pl [P] = and [P] = [P 1 p,
13

---

Published as a conference paper at ICLR 2024
08
0.6
Candly
Optinal
Ense
Figure 6: acCem (solid) and acCew (dashed), versus sequence lengths. Without mapping g from x to s, we uniformly sample n elements from [-10, 10), which are considered as ordinal scores s. Then, sort them using the respective sorting networks and measure accuracy the ground- truth permutation matrices computed by n elements. We repeat each experiment 10,000 times.
E PROOF OF PROPOSITION 2
Proof. Let min (xr v) and min (x,, y) be minimum and maximum values where swap with min and max is applied & times repeatedly. By Definition and min' the following inequalities are satisfied:
min and max max',
min( y) < min (z, v) < min (x, v) .... < min (x,
max" (z. y)
max (x. y) max (I, max(x,
(21)
under the assumption that V2o(z) O. By and [ạo(T) 0, we can obtain the following inequality:
0 max k+1 (x.z)= min k+1 (x, v) < max (z, v) min (I, y) max - (z. v) min (x: y)
(22)
Therefore, limg-+o max* (x, min (s,
0. and min't (x,, v) max* (I, v) if k -
To sum up, softening error for k + is (max(x y) min(x, w))/2 since max (x, 1) (min(x, y) + max(x, /) by (9). Note that the assumption Vzo(z) > 0 implies that (-)) is a strictly monotonic sigmoid function.
F PROOF OF PROPOSITION 3
Proof. According to Definition ! given and y, the softening error x' - -min(r, y) is expressed as the following:
min(x, y) = (min(x, y) min(x,8) vi) og + min (z, y) min min(x,
m2, y) min(x, 8) (a, y) min(x,y)
0.
(23)
while forward pass is applied. The proof for max(x; (r. y) y is omitted because it is obvious.
G DETAILS OF PERMUTATION--QUIVAAAAN NETWORKS WITH MULTI-HEAD ATTENTION
Figure illustrates the Transformer- based permutation-equiivrrian network, which implemented with multi-head attention (Vaswani et al.) 2017). For the sake of brevity, this illustration briefly depicts our permutation-equivarian network without detailing the specifics the Transformer net- work. Each instance in sequence is first processed by a feature extractor, i.e., a convolutional neural network. Then, a sequence of latent vectors is provided into the Transformer network with- out positional encoding. At each multi-heat attention module, each latent vector is updated by the aggregation of the latent vectors given where the aggregation is determined by the operations ex- plained in Section 4 and (6).. After passing through multiple layers of multi-head attention and the
14

---

Published as a conference paper at ICLR 2024
$2
83
Malhi-ieul
xL
4
FE
FE
FE
FE
FE
373
9993
2432 2
Figure 7: Simple illustration of our permutation-equivariinn network with multi-head attention. For the sake of brevity, we do not depict the details of multi-head attention, layer normalization, and feed-forward networks. Note that FE stands for a feature extractor.
corresponding components such as layer normalization and feed-forward neural networks, the final fully-connected layer is applied to transform the outputs of the Transformer network into score vector s. The details of the Transformer network can be found in the work by Vaswani et (2017).
H SPLIT STRATEGY TO REDUCE THE NUMBER OF POSSIBLE PERMUTATIONS
1
0
1
0
4
3
0
0
1
7
4
1
0
0
7
0
0
0
9
9
0
0
0
3
0
splic
4
0
0
7
7
1
0
3
9
3
Figure 8: split process of P.
As presented in 14 and Proposition the permutation matrix for the error-free DSF a discretized doubly-stochastic matrix, which is denoted Phard, in forward pass, and is differentiable in backward pass. Here, we show an interesting proposition of P hard:
Proposition Let s E R" and hard E gu be an unordered sequence and the corresponding permutation matrix transform it Su, respectively. We able split to subsequences 81 E R and $2 E I2 where $1 = [s]1:n and $2 (s)m+timnttn Then, P Paar is also split to P Ruixai and P2 E Ro2xn2, so that P1 and Pa are (discretized) doubly-stochastic.
Proof. A split does not change the relative order of elements in the same split and each entry in the permutation matrix is zero or one, so that permutation matrix can be split as shown in Figure g Moreover, multiple splits are straightforwardly doable.
In contrast to Phard it is impossible to split Psof to sub-block matrices since such sub-block ma- trices cannot satisfy the property of coubly-stochasee Importantly, Proposition Aodes not show a possibility of the recoverable decomposition of the per-
matrix, which is discussed in Proposition I
mutation matrix, which implies that cannot guarantee the recovery of decomposed matrices
15

---

Published as a conference paper at ICLR 2024
the original matrix. Regardless of the existence of recoverable decomposition, attempt to reduce the number of possible permutations with sub-block matrices, rather than holding the large number of possible permutations with the original permutation matrix. Therefore, by Proposition 4 relative relationships between instances with a smaller number of possible permutations are more distinc- tively learnable than the relationships with larger number of possible permutations, preventing sparse correct permutation among a large number of possible permutations.
I DETAILS OF ARCHITECTURES
We describe the details of the neural architectures used in our paper, as shown in Tables 6
8 P 10
12
13 and [4 For the experiments on sorting image fragments, we omit some of
the architectures employed for particular fragmentation, since they follow the same architectures presented in Tables II
12 13 and 14 Only differences are the sizes of inputs, and therefore the respective sizes of the first cullycconnccedd layers change.
Table 5: Architecture of the convolutional neural networks for the four-digit MNIST dataset.
Layer
Input & Output (Channel) Dimensions
Kernel Size
Details
Convolutional
32
strides padding 2
ReLU
Max: pooling
pooling strides
Convolational
32 64
5 5
strides I, padding 2
RcLU
Max-pooling
pooling strides
Fully-connectee
12544 x 64
ReLU
Fully- colleceddeeet
64 x
Table 6: Architecture of the Transformer- Small models for the four-digit MNIST dataset.
Layer
Input & Output (Channel) Dimensions
Kernel Size
Details
Convolutional
32
strides padding
ReL.U
Max-pooling
pooling strides 2
Convolational
32 x 64
5 5
strides padding
ReLU
Max pooling
pooling strides 2
Fully-connected
12544 x 16 16 x
Transformer Encuter
#layers Wheads
Rel. U
Pully-oonnected
16
Table 7: Architecture of the Transformer-Large models for the four-digit MNIST dataset.
Layer
Input & Output (Channel) Dimensions
Kernel Size
Details
Convolational ReLU
1 x 32
5
strides padding
Max-pooling
posling strides 2
Convolational
32 x 64
x 5
strides padding 2
ReLU
Max: paa-ppooing
pooling 2, strides 2
Fully-sonnected
12544 61 x 641
Transforner Encodor
#layers 8, #heads 8
ReLU
Fully connected
64
J DETAILS OF EXPERIMENTS
As described in the main article, we use three public datasets: SVHN (Netzer et al., 2011), and CIFAR-10 (Krizhevsky & Hinton 2009). Unless otherwise spec-
MNIST (LeCun et al.] 1998),
16

---

Published as a conference paper at ICLR 2024
ified, learning rate 10-3.6 is used for the CNN architectures and learning rate 10 is used for the Transformer-based architectures; see our implementation for the exact learning rates we utilize in the experiments. Learning rate decay is applied by multiplying 0.5 in every 50,000 steps for the experiments on sorting multi-digit images and every 20,000 steps for the experiments on sorting image fragments. Moreover, balance two objectives for Pardd and soft by multiplying 1, 0.1, 0.01, or 0.001; see our implementation for the respective values for all the experiments. For random seeds, we pick five random seeds 42, 84, 126, 168, and 210 for all the experiments; these values are picked without any trials. Other missing details can be found in our implementation. Furthermore, we employ several commercial NVIDIA GPUs, i.e., GeForce GTX Titan Xp. GeForce RTX 2080, and Geforce RTX 3090, in the experiments.
K STUDY ON BALANCING HYPERPARAMETER
We conduct study on balancing hyperparameter in the experiments on sorting the four-digit MNIST dataset, as shown Table 15 For these experiments, we use steepness 2, 14, 23, 38, 25, and 124 for sequence lengths 3, 5, 7, 9, 15, and 32, respectively. Also, we use a learning rate 10-3 and random seeds 42, 84, 126, 168, and 210.
L STUDY ON STEEPNESS AND LEARNING RATE
We present studies on steepness and learning rate for the experiments on sorting the multi-digit MNIST dataset, as shown in Tables 16
18 19 20 and 2T] For these experiments, random seed 42 is only used due to numerous experimental settings. Also, we use balancing hyperparameters À as 1.0, 1.0, 0.1, 0.1, 0.1, and 0.1 for sequence lengths 3, 5, 7, 9, 15, and 32, respectively. Since there many configurations of steepness, learning rate, and balancing hyperparameter, we cannot include all the configurations here. The final configurations we use in the experiments described in implementation. As widely known in the deep learning community, a learning rate should he set as value around 10-3 Moreover, according our empirical analyses, steepness should generally be higher as sequence length is longer.
M LIMITATIONS
While a sorting task is one of the most significant problems in computer science and mathemat- ies (Cormen al., 2022), our ideas, which are built on sorting networks (Knuth) 1998: Ajtai al, 1983), can be limited to sorting algorithms. It implies that it is not easy to devise neural network- based approaches to solving general problems in computer science, e.g., combinatorial optimization, which are inspired by our ideas.
In addition, while our proposed methods show the superior performance compared to the baseline methods, this line of research suffers from performance degradation for longer sequences as shown in Tables [ 2 and More precisely, for longer sequences, the element-wise accuracy does not de- cline dramatically, but the sequence- wise accuracy significantly drops due to the nature of sequences. Incorporating our contributions such as the error- free DSFs and the Transformer based networks, we expect that the further progress of neural network- based sorting networks can be achieved. In partic- ular, the consideration of more sophisticated neural networks, which are capable of handling longer sequences, might help improve performance. This will be left for future work.
Our frameworks successfully learn relationships between high-dimensional data with ordinal con- tents as shown in Section [5] However, we suppose that our methods might fail in sorting data without ordinal information; the elaborate discussion on this topic can be found in Section 7 In order to sort more ambiguous high-dimensional data, we can combine our work with part- based or segmentation based approaches.
17

---

Published as a conference paper at ICLR 2024
Table 8: Architecture of the convolutional neural networks for the SVHN dataset.
Layer
Input & Outpul (Channel) Dimensions
Kernel Size
Details
Convolational
3 x 32
5 5
strides 1. padding 2
ReLU
Max. Max-pooling
pooling 2, strides 2
Convolational
strides padding 2
ReL.U
Max-pooling
pooling 2, strides
Convolutional
641
strides padding 2
ReLU
Max: pooling
pooling strides
Convolational
128 256
5 x 5
strides I, pacding 2
ReLU
Max: pooling
pooling strides
Pully-connectdd
2304 x 64
RcLU
Fully conneccd
64 x
Table 9: Architecture of the Transformer- Small models for the SVHN dataset.
Layer
Input & Output (Channel) Dimensious
Details
Convolutional
3 x 32
x 5
strides padding
ReLU
Max paoling
pouling 2, strides 2
Convolational
32
5
strides padding
RcLU
Max-pooling
pooling strides strides padding
Convolutional
64 x 64
5
ReLU
Max: Max-pooling
posling strides 2
Convolational
64 x 128
5 x 5
strides paddingg 2
ReLU
Max-pooling
pooling 2. strides 2
Fully-sonnected
1152 x 32
Transfonnce Encoder
32 x 32
#layers 6, #heads 8
ReLU
Fully connected
32
Table 10: Architecture of the Transformer-Large models for the SVHN dataset.
Layer
Input & Output (Channel) Dimensions
Kernel Size
Details
Convolutional
3 32
strides padding
ReL.U
Max paoling
pooling strides 2 strides padding
Consolational
32 64
5
RcLU
Max- Mlax-pooiing
pooling strides strides padding 2
Convolational
64 x 128
x 5
Max-pooling
pooling strides 2
Convolational
128 x 256
5 x 5
strides padding 2
ReLU
Max-pooling
pooling 2. strides 2
Fully-sonnected
2304 64 64 x 64
Transforner Encoder
#layers 8, theads 8
ReL.U
Fully-coanocted
61
18

---

Published as a conference paper at ICLR 2024
Table 11: Architecture the convolutional neural networks for the MNIST dataset of image fragments of size 14 x 14.
Layer
Input & Output (Channel) Dimensions
Kernel Size
Details
Convolational
x 32
3 x
strides 2, pudlligg
ReLU
Convolational
32 64
strides 2. pucding I
ReLU
Pully-connected
1024
RcLU
Fully-soanected
Table 12: Architecture of the Transformer models for the MNIST dataset of image fragments of size 14 14.
Layer
Input & Output (Channel) Dimensions
Convolational
1 x 32
x 3
strides padling
ReL.U Convolational
32 x 32
x 3
strides 2, pudding
Fully-oonnecred
512 16 16 x
Transforner Eucoder
#layors #heads 8
ReLU
Fully-comnected
Table 13: Architecture of the convolutional neural networks for the CIFAR-I0 dataset of 4 image fragments of size 16 16.
Layer
Input Output (Channel) Dimensions
Kernel Size
Details
strides 2, pudding
ReL.U Convolutional ReLU Pully-connected
strides 2, padding
1024 x 64
RcLU
Fully- colleceddeetted
64 x
Table 14: Architecture of the Transformer models for the CIFAR-10 dataset of 4 image fragments of size x 16.
Layer
Input & Output (Channel) Dimensions
Kernel Size
Details
Convolational ReLU Convolutional
3 32
3
strides padding
32
strides padding
ReLU
Fully connecte
Transformer Encoder
16 16
#layers #heads 8
ReLU Fully-connected
16
Table 15: Study on a balancing hyperparameter À in the experiments on sorting the four-digit MNIST dataset.
Sequence Length
X
32
1.000
94.8 (96.4)
86.9 (94.1)
74.2 (90.9)
62.6 (88.6)
(88.688.6)
12.0 (69.4)
0.0 (38.9)
(96.5)
(94.2)
(91.3)
(83.3)
(69.2)
0.010
95.1 (96.6)
87.1 (92.7)
(91.2))
63.5 (88.8)
33.2 (82.7)
0.7 (60.7)
0.001
95.2 (96.7)
(94.1
76.6
64.8 (89.2)
32.9 (82.7)
0.5 (61.5)
0.000
94.9 (96.5)
87.2 (94.2)
(9.55
64.4 (89.1)
34.1 (83.2)
0.9 (60.6)
19

---

Published as a conference paper at ICLR 2024
Table 16: Study on steepness and learning rate for sequence length 3. Ir stands for learning rate.
Steepuess
logn
10
12
-4.0
89.2 (92.6)
91.5 (94.2)
92.1 (94.6)
92.3 (94.7)
92.7 (95.0)
92.1 (94.6)
92.7 (95.0)
(95.5)
(95.5)
(96.2)
93.9 (95.9)
(464(96.1)
94.5 (96.2)
-3.0
95.3 (96.8)
95.1 (96.6)
95.0
94.4 (96.2)
94.3 (96.1)
94.7 (96.4)
94.8 (96.5)
-25
94.5 (96.2)
94.3 (96.1)
93.7 (95.6)
93.8 (95.7)
93.7 (95.7)
93.7 (95.6)
94.1 (95.9)
Table 17: Study on steepness and learning rate for a sequence length 5. Ir stands for learning rate.
Steepness 20
Jog
16
18
22
24
26
-4.0
78.3 (90.2)
76.3 (89.3)
79.5 (90.9)
78.7 (90.4)
78.4 (90.4)
77.3 (89.8)
79.0 (90.6)
-3.5
85.1 (93.3)
83.6 (92.7)
84.8 (93.1)
85.5 (93.5)
83.4 (92.5)
85.6 (93.6)
84.1 (92.8)
(94.1)
(93.3)
(93.8)
(93.6)
85.4 (93.5)
(93.3)
-2.5
83.1 (92.3)
83.2 (92.4)
83.1 (92.4)
81.7 (91.8)
83.3 (92.5)
82.4 (92.1)
82.5 (92.1)
Table 18: Study steepness and learning rate for sequence length 7. Ir stands for learning rate.
Steepness 29
log Ir
33
35
(82.9)
(84.)
61. (86.0)
58.3 (85.1)
(88.0)
$7.3 (84.6)
(86.4)
.3.5
71.6 (90.0)
73.5 (90.)
68.1 (88.6)
72.9 (90.5)
72.2 (90.2)
71.4 (89.9)
74.2 (91.0)
74.4 (90.9)
(90.4)
74.2 (90.8)
69.2 (89.0)
69.9 (89.3)
73.0 (90.4)
73.0 (90.5)
68.0 (88.6)
(88.1)
(88.6)
64.5 (86.9)
66.8 (88.0)
70.4 (89.3)
66.2 (87.9)
Table 19: Study steepness and learning rate for sequence length Ir stands for learning rate.
Steepness 32
logm
30
34
36
38
-4.0
(77.7)
37.8 (79.7)
37.3 (79.4)
45.9 (83.0)
46.4 (83.1)
36.2 (78.9)
45.3 (82.5)
(84.8)
(87.5)
(87.5)
(88.2)
(88.1)
54.6
-3.0
62,5 (88.8)
60.5 (88.0)
61.8 (88.4)
63.2 (88.9)
61.5 (88.2)
62.2 (88.6)
65.0 (89.5)
-2.5
57.4 (86.8)
58.7 (87.2)
56.5 (86.4)
55.3 (86.1)
52.8 (85.0)
46.9 (82.1)
52.1 (84.6)
Table 20: Study on steepness and learning rate for a sequence length 15. Ir stands for learning rate.
Steepness 25
log
19
21
23
27
29
31
..0
3.6 (62.7)
(67.6)
4.9 (64.8)
2.6 (60.9)
2.9 (.1.)))))
2.5 (60.2)
6.8 (68.3)
-3.5
10.3 (71.5)
11.9 (73.0)
7.6 (68.6)
22.3 (78.7)
7.1 (68.7)
8.2 (69.6)
10.6 (71.8)
(82.7)
23.9 (79.9)
31.6
-2.5
30.5 (81.4)
28.2 (80.0)
18.98)6.8)
29.8 (80.9)
19.8 (77.8)
(75.4)
24.6 (79.6)
Table 21: Study on steepness and learning rate for a sequence length 32. Ir stands for learning rate.
Steepness 124
log,n Ir
120
122
126
128
130
0.0 (46.4)
0.0 (45.8)
0.0 (46.4)
(43.1)
0.0 (42.9)
0.0 (49.4)
0.0 (48.9)
-3.5
0.2 (60.5)
0.3 (61.8)
0.7 (64.8)
0.3 (62.7)
0.0 (56.0)
0.3 (62.7)
0.2 (59.8)
0.6 (63. 1)
0.5 (63.6)
0.4 (59.8)
0.8 (65.8)
0.2 (58.1
D.1 (56.0)
(57.1)
-2.5
0.5 (62.8)
0.5 (62.3)
0.5 (62.5)
0.1 (58.3)
0.3 (61.2)
(59.5)
0.2 (58.1)
20

---

Published as a conference paper at ICLR 2024
N ADDITIONAL DISCUSSION
challenging to directly sort a sequence of generic data instances without using auxiliary net- works and explicit supervision. Unlike earlier sorting methods, this sorting network-based re- search (Petersen et al. 2021; 2022) including our work ensures that we can train a neural network that predicts numerical scores and eventually sorts them, even though we do necessitate access- ing explicit supervision such as exact numerical values of the contents in high-dimensional data. In this sense, the practical significance of our proposed methods can be highlighted by offering this possibility of solving sorting problem with high-dimensional inputs. For example, as shown in Section [] we can compare images of street view house numbers using the sorting network where neural network is trained without exact house numbers.
Moreover, instead of using costly supervision, our networks allow us to sort high-dimensional in- stances in sequence where information on comparisons between instances is only given. This scenario often occurs when we cannot obtain complete supervision. For example, if we would sort four-digit MNIST images, ordinary neural networks designed solve classification task by predicting class probabilities each of which indicates one of all labels from "0000" to "9999". some labels missing and further do not know the exact number of labels, they might fail in predicting unseen data corresponding to those labels. Unlike these methods, it is possible to solve sorting problems using our networks such a scenario.
Furthermore, this study can be applied in diverse deep learning tasks for learning to sort generic high-dimennional data, such as information retrieval (Cao et al., 2007 Liu 2009) and top-k classi- fication (Berrada et al. 2018).
21


Reviews:
[{"review_id": "EloHK7HyzU", "reviewer": "Reviewer_LP9f", "summary": "The main content of the paper is the proposal of a generalized neural sorting network with error-free differentiable swap functions. The authors introduce scaled dot-product and multi-head attention and provide proofs for several propositions related to their network. They also discuss the effects of multi-head attention in the problem they are addressing and present empirical studies on the performance gains achieved by their proposed methods.", "questions": "1. I hope the author can provide a detailed explanation of the practical significance of this work.\n\n2. Why does the performance drop significantly when the quantity increases?", "limitations": "", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Generalization: The proposed neural sorting networks with error-free differentiable swap functions provide a general framework for solving sorting tasks on various types of data, including multi-digit images and image fragments.\n\n2. Performance Improvement: The experimental results demonstrate that the proposed methods outperform the baseline method in terms of sorting performance, as measured by accuracy metrics.\n\n3. Numerical Analysis: The authors provide a thorough numerical analysis of the effects of their methods, compared to the baseline method. This analysis validates the effectiveness of the proposed methods in sorting tasks.\n\n4. In terms of writing, it is explained quite clearly, and one can generally follow the author's train of thought.", "weaknesses": "1. Since the methods proposed in the paper are based on sorting networks, they are not applicable to solving general problems in computer science, such as combinatorial optimization. This implies that it may not be easy to devise a neural network-based approach for solving these types of problems using the ideas presented in this work.\n\n2. In terms of the results, it can be observed that as the sequence length increases or the number of segments grows, the performance decreases significantly.\n\n3. I find it somewhat challenging to grasp the practical significance of this work. I believe that this work lacks practical significance to some extent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WLCaKRn9Vl", "reviewer": "Reviewer_Stfx", "summary": "The paper introduces a new approach to sorting through neural networks. The authors extend traditional sorting mechanisms to handle more abstract and high-dimensional data types like multi-digit images and image fragments. The core contribution is an \"error-free differentiable swap function,\" which allows the network to learn a mapping from complex inputs to sorted sequences effectively. This work aims to broaden the applicability of sorting algorithms by making them more versatile for dealing with intricate data types.", "questions": "How sensitive is the model's performance to the choice of hyperparameters like steepness and learning rate? Could the authors provide more insights into this?\nCould the authors provide a more comprehensive discussion on the limitations of their approach, particularly in terms of scalability and conditions where the method may not be applicable?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Novelty: The paper introduces a novel \"error-free differentiable swap function\" to generalize sorting algorithms for more complex data types.\n- Mathematical Rigor: The paper employs rigorous mathematical formulations to define the sorting problem and its extension for high-dimensional data.\n- Methodological Approach: The use of a permutation-equivariant Transformer network with multi-head attention is a strong methodological choice for capturing dependencies between elements in the sequence.\n- Clarity and Organization: The paper is well-organized and clearly written, making it accessible to readers who are familiar with the domain.", "weaknesses": "- Insufficient Discussion on Limitations: While the paper mentions that its methods are limited to sorting algorithms, it doesn't provide a thorough discussion on other potential limitations, such as scalability or conditions under which the method may not work well.\n- Hyperparameter Sensitivity: The paper discusses various hyperparameters like steepness and learning rate but does not provide a comprehensive analysis of their impact, which could be a concern for practical implementations.\n- Complexity of the Model: The use of a permutation-equivariant Transformer network with multi-head attention could make the model computationally expensive, which is not addressed in the paper.\n- Missed Opportunity for Theoretical Analysis: While the paper is empirically driven, a more in-depth theoretical analysis could strengthen the paper by providing bounds or guarantees on the performance of the proposed methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1KSEqY8jM8", "reviewer": "Reviewer_rtfd", "summary": "This paper examines an error-free differentiable swap function, which enables the creation of trainable sorting networks which do not accumulate errors as multiple applications of this function are performed. The authors evaluate the sorting network created using their swap function, and demonstrate improvements over previous differentiable sorting techniques.", "questions": "As mentioned above, I would be grateful if the authors could clarify the paragraph “Utilization of Hard Permutation Matrices” of Section 7.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The proposed method is simple and easy to understand. The function used is equivalent to using the soft version of the maximum / minimum functions during the backward step, and the exact functions during the forward step. This allows for differentiability, without accumulating errors.  I especially appreciated the presentation of the samples in Figure 3, as it helped me understand how the method precisely works.\n\n- The authors perform experiments on a variety of architectural choices and sequence lengths, which affect the accuracy of sorting algorithms. They show how incorporating an attention based part in the architecture is the better choice for sorting large sequences of data, since it provides a way to incorporate the entire sequence of data to sort and contextualize the output for each sample.", "weaknesses": "- Overall, while interesting, the applicability of the method seems limited at first glance, since one can in principle learn the function that maps samples to ordered objects first and then perform the sort using standard methods. I believe that the authors should either better motivate the need for this sort of method, or demonstrate in their experiments why learning the ordinal value directly does not perform as well.\n\n- I think there is a gap in the proof of Proposition 2. Namely, the fact that the soft minimum and the soft maximum are the same as $k \\to \\infty$ seems like it is missing a step in how it is derived. I believe that it should hold, given the differentiability of the function, but filling in the missing step here is needed.\n\n- I believe that certain parts can be improved with respect to the clarity of the paper. More specifically:\n\n  - It seems to me that the paper assumes that the function used to soften the maximum is the sigmoid, and some of its properties are listed in Section 2 - however, it is not clear if the sigmoid is the only choice, or if these properties are sufficient for a function to satisfy. I would appreciate it if the authors could clarify this point.\n\n  - Again in Section 2, I had some trouble understanding the wire-based construction of the permutation matrix, especially since the associated Figure is in the Appendix. I believe that the point of the authors would be clearer if they moved the Figure in the main paper, as well as simplify the explanation for the construction (saying, e.g., that each wire is a step to fix a single wrong ordering, and iterative application of these steps results in a sorted set).\n\n  - I believe that Figures 1 and 2 can be simplified / combined, since they are essentially showing similar things - namely, that the function is error-free, which is not surprising given that it is not softened during the forward pass.\n\n  - In Section 7, the paragraph “Utilization of Hard Permutation Matrices” is not very clear to me. I would appreciate it if the authors could rephrase the point they are trying to make here.\n\n- As a minor point, in Section 6, the authors should rephrase how they refer to previous works, for example: “The work (Petersen et al., 2021) has suggested …” -> “Petersen et al. (2021) have suggested…”.\n\nOverall, I think this is an interesting work, but I believe that the authors should improve upon the clarity of the paper and the motivation of their technique.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZAfJO9KsFf", "reviewer": "Reviewer_M9Vx", "summary": "The authors investigate the properties of differentiable swap functions for neural sorting. They conclude that the existing methods shrink the difference between different elements at each application of the swap function. This has a negative effect on the performance of such networks. To alleviate this problem, the authors propose an Error-Free Differentiable Swap Function, based on the straight-through estimator. Also, they propose to use transformers without positional encodings for processing the raw inputs before they are fed to", "questions": "Why are the results on 4-digit MNIST with a seq length of 32 significantly better in Tab 1 than in Tab 15?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Simple method\n- Better performance on long sequences\n- Motivated by analyzing existing methods", "weaknesses": "- No clear distinction between the Transformer-based network vs the differentiable swap function. These are two orthogonal changes, and the Transformer seems to have much more performance impact than the swap function itself. Yet, the paper focuses mostly on the swap function.\n- The method uses both the soft and the hard sorting network for training. Also, Tab 15 shows that training with $\\lambda = 0$ has basically no effect on the quality of the trained network. As the standard deviations are not shown, it is unclear whether there is any effect here, but $\\lambda=1$ seems to hinder accuracy. This begs the question if the Error-Free Differentiable Swap Function has any contribution to training, or just during inference, in which case there is no need for the straight-through estimator. It would be worth evaluating the baseline Optimal Diffsort with hard min/max during inference, to see this.\n\nBased on the 2 points above, I'd like to see two sets of experiments:\n- the best optimal diff sort models with identical transformer architecture to those of the Error-Free DSF\n- The same architecture as the best Error-Free DSF with \\lambda=0 (thus, being equivalent to using hard min/max during inference, but being trained as \"Diffsort Optimal\")", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)