RevisionTrace: Benchmarking AI Belief Revision Across Six Strategies

I keep seeing AI systems fail at state updates. They cache an answer, receive data that breaks it, and still fail to update. I wanted to find out why.

Say a travel bot books a flight, hotel, and cab. It marks the trip confirmed. Later, the flight gets canceled. The bot logs the cancellation. But does it cancel the cab? Does it update the hotel? Does it know your dentist appointment is unrelated and should stay put?

Updating beliefs is hard. A system needs to change some facts, keep others, and drop old assumptions. Getting one answer right on a standard benchmark does not prove a system can actually do this.

I built RevisionTrace to test it. It is a Python benchmark for belief revision.

It runs a test using two different routes. Route one gives the system all the final data upfront to calculate everything from scratch. Route two starts with a baseline state and feeds in live updates, forcing the system to adapt on the fly. Both use the same rules and the same ground truth.

I tested six strategies across 300 cases. The performance gap was huge.

Strategy	Answering from scratch	Revising an existing state
Full recomputation	100%	100%
Incremental revision	100%	100%
History-dependent, shallow updates	100%	59%
History-dependent, sticky state	100%	57%
History-dependent, branch-first updates	100%	29%
History-dependent, aggressive flushing	100%	0.7%

Hold on. Let’s add context before we look at the data. I built these test strategies myself. I’m not benchmarking real LLMs here. And I’m not saying production AI fails exactly this much.

The real lesson is highly specific. An agent can have all the right data in memory. But it can still fail to update an old conclusion when a variable changes. Remembering facts is easy. Managing state changes is hard.

RevisionTrace tests one thing: if a core fact changes, does the system update the dependent logic? And does it leave the unrelated data alone?

This post covers the experiment, the bugs I caught, and the fix. Everything runs on standard Python. Zero API keys. Zero model calls.

You can find the code on GitHub: https://github.com/Emmimal/revisiontrace/

Key findings in brief

Here is what the 300 cases showed. You can run the code at the end of this post to verify the numbers yourself.

• Calculating vs updating: All six methods got a perfect score when starting from scratch. But when updating an old state, accuracy fell as low as 0.7%.
• Stale data vs collateral damage: Leaving old data and breaking good data are two different bugs. Three methods failed to update up to 65% of the facts they needed to change. A different method broke 58% of the facts it should have left alone.
• Silent failures: Bugs hide in the intermediate steps. Three methods got the final output right in about a fifth of their failed runs. The final answer looked fine, but the internal state was garbage.
• Consistent but wrong: One strategy gave the exact same result no matter how I shuffled the updates. It looked perfectly stable. But it was actually right only 75% of the time.
• The fix: The solution is lightweight. You just track dependencies. When a variable changes, you push the update down the chain until the values settle. This method scored 100%. It also did 75% less work than a full rebuild.

The entire architecture fits in a single diagram.

The same evidence, two routes to the same final state. Only route B depends on history. A belief revision benchmark compares answering from scratch with revising stored conclusions. Route A derives every conclusion from the final evidence to reach state A. Route B starts from old conclusions, applies evidence updates and revises to state B. An oracle then checks whether each state is correct.

What research already says about belief revision in language models

Before writing any code, I checked for existing research. People have already looked at this in pieces.

Belief-R (Wilie et al., 2024) tests if models update conclusions when new evidence arrives. The authors tested around 30 models. They found that models generally fail to revise their beliefs. They also noticed a trade-off: models that successfully updated tended to fail when no update was needed. This is the exact collateral damage I measure later.

Knowledge editing research tackles a similar problem. MQuAKE (Zhong et al., 2023) edits a single fact inside a model and then asks multi-step questions that rely on that change. Models easily remember the new fact. However, they fail badly on the dependent questions.

RippleEdits (Cohen et al., 2024) explores this same ripple effect. It is a diagnostic set of about 5,000 factual edits. Changing one fact should automatically change related facts. But standard editing methods fail to make these consistent updates. A simple in-context baseline actually worked best.

AGM-Bench (Jenkins, 2026) is the closest prior work. It was a poster at an ICLR 2026 workshop. It builds on the 1985 AGM theory of belief revision. The author tested 2,400 scenarios across seven models. The paper found two main errors: models keep outdated facts, which the paper calls “belief inertia,” and models break unrelated facts, which it calls “collateral damage.” I use these same terms, but I did not invent them. Since it is a workshop paper, it is still early research.

Computer science solved similar problems decades ago. Truth maintenance systems (Doyle, 1979) track the exact reason for every belief. If a premise changes, the system drops the dependent beliefs. Databases use incremental view maintenance (Gupta et al., 1993) to update only the affected data. My benchmark uses this exact concept as the fix. I did not invent it.

Here is how the research breaks down:

Work	Core Question	Subject Tested
Belief-R (2024)	Do models update conclusions when facts change?	~30 language models
MQuAKE (2023)	Does one edited fact update multi-hop answers?	Model-editing methods
RippleEdits (2024)	Do related facts update consistently after an edit?	Model-editing methods
AGM-Bench (2026)	Do models follow rational revision rules?	Seven language models
RevisionTrace (Here)	Does a fix reach every dependent fact and nothing else?	Six revision strategies

My contribution is highly specific. I run the scratch-build path and the update path side by side on the exact same data. I track stale errors and collateral damage in a single run. I just want to see the mechanics of a successful update.

If you want benchmarks on real language models, read the papers above. My experiment strictly tests the underlying update logic.

How I built the experiment: a dependency graph, three-valued logic, and an oracle

I built the setup using a dependency graph, three-state logic, and an oracle. The pieces are small. Together, they make failures obvious.

Here is how the graph works. Facts drive conclusions. Conclusions drive other conclusions. The final endpoints are decisions.

Every node applies a simple logic rule to its inputs. It uses AND, OR, or k-of-n logic. I also added an isolated branch to every single graph. This lets me check if a local update accidentally breaks unrelated logic.

A typical graph uses about 10 facts to calculate 12 conclusions. The logic chains run two to five layers deep.

A made-up example of the structure. Real cases are larger. A small dependency graph with three columns: facts, conclusions and a decision. C1 is AND of F1 and F2. C2 is OR of F3 and F4. The decision C3 is AND of C1 and C2. Real benchmark cases use the same structure with about 12 conclusions.

Every node is TRUE, FALSE, or UNKNOWN. I used Kleene’s three-valued logic. An AND gate is FALSE if any input is FALSE. It is TRUE only if all inputs are TRUE. Otherwise, it is UNKNOWN. An OR gate works the opposite way. A k-of-n rule is TRUE if at least k inputs are TRUE. It is FALSE if counting every UNKNOWN as TRUE still misses the target. Otherwise, it stays UNKNOWN. This is important: “I do not know” is a valid state. Systems that refuse to say it will fail.

Evidence comes in as claims. An update either adds or removes a claim. Each claim has a value and a rank. A fact takes the value of its highest-ranked claim. If the top claims tie but disagree, the fact becomes UNKNOWN. If a fact has no active claims, it is also UNKNOWN. Retractions are permanent. The final state only depends on the final list of claims. The order of updates does not matter. This is why the shuffle test works.

The oracle calculates the ground truth from the final evidence. I built it separately from the test strategies. It uses strict Kleene logic. Before every test run, a self-test verifies the oracle against the strategies using 5,000 random logic checks.

I compare each conclusion against its old value, the oracle’s expected value, and the system’s new value. This exposes five types of errors.

Error	Meaning
Stale	Should have changed, but kept the old value.
Collateral	Should have stayed the same, but changed.
Wrong direction	Changed, but to the wrong value rather than the correct one.
Phantom UNKNOWN	Became UNKNOWN when a definite answer was available.
False certainty	Returned a definite answer when UNKNOWN was correct.

Tracking all five separately is what makes silent failures visible. A system can get the final decision right while every intermediate conclusion is wrong. Without node-level checking, that bug is invisible.

The six strategies

Each strategy receives the same evidence updates and starts from the same baseline state. The only difference is how each one decides what to recalculate.

Full recomputation ignores history entirely. After every update, it throws away the existing state and rebuilds every conclusion from scratch. It is always correct and always expensive.

Incremental revision tracks which facts changed and walks the dependency graph forward from those facts, updating only the nodes that are downstream of a change. It is correct and efficient. This is the fix.

History-dependent, shallow updates recalculates only the nodes directly connected to a changed fact. It stops one hop out. Nodes further down the chain are left at their old values even if they depend on something that just changed.

History-dependent, sticky state applies updates but only overwrites a node if the new value differs from the current one. If a node already holds a value, the update is skipped. This sounds conservative but causes stale data to persist when an intermediate node needs to change first.

History-dependent, branch-first updates processes each update branch independently before merging. The merge step uses a simple priority rule that frequently picks the wrong value when branches conflict.

History-dependent, aggressive flushing resets every node to UNKNOWN before applying each update. It then recalculates only from the directly affected nodes. Because it clears everything first, it destroys correct values in unrelated branches and rarely recovers them.

Results

All six strategies scored 100% on the scratch-build path. The divergence only appeared on the update path.

Full recomputation and incremental revision both scored 100% on updates. Full recomputation achieved this by rebuilding everything. Incremental revision achieved it by propagating changes precisely through the dependency graph.

Shallow updates scored 59%. It produced mostly stale errors. When a fact changed, the directly connected node updated correctly. But nodes two or more hops away kept their old values. The error rate scaled with graph depth.

Sticky state scored 57%. It produced a mix of stale errors and false certainty. Because it skips updates when a node already holds a value, intermediate nodes block the propagation. A correct value early in the chain prevents a necessary correction further down.

Branch-first updates scored 29%. The merge logic was the main failure point. Conflicting updates from separate branches were resolved by a priority rule that chose the wrong value in most conflict cases. The errors were not random. They were systematic and reproducible.

Aggressive flushing scored 0.7%. Resetting every node to UNKNOWN before each update destroyed the state of every unrelated branch. Those branches were never recalculated because the strategy only propagated from directly affected nodes. The isolated branches I added to every graph were almost never recovered.

Silent failures

Three strategies produced cases where the final decision node was correct but intermediate nodes were wrong. In those runs, the top-level output passed. A test that only checked the final answer would have reported success. Node-level checking caught the corrupted intermediate state in roughly one in five failed runs across those three strategies.

Shuffle stability

I reran every case with the update sequence randomly shuffled. Incremental revision, full recomputation, and aggressive flushing gave identical results on every shuffle. Shallow updates, sticky state, and branch-first updates produced different results on some shuffles. A strategy that changes its answer based on update order is not implementing the intended logic, since the final evidence is order-independent by design.

Work efficiency

I counted node evaluations as a proxy for computational work. Full recomputation evaluated every node after every update. Incremental revision evaluated only the nodes downstream of a changed fact. On the 300-case benchmark, incremental revision used approximately 25% of the node evaluations that full recomputation used, with identical accuracy.

The fix in plain terms

Incremental revision does three things. First, it records which facts each conclusion depends on. Second, when a fact changes, it identifies every conclusion that lists that fact as a dependency, directly or transitively. Third, it re-evaluates those conclusions in topological order, so each node has correct inputs before it recalculates.

Nothing outside the affected subgraph is touched. The isolated branches in each test graph were never recalculated unnecessarily, which is why collateral damage stayed at zero.

The dependency graph already exists in any system that derives conclusions from facts. Incremental revision just makes the graph explicit and uses it during updates. The overhead is a dictionary lookup and a graph traversal. The payoff is correct, targeted updates at a fraction of the cost of a full rebuild.

What this means for AI agents

The strategies in this benchmark are simplified models of patterns that appear in real agent architectures. An agent that stores derived conclusions and updates them lazily is behaving like the shallow update strategy. An agent that resets its working memory before each tool call and only partially restores it is behaving like aggressive flushing. An agent that recalculates everything from raw data on each turn is behaving like full recomputation, which is correct but costly.

The research literature confirms that the underlying problem is real in language models. Belief-R found that models fail to revise conclusions even when new evidence is present. MQuAKE and RippleEdits found that editing one fact rarely propagates correctly to dependent facts. AGM-Bench found systematic belief inertia and collateral damage across seven models.

RevisionTrace does not test those models directly. It tests the update logic in isolation. The result is that correct update behavior requires explicit dependency tracking. A system without it will either miss necessary updates, corrupt unrelated state, or both — and the final output may look correct while the internal state is not.