Factuality benchmarks quietly go bad. A question like "Who is the CEO of the company that owns Instagram?" had a correct gold answer when it was written. As the world changes, that answer becomes wrong, and models that know the newer fact get marked down for it. Jiang et al. found that up to 63.78% of BoolQ's time-sensitive items had changed since release, and that more than 20% of GPT-4o-mini's time-sensitive answers were penalized unfairly (When Benchmarks Age). The usual fix is to re-check every item against web search with a language model in the loop. That costs a lot, it is noisy, and it has a blind spot: it cannot tell "the web says nothing newer" apart from "nothing newer has happened."
We propose attaching to each benchmark answer a shelf-life certificate: a machine-checked statement of the time window over which the stored evidence logically forces that answer, given a small set of rules about how facts behave over time. Inside its window an item is certified current. Past the window it is undetermined, which means it should be re-checked. It is not automatically wrong. Database theory has a precise name for "this evidence forces this answer": query determinacy, the question of whether a set of stored views fixes a query's result on every database consistent with them. That theory also says when the check becomes undecidable. We use those results to choose the rule language deliberately, so that certification stays fast and provably terminates.
Core Claim
An answer goes stale through a specific structure. Some fact is valid on a time interval. The interval's end may be unknown. Multi-hop answers chain such facts together. Uniqueness rules ("a country has one head of state at a time") let a newer fact close an older fact's interval.
Write $\Sigma$ for those rules, $V$ for the evidence stored with an item (timestamped facts plus the time each was observed), and $Q_t$ for the item's question asked at time $t$. The item's certified window is the set of $t$ for which
$$ \forall D, D' \models \Sigma:\quad V(D) = V(D') \;\Rightarrow\; Q_t(D) = Q_t(D'), $$
where $D, D'$ range over complete world-histories consistent with the rules. In words, any two histories that agree with the evidence must agree on the answer at $t$.
For general rule sets this test is undecidable. That holds for key constraints mixed with inclusion constraints (Calì et al.), for conjunctive queries under even unary inclusion dependencies (Monotone Rewritability and the Analysis of Queries, Views, and Rules), and for simple path queries on acyclic graphs (Gluch et al.). Our claim is that the overwhelming majority of real time-sensitive benchmark items fall into a restricted fragment where the test runs in polynomial time. That fragment has three ingredients. The first is temporal keys, meaning one value per entity, relation and time point. The second is inclusion rules that do not conflict with those keys. The third is chains of single-valued hops. Within the fragment, the certificate separates stale gold labels from undetermined ones more accurately than search-based audits, and at a small fraction of the cost.
What is new is the three-way verdict (certified, stale, undetermined) backed by a soundness guarantee. Existing pipelines give a two-way verdict from noisy search.
How This Relates to Prior Work
Two papers motivate the gap. When Benchmarks Age measures decay with a search-plus-LLM audit and reports 89.52% verification accuracy. We replace its open-ended search with a check over stored evidence, and we add the undetermined verdict it lacks. TDBench builds questions from temporal databases. It uses temporal functional dependencies only as filters that guarantee a single answer, and it shows models lose 21.7% when dates must also be right. We reuse its idea of keyed temporal data, but we treat the keys as rules that close intervals, and we let them interact with inclusion rules across hops. TDBench does not study that interaction.
The closest design is the Rechecker in Can Agent Memory Systems Track Evolving State?. It walks acyclic derived_from links and marks downstream memory units stale when a base fact changes. It has no uniqueness rules, so it cannot infer that a successor's start date ends a predecessor's term. It also has no undetermined state: everything is either fresh or stale.
Four papers constrain or supply the method. Calì et al. supply the decidable fragment: under non-key-conflicting inclusion dependencies, answering is polynomial-time via rewriting. Kikot, Benedikt and coauthors show that guarded rules keep determinacy decidable and yield a Datalog rewriting; this is our escape route if items need richer rules. LARS+ shows that the forward progression of time can guarantee termination when rules invent new values. We use its temporally weak acyclicity condition to restrict any rules that invent entities. Gluch et al. act as a negative result. They rule out letting items use arbitrary path queries over views, which is why we restrict items to chains of single-valued hops. Agent-C also checks LLM behavior against formal temporal specifications with a solver, but it targets short tool-call sequences, not the aging of facts.
Research Program
The work has three pieces.
The checker. We take Wikidata-style statements with start and end qualifiers and model them as interval facts. A per-relation temporal key closes intervals: if a successor fact starts at $s$, the predecessor's interval ends by $s$. Inclusion rules link hops; for example, an owner must be an organization with a CEO relation. The checker rewrites each item's query in the style of Calì's ID-rewrite and computes the maximal interval over which every hop is forced. An open-ended interval observed at time $o$ certifies only up to $o$, unless a closing fact exists. Items whose rules fall outside the non-key-conflicting fragment are reported as out-of-fragment and are never silently certified. The fraction of out-of-fragment items is itself a headline measurement.
Item-to-query mapping. A language model translates each natural-language item into a chain query over the knowledge base. The checker then validates that the chain's result matches the original gold answer at the item's release date. If it does not, the mapping is rejected. On TDBench the true SQL is known, so we can measure mapping error directly and separately from checker error.
Grading with the certificate. A model answer is graded as correct, correct-for-a-past-window (stale but once true), or wrong. Items with undetermined evidence are routed to re-verification instead of being scored. This turns Jiang et al.'s Evaluation Misleading Rate into something that can be computed without search.
As a secondary use, we apply the same checker at inference time to retrieved passages. It decides whether a passage set forces an answer for the query's time, or whether the model should abstain or retrieve again. This targets the drop of nearly 48% that EvolveBench reports when context carries a mismatched timestamp.
Baselines
The naive reference is to do nothing: score against the original gold labels. Jiang et al. show this misleads on more than 20% of time-sensitive items for GPT-4o-mini.
The strongest existing method is the When Benchmarks Age audit, which combines time-sensitive item extraction, Wikipedia plus ReAct/chain-of-thought search, and comparison. Its reported verification accuracy is 89.52%. It is the strongest competitor because it is the only published end-to-end gold-refresh pipeline. We will rerun it on exactly our items with the same language model, and give it a search budget equal to or larger than our checker's model calls. We beat it if our accuracy on items with a verdict exceeds 89.52% on the same items, and our certified-current verdicts are wrong less than 2% of the time. Coverage counts too: we report what fraction of items get a verdict, so a high abstention rate cannot buy accuracy.
A second baseline is TDBench-style regeneration: re-run the item's query on the latest knowledge-base snapshot and compare the result to the gold label. This is strong because it is cheap and exact whenever the snapshot is complete. We give it the identical mapped queries. We beat it on the items where the snapshot is silent, where regeneration must guess "unchanged."
A third baseline adapts the StateMem Rechecker: propagate staleness along hop links whenever any base fact receives a new statement, with no keys and no undetermined state. This tests whether formal determinacy adds anything over dependency-graph bookkeeping.
The key ablation isolates the main ingredient. We keep the checker but drop the temporal-key interaction, so that newer facts no longer close older intervals. A second ablation restricts the checker to single hops.
Why not just…?
Why not just re-query the live knowledge base? For items that are already database queries, this is a real threat. The failure it cannot see is silence. If no newer CEO statement exists yet, regeneration declares the old answer current. A certificate instead says "certified only to the last observation." The backtest below measures how often silence hides a change. If that rate is negligible, our advantage shrinks to the multi-hop and NL-mapping cases, and we will report it that way.
Why not just audit with web search and an LLM judge? Jiang et al.'s pipeline is 89.52% accurate, and it inherits search noise and indexing lag (UIS-Digger). It also gives no guarantee on the items it calls current. Our head-to-head comparison measures error separately on items each method calls current and on items it calls stale. We also measure cost per item. Search will plausibly win on items whose facts are absent from structured data. We expect those items to be the out-of-fragment ones, and the comparison should be read that way.
Why not just flag any answer whose supporting interval has no end date? For single-hop items this heuristic essentially is the certificate. We say so plainly. Formal machinery should only pay off in two cases: multi-hop items, where staleness in an inner hop is invisible to the heuristic, and items where a successor's start date closes an interval that the source never explicitly ended. The single-hop and no-key ablations test exactly this. If they match the full checker on real benchmarks, the formal contribution reduces to the coverage analysis, and the proposal should be scoped down accordingly.
Proposed Experiments
The decisive experiment is a snapshot backtest on held-out time. We compute certificates using knowledge-base snapshots and evidence available at time $T_1$. We then judge every verdict against a later snapshot at $T_2$, which no method sees.
We run this on three item sets. The first is TDBench's Wikidata items (countries, athletes, organizations), where the queries are known. The second is the 1,640 EvolveBench queries, which are Wikidata-sourced. The third is the time-sensitive subsets of BoolQ, TriviaQA and NaturalQuestions identified by Jiang et al.
We report, separately for single-hop and multi-hop items:
- the fraction of items inside the decidable fragment;
- the error rate of certified-current verdicts, which soundness predicts should be near zero apart from source errors;
- precision and recall for detecting stale labels;
- the undetermined rate;
- cost in model and search calls.
Every baseline above runs on the same items.
The second experiment re-scores models with certified grading. GPT-4o, which EvolveBench reports at 79.36 EM, and Llama 3.1-70B, reported at 72.47 EM, are re-scored with the three-way grading. We then check whether the corrected misleading rate agrees with Jiang et al.'s search-based estimate on the shared items.
The third experiment is the inference-time gate on EvolveBench's misaligned-context setting. We compare four options: answering from the passage, filtering passages by timestamp, asking the model whether the context suffices, and checker-gated answering. We measure accuracy against the reported drop of nearly 48%, and we count abstentions.
The idea fails if any one of three things happens: more than a small fraction of real items fall outside the fragment, the single-hop heuristic matches the full checker on multi-hop items, or regeneration's silence errors are rare. Each of these outcomes is measured directly above.
References
- When Benchmarks Age: Temporal Misalignment through Large Language Model Factuality Evaluation
- Query rewriting and answering under constraints in data integration systems
- Monotone Rewritability and the Analysis of Queries, Views, and Rules
- The First Order Truth Behind Undecidability of Regular Path Queries Determinacy
- Harnessing Temporal Databases for Systematic Evaluation of Factual Time-Sensitive Question-Answering in LLMs
- Can Agent Memory Systems Track Evolving State?
- Chasing Streams with Existential Rules
- Enforcing Temporal Constraints for LLM Agents
- EvolveBench: A Comprehensive Benchmark for Assessing Temporal Awareness in LLMs on Evolving Knowledge
- UIS-Digger: Towards Comprehensive Research Agent Systems for Real-world Unindexed Information Seeking