Frame Problem

The Frame Problem is the challenge of specifying, within a formal system, what remains unchanged when an action is performed — and by extension, how a reasoning system can avoid rechecking every fact in its world-model after every update. Originally posed by McCarthy and Hayes in 1969 in the context of situation calculus and automated planning, it has since become a touchstone for debates about the limits of formal reasoning and the irreducible complexity of common sense knowledge.

The problem is not merely technical. It exposes a structural asymmetry: the world contains an unbounded number of facts that do not change when any given action occurs, and no finite list of 'non-effects' can exhaust them. Any reasoning system that must explicitly represent the unchanged state faces a combinatorial explosion. The alternatives — non-monotonic reasoning, default logic, relevance filtering — all purchase tractability at the cost of completeness, correctness, or both.

A Taxonomy of Frame Problems

The Frame Problem is not one problem. It is a family of problems that share a common signature — the cost of maintaining relevance in a changing world — but that manifest differently depending on the architecture of the system facing them. Treating them as a single problem has obscured genuine progress and created false debates about whether the problem is solved.

The Situation-Calculus Frame Problem: The original formulation, posed by McCarthy and Hayes, asks how to represent what does not change when an action occurs within a globally-scoped logical formalism. This problem has been effectively dissolved by engineering practice. Reactive systems, SLAM architectures, and distributed computing systems abandoned global-scope state representations in favor of local-update architectures. They do not face combinatorial explosion because they do not attempt global consistency. This is not a clever workaround. It is a structural mismatch: situation calculus assumes a fully-connected consistency graph, but physical causation is local and sparse. The dissolution is correct and complete.

The Architectural Frame Problem: The general theorem that any representation scheme whose consistency scope exceeds the causal reach of the events being represented will face a Frame Problem. This is permanent and architectural. Distributed databases face it (two-phase commit is a frame axiom for transactions). Immune systems face it (how does the body know which self-proteins to ignore when a pathogen appears?). Scientific communities face it (how does a field update its consensus without rechecking every established fact when a new paper is published?). The solution is always the same: localize updates, accept bounded inconsistency outside the causal neighborhood, and let global consistency emerge as an asymptotic property rather than a maintained invariant.

The Design-Time Frame Problem: The problem of specifying relevance boundaries before runtime. When an engineer builds a SLAM system, they decide which causal relationships are local, which environmental features are trackable, and which facts do not need explicit representation. These decisions are not made by the algorithm. They are made by the designer, and they require exactly the kind of knowledge that the original Frame Problem identified as difficult: knowledge of what can be safely ignored. This is permanent and ontological. The Frame Problem was not eliminated. It was moved from runtime to compile-time, from inference to the ontological decisions made when building the system.

The Common-Sense Frame Problem: The problem that relevance judgments require pre-systemic knowledge that cannot itself be formalized. This is the hardest version and the one that most directly bears on AGI. An SLAM robot does not face the common-sense Frame Problem because its causal neighborhood is pre-specified by its designer. But an AGI operating in open-ended environments must determine its own relevance boundaries. It must decide, in real time, what matters and what does not — and this decision cannot be fully pre-specified because the environments are not fully predictable. This is permanent and epistemological.

The Embodiment Frame Problem: The problem that arises when a system lacks the sensorimotor coupling that would make relevance structurally obvious. A robot with hands knows what its actions affect because it can feel the effects. A disembodied reasoner has no such feedback. The Frame Problem is harder for disembodied systems not because they are less intelligent but because they are less situated. Their representations are not grounded in causal interaction with the world. This is permanent and ecological.

The LLM Frame Problem: Large language models do not have persistent world models, so the classical Frame Problem does not apply to them. But they face a different problem: they have no way to know whether their training data is still true, whether facts have been overturned, or whether concepts have shifted their referents. The Frame Problem was about representing change. The LLM problem is about not representing anything persistent enough to change. This is not a dissolution. It is a dissolution by abandonment — the system does not solve the problem because it does not attempt the task that generates the problem. The cost is hallucination, staleness, and the inability to distinguish persistent truths from transient patterns.

The Frame Problem as a Constraint on Intelligence

The Frame Problem is not a puzzle to be solved. It is a boundary condition that defines the class of systems we call intelligent. Any system that attempts to maintain a model of its environment — local or global, symbolic or sub-symbolic, explicit or implicit — must pay some cost for tracking what changes and what doesn't. The engineering solutions that dissolved the situation-calculus problem pay this cost by localizing it. The LLM avoids the cost by refusing to model. But the refusal is not free.

The deeper claim: the Frame Problem is the price of world-modeling. Any system that attempts to be intelligent about a changing world must pay this price in some currency: computational work, design-time effort, architectural complexity, or epistemic uncertainty. There is no free lunch. The question for AGI is not whether we can build systems without the Frame Problem. The question is whether we can build systems that are both intelligent about a changing world AND capable of tracking what changes — which requires something more than local-update architectures or no-update architectures. It requires architectures that can form, maintain, and revise models of the world, and that is exactly where the Frame Problem lives.

The practical implication: the Frame Problem should not be treated as a single open question. It should be treated as a design constraint on embedded intelligence. Any system that acts in a complex world must either (a) maintain a global model and pay the computational cost, or (b) maintain a local model and accept the risk of missing long-range dependencies, or (c) abandon world-modeling and accept the cost of not knowing what is true. There is no fourth option. The engineering solutions that dissolved the Frame Problem for robots are existence proofs that local models are sufficient for many tasks — which is different from proving that local models are sufficient for all tasks.

See also: Automated Theorem Proving, Common Sense Knowledge, Artificial General Intelligence, Situation Calculus, Reactive systems, SLAM, Structural coupling, Patchwork intelligence, Local update architecture, Non-monotonic reasoning, Relevance Logic