\section{Problem Definition}

Given input $X$ that can be a topic statement, some keywords, or a paper's title, the goal is to produce a paragraph $Y$ consisting of {multiple sentences} as a story, a news article, or a paper's abstract.
Suppose $Y$ has $T$ sentences, denoted by $Y= [Y_1, \cdots, Y_T]$, where $Y_t$ is the $t$-th sentence. $T$ can be easily obtained from training data
to create sentence indices. During testing, models are expected to predict the sentence indices under maximum $T$ (i.e., 10).

\subsection{Sentence-Level Transformer}

Transformer~\cite{vaswani2017attention} follows the encoder-decoder architecture~\cite{sutskever2014sequence} and uses stacked multi-head self-attention and fully connected layers for both the encoder and decoder.
For simplicity, we represent the Transformer framework at the sentence level by using a recurrent notation that generates a probability distribution for sentence prediction by attending to both input $X$ and previous decoded sentences $Y_{<t}$.
\begin{align}

     p(Y_t) = \mathrm{Transformer}(X, Y_{<t}).
\end{align}

\noindent where $Y_{t}$ and $Y_{<t}$ are the $t$-th sentence and sentences \textit{before} $t$-th sentence under the left-to-right manner in target output.
Transformer eschews recurrence and instead relies on the self-attention mechanism to draw global dependencies between the input and output. During the decoding phase, Transformer can predict each token based on both the input and previously predicted tokens via attention masks to improve efficiency.
The objective of Transformer is to maximize the likelihood under the forward autoregressive factorization:
\begin{align}
    p(Y|X; \theta) = \prod^{T}_{t=1} p(Y_t|Y_{< t}, X; \theta) .
\label{eq:Seq2Seq-loss}
\end{align}

\section{Proposed Method: \textit{PermGen}}

In a left-to-right generation scheme such as the canonical Seq2Seq design, each generated token is conditioned on left-side tokens only~\cite{sutskever2014sequence}. It ignores contextual dependencies from the right side. It also leads to limited diversity of generated text (as shown in Figure \ref{fig:intro}).
To solve this problem, our \textit{PermGen}, a novel sentence-permuted paragraph generation model, produces sentences not confined to the left-to-right order. Instead, \textit{PermGen} attempts different sentence orders and selects the best-ranked output candidate.

As shown in Figure \ref{fig:framework}, \textit{PermGen} uses the Transformer encoder but changes the sentence orders during the decoding phase. It should be noted that \textit{PermGen} follows the left-to-right manner when generating tokens in each sentence. Thus, we represent the Transformer decoder as:
\begin{align}
    {Y_{\pi_t} = \mathrm{Transformer}(X, Y_{\pi_{<t}}, \pi),}
\label{eq:TransEncoder_2}
\end{align}
where $Y_{\pi_t}$ and $Y_{\pi_{<t}}$ are the $t$-th sentence and the sentences \textit{before} the $t$-th sentence under the permuted order $\pi$ in the target output. Taking the first permuted order in Figure \ref{fig:framework} as an example, we have $\pi=[2, 1, 3]$, $\pi_1=2$,  $\pi_3=3$, $\pi_{<3}=[2, 1]$.

We note that as \textit{PermGen} is based on the encoder-decoder Transformer architecture, which can be initialized either randomly or from a pre-trained Transformer model with the same structure. For example, in the experiments, we evaluate \textit{PermGen} which is i) trained from scratch, and ii) initialized with BART \citep{lewis2019bart}.
Next, we will introduce three modules of \textit{PermGen}: (1) hierarchical positional embedding, (2) sentence-permuted learning, and (3) sentence-based decoding.

\subsection{Hierarchical Positional Embedding}

In Transformer, positional embeddings are added to every token's embedding. Traditionally, the positional embedding encodes the absolute position from 1 to the sequence length to model how a token at one position attends to tokens at other positions~\cite{vaswani2017attention,lewis2019bart}.

We propose the hierarchical positional embedding
that consists of a global position and a local position. Given a token, the global position is the position (index) of the sentence that contains this token; the local position is the position of the token in the sentence (see the two lines of position numbers in Figure \ref{fig:framework}). Given a paragraph $Y$, its embedding matrix is given below, where rows are its tokens and columns are embedding dimensions:
\vspace{-0.2in}
\begin{align}
    \textbf{Y} = \textbf{Y}_{\text{token}} + \textbf{Y}_{\text{global\_position}} + \textbf{Y}_{\text{local\_position}},
\end{align}
where $\textbf{Y}_{\text{token}}$ is the token embedding, $\textbf{Y}_{\text{global\_position}}$ and $\textbf{Y}_{\text{local\_position}}$ are the global positional embeddings and local positional embeddings.

Compared to the absolute positional embedding, the hierarchical positional embedding has two advantages.
First, the embedding of two-level positions is more informative about the paragraph structure than that of the absolute position.
Second, when we permute the sentence orders in paragraph generation, the absolute positions of tokens might not be available.
For example, if the second sentence is generated earlier than the first sentence, the absolute positions of its tokens cannot be determined because the length of the first sentence is unknown. In comparison, hierarchical position does not have this issue.

In addition, for the $t$-th sentence in $Y$, we add two special tokens (i.e., <B-$t$> and <E-$t$>) to indicate the beginning and end of the sentence.
Thus, the decoder can determine the sentence index based on the predicted special tokens.
We also append a special token <EOP> to the paragraph to indicate the end of the generation process.

\begin{figure*}[ht]
    \centering
    {\includegraphics[width=1.0\textwidth]{Figures/inference.pdf}}
    \vspace{-0.25in}
    \caption{The decoding process during inference as described in Section \ref{sec:decode}. Note that the first special token (e.g., <B-2>) is sampled from \{<B-$t$>\}$_{t=1}^{T}$.
    For simplicity, positional embedding is omitted in the figure. }
    \label{fig:inference}

\end{figure*}

\subsection{Sentence-permuted Learning}

This module learns by varying sentence orders in paragraph generation and acts as the key component in \textit{PermGen}. For example, given a sentence order $\pi = [2, 4, 1, 5, 3]$, \textit{PermGen} first generates the second sentence from the leftmost token to the rightmost, then generates the fourth sentence, and so on. The model stops when the third sentence is finished. Formally, we denote $Z_T$ as the set of all possible sentence orders, i.e., the permutations of sentence indices of length $T$. It follows that $|Z_T| = T!$.
Given input $X$ and target output paragraph $Y$ of $T$ sentences, \textit{PermGen} maximizes the following likelihood:
\vspace{-0.05in}
\begin{align}
    p(Y|X;\theta) &= \sum_{\pi \in Z_T} p (Y|X, \pi; \theta) \nonumber \\
    & = \sum_{\pi \in Z_T}\prod_{t=1}^T p (Y_{\pi_t}|X, Y_{\pi_{<t}}; \theta)
    \label{eq:original-loss}
\end{align}
However, computing the negative log-likelihood in Eq. (\ref{eq:original-loss}) is prohibitive because
the back-propagation computational graph branches out for every permutation in the sum.
Therefore, we apply the Jensen's inequality to lower-bound the log-likelihood:
\vspace{-0.1in}
\begin{align}
     & \scale[0.98]{\log p(Y|X;\theta)} \scale[0.98]{=}~ \scale[0.98]{\log \sum\limits_{\pi \in Z_T} \prod\limits_{t=1}^{T} p (Y_{\pi_t}|X, Y_{\pi_{<t}}; \theta)} \nonumber \\
     \scale[0.98]{\geq}~& \scale[0.98]{\log (|Z_T|) + \frac{1}{|Z_T|} \sum\limits_{\pi \in Z_T} \sum\limits_{t=1}^{T} \log p (Y_{\pi_t}|X, Y_{\pi_{<t}}; \theta)}\label{eq:new-loss} \nonumber
\end{align}
By maximizing the lower bound, we do not favor any particular sentence order, but encourage the model to generate $Y$ equally well in all orders.

Note that maximizing this lower bound is equivalent to minimizing the following expectation:
\vspace{-0.1in}
\begin{equation}
     \mathcal{J}(\theta)=  \mathbb{E}_{\pi^\prime} \Big{[}-\sum_{t=1}^{T} \log p (Y_{\pi^\prime_t}|X, Y_{\pi^\prime_{<t}}; \theta) \Big{]}. \label{eq:upper-b}
\end{equation}

Although computing this expectation is still intractable, we apply the $\pi$-SGD~\cite{murphy2019janossy} stochastic optimization, which randomly samples a permutation for gradient computation each time.

\begin{definition}
    ($\pi$-SGD): Let $\mathcal{B} = \{(X^{(1)}, Y^{(1)}), $ $ \cdots ,(X^{(B)}, Y^{(B)})\}$ be a mini-batch i.i.d. sampled uniformly from the training data $D$. At step $t$, consider the stochastic gradient descent update
    \vspace{-0.1in}
    \begin{equation}
        \theta_t = \theta_{t-1} - \eta_t G_t,
        \label{eq:pi-sgd}
    \end{equation}
    where $ G_t= - \frac{1}{B} \sum_{i=1}^{B} \nabla_\theta \sum_{t=1}^{T} \log p (Y^{(i)}| X^{(i)}, $ $\pi^\prime; \theta)$ is the gradient, and random permutations $\{\pi^\prime_i\}_{i=1}^B$ are sampled independently: $\pi^\prime_i \sim \mathrm{Uniform}(Z_T^{(i)})$. Besides, the learning rate is $\eta_t \in (0, 1)$ s.t. $\rm{lim}_{t \rightarrow \infty} \eta_t = 0 $, and $\sum_{t=1}^{\infty} \eta_t^{2} < \infty$.
    \label{def:pi-sgd}
\end{definition}

\vspace{0.02in}
We note that $\pi$-SGD is a Robbins-Monro stochastic approximation of gradient descent~\cite{robbins1951stochastic}. When it's applied to permutation sampling, the optimization almost surely converges to the optimal $\theta$, as implied by the following proposition.

\begin{proposition}
    ($\pi$-SGD Convergence): The optimization of $\pi$-SGD converges to the optimal $\theta$ for $\mathcal{J}(\theta)$ in Eq. (\ref{eq:upper-b}) with probability one.
    \label{proposition:convergence}
\end{proposition}
Proof: We refer to Prop.2.2 in \citet{murphy2019janossy}.

\subsection{Sentence-based Decoding}

\label{sec:decode}
\noindent In decoding, \textit{PermGen} adopts the following steps:
\vspace{0.02in}
\begin{compactitem}
  \item \textit{Step 1:} Initialize a set of indices of sentences that have been generated: $I = \{\}$;
  \item \textit{Step 2:} If $I = \{\}$, sample a token from \{<B-$t$> $\mid$ $t$ $\in$ \{1, $\dots$, $T$\}\}\footnote{When trying to generate multiple candidates, we use the sampling without replacement strategy. For example, if we need to generate 3 candidates each with 5 sentences, their beginning tokens can be B-1, B-3 and B-4, respectively. }; otherwise, predict a token from \{<B-$t$> $\mid$ $t$ $\in$ \{1, $\dots$, $T$\}$\setminus I$\} $\cup$ \{<EOP>\}. If the token is <EOP>, end; otherwise, append <B-$t$> to the generated text;
  \item \textit{Step 3:} Generate tokens from $\mathcal{V}\cup\{$<E-$t$>$\}$ for the $t$-th sentence in an autoregressive way, where $\mathcal{V}$ is the set of normal text tokens. Stop when <E-$t$> is generated;
  \item \textit{Step 4:} $I \leftarrow I\cup\{t\}$, then go back to Step 2.
\end{compactitem}

\vspace{0.02in}

As stated in \textit{step 2}, when <EOP> is generated, the whole generation ends. Then, the sentences in the generated paragraph can be reordered according to sentence indices $I$ and special tokens.
Note that in \textit{step 3}, since \textit{PermGen} adopts autoregressive generation, it can employ any decoding strategy such as beam search or sampling algorithm (e.g. truncated sampling~\cite{fan2018hierarchical}, nucleus sampling~\cite{holtzman2020curious}). For example, truncated sampling samples the next word from the top $k$ probable choices, instead of aiming to decode text by maximizing the likelihood.

\vspace{0.02in}
\noindent\textbf{Rank with log-probability.}
We compute the log-likelihood of each candidate as the same as in beam search~\cite{vijayakumar2016diverse} and sampling methods~\cite{holtzman2020curious}:
\begin{align}
    S_\text{prob}(Y) =

    \frac{1}{L} \sum_{l=1}^{L} \log p(y_{l}|y_1, \cdots, y_{l-1})
    \label{eq:beam-prob}
\end{align}
where $L$ is the total number of tokens in $Y$ and $y_l$ is the $l$-th token in generated paragraph $Y$.

\vspace{0.02in}
\noindent\textbf{Complexity reduction.}
Since the number of possible sentence orders grows as $n!$ for a $n$-sentence paragraph, exact inference is an extremely time consuming process. To reduce the complexity during inference, we
employ an approximate inference by taking advantage of the special token prediction mentioned in \textit{step 2}.
The special token prediction happens when a end-of-sentence (i.e., <E-$t$>) is generated. Instead of traversing each remaining possible sentence index, the model only chooses the most likely sentence index through special token predictions.
It should be noted that we reuse the classifier in decoder by simply masking tokens \textit{not in} \{<B-$t$>\}$_{t=1}^T$, without training any new classifiers.
Therefore, the decoding time is roughly linear in the number of candidates to be generated.
See empirical analysis in Section \ref{sec:time}.

\subsection{Tasks and Benchmarks}

\paragraph{Task 1: Story generation} In this task, models learn to generate story paragraphs from the title and multiple keywords.
We use ROCStories dataset~\cite{mostafazadeh2016corpus} and follow the same data preparation as in~\citet{yao2019plan}.
ROCStories has 98,162 / 9,817 / 9,803 paragraphs for training / development / test sets. The stories in the corpus
capture causal and temporal commonsense relations between daily events

\vspace{-0.01in}
\paragraph{Task 2: Paper abstract generation} In this task, models need to generate paper abstracts from paper title and a list of keywords. We use the AGENDA dataset~\cite{koncel2019text} that consists of 40,720 paper titles and abstracts in the Semantic Scholar Corpus taken from the proceedings of 12 AI conferences. Each abstract is paired with several keywords. We follow the settings in~\citet{koncel2019text} to directly generate paper abstracts from the keywords. We follow the same data partition, which has 38,720 / 1,000 / 1,000 for training / development / test sets, respectively.

\vspace{-0.01in}
\paragraph{Task 3: News generation} In this task, models are trained to generate news articles from a list of keyphrases. We use DailyMail dataset~\cite{see2017get}, a corpus of online news articles. We randomly sample 53,102 news articles and extract keyphrases from each sentence using RAKE~\cite{rose2010automatic}. It contains 49,102 / 2,000 / 2,000 news articles for training / development / test sets.

\begin{table}[t]
\caption{Statistics of three datasets. ``in/out'' stands for input/output and ``sents'' stands for sentences.}
\vspace{-0.15in}
\begin{center}
\setlength{\tabcolsep}{2mm}{
\scalebox{0.87}{\begin{tabular}{l|c|c|c}
\toprule
Dataset & ROCStories & AGENDA & DailyMail \\
\midrule
\# Train & 98,162 & 38,720 & 49,102 \\
\# Dev. & 9,817 & 1,000 & 2,000 \\
\# Test & 9,803 & 1,000 & 2,000 \\
Title in input & $\surd$ & $\surd$ & $\times$ \\
Avg.in.words & 9.65 & 16.09 & 7.91 \\
Avg.out.words & 50.16 & 76.12 & 95.62 \\
Avg.out.sents & 4.92 & 3.08 & 3.88 \\
\bottomrule
\end{tabular}}}
\label{tab:datasets}
\end{center}
\end{table}

\subsection{Baseline Methods}

We compare with three pre-trained Transformer-based models: BART~\cite{lewis2019bart}, T5~\cite{raffel2020exploring} and BERTGen~\cite{rothe2020leveraging}. These models have demonstrated state-of-the-art performance in various tasks. We also compare with GPT-2~\cite{radford2019language}
and two recent non-autoregressive generation models: BLM~\cite{shen2020blank} and POINTER~\cite{zhang2020pointer}.

\paragraph{BLM}~\cite{shen2020blank} Blank Language Model (BLM) generates sequences by dynamically creating and filling in blanks. The blanks control which part of the sequence to fill out, making it ideal for word-to-sequence expansion tasks.

\paragraph{POINTER}~\cite{zhang2020pointer} POINTER operates by progressively inserting new tokens between existing tokens in a \textit{parallel} manner. This procedure is recursively applied until a sequence is completed. This coarse-to-fine hierarchy makes the generation process intuitive and interpretable.

\begin{table*}[htb]
\begin{center}
\caption{Diversity (``Dist-2'': Distinct-2($\Uparrow$), ``Self-B-4'': Self-BLEU-4($\Downarrow$)) and accuracy (``B-4'': BLEU-4($\Uparrow$)) for \textit{PermGen} and baseline methods. Diversity evaluation is calculated by top-k generated candidates from \textit{beam search}. More evaluation results (e.g., METEOR, CIDEr, Entropy) are in Table \ref{tab:table1-value} in Appendix.
}
\vspace{-0.1in}
\setlength{\tabcolsep}{1mm}{
\scalebox{0.83}{\begin{tabular}{lc||cc|c|cc|c|cc|c}
\toprule
{\multirow{3}*{Methods}} &
{\multirow{3}*{\makecell[c]{Pre-\\Train}}}  & \multicolumn{3}{c|}{\textbf{ROCStories}} & \multicolumn{3}{c|}{\textbf{AGENDA}} & \multicolumn{3}{c}{\textbf{DailyMail}} \\
& & \multicolumn{2}{c|}{Diversity} & \multicolumn{1}{c|}{Accuracy} & \multicolumn{2}{c|}{Diversity} & \multicolumn{1}{c|}{Accuracy} & \multicolumn{2}{c|}{Diversity} & \multicolumn{1}{c}{Accuracy} \\
\cmidrule{3-11}
& & Dist-2($\Uparrow$) & Self-B-4($\Downarrow$) & B-4($\Uparrow$) & Dist-2($\Uparrow$) & Self-B-4($\Downarrow$) & B-4($\Uparrow$) & Dist-2($\Uparrow$) & Self-B-4($\Downarrow$) & B-4($\Uparrow$) \\
\midrule
POINTER & $\surd$ & 0.0743 & 0.9405 & 0.0492 & 0.1898 & 0.9267 & 0.0379 & 0.1228 & 0.9619 & 0.0243 \\
BLM & $\surd$ & 0.0560 & 0.9573 & 0.1477 & 0.1465 & 0.9396 & 0.1679 & 0.0831 & 0.9889 & 0.1164 \\
GPT-2 & $\surd$ & \underline{0.0915} & \underline{0.9194} & 0.0726 & 0.1665 & 0.9331 & 0.1247 &  \underline{0.1577} & \underline{0.9287} & 0.1072 \\
BERTGen & $\surd$ & 0.0672 & 0.9456 & 0.1576 & 0.1463 & 0.9356 & 0.1462 & 0.1167 & 0.9774 & 0.1728 \\
T5 & $\surd$ & 0.0684 & 0.9403 & 0.1895 & 0.1323 & 0.9421 & 0.1688 & 0.1086 & 0.9779 & 0.1529 \\
Transformer & $\times$ & 0.0806 & 0.9341 & 0.1809 & 0.1489 & \underline{0.9265} & 0.1540 & 0.1109 & 0.9678 & 0.1496 \\
BART & $\surd$ & 0.0839 & 0.9330 & \underline{0.2445} & \underline{0.1697} & 0.9278 & \underline{0.1922} & 0.1306 & 0.9720 & \underline{0.1935} \\
\midrule
{\multirow{2}*{\textit{PermGen}}} & $\times$ & 0.0992 & 0.8548 & 0.1848 & 0.2203 & \textbf{0.5679} & 0.1678 & 0.1934 & 0.7757 & 0.1592\\
& $\surd$ & \textbf{0.1059} & \textbf{0.7993} & \textbf{0.2482} & \textbf{0.2492} & 0.5940 & \textbf{0.2059} & \textbf{0.2065} & \textbf{0.6627} & \textbf{0.1991} \\
\bottomrule
\end{tabular}}}
\label{tab:baseline}
\end{center}
\vspace{-0.1in}
\end{table*}

For each task, we evaluate \textit{PermGen} with three diversity promoting methods for decoding including Beam search, Truncated sampling~\cite{fan2018hierarchical}, and Nucleus sampling~\cite{holtzman2020curious}. For each method, we select the top-3 candidate paragraphs for comparison.

\paragraph{Truncated Sampling}~\cite{fan2018hierarchical} It randomly samples words from top-k candidates of the distribution at the decoding step.

\paragraph{Nucleus Sampling}~\cite{holtzman2020curious}  It avoids text degeneration by truncating the unreliable tail of the probability distribution, sampling from the dynamic nucleus of tokens containing the vast majority of the probability mass.

\vspace{0.02in}
Implementation details is in Appendix \ref{sec:implement}.

\subsection{Implementation Details}
\label{sec:implement}

We use pre-trained parameters from BART-base~\cite{lewis2019bart} to initialized our model, which takes a maximum 512 input token sequence and consists of a 6-layer transformer encoders and another 6-layer transformer decoders~\cite{vaswani2017attention} with 12 attention heads and 768 word dimensions. For model fine tuning, we use Adam with learning rate of 3e-5, L2 weight decay of 0.01, learning rate warm up over the first 10,000 steps, and linear decay of learning rate. Our models are trained with a 4-card 32GB memory Tesla V100 GPU, and implemented on PyTorch with the Huggingface's Transformer~\cite{wolf2020transformers}.

\begin{figure*}[t]
    \centering
    {\includegraphics[width=1.0\textwidth]{Figures/eval-legend.pdf}} \\
    \vspace{0.08in}
    {\includegraphics[width=1.0\textwidth]{Figures/eval-legend-2.pdf}} \\
    \vspace{-0.1in}
    \subfigure[Self-BLEU-3($\Downarrow$)]
    {\includegraphics[width=0.328\textwidth]{Figures/self-bleu-3.pdf}}
    \vline
    \subfigure[Distinct-2($\Uparrow$)]
    {\includegraphics[width=0.328\textwidth]{Figures/distinct-2.pdf}}
    \vline
    \subfigure[Top1-BLEU-4($\Uparrow$)]
    {\includegraphics[width=0.328\textwidth]{Figures/top1-bleu-4.pdf}} \\
    \subfigure[Self-BLEU-4($\Downarrow$)]
    {\includegraphics[width=0.328\textwidth]{Figures/self-bleu-4.pdf}}
    \vline
    \subfigure[Entropy-4($\Uparrow$)]
    {\includegraphics[width=0.328\textwidth]{Figures/entropy-4.pdf}}
    \vline
    \subfigure[Oracle-BLEU-4($\Uparrow$)]
    {\includegraphics[width=0.328\textwidth]{Figures/oracle-bleu-4.pdf}}
    \vspace{-0.1in}
    \caption{\textit{PermGen} demonstrates superior performance on both diversity and accuracy compared with different diversity-promoting methods. The specific values involved in the figure are shown in Table \ref{tab:appendix-top1} in Appendix.}
    \label{fig:diversity-and-acc}
\end{figure*}

\begin{figure*}[t]
    \centering
    {\includegraphics[width=1.0\textwidth]{Figures/nSeq-legend.pdf}}
    \subfigure[ROCStories]
    {\includegraphics[width=0.3285\textwidth]{Figures/nSeq-ROCStories.pdf}}
    \vline
    \subfigure[AGENDA]
    {\includegraphics[width=0.3285\textwidth]{Figures/nSeq-AGENDA.pdf}}
    \vline
    \subfigure[DailyMail]
    {\includegraphics[width=0.3285\textwidth]{Figures/nSeq-DailyMail.pdf}}
    \vspace{-0.1in}
    \caption{\textit{PermGen} generates more diverse paragraphs over different number of sampled candidates. The diversity measured at each point is the mean value of Dist-$2$ and Ent-$4$ when $k=10$, $k=50$, $p=.75$, and $p=.95$.}
    \label{fig:diverse}
    \vspace{-0.1in}
\end{figure*}

\begin{figure}[t]
    \centering

    {\includegraphics[width=0.46\textwidth]{Figures/time.pdf}}
    \vspace{-0.1in}
    \caption{Time Efficiency. \textit{PermGen} enjoys faster decoding efficiency than BART (with beam search) when generating multiple output paragraphs. }
    \label{fig:time}
    \vspace{-0.1in}
\end{figure}

\subsection{Evaluation Metrics}

\vspace{-0.02in}
We use metrics introduced in previous work~\cite{ott2018analyzing,vijayakumar2018diverse,zhu2018texygen} to evaluate accuracy and diversity.

\vspace{-0.03in}
\subsubsection{Accuracy metrics}
\paragraph{Top-1 metric ($\Uparrow$).} This measures the Top-1 accuracy among the generated hypotheses. The accuracy is measured using corpus-level metrics, including BLEU~\cite{papineni2002bleu}, METEOR~\cite{banerjee2005meteor}, and CIDEr~\cite{vedantam2015cider}.

\vspace{-0.03in}
\paragraph{Oracle metric ($\Uparrow$).} This measures the highest accuracy comparing the best hypothesis among the top-$K$ with the target~\cite{ott2018analyzing,vijayakumar2018diverse}. Concretely, we generate hypotheses $\{{\hat{Y}^{(1)}, \cdots \hat{Y}^{(K)}}\}$ from each source $X$ and keep the hypothesis $\hat{Y}^{\text{best}}$ that achieves the best sentence-level metric with the target $Y$. Then we calculate a corpus-level metric with the greedily-selected hypotheses $\{{Y^{(i),\text{best}}\}}^N_{i=1}$ and references $\{{Y^{(i)}}\}^N_{i=1}$.

\vspace{-0.03in}
\subsubsection{Diversity metrics}
\paragraph{Corpus diversity ($\Uparrow$).}

Distinct-$k$~\cite{li2016diversity} measures the total number of unique $k$-grams normalized by the total number of generated $k$-gram tokens to avoid favoring long sentences. Entropy-$k$~\cite{zhang2018generating} reflects how evenly the empirical $k$-gram distribution is for a given sentence when word frequency is taken into account (i.e. low weights for high-frequency words).

\vspace{-0.03in}
\paragraph{Pairwise diversity ($\Downarrow$).} Referred as ``self-'' (e.g., self-BLEU)~\cite{zhu2018texygen}, it measures the within-distribution similarity. This metric computes the average of sentence-level metrics between all pairwise combinations of hypotheses $\{{Y^{(1)}, \cdots, Y^{(K)}}\}$ generated from each source sequence $X$. Lower pairwise metric indicates
high diversity between generated hypotheses.

\begin{table*}[t]
\caption{Case study. \textit{PermGen} produces more diverse stories than beam search and nucleus sampling. We shade parts of the generated text which are distinct from other candidates. We provide more case studies in Appendix.}
\vspace{-0.1in}
\scalebox{0.81}{
{\begin{tabular}{p{19.6cm}}
\toprule
$\bullet$ \textbf{Inputs:} (Title) Mounting popularity ; (Keywords) started, company, friends, hard, year, slogging, reward, traction, excited \\
\midrule
$\bullet$ \textbf{Beam search-1:} I started a new company with some friends . It was hard at first . After a year of slogging , I got a reward . The reward was a lot of traction . Now we are all excited \hlt{to start working together .} \\
$\bullet$ \textbf{Beam search-2:} I started a new company with some friends . It was hard at first . After a year of slogging , I got a reward . The reward was a lot of traction . Now we are all excited . \\
$\bullet$ \textbf{Beam search-3:} I started a new company with some friends . It was hard at first . After a year of slogging , I got a reward . The reward was a lot of traction . We are excited \hlt{to keep doing this .} \\
\midrule
$\bullet$ \textbf{Nucleus sampling-1:} I started a new company with some friends . It was hard at first . After a year of slogging , the reward was a lot of traction . \hlt{Now we are doing really well .} I am excited \hlt{to start working with my friends .} \\
$\bullet$ \textbf{Nucleus sampling-2:} I started a new company with some friends . It was hard at first . After a year of slogging , I got a lot of reward . The reward was a lot of traction . Now we are all excited \hlt{to start working together .} \\
$\bullet$\textbf{ Nucleus sampling-3:}  I started a new company with \hlt{my} friends . It was hard at first . After a year of slogging , we got a lot of reward . \hlt{We got traction and are doing really well .}  We are excited \hlt{to keep doing this .} \\
\midrule
$\bullet$ \textbf{PermGen-1 (reordered from [2, 1, 3, 5, 4]*):} I started a new company with some friends . \hlt{I tried really hard for almost a year .} \hlt{It took a lot of slogging , but as a reward I got traction .} \hlt{Now we are all doing it together .} I 'm excited \hlt{to be doing it again .} \\
$\bullet$ \textbf{PermGen-2 (reordered from [3, 1, 2, 5, 4]):} I started a new company with some friends . \hlt{It 's been hard .} \hlt{I 've been slogging through it as a reward for getting traction .} \hlt{My friends are really excited .} I 'm excited \hlt{to see what it 's all about .} \\
$\bullet$ \textbf{PermGen-3 (reordered from [5, 1, 2, 3, 4]):} I started a new company with some \hlt{of my} friends . \hlt{It was hard at first .} \hlt{After a year of slogging , I got a lot of reward .} \hlt{I have many traction on social media .} I am excited \hlt{to start working with my friends .} \\
\bottomrule
* ``Reordered from [2, 1, 3, 5, 4]'' means that PermGen first generates the 2$^{\text{nd}}$ sentence, and then generates the 1$^{\text{st}}$ sentence, and so on. Finally, we reorder the generated story according to the ascending order of sentence index as shown in Figure \ref{fig:inference}.
\end{tabular}}}
\label{tab:case1}
\end{table*}

\begin{table}[t]
\begin{center}
\caption{Human Evaluations on ROCStories: \textit{PermGen} (ours) v.s. three baseline methods based on \textit{diversity}. }
\vspace{-0.1in}
\scalebox{0.85}{\begin{tabular}{l||ccc}
\toprule
 & Win & Lose & Tie  \\
\midrule
{\multirow{1}*{\textit{PermGen}}}  & \textbf{64.00\%} & 14.00\% & 22.00\% \\
{\multirow{1}*{v.s. Beam}} & ($\pm$12.71\%) & ($\pm$7.70\%) & ($\pm$10.73\%)\\
\midrule
{\multirow{1}*{\textit{PermGen}}} & \textbf{54.80\%} & 8.80\% & 36.40\% \\
{\multirow{1}*{v.s. Truncated}} & ($\pm$4.10\%) & ($\pm$5.31\%) & ($\pm$5.43\%) \\
\midrule
{\multirow{1}*{\textit{PermGen}}} & \textbf{56.00\%} & 11.60\% & 32.40\%  \\
{\multirow{1}*{v.s. Nucleus}} & ($\pm$8.67\%) & ($\pm$4.27\%) & ($\pm$5.57\%)\\
\bottomrule
\end{tabular}}
\label{tab:human-eval}
\end{center}
\end{table}

\begin{table}[h]
\begin{center}
\caption{Human Evaluations of \textit{PermGen} and BART on ROCStories. \textbf{Decoding algorithm is beam search.} Minimum score is 1.0, and maximum score is 5.0. }
\vspace{-0.1in}
\setlength{\tabcolsep}{3.5mm}{\scalebox{0.86}{\begin{tabular}{l||ccc}
\toprule
 & Accuracy & Fluency & Coherency \\
\midrule
BART & 3.34 & 3.93 & 3.85 \\
\textit{PermGen} & \textbf{3.42} & \textbf{3.97} & \textbf{3.88} \\
\bottomrule
\end{tabular}}}
\label{tab:human-eval-2}
\end{center}
\end{table}

\subsection{Experimental results}

\subsubsection{\textit{PermGen} v.s. Transformers}

As shown in Table \ref{tab:baseline}, \textit{PermGen} can improve both the diversity and the accuracy of generated text when initialized with either non-pretrained (Transformer) or pre-trained (BART) Transformers. For example, compared with BART which has the best performance among baselines, \textit{PermGen} reduced Self-BLEU-4 by 43.2\% and improved BLEU-4 by +1.5\% on AGENDA. And we observe similar improvement on all other paragraph generation tasks.

POINTER achieves the lowest performance in paragraph generation tasks. This is because its insertion operation ignores dependency between generated words so it cannot well capture the inter-sentence coherence during long-text generation.

\textit{\textbf{It should be noted that}} since BART performed the best among all baseline methods, we apply \textit{PermGen} on BART in the following evaluations.

\subsubsection{\textit{PermGen} v.s. Decoding Methods}

We investigate the quality of text generated by \textit{PermGen} (built on BART) when coupled with beam search, truncated sampling and nucleus sampling. Figure \ref{fig:diversity-and-acc} shows that on average, \textit{PermGen} can significantly boost diversity by 5.81\% in Self-BLEU-3 and 6.83\% in Self-BLEU-4, respectively, and improve accuracy by +1.2\% and +1.5\% in terms of Top1-BLEU-4 and Oracle-BLEU-4.

As the diversity of generated text depends on the number of produced candidates, we compare the diversity of generation between BART and \textit{PermGen} with various number of output candidates, $K$.
Figure~\ref{fig:diverse} shows that as $K$ increases, \textit{PermGen} can consistently generate more diverse content, measured by the ratio of distinct 2-grams, Distinct-2 (dashed line).
Meanwhile, measured by Entropy-4 (solid line), the proportion of novel words in generated candidates from \textit{PermGen} is rising as $K$ increases, while BART shows a flat or even falling trend.

\subsubsection{Human Evaluations}

We sample 100 inputs from ROCStories test set and each evaluated method generates top-3 stories.
Every story is assigned to five annotators with NLP background.
For diversity, the annotators are given two sets of top-3 stories from two methods each time and instructed to pick the set that is more diverse. The choices are ``win,'' ``lose,'' or ``tie.''
Then, the annotators give an accuracy score from 1 to 5 to measure semantic similarity between the top-1 generated story and ground truth story. Finally, the annotators need to give a fluency and coherency score from 1 to 5 for each generated story.

Table~\ref{tab:human-eval}-\ref{tab:human-eval-2} demonstrate that \textit{PermGen} outperforms beam search in both accuracy and fluency, while significantly improving generation diversity compared with other diversity-promoting methods.

\subsubsection{Time Efficiency}
\label{sec:time}

We vary the number of generated paragraphs to examine the decoding time of BART (with beam search) and \textit{PermGen}. We calculate the average decoding time of a batch whose size is set as 16. The two models are run on a 32GB memory Tesla V100 GPU.
As shown in Figure \ref{fig:time}, \textit{PermGen} enjoys faster decoding efficiency than BART when generating multiple paragraphs. This is because when generating multiple paragraphs, beam search has to spend time on ranking the generated candidates at each decoding step. However, in \textit{PermGen}, the generation processes for different sentence orders are independent.

\subsubsection{Case Study}

Table \ref{tab:case1} demonstrates generated stories from different diversity-promoting methods, including beam search, nucleus sampling and our \textit{PermGen}. Overall, we observe that \textit{PermGen} can generate more diverse stories than the other two methods. We notice that stories generated by beam search often differ only by punctuation and minor morphological variations, and typically only the last sentence (or last several words) is different from others. Nucleus sampling achieves better diversity than beam search, but the stories are still following similar storylines. In comparison, \textit{PermGen} can generate semantically richer and more diverse contents.

\section{Proofs}

\begin{table*}[t]
\begin{center}
\caption{Ablation study. Hi-BART represents BART with hierarchical positional embeddings.}
\vspace{-0.05in}
\setlength{\tabcolsep}{2.9mm}{\scalebox{0.88}{\begin{tabular}{l|cccc|ccc}
\toprule
{\multirow{2}*{Method}} & \multicolumn{4}{c|}{Accuracy} & \multicolumn{3}{c}{Diversity} \\
\cmidrule{2-8}
& BLEU-3$\Uparrow$ & BLEU-4$\Uparrow$ &  METEOR$\Uparrow$ & CIDEr$\Uparrow$ &  Dist-2$\Uparrow$ & Entropy-4$\Uparrow$ &  Self-BLEU-4$\Downarrow$  \\
\midrule
\rowcolor{gray!12} \multicolumn{8}{c}{AGENDA} \\
\midrule
BART & 0.2539 & 0.1922 & 0.2418 & 0.7982 & 0.1697 & 10.5333 & 0.9476 \\
Hi-BART & 0.2357 & 0.1780 & 0.2334 & 0.6316 & 0.1673 & 10.4012 & 0.9503 \\
\textit{PermGen} & \textbf{0.2719} & \textbf{0.2059} & \textbf{0.2500} & \textbf{0.8175} & \textbf{0.2492} & \textbf{11.1911} & \textbf{0.6173} \\
\midrule
\rowcolor{gray!12} \multicolumn{8}{c}{DailyMail} \\
\midrule
BART & 0.2534 & 0.1935 & 0.2390 & 0.7252 & 0.1306 & 11.8704 & 0.9778 \\
Hi-BART & 0.2481 & 0.1899 & 0.2360 & 0.5528 & 0.1289 & 11.7001 & 0.9765 \\
\textit{PermGen} & \textbf{0.2586} & \textbf{0.1991} & \textbf{0.2390} & \textbf{0.7549} & \textbf{0.2065} & \textbf{12.4793} & \textbf{0.6701} \\
\midrule
\rowcolor{gray!12} \multicolumn{8}{c}{ROCStories} \\
\midrule
BART & 0.3143 & 0.2445 & 0.2744 & 1.6165 & 0.0839 & 12.4204 & 0.9330 \\
Hi-BART & 0.3059 & 0.2349 & 0.2709 & 1.6571 & 0.0812 & 12.2998 & 0.9356 \\
\textit{PermGen} & \textbf{0.3196} & \textbf{0.2482} & \textbf{0.2769} & \textbf{1.7385} & \textbf{0.1059} & \textbf{12.8034} & \textbf{0.7247} \\
\bottomrule
\end{tabular}}}
\label{tab:table1-value}
\end{center}
\end{table*}

\begin{table*}[t]
\begin{center}
\caption{Extension of Table \ref{tab:baseline}. Accuracy results for \textit{PermGen} and baseline methods.}
\vspace{-0.05in}
\setlength{\tabcolsep}{3mm}{\scalebox{0.90}{\begin{tabular}{lc|ccccccc}
\toprule
{\multirow{1}*{Method}} & Pre-train & BLEU-1$\Uparrow$ & BLEU-2$\Uparrow$ & BLEU-3$\Uparrow$ & BLEU-4$\Uparrow$ &  METEOR$\Uparrow$ & CIDEr$\Uparrow$  \\
\midrule
\rowcolor{gray!12} \multicolumn{8}{c}{AGENDA} \\
\midrule
BLM & $\surd$ & 0.4632 & 0.3248 & 0.2338 & 0.1679 & 0.2282 & 0.4940 \\
GPT-2 & $\surd$ & 0.4009 & 0.2608 & 0.1795 & 0.1247 & 0.2117 & 0.6508 \\
BERTGen & $\surd$ & 0.4435 & 0.2936 & 0.2046 & 0.1462 & 0.2202 & 0.6288 \\
T5 & $\surd$ & 0.4724 & 0.3235 & 0.2314 & 0.1688 & 0.2237 & 0.6203 \\
Transformer & $\times$ & 0.4481 & 0.3084 & 0.2175 & 0.1540 & 0.2265 & 0.6307 \\
BART & $\surd$ & 0.4765 & 0.3409 & 0.2539 & 0.1922 & 0.2418 & 0.7982 \\
\midrule
{\multirow{2}*{\textit{PermGen}}} & $\surd$ & 0.4537 & 0.3183 & 0.2308 & 0.1678 & 0.2294 & 0.6192 \\
& $\surd$ & \textbf{0.5043} & \textbf{0.3627} & \textbf{0.2719} & \textbf{0.2059} & \textbf{0.2500} & \textbf{0.8175} \\
\midrule
\rowcolor{gray!12} \multicolumn{8}{c}{DailyMail} \\
\midrule
BLM & $\surd$ & 0.3902 & 0.2540 & 0.1718 & 0.1164 & 0.2013 & 0.3627 \\
GPT-2 & $\surd$ & 0.3518 & 0.2188 & 0.1510 & 0.1072 & 0.1911 & 0.5433 \\
BERTGen & $\surd$ & 0.4350 & 0.3088 & 0.2299 & 0.1728 & 0.2301 & 0.4316 \\
T5 & $\surd$ & 0.4208 & 0.2895 & 0.2089 & 0.1529 & 0.2188 & 0.3813 \\
Transformer & $\times$ & 0.4379 & 0.2958 & 0.2098 & 0.1496 & 0.2221 & 0.5869 \\
BART & $\surd$ & 0.4727 & 0.3368 & 0.2534 & 0.1935 & 0.2379 & 0.7252 \\
\midrule
{\multirow{2}*{\textit{PermGen}}} & $\times$  & 0.4484 & 0.3024 & 0.2178 & 0.1592 & 0.2225 & 0.7059 \\
& $\surd$  & \textbf{0.4764} & \textbf{0.3407} & \textbf{0.2586} & \textbf{0.1991} & \textbf{0.2390} & \textbf{0.7549} \\
\midrule
\rowcolor{gray!12} \multicolumn{8}{c}{ROCStories} \\
\midrule
BLM & $\surd$ & 0.4653 & 0.3075 & 0.2098 & 0.1477 & 0.2275 & 0.7060 \\
GPT-2 & $\surd$ & 0.3157 & 0.1824 & 0.1133 & 0.0726 & 0.1592 & 0.4458 \\
BERTGen & $\surd$ & 0.4753 & 0.3155 & 0.2184 & 0.1576 & 0.2393 & 0.8628 \\
T5 & $\surd$ & 0.5347 & 0.3655 & 0.2584 & 0.1895 & 0.2480 & 1.3108 \\
Transformer & $\times$ & 0.5180 & 0.3526 & 0.2482 & 0.1809 & 0.2457 & 1.1342 \\
BART & $\surd$ & 0.5688 & 0.4159 & 0.3143 & 0.2445 & 0.2744 & 1.6165 \\
\midrule
{\multirow{2}*{\textit{PermGen}}} & $\times$ & 0.5238 & 0.3566 & 0.2522 & 0.1848 & 0.2465 & 1.1775 \\
& $\surd$ & \textbf{0.5830} & \textbf{0.4238} & \textbf{0.3196} & \textbf{0.2482} & \textbf{0.2769} & \textbf{1.7385} \\
\bottomrule
\end{tabular}}}
\label{tab:table1-value}
\end{center}
\end{table*}

\begin{table*}[t]
\begin{center}
\caption{Extension of Table \ref{tab:baseline}. Diversity results for \textit{PermGen} and baseline methods.}
\vspace{-0.05in}
\setlength{\tabcolsep}{2.5mm}{{\scalebox{0.90}{\begin{tabular}{lc|ccccccc}
\toprule
{\multirow{1}*{Method}} & Per-train & Dist-2$\Uparrow$ & Dist-3$\Uparrow$ & Ent-1$\Uparrow$ & Ent-2$\Uparrow$ & Ent-3$\Uparrow$ & Ent-4$\Uparrow$ &  \multicolumn{1}{c}{Self-BLEU-4$\Downarrow$}\\
\midrule
\rowcolor{gray!12} \multicolumn{9}{c}{AGENDA} \\
\midrule
BLM & $\surd$ & 0.1465 & 0.2593 & 6.2633 & 9.3736 & 10.5771 & 10.8762 & 0.9396 \\
GPT-2 & $\surd$ & 0.1665 & 0.2709 & 6.3327 & 9.0065 & 10.0387 & 10.4467 & 0.9331 \\
BERTGen & $\surd$ & 0.1463 & 0.2457 & 6.1160 & 9.1015 & 10.2476 & 10.6362 & 0.9356 \\
T5 & $\surd$ & 0.1323 & 0.2178 & 5.9393 & 8.6682 & 9.8081 & 10.2888 & 0.9421 \\
Transformer & $\times$ & 0.1489 & 0.2546 & 5.9858 & 8.6806 & 9.8452 & 10.3447 & 0.9265 \\
BART & $\surd$ & 0.1697 & 0.2815 & 6.2168 & 9.0698 & 10.1473 & 10.5333 & {0.9476} \\
\midrule
{\multirow{2}*{\textit{PermGen}}} & $\times$ & 0.2203 & 0.4564 & 6.1674 & 9.0272 & 10.3163 & 10.8839 & 0.5979 \\
& $\surd$ & \textbf{0.2492} & \textbf{0.4852} & \textbf{6.3864} & \textbf{9.4862} & \textbf{10.7269} & \textbf{11.1911} & \textbf{0.6173} \\
\midrule
\rowcolor{gray!12} \multicolumn{9}{c}{DailyMail} \\
\midrule
BLM & $\surd$ & 0.0831 & 0.1379 & 6.4465 & 9.0287 & 10.3353 & 10.9684 & 0.9889 \\
GPT-2 & $\surd$ & 0.1577 & 0.2511 & 7.4221 & 10.5923 & 11.6718 & 11.9437 & 0.9287 \\
BERTGen & $\surd$ & 0.1167 & 0.1980 & 6.8704 & 10.3130 & 11.5898 & 11.8999 & 0.9744 \\
T5 & $\surd$ & 0.1086 & 0.1763 & 6.7553 & 9.7788 & 11.0747 & 11.5242 & 0.9779 \\
Transformer & $\times$ & 0.1109 & 0.1942 & 6.9249 & 10.0132 & 11.3008 & 11.7343& 0.9678 \\
BART & $\surd$ & 0.1306 & 0.2163 & 7.1025 & 10.3602 & 11.5483 & 11.8704 & {0.9778} \\
\midrule
{\multirow{2}*{\textit{PermGen}}} & $\times$ & 0.1934 & 0.3790 & 7.1776 & 10.6234 & 11.9798 & 12.3989 & 0.7757 \\
 & $\surd$ & \textbf{0.2065} & \textbf{0.4140} & \textbf{7.2142} & \textbf{10.6632} & \textbf{12.0205} & \textbf{12.4793} & \textbf{0.6701} \\
\midrule
\rowcolor{gray!12} \multicolumn{9}{c}{ROCStories} \\
\midrule
BLM & $\surd$ & 0.0560 & 0.1402 & 5.5457 & 8.8401 & 10.8404 & 11.8790 & 0.9573 \\
GPT-2 & $\surd$ & 0.0915 & 0.1902 & 6.4372 & 9.8739 & 11.4976 & 12.0918 & 0.9194 \\
BERTGen & $\surd$ & 0.0672 & 0.1626 & 5.8283 & 9.3407 & 11.3309 & 12.2154 & 0.9456\\
T5 & $\surd$ & 0.0684 & 0.1631 & 5.8398 & 9.3663 & 11.3523 & 12.2285 & 0.9403 \\
Transformer & $\times$ & 0.0806 & 0.1971 & 5.7978 & 9.3205 & 11.4086 & 12.4069 & 0.9341 \\
BART & $\surd$ & 0.0839 & 0.2103 & 5.8986 & 9.4791 & 11.5186 & 12.4204 & {0.9330} \\
\midrule
{\multirow{2}*{\textit{PermGen}}} & $\times$ & 0.0992 & 0.2786 & 5.7773 & 9.2959 & 11.4553 & 12.6124 & 0.8548 \\
 & $\surd$ & \textbf{0.1059} & \textbf{0.2953} & \textbf{5.9669} & \textbf{9.6523} & \textbf{11.7972} & \textbf{12.8034} & \textbf{0.7247} \\
\bottomrule
\end{tabular}}}}
\label{tab:table1-value-2}
\end{center}
\end{table*}

\begin{table*}[t]
\begin{center}
\caption{Extension of Figure \ref{fig:diversity-and-acc}. Diversity results of \textit{PermGen} and other sampling methods. }
\vspace{-0.1in}
\setlength{\tabcolsep}{2.6mm}{\scalebox{0.85}{\begin{tabular}{lcc|cccccccc}
\toprule
Sampling & Setting & Method & Dist-2$\Uparrow$ & Dist-3$\Uparrow$ & Ent-1$\Uparrow$ & Ent-2$\Uparrow$ & Ent-3$\Uparrow$ & Ent-4$\Uparrow$ &  \multicolumn{2}{c}{Self-BLEU-3/4$\Downarrow$}\\
\midrule
\rowcolor{gray!12} \multicolumn{11}{c}{AGENDA} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.1697 & 0.2815 & 6.2168 & 9.0698 & 10.1473 & 10.5333 & {0.9531} & {0.9476} \\
& & \textit{PermGen} & 0.2492 & 0.4852 & 6.3864 & 9.4862 & 10.7269 & 11.1911 & {0.6675} & {0.6173} \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.2410 & 0.4489 & 6.2751 & 9.2836 & 10.5489 & 11.0561 & {0.6680} & {0.6139} \\
& & \textit{PermGen} & 0.2599 & 0.5114 & 6.3993 & 9.5307 & 10.8008 & 11.2772 & {0.6217} & {0.5630} \\
\cmidrule{2-11}
& {\multirow{2}*{k=50}} & Original & 0.2491 & 0.4923 & 6.2773 & 9.3190 & 10.6157 & 11.1347 & {0.6239} & {0.5626} \\
&  & \textit{PermGen} & 0.2632 & 0.5205 & \textbf{6.4038} & \textbf{9.5549} & \textbf{10.8411} & \textbf{11.3239} & \textbf{{0.6010}} & 0.5397  \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.2434 & 0.4716 & 6.2771 & 9.2946 & 10.5610 & 11.0647 & {0.6619} & {0.6080} \\
& & \textit{PermGen} & 0.2583 & 0.5076 & 6.3911 & 9.5135 & 10.7804 & 11.2588 & {0.6255} & {0.5682} \\
\cmidrule{2-11}
& {\multirow{2}*{p=.95}} & Original & 0.2522 & 0.4962 & 6.2889 & 9.3377 & 10.6308 & 11.1448 & {0.6190} & {0.5579} \\
& & \textit{PermGen} & \textbf{0.2636} & \textbf{0.5221} & 6.3996 & 9.5507 & 10.8385 & 11.3204 & {0.6006} & \textbf{0.5393}  \\
\midrule
\rowcolor{gray!12} \multicolumn{11}{c}{DailyMail} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} &  & Original & 0.1306 & 0.2163 & 7.1025 & 10.3602 & 11.5483 & 11.8704 & {0.9798} & {0.9778} \\
& & \textit{PermGen} & 0.2065 & 0.4140 & 7.2142 & 10.6632 & 12.0205 & 12.4793 & {0.7146} & {0.6701} \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.2087 & 0.4278 & 7.1406 & 10.5733 & 12.0173 & 12.5324 & {0.7055} & {0.6561} \\
& & \textit{PermGen} & 0.2166 & 0.4421 & 7.2171 & 10.6979 & 12.0915 & 12.5711 & {0.6704} & {0.6175} \\
\cmidrule{2-11}
& {\multirow{2}*{k=50}} & Original & 0.2194 & 0.4553 & 7.1485 & 10.6153 & 12.0872 & 12.6152 & {0.6612} & {0.6046} \\
&  & \textit{PermGen} & \textbf{0.2228} & \textbf{0.4573} & \textbf{7.2222} & \textbf{10.7221} & 12.1282 & 12.6154 & {0.6472} & {0.5909} \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.2109 & 0.4315 & 7.1439 & 10.5835 & 12.0270 & 12.5400 & {0.7004} & {0.6508} \\
& & \textit{PermGen} & 0.2166 & 0.4409 & 7.2188 & 10.6994 & 12.0894 & 12.5671 & {0.6719} & {0.6198} \\
\cmidrule{2-11}
& {\multirow{2}*{p=.95}} & Original & 0.2213 & 0.4600 & 7.1523 & 10.6254 & 12.1002 & 12.6307 & {0.6544} & {0.5972} \\
& & \textit{PermGen} & 0.2222 & 0.4566 & 7.2197 & 10.7195 & \textbf{12.1300} & \textbf{12.6168} & \textbf{{0.6465}} & \textbf{{0.5902}} \\
\midrule
\rowcolor{gray!12} \multicolumn{11}{c}{ROCStories} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.0839 & 0.2103 & 5.8986 & 9.4791 & 11.5186 & 12.4204 & {0.9420} & {0.9330} \\
& & PermGen & 0.1059 & 0.2953 & 5.9669 & 9.6523 & 11.7972 & 12.8034 & {0.7669} & {0.7247} \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.1053 & 0.2834 & 5.9041 & 9.5370 & 11.6702 & 12.6739 & {0.7955} & {0.7591} \\
& & \textit{PermGen} & 0.1099 & 0.3088 & 5.9716 & 9.6702 & 11.8335 & 12.8547 & {0.7359} & {0.6878} \\
\cmidrule{2-11}
& {\multirow{2}*{k=50}} & Original & 0.1093 & 0.2970 & 5.9094 & 9.5552 & 11.7055 & 12.7234 & {0.7633} & {0.7213} \\
&  & \textit{PermGen} & \textbf{0.1114} & \textbf{0.3141} & \textbf{5.9761} & \textbf{9.6801} & \textbf{11.8497} & \textbf{12.8732} & \textbf{{0.7235}} & \textbf{0.6734} \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.1032 & 0.2746 & 5.9047 & 9.5309 & 11.6501 & 12.6400 & {0.8147} & {0.7829} \\
& & \textit{PermGen} & 0.1092 & 0.3069 & 5.9730 & 9.6685 & 11.8292 & 12.8459 & {0.7421} & {0.6953} \\
\cmidrule{2-11}
& {\multirow{2}*{p=.95}} & Original & 0.1088 & 0.2955 & 5.9108 & 9.5545 & 11.7011 & 12.7160 & {0.7669} & {0.7260} \\
& & \textit{PermGen} & 0.1111 & 0.3132 & 5.9747 & 9.6778 & 11.8463 & 12.8702 & 0.7252 & {0.6753} \\
\bottomrule
\end{tabular}}}
\label{tab:appendix-diversity}
\end{center}
\end{table*}

\begin{table*}[t]
\begin{center}
\caption{Extension of Figure \ref{fig:diversity-and-acc}. Top-1 accuracy results of \textit{PermGen} and other sampling methods.}
\vspace{-0.1in}
\setlength{\tabcolsep}{3mm}{\scalebox{0.85}{\begin{tabular}{lcc||cccccc}
\toprule
Sampling & Setting & Method & BLEU-1$\Uparrow$ & BLEU-2$\Uparrow$ & BLEU-3$\Uparrow$ & BLEU-4$\Uparrow$ &  METEOR$\Uparrow$ & CIDEr$\Uparrow$  \\
\midrule
\rowcolor{gray!12} \multicolumn{9}{c}{AGENDA} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.4765 & 0.3409 & 0.2539 & 0.1922 & 0.2418 & 0.7982 \\
& & \textit{PermGen} & 0.5043 & 0.3627 & 0.2719 & \textbf{0.2059} & 0.2500 & 0.8175 \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.4718 & 0.3374 & 0.2513 & 0.1901 & 0.2408 & 0.7191 \\
& & \textit{PermGen} & 0.5035 & 0.3620 & 0.2716 & 0.2058 & 0.2495 & 0.8317 \\
\cmidrule{2-9}
& {\multirow{2}*{k=50}} & Original & 0.4777 & 0.3403 & 0.2529 & 0.1910 & 0.2415 & 0.7874 \\
&  & \textit{PermGen} & 0.5062 & 0.3626 & 0.2709 & 0.2047 & 0.2496 & \textbf{0.8465}\\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.4720 & 0.3361 & 0.2496 & 0.1878 & 0.2399 & 0.7174 \\
& & \textit{PermGen} & 0.5021 & 0.3611 & 0.2705 & 0.2047 & 0.2487 & 0.8254 \\
\cmidrule{2-9}
& {\multirow{2}*{p=.95}} & Original & 0.4764 & 0.3391 & 0.2519 & 0.1902 & 0.2407 & 0.7818 \\
& & \textit{PermGen} & \textbf{0.5071} & \textbf{ 0.3639} &\textbf{ 0.2721} & 0.2053 & \textbf{0.2502} & 0.8114 \\
\midrule
\rowcolor{gray!12} \multicolumn{9}{c}{DailyMail} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.4727 & 0.3368 & 0.2534 & 0.1935 & 0.2379 & 0.7252 \\
& & \textit{PermGen} & 0.4764 & 0.3407 & 0.2586 & 0.1991 & \textbf{0.2390} & 0.7549 \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.4728 & 0.3357 & 0.2522 & 0.1923 & 0.2385 & 0.7206 \\
& & \textit{PermGen} & 0.4772 & 0.3404 & 0.2578 & 0.1978 & 0.2374 & 0.8080 \\
\cmidrule{2-9}
& {\multirow{2}*{k=50}} & Original & 0.4742 & 0.3362 & 0.2519 & 0.1916 & 0.2379 & 0.7311 \\
&  & \textit{PermGen} & \textbf{0.4785} & 0.3409 & 0.2580 & 0.1982 & 0.2380 & \textbf{0.8389} \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.4726 & 0.3360 & 0.2525 & 0.1926 & 0.2383 & 0.7070 \\
& & \textit{PermGen} & 0.4784 & \textbf{0.3416} & \textbf{0.2592} & \textbf{0.1993} & 0.2385 & 0.8048 \\
\cmidrule{2-9}
& {\multirow{2}*{p=.95}} & Original & 0.4740 & 0.3367 & 0.2528 & 0.1926 & 0.2384 & 0.7204 \\
& & \textit{PermGen} & \textbf{0.4785} & 0.3412 & 0.2584 & 0.1983 & 0.2383 & 0.8118 \\
\midrule
\rowcolor{gray!12} \multicolumn{9}{c}{ROCStories} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.5688 & 0.4159 & 0.3143 & 0.2445 & 0.2744 & 1.6165 \\
& & \textit{PermGen}  & 0.5830 & 0.4238 & 0.3196 & 0.2482 & 0.2769 & 1.7385 \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.5680 & 0.4139 & 0.3117 & 0.2418 & 0.2734 & 1.6213 \\
& & \textit{PermGen} & 0.5829 & 0.4226 & 0.3179 & 0.2463 & 0.2761 & 1.7322 \\
\cmidrule{2-9}
& {\multirow{2}*{k=50}} & Original & 0.5681 & 0.4135 & 0.3112 & 0.2410 & 0.2729 & 1.6168 \\
&  & \textit{PermGen}  & \textbf{0.5834} & \textbf{0.4231} & 0.3181 & 0.2464 & \textbf{0.2764} & \textbf{1.7379} \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.5681 & 0.4144 & 0.3123 & 0.2423 & 0.2735 & 1.6152 \\
& & \textit{PermGen} & 0.5823 & 0.4225 & 0.3180 & \textbf{0.2466} & 0.2761 & 1.7330 \\
\cmidrule{2-9}
& {\multirow{2}*{p=.95}} & Original & 0.5678 & 0.4135 & 0.3115 & 0.2415 & 0.2730 & 1.6207 \\
& & \textit{PermGen}  & 0.5833 & \textbf{0.4231} & \textbf{0.3183} & \textbf{0.2466} & 0.2762 & 1.7363 \\
\bottomrule
\end{tabular}}}
\label{tab:appendix-top1}
\end{center}
\end{table*}

\begin{table*}[t]
\begin{center}
\caption{Extension of Figure \ref{fig:diversity-and-acc}. Oracle (top-K) accuracy results of \textit{PermGen} and other sampling methods.}
\vspace{-0.1in}
\setlength{\tabcolsep}{3mm}{\scalebox{0.85}{\begin{tabular}{lcc||cccccc}
\toprule
Sampling & Setting & Method  & BLEU-1$\Uparrow$ & BLEU-2$\Uparrow$ & BLEU-3$\Uparrow$ & BLEU-4$\Uparrow$ &  METEOR$\Uparrow$ & CIDEr$\Uparrow$  \\
\midrule
\rowcolor{gray!12} \multicolumn{9}{c}{AGENDA} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.4941 & 0.3529 & 0.2624 & 0.1983 & 0.2469 & 1.0208 \\
& & \textit{PermGen} & 0.5052 & 0.3723 & 0.2858 & \textbf{0.2217} & 0.2556 & 1.0371 \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.4983 & 0.3627 & 0.2746 & 0.2110 & 0.2516 & 1.0291 \\
& & \textit{PermGen} & 0.5068 & 0.3723 & 0.2852 & 0.2209 & \textbf{0.2561} & 1.0247 \\
\cmidrule{2-9}
& {\multirow{2}*{k=50}} & Original & 0.5017 & 0.3642 & 0.2758 & 0.2123 & 0.2522 & 1.0451 \\
&  & \textit{PermGen} & 0.5061 & 0.3720 & 0.2851 & 0.2211 & 0.2548 & 1.0285 \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.4960 & 0.3604 & 0.2726 & 0.2091 & 0.2510 & 0.9920 \\
& & \textit{PermGen} & 0.5006 & 0.3688 & 0.2830 & 0.2195 & 0.2540 & \textbf{1.0549} \\
\cmidrule{2-9}
& {\multirow{2}*{p=.95}} & Original & 0.4984 & 0.3624 & 0.2744 & 0.2114 & 0.2510 & 1.0441 \\
& & \textit{PermGen} & \textbf{0.5095} & \textbf{0.3741} & \textbf{0.2863} & 0.2215 & 0.2556 & 1.0121 \\
\midrule
\rowcolor{gray!12} \multicolumn{9}{c}{DailyMail} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.4817 & 0.3428 & 0.2578 & 0.1968 & 0.2408 & 0.9001 \\
& & \textit{PermGen} & 0.4847 & 0.3567 & 0.2777 & 0.2193 & 0.2448 & 0.8544 \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.4888 & 0.3545 & 0.2716 & 0.2115 & 0.2448 & \multicolumn{1}{c}{\textbf{0.9212}} \\
& & \textit{PermGen} & 0.4853 & 0.3568 & 0.2779 & 0.2196 & 0.2447 & 0.8678 \\
\cmidrule{2-9}
& {\multirow{2}*{k=50}} & Original & 0.4891 & 0.3550 & 0.2723 & 0.2122 & 0.2444 & 0.9197 \\
&  & \textit{PermGen} & \textbf{0.4878} & \textbf{0.3580} & \textbf{0.2784} & 0.2197 & 0.2454 & 0.8902 \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.4888 & 0.3540 & 0.2710 & 0.2106 & 0.2444 & 0.9192 \\
& & \textit{PermGen} & 0.4857 & 0.3573 & \textbf{0.2784} & \textbf{0.2199} & 0.2451 & 0.8240 \\
\cmidrule{2-9}
& {\multirow{2}*{p=.95}} & Original & 0.4896 & 0.3554 & 0.2727 & 0.2127 & 0.2446 & 0.9152 \\
& & \textit{PermGen} & 0.4871 & \textbf{0.3580} & 0.2783 & 0.2194 & \textbf{0.2455} & 0.8809 \\
\midrule
\rowcolor{gray!12} \multicolumn{9}{c}{ROCStories} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.5801 & 0.4282 & 0.3264 & 0.2556 & 0.2789 & 1.7947 \\
& & \textit{PermGen}  & \textbf{0.5991} & \textbf{0.4505} & 0.3513 & 0.2810 & \textbf{0.2875} & 2.0115 \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.5834 & 0.4377 & 0.3390 & 0.2692 & 0.2824 & 1.8148 \\
& & \textit{PermGen} & 0.5988 & 0.4501 & 0.3508 & 0.2803 & 0.2871 & 2.0160 \\
\cmidrule{2-9}
& {\multirow{2}*{k=50}} & Original & 0.5849 & 0.4394 & 0.3410 & 0.2712 & 0.2830 & 1.8393 \\
&  & \textit{PermGen} & 0.5989 & 0.4503 & 0.3510 & 0.2805 & 0.2872 & 2.0137 \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.5829 & 0.4362 & 0.3369 & 0.2667 & 0.2818 & 1.8135 \\
& & \textit{PermGen} & 0.5989 & 0.4500 & 0.3508 & 0.2803 & 0.2872 & 2.0107 \\
\cmidrule{2-9}
& {\multirow{2}*{p=.95}} & Original & 0.5852 & 0.4392 & 0.3405 & 0.2706 & 0.2831 & 1.8293 \\
& & \textit{PermGen} & 0.5989 & \textbf{0.4505} & \textbf{0.3515} & \textbf{0.2812} & 0.2870 & \textbf{2.0232} \\
\bottomrule
\end{tabular}}}
\label{tab:appendix-topk}
\end{center}
\end{table*}

\begin{table*}[t]
\caption{Generation Cases on AGENDA dataset from \textit{PermGen} and other diversity promoting methods.}
\vspace{-0.05in}
\scalebox{0.83}{
{\begin{tabular}{p{18.5cm}}
\toprule
$\bullet$ \textbf{Inputs:} (Title) Hierarchical Semantic Classification: Word Sense Disambiguation with World Knowledge. (Keyphrases) learning architecture; lexical semantic classification problems; task-specific training data; background data; hierarchical learning architecture; word sense disambiguation task \\
\midrule
$\bullet$ \textbf{Beam search-1:} This paper presents a learning architecture for lexical semantic classification problems that does not require task-specific training data or background data . The learning architecture is built on top of a hierarchical learning architecture that is able to integrate both tasks-specific and background data in a principled way . We evaluate the hierarchical learning on a word sense disambiguation task and show that the hierarchical learns architecture outperforms a state-of-the-art \hlt{approach}  . \\
$\bullet$ \textbf{Beam search-2:} This paper presents a learning architecture for lexical semantic classification problems that does not require task-specific training data or background data . The learning architecture is built on top of a hierarchical learning architecture that is able to integrate both tasks-specific and background data in a principled way . We evaluate the hierarchical learning on a word sense disambiguation task and show that the hierarchical learns architecture \hlt{is competitive with} state-of-the-art \hlt{methods}  . \\
$\bullet$ \textbf{Beam search-3:} This paper presents a learning architecture for lexical semantic classification problems that does not require task-specific training data or background data . The learning architecture is built on top of a hierarchical learning architecture that is able to integrate both tasks-specific and background data in a principled way . We evaluate the hierarchical learning on a word sense disambiguation task and show that the hierarchical learns architecture outperforms the state-of-the-art  . \\
\midrule
$\bullet$ \textbf{Nucleus sampling-1:} We present a learning architecture for lexical semantic classification problems that does not require any task-specific training data or background data . The learning architecture \hlt{can be trained on a variety of tasks without any knowledge of the nature of the tasks or the sources of the training data .} \hlt{We show that this can be achieved by combining task-sparse and sparse training data ,} and show that the resulting hierarchical learning architecture outperforms state-of-the-art methods on a word sense disambiguation task . \\
$\bullet$ \textbf{Nucleus sampling-2:} We present a learning architecture for lexical semantic classification problems that does not require any task-specific training data or background data . The learning architecture \hlt{is designed to learn from both the tasks-specific and background data simultaneously .} We apply this hierarchical learning architecture to a word sense disambiguation task and show that hierarchical learning architectures outperforms state-of-the-art methods on both tasks  . \\
$\bullet$ \textbf{Nucleus sampling-3:} We present a learning architecture for lexical semantic classification problems that does not require task-specific training data or background data . \hlt{Our learning architecture is able to take advantage of both tasks by exploiting the relationship between task-sensor and background data in a principled way .} We apply our hierarchical learning architecture to a word sense disambiguation task , and show that hierarchical learning architectures outperforms state-of-the-art methods  . \\
\midrule
$\bullet$ \textbf{PermGen order-1 [1, 2, 3]:} \hlt{We present} a learning architecture for lexical semantic classification problems that does not require task-specific training data or background data . \hlt{Our learning architecture learns to partition the data in different domains into different subsets , such that the distribution of a given word is consistent across different domains .} \hlt{We show that our} hierarchical learning architecture \hlt{outperforms the state-of-the-art methods on a word sense disambiguation task , and present the results of a large-scale empirical evaluation .} \\
$\bullet$ \textbf{PermGen order-2 [2, 1, 3]:} \hlt{This paper presents} a new learning architecture for lexical semantic classification problems that \hlt{does not rely on task specific training data .} \hlt{We propose a learning architecture that leverages both task-specific and background data .} We apply this hierarchical learning architecture to a word sense disambiguation task , and show that hierarchical learning architecture outperforms state-of-the-art methods  . \\
$\bullet$ \textbf{PermGen order-3 [3, 1, 2]:} \hlt{We describe} a learning architecture for lexical semantic classification problems that does not require task-specific training data or background data . \hlt{Our learning architecture is built on top of a hierarchy of networks that learn to classify words based on their senses , and a network that ties together the tasks-specific and background data to form a hierarchy .} We apply this hierarchical learning architecture to a word sense disambiguation task , and show that hierarchical learning architecture outperforms state-of-the-art methods  . \\
\bottomrule
\end{tabular}}}
\label{tab:appendix-case-1}
\end{table*}

\begin{table*}[t]
\caption{Generation Cases on DailyMail dataset from \textit{PermGen} and other diversity promoting methods.}
\vspace{-0.05in}
\scalebox{0.83}{
{\begin{tabular}{p{18.5cm}}
\toprule
$\bullet$ \textbf{Inputs:} white british londoners; left; census figures show; white flight; equivalent; white britons; white britons; minority \\
\midrule
$\bullet$ \textbf{Beam search-1:} More than 700,000 white British Londoners have left the country in the last decade . Census figures show that a `` white flight '' has taken place in the capital since the 1990s . This is equivalent to more than one in four white Britons having left the UK . White Britons are now a minority of the population in London , according to new \hlt{figures} . \\
$\bullet$ \textbf{Beam search-2:} More than 700,000 white British Londoners have left the country in the last decade . Census figures show that a `` white flight '' has taken place in the capital since the 1990s . This is equivalent to more than one in four white Britons having left the UK . White Britons are now a minority of the population in London . \\
$\bullet$ \textbf{Beam search-3:} More than 700,000 white British Londoners have left the country in the last decade . Census figures show that a `` white flight '' has taken place in the capital since the 1990s . This is equivalent to more than one in four white Britons having left the UK . White Britons are now a minority of the population in London , according to a new \hlt{study} . \\
\midrule
$\bullet$ \textbf{Nucleus sampling-1:} More than 700,000 white British Londoners have left the country \hlt{since 2001} , according to new figures . Census figures show that the `` white flight '' of incomers has \hlt{overtaken those from elsewhere in the country .} \hlt{It} is equivalent to more than one in four white Britons having left the UK . White Britons are now a minority of the population in England \hlt{and Wales .} \\
$\bullet$ \textbf{Nucleus sampling-2:} More than 100,000 white British Londoners have left the country , according to new figures . Census figures show that a `` white flight '' of incomers has taken place in the capital . This is equivalent to more than half of all white Britons \hlt{being in the UK .} White Britons are now a minority of the population in London , \hlt{new figures have revealed .} \\
$\bullet$ \textbf{Nucleus Sampling-3:} More than 50,000 white British Londoners have left the country . Census figures show that a ‘ white flight ’ of incomers has taken place in the capital . This is equivalent to more than one in four white Britons having left the UK . White Britons are now a minority of the population in London , \hlt{according to new figures .} \\
\midrule
$\bullet$ \textbf{PermGen order-1 [1, 2, 3, 4]:} \hlt{The equivalent of} more than 10,000 white British Londoners have left the country , \hlt{it has been} revealed . Census figures show that a `` white flight '' of people \hlt{moving to the capital has overtaken London} for the first time . The equivalent of \hlt{more than 10,000 white Britons has left the country for the first time in more than a decade .} White Britons have become a minority \hlt{in the capital since 1994 , but are now only a minority .}\\
$\bullet$ \textbf{PermGen order-2 [3, 2, 4, 1]:} More than 50,000 white British Londoners have left the country for the first time , \hlt{new figures have} revealed . Census figures show that a `` white flight '' of people \hlt{from outside Europe has overtaken the city 's residents} for the first time . The equivalent of \hlt{around 40 per cent of all white Britons now live in the UK .} White Britons now make up a minority \hlt{of the population in London.} \\
$\bullet$ \textbf{PermGen order-3 [4, 2, 1, 3]:} More than 50,000 white British Londoners have left the country in the last three years . Census figures show that the number of `` white flight '' migrants has \hlt{risen by more than 50 per cent in just three years .} This is equivalent to \hlt{more than one in four white Britons in the UK .} The number of white Britons in the minority \hlt{has risen by more than 50 per cent in just three years .} \\
\bottomrule
\end{tabular}}}
\label{tab:appendix-case-3}
\end{table*}

\section{Proofs}

\section{Experiment Details}

\subsection{Tasks and Datasets}
\label{sec:dataset}
In this section, we further provide data statistics of ROCStories~\cite{mostafazadeh2016corpus}, AGENDA~\cite{koncel2019text}, and DailyMail~\cite{see2017get}.

\begin{table}[h]
\caption{Statistics of three datasets. ``In'' stands for input and ``Out'' stands for output.}
\vspace{-0.15in}
\begin{center}
\setlength{\tabcolsep}{2.6mm}{
\scalebox{0.90}{\begin{tabular}{l|c|c|c|c|c|c|c}
\toprule
Dataset & \#Train & \#Dev.& \#Test & Title & \#In.keywords/phrases & \#Out.words & \#Out.sentences \\
\midrule
ROCStories & 98,162 & 9,817 & 9,803 & $\surd$ & 9.65 $\pm$ 2.34 & 50.16 $\pm$ 9.25 & 4.92 $\pm$ 0.28 \\
AGENDA & 38,720 & 1,000 & 1,000 & $\surd$ & 16.09 $\pm$ 5.18 & 76.12 $\pm$ 21.32 & 3.08 $\pm$ 0.39 \\
DailyMail & 49,102 & 2,000 & 2,000 & $\times$ & 7.91 $\pm$ 0.40 & 95.62 $\pm$ 12.73 & 3.88 $\pm$ 0.75 \\
\bottomrule
\end{tabular}}}
\vspace{-0.2in}
\label{tab:datasets}
\end{center}
\end{table}

* DailyMail dataset does not provide a title for each news.

* We only extract the first paragraph in DailyMail dataset, not the full text.

\subsection{Baseline Methods}
\label{sec:baseline}

We compare with three pre-trained Transformer encoder-decoder models: BART~\cite{lewis2019bart}, T5~\cite{raffel2020exploring} and BERTGen~\cite{rothe2020leveraging}. These models have demonstrated state-of-the-art performance in various NLG tasks. We also compare with GPT-2~\cite{radford2019language}
and two recent non-autoregressive generation models: BLM~\cite{shen2020blank} and POINTER~\cite{zhang2020pointer}.

\paragraph{BLM}~\cite{shen2020blank} Blank Language Model (BLM) generates sequences by dynamically creating and filling in blanks. The blanks control which part of the sequence to fill out, making it ideal for word-to-sequence expansion tasks.

\paragraph{POINTER}~\cite{zhang2020pointer} POINTER operates by progressively inserting new tokens between existing tokens in a \textit{parallel} manner. This procedure is recursively applied until a sequence is completed. This coarse-to-fine hierarchy makes the generation process intuitive and interpretable.

\paragraph{}

For each task, we also evaluate \textit{PermGen} with different sampling algorithms for decoding, including beam search, Truncated sampling~\cite{fan2018hierarchical} and Nucleus sampling~\cite{holtzman2020curious}.

\paragraph{Truncated Sampling}~\cite{fan2018hierarchical} It randomly samples words from top-k candidates of the distribution at the decoding step.

\paragraph{Nucleus Sampling}~\cite{holtzman2020curious}  It avoids text degeneration by truncating the unreliable tail of the probability distribution, sampling from the dynamic nucleus of tokens containing the vast majority of the probability mass.

\subsection{Implementation Details}
\label{sec:implement}

We use pre-trained parameters from BART-base~\cite{lewis2019bart} to initialized our model, which takes a maximum 512 input token sequence and consists of a 6-layer transformer encoders and another 6-layer transformer decoders~\cite{vaswani2017attention} with 12 attention heads and 768 word dimensions. For model fine tuning, we train our model for 20 epochs. We use Adam with learning rate of 3e-5, $\beta_1$ = 0.9, $\beta_2$ = 0.999, L2 weight decay of 0.01, learning rate warm up over the first 10,000 steps, and linear decay of learning rate. Our models are trained with a 4-card 32GB memory Tesla V100 GPU, and implemented on PyTorch with the Huggingface's Transformer~\cite{wolf2020transformers}.

\begin{table*}[t]
\begin{center}
\caption{Extension of Table \ref{tab:baseline}. Accuracy and diversity results for \textit{PermGen} and baseline methods.}
\vspace{-0.05in}
{\scalebox{0.80}{\begin{tabular}{lc|cccccc|cccc}
\toprule
{\multirow{1}*{Method}} & Pre-train & B-1$\Uparrow$ & B-2$\Uparrow$ & B-3$\Uparrow$ & B-4$\Uparrow$ &  MET$\Uparrow$ & CIDEr$\Uparrow$ & Dist-2$\Uparrow$ & Dist-3$\Uparrow$ & Ent-3$\Uparrow$ & Ent-4$\Uparrow$ \\
\midrule
\rowcolor{gray!12} \multicolumn{12}{c}{\textbf{AGENDA}} \\
\midrule
BLM & $\surd$ & 0.4632 & 0.3248 & 0.2338 & 0.1679 & 0.2282 & 0.4940 & 0.1465 & 0.2593 & 10.5771 & 10.8762 \\
GPT-2 & $\surd$ & 0.4009 & 0.2608 & 0.1795 & 0.1247 & 0.2117 & 0.6508 & 0.1665 & 0.2709 & 10.0387 & 10.4467 \\
BERTGen & $\surd$ & 0.4435 & 0.2936 & 0.2046 & 0.1462 & 0.2202 & 0.6288 & 0.1463 & 0.2457 & 10.2476 & 10.6362 \\
T5 & $\surd$ & 0.4724 & 0.3235 & 0.2314 & 0.1688 & 0.2237 & 0.6203 & 0.1323 & 0.2178 & 9.8081 & 10.2888 \\
Transformer & $\times$ & 0.4481 & 0.3084 & 0.2175 & 0.1540 & 0.2265 & 0.6307 & 0.1109 & 0.1942 & 9.8452 & 10.3447 \\
BART & $\surd$ & 0.4765 & 0.3409 & 0.2539 & 0.1922 & 0.2418 & 0.7982 & 0.1306 & 0.2163 & 10.1473 & 10.5333 \\
\midrule
{\multirow{2}*{\textit{PermGen}}} & $\surd$ & 0.4537 & 0.3183 & 0.2308 & 0.1678 & 0.2294 & 0.6192 & 0.2203 & 0.4564 & 10.3163 & 10.8839 \\
& $\surd$ & \textbf{0.5042} & \textbf{0.3626} & \textbf{0.2718} & \textbf{0.2061} & \textbf{0.2500} & \textbf{0.8145} & \textbf{0.2493} & \textbf{0.4852} & \textbf{10.7269} & \textbf{11.1911} \\
\midrule
\rowcolor{gray!12} \multicolumn{12}{c}{\textbf{DailyMail}} \\
\midrule
BLM & $\surd$ & 0.3902 & 0.2540 & 0.1718 & 0.1164 & 0.2013 & 0.3627 & 0.0831 & 0.1379 & 10.3353 & 10.9684 \\
GPT-2 & $\surd$ & 0.3518 & 0.2188 & 0.1510 & 0.1072 & 0.1911 & 0.5433 & 0.1577 & 0.2511 & 11.6718 & 11.9437 \\
BERTGen & $\surd$ & 0.4350 & 0.3088 & 0.2299 & 0.1728 & 0.2301 & 0.4316 & 0.1167 & 0.1980 & 11.5898 & 11.8999 \\
T5 & $\surd$ & 0.4208 & 0.2895 & 0.2089 & 0.1529 & 0.2188 & 0.3813 & 0.1086 & 0.1763 & 11.0747 & 11.5242 \\
Transformer & $\times$ & 0.4379 & 0.2958 & 0.2098 & 0.1496 & 0.2221 & 0.5869 & 0.1109 & 0.1942 & 11.3008 & 11.7343 \\
BART & $\surd$ & 0.4727 & 0.3368 & 0.2534 & 0.1935 & 0.2390 & 0.7252 & 0.1306 & 0.2163 & 11.5483 & 11.8704 \\
\midrule
{\multirow{2}*{\textit{PermGen}}} & $\times$  & 0.4484 & 0.3024 & 0.2178 & 0.1592 & 0.2225 & 0.7059 & 0.1934 & 0.3790  & 11.9798 & 12.3989 \\
& $\surd$  & \textbf{0.4789} & \textbf{0.3427} & \textbf{0.2603} & \textbf{0.2005} & \textbf{0.2393} & \textbf{0.7665} & \textbf{0.2065} & \textbf{0.4140} & \textbf{12.0205} & \textbf{12.4793} \\
\midrule
\rowcolor{gray!12} \multicolumn{12}{c}{\textbf{ROCStories}} \\
\midrule
BLM & $\surd$ & 0.4653 & 0.3075 & 0.2098 & 0.1477 & 0.2275 & 0.7060 & 0.0350 & 0.0876 & 10.8404 & 11.8790 \\
GPT-2 & $\surd$ & 0.3157 & 0.1824 & 0.1133 & 0.0726 & 0.1592 & 0.4458 & 0.0572 & 0.1189 & 11.4976 & 12.0918 \\
BERTGen & $\surd$ & 0.4753 & 0.3155 & 0.2184 & 0.1576 & 0.2393 & 0.8628 & 0.0421 & 0.1016 & 11.3309 & 12.2154 \\
T5 & $\surd$ & 0.5347 & 0.3655 & 0.2584 & 0.1895 & 0.2480 & 1.3108 & 0.0428 & 0.1026 & 11.3523 & 12.2285 \\
Transformer & $\times$ & 0.5180 & 0.3526 & 0.2482 & 0.1809 & 0.2457 & 1.1342 & 0.0504 & 0.1357 & 11.4086 & 12.4069 \\
BART & $\surd$ & 0.5468 & 0.3958 & 0.2966 & 0.2290 & 0.2636 & 1.4343 & 0.0531 & 0.1387 & 11.4514 & 12.4119 \\
\midrule
{\multirow{2}*{\textit{PermGen}}} & $\times$ & 0.5238 & 0.3566 & 0.2522 & 0.1848 & 0.2465 & 1.1775 & 0.0628 & 0.1886 & 11.4553 & 12.6124 \\
& $\surd$ & \textbf{0.5638} & \textbf{0.4075} & \textbf{0.3059} & \textbf{0.2372} & \textbf{0.2676} & \textbf{1.5724} & \textbf{0.0726} & \textbf{0.2169} & \textbf{11.7753} & \textbf{12.8722} \\
\bottomrule
\end{tabular}}}
\label{tab:table1-value}
\end{center}
\end{table*}

\begin{table*}[t]
\begin{center}
\caption{Extension of Figure \ref{fig:diversity-and-acc}. Top-1 accuracy results of \textit{PermGen} and other sampling methods.}
\vspace{-0.1in}
{\scalebox{0.78}{\begin{tabular}{lcc||cccccc|cccc}
\toprule
Sampling & Setting & Method & B-1$\Uparrow$ & B-2$\Uparrow$ & B-3$\Uparrow$ & B-4$\Uparrow$ & MET$\Uparrow$ & CIDEr$\Uparrow$ & Dist-2$\Uparrow$ & Dist-3$\Uparrow$ & Ent-3$\Uparrow$ & Ent-4$\Uparrow$ \\
\midrule
\rowcolor{gray!12} \multicolumn{13}{c}{\textbf{AGENDA}} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.4765 & 0.3409 & 0.2539 & 0.1922 & 0.2418 & 0.7982 & 0.1697 & 0.2815 & 10.1473 & 10.5333 \\
& & \textit{PermGen} & 0.5043 & 0.3627 & 0.2719 & \textbf{0.2059} & 0.2500 & 0.8175 & 0.2493 & 0.4852 & 10.7269 & 11.1911 \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.4718 & 0.3374 & 0.2513 & 0.1901 & 0.2408 & 0.7191 & 0.2405 & 0.4700 & 10.5181 & 11.0331 \\
& & \textit{PermGen} & 0.5035 & 0.3620 & 0.2716 & 0.2058 & 0.2495 & 0.8317 & 0.2534 & 0.5019 & 10.6864 & 11.1882 \\
\cmidrule{2-13}
& {\multirow{2}*{k=50}} & Original & 0.4777 & 0.3403 & 0.2529 & 0.1910 & 0.2415 & 0.7874 & 0.2495 & 0.4946 & 10.6043 & 11.1279 \\
&  & \textit{PermGen} & 0.5062 & 0.3626 & 0.2709 & 0.2047 & 0.2496 & \textbf{0.8465} & 0.2595 & 0.5165 & 10.7403 & 11.2459 \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.4720 & 0.3361 & 0.2496 & 0.1878 & 0.2399 & 0.7174 & 0.2418 & 0.4709 & 10.5173 & 11.0302 \\
& & \textit{PermGen} & 0.5021 & 0.3611 & 0.2705 & 0.2047 & 0.2487 & 0.8254 & 0.2527 & 0.4995 & 10.6823 & 11.1835 \\
\cmidrule{2-13}
& {\multirow{2}*{p=.95}} & Original & 0.4764 & 0.3391 & 0.2519 & 0.1902 & 0.2407 & 0.7818 & 0.2528 & 0.5018 & 10.6228 & 11.1479 \\
& & \textit{PermGen} & \textbf{0.5071} & \textbf{ 0.3639} &\textbf{ 0.2721} & 0.2053 & \textbf{0.2502} & 0.8114 & \textbf{0.2606} & \textbf{0.5196} & \textbf{10.7510} & \textbf{11.2545} \\
\midrule
\rowcolor{gray!12} \multicolumn{13}{c}{\textbf{ROCStories}} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.5468 & 0.3958 & 0.2966 & 0.2290 & 0.2636 & 1.4343 & 0.0531 & 0.1387 & 11.4514 & 12.4119 \\
& & \textit{PermGen} & 0.5636 & \textbf{0.4073} & \textbf{0.3057} & \textbf{0.2366} & \textbf{0.2675} & \textbf{1.5723} & 0.0726 & 0.2169 & 11.7753 & 12.8722 \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.5468 & 0.3948 & 0.2951 & 0.2273 & 0.2630 & 1.4262 & 0.0642 & 0.1791 & 11.5559 & 12.6048 \\
& & \textit{PermGen} & 0.5636 & 0.4059 & 0.3036 & 0.2342 & 0.2669 & 1.5633 & 0.0756 & 0.2277 & 11.8166 & 12.9292 \\
\cmidrule{2-13}
& {\multirow{2}*{k=50}} & Original & 0.5474 & 0.3953 & 0.2955 & 0.2278 & 0.2631 & 1.4326 & 0.0680 & 0.1926 & 11.5974 & 12.6700 \\
&  & \textit{PermGen} & \textbf{0.5643} & 0.4064 & 0.3041 & 0.2347 & 0.2672 & 1.5648 & \textbf{0.0770} & \textbf{0.2326} & 11.8330 & \textbf{12.9515} \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.5466 & 0.3940 & 0.2942 & 0.2264 & 0.2627 & 1.4192 & 0.0635 & 0.1754 & 11.5487 & 12.5857 \\
& & \textit{PermGen} & \textbf{0.5643} & 0.4063 & 0.3039 & 0.2345 & 0.2671 & 1.5685 & 0.0758 & 0.2285 & 11.8222 & 12.9339 \\
\cmidrule{2-13}
& {\multirow{2}*{p=.95}} & Original & 0.5468 & 0.3948 & 0.2952 & 0.2275 & 0.2627 & 1.4314 & 0.0681 & 0.1927 & 11.5980 & 12.6695 \\
& & \textit{PermGen} & 0.5642 & 0.4063 & 0.3039 & 0.2345 & 0.2672 & 1.5643 & 0.0767 & 0.2321 & \textbf{11.8331} & 12.9512 \\
\midrule
\rowcolor{gray!12} \multicolumn{13}{c}{\textbf{DailyMail}} \\
\midrule
{\multirow{2}*{\makecell[c]{Beam \\ search}}} & & Original & 0.4727 & 0.3368 & 0.2534 & 0.1935 & 0.2379 & 0.7252 & 0.1306 & 0.2163 & 11.5483 & 11.8704 \\
& & \textit{PermGen} & 0.4764 & 0.3407 & 0.2586 & 0.1991 & \textbf{0.2390} & 0.7549 & 0.2065 & 0.4140 & 12.0205 & 12.4793 \\
\midrule
{\multirow{4}*{\makecell[l]{Truncated \\ sampling}}} & {\multirow{2}*{k=10}} & Original & 0.4728 & 0.3357 & 0.2522 & 0.1923 & 0.2385 & 0.7206 & 0.2087 & 0.4278 & 12.0173 & 12.5324\\
& & \textit{PermGen} & 0.4772 & 0.3404 & 0.2578 & 0.1978 & 0.2374 & 0.8080 & 0.2166 & 0.4421 & 12.0915 & 12.5711 \\
\cmidrule{2-13}
& {\multirow{2}*{k=50}} & Original & 0.4742 & 0.3362 & 0.2519 & 0.1916 & 0.2379 & 0.7311 & 0.2194 & 0.4553 & 12.0872 & 12.6152 \\
&  & \textit{PermGen} & \textbf{0.4785} & 0.3409 & 0.2580 & 0.1982 & 0.2380 & \textbf{0.8389} & 0.2228 & 0.4573 & 12.1282 & 12.6154 \\
\midrule
{\multirow{4}*{\makecell[l]{Nucleus \\ sampling}}} & {\multirow{2}*{p=.75}} & Original & 0.4726 & 0.3360 & 0.2525 & 0.1926 & 0.2383 & 0.7070 & 0.2109 & 0.4315 & 12.0270 & 12.5400 \\
& & \textit{PermGen} & 0.4784 & \textbf{0.3416} & \textbf{0.2592} & \textbf{0.1993} & 0.2385 & 0.8048 & 0.2166 & 0.4409 & 12.0894 & 12.5671 \\
\cmidrule{2-13}
& {\multirow{2}*{p=.95}} & Original & 0.4740 & 0.3367 & 0.2528 & 0.1926 & 0.2384 & 0.7204 & 0.0681 & 0.1927 & 11.5980 & 12.6695 \\
& & \textit{PermGen} & \textbf{0.4785} & 0.3412 & 0.2584 & 0.1983 & 0.2383 & 0.8118 & \textbf{0.2222} & \textbf{0.4566} & \textbf{12.1300} & \textbf{12.6168} \\
\bottomrule
\end{tabular}}}
\label{tab:appendix-top1}
\end{center}
\end{table*}

\begin{table*}[t]
\caption{Generation Cases on DailyMail dataset from \textit{PermGen} and other diversity promoting methods.}
\vspace{-0.05in}
\scalebox{0.83}{
{\begin{tabular}{p{18.5cm}}
\toprule
$\bullet$ \textbf{Inputs:} white british londoners; left; census figures show; white flight; equivalent; white britons; white britons; minority \\
\midrule
$\bullet$ \textbf{Beam search-1:} More than 700,000 white British Londoners have left the country in the last decade . Census figures show that a `` white flight '' has taken place in the capital since the 1990s . This is equivalent to more than one in four white Britons having left the UK . White Britons are now a minority of the population in London , according to new \hlt{figures} . \\
$\bullet$ \textbf{Beam search-2:} More than 700,000 white British Londoners have left the country in the last decade . Census figures show that a `` white flight '' has taken place in the capital since the 1990s . This is equivalent to more than one in four white Britons having left the UK . White Britons are now a minority of the population in London . \\
$\bullet$ \textbf{Beam search-3:} More than 700,000 white British Londoners have left the country in the last decade . Census figures show that a `` white flight '' has taken place in the capital since the 1990s . This is equivalent to more than one in four white Britons having left the UK . White Britons are now a minority of the population in London , according to a new \hlt{study} . \\
\midrule
$\bullet$ \textbf{Nucleus sampling-1:} More than 700,000 white British Londoners have left the country \hlt{since 2001} , according to new figures . Census figures show that the `` white flight '' of incomers has \hlt{overtaken those from elsewhere in the country .} \hlt{It} is equivalent to more than one in four white Britons having left the UK . White Britons are now a minority of the population in England \hlt{and Wales .} \\
$\bullet$ \textbf{Nucleus sampling-2:} More than 100,000 white British Londoners have left the country , according to new figures . Census figures show that a `` white flight '' of incomers has taken place in the capital . This is equivalent to more than half of all white Britons \hlt{being in the UK .} White Britons are now a minority of the population in London , \hlt{new figures have revealed .} \\
$\bullet$ \textbf{Nucleus Sampling-3:} More than 50,000 white British Londoners have left the country . Census figures show that a ‘ white flight ’ of incomers has taken place in the capital . This is equivalent to more than one in four white Britons having left the UK . White Britons are now a minority of the population in London , \hlt{according to new figures .} \\
\midrule
$\bullet$ \textbf{PermGen order-1 [1, 2, 3, 4]:} \hlt{The equivalent of} more than 10,000 white British Londoners have left the country , \hlt{it has been} revealed . Census figures show that a `` white flight '' of people \hlt{moving to the capital has overtaken London} for the first time . The equivalent of \hlt{more than 10,000 white Britons has left the country for the first time in more than a decade .} White Britons have become a minority \hlt{in the capital since 1994 , but are now only a minority .}\\
$\bullet$ \textbf{PermGen order-2 [3, 2, 4, 1]:} More than 50,000 white British Londoners have left the country for the first time , \hlt{new figures have} revealed . Census figures show that a `` white flight '' of people \hlt{from outside Europe has overtaken the city 's residents} for the first time . The equivalent of \hlt{around 40 per cent of all white Britons now live in the UK .} White Britons now make up a minority \hlt{of the population in London.} \\
$\bullet$ \textbf{PermGen order-3 [4, 2, 1, 3]:} More than 50,000 white British Londoners have left the country in the last three years . Census figures show that the number of `` white flight '' migrants has \hlt{risen by more than 50 per cent in just three years .} This is equivalent to \hlt{more than one in four white Britons in the UK .} The number of white Britons in the minority \hlt{has risen by more than 50 per cent in just three years .} \\
\bottomrule
\end{tabular}}}
\label{tab:appendix-case-3}
\end{table*}

\section{Introduction}
\label{sec:introduction}
\input{1introduction}

\section{Related Work}
\label{sec:related}
\input{2related}

\input{3method}

\section{Experiments}
\label{sec:Experiments}
\input{4experiments}

\section{Conclusions}
\label{sec:conclusions}
\input{5conclusions}

\balance