ROUGE-L
How it works
1) Candidate and reference are tokenized (optionally with stemming and stop-word removal). 2) The Longest Common Subsequence (LCS) is computed — the longest sequence of tokens appearing in both texts in the same order but not necessarily contiguously; solved by dynamic programming in O(m·n) time. 3) LCS recall R_lcs = LCS/m (m = reference length) and LCS precision P_lcs = LCS/n (n = candidate length) are computed. 4) The score is the F-measure: F_lcs = (1+β²)·R_lcs·P_lcs / (R_lcs + β²·P_lcs), where β = P_lcs/R_lcs controls the weight of recall relative to precision. 5) For summary level (ROUGE-Lsum), LCS is computed per sentence pair and unioned (union LCS), capturing the sentence structure of the whole summary.
Problem solved
Fixed-length n-gram metrics (like ROUGE-N or BLEU) penalize valid rewordings with different word order and require an arbitrary choice of n-gram length. ROUGE-L addresses this by measuring the longest order-preserving common subsequence, without requiring contiguity or a fixed n-gram length.
Components
Dynamic programming that finds the longest order-preserving common token subsequence, without requiring contiguity.
Combines LCS recall and precision into a single beta-weighted F-measure.
Summary-level LCS aggregation as the union of pairwise sentence LCS; sensitive to sentence splitting.
Official
Implementation
ROUGE-L (sentence-level) and ROUGE-Lsum (summary-level, with sentence splitting) differ; reporting without stating the variant yields incomparable results.
Different libraries (Perl ROUGE 1.5.5, rouge-score, pyrouge) produce different scores due to differing tokenization, stemming and stop-word handling.
ROUGE-L measures only lexical overlap and order; correct paraphrases with different words are undervalued.
Evolution
Chin-Yew Lin defines the ROUGE package, including the LCS-based ROUGE-L, at the Text Summarization Branches Out workshop.
ROUGE becomes the standard evaluation metric at the Document Understanding Conference.
Models such as the pointer-generator (See et al., 2017) report ROUGE-1/2/L as the primary metric.
Work such as PEGASUS (Zhang et al., 2020) reports ROUGE-Lsum, popularizing the google-research/rouge-score implementation.
Hyperparameters (configurable axes)
The β parameter in the F-measure; in original ROUGE β=P_lcs/R_lcs, heavily favoring recall.
Sentence-level (ROUGE-L) vs summary-level (ROUGE-Lsum).
Optional stemming and stop-word removal; changes values and cross-study comparability.
Computational complexity
Time complexity: O(m · n). Space complexity: O(m · n).
Compute bottleneck
Cost dominated by filling the m×n DP table for each candidate-reference pair; negligible for typical text lengths.
Parallelism
A single pair's LCS is internally sequential, but dataset-level evaluation is fully parallel.
Hardware requirements
Lightweight string-based algorithm; computed on CPU with no need for accelerators.