---
title: "A Scalable Global Model for Summarization — Gillick 2009"
description: "The paper addresses extractive multi-document summarization, where sentences must be chosen to be informative without repeating each other."
authors: ["Dan Gillick", "Benoit Favre"]
year: 2009
venue: "Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing"
source: "https://aclanthology.org/W09-1802/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/gillick-2009-scalable-global-model-summarization/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/gillick-2009-scalable-global-model-summarization/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2009](https://md.research.elamur.ai/free/en/papers/2009/) / A Scalable Global Model for Summarization

# A Scalable Global Model for Summarization

**Authors:** [Dan Gillick](https://md.research.elamur.ai/free/en/authors/dan-gillick/), [Benoit Favre](https://md.research.elamur.ai/free/en/authors/benoit-favre/) · **Year:** 2009 · **Venue:** Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/W09-1802/) · [PDF](https://aclanthology.org/W09-1802.pdf) · [OpenAlex](https://openalex.org/W2150869743)

**Citations:** 280 citations (openalex-snapshot · 2026-10-14) · [96](#cited-by) in our library, of the 140884 papers whose bibliographies we read

## Summary
The paper addresses extractive multi-document summarization, where sentences must be chosen to be informative without repeating each other. A previous exact approach by McDonald (2007) scored sentences for relevance and penalized every pair of chosen sentences for overlap. This needs a quadratic number of variables, so it becomes impractical beyond roughly 100 input sentences. Gillick and Favre instead score a summary by the sub-sentence "concepts" it covers. In their experiments, concepts are stemmed word bigrams weighted by how many input documents contain them, and each concept earns credit only once. This choice handles redundancy for the summary as a whole rather than pair by pair. They cast the problem as an Integer Linear Program (a maximum-coverage-style model) and solve it with an off-the-shelf solver. On TAC 2008 data, the concept model clearly beats both the sentence-level ILP and a lead baseline, and it matches the top TAC systems on ROUGE, Pyramid and content responsiveness. They also extend the ILP to compress and select sentences jointly. This raised ROUGE-2 but hurt grammaticality and Pyramid.

## Key points
- **Data and task:** TAC 2008 multi-document summarization, standard task only. There are 48 topics, each with 10 newswire documents, and the target is a 100-word summary. Topics average 235 input sentences, ranging from 47 to 652.
- **Results (ROUGE-2 / Pyramid):**
  - lead baseline: 0.058 / 0.186
  - McDonald's sentence-level ILP: 0.072 / 0.295
  - concept-based ILP: 0.110 / 0.345
  - All differences between systems are significant.
- **Concept weighting:** Concepts are word bigrams weighted by document frequency. Bigrams worked better than unigrams or trigrams, and TFIDF-style normalization lowered ROUGE.
- **Why document frequency works:** On DUC data, a bigram's document frequency correlates strongly with its chance of appearing in human summaries (ρ = 0.95 for DUC 2007, 0.97 for DUC 2006).
- **Pipeline:**
  - Sentences are split with Punkt.
  - Sentences under 5 words are dropped.
  - Bigrams made only of stopwords, or found in fewer than three documents, are removed.
  - The ILP is solved with GLPK.
  - Chosen sentences are ordered by document date, then by position.
  - The parse-tree-based compression variant produced ungrammatical sentences in about 60% of its summaries.

## Interesting ideas
- **Implicit redundancy control:** Instead of penalizing overlap between pairs of items, reward each unique unit of content once. This captures redundancy that only appears when three or more items are combined. It also avoids variables for every pair, so it suits any selection task where overlap is the concern, such as dataset deduplication or choosing examples for a corpus.
- **Linking constraints between two layers:** Two small inequalities tie sentence variables to concept variables. Choosing a sentence switches on its concepts, and a concept counts only if some chosen sentence contains it. This pattern carries over to many ILP problems where items are scored through their parts.
- **Checking a cheap weighting signal against gold data:** The authors justify document-frequency weights by showing a strong correlation with gold-summary content before relying on them. Testing whether a cheap heuristic tracks the target in this way is a useful habit before investing in learned weights.
- **Joint compression and selection in one program:** Compression options are encoded as tree nodes that can be extracted, removed or substituted, inside the same optimization. This lets shortening and choosing interact, but the paper warns that the candidate generator must keep outputs grammatical.
- **Evaluating with both automatic and human metrics:** In the compression experiment, ROUGE rose while Pyramid and linguistic quality fell. This shows that n-gram recall alone can reward broken output, so pairing it with human-based measures is worth doing in other generation evaluations.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/)

## Cited by

Cited by

96 papers of our library cite it (of the 140884 whose bibliographies we read); 7 of them have a page here, 89 not yet.

- [Fast Abstractive Summarization with Reinforce-Selected Sentence Rewriting](https://md.research.elamur.ai/free/en/papers/chen-2018-fast-abstractive-summarization-reinforce-selected/)
- [Learning-Based Single-Document Summarization with Compression and Anaphoricity Constraints](https://md.research.elamur.ai/free/en/papers/durrett-2016-learning-based-single-document-summarization/)
- [Toward Abstractive Summarization Using Semantic Representations](https://md.research.elamur.ai/free/en/papers/liu-2015-abstractive-summarization-semantic-representations/)
- [Automatically Assessing Machine Summary Content Without a Gold Standard](https://md.research.elamur.ai/free/en/papers/louis-2013-automatically-assessing-machine-summary-content/)
- [Graph-based Neural Multi-Document Summarization](https://md.research.elamur.ai/free/en/papers/yasunaga-2017-graph-based-neural-multi-document/)
- [Extractive Summarization as Text Matching](https://md.research.elamur.ai/free/en/papers/zhong-2020-extractive-summarization-as-text-matching/)
- [Neural Document Summarization by Jointly Learning to Score and Select Sentences](https://md.research.elamur.ai/free/en/papers/zhou-2018-neural-document-summarization-jointly-learning/)

## Cite

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{gillick2009scalable,
  title = {{A Scalable Global Model for Summarization}},
  author = {Gillick, Dan and Favre, Benoit},
  booktitle = {Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing},
  year = {2009},
  doi = {10.3115/1611638.1611640},
  url = {https://doi.org/10.3115/1611638.1611640}
}
```

- [← previous A Probabilistic Model for Associative Anaphora Resolution](https://md.research.elamur.ai/free/en/papers/sasano-2009-probabilistic-model-associative-anaphora-resolution/)
- [next → A Study on Similarity and Relatedness Using Distributional and WordNet-based Approaches](https://md.research.elamur.ai/free/en/papers/agirre-2009-study-similarity-relatedness-distributional-wordnet/)
- [↑ back to papers of 2009](https://md.research.elamur.ai/free/en/papers/2009/)

## References

28 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. James Clarke and Mirella Lapata. 2008. Global inference for sentence compression: An integer linear programming approach. Journal of Artificial Intelligence Research, 31:273–381. [find](https://scholar.google.com/scholar?q=James+Clarke+and+Mirella+Lapata%2E+2008%2E+Global+inference+for+sentence+compression%3A+An+integer+linear+programming+approach%2E+Journal+of+Artificial+Intelligence+Research%2C+31%3A273%E2%80%93381%2E)
2. John M. Conroy, Judith D. Schlesinger, and Dianne P. O’Leary. 2006. Topic-focused multi-document summarization using an approximate oracle score. In Proceedings of COLING/ACL. [find](https://scholar.google.com/scholar?q=John+M%2E+Conroy%2C+Judith+D%2E+Schlesinger%2C+and+Dianne+P%2E+O%E2%80%99Leary%2E+2006%2E+Topic%2Dfocused+multi%2Ddocument+summarization+using+an+approximate+oracle+score%2E+In+Proceedings+of+COLING%2FACL%2E)
3. Hoa Trang Dang and Karolina Owczarzak. 2008. Overview of the TAC 2008 Update Summarization Task. In Proceedings of Text Analysis Conference. [find](https://scholar.google.com/scholar?q=Hoa+Trang+Dang+and+Karolina+Owczarzak%2E+2008%2E+Overview+of+the+TAC+2008+Update+Summarization+Task%2E+In+Proceedings+of+Text+Analysis+Conference%2E)
4. E. Filatova and V. Hatzivassiloglou. 2004. Event-based extractive summarization. In Proceedings of ACL Workshop on Summarization, volume 111. [find](https://scholar.google.com/scholar?q=E%2E+Filatova+and+V%2E+Hatzivassiloglou%2E+2004%2E+Event%2Dbased+extractive+summarization%2E+In+Proceedings+of+ACL+Workshop+on+Summarization%2C+volume+111%2E)
5. G. Gallo, PL Hammer, and B. Simeone. 1980. Quadratic knapsack problems. Mathematical Programming Study, 12:132–149. [find](https://scholar.google.com/scholar?q=G%2E+Gallo%2C+PL+Hammer%2C+and+B%2E+Simeone%2E+1980%2E+Quadratic+knapsack+problems%2E+Mathematical+Programming+Study%2C+12%3A132%E2%80%93149%2E)
6. D. Gillick, B. Favre, and D. Hakkani-Tur. 2008. The ICSI Summarization System at TAC 2008. In Proceedings of the Text Understanding Conference. [find](https://scholar.google.com/scholar?q=D%2E+Gillick%2C+B%2E+Favre%2C+and+D%2E+Hakkani%2DTur%2E+2008%2E+The+ICSI+Summarization+System+at+TAC+2008%2E+In+Proceedings+of+the+Text+Understanding+Conference%2E)
7. Jade Goldstein, Vibhu Mittal, Jaime Carbonell, and Mark Kantrowitz. 2000. Multi-document summarization by sentence extraction. Proceedings of the ANLP/NAACL Workshop on Automatic Summarization, pages 40–48. [find](https://scholar.google.com/scholar?q=Jade+Goldstein%2C+Vibhu+Mittal%2C+Jaime+Carbonell%2C+and+Mark+Kantrowitz%2E+2000%2E+Multi%2Ddocument+summarization+by+sentence+extraction%2E+Proceedings+of+the+ANLP%2FNAACL+Workshop+on+Automatic+Summarization%2C+pages+)
8. Martin Hassel and Jonas Sjöbergh. 2006. Towards holistic summarization: Selecting summaries, not sentences. In Proceedings of Language Resources and Evaluation. [find](https://scholar.google.com/scholar?q=Martin+Hassel+and+Jonas+Sjo%CC%88bergh%2E+2006%2E+Towards+holistic+summarization%3A+Selecting+summaries%2C+not+sentences%2E+In+Proceedings+of+Language+Resources+and+Evaluation%2E)
9. D.S. Hochbaum. 1996. Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. PWS Publishing Co. Boston, MA, USA, pages 94–143. [find](https://scholar.google.com/scholar?q=D%2ES%2E+Hochbaum%2E+1996%2E+Approximating+covering+and+packing+problems%3A+set+cover%2C+vertex+cover%2C+independent+set%2C+and+related+problems%2E+PWS+Publishing+Co%2E+Boston%2C+MA%2C+USA%2C+pages+94%E2%80%93143%2E)
10. E. Hovy, C.Y. Lin, and L. Zhou. 2005. A BE-based multi-document summarizer with sentence compression. In Proceedings of Multilingual Summarization Evaluation. [find](https://scholar.google.com/scholar?q=E%2E+Hovy%2C+C%2EY%2E+Lin%2C+and+L%2E+Zhou%2E+2005%2E+A+BE%2Dbased+multi%2Ddocument+summarizer+with+sentence+compression%2E+In+Proceedings+of+Multilingual+Summarization+Evaluation%2E)
11. Fatma Jaoua Kallel, Maher Jaoua, Lamia Belguith Hadrich, and Abdelmajid Ben Hamadou. 2004. Summarization at LARIS Laboratory. In Proceedings of the Document Understanding Conference. [find](https://scholar.google.com/scholar?q=Fatma+Jaoua+Kallel%2C+Maher+Jaoua%2C+Lamia+Belguith+Hadrich%2C+and+Abdelmajid+Ben+Hamadou%2E+2004%2E+Summarization+at+LARIS+Laboratory%2E+In+Proceedings+of+the+Document+Understanding+Conference%2E)
12. Richard Manning Karp. 1972. Reducibility among combinatorial problems. Complexity of Computer Computations, 43:85–103. [find](https://scholar.google.com/scholar?q=Richard+Manning+Karp%2E+1972%2E+Reducibility+among+combinatorial+problems%2E+Complexity+of+Computer+Computations%2C+43%3A85%E2%80%93103%2E)
13. Tibor Kiss and Jan Strunk. 2006. Unsupervised multilingual sentence boundary detection. Computational Linguistics, 32. [find](https://scholar.google.com/scholar?q=Tibor+Kiss+and+Jan+Strunk%2E+2006%2E+Unsupervised+multilingual+sentence+boundary+detection%2E+Computational+Linguistics%2C+32%2E) [our card](https://md.research.elamur.ai/free/en/papers/cl-2006-kiss-unsupervised-multilingual-sentence-boundary-detection/)
14. K. Knight and D. Marcu. 2000. Statistics-Based Summarization-Step One: Sentence Compression. In Proceedings of the National Conference on Artificial Intelligence, pages 703–710. [find](https://scholar.google.com/scholar?q=K%2E+Knight+and+D%2E+Marcu%2E+2000%2E+Statistics%2DBased+Summarization%2DStep+One%3A+Sentence+Compression%2E+In+Proceedings+of+the+National+Conference+on+Artificial+Intelligence%2C+pages+703%E2%80%93710%2E)
15. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999. [find](https://scholar.google.com/scholar?q=Menlo+Park%2C+CA%3B+Cambridge%2C+MA%3B+London%3B+AAAI+Press%3B+MIT+Press%3B+1999%2E)
16. Chin-Yew Lin. 2004. ROUGE: A Package for Automatic Evaluation of Summaries. In Proceedings of the Workshop on Text Summarization Branches Out (WAS 2004), pages 25–26. [find](https://scholar.google.com/scholar?q=Chin%2DYew+Lin%2E+2004%2E+ROUGE%3A+A+Package+for+Automatic+Evaluation+of+Summaries%2E+In+Proceedings+of+the+Workshop+on+Text+Summarization+Branches+Out+%28WAS+2004%29%2C+pages+25%E2%80%9326%2E)
17. D. Liu, Y. Wang, C. Liu, and Z. Wang. 2006. Multiple Documents Summarization Based on Genetic Algorithm. Lecture Notes in Computer Science, 4223:355. [find](https://scholar.google.com/scholar?q=D%2E+Liu%2C+Y%2E+Wang%2C+C%2E+Liu%2C+and+Z%2E+Wang%2E+2006%2E+Multiple+Documents+Summarization+Based+on+Genetic+Algorithm%2E+Lecture+Notes+in+Computer+Science%2C+4223%3A355%2E)
18. N. Madnani, D. Zajic, B. Dorr, N.F. Ayan, and J. Lin. 2007. Multiple Alternative Sentence Compressions for Automatic Text Summarization. In Proceedings of the Document Understanding Conference at NLT/NAACL. [find](https://scholar.google.com/scholar?q=N%2E+Madnani%2C+D%2E+Zajic%2C+B%2E+Dorr%2C+N%2EF%2E+Ayan%2C+and+J%2E+Lin%2E+2007%2E+Multiple+Alternative+Sentence+Compressions+for+Automatic+Text+Summarization%2E+In+Proceedings+of+the+Document+Understanding+Conference+at+NLT%2F)
19. R. McDonald. 2006. Discriminative sentence compression with soft syntactic constraints. In Proceedings of the 11th EACL, pages 297–304. [find](https://scholar.google.com/scholar?q=R%2E+McDonald%2E+2006%2E+Discriminative+sentence+compression+with+soft+syntactic+constraints%2E+In+Proceedings+of+the+11th+EACL%2C+pages+297%E2%80%93304%2E)
20. R. McDonald. 2007. A Study of Global Inference Algorithms in Multi-document Summarization. Lecture Notes in Computer Science, 4425:557. [find](https://scholar.google.com/scholar?q=R%2E+McDonald%2E+2007%2E+A+Study+of+Global+Inference+Algorithms+in+Multi%2Ddocument+Summarization%2E+Lecture+Notes+in+Computer+Science%2C+4425%3A557%2E)
21. Ani Nenkova and Rebecca Passonneau. 2004. Evaluating content selection in summarization: The pyramid method. In Proceedings of HLT-NAACL. [find](https://scholar.google.com/scholar?q=Ani+Nenkova+and+Rebecca+Passonneau%2E+2004%2E+Evaluating+content+selection+in+summarization%3A+The+pyramid+method%2E+In+Proceedings+of+HLT%2DNAACL%2E)
22. A. Nenkova and L. Vanderwende. 2005. The impact of frequency on summarization. Technical Report MSR-TR-2005-101, Microsoft Research, Redmond, Washington. [find](https://scholar.google.com/scholar?q=A%2E+Nenkova+and+L%2E+Vanderwende%2E+2005%2E+The+impact+of+frequency+on+summarization%2E+Technical+Report+MSR%2DTR%2D2005%2D101%2C+Microsoft+Research%2C+Redmond%2C+Washington%2E)
23. A. Nenkova. 2008. Entity-driven rewrite for multidocument summarization. Proceedings of IJCNLP. [find](https://scholar.google.com/scholar?q=A%2E+Nenkova%2E+2008%2E+Entity%2Ddriven+rewrite+for+multidocument+summarization%2E+Proceedings+of+IJCNLP%2E)
24. Slav Petrov and Dan Klein. 2007. Learning and inference for hierarchically split PCFGs. In AAAI 2007 (Nectar Track). [find](https://scholar.google.com/scholar?q=Slav+Petrov+and+Dan+Klein%2E+2007%2E+Learning+and+inference+for+hierarchically+split+PCFGs%2E+In+AAAI+2007+%28Nectar+Track%29%2E)
25. D. Pisinger, A.B. Rasmussen, and R. Sandvik. 2005. Solution of large-sized quadratic knapsack problems through aggressive reduction. INFORMS Journal on Computing. [find](https://scholar.google.com/scholar?q=D%2E+Pisinger%2C+A%2EB%2E+Rasmussen%2C+and+R%2E+Sandvik%2E+2005%2E+Solution+of+large%2Dsized+quadratic+knapsack+problems+through+aggressive+reduction%2E+INFORMS+Journal+on+Computing%2E)
26. K. Toutanova, C. Brockett, M. Gamon, J. Jagarlamudi, H. Suzuki, and L. Vanderwende. 2007. The Pythy Summarization System: Microsoft Research at DUC 2007. In Proceedings of the Document Understanding Conference. [find](https://scholar.google.com/scholar?q=K%2E+Toutanova%2C+C%2E+Brockett%2C+M%2E+Gamon%2C+J%2E+Jagarlamudi%2C+H%2E+Suzuki%2C+and+L%2E+Vanderwende%2E+2007%2E+The+Pythy+Summarization+System%3A+Microsoft+Research+at+DUC+2007%2E+In+Proceedings+of+the+Document+Understanding+C)
27. J. Turner and E. Charniak. 2005. Supervised and Unsupervised Learning for Sentence Compression. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=J%2E+Turner+and+E%2E+Charniak%2E+2005%2E+Supervised+and+Unsupervised+Learning+for+Sentence+Compression%2E+In+Proceedings+of+ACL%2E)
28. W. Yih, J. Goodman, L. Vanderwende, and H. Suzuki. 2007. Multi-document summarization by maximizing informative content-words. In International Joint Conference on Artificial Intelligence. [find](https://scholar.google.com/scholar?q=W%2E+Yih%2C+J%2E+Goodman%2C+L%2E+Vanderwende%2C+and+H%2E+Suzuki%2E+2007%2E+Multi%2Ddocument+summarization+by+maximizing+informative+content%2Dwords%2E+In+International+Joint+Conference+on+Artificial+Intelligence%2E)