Paraphrasing natural language sentences is a multifaceted process: it might involve replacing individual words or short phrases, local rearrangement of content, or high-level restructuring like topicalization or passivization. Past approaches struggle to cover this space of paraphrase possibilities in an interpretable manner. Our work, inspired by pre-ordering literature in machine translation, uses syntactic transformations to softly reorder the source sentence and guide our neural paraphrasing model. First, given an input sentence, we derive a set of feasible syntactic rearrangements using an encoder-decoder model. This model operates over a partially lexical, partially syntactic view of the sentence and can reorder big chunks. Next, we use each proposed rearrangement to produce a sequence of position embeddings, which encourages our final encoder-decoder paraphrase model to attend to the source words in a particular order. Our evaluation, both automatic and human, shows that the proposed system retains the quality of the baseline approaches while giving a substantial increase in the diversity of the generated paraphrases. 1 1 Introduction Paraphrase generation (McKeown, 1983; Barzilay and Lee, 2003) has seen a recent surge of interest, both with large-scale dataset collection and curation (Lan et al., 2017; Wieting and Gimpel, 2018) and with modeling advances such as deep generative models (Gupta et al., 2018; Li et al., 2019). Paraphrasing models have proven to be especially useful if they expose control mechanisms that can be manipulated to produce diverse paraphrases (Iyyer et al., 2018; Chen et al., 2019b; Park et al., 2019), which allows these models to be employed for data augmentation (Yu et al., 2018) and 1 Data and code are available at https://github. adversarial example generation (Iyyer et al., 2018). However, prior methods involving syntactic control mechanisms do not effectively cover the space of paraphrase possibilities. Using syntactic templates covering the top of the parse tree (Iyyer et al., 2018) is inflexible, and using fully-specified exemplar sentences (Chen et al., 2019b) poses the problem of how to effectively retrieve such sentences. For a particular input sentence, it is challenging to use these past approaches to enumerate the set of reorderings that make sense for that sentence. In this paper, we propose a two-stage approach to address these limitations, outlined in Figure 1. First, we use an encoder-decoder model (SOW , for Source Order reWriting) to apply transduction operations over various abstracted versions of the input sentence. These transductions yield possible reorderings of the words and constituents, which can be combined to obtain multiple feasible rearrangements of the input sentence. Each rearrangement specifies an order that we should visit words of the source sentence; note that such orderings could encourage a model to passivize (visit the object before the subject), topicalize, or reorder clauses. These orderings are encoded for our encoder-decoder paraphrase model (REAP , for REarrangement Aware Paraphrasing) by way of position embeddings, which are added to the source sentence encoding to specify the desired order of generation (see Figure 2). This overall workflow is inspired by the pre-ordering literature in machine translation (Xia and McCord, 2004; Collins et al., 2005); however, our setting explicitly requires entertaining a diverse set of possible orderings corresponding to different paraphrasing phenomena. We train and evaluate our approach on the large-scale English paraphrase dataset PARA NMT-50M (Wieting and Gimpel, 2018). Results show that our approach generates considerably more diverse paraphrases while retaining the quality exhibited by strong baseline models. We further demonstrate that the proposed syntax-based transduction procedure generates a feasible set of rearrangements for the input sentence. Finally, we show that position embeddings provide a simple yet effective way to encode reordering information, and that the generated paraphrases exhibit high compliance with the desired reordering input. Given an input sentence x = { x 1 , x 2 , . . . , x n } , our goal is to generate a set of structurally distinct paraphrases Y = { y 1 , y 2 , . . . , y k } . We achieve this by first producing k diverse reorderings for the input sentence, R = { r 1 , r 2 , . . . , r k } , that guide the generation order of each corresponding y . Each reordering is represented as a permutation of the source sentence indices. Our method centers around a sequence-to-sequence model which can generate a paraphrase roughly respecting a particular ordering of the input tokens. Formally, this is a model P ( y | x , r ) . First, we assume access to the set of target reorderings R and describe this rearrangement aware paraphrasing model (REAP ) in Section 2.2. Then, in Section 2.3, we outline our reordering approach, including the source order rewriting (SOW ) model, which produces the set of reorderings appropriate for a given input sentence x during inference ( x  R ) . The models discussed in this work build on a standard sequence-to-sequence transformer model (Vaswani et al., 2017) that uses stacked layers of self-attention to both encode the input tokens x and decode the corresponding target sequence y . This model is pictured in the gray block of Figure 2. Throughout this work, we use byte pair encoding Encoder Decoder + + + + Input tokens x Original Order Token embeddings Encoder Output EM Target Order r New Encoder Output E 4 3 1 2 1 2 3 4 Output tokens y Clippers won the game BOS The The game Figure 2: Rearrangement aware paraphrasing (REAP ) model. (BPE) (Sennrich et al., 2016) to tokenize our input and output sentences. These models are trained in the standard way, maximizing the log likelihood of the target sequence using teacher forcing. Additionally, in order to ensure that the decoder does not attend to the same input tokens repeatedly at each step of the decoding process, we include a coverage loss term, as proposed in See et al. (2017). Note that since the architecture of the transformer model is non-recurrent, it adds position embeddings to the input word embeddings in order to indicate the correct sequence of the words in both x and y (see Figure 2). In this work, we propose using an additional set of position embeddings to indicate the desired order of words during generation, described next. Let r = { r 1 , r 2 , . . . , r n } indicate the target reordering corresponding to the input tokens x . We want the model to approximately attend to tokens in this specified order when generating the final output paraphrase. For instance, in the example in Figure 1, the reordering specifies that when producing the paraphrase, the model should generate content related to the game before content related to Clippers in the output. In this case, based on the rearrangement being applied, the model will most likely use passivization in its generation, although this is not strictly enforced. The architecture for our model P ( y | x , r ) is outlined in Figure 2. Consider an encoder-decoder architecture with a stack of M layers in the encoder R EORDER(S0): Recursively reorder constituents to get final ordering S0 SBAR PRP VP IN S PRP VP1 If it continues to rain I will carry an umbrella MD VP2 VB NPSOW Input SOW Output If S I will VP 4 5 1 2 3 SBAR I will carry NP 1 3 4 5 2 SELECTSEGMENTPAIRS : Choose constituents to abstract REORDERPHRASE : Use seq2seq model to reorder phrase SBAR I will carry NP If S I will VP I will VP if S SBAR NP I carry Source reordering Final paraphrases I will carry an umbrella if rain continues. and N layers in the decoder. We make the target reordering r accessible to this transformer model through an additional set of positional embeddings P E r . We use the sinusoidal function to construct these following Vaswani et al. (2017). Let EM = encoder M ( x ) be the output of the M th (last) layer of the encoder. The special-purpose position embeddings are added to the output of this layer (see Figure 2): E = EM + P E r . Note that these are separate from standard position embeddings added at the input layer; such embeddings are also used in our model to encode the original order of the source sentence. The transformer decoder model attends over E while computing attention and the presence of the position embeddings should encourage the generation to obey the desired ordering r , while still conforming to the decoder language model. Our experiments in Section 4.3 show that this position embedding method is able to successfully guide the generation of paraphrases, conditioning on both the input sentence semantics as well as the desired ordering. We now outline our approach for generating these desired reorderings r . We do this by predicting phrasal rearrangements with the SOW model at various levels of syntactic abstraction of the sentence. We combine multiple such phrase-level rearrangements to obtain a set R of sentence-level rearrangements. This is done using a top-down approach, starting at the root node of the parse tree. The overall recursive procedure is outlined in Algorithm 1. One step of the recursive algorithm has three Algorithm 1 REORDER ( t ) Input: Sub-tree t of the input parse tree Output: Topk list of reorderings for t 's yield T = SELECTSEGMENTPAIRS ( t ) // Step 1 R = INITIALIZEBEAM ( size = k ) for ( A, B ) in T do z = REORDERPHRASE ( t, A, B ) // Step 2 RA (1 , . . . , k ) = REORDER ( t A ) // k orderings RB (1 , . . . , k ) = REORDER ( t B ) // k orderings for r a , r b in RA  RB do r = COMBINE ( z, r a , r b ) // Step 3 score ( r ) = score ( z )+ score ( r a )+ score ( r b ) R . major steps: Figure 3 shows the overall workflow for one iteration (here, the root node of the sentence is selected for illustration). First, we select sub-phrase pairs of the input phrase that respect parse-tree boundaries, where each pair consists of non-overlapping phrases (Step 1). Since the aim is to learn generic syntax-governed rearrangements, we abstract out the two sub-phrases, and replace them with non-terminal symbols, retaining only the constituent tag information. For example, we show three phrase pairs in Figure 3 that can be abstracted away to yield the reduced forms of the sentences. We then use a seq2seq model to obtain rearrangements for each abstracted phrase (Step 2). Finally, this top-level rearrangement is combined with recursively-constructed phrase rearrangements within the abstracted phrases to obtain sentence-level rearrangements (Step 3). We begin by selecting phrase tuples that form the input to our seq2seq model. A phrase tuple ( t, A, B ) consists of a sub-tree t with the constituents A and B abstracted out (replaced by their syntactic cat-egories). For instance, in Figure 3, the S 0 , S, and VP 2 nodes circled in red form a phrase tuple. Multiple distinct combinations of A and B are possible. 2 Step 2: REORDERPHRASE Next, we obtain rearrangements for each phrase tuple ( t, A, B ) . We first form an input consisting of the yield of t with A and B abstracted out; e.g. If S I will VP , shown in red in Figure 3. We use a sequence-to-sequence model (the SOW model) that takes this string as input and produces a corresponding output sequence. We then perform word-level alignment between the input and generated output sequences (using cosine similarity between GloVe embeddings) to obtain the rearrangement that must be applied to the input sequence. 3 The log probability of the output sequence serves as a score for this rearrangement. SOW model The SOW model is a sequence-to-sequence model P ( y (cid:48) | x (cid:48) , o ) , following the transformer framework in Section 2.1. 4 Both x (cid:48) and y (cid:48) are encoded using the word pieces vocabulary; additionally, embeddings corresponding to the POS tags and constituent labels (for non-terminals) are added to the input embeddings. For instance, in Figure 3, If S I will VP and I will VP if S is an example of an ( x (cid:48) , y (cid:48) ) , pair. While not formally required, Algorithm 1 ensures that there are always exactly two non-terminal labels in these sequences. o is a variable that takes values MONOTONE or FLIP . This encodes a preference to keep the two abstracted nodes in the same order or to flip them in the output. 5 o is encoded in the model with additional positional encodings of the form { . . . 0 , 0 , 1 , 0 , . . . 2 , 0 . . . } for monotone and 2 In order to limit the number of such pairs, we employ a threshold on the fraction of non-abstracted words remaining in the phrase, outlined in more detail in the Appendix. { . . . 0 , 0 , 2 , 0 , . . . 1 , 0 . . . } for flipped, wherein the non-zero positions correspond to the positions of the abstracted non-terminals in the phrase. These positional embeddings for the SOWMODEL are handled analogously to the r embeddings for the REAP model. During inference, we use both the monotone rearrangement and flip rearrangement to generate two reorderings, one of each type, for each phrase tuple. The previous step gives a rearrangement for the subtree t . To obtain a sentence-level rearrangement from this, we first recursively apply the REORDER algorithm on subtrees t A and t B which returns the top-k rearrangements of each subtree. We iterate over each rearrangement pair ( r a , r b ) , applying these reorderings to the abstracted phrases A and B . This is illustrated on the left side of Figure 3. The sentence-level representations, thus obtained, are scored by taking a mean over all the phrase-level rearrangements involved. We train and evaluate our model on the PARA NMT-50M paraphrase dataset (Wieting and Gimpel, 2018) constructed by backtranslating the Czech sentences of the CzEng (Bojar et al., 2016) corpus. We filter this dataset to remove shorter sentences (less than 8 tokens), low quality paraphrase pairs (quantified by a translation score included with the dataset) and examples that exhibit low reordering (quantified by a reordering score based on the position of each word in the source and its aligned word in the target sentence). This leaves us with over 350k paired paraphrase pairs. To train our REAP model (outlined in Section 2.2), we take existing paraphrase pairs ( x , y  ) and derive pseudo-ground truth rearrangements r  of the source sentence tokens based on their alignment with the target sentence. To obtain these rearrangements, we first get contextual embeddings (Devlin et al., 2019) for all tokens in the source and target sentences. We follow the strategy outlined in Lerner and Petrov (2013) and perform reorderings as we traverse down the dependency tree. Starting at the root node of the source sentence, we determine the order between the head and its children (independent of other decisions) based on the order If it continues to rain I will carry an umbrella I will carry an umbrella if rain continues Figure 4: Paraphrase sentence pair and its aligned tuples A  B, C and A (cid:48)  B (cid:48) , C (cid:48) . of the corresponding aligned words in the target sentence. We continue this traversal recursively to get the sentence level-rearrangement. This mirrors the rearrangement strategy from Section 2.3, which operates over constituency parse tree instead of the dependency parse. The PARA NMT-50M dataset contains sentence-level paraphrase pairs. However, in order to train our SOW model (outlined in section 2.3), we need to see phrase-level paraphrases with syntactic abstractions in them. We extract these from the PARA NMT-50M dataset using the following procedure, shown in Figure 4. We follow Zhang et al. (2020) and compute a phrase alignment score between all pairs of constituents in a sentence and its paraphrase. 6 From this set of phrase alignment scores, we compute a partial one-to-one mapping between phrases (colored shapes in Figure 4); that is, not all phrases get aligned, but the subset that do are aligned one-to-one. Finally, we extract aligned chunks similar to rule alignment in syntactic translation (Galley et al., 2004): when aligned phrases A and A (cid:48) subsume aligned phrase pairs ( B, C ) and ( B (cid:48) , C (cid:48) ) respectively, we can extract the aligned tuple ( t A , B, C ) and ( t A (cid:48) , B (cid:48) , C (cid:48) ) . The phrases ( B, C ) and ( B (cid:48) , C (cid:48) ) are abstracted out to construct training data for the phrase-level transducer, including supervision of whether o = MONOTONE or FLIP . Using the above alignment strategy, we were able to obtain over 1 million aligned phrase pairs. Setup As our main goal is to evaluate our model's ability to generate diverse paraphrases, we 6 The score is computed using a weighted mean of the contextual similarity between individual words in the phrases, where the weights are determined by the corpus-level inverse-document frequency of the words. Details in the Appendix. obtain a set of paraphrases and compare these to sets of paraphrases produced by other methods. To obtain 10 paraphrases, we first compute a set of 10 distinct reorderings r 1 , . . . , r 10 with the SOW method from Section 2.3 and then use the REAP to generate a 1-best paraphrase for each. We use top-k decoding to generate the final set of paraphrases corresponding to the reorderings. Our evaluation is done over 10k examples from PARA NMT-50M. Baselines We compare our model against the Syntactically Controlled Paraphrase Network ( SCPN ) model proposed in prior work (Iyyer et al., 2018). It produces 10 distinct paraphrase outputs conditioned on a pre-enumerated list of syntactic templates. This approach has been shown to outperform other paraphrase approaches that condition on interpretable intermediate structures (Chen et al., 2019b). Additionally, we report results on the following baseline models: i) A copy-input model that outputs the input sentence exactly. ii) A vanilla seq2seq model that uses the same transformer encoder-decoder architecture from Section 2.1 but does not condition on any target rearrangement. We use topk sampling (Fan et al., 2018) to generate 10 paraphrases from this model. diverse-decoding model that uses the above transformer seq2seq model with diverse decoding (Kumar et al., 2019) during generation. Here, the induced diversity is uncontrolled and aimed at maximizing metrics such as distinct n-grams and edit distance between the generated sentences. iv) A LSTM version of our model where the REAP model uses LSTMs with attention (Bahdanau et al., 2014) and copy (See et al., 2017) instead of transformers. We still use the transformer-based phrase transducer to obtain the source sentence reorderings, and still use positional encodings in the LSTM attention. Similar to Cho et al. (2019), we report two types of metrics: 1. Quality : Given k generated paraphrases Y = { y 1 , y 2 . . . y k } for each input sentence in the test set, we select  y best that achieves the best (oracle) sentence-level score with the ground truth paraphrase y . The corpus level evaluation is performed using pairs ( y best , y ) . 2. Diversity : We calculate BLEU or WER be-7 Prior work (Wang et al., 2019; Li et al., 2019) has shown that such a transformer-based model provides a strong baseline and outperforms previous LSTM-based (Hasan et al., 2016) and VAE-based (Gupta et al., 2018) approaches. In addition to these metrics, we use the paraphrase similarity model proposed by Wieting et al. (2017) to compute a paraphrase score for generated outputs with respect to the input. Similar to Iyyer et al. (2018), we use this score to filter out low quality paraphrases. We report on the rejection rate according to this criterion for all models. Note that our diversity metric is computed after filtering as it is easy to get high diversity by including nonsensical paraphrase candidates that differ semantically. Table 1 outlines the performance of the different models. The results show that our proposed model substantially outperforms the SCPN model across all quality metrics. 8 Furthermore, our LSTM model also beats the performance of the SCPN model, demonstrating that the gain in quality cannot completely be attributed to the use of transformers. The quality of our full model (with rearrangements) is also comparable to the quality of the vanilla seq2seq model (without rear-rangements). This demonstrates that the inclusion of rearrangements from the syntax-based neural transducer do not hurt quality, while leading to a substantially improved diversity performance. The SCPN model has a high rejection score of 40 . 6% . This demonstrates that out of the 10 templates used to generate paraphrases for each sentence, on average 4 were not appropriate for the given sentence, and therefore get rejected. On the other hand, for our model, only 15 . 9% of the generated paraphrases get rejected, implying that the rearrangements produced were generally meaningful. This is comparable to the 12 . 7% rejection rate 8 The difference in performance between our proposed model and baseline models is statistically significant according to a paired bootstrap test. exhibited by the vanilla seq2seq model that does not condition on any syntax or rearrangement, and is therefore never obliged to conform to an inappropriate structure. Finally, our model exhibits a much higher diversity within the generated paraphrases compared to the transformer seq2seq baseline. As expected, the SCPN model produces slightly more diverse paraphrases as it explicitly conditions the generations on templates with very different top level structures. However, this is often at the cost of semantic equivalence, as demonstrated by both quantitative and human evaluation (next section). A similar trend was observed with the diverse-decoding scheme. Although it leads to more diverse generations, there is a substantial decrease in quality compared to SOW-REAP and the seq2seq model. Moreover, the paraphrases have a higher rejection rate (21.3%), suggesting that diverse decoding is more likely to produce nonsensical paraphrases. A similar phenomenon is also reported by Iyyer et al. (2018), wherein diverse-decoding resulted in paraphrases with different semantics than the input. Syntactic Exemplars In addition to SCPN, we compare our proposed model against the controllable generation method of Chen et al. (2019b). Their model uses an exemplar sentence as a syntactic guide during generation; the generated paraphrase is trained to incorporate the semantics of the input sentence while emulating the syntactic structure of the exemplar (see Appendix D for exam-ples). However, their proposed approach depends on the availability of such exemplars at test time; they manually constructed these for their test set ( 800 examples). Since we do not have such example sentences available for our test data, we report results of our model's performance on their test data. Note that Chen et al. (2019b) carefully curated the exemplar to be syntactically similar to the actual target paraphrase. Therefore, for fair comparison, we report results using the ground truth ordering (that similarly leverages the target sentence to obtain a source reordering), followed by the REAP model. This model (ground truth order + REAP ) achieves a 1-best BLEU score of 20.9, outperforming both the prior works: Chen et al. (2019b) (13.6 BLEU) and SCPN (17.8 BLEU with template, 19.2 BLEU with full parse). Furthermore, our full SOWREAP model gets an oracle-BLEU (across 10 sentences) score of 23.8. These results show that our proposed formulation outperforms other controllable baselines, while being more flexible. Table 2 provides examples of paraphrase outputs produced by our approach and SCPN. The examples show that our model exhibits syntactic diversity while producing reasonable paraphrases of the input sentence. On the other hand, SCPN tends to generate non-paraphrases in order to conform to a given template, which contributes to increased diversity but at the cost of semantic equivalence. In Table 3, we show the corresponding sequence of rules that apply to an input sentence, and the final generated output according to that input rearrangement. Note that for our model, on average, 1 . 8 phrase-level reorderings were combined to produce sentence-level reorderings (we restrict to a maximum of 3 ). More examples along with the input rule sequence (for our model) and syntactic templates (for SCPN) are provided in the Appendix. evalu-Input Sentence : if at any time in the preparation of this ate the quality of the generated paraphrases. We randomly sampled 100 sentences from the development set. For each of these sentences, we obtained 3 generated paraphrases from each of the following models: i) SCPN, ii) vanilla sequence-to-sequence and iii) our proposed SOW-REAP model. We follow earlier work (Kok and Brockett, 2010; Iyyer et al., 2018) and obtain quality annotations on a 3 point scale: 0 denotes not a paraphrase, 1 denotes that the input sentence and the generated sentence are paraphrases, but the generated sentence might contain grammatical errors, 2 indicates that the input and the candidate are paraphrases. To emulate the human evaluation design in Iyyer et al. (2018), we sample paraphrases after filtering using the criterion outlined in the previous section and obtain three judgements per sentence and its 9 paraphrase candidates. Table 4 outlines the results from the human evaluation. As we can see, the results indicate Model 2 1 0 SCPN (Iyyer et al., 2018) 35.9 24.8 39.3 Transformer seq2seq 45.1 20.6 34.3 SOW-REAP 44.5 22.6 32.9 Table 4: Human annotated quality across different models. that the quality of the paraphrases generated from our model is substantially better than the SCPN model. 9 Furthermore, similar to quantitative evaluation, the human evaluation also demonstrates that the performance of this model is similar to that of the vanilla sequence-to-sequence model, indicating that the inclusion of target rearrangements do not hurt performance. Next, we intrinsically evaluate the performance of our SOW model (Section 2.3). Specifically, given a budget of 10 reorderings, we want to understand how close our SOW model comes to covering the target ordering. We do this by evaluating the REAP model in terms of oracle perplexity (of the ground truth paraphrase) and oracle BLEU over these 10 orderings. We evaluate our proposed approach against 3 systems: a) Monotone reordering { 1 , 2 , . . . , n } . b) Random permutation, by randomly permuting the children of each node as we traverse down the constituency parse tree. c) Ground Truth , using the pseudo-ground truth rearrangement (outlined in Section 3) between the source and ground-truth target sentence. This serves as an upper bound for the reorderings' performance, as obtained by the recursive phrase-level transducer. 9 The difference of our model performance with SCPN is statistically significant, while that with baseline seq2seq is not according to a paired bootstrap test. Table 5 outlines the results for 10 generated paraphrases from each rearrangement strategy. Our proposed approach outperforms the baseline monotone and random reordering strategies. Furthermore, the SOW model's oracle perplexity is close to that of the ground truth reordering's perplexity, showing that the proposed approach is capable of generating a diverse set of rearrangements such that one of them often comes close to the target rearrangement. The comparatively high performance of the ground truth reorderings demonstrates that the positional embeddings are effective at guiding the REAP model's generation. Finally, we evaluate whether the generated paraphrases follow the target reordering r . Note that we do not expect or want our REAP model to be absolutely compliant with this input reordering since the model should be able to correct for the mistakes make by the SOW model and still generate valid paraphrases. Therefore, we perform reordering compliance experiments on only the monotone reordering and the pseudo-ground truth reorderings ( r  , construction outlined in Section 3), since these certainly correspond to valid paraphrases. For sentences in the test set, we generate paraphrases using monotone reordering and pseudo-ground truth reordering as inputs to REAP . We get the 1-best paraphrase and compute the degree of rearrangement 10 between the input sentence and 10 Quantified by Kendall's Tau rank correlation between original source order and targeted/generated order. Higher the generated sentence. In Figure 5, we plot this as a function of the target degree of rearrangement, i.e., the rearrangement between the input sentence x and the ground truth sentence y  . The dotted line denotes the ideal performance of the model in terms of agreement with the perfect reordering r  . The plot shows that the REAP model performs as desired; the monotone generation results in high Kendall's Tau between input and output. Conditioning on the pseudo-ground truth reorderings ( r  ) produces rearrangements that exhibit the same amount of reordering as the ideal rearrangement. Paraphrase Generation Compared to prior seq2seq approaches for paraphrasing (Hasan et al., 2016; Gupta et al., 2018; Li et al., 2018), our model is able to achieve much stronger controllability with an interpretable control mechanism. Like these approaches, we can leverage a wide variety of resources to train on, including backtranslation (Pavlick et al., 2015; Wieting and Gimpel, 2018; Hu et al., 2019) or other curated data sources (Fader et al., 2013; Lan et al., 2017). Controlled Generation Recent work on controlled generation aims at controlling attributes such as sentiment (Shen et al., 2017), gender or political slant (Prabhumoye et al., 2018), topic (Wang et al., 2017), etc. However, these methods cannot achieve fine-grained control over a property like syntax. Prior work on diverse paraphrase generation can be divided into three groups: diverse decoding, latent variable modeling, and syntax-based. The first group uses heuristics such as Hamming distance or distinct n -grams to preserve diverse options during beam search decoding (Vijayaku-mar et al., 2018; Kumar et al., 2019). The second group includes approaches that use uninterpretable latent variables to separate syntax and semantics (Chen et al., 2019a), perturb latent representations to enforce diversity (Gupta et al., 2018; Park et al., 2019) or condition on latent codes used to represent different re-writing patterns (Xu et al., 2018; An and Liu, 2019). Qian et al. (2019) uses distinct generators to output diverse paraphrases. These methods achieve some diversity, but do not control generation in an interpretable manner. Finally, methods that use explicit syntactic structures (Iyyer et al., 2018; Chen et al., 2019b) may try to force a Kendall's Tau indicates lower rearrangement and vice-versa. sentence to conform to unsuitable syntax. Phrase-level approaches (Li et al., 2019) are inherently less flexible than our approach. Machine Translation Our work is inspired by pre-ordering literature in machine translation. These systems either use hand-crafted rules designed for specific languages (Collins et al., 2005; Wang et al., 2007) or automatically learn rewriting patterns based on syntax (Xia and McCord, 2004; Dyer and Resnik, 2010; Genzel, 2010; Khalilov and Simaan, 2011; Lerner and Petrov, 2013). There also exist approaches that do not rely on syntactic parsers, but induce hierarchical representations to leverage for pre-ordering (Tromble and Eisner, 2009; DeNero and Uszkoreit, 2011). In the context of translation, there is often a canonical reordering that should be applied to align better with the target language; for instance, head-final languages like Japanese exhibit highly regular syntax-governed reorderings compared to English. However, in diverse paraphrase generation, there doesn't exist a single canonical reordering, making our problem quite different. In concurrent work, Chen et al. (2020) similarly use an additional set of position embeddings to guide the order of generated words for machine translation. This demonstrates that the REAP technique is effective for other tasks also. However, they do not tackle the problem of generating plausible reorderings and therefore their technique is less flexible than our full SOW-REAP model. In this work, we propose a two-step framework for paraphrase generation: construction of diverse syntactic guides in the form of target reorderings followed by actual paraphrase generation that respects these reorderings. Our experiments show that this approach can be used to produce paraphrases that achieve a better quality-diversity trade-off compared to previous methods and strong baselines. This work was partially supported by NSF Grant IIS-1814522, a gift from Arm, and an equipment grant from NVIDIA. The authors acknowledge the Texas Advanced Computing Center (TACC) at The University of Texas at Austin for providing HPC resources used to conduct this research. Thanks as well to the anonymous reviewers for their helpful comments.
abstain abstain method objective abstain objective objective abstain other abstain abstain abstain abstain objective abstain method result abstain method result objective result method method abstain method abstain method method method method method abstain method abstain method abstain method abstain abstain method abstain method method abstain abstain method abstain method method method method abstain other abstain method method method method abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain method abstain abstain method abstain method method abstain method abstain method abstain abstain abstain abstain abstain abstain abstain method method abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain method method abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method method method method abstain abstain abstain abstain abstain abstain method other other other other other other other other other abstain abstain other other other abstain other other method objective result other other other