Truth Maintenance System

A truth maintenance system (TMS) is a computational mechanism that tracks the logical dependencies between beliefs in an artificial reasoning system, enabling efficient retraction of conclusions when their supporting premises are invalidated. Unlike a simple database that stores assertions, a TMS stores justifications — records of which premises and inference rules were used to derive each conclusion. When a premise is withdrawn, the TMS propagates the retraction through the dependency graph, identifying all downstream conclusions that lose support and marking them as retracted or suspended.

The TMS architecture was developed by Jon Doyle in 1979 as part of the artificial intelligence effort to build reasoning systems that could operate in changing environments. The core insight is that non-monotonic reasoning requires not just inference rules that permit retraction, but an explicit data structure that remembers why each conclusion was drawn. Without this memory, a system that encounters contradictory information has no way to know which of its beliefs were affected.

Dependency Graphs and Retraction Propagation

A TMS represents beliefs as nodes in a directed graph and justifications as edges. A node may have multiple incoming edges (multiple supporting justifications) and multiple outgoing edges (supporting downstream conclusions). When a justification fails, the TMS checks whether the node still has other supporting justifications. If yes, the node remains believed. If no, the node is retracted, and the process propagates recursively to its children.

This propagation algorithm is the computational analog of causal intervention in a probabilistic model: removing a variable and observing which downstream variables change. The TMS is, in effect, a deterministic causal graph for the reasoning process itself. The cost of propagation is proportional to the size of the affected subgraph, which makes the TMS efficient when retractions are local and costly when they are global — a structural property that mirrors the computational complexity of belief revision in general.

The Assumption-Based TMS

The basic TMS tracks whether each node is in or out of the belief set. The assumption-based truth maintenance system (ATMS), developed by Johan de Kleer, extends this by tracking the minimal sets of assumptions under which each conclusion holds. An ATMS can answer questions like: "under what combinations of assumptions is this conclusion valid?" This makes it useful for design and diagnosis problems, where different design choices or fault assumptions produce different conclusions, and the system must explore multiple consistent scenarios simultaneously.

The ATMS has been applied to circuit diagnosis, design space exploration, and constraint satisfaction. It is the logical foundation of constraint programming systems that must backtrack efficiently when a partial solution is found to violate a constraint. The ability to identify exactly which assumptions led to a contradiction — and to explore alternative assumptions without redundant computation — is the source of the ATMS's power.

The TMS is not a peripheral bookkeeping mechanism. It is the architecture of accountable reasoning — the data structure that makes a system's beliefs traceable, contestable, and revisable. Any intelligence that cannot answer "why do you believe that?" is not reasoning; it is pattern-matching with amnesia.