The logic of KM belief update is contained in the logic of AGM belief revision
| Authors | Giacomo Bonanno |
| Year | 2026 |
| Field | AI / Agents |
| arXiv | 2602.23302 |
| Download | |
| Categories | cs.AI, cs.LO |
Abstract
For each axiom of KM belief update we provide a corresponding axiom in a modal logic containing three modal operators: a unimodal belief operator , a bimodal conditional operator > and the unimodal necessity operator . We then compare the resulting logic to the similar logic obtained from converting the AGM axioms of belief revision into modal axioms and show that the latter contains the former. Denoting the latter by \mathcal L_{AGM} and the former by \mathcal L_{KM} we show that every axiom of \mathcal L_{KM} is a theorem of \mathcal L_{AGM}. Thus AGM belief revision can be seen as a special case of KM belief update. For the strong version of KM belief update we show that the difference between \mathcal L_{KM} and \mathcal L_{AGM} can be narrowed down to a single axiom, which deals exclusively with unsurprising information, that is, with formulas that were not initially disbelieved.
Engineering Breakdown
Plain English
This paper establishes a formal logical relationship between two competing frameworks for how AI agents update their beliefs when encountering new information: KM (Kripke-Montague) belief update and AGM (Alchourrón-Gärdenfels-Makinson) belief revision. The authors translate both frameworks into modal logic expressions using three operators (a belief operator B, a conditional operator >, and a necessity operator □) and prove that AGM's logical axioms subsume KM's axioms—meaning every valid statement in KM logic is also provable in AGM logic. This shows that AGM belief revision is actually a generalization of KM belief update rather than an alternative approach. The work provides a rigorous mathematical foundation for understanding how these two competing theories relate to each other at the logical level.
Core Technical Contribution
The core novelty is a formal proof that AGM belief revision subsumes KM belief update at the logical level by translating both frameworks into a unified modal logic language. Rather than treating these as separate incompatible theories, the authors show that KM's axioms translate to theorems within the AGM framework (L_KM ⊆ L_AGM), establishing a strict containment relationship. This is achieved by carefully mapping each KM axiom to corresponding modal logic axioms and demonstrating that every KM-valid statement can be derived from AGM axioms. The paper also addresses the strong version of KM belief update, showing how the differences emerge and are characterized within the AGM framework. This represents a significant theoretical unification that clarifies the mathematical relationship between two fundamental approaches to belief dynamics in multi-agent systems.
How It Works
The paper begins by taking each axiom from KM belief update theory and translating it into an equivalent statement in modal logic using three key operators: B for 'the agent believes', > for material conditional (if-then relationships between beliefs), and □ for logical necessity. This creates a logical system L_KM. Simultaneously, the authors perform the same translation process on AGM belief revision axioms, producing a separate logical system L_AGM. The comparison then proceeds by formal logical proof: the authors systematically show that for every axiom or theorem in L_KM, there exists a corresponding derivation within L_AGM. This proof technique involves showing that AGM's richer axiomatization (which governs how beliefs change when new information arrives) can express and encompass all the constraints that KM imposes. The key insight is that AGM's framework is more general because it can handle additional constraints and relationships that KM's framework doesn't explicitly require, making KM a special case or restricted version of AGM.
Production Impact
For engineers building belief-update systems in autonomous agents, dialogue systems, or knowledge management platforms, this paper clarifies which theoretical framework to implement. If you're building a multi-agent system, you can now confidently base your belief-update logic on AGM principles knowing that it will preserve all the guarantees that KM-based approaches provide while offering additional expressiveness and flexibility. This means a single AGM-based implementation can handle both KM-style belief updates and more complex scenarios without requiring separate code paths or different engines. The practical implication is that teams should standardize on AGM belief revision for new systems, as it's a strict superset—you get KM's guarantees for free while gaining additional capabilities. However, the computational cost of implementing full AGM logic (which is more expressive) may be higher than a minimal KM implementation, so for extremely resource-constrained systems (embedded agents, edge devices), this trade-off should be evaluated carefully.
Limitations and When Not to Use This
The paper operates entirely at the logical/theoretical level and does not address computational complexity—implementing AGM belief revision in actual code may be significantly more expensive than KM update in terms of CPU cycles, memory, or query time. The work assumes classical logic and formal axiomatization, which means it doesn't apply to probabilistic belief systems, fuzzy logic, or approximate reasoning that real-world applications often use. The paper doesn't provide empirical comparisons or benchmarks showing how AGM versus KM performs on actual agent decision-making tasks or whether the theoretical unification translates to practical advantages. Additionally, the result only shows that AGM subsumes KM logically—it doesn't prove that KM's practical or computational properties are preserved when implemented via AGM's framework. The incomplete abstract (ending mid-sentence) suggests the full treatment of strong KM belief update may reveal additional nuances that aren't captured in this summary.
Research Context
This work sits at the intersection of modal logic, epistemic logic, and multi-agent systems theory. It builds on decades of research: KM belief update originates from Kripke semantics and Montague's approach to possible worlds, while AGM belief revision grew from work by Alchourrón, Gärdenfels, and Makinson in the 1980s on rational belief change. The paper contributes to a long-standing debate about which framework better captures how agents should revise their beliefs when receiving new information—a foundational question in AI reasoning systems. By establishing the logical containment relationship L_KM ⊆ L_AGM, the work provides theoretical closure to this debate by showing these aren't competing frameworks but rather nested ones. This opens research directions into understanding what additional constraints or properties AGM axioms enforce beyond KM's requirements, and whether there are practical scenarios where KM's minimalist approach offers advantages despite its logical limitations.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::