Clustering the news with cheap models: a measured look at embeddings, online centroids and entity extraction

A news aggregator has a deceptively simple job: notice when forty outlets are writing about the same event, and show it once. Underneath, that job is an online clustering problem on a stream of short, noisy, multilingual texts, with a hard budget on cost per item.

The usual instinct is to throw a large language model at it. That does not scale. A large model reading every incoming article is the most expensive possible design, and most of what it reads is noise: most articles are about something nobody else is covering.

This post describes the design we arrived at for NewSumm and, more usefully, measures it. Every figure below comes from our own pipeline's output for a two-day window (3–4 November 2026): 51,842 articles, which became 34,929 stories. Where we analyse extracted people and places, the window runs to 9 November.

The short version: almost all of the work is done by geometry, not by language models. Embeddings cost a few dollars per million articles. Language models only see the narrow end of a long funnel, so their cost scales with the number of stories, not the number of articles.

Note: This is a description of the method and its measured behaviour, not a recipe. We deliberately leave out our thresholds, model choices, prompts and tuning, which are specific to our data and change as it does.

1. The problem, stated precisely

Let articles arrive as a stream x₁, x₂, x₃, … Each must be assigned, on arrival, to an existing story or to a new one. The constraints:

• Online. We cannot wait for the day to finish and run a batch algorithm. A story should appear minutes after its first articles.
• Unknown k. The number of stories is not fixed. On a typical day thousands are born and most never grow.
• Short, uneven input. We only have what feeds provide: a headline and usually a sentence or two. In our sample the median input is 225 characters, the mean 471.
• Duplicates that aren't independent. The same agency copy is reprinted by many outlets. Ten articles can be one report.
• Cost per item must be tiny. Whatever touches every article must cost a fraction of a cent.

This is the topic detection and tracking (TDT) problem studied since the late 1990s [1], with modern tools.

2. Representation: one cheap vector per article

Each article is mapped once to a dense embedding vector x ∈ ℝᵈ from a small, inexpensive embedding model, using only its headline and description. Similarity is cosine similarity:

cos(x, y) = (x · y) / (‖x‖ ‖y‖) 

With unit-normalised vectors this is just the dot product, and cosine distance is 1 − cos(x, y).

The economics are the first surprise. At a mean of roughly 120 tokens per article and current list prices for small embedding models (a few cents per million tokens), embedding a million articles costs in the order of a few dollars. Embedding is the only model call made for every article. Everything downstream is arithmetic and an index lookup.

Does the geometry separate stories?

Before trusting a single threshold, look at the distributions. For 2,500 randomly sampled articles from multi-article stories, we measured three quantities:

1. Unrelated pairs: the similarity between two randomly chosen articles from different stories.
2. Nearest other story: the similarity between the article and the closest story it does not belong to. These are the hard negatives: the decision the algorithm actually has to make.
3. Own story: the similarity between the article and the centroid of the story it ended up in.

Three things stand out.

Unrelated news is nowhere near a decision boundary. Random pairs sit around 0.1 and almost never pass 0.35. Any threshold sensible enough to group stories will never confuse a football result with a central bank decision.

The real difficulty is the nearest neighbour, not the average. The nearest other story sits at 0.73, uncomfortably close to the own-story distribution. These neighbours are mostly genuinely related: the same war on a different day, the same company in a different deal, the same league on a different match. A cosine threshold is a decision about granularity (what counts as "the same event") as much as about relevance.

The distributions overlap, so a single global threshold cannot be perfect. About 3.4% of nearest-other similarities are at or above the median own-story similarity. No threshold separates them cleanly. This is where the algorithm needs structure beyond the threshold: time, story maturity and a second pass (section 4).

Tip: Plot these three distributions on your own data before choosing a threshold. The random-pair curve tells you nothing; the nearest-other curve is the one your threshold has to beat.

3. Online clustering with running centroids

The core algorithm is a single-pass, threshold-based scheme (a "leader" or sequential clustering algorithm), refined for news:

for each new article x: candidates ← approximate nearest story centroids to x keep candidates that are still "live" (recent enough) if the best candidate passes the similarity rule: add x to it, update its centroid else: start a new story with centroid x 

Centroids as running means

A story k with nₖ members has centroid μₖ, the mean of its member embeddings. Recomputing that mean from scratch on every insertion costs O(nₖ·d), which makes building a story of n articles O(n²·d). The running-mean update is exact and costs O(d):

μₖ⁽ⁿ⁾ = μₖ⁽ⁿ⁻¹⁾ + (x − μₖ⁽ⁿ⁻¹⁾) / n 

When two stories A and B merge, the combined centroid is the size-weighted mean, which again equals the from-scratch recomputation:

μ_AB = (n_A μ_A + n_B μ_B) / (n_A + n_B) 

A useful property follows for unit-normalised embeddings. The squared norm of a centroid is the mean pairwise similarity of its members (self-pairs included):

‖μ‖² = (1/n²) Σᵢ Σⱼ xᵢ · xⱼ 

So the length of the centroid is a free measure of cohesion. A tight story has a centroid close to the unit sphere; a story that has drifted across loosely related events has a visibly shorter one. This is also why an article's similarity to its own centroid reads higher than its similarity to any single fellow member. The centroid averages away each article's idiosyncrasies.

Making the lookup sub-linear

Comparing each article to every live story is O(m·d) for m stories, and m reaches tens of thousands within a few days. Instead, centroids live in an approximate nearest-neighbour index, a hierarchical navigable small-world graph (HNSW) [2], which answers top-k queries in roughly logarithmic time.

One practical lesson cost us real downtime. Ask the index a pure nearest-neighbour question, then apply your business rules in application code. Mixing filters such as "updated in the last day" into the same query invites the database planner to abandon the index for a scan whenever its statistics shift. We saw per-article lookup time jump from milliseconds to seconds overnight. Pulling a generous candidate pool from the index and filtering it afterwards is both faster and predictable.

Time is a feature

A story is not just a point in embedding space. It has a lifespan. The rule that decides membership treats a story differently depending on when it was last updated and how established it is. An active story accepts close matches. A quiet but established story, whose centroid is averaged over many articles and therefore stable, can still accept a continuing development. And a story eventually stops growing, so that next month's coverage of a long-running subject starts a new story instead of joining an ever-widening blob.

How fast do stories actually fill up? For the 16,273 articles in stories of three or more:

Half of a story's articles arrive within 6.6 hours of the first (the 36% at hour zero is mostly the opening burst, including the founding article itself), and 90% within 48 hours. The curve has a fast head (the initial burst as outlets pick up the same news) and a long tail of follow-ups, analysis and regional angles. That tail is precisely the population that sits near the decision boundary in section 2: later articles drift semantically from the original report.

4. Second passes: merging and chaptering

A single online pass has a known weakness: order dependence. If the first two articles about an event arrive close together, before either is part of a story, they can found two separate stories that then grow in parallel. Their centroids converge as they fill up.

The cure is a periodic merge pass. Any recently changed story is compared with other live stories, centroid to centroid. Pairs above a merge rule are folded together using the weighted-mean formula above. Only recently changed stories need checking, because a pair can only become mergeable when one side changes. That keeps the pass proportional to recent activity, not to the size of the archive.

A related pass links chapters. When a story has aged out, continuing coverage starts a new story. A new story that is close enough to an aged-out one is linked to it as its continuation, so readers can follow a long-running subject without one story growing forever.

The merge pass does real work. Of the stories first seen in our two-day window, 529 were later folded into another story as duplicates.

5. The shape of the output: a heavy tail

What does the resulting set of stories look like?

• 86% of stories are a single article (30,181 of 34,929). They hold 58% of all articles.
• 13.6% of stories have two or more articles, and these hold 42% of the input.
• Fewer than 1% reach ten articles. The largest story in the window has 409.

The tail, from two articles upward, is close to a straight line on a log–log plot of the complementary cumulative distribution. A maximum-likelihood fit for a discrete power law [3] gives:

α̂ = 1 + n · [ Σᵢ ln( kᵢ / (k_min − ½) ) ]⁻¹ ≈ 2.42 (k_min = 2) 

We are not claiming the distribution is a power law: the tail bends below the fit past a hundred articles, and a two-day window truncates the largest stories. But the qualitative point is robust and matters for system design: attention in the news is extremely concentrated. A small number of events absorb most of the coverage, and most items are about something nobody else is covering.

That shape is what makes the economics work.

6. Counting independent sources: syndication

"Covered by 12 outlets" is the most natural signal of importance, and it is easy to get wrong. A wire story reprinted verbatim by many publishers is one report, not many. Several feeds of the same publisher are one outlet.

We count independent sources as the number of distinct publishers, capped by the number of distinct normalised headlines. Normalisation folds case, punctuation and the HTML-entity mess that real feeds produce (the same apostrophe arrives as ', ' and even double-encoded '):

sources(C) = min( |publishers(C)|, |normalised headlines(C)| ) 

Then a story with ten publishers and three distinct headlines counts as three independent reports.

The effect is large. In our window, 3,252 stories had articles from at least two publishers. For 652 of them (20%), the independent count was lower than the publisher count. 442 (13.6%) collapsed to a single independent report: one piece of agency copy, reprinted. Without this correction, a reader sees a "multi-source" badge that means nothing, and any downstream signal built on source counts, such as ranking, alerting or bias balance, inherits the error.

7. Where the language model comes in

Only now does a language model enter, and only for stories that more than one article has joined. The funnel shows why that matters:

For the two-day window, the whole input is 51,842 articles. A per-article language-model design would make 51,842 calls. The stories that merit reading number 4,748 (9.2% of the article count) and 2,810 after removing syndicated copies. Because a story is read as one unit, with its articles together, model cost scales with the number of multi-article stories. Thanks to the heavy tail, that is an order of magnitude smaller than the input. (A growing story is read again as it changes, so the exact ratio depends on how often you refresh; the order of magnitude does not.)

The second lever is the size of the model. The tasks we ask of it are narrow and well-specified: summarise what several articles agree on, describe where their coverage differs, and fill a fixed schema. A small, inexpensive model with structured output (a strict JSON schema the response must match) handles them well. Structure turns a generative model into a classifier and extractor whose output can be validated like any other input.

Warning: Strict schemas fail closed, and that is a feature. A schema the provider rejects fails every call, loudly. Test the real schema against the real API, because mocked model calls in unit tests will never catch it.

8. Extracting people and places

The same pass that summarises a story also extracts who it is about and where it happened, at almost no marginal cost: the model is already reading the articles. Two design choices did most of the work.

Ask for roles, not just names. Each person comes with a canonical full name, a short role (which later helps tell namesakes apart), and whether they are the subject of the story or merely mentioned. Each place comes with its precision (city, region or country), its country code, and whether it is where the event happened or a place merely reacting. "Country X condemns strike in City Y" has one event place and one reacting place. Collapsing them is the most common error in naive extraction.

Constrain the vocabulary. Places must be real cities, regions or countries. Venues, streets and districts resolve to their city. Continents and multi-country regions are excluded. A country acting as a state ("Russia said") is a place, not an organisation. Each rule removes a class of ambiguity that would otherwise surface later as a duplicate or a mis-pinned location.

Entity resolution

Extraction produces strings. Turning strings into things is the harder half. The pipeline has three stages:

1. Candidate generation. Places are matched against a geographic gazetteer. People are matched against an open knowledge graph (Wikidata [4]) by label and aliases, including spelling variants.
2. Type-constrained filtering. A candidate is judged by the classes it belongs to in the knowledge graph, following the "instance of / subclass of" hierarchy, not by whether its description happens to contain the right words. A person must be a human, never a fictional character, band or TV episode that shares the name. This one change removed a whole family of false matches that description-based heuristics let through.
3. Abstention. When candidates remain ambiguous, the entity stays unresolved rather than being guessed. A wrong link is worse than no link: it merges two people's coverage silently.

What comes out: another heavy tail

Across 3,508 stories first seen 3–9 November, extraction produced 6,276 distinct people and places with 10,291 story links, about 2.9 per story:

• 81% of entities appear in exactly one story. News constantly introduces new names: witnesses, local officials, athletes in a single match.
• The top 1% of entities account for 16.6% of all mentions. A handful of heads of state, capitals and conflict zones recur constantly.
• The rank–frequency curve is close to Zipf-like, f(r) ∝ r⁻ˢ, with s ≈ 0.67 over the top thousand ranks. That is flatter than the classic s ≈ 1 of word frequencies [5]. Over a week, news spreads its attention across more distinct people and places than language spreads across words.
• Places concentrate more than people: on average a place recurs in 2.0 stories, a person in 1.45.

The engineering consequences are practical. Resolution effort should be spent where the mass is: the head of the distribution, which recurs, is worth resolving carefully, ideally with a human-reviewed override path. The singleton tail cannot be curated by hand and must be handled by conservative automatic rules that abstain rather than guess.

9. Measuring quality honestly

None of this is worth much without measurement, and clustering is notoriously hard to evaluate because there is rarely a gold standard. What has worked for us:

• Replay, don't guess. Changes to the similarity rules are evaluated by replaying a stored window of real articles through old and new rules and comparing the outputs: stories formed, merges made, and a hand-checked sample of the pairs that differ. Our first tuning round was validated this way before it shipped.
• Event logs per story. Every creation, article addition and merge is recorded. When a story looks wrong, the log shows exactly which decision produced it, and when.
• Precision and recall for extraction, from hand review. Reviewers mark each extracted entity as correct or wrong, and add the entities that were missed:

precision = correct / (correct + wrong) recall = correct / (correct + missed) F₁ = 2 · precision · recall / (precision + recall) 

These are tracked by extraction date, so the effect of any rule change shows up from the day it went in.

10. What we would tell someone starting today

1. Let geometry do the bulk of the work. One embedding per article and an approximate nearest-neighbour index handle the full stream for almost nothing. Reserve language models for the aggregated, narrow end.
2. Study the nearest-neighbour distribution, not the average. The hard decisions are between related events, and a single threshold will not separate them. Add time, maturity and a merge pass.
3. Use running centroids. They are exact, O(d) per update, and their length is a free cohesion signal.
4. Correct for syndication before you count sources. In our data, one in five multi-publisher stories overstated its independent coverage.
5. Extract with roles and constraints, resolve with types, and abstain when unsure. The output follows a heavy tail; spend human attention on the head.
6. Keep the index query pure. Nearest neighbours first, business rules after.

The result is a pipeline where the expensive model never sees a lone article. It only reads stories, and only the one in seven that more than one article has joined.

References

1. J. Allan, J. Carbonell, G. Doddington, J. Yamron, Y. Yang. Topic Detection and Tracking Pilot Study: Final Report. Proceedings of the DARPA Broadcast News Transcription and Understanding Workshop, 1998.
2. Y. A. Malkov, D. A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42(4), 2020. arXiv:1603.09320
3. A. Clauset, C. R. Shalizi, M. E. J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 2009. arXiv:0706.1062
4. D. Vrandečić, M. Krötzsch. Wikidata: a free collaborative knowledgebase. Communications of the ACM 57(10), 2014.
5. G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, 1949.

Data: NewSumm pipeline output for stories first seen 3–4 November 2026 (clustering, sources, funnel and arrival figures) and 3–9 November 2026 (entities). Similarity figures are from a random sample of 2,500 articles in stories of four or more, and 2,498 random cross-story pairs. The own-story centroid includes the article itself, which lifts that curve slightly, most for small stories.

Originally published on the NewSumm blog. NewSumm groups news from hundreds of outlets into single stories: newsumm.com.