Non-Autoregressive Sentence Ordering
Authors: Yi Bin
WENHAO SHI
Bin Ji
Jipeng Zhang
Yujuan Ding
Yang Yang
Venue: EMNLP 2023 Findings (2023)
Keywords: sentence ordering
non-autoregressive transformer
TL;DR: This paper presents a non-autoregressive ordering network, which could leverage bilateral dependency. It also can integrate with other methods and makes marvelous improvements.

Abstract: Existing sentence ordering approaches generally employ encoder-decoder frameworks with the pointer net to recover the coherence by recurrently predicting each sentence step-by-step. Such an autoregressive manner only leverages unilateral dependencies during decoding and cannot fully explore the semantic dependency between sentences for ordering. To overcome these limitations, in this paper, we propose a novel Non-Autoregressive Ordering Network, dubbed \textit{NAON}, which explores bilateral dependencies between sentences and predicts the sentence for each position in parallel. We claim that the non-autoregressive manner is not just applicable but also particularly suitable to the sentence ordering task because of two peculiar characteristics of the task: 1) each generation target is in deterministic length, and 2) the sentences and positions should match exclusively. Furthermore, to address the repetition issue of the naive non-autoregressive Transformer, we introduce an exclusive loss to constrain the exclusiveness between positions and sentences. To verify the effectiveness of the proposed model, we conduct extensive experiments on several common-used datasets and the experimental results show that our method outperforms all the autoregressive approaches and yields competitive performance compared with the state-of-the-arts. The codes are available at: \url{https://github.com/steven640pixel/nonautoregressive-sentence-ordering}.

Non-Autoregressive Sentence Ordering
Yi Bin', Wenhao Shi', Bin Ji', Jipeng Zhang', Yujuan Ding', Yang Yang'
'University of Electronic Science and Technology of China, "National University of Singapore The Hong Kong university of Science and Technology, "The Hong Kong Polytechnic University yi.bin @ @hotmail.com jibin @ @us..edu.sg
(shiwenhaol6, zip1111299782, dingyujuan385, dlyyang) @ gmail.com
Abstract
Unordered Sentenees
Coherent Paragraph
15, poured henella glass.
52. opened up bottle grape juice.
Existing sentence ordering approaches gener- ally employ incoder-decoder frameworks with the pointer net to recover the coherence by re- currently predicting each sentence step-by-step. Such an autoregressive manner only leverages unilateral dependencies during decoding and cannot fully explore the semantic dependency between sentences for ordering. To overcome these limitations, in this paper, we propose novel Von-Auvereeresssive Ordering Network, dubbed NAON, which explores bilateral depen- dencies between sentences and predicts the sen- tence for each position in parallel. We claim that non-auvoregressive manner is not just applicable but also particularly suitable the sentence ordering task because of two pecu- liar characteristics of the task: 1) each gen- eration target is in deterministic length, and 2) the sentences and positions should match exclusively. Furthermore, address the rep- etition issue of the naive non -attuurrrrrrssvve Transformer, we introduce an exclusive loss to constrain the exclusiveness between positions and sentences. To verify the offectiveness of the proposed model, we conduct extensive experi- ments several common-used datasets and the experimental results show that our method out- performs all the autoregressive approaches and yields competitive performance compared with the state-of-the--rts The codes are available at: httpp://giis thub. com/ stpeeee400piielll nonautoregressivee sentence- ordering.
52, opened up bottle grape juice.
She poused a glass.
The carpet
Accidentally spilled some.
S4, Accidenially she spilled
carpet was
just hud cell jUio.
S8, Kelki just had call the cleaners.
Figure 1: An example of sentence ordering sourced from SIND dataset. The goal of sentence ordering is to understand the semanties and logic of of unordered sentences (the left box), and reorganize them to coher- ent paragraph (the right box).
sophisticated designs are costly in labor and time, expertise-rqquired, and even cannot be well gen- eralized to other scenarios. In the past couple of years, inspired by the great success of deep learn- ing, dozens of deep neural methods for sentence ordering have been proposed and achieved great success (Cui et al., 2018; 8; Kumar et al., 2020; Wang and Wan, 2019; Prabhumoye et al., 2020; Basu Roy Chowdhury al., 2021).
There exist two paradigms of neural sentence or- dering: 1) ranking model via the scores of relative positions between paired sentences, and 2) genera- tion model based on an encoder-decoder framework to predict the sentence order with sequence genera- tion. The former one, ranking model (Prabhumoye et al.. 2020; Chen et al., 2016), starts from calcu- lating score for each sentence pair to indicate their relative position in coherent paragraph, then employs ranking or searching strategies derive out the gold order. Since the score between paired sentences only measures the one-to-one relative po- sition, which may fail to capture the one-to-many interactions on the global context level. Besides, the naive ranking process is somehow brute-force and time-consuming, and highly depends on the quality of sentence representation.
1 Introduction
Sentence ordering is one of the fundamental and common tasks to model document coherence, which targets at re-organizing a set of sentences into a coherent paragraph (as shown in Figure 1). Most early works of sentence ordering (Lapata, 2003; Barzilay and Lee, 2004; Barzilay and Lap- ata, 2008) apply probabilistic transition model and rule-based model, e.g., HMM, entity, and content
The latter one, generation model regards sen- tence ordering as sequence prediction problem to explore the relations between sentences and posi- tions, which takes a set of sentences and generates
model, based on hrnd-crafted features. While such

---

the coherent sentence sequence. At the early stage, several encoder-decoder based approaches (Gong et al., 2016; Logeswaran et al., 2018) treat the un- ordered input sentences as a permutation sequence and encode them sequentially. Such sequential modeling encodes incorrect sentence order and se- mantic logic between sentences, which may mis- lead the decoder to predict incoherent paragraph. Specifically, with sequential modeling, different permutations of the same paragraph may derive dif- ferent paragraph representations and result in differ- ent output sentence order, which is not reasonable and inconsistent with the intuition of humans. To address this issue, Cui et al. (2018) first propose a deep attentive sentence ordering network equipped with self-attention to learn a reliable and consistent paragraph representation. Their model implements order-independent encoding with non-positional variant of Transformer (Vaswani al., 2017), but still predicts sentences via pointer network as most previous works do. Nevertheless, the RNN- based pointer networks predict the sentence order step-by-step by-step, which only explores the unilateral dependencies with past predictions and fails to leverage the comprehensive bilateral interactions between sentences for ordering.
the sentence for each position utilizing pointer network (Vinyals al., 2015). In particular, we first employ multi-head attention to explore the relations between positions. Then the output dis- tribution over the original sentence representation set for each position will be modelled by a pointer network. As mentioned in (Gu et al., 2018), naive non-autoregressive decoding suffers from severe problem of output repetition due to the complete conditional independence. To address this issue, we elaborate an exclusive loss constraining the ex- clusiveness between each sentence and position pair during training, and a greedy selective and re- moving strategy for inference. In summary, our main contributions are as follows:
We propose novel approach, non-autoregressive ordering network (NAON), for sentence order- ing, which implements self-attention explore the bilateral interactions between sentences, go- ing beyond the unilateral dependencies of RNN- based step-by-step decoding. To the best of our knowledge, our approach is one of the first at- tempts using non-autoregressive decoders for the sentence ordering problem.
To alleviate the repetition problem of vanilla non- autoregressive models, we design an exclusive loss under the implication of exclusive constraint between positions and sentences during train- ing. For inference, we simply design a greedy selective and removing strategy to match each sentence-position pair.
To overcome the above limitations, in this paper, we propose novel Non-Autoregressive Ordering Network, dubbed NAON, which explores the bi- lateral dependencies between sentences and pre- diets the sentence for each position in parallel. Specifically, our NAON consists of a basic sen- tence encoder, an order--nnependent contextual sentence encoder and non-autoregressive Trans- former (NAT) (Gu et al., 2018) decoder. We first employ sequence encoder, e.g., BERT in this work, to map discrete words in each sentence to compact representation. The obtained sentence rep- resentations are injected a Transformer (Vaswani et al., 2017) encoder exploit the interaction and relation between sentences, and export contextual sentence representations. Note that we remove the positional embedding in the Transformer to achieve the invariinar encoding for the sen- tences. In contrast to obtaining the paragraph rep- resentation via pooling initialize the memory of auto-regressive decoder (Cui et al., 2018), we make full use of contextual sentence representations through multi-head attention in non-autoregreessive decoder. We design a non non-autoren aonaauoorerrsssvve decoder (NAD) that takes positions as input and predicts
Extensive experiments are conducted on several common-usee datasets, and the results demon- strate the effectiveness of the proposed approach.
2
The Proposed Approach
2.1
Preliminary
Sentence ordering aims to capture the coherence and recover the gold order of a set of unordered sentences. Specifically, given a sentence set S {81, 82, ..... sN. with N sentences, and each sen- tence 8; = [wi W12: .... W.L,] contains sequence of I. words. The goal of sentence ordering is find an order O [oj oři,... .... o'yl conveying the coherent semantics, which can be modelled by:
P(O*[S) 2 P(OIS).VO e Ω
(1)
where P(O]S) is the probability of order given S, and Q denotes the exhaustive set of all potential

---

Input
KCLs)
57
?
Px
Basic Sentence Encoder
Taken
Embedding
Sug
Sogment Embedding
Multi-head Self-attention
Multi-head Attention
Positional
Fmmeedsingg
Forward
Multi- head Inter attentittnntin
BERT
Multi-head Attention
Pro traitrnned
Pointer Network
Feed Forward
Meon
Pooling
g
Basic Sentence Encoder
Contextual Sentence Encoder
Non-autoregressive Decoder
Figure 2:
The overall flowchart the proposed Non-Auutregressive Ordering Network (NAON), which consists of a basic sentence encoder, a contextual sentence encoder and a non-autoregressive decoder.
order with the size of A Existing autoregres- sive approaches (Cui et al., 2018; Wang and Wan, 2019) generate the coherent paragraph sentence- by-sentence to recover the gold order, and optimize the model by maximizing:
2018) provide a "paragraph representation" ini- tialize the hidden state and memory cell of the de- coder. A straightforward way is assuming that the given order is a "pseudo order" of the unordered sentences, and implementing an RNN-based en- coder (Wang and Wan, 2019), e.g., LSTM or GRU, to map sentence representations to dense feature vector for the paragraph. While such pseudo der assumption introduces incorrect sentence order, which may induce semantic incoherence and mis- lead the decoder in recovering the ground-truth order. To address this issue, Cui et al. (2018) pro- posed a deep attentive ordering network integrating self-attention mechanism to derive the order in- variant sentence representations, and adopted mean pooling across sentences to obtain the paragraph representation. Different from existing autoregres- sive approaches which need to initialize the decoder memory, our non-autoregressive decoder does not require such "paragraph representation". We de- sign contextual sentence encoder to interact each sentence with all the sentences in the set and injects all the contextual sentence representations into the decoder to find the correct order.
N
log P(s, (1s))(11,0 52. $)-1.S).
(2)
While non-autoregressive ordering network im- plements the optimization in parallel by maximiz- ing the logarithmic probabilities for all sentences:
log P(ss[S).
2.2 Basic Sentence Representation
To map discrete words of sentence into compact representations, as shown on the left of Figure 2, sequential encoder is first employed, e.g., an LSTM or BERT. Inspired by the success in language mod- cling of BERT (Devlin et al., 2019), we adopt a pre-trained BERT-base model for basic sentence representation. In particular, following previous work (Kumar et al., 2020), we concatenate the [CLS] token and word sequence BERT encoder input and average the outputs of all the tokens to denote the entire sentence representation. To make the representation more compatible with sentence ordering task, we also fine-tune it in an end-to-end fashion on each dataset.
Obviously, it is important to exploit semantic re- lations between sentences for recovering coherence. Towards this end, we design contextual sentence encoder, shown in the middle of Figure 2, to inter- act each sentence with other sentences. Specifically, after obtaining the basic sentence representations E {el, ..., ). employ a Transformer- based architecture similar to (Cui al., 2018), equipped with multi-heas head self-attention mechanism without the positional embedding, to exploit the
2.3 Contextual Sentence Representation
Most existing autoregressive approaches (Cui et al., 2018; Wang and Wan, 2019; Logeswaran et al.,

---

contextual information follows:
take the position information as input and predict the correct sentence for each position in parallel. Specifically, we follow previous work (Vaswani et al., 2017) to project each discrete position into a compact representation P via:
Attention (Q, V) = softmaxt QKT
V
(4)
vdg
MH(Q, K, V) = |H, H2, ... H,]W, H; AttentionnQW, v
(6)
Pt2j = sin sin(ii (1/1000000)//))))
(7)
To explore deep contextual interaction, we dupli- cate the multi-head self-attention block multiple times, e.g., 4 for NSF and arXiv datasets in this work. Finally, the contextual sentence representa- tions E {ei, e..... .... e'y can be derived from the output of the last layer.
Pi.2j cos(i/10000 2//44
(8)
where denotes the position and j is the j-th di- mension in pt- We then exploit the interaction and relative information between positions implement- ing multi-head self-attention as:
2.4 Non-Autoregressive Prediction
P = MHAU(PWS PW PWV),
(9)
Almost all the previous generation approaches (Lo- geswaran et al., 2018; Cui et al., 2018; Basu Roy Chowdhury et al.. 2021) adopt a recurrent- based architecture composing with a pointer net- work (Vinyals et al., 2015) to predict the ordered sentence step-by-step, which only leverages the unilateral dependencies with the past prediction, and cannot capture the coherent dependencies be- tween all the sentences. Besides, argued (Ben- gio et al., 2015), the discrepancy between training and inference of RNN-based generation strategy may decrease the inference performance. Inspired by the potentials of the non-autoregressive trans- former in neural machine translation, we devise non-autoregressive decoder (NAD) for recovering the correct order of sentences, with the exploration of bilateral dependencies. Our NAD is designed based on a Aon-eutoreeressive Transformer (NAT) decoder in machine translation, which removes the autoregressive connections between steps and generates all the target words in parallel, rather than step-by-step (i.e., wordd..-word). Beyond the aforementioned superiority of NAT in translation, NAD is especially suitable for sentence ordering from two aspects: (1) the length of the decoder is determined by the input of sentences, and (2) the sentences and positions match exclusively.
where MHAtt denotes multi-head self-attention block comprised of Equation 4-6. To connect the positions and the elements in the unordered con- text set, we further implement multi-head inter- attention between positions and sentences to ex- ploit the correlations between them. Specifically, query the contextual sentence representation set using P, to obtain the attentive representations of sentences as:
P(EST de
E = softmarl
E
(10)
where E is the contextual sentence representation derived from the contextual encoder. With such operation, the obtained E" now is position sensi- tive representation, and could be used select the most relevant sentence for each position. Specifi- cally, the probability of the sentence j to be in the position i can be obtained by:
Wij = n" tanh(W, + Wse)),
(11)
Ptr; = softmar(ws))
(12)
where W, are learned parameters, and is col- umn weight vector. dy and ep are the basic and positional sensitive representations of sentence j. Ptr, is the probabilistic distribution across all the sentences for i-th position.
As suggested in (Gu et al., 2018), different inputs of non-autoregressive decoder may lead to quite different outputs resulting in a remarkable perfor- mance gap. Thus it is crucial to choose a proper information source for the input of NAD. Towards this end, we meticulously adopt positional informa- tion as the input of our non-autoregressive decoder. Because the sentence ordering problem could be interpreted as matching the unordered sentences to the right positions, and it is straightforward to
2.5 Training and Inference
Training: Following previous ordering works (Cui et al., 2018; Chen et al., 2016), the entire model could be trained to maximize the coherence proba- bility by minimizing the cross entropy loss as:
N
L. log P(o θ),
(13)
N

---

cannot completely avoid repetition problem during decoding. Similar with the masking stralegy used in recurrent pointer networks, we introduce a sim- ple yet effective greedy selective and removing strategy to ensure the exclusive matching for in- ference. Given the probability distribution array, as described in Algorithm 1, the proposed strategy greedily selects the largest probability and returns its index indicating the matching position and sen- tence. then removes all the probability values of the corresponding column and row by setting them to zero. The process is repeated until all the values of the array are set to zero, which means that the matching process between positions and sentences is completely finished.
2 P
2
P
P
Decoder
0
0
22
0
Exclusive loss
0
0
0
0
1
S5
0
Truditional pointer loss
Figure Illustration of our proposed exclusive loss, which simultaneously constrain the sentence selection and position matching.
A Algorithm 1 Pseudo-code of greedy selective and removing a PyTorch-like style.
where 0j is the ground-truth sentence for given i-th position pi, and @ denotes all the learnable parameters in the model. As each sentence in the ordering problem is allowed to be selected only once, to avoid repeat selection, the RNN-based autoregressive model adopts mask to remove se- lected sentences (Yin et al., 2020). However, the non-autoregressiive model suffers from the repeti- tion problem for its parallel decoding fashion (Gu al., 2018). We have observed that the traditional pointer loss only penalizes the repetition for sen- tence choosing. Considering the characteristic of the ordering task, as depicted in Figure 3, every position should also choose one and only one sen- tence. Towards this end, we introduce an elegant exclusive loss to constrain the mutual exclusive- ness of optimal matching between positions and elements. Specifically, we simultaneously calcu- late two pointers for sentence choosing and position choosing when we obtain the pointer map by Equa- tion 11. Given the pointer map w, we implement softmax across column and row similar to Equa- tion 12, where the column one interprets choosing sentence for each position and the row one assigns position for each sentence. Then optimize the entire model by minimizing the combined exclu- sive loss follows:
# Ptr: N N output probability distribution amay of NAD INPUT Ptr
output =[]
while sum(Ptr)>O0:
www_ixx coLidx max indexx(((r)
# max max_index( ): get the index of the maximum value outputappendd(row idx, col_idx))
Ptr[row idx, =
Ptrf: col idx] 0
RETURN output
3 Experiments
To verify the effectiveness of our NAON, we con- duct extensive experiments on six datasets, and evaluate the performance with Ace, PMR, and т. More detailed experimental settings are described in the Appendix B.
3.1 Comparing with Baselines
As aforementioned, existing works lie in two cate- gories: ranking-based and generation-base meth- ods. To assess the proposed NAON, compare it with the recent state-of thettrrrt methods, including Pairwise model via pairwise ranking (Chen et al., 2016), RankTxNe via deep attentive ranking (Ku- mar et al., 2020), and B-TSort searching correct or- der with topological sort (Prabhumoye et al., 2020) of ranking model, and the first architecture using pointer network LSTM-Ptr (Gong et al., 2016), SetLSTM designing an LSTM based attention to process the set encoding (Logeswaran et al., 2018), AON with a deep attentive order invariant para- graph encoder (Cui et al., 2018), HAN equipped with hierarchical attention (Wang and Wan, 2019), 9), TGCM modeling guide coherence (Oh et al.,
Les Σ (log P(o.lp)) + log P(pilo:).
(14) Through such an exclusive constraint, the repetition problem could be distinctly alleviated. Inference: Obviously, the proposed exclusive loss

---

Table I: Comparison with baselines. The best and 2nd-best results are in bold and underlined. respectively. NAON-NE indicates no exclusive loss. Besides, we also take attempt at relative order exploration and BART enhancement, namely NAON-RO and BART-NAON respectively, and compare them with BERSON and RE-BART, listed the last two blocks in blue.
NIPS
AAN
NSF
arXiv
SIND
ROCStory
Model
Ace
PMR
7
Ace PMR
Acc
PMR
Acc
PMR
Ace
PMR
T
Ace PMR
Pairwise
33.43 0.66
LSTM-Pu
50.87
0.67
58.20
0.69
32.45
0.52
40.44 0.72
12.34 0.48
SetL. STM
51.55
0.72
58.06
0.73
28.33
0.51
AON
56.09
0.72
63.24
0.73
37.72
0.55
42.19 0.73
14.01 0.49
HAN
44.55 0.75
15.01 0.50
39.62 0.73
SE-Graph
57.27
0.75
64.64
0.78
44.33 0.75
16.22 0.52
En-Ptr
46.58
0.77
17.37 0.53
46,00 0.77
TGCM
59.43
31.44
0.75
65.16
36.69
0.75
42.67
22.35
0.55
58.31
44.28
0.75
38.71
15.18 0.53
RankTxNet
24.13
0.75
39.18
0.77
9.78
0.58
43.44 0.77
15.48 0.57
38.02 0.76
B-TSort
61.48
32.59
0.81
69.22
50.76
0.83
35.21
10.44
0.66
52.23
20.32
0.60
NAON-NE
63.37
32.13 0.79
68.33
45.87 0.80
40.88
12.86
0.63
63.12
45.71
0.77
51.40
18.45
0.58
74,45
52.68 0.8T
NAON
64.43
33.02
0.80
69.28
46.71 0822
41.82
13.68
0.64
64.50 46.82
0.79
52.38
19.13 0.60
75.89 53.36 0.82
BERSON
73.87
48.01
0.85
78.03
59.79 0.85
50.02 23.07 0.67 75.08 56.06
0.83 58.91 31.69 0.65 82.86 68 23 0.88
NAON-RO
74.15
48.03 0.85
78.22
59.81 0.86 50.39 23.11 0.67 75.16 56.12 0.83 59.04 31.71 0.66 83.07 68.31 0.88
RE-BART
77.41
57.03 0.89
84,28
73.50
0.91 50.23 29.74 0.76 74.28 62.40 0,86 64.99 43.15 0.72 90.78 81.88 0.94
NAON-BART
84.19 61.17 0.92
87.17 73.90
0.93 54.76 30.64 0.77 79.16 62.63 0.87 79.57 55.59 0.87 95.13 89.07 0.97
2019), SE-Graph encoding paragraph with sen- tence entities (Yin al., 2019), and En-Ptr en- hancing pointer network for sentence ordering with pairwise information (Yin et al., 2020) of genera- tion based strategy. The performance comparisons of different compared methods are illustrated in Table 1. We compare our method with the base- lines from several perspectives to analyze its per- formance comprchensively.
lowing (Cui et al., 2020), dubbed as NAON-RO. Furthermore, we report the performance of the ex- isting method BERSON, which also applics RO modeling. First, it is clear that NAON-RO and BERSON gain significant improvement, showing the effectiveness of RO modeling. Second, our NAON-RO performs better than BERSON exten- sively in terms of all the datasets and metrics. It demonstrates that with the enhancement of RO modeling, the non-autoregressive nature of our method is still superior to the autoregressive for the sentence ordering task.
General Comparison: Standard performances of different methods, including our NAON, are shown in Black in the table. First, comparing with generation-base based methods (e.g. AON, En-Ptr, and TGCM), our method is clearly better as it greatly outperforms them on four datasets and is almost competitive on the NSF dataset. In particular, our NAON achieves best 7 across all datasets, which suggests that it performs more like humans than other methods the metric shows consistency of models with human judgments (Kumar al., 2020). Second, compared with ranking-based methods, NAON outperforms most of them except B-TSort. However, B-T achieves slightly better performance than NAON mainly because of the relative order it takes advantage of, which also greatly increases computational costs.
Despite of the superb of the RO-enhanced model in terms of the ordering accuracy, we take the plain model as the standard NAON considering the com- putational or memorial cost, The time and space complexity both turn into ((N)) with the RO mod- eling. For example, it costs 12GB more memory to process a paragraph with more than 18 sentences and takes several days to train, and both costs will grow quadratically. Nevertheless, it still needs mention that RO modeling is one of the potential directions to boost the sentence ordering models by exploring relative dependency. We hope in the fu- ture more computation-frient be developed to this end.
algorithms would
Relative Order Exploration: Previous re- search has suggested that explicitly modeling the relative position of sentence pairs can bring consid- erably improve the sentence ordering models (Cui et al., 2020). Therefore, we further test our model with the boost of relative order (RO) modeling fol-
Suitable Pre-training Task and Model: En- hancing representations with effective pre-training process nowadays a general way to improve the performance of models for higher-level tasks. RE- BART (Basu Roy Chowdhury et al., 2021) applies the BART as the pre-training model for sentence

---

Table 2: Accuracy comparison of predicting the first and last sentences on arXiv and SIND.
AAN
ROCStory
99.46
99.97
ar
SIND
Model
662.18
63.65
head
tail
head
tail
Pairwise
84.85
62.37
32,92
LStM-Ptr
90.47
66.49
74.66
53.30
19.54
6.36
AON
91.00
68.08
76.00
54.42
SE-Graph
92.28
70.45
78.12
56.68
PRR
mSRR
PRR
mSRR
En-Ptr
92.76
71.49
78.08
57.32
NAON-NE
NAON
TGCM
92.46
69.45
78.98
56.24
Figure 4: Repetition evaluation for NAON with and
RankTxNet
92.97
69.13
80.32
59.68
without exclusive loss, which do not apply the selective and removing strategy during inference. Smaller value indicates less repetition.
NAON
93.92
72.58
81.47
61.82
BERSON
94.75
76.69
84.95
64.87
NAON-RO
94.83
76.71
84.98
64.91
RE-BART
96.46
80.62
87.97
73.02
tion still better than the last one. This implies that there may exist distinct signals in the first sentence, which indicates the important potential of exploit- ing such signals underlying sentences. Besides, the experiments of integrating NAON with BERSON and BART achieve similar and consistent results, further verifying the effectiveness of our NAON.
NAON-BART
98.98
85.91
90.10
80.99
ordering, which already includes the sentence per- mutation task the pre-training stage, and achieves excellent performance. Therefore, we also equip our aonr-utoreeressvve ordering strategy with the pre-trained BART model, namely NAON-BART, and examine its effectiveness. As the results shown in the last two blue rows in Table empowering our NAON with BART pre-trained weights, it gains marvelous improvement and sets a new SOTA. This observation implies that: I) our NAON could be ap- plicable to various generation-bant based ordering mod- els and boost their performance, and 2) exploring appropriate proxy tasks during pre-training might be beneficial for sentence ordering. Besides, these results also imply that NAON is applicable various ceneration-basel models and can boost their performances by exploring the bilateral de- pendency of sentences.
3.3 Diving into Exclusive Loss
As illustrated in the fifth and sixth lines from the bottom of Table 1, the proposed exclusive loss im- proves the sentence ordering performance signifi- cantly. Nevertheless, is hard to investigate how it alleviates the repetition problem exactly. Towards this end, we produce the inference results before the selective and removing procedure, in which rep- etition exist. We conduct two levels of repetition evaluation. Specifically, the Paragraph Repetition Ratio (PRR) evaluates the paragraph-level repe- tition which equals when a repetitive sentence exists the paragraph otherwise O. We also cal- culate the mean of the Sentence Repetition Ratio (mSRR) to evaluate from the sentence level by di- viding the number of repetitive sentences by the total number of sentences in the paragraph.
3.2 Predicting Head and Tail
As mentioned in (Gong et al., 2016; Chen al., 2016; Cui et al., 2018), the first and the last sen- tences play an important role sentence ordering due to their special positions. Following previous works, we conduct the experiments on arXiv and SIND datasets and illustrate the comparison in Ta- ble 2. We can observe that our NAON outperforms all the baselines demonstrating superiority. Be- sides, the autoregressive fashion takes the previous output as current input, the first sentence predic- tion much more crucial than others. While our non aon-autoregressive decoder not subject to this limitation, the accuracy of the first sentence predic-
We investigate the repetitive predictions from the NAON model with and without exclusive loss on AAN and ROCStory datasets. From the results exhibited Figure 4, we can see that without exclu- sive loss, NAON is highly likely to generate para- graphs with repetitive sentences (PRR is 99,46% for AAN and 99.97% for ROCStory)!. While con-
NNte that our full model equipped with greedy selective and removing strategy will not generate repetition onder. Here we remove this strategy to deeply probe and investigate the effectiveness of the exclusive loss for alleviating repetition issue from the training side.

---

strained by our novel exclusive loss during training, the model remarkably decreases the repetition ra- tio to 68% and 35.5 35.58% which means that the exclusive constraint between sentences and posi- tions makes great contributions in alleviating the repetition issue. At sentence level, the repetitive ratios for two datasets also drop dramatically with the introduction of exclusive loss, even achieving 6.36 indicating that there only exist very small proportion of sentences repeated in the prediction. Based on the above observations, we can conclude that our exclusive loss can effectively alleviate the repetition problem of NAD, and thereby improve its performance for sentence ordering.
Table 3: Efficiency comparison of autoregressive and non-autoregressive strategies during inference, well as B-TSort. We conduct this experiment on an NVIDIA TITAN V, and use second to measure the inference time of each dataset. ratio denotes the accelerating ratio comparing NAON to AON and B- B-TSort.
NAON
AON
B-TSort
Dataset
time
lime
ralio
time
ratio
NIPS
4.35
6.55
1.51x
93.22
21.43x
AAN
13.82
21.92
1.59x
375.82
27.19x
NSF
123.26
187.76
1.52x
1848.91
15.00x
arXiv
1040.81
1401.88
1.35x
SIND
42.47
54,53
1.28x
583.40
13.74x
ROCStory
45.98
59.64
x.30x
and Chowdary, 2020; Logeswaran et al., 2018; Yin et al., 2020). For ranking-bused strategy, Chen et al. (2016) introduced a pairwise model which ranks relative order for sentence pairs. Kumar et al. (2020) employed BERT-improved feedforward neu- ral networks to generate scores for each sentence and optimized the scores with several ranking losses, e.g., pairwise ranking loss. Prabhumoye et al. (2020) proposed to constrain the relative or- der between paired sentences and introduced the classic topological sort algorithm to find the gold order, which achieves considerable improvement.
4 Accelerating Sentence Ordering
Non-autoregressivv strategy implementing paral- lel decoding is with low latency and more effi- cient than the autoregressive one (Gu et al., 2018). In this part, we investigate the time efficiency of our NAON empirically. We compare the inference time of NAON and AON, which share the same encoder and employ different decoders, i.e., non- autoregressive and autoregressive decoders. Ta- ble 3 exhibits the inference time (measured by sec- ond) comparison between NAON and AON on each dataset, as well as the ratio comparing with NAON. We also include the comparison with B-TSort, the SotA ranking-basc based method, which shows huge time costs because it computes the relative orders of all the sentence pairs. From the above results, we observe that the proposed NAON gains significant speed-up on all datasets. Besides, since the aver- age number of sentences per paragraph in NIPS, AAN, and NSF are larger than SIND and ROC- Story, they benefit more from the parallel decoding of the noneuutoregeessive strategy. Such results are also consistent with our intuition that paragraph with more sentences takes more time with autore- gressive methods.
For generation based strategy, Gong et al. (2016) firstly utilized an RNN to encode sentences and Lo- geswaran et al. (2018) explored LSST-bbaee atten- tion encoder, both works employed similar recur- rent pointer net to generate the coherent paragraph centence-by-sentenee
However, since the input of sentence ordering is a set of unordered sentences, it is inappropriate to model the unordered sentences in an autoregressive manner. To address this is- sue, Cui et al. (2018) proposed to use Transformer but without positional embedding to encode the unordered sentences. Most of the follow-up meth- ods also applied the order invariant Transformer as paragraph encoder (Yin et al., 2019, 2020; Ku- mar et al., 2020: Cui et al., 2020). Besides, other attempts also have been explored for order invari- ant encoding. Yin et al. (2019) devised a graph structure to encode the input order-free sentence set. Wang and Wan (2019) proposed a hierarchical attention network composed of a word encoder and sentence encoder-decoder. Cui et al. (2020) and Li et al. (2022) further took advantage of BERT to explore the deep semantic connection and rela- tive order between sentences. Basu Roy Chowd- hury et al. (2021) employed the BART as backbone, which benefited from the sentence permutation task during pre-training and set strong SotA.
5
Related Works
5.1 Sentence Ordering
Early works on sentence ordering attempt to utilize probabilistic transition method based on linguistic features (Lapata, 2003), content model (Barzilay and Lee, 2004) and entity-based approaches (Barzi- lay and Lapata, 2008; Prabhumoye et al., 2020). Recent neural models for the sentence ordering task are built on generation or ranking struc- ture (Chen et al., 2016; Gong et al., 2016; Pandey

---

5.2 Non-Autoregressive Transformer
ber of sentences is fixed in the input, our NAON model does not need to consider this issue and can fully explore the potential of NAT in this task.
Non-autoregresssive transformer (NAT) (Gu et al., 2018) has been proposed an effective non- autoregressive decoding method in machine trans- lation. NAT predicts the output sequence based on source sequence and latent representation via par- allel fashion. In order to narrow the performance gap between NAT and autoregressive transformer (AT), various approaches have been proposed in many research areas (Guo et al., 2020; Yang et al.,,
NAT models usually suffer from repetitive gen- eration issue due to conditional independence be- tween output representations. For machine trans- lation, Gu et al. (2018) proposed to use fertility L.e., copy times of each source token, bridge the encoding and decoding processes, copying input tokens for several times as inputs of the decoder. Due to the conditional independence between out- put tokens, NAT model tends to generate repeated tokens in the output sequence. To alleviate this issue, Wang et al. (2019) and Li et al. (2019) in- troduced auxiliary loss functions to deal with the problem of repetition. Recently, semi-NAT style models (Stern et al., 2019; Gu et al., 2019) pro- posed new generation approaches to alleviate repe- tition issue. In our NAON model, we introduce an exclusive loss to tackle this problem.
2021; Bin et al., 2023). Several methods (Lee et al..
2018; Guo et al., 2019; Wang et al., 2019 Li et al..
2019; Guo et al., 2020) proposed to modify the la- tent presentation by making use of extra refinement process, designing auxiliary modules and latent forms. Another line of research (Ghazvininejad et al., 2019; Stern et al., 2019; Gu et al., 2019) tended to achieve trade-off between performance and inference efficiency by using semi-NAT ar- chitecture. Besides, many researchers had made attempts introduce NAT into different sequence generation tasks like speech recognition (Ren et al., 2019) and dialog state tracking (Le et al., 2020). Moreover, it is worth noting that many NAT' related pre-trained generation models (Chan et al., 2019; Qi et al., 2020) had been proposed to improve the generation results of pre-trained models. Our work makes the first attempt accomplish sentence or- dering task by NAT style model.
6 Conclusion
We presented a novel non autoarrgrrrrsivve ordering network for sentence ordering, which consists of a basic sentence encoder, a contextual sentence en- coder, and non-autoregressive decoder. Different from existing autoregressive methods, the proposed NAON predicted sentence for each position in par- allel, which also leveraged bilateral dependencies among sentences, and demonstrated competitive performance. To alleviate the repetition problem of the proposed NAON, we devised an exclusive loss to constrain the exclusiveness matching between sentences and positions. The experimental results on several common-used datasets demonstrated the effectiveness of the proposed approach. The analy- ses of exclusive loss also indicate that alleviating repetition issue could improve the generation per- formance of the non-autores an---utoregressvve decoder.
In order to perform parallel decoding, sequence length should be determined firstly in NAT. The pioneer work NAT (Gu et al., 2018) designed fertility predictor to predict the copy times of cach token in the source sequence. By summarizing the copy times of all the tokens, model can obtain the target length of output sequence. Later, (Lee et al., 2018) proposed to use separate length predictor to obtain the target length for the inference process. Some Semi-NAT models (Stern al., 2019; Gu et al., 2019) even proposed to implement insertion or deletion-based methods to control the length of generated sequences. Ran et al. (2021) intro- duced an intermediate pseudo-translation to align the order between source and target languages, which could help model the conditional dependen- cics of the target words and encourage the decoder choose right words. Du et al. (2021) claimed the penalty for word order errors should not be in- cluded, because the semantic alignment between source and target words could be agnostig. In the ordering problem (Bin et al., 2022), as the num-
7 Acknowledgement
This research is partially supported by the National Natural Science Foundation of China under grant 62 621020 62220106008 and U20B2063, and par- tially supported by Sichuan Science and Technol- ogy Program under grant 2023NSFSC1392. This research is supported by * CISCO Sys- tems (USA) Pte. Ltd and National University of Singapore under its Cisco-NUS Accelerated Digital Economy Corporate Laboratory (Award 12 22001E0002),

---

8 Limitations
Xinchi Chen, Xipeng Qiu, and Xuanjing Huang. 2016. Neural sentence ordering. arXiv preprint MrXiv:1607.060
In this work, we propose to employ non- autoregressive Transformer (NAT) as the decoder for sentence ordering, which could leverage bi- lateral dependencies between sentences, different with previous autoregressive decoders (e.g., RNN and LSTM) which explore only unilateral depen- dencies. However, to clearly analyze the particular priority of the NAT structure for sentence ordering. we adopt the vanilla NAT and simple repetition mitigatioon strategy for our NAON, ignoring further improvements or advances on NAT. Therefore, only use the vanilla NAT could be a limitation of our work. Despite that previous work or experimental results have suggested techniques such as exploring relative order exploration applying the BART model could further improve the performance of sentence ordering, we do not want these detailed techniques to overshadow the main deployment of non-autoregressive decoding. We hope our work could bring some insights to the research or- dering problem and encourage more attempts at integrating advanced techniques with NAT.
Baiyun Cui, Yingming Li, Ming Chen, and Zhongfei Zhang. 2018. Deep attentive sentence ordering net- work. In EMNLP. pages 4340-4349.
Baiyun Cui, Yingming Li, and Zhongfei Zhang. 2020. Bert-enhanced relational sentence ordering network. In EMNLP, pages 6310-6320.
Jacob Devlin, Ming-Wer Wei Chang, Kenton Lec, and Kristina Toutanova. 2019. Bert: Pre-training deep bidirectional transformers for language understand- ing. In NAACL, pages 4171
Cunxiao Du, Zhaopeng Tu, and Jing Jiang. 2021. Order-agnostic cross entropy for non-autoregressive machine translation. In ICML, pages 2849-2859. PMLR.
Marjan Ghazvininejad. Omer Levy, Yinhan Liu, and Luke Zettlemoyer. 2019. Mask-predict: Parallel de- coding of conditional masked language models. In EMNLP- pages 6111-6120.
Jingjing Gong, Xinchi Chen, Xipeng Qiu, and Xu- anjing Huang. 2016. End-to-end neural sentence ordering using pointer network. arXiv preprint arXiv: 100166111195....
Jiatao Gu, James Bradbury, Caiming Xiong, Victor O. K. Li, and Richard Socher. 2018. Non-auvoreeresssve neural machine translation. In ICLR.
References
Regina Barzilay and Mirella Lapata. 2008 Modeling local coherence: Au entity-based approach. Compu- tational Linguistics, 34(1):1-34,
Jiatao Gu, Changhan Wang, and Junbo Zhao. 2019. Levenshtein transformer. In NeurlPS, pages 11179- 11189.
Regina Barzilay and Lillian Lee. 2004. Catching drift: Probabilistic content models, with applications generation and summarization. In HLT-NAACL, pages 113-120.
Junliang Guo, Xu Tan, Di He, Tao Qin, Linli Xu, and Yan Liu. 2019. Non-autoregressive neural ma- chine translation with enhanced decoder input. AAAI pages 3723-3730.
Somnath Basu Roy Chowdhury, Faeze Brahman, and Snigdha Chaturvedi. 2021. Is everything order? a simple way to order sentences. In EMNLP, pages 10769-10779.
Junliang Guo, Xu Tan, Linli Xu, Tao Qin, Enhong Chen, and Tie- Yan Liu. 2020. Fine-tuning by curriculum learning for non-autoregressive neural machine trans- lation. In AAAI, pages 7839-7846.
Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer. 2015. Scheduled sampling for sequence prediction with recurrent neural networks. NeurIPS, 28: 28:1171-1179.
Ting-Har Hao Huang, Francis Ferraro, Nasrin Mostafazadeh, Ishan Misra, Aishwarya Agrawal, Jacob Devlin, Ross Girshick, Xiaodong He, Pushmeet Kohli, Dhruv Ba- tra, et al. 2016. Visual storytelling. In NAACL-HLT, pages 1233-1239.
Yi Bin, Mengqun Han, Wenhao Shi, Lei Wang. Yang Yang, See- See-Kiong Ng, and Heng Tao Shen. 2023. Non- autoregressive math word problem solver with uni- fied tree structure. EMNLP.
Diederik P Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In ICLR.
Yi Bin, Wenhao Shi, Jipeng Zhang, Yujuan Ding, Yang Yang, and Heng Tao Shen. 2022. aon-autoreeeessive cross-modal coherence modelling. In ACM MM, pages 3253-3261
Pawan Kumar, Dhanajit Brahma, Harish Karnick, and Piyush Rai. 2020. Deep attentive ranking networks for learning to order sentences. In AAAI, pages 8115- 8122.
William Chan, Nikita Kitaev, Kelvin Guu, Mitchell Stern, and Jakob Uszkoreit. 2019. KERMIT: genera- tive insertion-bant based modeling for sequences. CoRR, 0bss/996.01660
Mirella Lapata. 2003. Probabilistic text structuring: Experiments with sentence ordering. In ACL, pages 545-552.

---

Hung Le. Richard Socher, and Steven C. H. Hoi. 2020. con-autoregressive dialog state tracking. In JCLR.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In NeurIPS, pages 5998-6008.
Jason Lee, Elman Mansimov, and Kyunghyun Cho.
2018. Deterministic aooreettreeressvve neural se- quence modeling by iterative refinement. In EMNLP. pages 1172-1182.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer networks. NeurIPS, 28:2692-2700.
Yingming Li. Baiyun Cui, and Zhongfei Zhang. 2022. Efficient relational sentence ordering network. IEEE Transactions on Pattern Analysis and Machine Intel- ligence, 44(10))6169-611
Qingyun Wang, Zhihao Zhou, Lifu Huang, Spencer Whitehead, Boliang Zhang, Heng Ji, and Kevin Knight. 2018 Paper abstract writing through editing mechanism. In ACL, pages
Zhuohan Li, Zi Lin, Di He, Fei Tian, Tao Qin, Liwei Wang, and Tic- Liu. 2019. fint-based train- ing for -toreeeereee machine translation. In EMNLP-IJCNLP, pages 5702-5712.
Tianming Wang and Xiaojun Wan. 2019. Hierarchical attention networks for sentence ordering. In AAAI, volume 33, pages 7184-7191.
Yiren Wang, Fei Tian, Di He, Tao Qin, ChengXiang Zhai, and Tie- Yan Liu. 2019. Non-autoregressive machine translation with auxiliary regularization. AAAI, pages 5377-5384.
Lajanugen Logeswaran, Honglak Lee, and Dragomir Radev. 2018. Sentence ordering and coherence mod- eling using recurrent neural networks. In AAAI, vol- ume 32.
Jason Wei, Xuezhi Wang. Dale Schuurmans. Maarten Bosma, Fei Xia, Ed H Chi, Quoe V Le, Denny Zhou, et al. thhiin-of-thouge prompting elicits reasoning in large language models. In NeurIPS.
Nasrin Mostafazadeh, Nathanael Chambers, Xiaodong He. Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, and James Allen. 2016. A corpus and cloze evaluation for deeper understanding of commonsense stories. In NAACL-HIIT, pages 839- 849.
Bang Yang. Yuexian Zou, Fenglin Liu, and Can Zhang. 2021. Non-autoregressive coarse-to-fine video cap- tioning. In AAAI, volume 35, pages 3119-3127.
Byungkook Oh, Seungmin Seo, Cheolheon Shin, Eunju Jo, and Kyong-Ho Lee. 2019. Topic-guided coher- ence modeling for sentence ordering by preserving global and local information. In EMNLP-IJCNLP pages 2273-2283.
Yongjing Yin, Fandong Meng, Jinsong Su, Yubin Ge, Linfeng Song, Jie Zhou, and Jiebo Luo. 2020. En hancing pointer network sentence ordering with pairwise ordering predictions. In AAAI, pages 9482- 9489.
Divesh Pandey and C Ravindranath Chowdary. 2020. Modeling coherence by ordering paragraphs using pointer networks. Neural Networks, 126:36-41.
Yongjing Yin, Linfeng Song. Jinsong Su, Jiali Zeng. Chulun Zhou, and Jiebo Luo. 2019. Graph-based neural sentence ordering. In IJCAI, pages 5387-
5393. AAAI Press.
Shrimai Prabhumoye, Ruslan Salakhutdinov, and Alan Black. 2020. Topological sort for sentence ordering. In ACI. pages 2783-2792.
A Sentence Ordering with ChatGPT
With the blooming of Large Language Models (LLMs), especially the great success of GPT se- ries, e.g., ChatGPT² and GPT-43, many NLP tasks have been proposed to integrate with LLMs based on suitable prompts and demonstrated marvelous results and performance. We therefore take an at- tempt to recover the coherence of sentences with ChatGPT API. We test ChatGPT on NIPS and SIND datasets only, due to the expensive costs of ChatGPT API calling, and the results are shown in Table 4. Before the test, we expected ChatGPT could achieve marvelous ordering performance, e.g., more than 95% in Acc, but the results show that it seemed be not skilled in sentence ordering problems, and shocked us with dramatically low
Weizhen Qi. Yeyun Gong, Jian Jiao, Yu Yan, Dayi- heng Liu, Weizhu Chen, Kewen Tang, Houqiang Li. Jiusheng Chen, Ruofei Zhang, Ming Zhou, and Nan Duan. 2020. BANG: bridging autoregressive and non-autoregressive generation with large scale pre- training. CoRR, abs/2012. 15525.
Qiu Ran, Yankai Lin, Peng Li, and Jie Zhou. 2021. Guiding aoorreeereeressivve neural machine transla- tion decoding with reordering information. In AAAI, volume 35, pages 13735-
Ren, Yangjun Ruan, Xu Tan, Tao Qin, Sheng Zhao, Zhou Zhao, and Tie- Yan Liu. 2019. Fastspeech: Fast, robust and controllable text to speech. In NewrlPS, pages 3165-311 3174.
Mitchell Stern, William Chan, Jamie Kiros, and Jakob Uszkoreit. 2019, Insertion transformer: Flexible se- quence generation via insertion operations. In ICML, pages 5976-5985.
thups://opeeaiicom https///opemaiiccoo///lolhaaaag Phaps://opemail.oo//gg-4

---

Prompt
NIPS
SIND
GPT may fail to count the number of sentences with "List" input. For example, it might output four or six indices to indicate the new order of five sentences (A true output case is shown in Figure 7). The failure cases are about 5% and 6.8% for NIPS and SIND datasets. While the "Dict" input provides explicit labels, e.g., sl and s2, for each sentence. and significantly avoids such outputs (decreased to 0.8% and 0.5% for NIPS and SIND).
Ace
PMR
7
Ace
PMR
List
-PO
24.87
6.12
0.26
-PI
27.40
6.12
-P2
42.44
17.82
0.39
37.32
9.95
0.27
-P3
46.89
19.41
0.5
41.34
13.1
0.45
Dict
-P1
30.48
6.12
0.39
-P2
56,92
24.93
0.7
44.96
17.07
0.49
-P3
58.10
28.8
0.71
52.38
22,71
0.57
TGCM
59,43
31.44
0.75
38.71
15.18
0.53
B-TSort
61.48
32.59
0.81
52.23
20.32
0.60
Analyses of Prompts: As we know, the quality of prompts could introduce significant impacts and result in violent fluctuations of performance. Dur- ing our experiments, we have tried to make our prompts clearer and more suitable for sentence ordering, shown in Figure 6. We note that only request ChatGPT to output the order without the coherent paragraph (e.g., Prompt-O and Prompt-1), works extremely badly (PO and PI in Table 4), When we instruct first to output the coherent paragraph and give the new order subsequent (Prompt-2), it gains significant improvement. This is also consistent with that LLMs are somehow heuristic and could be guided with step-by-step rea- soning (Wei et al.). We observe it might predict the number of indices or sentence signs inconsistent with the true number of sentences for both List and Dict inputs. We further explicitly indicate the num- ber of sentences in the prompt (Prompt-3), the in- consistent number of sentences could be effectively avoided, resulting in 1/367 (0.27%) and 3/5055 (0.06%) for NIPS and SIND datasets. Though the clearer prompts significantly boost the sentence ordering of ChatGPT, it is still far from our expec- tation, even compared to the relatively small pre- trained models, e.g. BERT and BART, Therefore. we will keep designing more instructive prompts for sentence ordering in future works.
NAON 64.43
33.02
0.80
52.38
19.13
0.60
Table 4: The test performance using ChatGPT API on NIPS and SIND datasets. List and Dict mean that the unordered sentences are input with the format of list and dict. p# indicate different prompts that could be found in Figure 6. To reduce the token costs of API calling, we only test on NIPS (only 376 samples) for exploratory study for inferior prompts early stage, egg. PO and Pl. We also list three ordering models for reference.
performance. We analyze the results and assume the reasons may come from two points. The first one is that, our prompts are not very well to instruct the ChatGPT to effectively recover the coherence and reorder the sentences. Because we have also tried revise our prompts several times to make the prompt more clear and more instructive (in Figure 6). the performance could be significantly improved with better prompts. Therefore, if we can find more suitable and instructive prompts to en- courage the ChatGPT to understand the semantics better, it should work well for recovering the coher- ence of set of unordered sentences. We will keep taking further attempts this point. The second one might come from the model side of ChatGPT. As we know, GPT series are decoder-only and de- signed for generative pre-training and exhibit ex- traordinary abilities of generation, e.g., creative writing, and story completion, etc. While sentence ordering is a semantic coherence understanding task, where the output is strictly constrained by the input. We therefore suppose that the strict output may limit the ability of GPT model for sentence ordering.
For this part of work, we would like to thank An- drew Ng and Isa Fulford for providing the prompt instructions in an open-source course". We also thank all the people sharing tricks online for prompt engineering.
B Details of Experiments
B.1 Datasets
Analyses of Input Styles: For the unordered sen- tences, we have tried two ways to feed them to ChatGPT: List and Diet, detailed in Figure 5. The performance comparisons are in Table 4, from which we can observe that ChatGPT works better with the "Dict" format than "List". We also have further investigated the reasons, and found Chat-
As aforementioned, to evaluate the effectiveness of the proposed NAON, we conduct experiments on several commonly used datasets for comprehen- sive analyses, including four datasets collecting the
promp--oggineernn-ffddddvveeee aishsoott-ccuussscchhgggg

---

abstract of academic papers and two story under- standing corpora.
N the total number of sentences in the para- graph.
AAN (Wang al., 2018): the abstracts of pa- pers published on ACL Anthology Network until 2016. We the data provided by (Lo- geswaran et al., 2018), as well the data split.
All the metrics indicate the better performance by higher score.
B.3 Experimental Settings
We implement our model using PyTorch, and em- ploy the Adam algorithm (Kingma and Ba, 2015) to optimize all the models. The initial learning rate is set as ir; = 1e- for the contextual encoder and non-autoregressive decoder, and Ir, 5c for fine-tuning BERT-BASE with 12 Transformer blocks. The training process is terminated if the per- formance of validation worse than the best one for times. To prevent over-fitting, adopt weight decay and dropout operation during training, the parameters of which are = 1e and = 0.1. The hidden size of transformer blocks are 1024 and 2 multi-head inter-attention blocks in decoder. The number of Transformer blocks in encoder are specific to different datasets, in particular, 2 for SIND, ROCStory and NIPS, 4 for NSF and arXiv, for AAN. All the experiments are conducted on workstation with 8 NVIDIA Titan V GPUs.
NIPS: the paper abstracts of NIPS con- ference in years 2005-2013/2014/0111 for trainingvaliddiioneestnng, provided by (Lo- geswaran et al., 2018).
NSF: the abstracts of NSF Research Award, also provided by (Logeswaran et al., 2018).
arXiv (Chen et al., 2016): contains abstracts of seven disciplines, including physics, com- puter science and etc, on arXiv website.
SIND (Huang et al., 2016): stories for images in sequence, collected for visual storytelling. Each story consists of sentences.
ROCStory (Mostafazadeh al., 2016): origi- nally collected for commonsense story under- standing, which provides sentences in each story.
B.2 Evaluation Metrics
In this work, we employed three metrics, including Ace, PMR, and r, to evaluate the performance and compare with the baselines. The details of the metrics are as follows:
Perfect Match Ratio (PMR) calculates the exact matching on paragraph level, which the most rigid one of existing metrics.
Accuracy (Ace) takes more relaxed measure strategy by calculating the accuracy of abso- lute position prediction on sentence level. Ob- viously, it may fail to evaluate the coherence of relative order, e.g., scoring 0 for [2, 3, 1] with the ground-trute [1, 2,3, 4].
Kendall's tau (r) measures the relative or- der between all sentence pairs in predicted paragraph, which is defined as:
N
T T= -=1-2 I/
2
where the number inversion between two sentences comparing with gold order, and

---

List Input:
["some of these crafts very unique take of talent make. in unique costumes as part their selling act.", lots of folks come out and set up tables to sell their crafts.
the crafters even dress up
"the local parish holds craft show each year. falks of all ages come out peruse the crafts for sale. "]
Expected Output:
Output1:
The coherent order is: (4, 3, 1, 2] "(for the index only output)
Output2:
The coherent paragraph is: the local parish holds craft show each year. lots of folks come out and tables sell their crafts.
of these crafts are very unique and take lot talent make. folks of all ages come out to peruse the crafts for sale. some of the crafters even dress up unique costumes as part their selling act. Therefore, the coherent order is: 1, 2] -(for the coherent paragraph and index output)
Other Outputs of ChatGPT:
Output3: The coherent order is: [3, 2, 0, 1]
Output4:
The coherent order is; [1][][
Output5: The coherent order is: [3]][[[]][[[]]
Output6: The coherent order is: ["the local parish holds a craft show each year. lots of folks come out
set tables to sell their crafts. ", some of these crafts are very unique and take lot of talent to make. folks of all ages costumes as part of their selling act.")
out to peruse the crafts for sale, some of the crafters dress up in unique
Dict Input:
("s1": some of these crafts are very unique and take lot of talent to make. "s2": some of the crafters even up unique costumes as part selling act.", "s3": "lots of folks come and up tables to sell their crafts. "s4": "the local parish holds craft show each year.", "s5": "falks of all ages come out to peruse the crafts for sale." ")
Expected Output:
Output1: The coherent order is: (s4, s3, s1, s5, s2] -(for the index only output)
Output2: The coherent paragraph is: the local parish holds craft show each lots of folks come out and set up tables to sell their crafts. some these crafts very unique all ages come out to peruse the crafts for sale. some of the crafters even dress up in unique costumes as part of their selling act. Therefore, the coherent order is: (s4, s5, s2] "(for the coherent paragraph and index output)
take of talent make. folks
Other Outputs of ChatGPT:
Output3: The coherent order is: [s4[{s]][=]]{s{{{{]]]
Output4: The coherent order is: ('the local parish holds craft show each year. ", lots of folks come out and set up tables to sell their crafts.
some of these crafts very unique and take lot of talent to make. folks of ages come out to peruse the crafts for sale. some of the crafters even dress up in unique costumes as part of their selling act.")
Figure 5: The inputs and outputs for ChatGPT API calling. tested two formats of input: List and Dict, and the corresponding expected outputs the indices and keys of sentences. We note that ChatGPT does not always give the outputs as we expected, it also outputs some cases with other styles, as shown in the "other outputs of ChatGPT" blocks. When we make the output more formatted, egg., the "output2", it could avoid unexpected outputs.

---

Prompt-0:
Please analyze the following list of unordered sentences delimited by triple backticks and determine the coherent order.
Once you have identified the correct order, please output INDEX in following format: [0, 1, 4, 3j. Please DON'T provide any additional outputs or information other than the requested INDEX.
The unordered sentences:
"0"
Prompt-1:
From the point of semantic coherence, please REORDER the following sentences, delimited by triple backticks, coherent paragraph.
Once have recovered the coherence, please output the NEW ORDER in the following format: The coherent order is: [s1, s3, s2, s5, s4]. ([1, 2, 5, 4] LIST input)
Please be CONCISE and DO NOT provide any additional outputs or information other than the requested INDEX.
The sentences are: "(")"
Prompt-2:
Please REORDER the following sentences, delimited by triple backticks, to coherent paragraph.
The sentences are:
""()"
Once have recovered the coherence, please output in the following format: ""The coherent paragraph is: COHERENT PARAGRAPH. Therefore, the coherent order [SIGNS SENTENCES). ([IDDICES SENTENCES) for UST input)""
Please be CONCISE and DO NOT provide any additional outputs information other than the requested
output.
Prompt-3: Please REORDER following ( sentences, delimited by triple backticks, coherent paragraph.
The sentences are:
""O""
Once you have recovered the coherence, please output in the following format: "'The coherent paragraph is: COHERENT PARAGRAPH. Therefore, the coherent order is: [SIGNS OF SENTENCES). ([INDICES OF SENTENCES] LIST input)""
Please be CONCISE and DO NOT provide additional outputs or information other than the requested output.
Figure 6: The prompt templates used our ChatGPT API test. "Prompt-O", we have only tested LIST input, and tested LIST and DICT inputs for other prompts. The contents in brackets of "Prompt- 1/2/3" not part of the corresponding prompt, which are used to replace the output format for different input formats. The corresponding formats input and output could be found in Figure

---

Input and Prompt:
Please REORDER the following sentences, delimited by triple backticks, to coherent paragraph.
The sentences are:
also met lots of locals who quirky and fun. would pay more attention to the history of thailand." we were not sure what to expect from our trip to religious.
decided that the next time visited
thailand." we found lot of beautiful architecture and art and lot of bit for ourselves and found some areas where there was lot of poverty. "] Once you have recovered the coherence, please output in the following format: "Thhe coherent paragraph is: COHERENT PARAGRAPH. Therefore, the coherent order is: [INDICES OF SENTENCES). Please be CONCISE and DO NOT provide any additional outputs information other than the requested output.
explored
Number of predicted sentences increases: Output: The coherent paragraph lot of beautiful architecture and art. a lot of it was religious. we explored a bit for ourselves and found where there decided that the next time we visited we would pay more attention to the history of thailand. Therefore, coherent order is: [3, 4, Ground Truth Order: [3, 5, 1, 4,
what expect from trip thailand. found
lot of poverty. also met lots of locals who quirky and fun.
Input and Prompt:
Please REORDER the following sentences, delimited by triple backticks, to coherent paragraph.
The sentences
I" some of the guests will be sleeping over tonight and sleeping on the futons in the living room. we finally see the exit sign the highway for the party. when all the guests have gone home, the host is vacuuming the living room. there is long drive to the party tonight. when we got there, all our friends are already there.""
Once you have recovered the coherence, please output in the following format: "'The coherent paragraph is: COHERENT PARAGRAPH. Therefore, coherent order is: [INDICES SENTENCES). Please be CONCISE and DO NOT provide any additional outputs or information other than the requested output.
Number of predicted sentences is reduced:
Output: The coherent paragraph is: there is long drive to the party tonight. when we got there, all our friends are already there. some the guests will sleeping over tonight sleeping on the futons in the living room. when all the guests have gone home, the host is vacuuming the living room. Therefore, the coherent order is: [4,
Ground Truth Order: [4, 2, 5, 1, 3]
The cases of inconsistent number of sentences predicted by ChatGPT. The top one predicts one more index for the sentences, while the bottom one discards one sentence.
Figure 7:

---

Input and Prompt:
Please REORDER the following sentences, delimited by triple backticks, to coherent paragraph.
The sentences are:
(" there are lots of rides to enjoy this year. " the family a trip local carnival. " tthere are also lots of games and prizes to win. there are even rides for folks as young as this small boy. although some of the games seem fixed and a waste money."
Once have recovered the coherence, please output in the following format: "Thhe coherent paragraph COHERENT PARAGRAPH. Therefore, the coherent order [INDICES SENTENCES). Please CONCISE and DO NOT provide additional outputs or information other than the requested output.
Output is Correct:
Output: The coherent paragraph is; the family takes trip to the local carnival. there are lots of rides to enjoy this year. there are even rides folks as young as this small boy. there are also lots of games and prizes to win. although some of the games seem fixed and waste money.
Therefore, the coherent order is: [2, 1, 4, 3, Ground Truth Order: [2, 4,
Input and Prompt:
Please REORDER the following sentences, delimited by triple backticks, to coherent paragraph.
The sentences are:
I" every summer we head out west to texas to visit relatives and experience country life. these are cousins having fun moment with each other. and these are my friends and relatives while we check out the produce of their farm. ", "while it was hot and humid, we really enjoyed the country view with less noise and traffic no buildings. ", here we see my cousin's pigs and are they huge and noisy pigs. "] Once have recovered the coherence, please output in the following format: "'The coherent paragraph is: COHERENT PARAGRAPH. Therefore, the coherent order is: [INDICES OF SENTENCES). Please CONCISE and DO NOT provide any additional outputs information other than the requested output.
Output is Wrong:
Output: The coherent paragraph is: every summer we head out west to texas to visit my relatives and experience country life. while was hot and humid, we really enjoyed the country view with less noise and traffic and no buildings. here see cousin's pigs and are they huge and noisy pigs. these are friends and relatives while we check out the produce of their farm. these are my cousins having fun moment with each other. Therefore, the coherent order is: [1, 5,
Ground Truth Order: [1, 5, 4,
Figure 8: Two cases of SIND outputted by ChatGPT, inputting as "List" format with Prompt-3.


Reviews:
[{"review_id": "LPO6mYEpxu", "reviewer": "Reviewer_7JW7", "summary": "", "questions": "Please respond to the weakness mentioned above. ", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank and appreciate the reviewer's careful and valuable comments. To make our paper clearer, below we try to answer the questions and issues raised by the reviewer. Hope it could address the concerns of the reviewer. Thanks very much.\n\n**Question_1:** The described approach in the methods section does not achieve the best results. Only when non-autoregressive decoders are applied to BART it achieves the SOTA. It begs the question is the application of the Basic and Contextual Sentence Encoder really needed? Apart from the pre-training task, I feel it helps the model to encode all the sentences together. It would be good to see some empirical evaluation when you train an encoder that takes entire sentences as input either from scratch or using another pre-trained model apart from BART.\n\n**Answer_1:** Thanks for the constructive review. We think the improvement of integration with BART (NAON-BART in Table 1) mainly comes from the powerful and compatible representation learned from BART pre-trained model. Because **sentence permutation** is one of the pre-training tasks of BART, the representation extracted from BART is quite suitable for sentence ordering and gains significant improvement. To verify the real contributions of Basic and Contextual Sentence Encoder, we have conducted experiments with LSTM-based models, **contextual LSTM** (the same as LSTM-Ptr in Table 1) and **all sentence together LSTM** (we use TogLSTM to denote it), on SIND. The results are as below:\n\n\n$\\begin{matrix}\n\\hline\n\\text{Method} & \\text{Acc} & \\text{PMR} & \\text{$\\tau$} \\\\\\\\ \\hline\n\\text{LSTM-Ptr} & 45.33 & 12.7 & 0.47 \\\\\\\\\n\\text{TogLSTM} & 42.55 & 10.35 & 0.44 \\\\\\\\ \\hline\n\\end{matrix}$\n\nFrom the results, we observe the LSMT-Ptr with Basic and Contextual Sentence Encoder outperforms TogLSTM with large margin, which verifies the effectiveness of our Basic and Contextual Sentence Encoder. Due to the time limit, we only test with simple LSTM on SIND, we will conduct extensive experiments with pretrained models and other methods on other datasets to comprehensively evaluate the effectiveness of the Basic and Contextual Sentence Encoder. As our NAON is the first attempt at using non-autoregressive decoding for sentence ordering, we have not tried many advanced techniques at current stage. In future work, we will explore more advanced techniques and settings, e.g., the reviewer suggested taking all the sentence as input (but we think the sentences should be order-independent) and exploring relative order information, to further improve the non-autoregressive decoding for sentence ordering. We also hope our work could bring some insights to the community and encourage more attempts at NAT for sentence ordering. Thanks again for the suggestive comments.\n\n**Question_2:** The paper needs to provide some more introduction to non-autoregressive decoding. Without that it can be a bit difficult for the reader to go through Section 2.4 and 2.5.\n\n**Answer_2:** Thanks for the suggestion. To provide more introduction to NAT and make Sec2.4 and 2.5 more friendly to the readers, we will revise corresponding parts with two folds: 1) add a brief introduction to NAT in Line 256 as: \n```“Our NAD is designed based on a Non-Autoregressive Transformer (NAT) decoder in machine translation, which removes the autoregressive connections between steps and generates all the target words in parallel, rather than step-by-step (i.e., word-by-word).”```\n and 2) add a subsection of literature review of Non-Autoregressive Transformer (NAT) in Related Works in the revision. We thank again for your helpful suggestion.\n\n**Question_3:** The current state-of-the-art Re-BART was not mentioned at all in the introduction and related works while describing generation-based models. Some of the statements made in the paper (Line 241-243) when you consider systems like Re-BART.\n\n**Answer_3:** We apologize for missing description about RE-BART. We will introduce it in suitable place in the introduction and related works in revision. For the statement in L241-243, we apologize for the imprecise description. Actually, we want to express “recurrent-based”, of which RNN-based model is the most straightforward one. Thanks for the reviewer's reminder, we note that many works employ Transformer for generation, which also applies autoregressive (recurrent) decoding strategy and is excluded by the description of ‘RNN-based’. We will revise this in the revision to make the description more precise.\n\n**Question_4:** Table 2 in the paper is not complete. The paper hides several baselines that outperform it. These are reported in the Re-BART paper, and the paper should report them for completeness even though their results are slightly weak.\n\n**Answer_4:** Thanks for the constructive suggestions. We are not intentionally to omit the baselines. We actually have conducted the experiments of BERSON, NAON-RO, RE-BART, and NAON-BART, but we omitted them due to the page limitation. As mentioned in Answer_1, our NAON is a prior attempt for sentence ordering with non-autoregressive decoding, and we only use the vanilla NAD without advanced techniques to fairly compare with baselines. Then we have also verified its generalization ability by integrating with BERSON and BART. Therefore, we chose to remove these results from Table 2 to meet the page requirements. To dispel your doubts, we present the results below and will include them in Table 2 in the revision.\n\n$\\begin{matrix}\n\\text{Model} & \\text{arXiv (head)}  & \\text{arXiv (tail)} & \\text{SIND (head)} & \\text{SIND (tail)}           \\\\\\\\ \\hline\n    \\text{BERSON}  & 94.75  & 76.69  & 84.95  & 64.87  \\\\\\\\\n \\text{NAON-RO} & 94.83  & 76.71  & 84.98  &  64.91 \\\\\\\\ \\hline\n \\text{RE-BART} & 96.46 & 80.62 & 87.97 & 73.02 \\\\\\\\\n \\text{NAON-BART} & 98.98 & 85.91 & 90.1 & 80.99 \\\\\\\\\n     \\hline\n\\end{matrix}$\n\nFrom the results, we observe that equipped with our non-autoregressive decoder, NAON-RO and NAON-BART ourperform the corresponding autoregressive ones in head and tail prediction, which are consistent with the results and conclusions in Table 1.", "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": "1. The paper is mostly well-written.\n2. The paper achieved great results beating the previous SOTA Re-BART, which is hard to beat and held the SOTA for nearly 2 years.\n3. The utility of non-autoregressive decoders is novel and well-suited as the output length is known in advance.", "reasons_to_reject": "1. The described approach in the methods section does not achieve the best results. Only when non-autoregressive decoders are applied to BART it achieves the SOTA. It begs the question is the application of the Basic and Contextual Sentence Encoder really needed? Apart from the pre-training task, I feel it helps the model to encode all the sentences together. It would be good to see some empirical evaluation when you train an encoder that takes entire sentences as input either from scratch or using another pre-trained model apart from BART.\n2. The paper needs to provide some more introduction to non-autoregressive decoding. Without that it can be a bit difficult for the reader to go through Section 2.4 and 2.5.\n3. The current state-of-the-art Re-BART was not mentioned at all in the introduction and related works while describing generation based models. Some of the statements  made in the paper (Line 241-243) when you consider systems like Re-BART. \n4. Table 2 in the paper is not complete. The paper hides several baselines that outperform it. These are reported in the Re-BART paper, and  the paper should report them for completeness even though their results are slightly weak. ", "questions_to_authors": "Please respond to the weakness mentioned above. ", "paper_topic_and_main_contributions": "The paper introduces a new technique for sentence ordering tasks. Specifically, the primary novelty of the work involves the usage of non-autoregressive decoders. As the output length is known exactly beforehand, it makes the use of non-autoregressive decoders ideal for this task. The paper encodes sentences independently, passes the sentence representations to another self-attention based transformer and then uses non-autoregressive decoding. The paper also introduces a greedy inference technique to reduce repetitions in the output. The proposed approach achieves great results along with new SOTA for the task over 6 different datasets. ", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZdtnxKBfpB", "reviewer": "Reviewer_8B3p", "summary": "", "questions": "- Question A: The non-autoregressive decoding seems to use a basic greedy selection approach. Have you explored integrating more advanced NAT techniques like iterative refinement? How much gain can these provide?\n\n- Question B: You test integrating NAON with BART, but only report accuracy results. Can you also analyze the impact on efficiency and repetitions? How does BART integration compare to your exclusive loss?\n\n- Question C: The ChatGPT experiments are interesting but limited. Can you provide more details on the prompt engineering process and lessons learned on how to prompt sentence order effectively?\n", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank and appreciate the reviewer's careful and valuable comments. To make our paper clearer, below we try to answer the questions and issues raised by the reviewer. Hope it could address the concerns of the reviewer. Thanks very much.\n\n**Question_1:** The non-autoregressive decoding seems to use a basic greedy selection approach. Have you explored integrating more advanced NAT techniques like iterative refinement? How much gain can these provide?\n\n**Answer_1:** Thanks for the suggestive reviews. Our NAON indeed employs vanilla non-autoregressive decoding and a basic greedy selection strategy, and does not integrate with other advanced techniques, e.g., iterative refinement, to further improve the performance. The reason is that all the existing generation-based methods employ autoregressive decoding strategy, including RNN-based and Transformer, for sentence ordering. Our **NAON is the first one** to employ non-autoregressive decoding to explore bilateral dependencies for sentence ordering. To evaluate the performance of non-autoregressive decoding fairly and purely, we only employ vanilla NAT without any advanced techniques. We also verify the generalization ability of our NAON by integrating with BERSON and BART, which means our NAON could be further improved with advanced techniques. As Reviewer 7JW7 mentioned, ```RE-BART is hard to beat and held the SOTA for nearly 2 years```. **When equipped with our non-autoregressive decoder, NAON-BART substantially outperforms RE-BART by a large margin (shown in Table 1, averaging relative improvements across six datasets w.r.t Acc: 9.17%, PMR: 8.13%, and $\\tau$: 5.35%). Therefore, from this perspective, we believe we have pushed the boundaries of sentence ordering.** Though we have not explored more techniques in this work, as mentioned in **Section Limitation**, we hope our work, the first attempt at non-autoregressive decoding, could bring some insights to the research of ordering problem and encourage more attempts at integrating advanced techniques to facilitate non-autoregressive decoding. Thanks for the constructive review.\n\n\n**Question_2:** You test integrating NAON with BART, but only report accuracy results. Can you also analyze the impact on efficiency and repetitions? How does BART integration compare to your exclusive loss?\n\n**Answer_2:** Thanks for the suggestive comments. As the reviewer suggested, we test the efficiency of RE-BART and NAON-BART on ROCStory, because the authors of RE-BART only released the checkpoint on this dataset (We will try to train and test RE-BART on other datasets, and include the results in the revision). The results are as follows:\n\n\\begin{matrix}\n\\hline\n\\text{Dataset}    &  \\text{RE-BART} & \\text{NAON-BART} &   \\text{Accelerating Ratio}          \\\\\\\\  \\hline\n\\text{ROCStory}       & 851.59   & 524.32   & 1.62\\times  \\\\\\\\ \\hline\n\\end{matrix}\n\nFrom the results we can see, replacing the autoregressive decoder in RE-BART with our non-autoregressive decoder could gain 1.62 times acceleration, which shows similar performance in Table 3.\nFor the repetition performance of NAON-BART, the results are as:\n\n\\begin{matrix}\n\\hline\n\\text{Dataset}    &  \\text{PRR} & \\text{mSRR}           \\\\\\\\ \\hline\n\\text{ANN}       & 52.08   & 13.05     \\\\\\\\ \n\\text{ROCStory}       & 22.67   & 3.39     \\\\\\\\ \\hline\n\\end{matrix}\n\nComparing with the results shown in Figure 4, we observe significantly decrease of repetition comparing with vanilla NAON, which means the integration with BART also further improve the overall performance of sentence ordering.\n\nFor the question “How does BART integration compare to your exclusive loss”, BART and exclusive loss are two ways to reinforce our simple and naïve NAON, but **they contribute from two different aspects**. Integration with BART improves the performance from **representation perspective**. As we know, sentence permutation is one of the pre-training tasks of BART, which makes the sentence representations learned with BART is more compatible with sentence ordering than BERT and demonstrates superior performance. It also could be replaced by other more powerful representation learning model in the future. While exclusive loss contributes to the model from the **aspect of optimization constraint**, aiming to match the positions and sentences one-by-one and alleviate repetition matching. These two techniques **can be combined to work together** to boost the performance, which is what NAON-BART (in Table 1) does. Thanks again for the valuable comments.\n\n**Question_3:** The ChatGPT experiments are interesting but limited. Can you provide more details on the prompt engineering process and lessons learned on how to prompt sentence order effectively?\n\n**Answer_3:** Thanks for the review. As shown in Figure 5-8 (page13-16) and Table 4, we have explored the input format of unordered sentences, e.g., **List** and **Dict**, and observed sentences with Dict could significantly decrease the error rate of wrongly counting of sentences and achieve better performance. For effectively prompting, we have revised and improved the prompts via several ways, which also described in Section Appendix A. For the lessons and tricks learned online, we mainly learn how to effectively prompt the ChatGPT in general way. Such as we learned that the main goal of prompt engineering is to make the task description more precise, concise, and easy to understand for ChatGPT, and make the input and output clear and definite. We then applied the prompt engineering and tricks for sentence ordering by considering the task characteristic. Limited by the prompt engineering, the performance of ChatGPT has not met the expectation, and we will keep exploring on this.", "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": "- Proposes a novel application of non-autoregressive decoding for sentence ordering, which is interesting to the NLP community\n\n- Well-designed model with contextual encoders and NAT decoder that effectively exploits bilateral dependencies\n\n- Detailed analyses like quantifying repetition reduction from the exclusive loss\n\n- Explores integrating NAON with pre-trained models to push the state-of-the-art further\n\nOverall, this work demonstrates a novel application of an important technique (NAT) on an important problem (ordering) with empirical. Accepting this could significantly broaden the scope and advance the state-of-the-art of non-autoregressive decoding for sequence generation tasks.", "reasons_to_reject": "- The non-autoregressive decoding approach is basic without incorporating advanced NAT techniques like iterative refinement. This risks presenting a simple application without pushing boundaries.\n- The ChatGPT experiments, while interesting, seem preliminary and exploratory. Relying heavily on these incomplete experiments may be risky.\n- There could be more ablation studies to analyze the impact of various design choices instead of just the loss.", "questions_to_authors": "- Question A: The non-autoregressive decoding seems to use a basic greedy selection approach. Have you explored integrating more advanced NAT techniques like iterative refinement? How much gain can these provide?\n\n- Question B: You test integrating NAON with BART, but only report accuracy results. Can you also analyze the impact on efficiency and repetitions? How does BART integration compare to your exclusive loss?\n\n- Question C: The ChatGPT experiments are interesting but limited. Can you provide more details on the prompt engineering process and lessons learned on how to prompt sentence order effectively?\n", "paper_topic_and_main_contributions": "This paper proposes NAON, a novel non-autoregressive approach for sentence ordering. The key contribution is using a non-autoregressive transformer decoder to predict sentences in parallel rather than sequentially. Non-autoregressive decoding could explore bilateral dependencies between sentences and enable parallel prediction during inference. Furthermore, the authors introduce an exclusive loss to alleviate repetition issues in non-autoregressive decoding. \n\nOverall the paper is well-written and easy to follow. The experiments on several benchmark datasets demonstrate the effectiveness of the proposed NAON model.", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "MHZcKU1XTZ", "reviewer": "Reviewer_FhyS", "summary": "", "questions": "* Eq(2): Should it be $o_1$ to $o_j$ instead of $s_1$ to $s_j$? (Where S is the set of $s_1$ to $s_N$)\n* Eq(3): This is a similar problem. Additionally, since the non-autoregressive model predicts each token independently, the condition may not need to include $o_1$ to $o_N$.\n* L536-L539: I couldn't find the speed comparison with B-Tsort.\n* Previous research on non-autoregressive translation models generally believes that NAT models face challenges in capturing the correct order of predicted tokens. For instance, [1] proposes the use of an autoregressive model to guide the token generation order, while [2] introduces an order-agnostic loss to address the issue of NAT models mixing sentences with different orders. It would be helpful if the authors could discuss the distinctions between their findings and the earlier beliefs.\n\n[1] Qiu Ran, Yankai Lin, Peng Li, Jie Zhou. Guiding Non-Autoregressive Neural Machine Translation Decoding with Reordering Information. AAAI 2021.\n[2] Cunxiao Du, Zhaopeng Tu, Jing Jiang. Order-Agnostic Cross Entropy for Non-Autoregressive Machine Translation. ICML 2021.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank and appreciate the reviewer's careful and valuable comments. To make our paper clearer, below we try to answer the questions and issues raised by the reviewer. Hope it could address the concerns of the reviewer. Thanks very much.\n\n**Quetion_1:** Eq(2): Should it be $o_1$ to $o_j$ instead of $s_1$ to $s_j$? (Where $S$ is the set of $s_1$ to $s_n$)\n\n**Answer_1:** Thanks for the review. The notations are right here. We apologize for the ambiguous description. The generation-based models **do not directly generate the gold order** of the sentences, they instead generate the coherent paragraph **sentence-by-sentence** to achieve the goal of recovering the cohrence of unordered sentences. Therefore, the output of each step is a coherent representation of each sentence, rather than the order, and the model tries to maximize the similarity between such coherent representation and previous context representation. This is similar with text generation,  which can classify the output embedding to words or maximize the similarity between output word embedding and input word embedding. \nIn the revision, we will make the description in L170-172 clearer as follows:\n```Existing autoregressive approaches generate the coherent paragraph sentence-by-sentence to recover the gold order, and optimize the model by maximizing:```\n\n$ \\sum_{j=1}^{N}\\log P(s_{j}|s_1, s_2, ...,s_{j-1}, S) $ \n\n**Question_2:** Eq(3): This is a similar problem. Additionally, since the non-autoregressive model predicts each token independently, the condition may not need to include $o_1$ to $o_n$.\n\n**Answer_2:** Thanks for the suggestion. For $o_1$ to $o_n$, the condition does not need to include $o_1$ to $o_n$. Here we just want to emphasize the interaction between $o_1$ to $o_n$ during decoding. We will revise this in the revision, and emphasize the interaction with description.\n\n\n**Question_3:** L536-L539: I couldn't find the speed comparison with B-Tsort.\n\n**Answer_3:** We apologize for our carelessness during the space adjustment. Because our NAON employs very similar architecture with AON, except for the non-autoregressive decoder, comparing the speed of AON and NAON is the most proper setting to evaluate the efficiency of non-autoregressive decoding. We include B-TSort for additional reference to compare with other methods, but the space is limited. To meet the requirement of page limitation, we removed the results from Table 3 and adjusted it from two-column to single-column, but we forgot to remove corresponding descriptions in the analysis. We apologize for this carelessness. The inference time and acceleration ratio of **B-TSort** are listed below:\n\n\\begin{matrix}\n\\text{Dataset} & \\text{B-TSort} & \\text{NAON} & \\text{Accelerating Ratio} \\\\\\\\ \\hline\n\\text{NIPS}       & 93.22   & 4.35   & 21.43  \\times    \\\\\\\\\n\\text{AAN}         & 375.82  & 13.82 & 27.19  \\times   \\\\\\\\\n\\text{NSF}        & 1848.91 & 123.26 & 15.00  \\times  \\\\\\\\\n\\text{arXiv}      & - & 1040.81 & -  \\\\\\\\\n\\text{SIND}       & 583.40  & 42.47  & 13.74  \\times  \\\\\\\\\n\\text{ROCStory}   & -  & 45.98  & - \\\\\\\\ \\hline\n\\end{matrix}\n\nBecause the original paper and released codes did not conduct experiments on arXiv and ROCStory datasets, we also did not test their method on these two datasets. We will include these results in the revision.\n\n**Question_4:** Previous research on non-autoregressive translation models generally believes that NAT models face challenges in capturing the correct order of predicted tokens. For instance, [1] proposes the use of an autoregressive model to guide the token generation order, while [2] introduces an order-agnostic loss to address the issue of NAT models mixing sentences with different orders. It would be helpful if the authors could discuss the distinctions between their findings and the earlier beliefs.\n\n**Answer_4:** Thanks for providing the literatures. Both works are aiming at the multimodal problem in machine translation with NAT and trying to tackle this problem from the perspective of generation order. ReorderNAT [1] introduces an intermediate pseudo-translation to align the order between source and target languages, which could help model the conditional dependencies of the target words and encourage the decoder to choose right words. OAXE [2] claims the penalty for word order errors should not be included, because the semantic alignment between source and target words could be order-agnostic. We agree with that NAT models face challenges in capturing the correct order of predicted tokens, but we claim that the order should be **‘absolute order’**. In other words, **it is hard to align a certain word to an absolute position.** Through the bidirectional interactions of attention, NAT could capture the **‘relative order’** dependencies between words/sentences. In sentence ordering problem, the goal is to capture the ‘relative order’ between sentences, therefore, we believe it could avoid the ‘absolute order’ challenge in NAT. Thanks again for the review, we will include the discussion and distinctions between the mentioned works [1, 2] and our NAON in the revision.", "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": "* It's surprising that the proposed non-autoregressive model performs better than autoregressive models in sentence ordering tasks, considering non-autoregressive models are generally weak at modeling dependencies between generated tokens. This finding will be valuable for non-autoregressive model research.\n* The experiments are solid. The comparison against chatGPT in the appendix is particularly interesting.", "reasons_to_reject": "* Nothing particular.", "questions_to_authors": "* Eq(2): Should it be $o_1$ to $o_j$ instead of $s_1$ to $s_j$? (Where S is the set of $s_1$ to $s_N$)\n* Eq(3): This is a similar problem. Additionally, since the non-autoregressive model predicts each token independently, the condition may not need to include $o_1$ to $o_N$.\n* L536-L539: I couldn't find the speed comparison with B-Tsort.\n* Previous research on non-autoregressive translation models generally believes that NAT models face challenges in capturing the correct order of predicted tokens. For instance, [1] proposes the use of an autoregressive model to guide the token generation order, while [2] introduces an order-agnostic loss to address the issue of NAT models mixing sentences with different orders. It would be helpful if the authors could discuss the distinctions between their findings and the earlier beliefs.\n\n[1] Qiu Ran, Yankai Lin, Peng Li, Jie Zhou. Guiding Non-Autoregressive Neural Machine Translation Decoding with Reordering Information. AAAI 2021.\n[2] Cunxiao Du, Zhaopeng Tu, Jing Jiang. Order-Agnostic Cross Entropy for Non-Autoregressive Machine Translation. ICML 2021.", "paper_topic_and_main_contributions": "This paper presents a new approach to solve the sentence ordering task with non-autoregressive methods. The method uses an order-invariant encoder to get sentence representations and then non-autoregressively predicts the order for each position using pointer networks. To avoid repetitions in non-autoregressive generation, the paper introduces an exclusive loss and a greedy selective and removing strategy. The experiments demonstrate that this proposed method outperforms previous generation methods and most ranking-based methods, while also being slightly faster than autoregressive generation methods.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is about a new method for sentence ordering. Although the motivation and the task are not the most "exciting" (sentence ordering as a proxy for discourse coherence), the reviewers agree on the novelty of the method which predicts sentences in parallel (as opposed to sequentially). One reviewer expressed some concern that the task is too simple which risks not pushing the method enough, but they all agree that the results are "sound" and with potential to be built upon by other researchers working on non-autoregressive generation.
Decision: Accept-Findings