Certified Exclusion Caps: Making Entailment-Based Novelty Checks Affordable in Text Streams

A system that pushes breaking-news updates to users must decide, for every incoming sentence, whether it says anything the user has not already been told. The accurate way to judge this is natural language inference (NLI). NLI is a model that decides whether one sentence logically implies another. The accurate check is therefore to ask whether any already-delivered item implies the new one. Doing that against the whole delivery history costs one expensive model call per history item for every arrival, so deployed systems fall back on a cosine-similarity threshold over sentence embeddings. That shortcut is known to be wrong in both directions. It misses paraphrases that use different words, and it merges factual updates ("death toll rises to 40") with the earlier sentence they revise.

We propose to keep NLI as the judge and use geometry to decide which history items it needs to examine. Embeddings live on a unit sphere. Around each incoming candidate we draw a cap, a spherical region defined by a cosine threshold. The threshold is calibrated so that, with a stated probability, any history item that implies the candidate lies inside the cap. NLI runs only on history items inside the cap. A metric tree with triangle-inequality bounds discards whole groups of history items at once without computing their cosines. The new element is that the threshold is calibrated separately by local graph centrality: how densely connected the candidate's neighbourhood is in the similarity graph of recent stream items. Our hypothesis is that dense story cores and sparse peripheral regions need very different cap sizes. If that holds, one global threshold is either wasteful or unsafe.

Core Claim

The claim is that a centrality-stratified, conformally calibrated cosine cap gives a controlled miss rate for NLI-judged redundancy. It should nearly match exhaustive NLI on streaming novelty benchmarks while cutting NLI calls per arrival by a large factor. At an equal budget of NLI calls, it should also make fewer redundancy errors than retrieving a fixed number of nearest neighbours and re-checking them with NLI.

Formally, let $x$ be a redundant candidate and let $s(x)$ be the largest cosine between $x$ and any history item that NLI says implies $x$. Let $c(x)$ be the centrality stratum of $x$, defined below. For a tolerated miss rate $\varepsilon$ we set a threshold for each stratum from held-out redundant pairs:

$$t_c = \text{the } \lfloor \varepsilon (n_c+1) \rfloor\text{-th smallest value of } s(x) \text{ among the } n_c \text{ calibration candidates in stratum } c.$$

Split-conformal reasoning then gives the guarantee $P(s(x) < t_{c(x)}) \le \varepsilon$ for exchangeable data. The practical meaning is that restricting NLI to history items with cosine at least $t_{c(x)}$ misses a truly redundant candidate at most an $\varepsilon$ fraction of the time, within each stratum. A second, inner threshold, calibrated for precision, lets near-duplicates be rejected without any NLI call.

The stratum is the k-core number of the candidate's nearest recent neighbour in a sliding-window similarity graph. A k-core is the largest subgraph in which every node has at least $k$ neighbours; an item's core number is the largest $k$ for which it belongs to such a subgraph.

How This Relates to Prior Work

The geometric machinery comes from exact optimization. Global Optimization of K-Center Clustering builds ball-shaped exclusion zones from a current upper bound and uses the triangle inequality to rule out assignments in bulk. Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering proves that points outside two spherical caps have zero coefficients and drops them from optimization. We reuse both ideas: bulk exclusion through a metric tree, and cap-shaped regions on the sphere.

Our setting differs from both in a way that matters. Their bounds are exact consequences of a known objective. The link between cosine similarity and entailment is statistical, so our caps come from calibration rather than proof. The same paper that motivates the cap idea also warns about it: You et al. note that a badly chosen cap threshold either prunes too little or excludes the answer. Calibration with an explicit $\varepsilon$ is our answer to that sensitivity.

The redundancy side supplies both the motivation and the judge. Linguistic Redundancy in Twitter finds that about 30% of event tweets are paraphrase or entailment redundancy that lexical matching misses. SDAS shows raw cosine similarity collapsing under transformations that preserve meaning, in a different modality. NovAScore breaks documents into atomic content units, the individual facts a text asserts. It reports NLI accuracy of 0.94 at judging whether such a unit is novel. It also concedes that pairwise checks against a growing history are the cost barrier, and that barrier is what we attack.

Streaming systems such as ECNU at TREC 2015 compare against a history buffer with surface similarity. Osborne et al. replace the linear scan with locality-sensitive hashing, which buckets similar vectors together, and accept misses when wording diverges. Neither system calibrates its misses against an entailment judge.

Centrality enters as a conditioning signal, not as the ranker. Degeneracy-Based Real-Time Sub-Event Detection shows that k-core structure over a sliding window separates cohesive sub-events from chatter. We borrow its windowed degeneracy computation. We use it to answer a different question: how far apart, in embedding space, are the entailment pairs in this part of the stream?

Chen et al. and RAGP combine centrality with redundancy. The first does so for scoring finished summaries after the fact. The second prunes prompts by counting random-walk visits. Neither offers a guarantee on missed redundancy. Our proposal also does not claim to resolve the latency tension raised by the streaming summarization work, which is that waiting for cohesion delays alerts. It sidesteps that tension: centrality only sizes the cap, so an isolated first report is still judged by NLI with no wait.

Research Program

The first phase is diagnostic and could falsify the premise on its own. On streams from the TREC 2014 Temporal Summarization corpus and TREC 2015 Microblog, and on documents split into content units from TAP-DLND 1.0 and APWSJ, we run exhaustive NLI between each candidate and its full history on subsampled windows. This gives ground-truth values of $s(x)$. We then plot how $s(x)$ is distributed across core-number strata. We also measure how many high-cosine neighbours NLI rejects in each stratum; these are mostly factual updates.

The design rests on two expected patterns. Dense cores should contain many high-cosine non-entailing neighbours, which argues for tight caps. Peripheral regions should contain low-cosine paraphrases, which argues for wide caps. If the distributions do not differ, the stratification adds nothing and we report that.

The second phase builds the system. Its parts are a metric tree over the embedded history, the per-stratum thresholds $t_c$ together with inner precision thresholds, the windowed k-core computation, and an NLI model run only on items that survive the pruning. We also study recalibration when the stream drifts, because conformal guarantees assume exchangeability and news streams violate it. The plan is to recalibrate over a rolling window and report how the realized miss rate compares with $\varepsilon$ as time passes.

The third phase plugs the redundancy module into an otherwise fixed push pipeline and measures end-to-end effects. The relevance classifier and the emission policy stay the same throughout, so any change comes from the redundancy judgments.

Baselines

The naive reference point is a fixed global cosine threshold with no NLI. We tune it on TAC-2010-style held-out data, meaning a validation split drawn from the training topics. This is what most push systems deploy. Beating it means fewer redundancy errors, meaning both missed paraphrases and suppressed updates, at an acceptable added cost.

The quality ceiling is exhaustive NLI against the full history, with the same NLI model. It defines the error rate we are trying to approach, and every other method's NLI-call count is reported as a fraction of it.

The strongest practical competitor is retrieving the $k$ nearest history items with an approximate nearest-neighbour index and re-checking them with NLI. It is a strong competitor because it already concentrates NLI on the most similar items. For fairness we sweep $k$ so that its average NLI calls per arrival match ours at each $\varepsilon$, using the same embedder, NLI model and tuning data. We beat it if, at matched calls, our redundancy error rate relative to exhaustive NLI is lower. We also beat it if our realized miss rate stays within $\varepsilon$ in every stratum while top-$k$'s rate varies uncontrolled across strata.

The locality-sensitive hashing buffer of Osborne et al. is the established streaming method. It is run as a candidate generator for the same NLI judge.

Two ablations isolate our ingredients. The first uses a single global conformal threshold, keeping the calibration but removing centrality. The second stratifies by plain degree instead of core number, keeping density but removing degeneracy.

For end-task context, the file gives reported numbers on the same benchmarks. On TREC 2015 Microblog Scenario A, ECNU reports an expected latency-discounted gain of 0.2314, ranking 13th of 31 runs. On TREC 2014 Temporal Summarization, the best run in the track overview reached an $\mathcal{H}$ score of 0.1162. $\mathcal{H}$ is the track's combined score of latency-discounted gain and nugget recall.

At the unit level, NovAScore reports NLI accuracy of 0.94 on novelty of atomic content units, and a point-biserial correlation of 0.626 with human judgments on TAP-DLND 1.0. The last figure measures how well the score tracks a binary human novel/not-novel label. For APWSJ, no reported numeric result was found on Lacuna.

These end-task numbers come from different pipelines, so they are context rather than targets. Our headline comparison is always the same pipeline with the redundancy module swapped.

Why not just…?

Why not just retrieve the top-k neighbours and run NLI on those? This is the real threat, and it may match us on average error when $k$ is well tuned. Our argument is that one fixed $k$ cannot suit both dense cores and sparse peripheral regions. In a dense core, many near-duplicate updates crowd the top-$k$ slots and can push out the one real paraphrase, so the right $k$ depends on local density. Top-$k$ also gives no stated miss rate. The matched-budget, per-stratum comparison settles this. If top-$k$ matches us within every stratum, the contribution shrinks to the calibration guarantee alone, and we will say so.

Why not just use a well-tuned cosine threshold and skip NLI entirely? The evidence says cosine and entailment disagree often enough to matter. Paraphrase redundancy makes up roughly 30% of event tweets according to Zanzotto et al., and SDAS shows cosine sagging under meaning-preserving changes. Cosine also cannot separate an update from a restatement. Phase one measures this directly as the rate at which cosine and NLI disagree in each stratum. If that rate is negligible, NLI is unnecessary and the proposal loses its reason to exist.

Why not just use locality-sensitive hashing? It solves the lookup cost, but as Osborne et al. acknowledge, it misses items whose wording diverges, which are exactly the paraphrase cases that matter. Its misses are also not calibrated against an entailment judge. We run it as a candidate generator under the same NLI budget, so its recall deficit is measured rather than asserted.

Decisive Checks

Three results would confirm the proposal. First, the realized miss rate must stay at or below $\varepsilon$ in every core-number stratum on held-out TREC 2014 topics, including under rolling recalibration. Second, at $\varepsilon = 0.05$ the system must need at most one tenth of exhaustive NLI's calls while its redundancy error rate stays close to exhaustive NLI's. Third, at matched calls, the stratified cap must make strictly fewer errors than both top-$k$ re-checking and the global-threshold ablation, with the gap concentrated in the densest and sparsest strata. A secondary check is that swapping cosine-buffer redundancy for this module in a fixed TREC 2015 push pipeline raises expected latency-discounted gain. If stratification shows no per-stratum benefit, we will report the calibrated global cap as the finding and drop the centrality claim.