ROUGE Scores › ROUGE-L: Longest Common Subsequence

While n-gram recall is intuitive, it has a significant limitation: it requires exact n-gram matches. If a candidate summary uses synonymous phrases or slightly reorders words, ROUGE-N treats these as complete failures even when the meaning is preserved. Consider a reference stating "The President announced new economic policies yesterday" and a candidate reading "Yesterday, the President announced new economic policies." A human would recognize these as nearly identical in meaning, but ROUGE-2 would score them poorly because the word "yesterday" has moved, breaking the bigrams "policies yesterday" and introducing "Yesterday the" which does not appear in the reference.

This fragility of n-gram windows motivates a more flexible matching approach. Rather than requiring words to appear in fixed-size windows, what if we could find the longest chain of words that appears in both texts, in the same order, regardless of what other words intervene? This is precisely the idea behind the Longest Common Subsequence.

ROUGE-L addresses this by using the Longest Common Subsequence (LCS). A subsequence is a sequence that appears in the same relative order but not necessarily consecutively. For example, "the cat sat" is a subsequence of "the fluffy cat lazily sat," while "cat the" is not (wrong order). The LCS finds the longest chain of words that appears in both texts while maintaining sequence integrity. It offers flexibility that rigid n-gram windows cannot give.

The LCS is computed using dynamic programming in $O(mn)$ time, where $m$ and $n$ are the lengths of the two sequences. The algorithm builds a table where cell $(i, j)$ stores the length of the longest common subsequence of the first $i$ tokens of the reference and the first $j$ tokens of the candidate. If the tokens at positions $i$ and $j$ match, the LCS extends by one from the diagonal cell; otherwise it takes the maximum of the left and upper cells, representing the best LCS achievable by dropping one token from either sequence.

ROUGE-L computes precision and recall based on the LCS length between candidate $C$ and reference $R$:

$$\begin{aligned} R_{\text{lcs}} &= \frac{\text{LCS}(C, R)}{|R|} \\[6pt] P_{\text{lcs}} &= \frac{\text{LCS}(C, R)}{|C|} \end{aligned}$$

where:

• $R_{\text{lcs}}$: the recall based on the longest common subsequence
• $P_{\text{lcs}}$: the precision based on the longest common subsequence
• $|R|$: the length (in words) of the reference summary
• $|C|$: the length (in words) of the candidate summary
• $\text{LCS}(C, R)$: the length of the longest common subsequence between candidate and reference

These are then combined into an F-measure:

$$\text{ROUGE-L} = \frac{(1 + \beta^2) \cdot R_{\text{lcs}} \cdot P_{\text{lcs}}}{R_{\text{lcs}} + \beta^2 \cdot P_{\text{lcs}}}$$

where:

• $R_{\text{lcs}}$: the recall based on the longest common subsequence (defined above)
• $P_{\text{lcs}}$: the precision based on the longest common subsequence (defined above)
• $\beta$: a parameter controlling the relative importance of precision versus recall; when $\beta$ is large (typically $\beta > 1$), recall is weighted more heavily. In standard implementations, $\beta$ is often set such that recall is weighted more than precision (e.g., $\beta = 1.2$), though many implementations use $\beta = 1$ (standard F1)

The use of F-measure rather than pure recall is an important departure from ROUGE-N. Because the LCS can be short relative to the candidate length (imagine a candidate that rambles extensively but contains a small core that matches the reference), precision becomes relevant. If we only measured recall, a candidate containing the entire reference embedded in a much longer document would score perfectly, even though most of the candidate is irrelevant. The F-measure balances these concerns, rewarding summaries that efficiently capture the reference content without excessive verbosity.

The LCS approach gives several advantages for summarization evaluation. Each advantage addresses a specific failure mode in n-gram-based metrics:

First, the LCS works well with sentence-level paraphrasing. If a candidate summary restructures a sentence while keeping key phrases in order, LCS records this similarity. For instance, if the reference says "The company reported record profits despite economic headwinds" and the candidate says "Despite economic headwinds, the company reported record profits," the LCS includes all major content words in the correct order, even though the sentence structure changed. The n-gram approach breaks down here because the fronting of "Despite economic headwinds" disrupts all the bigrams that cross the clause boundary.

Second, unlike n-grams which require arbitrary window sizes, LCS automatically identifies the longest matching sequence, effectively adapting to local similarity structures. It doesn't force us to choose between unigrams (too permissive) and bigrams (too strict); instead, it finds the natural alignment between texts. This adaptivity is especially useful when the summary length and structure differ materially from the reference.

Third, adding words to the candidate doesn't break the LCS calculation the way it breaks n-gram precision. If a candidate inserts "significant" before "profits" in the example above, ROUGE-2 would drop bigram matches around that insertion, but ROUGE-L would simply treat "significant" as a gap in the subsequence, preserving the rest of the match. This robustness to word insertion makes ROUGE-L more forgiving of paraphrases that add modifiers or clarifications.