RECAP: Belief Revision in LLM Agents via Justification Tracing

Long-horizon language model agents routinely continue acting on premises that have already been falsified. An agent assumes a file exists, derives four subgoals from that assumption, then observes that the file is absent. In our traces, the agent seldom retracts the four derived subgoals. It patches the immediate step and proceeds. We call this stale premise propagation, and it is the dominant silent failure mode we observe in production agentic systems at KriraAI.

Existing mitigations treat this as a prompting or scaffolding problem. Reflection methods ask the model to critique its own trajectory after failure. Replanning methods discard the trajectory and regenerate from scratch. Both approaches share a structural weakness. Neither maintains any representation of which conclusions depended on which premises. Without a dependency structure, retraction is either blind or total.

This post presents KriraAI research on belief revision in LLM agents and how it powers our custom AI agent development. We introduce RECAP, the Retraction Enabled Cached Attention Planner. RECAP maintains an explicit justification graph over the beliefs a model commits to during decoding. The novel component is a low-rank justification probe distilled from causal ablation measurements rather than read from attention weights. When an observation contradicts a cached belief, a learned retraction gate propagates invalidation transitively through the graph.

Our central empirical result is a reduction in stale commitment rate from 61.4 percent to 17.9 percent on our hardest evaluation split. We achieve this at 1.19 times baseline token cost. Full replanning reaches a comparable 12.3 percent but costs 4.7 times baseline tokens.

The remainder of this post covers the mechanistic cause of stale premise propagation, our argument that attention weights are the wrong dependency signal, the full RECAP architecture, our experimental design, results including one counterintuitive scaling finding, and the limitations we have not yet resolved.

The Stale Premise Problem in Long-Horizon Agent Planning

Autoregressive decoding is structurally monotonic. Every token generated becomes conditioning context for every subsequent token. There is no mechanism by which a later token can remove an earlier one from the conditioning set. The model can only write a correction and hope that attention downweights the original. This is a weak and unreliable form of retraction.

The consequence is that contradiction handling degenerates into rationalisation. We observe this repeatedly in trace analysis. When a new observation conflicts with a committed belief, the model frequently produces a bridging explanation that preserves both. It writes something like a note that the environment must have changed. The plan structure derived from the falsified premise survives intact.

What Monotonic Decoding Costs in Deployment

The cost of this failure is not uniform across task types, which is why enterprises turn to our AI solutions for enterprise to build reliable long-horizon agents.

It scales sharply with two variables that we isolate explicitly in our benchmark design. The first is dependency depth, meaning how many inference hops separate the falsified premise from the affected subgoal. The second is retraction latency, meaning how many decoding steps elapse between belief formation and contradiction.

In our baseline measurements on a 13B instruction-tuned backbone, the effect is severe:

1. At dependency depth one and latency under four steps, the baseline model retracts correctly in 78.3 percent of cases, which is acceptable performance.

2. At dependency depth three or greater with latency of twelve steps or more, correct retraction collapses to 38.6 percent of cases.

3. The resulting stale commitment rate, meaning the fraction of final plans containing at least one belief supported only by a falsified premise, reaches 61.4 percent.

4. Recovery, when it happens spontaneously, costs a median of 27 additional decoding steps and frequently loops.

Why Reflection and Replanning Are Insufficient

Reflection-based methods ask the model to review its trajectory and identify errors. This helps, but it inherits the same defect it is meant to fix. The reflection pass is itself a monotonic generation conditioned on the full contaminated trace. Our Reflexion style baseline reduces stale commitment rate only to 48.9 percent.

Full replanning is more effective but economically unattractive. Discarding the trajectory on every contradiction throws away all valid derivations alongside the invalid ones. In our measurements, this costs 4.7 times the tokens of a clean run. It also introduces a second failure mode, since regeneration can reintroduce the same faulty assumption from the same prior.

The formal machinery for this problem has existed for decades in symbolic AI. Justification-based truth maintenance systems track which conclusions rest on which assumptions and retract exactly the affected set. AGM belief revision theory formalises minimal change under contradiction. Neither has been successfully embedded inside neural decoding, because both require an explicit dependency structure that transformers do not expose.

Why Attention Weights Are the Wrong Dependency Signal

The obvious approach to extracting dependencies is to read them from attention. If a reasoning step depends on a premise, the step should attend to that premise. We tested this assumption directly and found it substantially wrong.

Our diagnostic procedure was straightforward. We generated 12,000 short reasoning traces with known ground truth dependency structure. For each derived conclusion, we measured true causal dependence by resampling ablation. We replaced the premise span with a distribution-matched alternative and measured the KL divergence in the conclusion's token distribution. This gives a causal dependency score per premise and conclusion pair.

We then compared that causal score against attention-derived estimates. Aggregated raw attention across heads and layers achieved a Spearman correlation of only 0.29 with causal dependence. Attention rollout, which composes attention matrices across layers, reached 0.34. Both are far too noisy to drive a retraction decision.

The reason is mechanistic rather than incidental. Attention weight measures where a head reads from, not what it writes into the residual stream. A head can attend strongly to a token and contribute almost nothing through its output value circuit. Conversely, a small attention weight multiplied by a high norm value vector can dominate the residual update. Dependency is a property of the write, not the read.

This observation motivates our core design decision. We estimate dependency from residual stream write vectors rather than attention distributions. We then train that estimator against causal ablation ground truth rather than against a heuristic. Justification graph attention, in our formulation, is built from causal influence and not from attention mass.

RECAP: An Architecture for Belief Revision in LLM Agents

RECAP is an adapter-level addition to a frozen decoder-only backbone. It adds 41 million trainable parameters to a 13 billion parameter model, which is 0.31 percent overhead. It consists of five components operating during decoding, plus one training objective. We describe each in turn.

Belief Commitment Detector

Not every generated token represents a commitment. Deliberative text, hedged speculation, and restatement should not enter the dependency graph. The Belief Commitment Detector segments the generated stream into belief units, meaning contiguous spans that assert something the agent will subsequently rely on.

The detector is a two-layer bidirectional GRU over residual stream activations taken from layer 27 of 40. We chose that depth empirically. Probes at earlier layers tracked surface syntax, and probes at later layers had already collapsed toward next-token prediction. The detector emits BIO span labels and was trained on 46,000 human-validated span annotations.

We rejected an alternative design in which the model emits explicit belief delimiter tokens. That approach requires the backbone to learn a new output convention, which degraded fluency in early experiments. Passive detection from activations leaves the generation distribution untouched.

Dependency Indexed Belief Cache

Each detected belief unit is written into the Dependency Indexed Belief Cache. The cache entry for belief unit b is a tuple containing four fields:

1. A summary vector s_b of dimension 256, produced by projecting the mean residual write vector across the unit's tokens through a learned matrix W_s.

2. A support set S(b), which is the set of prior belief indices on which this unit causally depends, populated by the justification probe.

3. A validity scalar v_b in the interval zero to one, initialised at one and reduced by retraction propagation.

4. A token span pointer allowing the retraction gate to address the unit's key value entries directly.

The cache holds 512 belief units, which occupy 0.26 megabytes in bfloat16 per trajectory. This is negligible against the key value cache itself. Eviction is least recently justified rather than least recently used, which preserves foundational assumptions that are rarely restated but widely depended upon.

The Justification Probe and Causal Distillation

The justification probe is the technical centre of this work on belief revision in LLM agents. It estimates, for any pair of belief units, the causal dependence of the later on the earlier. The score is a low-rank bilinear form over cache summary vectors.

Formally, we compute J(b_i, b_j) equal to the sigmoid of the quantity s_i transpose U V transpose s_j divided by the square root of r. Here U and V are learned matrices of shape 256 by r, with rank r set to 32. The asymmetry of U and V is deliberate. Dependence is directional, and a symmetric form conflates support with mutual topical similarity.

The probe is trained by distillation from causal interventions. We generated 180,000 traces and, for each candidate pair, performed resample ablation on the earlier belief span. The measured KL divergence in the later belief's token distribution, min-max normalised per trace, becomes the regression target. The probe is trained with a binary cross-entropy loss against this soft target.

This distillation is what makes the approach practical. A direct causal measurement at inference time requires one forward pass per candidate premise. Our probe requires a single bilinear product over cached vectors. We measured the probe at approximately 340 times cheaper than online ablation, while reaching Spearman correlation of 0.71 against causal ground truth.

Retraction Gate and Transitive Invalidation

When a new observation enters the context, a Contradiction Scorer evaluates it against every valid cache entry. The scorer is a bilinear natural language inference head over summary vectors, trained on contradiction pairs drawn from our synthetic generator and from standard entailment corpora.

If contradiction confidence exceeds the threshold tau, set at 0.35, the Retraction Gate fires. It sets the contradicted belief's validity to zero. It then propagates invalidation transitively through the justification graph. A descendant's validity is reduced multiplicatively by the product of the incoming justification score and a damping factor gamma, set at 0.7.

Damping matters because justification scores are estimates and error compounds along chains. Without damping, a single confident retraction cascades through the entire graph and invalidates almost everything. We tuned gamma on a held-out split and found the useful range narrow, between 0.6 and 0.8.

Critically, retracted beliefs are not deleted from the key value cache. Deletion breaks positional structure and destroys the record that a hypothesis was tried and failed. Instead, we add a learned retraction embedding of dimension 5120 to the cached key vectors of the affected span. This suppresses attention to the retracted content while preserving its trace, and it lets the model avoid rederiving the same failed branch.

The Retraction Consistency Objective

The gate manipulates attention, but the backbone must learn to respond to that manipulation. We train this with the Retraction Consistency Objective, a contrastive loss over matched trajectory pairs.

Each pair consists of two trajectories identical up to a divergence point, where one receives a contradicting observation, and one does not. The objective has two terms. The sensitivity term penalises tokens whose logit distributions remain invariant across the pair when the justification graph says they depend on the retracted belief. The stability term penalises logit change for tokens with no dependency path to the retraction.

Both terms are symmetric KL penalties with a margin of 0.15 nats. The full training loss is a weighted sum of standard language modelling loss, probe distillation loss, and the retraction consistency objective, with weights 1.0, 0.4, and 0.25. We trained in three stages. Stage one trains the detector and probe with the backbone frozen. Stage two adds LoRA adapters at rank 64 with the retraction objective active. Stage three anneals on mixed clean and contradiction trajectories to prevent over-retraction.

Experimental Setup

Evaluating belief revision requires knowing ground truth dependency structure, which natural corpora do not provide. We therefore built a controlled generator alongside adapted versions of existing agent benchmarks.

The CASCADE Generator

CASCADE, our Contradiction Augmented Sequential Curriculum for Agent Dependency Evaluation, procedurally generates planning environments with injected contradictions. It produced 240,000 trajectories for training and 18,000 held out for evaluation.

Each generated instance controls four variables independently:

1. Dependency depth, ranging from one to six hops between the falsified premise and the affected subgoal.

2. Retraction latency, ranging from two to forty decoding steps between belief commitment and contradicting observation.

3. Contradiction explicitness, spanning direct negation, numeric inconsistency, and pragmatic implicature.

4. Distractor density, meaning the number of unrelated beliefs committed between the premise and its contradiction.

We also evaluate on two adapted external suites. ALFWorld-CR injects environment state contradictions into household task trajectories. WebArena-CR injects page state changes that falsify earlier navigation assumptions. These test whether gains on synthetic non-monotonic reasoning benchmarks transfer to realistic long-horizon agent planning.

Baselines and Metrics

We compare against six baselines. These are the unmodified backbone with chain of thought, a ReAct-style tool loop, a Reflexion-style self-critique loop, full replanning on detected contradiction, an attention rollout dependency tracker with the same gate, and a prompted symbolic truth maintenance scaffold in which the model maintains a textual justification table.

Our four primary metrics are as follows. Stale commitment rate measures the fraction of final plans containing at least one belief supported only by a falsified premise. Retraction recall measures the fraction of genuinely dependent beliefs correctly invalidated. Retraction precision measures the fraction of invalidated beliefs that genuinely depended on the falsified premise. Recovery cost measures token overhead relative to a contradiction-free run.

Computation and Implementation

All experiments used a 13B decoder-only backbone with 40 layers and hidden dimension 5120. Training ran on four nodes of eight NVIDIA H100 80GB GPUs, consuming approximately 2,300 GPU hours in total. We used PyTorch 2.4 with FSDP sharding and FlashAttention-2, and vLLM 0.6 for evaluation serving. Every reported number is the mean of three seeds, and seed variance on stale commitment rate stayed under 1.4 percentage points.

Results and Analysis

RECAP reduces stale commitment rate from 61.4 percent to 17.9 percent on the CASCADE hard split, a relative reduction of 70.8 percent. Retraction recall rises from 0.41 for the attention rollout tracker to 0.86, with retraction precision at 0.79. Task success on the same split improves from 34.2 percent to 58.7 percent.

Transfer to realistic environments is positive but smaller. On ALFWorld-CR, task success moves from 41.8 percent to 55.1 percent. On WebArena-CR, the gain is more modest, from 22.6 percent to 31.4 percent. We attribute the smaller web gain to contradiction detection difficulty rather than to retraction failure, a point we return to in limitations.

The efficiency comparison is the practically important result. Full replanning reaches a slightly better stale commitment rate of 12.3 percent but consumes 4.7 times the tokens of a clean run. RECAP achieves 17.9 percent at 1.19 times token cost, with 6.8 percent wall clock latency overhead. For production long-horizon agent planning, that tradeoff strongly favours targeted retraction.

Ablation Analysis

We ablated each component to isolate its contribution. All figures are stale commitment rate on the CASCADE hard split, where full RECAP scores 17.9 percent.

1. Replacing the justification probe with attention rollout raises stale commitment rate to 44.6 percent, confirming that the dependency signal is the largest single contributor.

2. Disabling transitive propagation, so that only directly contradicted beliefs are retracted, raises it to 38.2 percent.

3. Removing the retraction consistency objective raises it to 29.7 percent, showing that gate manipulation alone is insufficient without trained response.

4. Replacing the learned retraction embedding with hard deletion from the key value cache raises it to 24.1 percent and reduces precision to 0.61.

The ordering is informative. Dependency estimation quality dominates everything else. A truth maintenance mechanism with a poor dependency signal is close to useless, which explains why prior scaffolding approaches underperform despite implementing correct retraction logic.

The Confident Monotonicity Finding

Our most counterintuitive result concerns model scale. We measured spontaneous retraction recall, meaning retraction without any RECAP machinery, across three backbone sizes. Recall was 0.47 at 7B, 0.44 at 13B, and 0.39 at 70B.

Larger models retract less — a challenge we actively solve through our custom AI agent development that incorporates advanced belief revision mechanisms.

Inspecting traces, the mechanism appears to be increased confidence in prior derivations. The 70B model produces more elaborate reconciliations that preserve both the falsified premise and the new observation. It is a better reasoner and a worse revisor. We call this confident monotonicity, and it suggests that belief revision in LLM agents will not be solved by scale alone.

Where RECAP Fails

Two failure modes are worth reporting honestly. First, performance degrades sharply beyond dependency depth six, where retraction recall falls to 0.52. Damped multiplicative propagation attenuates signal along long chains, and estimation error compounds.

Second, over retraction is more damaging than under retraction in interactive settings. When we lowered tau to 0.15 to raise recall, 8.3 percent of runs entered thrash loops. The agent retracted a belief, rederived it, retracted it again, and failed to terminate. Precision matters more than recall when the agent is acting rather than only reasoning — a principle central to our enterprise AI solutions.

Discussion and Implications

The most important thing our results reveal is that dependency structure is already latent in transformer activations. It is simply not readable from attention weights. The justification probe recovers a Spearman correlation of 0.71 against causal ground truth using 256-dimensional summaries and rank 32 matrices. That is a small amount of machinery to extract something the field has largely assumed unavailable.

This reframes how we think about interpretability tooling in production systems. Causal ablation is normally treated as an offline analysis method, too expensive for the inference path. Our distillation result suggests a general pattern — much like recent breakthroughs in LLM context compression that also move expensive techniques into efficient runtime operations. Expensive causal measurements can be amortised into cheap probes and moved into the runtime loop.

For practitioners building agentic systems, the practical implication is specific. Contradiction handling should be decoupled into detection and propagation, and these should be evaluated separately. Our WebArena-CR results show a system can retract correctly and still fail because it never noticed the contradiction. Most production agent failures we have investigated at KriraAI are detection failures misdiagnosed as reasoning failures.

The confident monotonicity finding carries a broader warning. Capability benchmarks reward models for producing coherent derivations. Nothing in standard pretraining or preference optimisation rewards a model for abandoning a derivation it has already committed to. Revision capability may therefore diverge from reasoning capability as models scale.

We also think this connects to a longstanding question about neurosymbolic integration. The symbolic community solved truth maintenance decades ago but had no way to obtain dependency structure from a neural substrate. Our work suggests the missing piece was never the logic. It was the dependency extraction.

Limitations and Future Work

RECAP depends on detecting contradictions, and our Contradiction Scorer is imperfect. It achieves 0.81 recall on explicit contradictions but misses roughly 34 percent of pragmatic and implicit ones. In web environments, where contradiction often manifests as an absent element rather than a stated negation, this is the binding constraint.

The approach also assumes beliefs are linguistically segmentable spans. Beliefs held implicitly, never asserted in the generated trace, are invisible to the Belief Commitment Detector. We have no current mechanism for revising an assumption the model never wrote down.

Our validity scalar is functionally close to binary. Genuine degree of belief revision, where evidence shifts confidence without eliminating it, is not supported. Extending the gate to Bayesian-style updates over cache entries is an open design problem.

Cross-family transfer is weaker than we would like. The probe trained on our 13B backbone reaches a Spearman correlation of only 0.58 when transferred to a different model family without retraining. Dependency geometry appears to be partly architecture-specific.

We are pursuing four directions. These are contradiction detection from environment observations rather than text, probe architectures robust to dependency depth beyond six, graded confidence revision, and multi-agent settings where beliefs originate from other agents with differing reliability.

Conclusion

This research makes three contributions we consider significant. The first is a problem insight, namely that stale premise propagation is a distinct and measurable failure mode in long-horizon agent planning, separable from general reasoning weakness and worsening with dependency depth and retraction latency. The second is methodological, namely that causal dependency can be distilled from expensive ablation measurements into a rank 32 bilinear probe running at roughly 340 times lower cost. The third is our central empirical finding, a reduction in stale commitment rate from 61.4 percent to 17.9 percent at 1.19 times token cost.

The confident monotonicity result is the one we expect to matter most over time. If revision capability does not improve with scale, then belief revision in LLM agents is not a problem that waits for the next generation of models. It requires architectural attention now, and it requires evaluation suites that measure retraction rather than only derivation.

This work is one thread in KriraAI's ongoing applied research program. We investigate problems that surface in real enterprise deployments and then pursue them to research depth rather than patching them at the prompt layer. The stale premise problem reached us through agent failure analysis on client systems, and it turned into six months of architectural work. That path from production symptom to research contribution is how we prefer to operate at KriraAI.

We publish these findings openly because we think the field benefits from more honest reporting of agent failure modes. If you are working on non-monotonic reasoning benchmarks, justification graph attention, or truth maintenance in neural systems, we would value the exchange. Researchers who disagree with our dependency estimation approach are especially welcome to say so, and teams building production agents who want to discuss these failure modes against their own traces can reach the KriraAI research group directly.