Disk-Resident Coverage Selection for Cross-Document Summaries

When many sources report on the same events, the facts that matter most are the ones repeated everywhere, and those are also the facts that pile up as duplicates in any summary. One classical way to choose a small, non-redundant set of sentences is a coverage objective: reward a summary for having, for every sentence in the input, some chosen sentence that is similar to it. A greedy algorithm that keeps adding the sentence with the largest gain is provably within a constant factor of the best possible summary. Existing implementations assume the whole sentence-similarity graph sits in main memory. At archive scale, meaning months of news from many outlets or a large retrieved pool for a language model, people make it fit by truncating inputs, keeping only each sentence's top few neighbors, or splitting the corpus into shards. Each of these discards some of the cross-document repetition that indicates both what is central and what is redundant.

This note proposes running the selection without fitting the graph in memory. The program keeps one number per sentence in RAM and reads the similarity graph from disk in sequential sweeps. Each sweep makes exact greedy decisions, and the number of sweeps does not depend on how many sentences are chosen. Sentences are weighted by a random-walk centrality score computed in the same sweeping regime. This targets "cover what is central," and the coverage objective itself suppresses repeats. The research question is empirical as much as algorithmic. Does preserving the full, dense repetition structure actually beat the cheap shortcuts that make in-memory greedy feasible? If it does not, the note commits to saying so.

Core Claim

Let $V$ be the $N$ sentences of a corpus, $w_{ij}\ge 0$ the similarity between sentences $i$ and $j$ (zero below a threshold), and $\pi_i \ge 0$ a centrality score for sentence $i$. We maximize a centrality-weighted facility-location objective, which counts how well each sentence is "represented" by its best chosen neighbor:

$$f(S) = \sum_{i \in V} \pi_i \max_{j \in S} w_{ij}.$$

For any nonnegative weights this is monotone and submodular. Monotone means adding sentences never hurts. Submodular means diminishing returns: a sentence adds less once similar sentences are already chosen. The standard greedy guarantee of $(1-1/e)$ therefore applies, as in the analysis of Maximizing the spread of influence through a social network.

The structural fact we exploit concerns the vector $c_i = \max_{j\in S} w_{ij}$, the current coverage of sentence $i$. If $c$ is held in RAM, the gain of a candidate $e$ depends only on $e$'s own row of the graph:

$$\Delta(e \mid S) = \sum_{i:\, w_{ie}>0} \pi_i \,\max(0,\; w_{ie} - c_i).$$

Store the graph on disk row by row and stream it. When the sweep reaches row $e$, the gain is computed exactly from fresh state. If $e$ clears the current threshold, it is accepted, and $c$ is updated from the row already in hand. This turns the standard decreasing-threshold greedy into a semi-external algorithm, in the sense of the vertex-state-in-RAM, edges-on-disk model of Graphyti and GraphMP.

For a cardinality budget $k$, thresholds start at the largest singleton gain $d$ and shrink by a factor $(1-\epsilon)$ per sweep down to $\epsilon d/k$. This uses

$$O\!\left(\tfrac{1}{\epsilon}\log\tfrac{k}{\epsilon}\right)$$

sweeps and gives $(1-1/e-\epsilon)$. The pass count follows from geometric threshold decay. The guarantee follows from the usual argument that every accepted element has gain within $(1-\epsilon)$ of the best available. Memory is $O(N)$ regardless of edge count.

The centrality scores $\pi$ come from LexRank-style power iteration, meaning repeated averaging of scores over the similarity graph. That is a few more sequential sweeps over the same file. For byte budgets such as DUC's 665 bytes, we replace gain thresholds with gain-per-cost thresholds plus a best-single-sentence safeguard. We will prove which constant factor this semi-external variant preserves relative to the in-memory budgeted greedy of Lin & Bilmes 2010. We do not assume it inherits their $(1-1/\sqrt{e})$ bound.

What is new relative to the closest work is the combination, together with the question it allows us to ask. Lin & Bilmes 2010 and A Class of Submodular Functions for Document Summarization supply the coverage objectives and guarantees but hold all of $w$ in RAM. ACGraph and MariusGNN run disk-resident graph computations but only iterative linear algebra and gradient training, with no discrete selection. LexPageRank and Improved Affinity Graph Based Multi-Document Summarization compute centrality but remove redundancy with heuristic penalties that carry no guarantee.

Research Program

The first deliverable is the algorithm and its analysis. This covers the cardinality case above and the budgeted case. It also covers a single-sweep variant, analogous to one-pass streaming, which serves as a point on the passes-versus-quality curve. The analysis states exactly which guarantees survive when $\pi$ is itself only approximately converged after a fixed number of power-iteration sweeps. Because $f$ is linear in $\pi$, an $\ell_1$ error in $\pi$ shifts $f$ by at most that error times $\max w$. The guarantee therefore degrades additively, and we will measure how much.

The second deliverable is the systems piece. Graph construction is a one-time, tiled pass: embedding tiles are streamed, similarities above a threshold $\tau$ are kept, and rows are written to disk in compressed form. This borrows the 2D tiling idea of Sun et al. and Yu et al.. Selection then needs only sequential reads, so asynchronous prefetching of the kind ACGraph uses (it reports 60% less I/O volume and up to 15x over Blaze on ClueWeb12) applies directly.

One structural concern from the file shapes the design. Cross-document text graphs are not power-law web graphs. Consensus facts form dense cliques, which is the "centrality-redundancy trap." Degree-based partitioning such as Hybrid Edge Partitioner would send exactly those hubs to its lossy streaming path. Our design never partitions vertex state, so cliques stay intact.

The third deliverable is the empirical question that justifies the effort. We measure whether the repetition structure lost by memory-saving shortcuts measurably harms summaries. The specific mechanism we suspect is that keeping only top-$k$ neighbors caps every sentence's degree. In a clique of 300 near-identical reports, that cap erases the difference between a fact repeated 300 times and one repeated 30 times, which is exactly the signal centrality needs. Threshold graphs keep this difference, at the cost of edge counts that grow with clique size.

Baselines

The naive reference points are Lead and plain centrality ranking. Lead takes the first sentences of each article, uses no graph, and needs constant memory. LexPageRank reports that centrality beats Lead on DUC 2004, but no reported result for Lead on DUC 2004 was found on Lacuna. We will run Lead ourselves under the same byte budget. Plain LexRank ranking without redundancy control is reported at ROUGE-1 "around 0.38" on DUC 2004. A plain centrality ranking that is not beaten means the coverage objective adds nothing.

The strongest in-memory competitors are the following. Lin & Bilmes 2011 report saturated-coverage plus diversity at ROUGE-1 38.65% on DUC 2004. Improved Affinity Graph Based Multi-Document Summarization report 0.41102 on DUC 2004, the highest DUC 2004 figure in the file, obtained with a heuristic diversity penalty and no guarantee. We will reimplement both on identical sentence segmentation, embeddings, ROUGE settings, and DUC 2003 tuning with an equal hyperparameter grid, because published ROUGE configurations differ.

On small benchmarks our method is not expected to beat Wan & Yang. There, success means two things. First, the output exactly reproduces in-memory greedy on the same objective. Second, ROUGE stays within noise of the in-memory submodular systems while using a fixed small RAM cap. At archive scale, beating a baseline means a higher objective value on the full threshold graph and higher pooled reference recall at equal RAM and wall-clock budgets.

For abstractive context, Hi-MAP reports ROUGE-1 43.47 on Multi-News (Multi-News). A pointer-generator reports ROUGE-L 30.63 on Multi-XScience (Multi-XScience). These are not extractive competitors. We report them so readers can see the extractive ceiling, and we do not claim to beat them.

The memory-matched competitors are the ones that matter most for the proposal's claim. They are lazy greedy on a top-$k$ neighbor graph sized to the same RAM budget, shard-then-merge greedy, and one-pass streaming in the style of Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams. Each gets the same budget, the same embeddings, and its best $k$, shard count, or threshold chosen on held-out clusters.

Two ablations isolate the ingredients. The first sets all $\pi_i=1$ to isolate centrality weighting. The second runs our algorithm on top-$k$ instead of threshold graphs to isolate the graph-preservation claim from the algorithm.

Why not just…?

Why not just keep each sentence's top-$k$ neighbors and run ordinary lazy greedy in memory? This is the most serious threat. A top-$k$ graph over a few million sentences fits on a workstation, and lazy greedy is fast. The answer depends on whether degree capping actually distorts which consensus facts get covered. That is an empirical question, and the archive-scale experiment answers it directly. We compare objective value measured on the full threshold graph and pooled reference recall, sweeping $k$ until memory matches. If top-$k$ with modest $k$ matches the threshold graph, we will report that the disk-resident machinery is unnecessary for these corpora. The surviving contribution would then be the centrality-weighted objective and its guarantee.

Why not just split the corpus into shards, summarize each, and merge? Sharding is how Hybrid Edge Partitioner-style systems cope with memory. However, cross-document redundancy lives across shards. Two outlets' reports of the same event land in different shards, both get selected, and the merge step sees only the survivors. We will measure the redundancy of selected sets, defined as the fraction of chosen pairs above $\tau$, and the objective gap as shard count grows. That gap should widen with the number of outlets per event. If it does not, sharding is good enough.

Why not just make one streaming pass? With the row-wise file format, a single-threshold one-pass rule is easy and fast. One-pass methods trade approximation quality for passes, which is the motivation behind Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams. Our multi-pass schedule makes the trade explicit, and we will plot quality against number of sweeps. If two or three sweeps capture nearly all the gain, that becomes the recommended setting, which is a useful finding rather than a defeat.

Why not just give everything to a long-context language model? Multi-News reports that neural summarizers truncate inputs under GPU memory limits. Archive-scale inputs exceed any context window by orders of magnitude. Sakshi et al. use graph ranking precisely to compress legal text into a fixed context. We therefore treat our selector as the front end that decides what a language model sees. As an extension, we compare a model fed our selection against one fed truncated or top-$k$-selected input at equal token budget.

Proposed Experiments

The first check is exactness and guarantee fidelity on DUC 2004 Task 2 with a 665-byte budget, using DUC 2003 for tuning. For identical $\pi$, $w$, and objective, the semi-external selector under a RAM cap far below the graph size must return the same summary as in-memory greedy, or one whose objective is within the proven $\epsilon$. We also report the ratio to exact optimum on small clusters, where Lin & Bilmes 2010 found greedy above 90% of optimal. ROUGE-1 is reported against the 38.65% and 0.41102 figures above, with the centrality and graph-type ablations. We repeat this on DUC 2002, and on Multi-XScience, where positional shortcuts fail, to show the weighting is not a news-layout artifact.

The decisive experiment is at archive scale. We pool all Multi-News articles into one ground set of several million sentences. The gold "archive summary" is the concatenation of all reference summaries, and the budget is their total length. We then sweep the RAM cap and compare four approaches at equal RAM and wall-clock: threshold-graph semi-external selection, top-$k$ lazy greedy, shard-and-merge, and one-pass streaming. The metrics are full-graph objective value, ROUGE recall against the pooled gold, selected-set redundancy, sweeps, I/O volume, and wall-clock time.

A controlled stress test complements this. We vary the number of sources per story using Multi-News's 2–10 range and plot each method's gap as a function of clique size. Degree capping and sharding should fail increasingly as repetition grows. If the gap is flat, the central claim is wrong, and the note will say that the in-memory shortcuts suffice.