Model-Checking Memory Requirements of Resource-Bounded Reasoners

Alexandre Albore, Natasha Alechina, Piergiorgio Bertoli, Chiara Ghidini, Brian Logan, Luciano SerafiniAAAI 2006

Abstract

This paper introduces a formal framework to automatically calculate the minimum memory required for an artificial agent to prove specific logical statements. By recasting the reasoning process as a "strong planning" problem, the authors demonstrate that memory constraints do not merely slow down reasoning but can fundamentally limit an agent's capability to reach logical conclusions.

Introduction: The Reality of Resource-Bounded Reasoning

In classical logic, agents are often assumed to be "logically omniscient"—if an agent knows $A$ and $A \to B$, it is assumed to know $B$ instantaneously. However, real-world reasoning is a physical process consuming finite resources. Agents operating on low-power hardware or high-load servers have limited memory to store intermediate facts and track progress through complex proofs.

This research addresses a critical gap: how to formally verify if a resource-bounded reasoner has sufficient "mental space" to reach a conclusion. This is particularly vital for autonomous agents that must reason by cases (e.g., "If $P$ then $X$; if $\neg P$ then $Y$"), a process that requires storing pending branches in a stack, rapidly consuming available memory.

Methodology: Reasoning as a Transition System

The researchers propose a novel approach combining formal logic with automated planning:

  1. Bounded Memory Logic (BML): A new epistemic logic that explicitly tracks a "memory counter," monitoring both "active" memory and the backtracking stack.
  2. Transition Systems: The agent's state is modeled as the set of formulas currently in memory. Inference rules (e.g., Modus Ponens) or reading new facts are treated as transitions between states.
  3. Planning as Proof: Proof discovery is recast as a Strong Planning problem. Using the Model Based Planner (MBP), the system searches for a sequence of actions leading from an empty memory to the goal formula. For branching logic, the planner must find a "strong plan"—a strategy that succeeds regardless of which branch is explored.
Trace of reasoning steps showing memory and stack transitions.

Evaluation and Key Results

The framework was evaluated using synthetic benchmarks designed to test specific reasoning patterns, such as case-splitting and tautology derivations. The authors compared "store all" agents (saving everything to the stack) against "smart store" agents (selectively locking formulas).

Key findings include:

  • Automated Verification: The MBP planner successfully identified lower bounds for memory. For instance, it could prove a goal required at least 2 memory cells; with only 1, it correctly identified that no proof was possible.
  • Strategy Efficiency: "Smart" memory management significantly reduced total memory requirements compared to saving the entire state at every choice point.
  • Memory-Time Trade-off: There is a clear relationship between memory availability and proof length. Increasing memory often allows for "shortcuts" by holding more intermediate results.
Comparison of proof steps and memory requirements for different storage strategies across two test equations.

Discussion: Insights into Resource Constraints

A major insight is that logical equivalence does not imply resource equivalence. Two formulas may be semantically identical but require different memory amounts to prove, suggesting that for bounded agents, the syntax of information presentation is as critical as its semantics. Furthermore, branching is confirmed as the primary memory bottleneck due to the necessity of "locking" formulas for later use.

Conclusion and Future Work

While currently limited to propositional logic and assuming uniform formula sizes, this framework provides a foundation for verifying resource-bounded agents. Future work aims to extend this to First-Order Logic, account for actual bit-sizes of formulas, and explore multi-agent reasoning where agents must account for each other's memory constraints.

Summary updated

BibTeX
@inproceedings{albore2006model,
  author = {Alexandre Albore and Natasha Alechina and Piergiorgio Bertoli and Chiara Ghidini and Brian Logan and Luciano Serafini},
  title = {{Model-Checking Memory Requirements of Resource-Bounded Reasoners}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure