Concurrent Reasoning with Inference Graphs

Daniel R. Schlegel, Stuart C. ShapiroAAAI 2013 · DOI

Abstract

Traditional logical reasoning systems often struggle to leverage modern multi-core architectures due to complex execution models and refutation-based techniques. This paper presents Inference Graphs, a novel knowledge representation framework where the graph structure itself functions as the inference engine. By integrating "channels" and "valves" into propositional graphs, the system enables concurrent, bi-directional natural deduction. Experimental results demonstrate that this approach achieves near-linear speedup on multi-core processors and significantly outperforms standard queueing strategies through specialized prioritization heuristics.

Introduction

Efficient logical reasoning on parallel hardware has remained a challenge since the early 1980s. While statistical methods have flourished on GPUs, formal logic requires handling nuances like bi-directional reasoning and belief retraction. Most existing theorem provers rely on refutation-based techniques (such as resolution), which often discard intermediate results and struggle with "disbelief"—the ability to propagate the retraction of a statement through the system. This paper addresses these gaps by introducing Inference Graphs, a system where knowledge representation and inference are unified to support concurrent natural deduction.

Methodology

Inference Graphs are built upon Propositional Graphs (specifically from the SNePS family), where every unique expression is represented as a node. The static graph is transformed into an active inference engine through the addition of several key components:

  • Channels: Paths for message flow. i-channels carry messages from antecedents (the "if" part) to rules, while y-channels carry messages from rules to consequents (the "then" part).
  • Valves: Control mechanisms on channels that open or close to direct the flow of inference toward specific queries.
  • Messages: Discrete units of information, such as I-INFER (assertion) or CANCEL-INFER (control), that propagate through the graph.
  • Concurrency Model: Reasoning is decomposed into "segments." Message passage through a valve triggers a task in a global prioritized queue, allowing multiple processors to operate on different graph segments simultaneously.
An example of an inference graph showing nodes connected via antecedent (ant) and consequent (cq) edges, illustrating the flow of logical inference.

Key Insights and Results

The core innovation of this work is that the data structure is the algorithm. Information flows through the graph like a fluid through a network of pipes. Unlike refutation systems, this natural deduction approach retains all learned information in the Knowledge Base for future use.

To optimize performance and avoid wasting CPU cycles, the authors implemented two primary heuristics:

  1. Right-to-Left Priority: Tasks closer to the target query (the "right" side of the graph) are executed first.
  2. Eager Cancellation: Redundant tasks are canceled immediately once a node's truth value is determined.

Evaluation using synthetic benchmarks of chaining entailments showed that the system achieves nearly linear speedup relative to the number of processors when ignoring intrinsically sequential logic. Furthermore, the custom prioritization heuristics proved highly effective, outperforming standard LIFO and FIFO queues by factors of 10x and 20-40x, respectively. The system also uniquely handles "disbelief" via UNASSERT messages, allowing for dynamic updates to the knowledge base.

Conclusion

Inference Graphs provide a robust framework for concurrent logical reasoning by treating the knowledge representation as the engine itself. While certain logical operations like negation introduction and proof by cases remain challenging to implement in a flow-based model, the benefits of bi-directional reasoning and parallel efficiency are significant. Future work will focus on expanding the set of supported logical rules within this concurrent architecture.

Summary updated

BibTeX
@inproceedings{schlegel2013concurrent,
  author = {Daniel R. Schlegel and Stuart C. Shapiro},
  title = {{Concurrent Reasoning with Inference Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8524},
}
Figure