Pay for Evidence Only When It Would Change the Verdict: Index-Based Stopping for Fact-Checking Under Heterogeneous Costs

Automated fact-checkers usually spend the same effort on every claim. MultiFC attaches ten search snippets to each claim. RAAR runs four large-language-model agents on every post. Even systems that save money, such as FIRE, ask a single yes/no question: should the model search the web or answer from memory? In practice the available checks form a ladder with very different prices. A speaker's track record costs nothing. A style classifier costs a fraction of a cent. One search query costs a fixed API fee. Reading several full pages, or running a multi-step reasoning model over them, can cost a hundred times more, and the price depends on the claim: long pages and multi-hop claims cost more. We propose to treat each rung of this ladder as a "box" with a claim-specific price and an uncertain payoff. For each box we learn to predict how much opening it would improve the chance of a correct verdict. We then open boxes in the order given by a Gittins-style index, a single number per box that combines predicted payoff and cost, and stop as soon as the current verdict is worth more than any unopened box.

The practical claim is this. On a platform with a fixed daily verification budget, the right question is not "is the cheap model confident?" but "would the next, more expensive check change the answer often enough to pay for itself on this claim?" The two questions differ most in exactly the places misinformation research cares about. Cheap classifiers are confidently wrong on stylistically disguised claims, and multi-hop claims gain nothing from one search but a lot from two. We will test whether an index policy built on predicted value of information beats confidence-threshold cascades and FIRE-style adaptive search on these slices, at equal dollar cost, on MultiFC, FEVER and Factcheck-Bench.

Core Claim

Costs in verification are heterogeneous in two ways. They differ across tiers, and within a tier they differ across claims because of retrieved page length, number of hops and tokens of reasoning. Current stopping rules ignore both. FIRE lets the model decide from its own confidence whether to search, counts every search as equally costly, and stops on heuristic thresholds and step limits. Against SAFE it reports a 7.6x reduction in LLM API cost and a 16.5x reduction in search queries, with F1 of 0.87 on "True" labels on Factcheck-Bench. That result motivates this proposal: adaptive spending clearly pays. It also marks the gap: the stopping signal is the checker's own confidence, which Automatic Fake News Detection: Are current models "fact-checking" or "gut-checking"? shows is driven by emotional and stylistic cues that shift under formality transfer.

Our mechanism takes its stopping rule from the cost-aware optimization literature. Cost-aware Stopping for Bayesian Optimization derives a stopping rule from the Pandora's Box Gittins Index. In that model each unopened box has a cost and an uncertain reward, and one stops once the best value in hand beats every remaining box's index. That paper supplies the method but applies it to hyperparameter search. We apply it per claim, over verification tiers.

For tier $k$ on claim $x$, let $c_k(x)$ be its predicted dollar cost and $V_k(x)$ the random probability of a correct verdict after opening it. The index $\sigma_k(x)$ is the value solving

$$\mathbb{E}\big[(V_k(x) - \sigma_k(x))^+\big] = \lambda \, c_k(x),$$

where $(\cdot)^+$ keeps only positive parts. Here $\lambda$ is a price per dollar that converts cost into accuracy units. The policy opens the unopened tier with the largest index. It stops when the current verdict's estimated correctness $v$ exceeds every remaining $\sigma_k$. The price $\lambda$ is set once per budget period, by bisection on validation data, so that expected spend across the claim stream meets the budget $B$. In other words, $\lambda$ acts as the Lagrange multiplier of the budget constraint.

The new learned component is the outcome predictor. For each tier, a small model is trained on logged full-pipeline runs to output the distribution of $V_k$ and the cost $c_k$ from cheap features: claim text, metadata, and outputs of tiers already opened. Crucially, it predicts disagreement with the higher tier, not the lower tier's own confidence.

One caveat must be stated up front. The Gittins/Weitzman rule is optimal only when boxes are independent, and verification tiers are correlated because evidence is nested. In our setting the index is a principled heuristic, not an optimality guarantee. Part of the program is to measure how much this costs against a rollout planner.

Research Program

The first component is a replayable cost ladder, so that every policy can be charged the same dollars on the same data. On MultiFC (MultiFC) the ten Google snippets per claim are already stored, so tiers can be simulated exactly. The tiers are:

  • Tier 0: claim plus metadata, costing roughly nothing.
  • Tier 1: a stylistic and emotional classifier in the EmoAttention family from the gut-checking paper.
  • Tier 2: one snippet.
  • Tier 3: three snippets.
  • Tier 4: ten snippets with reranking, as in MultiFC's crawled_ranked model.
  • Tier 5: an LLM reasoning over all snippets, charged by actual token count.

Search tiers are charged at a fixed per-query API price. LLM tiers are charged at measured tokens times a published per-token price, which makes cost vary across claims. On FEVER (FEVER) the ladder is parametric LLM answer, single-page retrieval, then second-hop retrieval. We charge by pages and tokens, so the 17% multi-sentence and 12% multi-page claims are naturally more expensive to resolve. On Factcheck-Bench we reuse FIRE's setting so that FIRE runs natively.

The second component is the outcome predictor, trained on a held-out split where every tier was run. It predicts, for each unopened tier, the distribution of post-tier correctness (as a small categorical histogram) and the log cost. The third component is the index policy with a budget price, as above. The fourth is an analysis of where the index helps. We break results down by style-transferred versus original claims, single-hop versus multi-hop claims, and claims inside versus outside the training domain. These slices correspond directly to the documented failure modes of confidence-based stopping.

Baselines

The naive references are the two ends of the ladder. The cheap end is tier 0/1 only. It corresponds to MultiFC's claim-only model, which reports Macro F1 of 25.3%. The expensive end is always opening the full evidence tier: MultiFC reports 44.1% Macro F1 with evidence alone and 49.2% Macro F1 (Micro F1 0.625) with evidence plus metadata, all at the full ten-snippet cost for every claim. On FEVER, the end-to-end baseline reports 31.87% accuracy when correct evidence is required and 50.91% when it is not, and 64%–88% with oracle evidence. Our goal on each benchmark is to match the always-full F1 within one point at substantially lower average cost. A policy that reaches 49.2% Macro F1 on MultiFC while paying, say, half of the always-ten-snippets spend would count as beating the naive reference. The specific target ratio will be fixed after pilot cost measurement, not asserted here.

The strongest existing method is FIRE. It is the only system in the literature that already adapts retrieval spending per claim, and it has the reported numbers above on Factcheck-Bench. We will run FIRE with the same backbone LLM, the same search backend and the same price table. We will sweep its confidence threshold and step limit to trace its full cost–accuracy curve rather than comparing against one operating point. On MultiFC and FEVER, FIRE has no reported result on Lacuna, so we will run it ourselves. Beating FIRE means a higher area under the F1-versus-dollars curve and higher F1 at FIRE's own chosen spend, with the gap concentrated on the style-shift and multi-hop slices, which is where our mechanism predicts it.

The most dangerous baseline is a tuned confidence-threshold cascade. It uses the same tiers and the same trained classifiers, and escalates whenever the current tier's calibrated confidence falls below a per-tier threshold. The thresholds are tuned on the same validation split with the same number of tuning trials as our $\lambda$ search. A second strong baseline is a greedy one-step rule: open the tier maximizing predicted accuracy gain divided by cost, the analogue of expected improvement per unit cost from Recent Advances in Bayesian Optimization.

Three ablations isolate the key ingredients. The first replaces the predicted post-tier distribution with the current tier's confidence, keeping the index rule; this separates the value-of-information predictor from the stopping rule. The second keeps the predictor but charges every tier call a uniform unit cost, which tests whether modeling heterogeneous, claim-dependent cost matters. The third replaces the index with a rollout planner in the style of A Nonmyopic Approach to Cost-Constrained Bayesian Optimization, which simulates multi-step lookahead and handles correlated tiers. Because it is expensive, it runs only on a FEVER subset, to measure what the independence approximation loses. A hindsight oracle, which pays for the cheapest tier that happens to be correct, gives the ceiling.

Why not just…?

Why not just tune confidence thresholds per tier? This is the real threat. On clean, in-domain data a well-calibrated cascade may match our policy, because confidence and value of information coincide when the cheap model is calibrated. The case for our policy rests on two situations where they come apart. The gut-checking paper shows cheap classifiers lean on emotional and formality cues that style transfer disturbs, so they can be confidently wrong. And on multi-hop FEVER claims a first search leaves confidence flat even though a second hop would resolve the claim. The first ablation settles this directly. If the confidence-driven variant matches the full policy on the style-transferred and multi-hop slices, the predictor adds nothing and we will report that the contribution reduces to cost-aware pricing.

Why not just use FIRE and tune its threshold? FIRE has only two levels, search or no search, and it prices every query the same. It therefore cannot choose between one snippet and a full-page read, and it cannot take into account that some claims cost more to verify than others. The uniform-cost ablation and the tier breakdown will show whether the extra rungs and claim-dependent pricing account for any gain. If FIRE's swept curve dominates ours on Factcheck-Bench, the ladder is not worth its complexity on that benchmark.

Why not just retrieve top-k for every claim? MultiFC shows that fixed retrieval roughly doubles Macro F1 over claim-only. FIRE shows adaptive search cuts search cost 16.5x against exhaustive pipelines. Fixed top-k is therefore accurate but priced for the hardest claim. It also cannot buy the second hop that FEVER's multi-page claims need, which is reflected in that benchmark's 45.89% evidence recall. It remains the accuracy reference, not the competitor on cost.

Why not just build a better cheap classifier so escalation is rarely needed? The LIAR text-only CNN reaches 0.270 accuracy (Wang). Style transfer undermines affect-based detectors. A cheaper, stronger classifier would simply become a better tier 1 inside our ladder, and the policy would learn to stop there more often. The two approaches complement each other rather than compete.

Why not use multi-fidelity elimination with bias bounds instead? Multi-Fidelity Best-Arm Identification cuts cost dramatically, down to 6% of baseline in synthetic tests. However, it requires known bounds on how biased each cheap fidelity is, and no such bounds exist for LLM or style classifiers under domain shift. Our outcome predictor estimates that bias empirically, per claim, which is what makes the transfer possible.

Proposed Experiments

The main experiment plots Macro F1 against average dollars per claim on MultiFC (collapsed to the three-way True/Mixture/False labels used in the gut-checking paper, and also on the original labels) and on FEVER. It also plots F1 on "True" labels against dollars on Factcheck-Bench. The summary statistic is area under each curve, with bootstrap confidence intervals over claims.

The first decisive check is style robustness. We apply formality transfer to MultiFC test claims, restricting to the Snopes subset as the gut-checking paper did because of cost. We then measure the "confident-wrong stop rate": how often each policy stops at a cheap tier with a wrong verdict. Our prediction is that the threshold cascade's rate rises sharply after transfer while the index policy escalates instead.

The second decisive check is on FEVER multi-page claims. We measure how often each policy buys a second hop and how accuracy changes as a result. We compare the index against the rollout planner to quantify the cost of treating tiers as independent.

The third check shifts the domain. We train the outcome predictor on PolitiFact-derived MultiFC sources and test on the remaining sources. If predicted costs and payoffs miscalibrate, the budget price will overspend or underspend, and we will report the budget violation alongside accuracy.

A negative result on the first two checks would be informative in itself. It would say that, for fact-checking, cheap-model confidence is already a sufficient escalation signal and heterogeneous-cost machinery is unnecessary.