{'fraction_non_alphanumeric': 0.04300252017736945, 'fraction_numerical': 0.01451494560883019, 'mean_word_length': 4.682073590719594, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Character-Level Length-Control Algorithm for Non-Autoregressive Sentence Summarization

Sentence summarization aims at compressing a long sentence into a short one that keeps the main gist, and has extensive real-world applications such as headline generation. In previous work, researchers have developed various approaches to improve the ROUGE score, which is the main evaluation metric for summarization, whereas controlling the summary length has not drawn much attention. In our work, we address a new problem of explicit character-level length control for summarization, and propose a dynamic programming algorithm based on the Connectionist Temporal Classification (CTC) model. Results show that our approach not only achieves higher ROUGE scores but also yields more complete sentences.


Introduction
Sentence summarization aims at compressing a long sentence into a short one that keeps the main gist of the input. It is an established setting of summarization, and has extensive real-world applications such as headline generation [24,28,8]. In previous work, researchers have developed various approaches to improve the ROUGE score, which is the main evaluation metric for summarization [16], whereas controlling the summary length has not drawn much attention.
Recently, Liu et al. [19] show that length control is the key to summarization, since it is typically required by real-world applications. Moreover, the ROUGE score is found to be sensitive to the summary length [31,30], and summarization systems can achieve higher scores by simply generating longer output. In previous work, a typical setting of length control is to set a word budget for summarization [31,17].
In this paper, we address explicit length control in the character level for summarization, which is a different setting from previous work. In other words, we constrain the summary length by the number of characters, such as letters, punctuation marks, and spaces. We observe that this is a more realistic setting in real-world applications than word-level length control. For example, the headline shown in a mobile app or web page is constrained by the screen width (roughly speaking, the number of characters), rather than the number of words.
We further observe that controlling the summary length by characters cannot be easily addressed by previous approaches. For example, truncating is able to explicitly control the length, but the resulting summary is incomplete; Takase and Okazaki [34] feed length embeddings into the model as input, but such an approach cannot control the summary length in an explicit manner; and Schumann et al. [31] perform constrained discrete optimization by selecting a certain number of words from the source text as the output, but their generated summaries may vary to a large extent in terms of the number of characters.
To this end, we propose NACC, a Non-Autoregressive summarization model with Character-level length Control. We adopt a non-autoregressive approach because it generates all tokens in parallel and is much faster than autoregressive models. Moreover, we observe that non-autoregressive models predict the output words independently. Such predicted probabilities are thus local, which provides us with the unique opportunity to design a dynamic programming algorithm to constrain the summary length. Specifically, we formulate length control as a knapsack-like problem, where the weight is the number of characters in a token and the value is the predicted probability of the token. In this way, we are able to explicitly control the summary length at the character level, while retaining the completeness of the output text.
We evaluated our NACC model on the Gigaword headline generation [10] and DUC2004 [25] datasets in both supervised and unsupervised settings. In the latter setting, NACC learns from the pseudo-reference given by an unsupervised word-extraction method based on discrete search [31]. Experiments show that NACC establishes the state-of-the-art performance of non-autoregressive summarization under various target lengths in both supervised and unsupervised settings; NACC even outperforms autoregressive Transformers [35] in the unsupervised setting, where the input and output have stronger correspondence. These all confirm the effectiveness of our length-control algorithm. Regarding inference efficiency, we show that non-autoregressive models without length control are 10 times faster than autoregressive ones; even with our length-control dynamic programming, NACC is still several times more efficient. Further, our NACC is capable of length-transfer generation, i.e., generating summaries of different lengths from the training targets.

Related Work
Non-Autoregressive Generation. Non-autoregressive (NAR) models [12] predict target tokens in parallel and thus enjoy a much higher inference efficiency than autoregressive (AR) ones, which generate output tokens sequentially. NAR generation is more difficult than AR, because there lacks dependencies among the outputs. Previous work addresses the dependency issue by iterative refinement [15,20,3] or structured decoding with the conditional random field (CRF) [33,32,4].
The Connectionist Temporal Classification (CTC) algorithm [11] addresses a common problem in NAR generation, namely, token repetition, by merging consecutive identical tokens (unless separated by an empty token). Our work follows Liu et al. [17], who adopt CTC for NAR summarization, allowing empty tokens scattering over the entire sentence to generate a short summary.
NAR models are traditionally thought to generate worse-quality text than AR models. However, we have the unique insight that NAR also brings new opportunities for designing length-control algorithms: since the model predicts output independently, the decoding problem can be divided into shared sub-problems for dynamic programming.
Summarization Systems. Summarization systems can be generally categorized into two types: extractive and abstractive. Extractive methods output a summary by extracting important sentences or clauses from the source text [5,21,14], while abstractive methods generate summaries with new expressions [23,26,9].
Depending on the availability of training data, we may categorize summarization systems into supervised and unsupervised ones. Supervised methods typically follow a sequence-to-sequence (seq2seq) paradigm [40,18]. Recently, unsupervised summarization is drawing increasing attention because it does not require parallel training data. Yang et al. [39] use the lead approach (selecting the first several words or sentences) as pseudo-groundtruth for seq2seq training. Alternatively, cycle consistency is adopted as the training objective for unsupervised summarizaiton [36,2]. Schumann et al. [31] generate a summary by maximizing a heuristically defined scoring function (involving fluency and semantic similarity) with word-level extraction. We consider both settings in our work.
Controlling the output length is crucial for deploying summarization systems to real-world applications. In early extractive summarization research, truncating is adopted for fair comparison [21,22,14], but the resulting summary may not be complete sentences. As pointed out by [30,31], however, the length-control problem is not adequately addressed for abstractive summarization in the neural era, probably because researchers do not want to hurt the completeness. For example, length information [19,34] and soft penalty [32] are adopted to encourage short summaries, but they cannot control the length in an explicit way. Very recently, Schumann et al. [31] address the length-control problem by extracting a certain number of source tokens as the summary. Liu et al. [17] design a CTC-based algorithm that controls the output words explicitly. However, these approaches cannot be applied to the character level.
Our work follows Liu et al. [17] and adopts CTC as the training objective. However, we propose a character-level length-control algorithm that can explicitly constrain the number of characters within a given budget, which is different from all previous work.

Approach
In this section, we first introduce the CTC-trained NAR model for summarization ( §3.1). Then, we propose a dynamic programming algorithm to explicitly control the number of characters ( §3.2).

A Non-Autoregressive Model for Summarization
In the summarization task, the goal is to compress a source text x = (x 1 , x 2 , · · · , x S ) into a shorter text y = (y 1 , y 2 , · · · , y T ), while preserving the key information.  Figure 1: Overview of our NACC approach. Dashed yellow arrows refer to transitions that do not increase the summary length, while solid blue arrows refer to the increase of length. Thick arrows and blocks refer to the selected path by CTC. Due to the space limit, is omitted in the predicted sentence, and we use (S) to denote a sequence of S s. The number demonstrates the value (i.e., log-probability) of a word.
Encoder-Only Architecture. Our work follows recent non-autoregressive summarization methods [32,17], utilizing the encoder-only Transformer [35] as the base model ( Figure 1a). It is essentially a stack of Transformer layers, the last of which predicts all words simultaneously; thus, it has a much higher inference efficiency than autoregressive models.
Formally, let E (i) ∈ R S×d be the contextual representation of the input x at the ith Transformer layer, where S is the number of tokens in x and d is the dimension. Specially, E (0) is the word and positional embeddings of input tokens. Each layer is a Transformer block [35] based on its predecessor, which can be denoted by At the last layer E (L) , a softmax function is applied to predict the probability at every prediction slot independently, given by P s (·|x) = softmax(W e (L) s ) for input slot s = 1, · · · , S, where e (L) s is a column vector transposing the sth row of matrix E (L) , and W is a weight matrix.
Such an encoder-only architecture is able to capture the strong correspondence between the input and output in the summarization task and outperforms encoder-decoder non-autoregressive models, shown by Liu et al. [17].
CTC Training. Training the above encoder-only architecture requires padding the target with empty tokens ; otherwise, the output will have the same length as the input, and cannot be a summary. Gu et al. [12] pad s at the end of the target, but this hinders the input-output correspondence.
Instead, we follow Liu et al. [17] and train our model with the Connectionist Temporal Classification (CTC) [11], allowing s to scatter over the entire target summary as appropriate. During inference, the CTC approach removes s to generate a shorter text as the summary. In addition, CTC merges consecutive identical tokens that are not separated by , because non-autoregressive generation suffers from the word-repetition problem [12,29]. We denote the CTC operation as Γ, for example, Γ(aa abb ) = aab.
For training, CTC maximizes the marginal likelihood of token sequences (including ) that can be reduced to the target text y: where P (w|x) is the probability of generating a token sequence w = w 1 , · · · , w S , and P s (w s |x) is given by the non-autoregressive model. Although a brute force summation in Eqn. (1) is intractable, it can be efficiently computed by dynamic programming. We refer interested readers to Alex et al. [11] for the details of the above marginalization in CTC training.

Proposed Algorithm for Character-Level Length-Control Decoding
One of our main contributions is to propose a dynamic programming (DP) algorithm for character-level length control. mentioned in §1, controlling the number of characters in the output is important for summarization, since real-world applications usually involve character-level length constraints.
Our insight is that a non-autoregressive model predicts probabilities independently, so the length-control problem can be divided into shared sub-problems, making DP algorithms feasible. We formulate character-level length control as a knapsack-like problem. We treat the number of characters in a word (plus one) as the weight, 2 denoted by u(w) for the word w, and the predicted log-probability as the value v s (w) = log P s (w|x) for the prediction slot s. Our goal of character-level length-control summarization can be formulated as where U is the total length budget. Here, the value is the sum of the log-probability of every generation slot including , whereas the length is said in terms of the words of the CTC-reduced sequence y = Γ(w 1 , · · · , w S ).
We observe that handling every possible integer weight (i.e., length) as in a standard knapsack algorithm may slow down the inference. Thus, we divide the lengths into buckets for efficient inference. Formally, let the lth bucket cover the length ranging from α · (l − 1) + 1 to α · l characters, where α is a hyperparameter controlling the bucket size. We denote by d s,l = d s,l 1 · · · d s,l s the most probable s-token sequence that is reduced to a summary in the lth length bucket. Specially, we let d s,0 mean that the reduced summary has zero words.
The initialization of d s,l fills in the DP table for l = 0 and s = 1.
• For l = 0, we must have d s,0 = · · · (s-many), because l = 0 means no non-word has been generated. (First row of Figure 1b.) • For s = 1, we have Here, l = 0 is the same as the previous bullet item. For l > 0, we select the most probable word for each length bucket according to the value v 1 (·), i.e., the predicted log-probability of the first generation slot. (First column of Figure 1b.) The DP recursion is to compute d s,l based on a newly predicted token w s , assuming its top-left sub-table is filled. This involves three scenarios: • Case 1: w s = . In this case, the new word is . Thus, the index for generation slots increases from s − 1 to s, but the summary length does not change. We denote D s,l 1 as the set containing the candidate sequence, given by D s,l 1 = d s−1,l ⊕ (4) where ⊕ denotes string concatenation. (See yellow dash arrows in Figure 1b.) • Case 2: w s = , but w s = d s−1,l s−1 . In other words, the candidate non-word w s for the sth slot is identical to the last token of d s−1,l . Since repeated tokens are merged during CTC decoding, the output length index l is unchanged. We include this sequence in a set: for some l ≤ l. That is, w s is neither nor repetition, and thus the summary length will be increased from bucket l to l. We denote this candidate set by Then, our DP finds the most probable sequence at each recursion step: where d s is the sth token of a sequence d from the three candidate sets above. Theorem 1.
(1) If the bucket size α = 1 and consecutive repetitions are not merged, then d S,T is the most probable sentence of T characters given by the S prediction slots. (2) If α = 1 or repeating tokens are merged, our algorithm may not be exact. See the appendix for the proof.
Discussion. Our DP algorithm is inspired by the standard 0-1 knapsack problem [1], but also differs in several significant ways. First, we merge consecutive tokens during CTC decoding; this establishes some dependencies among different generation slots, and thus exact inference with DP is not possible. Second, our value function is non-stationary, as it changes over time. We require that every slot should select a token, either or a word. In both cases, the token's value is added to the total value. Therefore, our algorithm is compatible with negative values, namely, log-probabilities in our application, because only the relative difference matters for the value function.

Setup
Datasets. Our model is evaluated on the Gigaword headline generation [28] and DUC2004 datasets [25]. The Gigaword dataset comprises pairs of news articles and titles; we follow the standard setting [28,31,17] and adopt the first sentence of each news article as the input and consider the news title as the summary. In total, the dataset contains 3.8M, 198K, and 1951 samples for training, validation, and test, respectively. On the other hand, the DUC2004 dataset has 500 paired samples and is designed to be test-only; its performance is obtained by models trained on Gigaword.
Implementation Details. We use a Transformer encoder as the base model, which has 6 layers and 8 attention heads for each layer, following the settings in [35]. The dimensions are 512 and 2048 for the attention and feed-forward modules, respectively. Each training batch contains samples amounting to 4K tokens. The learning rate is chosen from {1e-4, 5e-4} by validation, and we ran 100K gradient updates for the unsupervised setting, but 400K updates for the supervised setting. Note that, in the unsupervised setting, our model learns from an extractive search-based method [31], and thus its training is relatively easy. By contrast, the supervised setting takes human-written sentences as the training targets, which are more abstractive and difficult to train with. All experiments were run on an i9-9940X CPU and an RTX6000 GPU.
For our length-control algorithm, we adopt a bucket size of 4, and only consider the most probable 20 words for every generation slot (cf. w s in Eqn. 6) due to efficiency concerns.

Results and Analyses
Results on Gigaword Headline Generation. Table 1 presents the performance on the Gigaword test set in both supervised and unsupervised settings. For the supervised setting, we train with the groundtruth references, which contain 51.29 characters on average. In the unsupervised setting, the training targets of machine learning models (Rows 9-13) are the output summaries given by an unsupervised search-based method [31]; specifically, we adopt the standard 8-word setting, which counts to 48.75 characters on average. Based on these, we set our length constraint to be 50 characters. We observe that our proposed algorithm is the only machine learning-based approach that can perform explicit character-level length control. For fair comparison, we truncate the output of other methods to satisfy the length constraint.
As seen, NACC even with truncating outperforms all other non-autoregressive (NAR) models [32,27,38] in both settings. Specifically, Su et al. [32] emit multiple end-of-sequence tokens at the end of the output sequence to generate a shorter summary than the source text (Rows 1 & 9); Qi et al. [27] propose to pretrain a summarization system in an autoregressive manner, and gradually adapt it to the NAR setting (Rows 5 & 10); Yang et al. [  strategy of autoregressive part-of-speech (POS) prediction and non-autoregressive summary generation (Rows 6 & 11). Our NACC trained by CTC is able to surpass all these methods, demonstrating the effectiveness of CTC training for summarization. Besides, NACC outperforms its search-based teacher model [31], showing that learning can smooth out the search noise.
Equipped with the length-control algorithm, our NACC model has a significant boost in terms of ROUGE scores. In a fair comparison with the same base architecture, the length-control algorithm alone improves NACC (truncate) bỹ 3 points. Our full model achieves an improvement of more than 4 total ROUGE points compared with previous state-of-the-art NAR methods.
Regarding the inference efficiency, NACC with truncating is faster than previous NAR models. Even with the lengthcontrol algorithm, our NACC is still in the same ballpark, being~500x faster than the search-based method.
Additionally, we design a variant of the unsupervised summarization method based on [31], where we directly impose the character-level length constraint during each search step (Row 8). We find this approach outperforms truncating word-constrained search (Row 7), but is much worse than our machine learning-based NACC with the length-control algorithm.
Results on DUC2004. Table 2 shows the performance of NACC on DUC2004, where we constrain the summary length to be at most 75 characters, following previous work [37,2,31]. Since the Gigaword training summaries have very different lengths from DUC2004 summaries, it is not straightforward to evaluate NACC in the supervised setting, as this involves length transfer. Therefore, we consider the unsupervised setting for DUC2004, where we use 13-word summaries (~80 characters) from [31] Table 4: Comparing autoregressive (AR) and non-autoregressive (NAR) models on the Gigaword headline generation test set. Our length-control algorithm requires the predicted probabilities to be independent, and thus is not compatible with AR models.
Human Evaluation. We additionally conduct human evaluations to investigate the effect of our length-control algorithm in terms of the completeness of summaries, which may not be captured by automatic metrics such as ROUGE scores. For controlled comparison, we consider NACC with truncating and NACC with the proposed length-control algorithm.
We invite three human annotators to compare the output summaries on each of 150 randomly selected samples from the Gigaword test set. We adopt the unsupervised setting in Table 1, where models are trained with 8-word summaries generated by [31]. The two systems' outputs for a sample are blindly given to annotators in a random order; annotators then vote for the better summary or a tie, regarding the overall quality and completeness/fluency separately. We count the votes for each decoding method on the two evaluation criteria, and show the percentage of wins/ties/loses on all samples in Table 3 As seen, our length-control decoding has a dominant advantage over the truncating method in terms of both the overall quality and completeness/fluency. Further, this result is statistically significant based on a two-sided binomial test (ignoring ties), verifying that our length-control algorithm indeed improves the quality and completeness of the predicted summaries.
Comparison with Autoregressive Models. We are curious about how our non-autoregressive NACC is compared with autoregressive (AR) methods. Thus, we train a standard AR Transformer with truncating and length-control decodings, and show results in Table 4.
As seen, our length-control algorithm is not compatible with the AR Transformer and hurts the ROUGE scores (Rows 2 & 6). This is because our algorithm is based on dynamic programming and requires model outputs to be local, so that the length-control problem can be divided into shared sub-problems; however, the predicted probabilities of the AR Transformer depend on partial generation at previous time steps. Note that this is not a disadvantage of our approach, but shows that NAR generation provides unique opportunities for length control.
Admittedly, NACC has slightly lower ROUGE scores than AR Transformers in the supervised setting (Rows 1-4), because human-written summaries are flexible, causing difficulties for NAR training. Nevertheless, our NACC achieves much higher inference efficiency, and outperforms all previous NAR systems (recall Table 1).
In the unsupervised setting, our approach achieves higher performance than the AR Transformer, which is a very strong result. This is because we learn from a search-based method that extracts source words as the summary [31], and our CTC training-with blank tokens scattering over the whole output sentence as appropriate-can capture such strong correspondence between input and output. Moreover, the proposed length-control algorithm is able to maintain the summary completeness given the length constraint, achieving better ROUGE scores than NACC with truncating.   Analysis of the Length Bucket. Our dynamic programming is an approximate algorithm with a α-sized length bucket (see Figure 1b and §3.2). Here, we investigate the effect of the bucket size in terms of ROUGE scores (the arithmetic mean of R-1, R-2, and R-L) and inference efficiency in the unsupervised setting where training targets are 8-word summaries from [31], following Table 1.
As seen in Figure 2, the ROUGE score continuously decreases with a larger bucket size (thick orange curve). This not only confirms the inexactness of our algorithm, but also shows that a small bucket size does not hurt the performance much. On the other hand, the inference time decreases drastically at the beginning (thin blue curve) because we have fewer dynamic programming steps; as the bucket size increases, the inference time convergences to NACC without length control. Based on this analysis, we set the bucket size to be 4 in our experiments.
Length-Transfer Generation. Our NACC model is capable of length-transfer generation, that is, generating summaries of different lengths from the training targets. Such generation is important to real-world applications where summaries of various lengths are needed for the same input, e.g., fitting different screen widths. Although generating a short enough summary may satisfy all possible length constraints, a longer summary that better utilizes the length budget can preserve more information; this is also reflected by ROUGE scores, which prefer longer summaries, as shown in [31]. Figure 3 compares the performance of NACC with Su et al. [32] when learning from 8-word summaries in the unsupervised setting. When the inference length budget is less than training (x-axis < 50), the ROUGE score of NACC decreases almost linearly with a decreasing length budget, but Su et al. [32]'s approach degrades faster than ours. For x-axis > 50, we find the soft penalty in [32] is unable to generate longer summaries than trained (shown by the dashed orange line), whereas our approach is able to utilize the increased length budget and achieve higher ROUGE scores.
Case Study. Table 5 shows example summaries generated by NACC and the AR Transformer on the Gigaword test set.
As seen, a model without length control may generate a summary that happens to have the desired length (AR Transformer in the supervised setting), a shorter summary (NACC in the supervised setting), or a longer summary (both AR Transformer and NACC in the unsupervised setting). A shorter summary fails to utilize the full length budget, leading to less information conveyed, whereas a longer summary requires truncating for explicit length control. Both cases are undesired.
By contrast, our proposed algorithm is able to generate a summary whose length is close to but less than the length budget. The resulting summary is more complete than truncating, and better keeps the key information.

Conclusion
In this work, we propose a Non-Autoregressive Summariation model with Character-level length Control (NACC), which can explicitly control the number of characters in the predicted summaries. Experiments show that our NACC approach not only achieves the state-of-the-art non-autoregressive (NAR) performance on Gigaword and DUC2004 datasets under length constraints. but is several times faster than autoregressive (AR) models, and even outperforms an AR Transformer in the unsupervised setting. Moreover, our approach is able to perform length-transfer generation, that is, generating summaries of different lengths from the training set.
Limitation and Future Work. Our proposed length-control algorithm only works with non-autoregressive models, which is a limitation (but not a disadvantage) of our work. We have clearly stated this throughout the paper.
Our NACC approach-although largely outperforming previous NAR models and retaining high inference efficiencyachieves lower ROUGE scores than AR models. This is the limitation of all NAR approaches in general, and can be addressed by future work. We nevertheless outperform AR models in the unsupervised setting.
A Proof of Theorem 1 Theorem 1. (1) If the bucket size α = 1 and consecutive repetitions are not merged, then d S,T is the most probable sentence of T characters given by the S prediction slots. (2) If α = 1 or repeating tokens are merged, our algorithm may not be exact.
Proof. [Part (1)] Our NACC is trained by the Connectionist Temporal Classification (CTC) algorithm [11], which merges repeated consecutive tokens and removes s in the output sequence. Since the merging operation establishes dependencies between tokens in the output sequence, our length-control algorithm is inexact.
In this part, we consider a variant of the CTC algorithm that does not merge repeated tokens but only removes s; we denote this modified reduction operation by Γ . For example, Γ (aa abb ) = aaabb. Our thus revised algorithm works as follows.
We denote d s,l = d s,l 1 · · · d s,l s as the recursion variable, being the most probable s-token sequence that is reduced to a summary of length l.
The initialization of d s,l is the same as the original length-control algorithm ( §3.2), since the merging operation is not involved here. However, the recursion involves only two cases: • Case 1: w s = . The recursion of this case is also the same (see Eqn. 4): • Case 2: w s = . We have a set of candidate sequences: This is analogous to Eqn. (6), where α = 1 (due to our theorem assumption). Also, the condition w s = d s−1,l s−1 in Eqn. (6) is dropped here because this algorithm variant does not merge repeated tokens.
Then, the algorithm chooses the most probable candidate sequence as d s,l , given by Now we will prove that the algorithm is exact: suppose P s,l := s i=1 v i ( d s,l i ) is the log probability of d s,l , we have P s,l = max d1···ds:|Γ (d1···ds)|=l In other words, d s,l is the most probable s-token sequence that is reduced to length l. This is proved by mathematical induction as follows.
Base Cases. For l = 0, the variable d s,0 can only be s-many s. The optimality in Eqn. (11) holds trivially.
We will show that the algorithm finds the sequence d s,l with P s,l = max d1···ds:|Γ (d1···ds)|=l Word P 1 (·|x) P 2 (·|x) I 0.3 0.1 am 0.4 0.6 a 0.2 0.05 0.1 0.25 Table 6: A counterexample showing that our algorithm may be inexact if α = 1 or repeated tokens are merged. Here, we set the vocabulary to be three words plus a blank token .
According to Eqn. (10), the variable d s,l is the most probable sequence in D s,l 1 ∪ D s,l 2 . Thus, we have P s,l = max l ,ds:l +u(ds)=l = max Here, (13) separates the max operation over l and d s ; (14) is due to the induction hypothesis; (15) holds because the two max terms in (14) are independent given l , and thus the summations can be grouped; and (16) further groups the two max operations with l eliminated. The last two lines are original proved in [13] and also used in [7].
[Part (2)] We now prove our algorithm may be inexact if α = 1 or repeated tokens are merged. We show these by counterexamples. 4 Suppose α = 1 and in particular we assume α = 2. We further assume repeated tokens are not merged. Consider the example shown in Table 6. The length-control algorithm finds d 1,1 = {"am"}, and then d 2,2 = {"am I"} with the probability of 0.4 · 0.1 = 0.04, as the first bucket covers the length range [1,2] and second [3,4]. Here, we notice that two words are separated by a white space, which also counts as a character). However, the optimum should be {"I am"}, which has a probability of 0.3 · 0.6 = 0.18.
The above theoretical analysis helps us understand when our algorithm is exact (or inexact). Empirically, our approach works well as an approximate inference algorithm.