A Decoding Algorithm for Length-Control Summarization Based on Directed Acyclic Transformers Chenyang Huang, Hao Zhou, Cameron Jen, Kangjie Zheng, Osmar R. Zaïane, Lili Mou Abstract Length-control summarization aims to condense long texts into a short one within a certain length limit. Previous approaches often use autoregressive (AR) models and treat the length requirement as a soft constraint, which may not always be satisfied. In this study, we propose a novel length-control decoding algorithm based on the Directed Acyclic Transformer (DAT). Our approach allows for multiple plausible sequence fragments and predicts a path to connect them. In addition, we propose a Sequence Maximum a Posteriori (SeqMAP) decoding algorithm that marginalizes different possible paths and finds the most probable summary satisfying the length budget. Our algorithm is based on beam search, which further facilitates a reranker for performance improvement. Experimental results on the Gigaword and DUC2004 datasets demonstrate our state-of-the-art performance for length-control summarization. 1 1 1 Our code, output, and data are available at https://github.com/MANGA-UOFA/DAT-LenC * * footnotetext: Work partially done during an internship at AIR † † footnotetext: Corresponding author ‡ ‡ footnotetext: Canada CIFAR AI Chair 1 Introduction Summarization systems aim to condense lengthy text into a shorter form, while preserving key information Nenkova et al. (2011) ; Rush et al. (2015) ; Schumann et al. (2020) ; Tsvigun et al. (2022) . Recent studies underscore the importance of length-control summarization Liu et al. (2018) ; Takase and Okazaki (2019) ; Liu et al. (2022a) . For example, the Google search engine limits webpage title displays to 63 characters, tweets have a 280-character cap, and scientific paper abstracts are typically restricted to a few hundred words. Most previous text summarization methods rely on autoregressive (AR) models Sutskever et al. (2014) ; Vaswani et al. (2017) , which generate a summary word by word. For length control, AR models typically treat the summary length as an additional signal during both training and inference Liu et al. (2018) ; Takase and Okazaki (2019) . However, such methods do not strictly control the generation length, and thus fall into the soft-constraint category. Recently, non-autoregressive (NAR) models Gu et al. (2018) ; Lee et al. (2018) have been applied to text summarization Su et al. (2021) ; Liu et al. (2022a) . Unlike its autoregressive counterpart, an NAR model predicts target words independently so that the length-control text generation problem can be decomposed into shared sub-problems, facilitating dynamic programming for efficient computation Liu et al. (2022a) ; Liu et al. (2022b) . Such methods fall into the hard-constraint category. Specifically, Liu et al. (2022a) ; Liu et al. (2022b) apply the Connectionist Temporal Classification (CTC) model Graves et al. (2006) , which allows placeholders and repetitions during generation but removes them in a post hoc manner. However, these CTC-based methods tend to produce word-level extractive summaries due to their restricted modeling capacity. As a result, the generated summaries contain very few new words and mostly preserve the original word order Chuang et al. (2021) ; Shao and Feng (2022) . In this work, our first insight is to apply the Directed Acyclic Transformer ( Huang et al., 2022b , DAT,) for length-control summarization. DAT, originally introduced for machine translation, is a powerful NAR approach that expands its canvas to allow multiple plausible text fragments and predicts links to connect them (the links along with the predicted words are called a path ). In this way, DAT is more flexible in predicting words and determining their order, resulting in better generation quality than CTC Huang et al. (2022b) ; Huang et al. (2023b) . For length-control decoding based on DAT, we propose a Sequence Maximum a Posteriori (SeqMAP) decoding objective, which marginalizes possible linked steps and seeks the most probable sequence satisfying the length budget. Our SeqMAP is different from the existing MAP decoding objective Shao et al. (2022) that seeks the most probable path (links and words), which we refer to as PathMAP. Since DAT training considers the marginalization of all possible links for a groundtruth sequence, our SeqMAP aligns with the training objective better (as it huggalso performs marginalization), and is expected to surpass PathMAP in length-control summarization. Compared with PathMAP, our SeqMAP is a more challenging decoding objective. The traditional PathMAP performs \arg\max for both links and words, which can be reorganized according to prediction time steps and accomplished by dynamic programming in one pass. On the contrary, our SeqMAP performs \arg\max for word selection after summing over all possible linked steps, but \max and \operatorname{sum} operations cannot be directly swapped to decompose the overall problem by time steps, breaking down the dynamic programming algorithm. To this end, we propose an approximate algorithm to address SeqMAP, where we nevertheless decompose the objective by time steps. For each step, we make a greedy selection for the \max operation, where we only consider a beam of high-probability sequences for the sum operation. Further, we may apply a reranker by a pretrained BERT model Zhuang et al. (2021) to select the best sequence in the beam for performance improvement. We perform extensive experiments using the Gigaword Graff et al. (2003) and DUC2004 Bommasani and Cardie (2020) datasets, following previous work in non-autoregressive length-control summarization Liu et al. (2022a) . Results show that both SeqMAP and PathMAP outperform existing models based on CTC, which justifies our choice of the DAT model. Further, our approximate algorithm for SeqMAP outperforms PathMAP even without the reranker, suggesting the superiority of the SeqMAP objective. Our reranker further improves the summarization quality consistently, demonstrating its effectiveness. 2 Methodology In this section, we first present the Directed Acyclic Transformer (DAT) and the existing PathMAP decoding method (Subsection 2.1 ). Then, we introduce our SeqMAP decoding objective, and develop a beam search-based dynamic programming algorithm to approach it (Subsection 2.2 ). Finally, we design a reranking process to select the best beam candidate (Subsection 2.3 ). 2.1 Length Control with DAT DAT Model. Our first contribution is the adaptation of the Directed Acyclic Transformer ( Huang et al., 2022b , DAT,) to the length-control summarization task. DAT is a non-autoregressive (NAR) model, capable of generating multiple plausible output segments, which are then selected and connected via links to form the final output. DAT provides more flexibility in word selection and ordering, compared with the existing NAR summarization system Liu et al. (2022a) , which is based on the Connectionist Temporal Classification (CTC) model Graves et al. (2006) . Consider the source text \mathbf{x}=(\mathrm{x}_{1},\cdots,\mathrm{x}_{T_{\mathrm{x}}}) and the corresponding groundtruth summary \mathbf{y}=(\mathrm{y}_{1},\cdots,\mathrm{y}_{T_{\mathrm{y}}}) , where T_{\mathrm{x}} and T_{\mathrm{y}} denote their lengths. To allow multiple plausible output segments, DAT expands its generation canvas by having S prediction steps, typically S\geq T_{\mathrm{y}} . At each step s\in\{1,\cdots,S\} , DAT makes a word prediction p_{\text{word}}^{(s)}(\cdot) and a link prediction p_{\text{link}}^{(s)}(\cdot) . In particular, the word prediction is given by \displaystyle p_{\text{word}}^{(s)}(\cdot|\textbf{x})=\operatorname{softmax}(\mathbf{W}_{\text{word}}\bm{h}_{s}) (1) where \mathbf{W}_{\text{word}}\in\mathbb{R}^{|\mathcal{V}|\times d} is a learnable matrix and \bm{h}_{s}\in\mathbb{R}^{d} is the decoder’s hidden state at step s , with d being the dimension and |\mathcal{V}| representing the vocabulary size. Link prediction forecasts the step of the subsequent word that follows the s th step: \displaystyle\begin{aligned} p_{\text{link}}^{(s)}(\cdot|\mathbf{x})=\operatorname{softmax}([\bm{k}_{s}^{\top}\bm{q}_{{s}+1};\cdots;\bm{k}_{s}^{\top}\bm{q}_{{S}}])\end{aligned} (2) where \bm{k}_{s}=\mathbf{W}_{\mathrm{k}}\bm{h}_{s} and \bm{q}_{s}=\mathbf{W}_{\mathrm{q}}\bm{h}_{s} are transformations of the hidden state, both \mathbf{W}_{\mathrm{k}} and \mathbf{W}_{\mathrm{q}} being learnable matrices in \mathbb{R}^{d\times d} . The [;] operation concatenates scalars into a column vector. Given a reference summary \mathbf{y} of length T_{\mathrm{y}} from the training set, the DAT model predicts links to connect T_{\mathrm{y}} -many steps among a total of S generation steps. We denote the linked steps by \bm{a}=(a_{1},\cdots,a_{T_{\mathrm{y}}}) , where 1=a_{1}<\cdots0 ) contains a special \langle\text{bos}\rangle token, indicating the beginning of a sentence. Additionally, the score for each u_{s}(\langle\text{bos}\rangle) is initialized to 1 . The DP recursion iteratively computes \mathcal{A}_{t,s} for every t>0 and every s such that t\leq s\leq S . We observe that each \mathcal{A}_{t,s} can be obtained by 1) expanding the length- (t-1) sequences in \mathcal{A}_{t-1,s-1} with words from the s th step, which results in sequences ending at step s , and 2) further merging them with the length- t sequences in \mathcal{A}_{t,s-1} , which approximates the best length- t sequences ending before step s . Therefore, we design a recursive step with an Expand operation and a Merge operation. Expand. Let \mathcal{B}_{t,s} be the approximated top- K length- t sequences that are generated exactly at the s th step. Intuitively, we can approximate \mathcal{B}_{t,s} by expanding sequences in \mathcal{A}_{t-1,s-1} with the word predictions at step s , given by \displaystyle\mathcal{B}_{t,s}=\operatorname{top-}\!K\Big\{\mathbf{b}\oplus\mathrm{v}\,\Big|\,\mathbf{b}\in\mathcal{A}_{t-1,s-1},\mathrm{v}\in\mathcal{V}\Big\} (13) When expanding a partial sequence with \mathrm{v}\in\mathcal{V} , our implementation only considers the top- V words based on the predicted word probability in Eqn. ( 1 ) to improve efficiency. For each expanded sequence in \mathcal{B}_{t,s} , the corresponding scores are given by \displaystyle u_{s}(\mathbf{b}\oplus\mathrm{v})=w_{s,\mathrm{v}}\,\sum_{s^{\prime}=t-1}^{s-1}\,u_{s^{\prime}}(\mathbf{b})\cdot l_{s^{\prime},s} (14) Here, we marginalize out different previous linked steps that may generate \mathbf{b} , which follows the spirit of the marginalization in our SeqMAP objective ( 11 ). Merge. By definition, \mathcal{A}_{t,s} approximates the best length- t sequences, which may be generated at the s th step (approximated by \mathcal{B}_{t,s} ) or before the s th step (approximated by \mathcal{A}_{t,s-1} ). Therefore, we can obtain \mathcal{A}_{t,s} by merging \mathcal{B}_{t,s} and \mathcal{A}_{t,s-1} : \displaystyle\mathcal{A}_{t,s}=\operatorname{top-}\!K\Big\{\mathcal{A}_{t,s-1}\cup\mathcal{B}_{t,s}\Big\} (15) where the \text{top-}\!K operation ranks the sequences by their total scores at and before the s th step, given by \sum_{s^{\prime}=t}^{s}u_{s^{\prime}}(\mathbf{b}) . This ensures that our approximation algorithm considers the marginalization over s in Eqn. ( 11 ). Appendix A provides the pseudocode of our decoding algorithm. Figure 1: The neural architecture of our reranker. This example assumes a beam size of K=3 . 2.3 Reranker Our SeqMAP beam search finds several high-probability summary candidates, providing an opportunity to further improve the generation quality using a reranker Och et al. (2004) ; Lee et al. (2021) ; Ravaut et al. (2022) . In particular, we train the reranker by predicting which beam candidate has the most overlapped words compared with the groundtruth summary. Neural Architecture. Figure 1 depicts the overall architecture of our reranker. First, we use the pretrained RoBERTa model Zhuang et al. (2021) to represent the source text \mathbf{x} and each of the summary candidates \mathbf{b}^{(k)} , for 1\leq k\leq K , individually. Then, we build a one-layer Transformer block to predict the best summary for \mathbf{x} . We start by proposing a novel approach of rank embeddings (initialized randomly and trained by backpropagation) to capture the rank of a candidate given by the DAT model. The rank embedding has the same dimension as RoBERTa, and the k th rank’s embedding is added to the RoBERTa representation of every word in the k th candidate. After that, self-attention is performed among the words in different candidates, and cross-attention is performed to fetch information from the source text. Finally, we pool the representations of all the time steps (including all the words in different candidates) and apply a K -way softmax to predict the best candidate. Training Objective. The target of the classification is the beam candidate \mathbf{b}^{(k)} having the highest number of overlapped words compared with the groundtruth summary \mathbf{y} of a training sample. We use the standard cross-entropy loss for training, and apply label smoothing Szegedy et al. (2016) to improve generalization. 3 Experiments 3.1 Setup Our experimental setups generally follow the previous non-autoregressive length-control studies Liu et al. (2022a) ; Liu et al. (2022b) . Datasets. We evaluated the proposed method on the Gigaword headline generation dataset Graff et al. (2003) and the DUC2004 dataset Bommasani and Cardie (2020) . The Gigaword dataset pairs news articles with their headlines; it contains 3.0M training pairs, 189K validation pairs, and 1951 test pairs. The DUC2004 dataset contains 500 samples, and is only used as a test set. The performance in the DUC2024 experiment is obtained by the model trained on Gigaword. Metrics. We used ROUGE scores Lin (2004) as the main metric for the quality evaluation of generated summaries. Specifically, we reported ROUGE- n , for n\in\{1,2\} , to measure the n -gram overlaps between the generated summary and the ground truth, and reported ROUGE-L to measure the length of the longest common subsequence. In addition, we used a large language model (LLM) as a surrogate for human evaluation. We performed pairwise comparisons between the generations of our SeqMAP and baseline models. We reported the win, loss, and tie percentages. Implementation Details. For the neural architecture of our DAT models, we used the Transformer-base Vaswani et al. (2017) as the backbone. To train the models, we used a batch size of 64K tokens, with a maximum of 100K updates. For regularization, we set the dropout rate to 0.1 and the label smoothing factor to 0.1. For decoding, our SeqMAP had a beam size of K=20 and a vocabulary exploration of V=5 , as mentioned after Eqn. ( 13 ). More details can be found in our GitHub repository (Footnote 1 ), where the configurations of training and inference are included. Ratio # Model %Truncate R-1 R-2 R-L R-Sum Length 20% 1 AT w/ Truncate 60.28% 33.16 15.02 30.91 79.09 6.1 2 AT-LenInfo w/ Truncate 1.03% 33.53 14.32 31.21 79.06 5.7 3 BERT-CRF w/ Truncate 39.98% 31.94 13.67 30.09 75.70 5.8 4 CTC Length Control 0.00% 34.14 13.61 31.96 79.71 6.9 5 DAT PathMAP 0.00% 35.19 16.95 32.84 84.98 6.9 6 DAT SeqMAP (Ours) 0.00% 36.34 17.29 33.81 87.44 6.9 7 w/o Reranking 0.00% 35.63 17.24 33.28 86.15 6.8 25% 1 AT w/ Truncate 33.52% 34.52 15.78 31.90 82.20 6.8 2 AT-LenInfo w/ Truncate 1.54% 35.12 16.19 32.60 83.91 7.3 3 BERT-CRF w/ Truncate 18.93% 32.85 14.23 30.86 77.94 6.2 4 CTC Length Control 0.00% 34.51 13.89 32.08 80.48 8.5 5 DAT PathMAP 0.00% 36.11 17.43 33.41 86.95 8.5 6 DAT SeqMAP (Ours) 0.00% 36.74 17.22 33.87 87.83 8.4 7 w/o Reranker 0.00% 36.30 17.40 33.64 87.34 8.4 30% 1 AT w/ Truncate 20.04% 35.07 16.00 32.35 83.42 7.1 2 AT-LenInfo w/ Truncate 4.66% 35.29 16.15 32.44 83.88 8.8 3 BERT-CRF w/ Truncate 9.65% 33.08 14.44 31.08 78.60 6.4 4 CTC Length Control 0.00% 34.04 13.63 31.49 79.16 10.0 5 DAT PathMAP 0.00% 35.57 16.65 32.88 85.10 9.9 6 DAT SeqMAP (Ours) 0.00% 36.24 16.74 33.34 86.32 9.9 7 w/o Reranker 0.00% 35.80 16.76 33.04 85.60 9.9 Table 1: Results on the Gigaword dataset, where we set the length constraint to be 20%, 25%, and 30% of the source length. %Truncate is the percentage of sentences that require truncation to meet the length requirement. R-1, R-2, R-L, and R-Sum denote the ROUGE-1, ROUGE-2, ROUGE-L, and the sum of the three ROUGE scores, respectively. 3.2 Results and Analyses Main Results on Gigaword. Table 1 presents our main results on the Gigaword dataset. For thorough comparison, we evaluate the approaches in three scenarios: setting the summary lengths to 20%, 25%, and 30% of the source text length. For non-strict length-control methods, the output will be truncated if the length exceeds the limit. We first include two baseline methods that do not have length control: 1) the standard autoregressive Transformer ( Vaswani et al., 2017 , AT,) , and 2) BERT-CRF Su et al. (2021) , which is a non-autoregressive method that uses BERT as the encoder Devlin et al. (2019) and applies a conditional random field ( Lafferty et al., 2001 , CRF,) for decoding. As seen in Table 1 , a large portion of the generated sentences from AT and BERT-CRF require truncation to meet the length requirement (Rows 1 and 3), resulting in incomplete summaries. Also, their ROUGE scores are low in general. We further consider a soft length-control method: AT-LenInfo Liu et al. (2018) , which integrates a length embedding to softly guide the output length of the autoregressive Transformer. As we can see, AT-LenInfo largely reduces the truncation ratio, while achieving similar ROUGE scores to AT. However, AT-LenInfo still has 1.03–4.66% of sentences truncated, suggesting that such a soft-constraint method is inadequate for length control. On the other hand, the CTC Liu et al. (2022a) and our DAT methods perform exact length control by dynamic programming; thus, no truncation is required (Rows 4–7). Among these models, our DAT (with any inference method) consistently outperforms CTC, verifying that DAT is a more powerful non-autoregressive model. We also observe that our SeqMAP method, with or without the reranker, is better than PathMAP, with only one exception (the R-2 score in the 25% setting); our reranker further improves the total ROUGE scores (R-Sum) by 0.49–1.32 points. The results verify the superiority of our SeqMAP objective and the effectiveness of our decoding algorithms. R-1 R-2 R-L R-Sum AT w/ Truncate 27.03 8.92 24.20 60.15 AT-LenInfo w/ Truncate 27.88 9.28 25.58 62.74 BERT-CRF w/ Truncate 23.69 7.16 21.64 52.49 CTC Length Control 28.67 8.29 26.34 63.30 DAT PathMAP 28.77 9.98 26.48 65.23 DAT SeqMAP (Ours) 30.11 10.29 27.22 67.62 w/o Reranker 29.17 10.27 26.66 66.10 Table 2: Results on the DUC2004 dataset. The summary length is set to 20% of the source length. Given the text: [Source] Consider two summaries of the text: Summary [ID1] : [Summary1] Summary [ID2] : [Summary2] A good summary is a shorter piece of text that has the essence of the original and adheres to coherence, faithfulness, relevance, and overall quality as defined above. Which summary is better? Answer: Table 3: Our prompt template for LLM-based pairwise evaluation. Here, “ Source ” is the text to be summarized. The choices of IDs are “1” and “2”; “ Summary1 ” and “ Summary2 ” are substituted with model-generated text. Since LLM is not robust to candidate ID and order Zheng et al. (2023) ; Shen et al. (2023) , we enumerate different combinations for a given case, resulting in four LLM queries. Pairwise Comparison Win Loss Tie Ours vs. AT w/ Trunc. 68.70% 0% 31.30% Ours vs. AT-LenInfo w/ Trunc. 69.45% 0% 30.55% Ours vs. CTC Length Control 72.40% 20.00% 7.60% Ours vs. DAT PathMAP 43.77% 32.04% 24.18% Table 4: LLM pairwise comparison between DAT SeqMAP and baseline methods. For each sample, we determine the outcome of “win,” “loss,” or “tie” based on the votes of the four LLM queries (by varying candidate order and ID tokens). We report the ratios of wins, losses, and ties of our model. Main Results on DUC2004. We report the performance on the DUC2004 dataset in Table 2 . As seen, the trends mirror those observed on the Gigaword dataset. In particular, our SeqMAP consistently outperforms other baselines in all metrics. Since the DUC2004 results are obtained from models trained on Gigaword, we conclude that our approach is transferable to different testing scenarios. LLM Evaluation. In addition to ROUGE scores, we prompt a large language model (LLM), in particular, gpt-4-0125-preview , serving as a surrogate for human evaluation. Concretely, we perform pairwise comparison between the outputs of our SeqMAP and baseline models on the Gigaword test set. For each comparison, we query an LLM four times by enumerating the order and IDs of the candidates for better robustness; the exact prompt is presented in Table 3 . Table 4 shows the results of LLM evaluation. We first observe that our SeqMAP dominates AT, AT-LenInfo, and CTC baselines with a winning rate of 68.80–72.40%. Further, our SeqMAP has an 11.73% higher winning rate than PathMAP with the same DAT backbone. Overall, our pairwise LLM evaluation is consistent with the comparison based on ROUGE scores (Tables 1 and 2 ), further verifying the effectiveness of our SeqMAP approach. # Model Word Novelty Reordering Degree 1 CTC 18.41% 8.69% 2 DAT PathMAP 21.80% 9.09% 3 DAT SeqMAP (Ours) 22.48% 9.01% 4 Human Reference 50.51% 8.05% Table 5: The word novelty and reordering ratio of CTC, DAT PathMAP, DAT SeqMAP, and the human reference. The results are based on the Gigaword test set. Generation Novelty. In this work, we hypothesize that the Directed Acyclic Transformer ( Huang et al., 2022b , DAT,) is more flexible in predicting words and determining their order, compared with the Connectionist Temporal Classification (CTC) model Graves et al. (2006) , which is used in Liu et al. (2022a) for length-control summarization. To verify this hypothesis, we adopt two metrics, namely word novelty and the reordering degree , to compare the generated summaries by DAT and CTC. In particular, word novelty measures the percentage of the summary’s words that are not in the source text, indicating the method’s flexibility in word choice. The reordering degree assesses the flexibility in generation order. It is computed by the following steps: 1) Align the words in the summary to the source text, 3 3 3 We use FastAlign Dyer et al. (2013) , a tool for word alignment, to obtain the target-to-source alignments. 2) Enumerate every pair of word positions (i,j) such that it then 13 \mathcal{A}_{t,s}:=\operatorname{top-}\!K\big\{\mathcal{B}_{t,s}\cup\mathcal{A}_{t,s-1}\big\} \triangleright Ranking is based on \sum_{s^{\prime}=t}^{s}u_{s^{\prime}}(\mathbf{b}) \triangleright Reranking 14 return the top reranked \mathbf{b} in \mathcal{A}_{T,S} according to our reranker (Section 2.3 )