Introduction
Logical reasoning has long been a cornerstone of artificial intelligence, yet its computational demands have historically limited its application in real-time or large-scale systems. This paper introduces Inference Graphs, a novel architecture designed to bring concurrent processing to symbolic logic. By integrating three previously distinct methodologies—Truth Maintenance Systems (TMS), RETE networks, and Active Connection Graphs (ACG)—the proposed system enables high-speed, bi-directional natural deduction that scales effectively across modern multi-core processors.
The Challenge: Logic in the Multi-Core Era
Since the 1980s, the parallelization of logical reasoning, particularly in languages like Prolog, has proven notoriously difficult. While modern hardware has transitioned toward multi-core architectures, most "large-scale" inference research has pivoted toward statistical methods optimized for GPUs. However, GPUs are fundamentally ill-suited for the symbolic and structural logic required for complex AI tasks.
Furthermore, many traditional theorem provers rely on "refutation"—proving a statement by demonstrating that its negation leads to a contradiction. While effective for specific proofs, refutation-based systems often discard intermediate work. This paper advocates for a natural deduction approach, where derived formulas are retained in a Knowledge Base (KB) for future reuse. The primary challenge lies in creating a system that supports forward, backward, and bi-directional reasoning while maintaining "truth maintenance"—the ability to retract beliefs and automatically propagate those changes throughout the dependency network.
Methodology: The Synthesis of Three Systems
The core innovation of Inference Graphs is the synthesis of three graph-based systems into a single propositional graph structure (derived from the SNePS family):
- Truth Maintenance Systems (TMS): These manage logical dependencies and handle the retraction of assertions, ensuring the KB remains consistent.
- RETE Networks: Borrowed from production rule systems, these are used to efficiently match patterns and manage the addition or removal of facts.
- Active Connection Graphs (ACG): These facilitate the flow of information—both forward and backward—through the graph.
The author discovered that these three systems share deep structural commonalities when visualized. By layering them onto a single graph, the system can handle complex reasoning tasks within a unified framework.
Concurrent Execution and Heuristics
Rather than attempting to force a rigid parallel algorithm onto hardware, the system treats inference as a series of concurrent tasks. The graph is partitioned into "inference segments" connected by "valves." When a logical message passes through a valve, it triggers the creation of a new task.
These tasks are managed via a Prioritized Task Queue. To optimize performance, the system employs specific concurrency heuristics:
- Directional Prioritization: Tasks that move "right" (toward the user's specific query) are prioritized over general forward-chaining tasks.
- Intelligent Cancellation: A critical feature of the system is the ability to cancel tasks. If a truth value is determined by one branch of the graph, the system identifies and terminates redundant tasks attempting to prove the same fact elsewhere.
Results and Performance
The system was evaluated using internal tests designed to measure the efficacy of the concurrency model and prioritization heuristics. The results highlight two major successes:
- Heuristic Efficiency: The use of "right-moving" prioritization resulted in a 10-40x speed increase compared to a standard, non-prioritized task queue.
- Scalability: By isolating the inherently sequential components of the inference process, the system achieved nearly linear speedup as the number of available processors increased.
Limitations and Future Directions
While Inference Graphs represent a significant step forward, certain logical operations remain challenging. Specifically, "negation introduction" and "proof by cases" are difficult to implement within a purely graph-based concurrent framework.
At present, the system is focused on propositional logic. The next phase of development (Stage 3) aims to extend the implementation to the Logic of Arbitrary and Indefinite Individuals. This extension is expected to significantly enhance the system's reasoning power, making it more applicable to complex domains such as cognitive robotics and information fusion.
Conclusion
Inference Graphs provide a scalable, bi-directional framework for natural deduction. By treating logical reasoning as a concurrent process and leveraging the structural overlaps between TMS, RETE, and ACGs, this approach offers a viable path for symbolic AI to leverage the power of modern multi-core computing.
Summary updated