Introduction
Reasoning in massive, expressive knowledge bases (KBs) like Cyc is often a "needle in a haystack" problem. Inference engines frequently get bogged down by millions of irrelevant rules, leading to "unproductive backtracking"—where a system follows a rule for minutes only to realize it is a dead end. While techniques like axiom selection and ordering heuristics exist, they are often hand-crafted and struggle with the scale of modern symbolic AI.
This paper introduces a search heuristic powered by Monte-Carlo Tree Search (MCTS) that simulates thousands of potential reasoning paths to learn which "moves" lead to answers. By applying these learned insights via a $k$-nearest neighbor ($k$-NN) approach, the researchers achieved significant performance gains, including up to a 7x speedup and nearly doubling the number of queries successfully answered within time limits.
Methodology
The proposed Simulation-Based Learning approach is inspired by techniques used in game-playing AI, such as AlphaGo. The core algorithm follows a standard MCTS loop to evaluate the utility of specific inference steps:
- Monte-Carlo Tree Search (MCTS): The system runs simulations from a given state to discover promising paths.
- Tree Policy (UCT): The Upper Confidence Bound for Trees (UCT) algorithm balances exploitation of known paths and exploration of new ones.
- Default Policy: If a simulation exceeds a depth cutoff, it falls back to Cyc’s standard engine for a fixed duration to check for reachability.
- State Representation: Search states are represented by vectors of 2,698 features, including entity types and tree depth.
- Generalization via $k$-NN: Since exact states rarely repeat in massive logic spaces, the system uses $k$-nearest neighbor to average values from similar previous states to guide the next step.
Evaluation
The study utilized the Cyc Knowledge Base, containing over 27 million assertions. Evaluation was conducted on a benchmark of hundreds of real-world queries designed to test Cyc's performance. Many of these are "difficult" queries that typically time out after 10 minutes using standard methods. The queries were divided into sets for cross-validation to ensure robust results.
Key Results and Insights
The MCTS-based approach significantly outperformed the baseline Cyc inference engine across several key metrics:
- Success Rate: In primary experiments, the baseline answered only 46% of queries within the 10-minute limit. The MCTS-guided version nearly doubled this, answering 92% of queries.
- Speedup: The system achieved up to a 7.1x speedup compared to the baseline.
- Difficulty Scaling: The most dramatic improvements occurred on the hardest queries (those taking >500 seconds), where the heuristic provided a massive boost in success.
- Parameter Sensitivity: A moderate exploration factor ($c = 10$ to $100$) was found to provide the optimal balance for finding answers quickly.
The success of this method lies in Simulation as a Teacher. Instead of manual rule-tuning, the system discovers importance through "sandbox" trials. By using $k$-NN to bridge the gap between sparse states, the algorithm produces a highly selective, asymmetric search tree that ignores irrelevant axioms that usually overwhelm provers.
Limitations and Future Work
Despite its success, the approach relies on 2,698 manually identified features. Future work aims to automate feature selection and incorporate more domain-specific knowledge into the simulations to make "random" walks more informed. Additionally, the researchers plan to test the generality of these methods across even larger and more diverse reasoning tasks to ensure the learned heuristics generalize effectively.
Summary updated