TL;DR
This paper tackles the problem of combinatorial explosion in AI production systems, specifically in Soar, by proposing a framework to systematically explore alternative "production system formulations." They demonstrate that while the "unique-attribute" formulation is optimal under certain conditions, new, more efficient formulations emerge when considering "tokenless match" algorithms, suggesting a promising direction for real-time AI.
What Problem Does This Paper Address?
Modern AI systems, particularly those aiming for real-time performance and complex reasoning, often rely on "production systems." These systems use a set of rules (productions) to process data (working memory). A critical bottleneck in these systems is the "production match" – the process of finding which rules apply to the current data. In systems like Soar, this matching process can become computationally intractable (combinatorial) due to factors like "multi-attributes" (where a single attribute can have multiple values). This combinatorial explosion prevents real-time operation, leads to inefficiently learned rules ("expensive chunks"), and hinders parallelization. The authors aim to find production system formulations that guarantee a polynomially bounded match complexity, meaning the computation time grows predictably with the problem size, not exponentially.
Methods
The core of the paper is the introduction of a framework for systematically generating and evaluating alternative production system formulations. This framework is built upon identifying independent dimensions that define how working memory elements (data) and production conditions are structured.
Key dimensions identified include:
- Forward-attribute: Restrictions on the number of attributes for a given identifier.
- Values-per-attribute: Restrictions on the number of values for a given attribute (this is where "multi-attributes" come in).
- Reverse-attribute: Restrictions on the number of attributes for a given value.
- Identifiers-per-attribute: Restrictions on the number of identifiers for a given attribute.
The authors then introduce a novel concept: tokenless match. Unlike traditional "token match" (where a token represents a specific combination of variable bindings), tokenless match focuses on finding consistent bindings for each variable independently. This is mapped to the well-understood problem of constraint satisfaction. By combining these dimensions with the tokenless match, new formulations emerge.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and a framework for evaluation, using examples from Soar's existing tasks and a hypothetical "grid task" for illustration.
Key Insights and Ideas
- The power of a systematic framework: Instead of ad-hoc exploration, the paper provides a structured way to think about and generate production system formulations by breaking them down into independent dimensions. This significantly reduces the search space for optimal formulations.
- Trade-off between expressiveness and efficiency: The paper highlights a fundamental trade-off: restricting the expressiveness of the production system (e.g., by disallowing multi-attributes) can lead to significant gains in match efficiency.
- Tokenless match as a game-changer: The introduction of tokenless match, inspired by constraint satisfaction, unlocks new possibilities. It allows for polynomially bounded match even with unrestricted working memory, provided productions are "tree-structured" (i.e., no equality tests across value fields).
- Unique-attributes are not always best: While the "unique-attribute" formulation (which disallows multi-attributes) is shown to be optimal within the traditional token-based match, the advent of tokenless match creates scenarios where other formulations, like the "unrestricted-tree formulation," can outperform it.
- Generality of the framework: The paper demonstrates the framework's generality by showing how even a seemingly different paradigm like marker passing systems can be mapped onto one of the generated formulations, suggesting broad applicability.
Key Results
- The "unique-attribute" formulation is identified as the best possible formulation within the investigated dimensions, assuming a traditional token-based match. This formulation achieves a linear bound on match complexity.
- The introduction of "tokenless match" allows for new formulations, such as the "unrestricted-tree formulation," which can satisfy absolute requirements (polynomial bound, closure under chunking, correctness) even with unrestricted working memory, provided productions are tree-structured.
- The paper suggests that the "unrestricted-tree formulation" might outperform unique-attributes in terms of chunk generality and avoid the "expensive chunk" problem, though this requires further empirical validation.
Limitations and Future Work
- Empirical validation: While promising, the paper acknowledges that the implementation and evaluation of these new formulations on actual tasks are ongoing and represent key future work.
- Expressive adequacy of new formulations: The paper notes that while tokenless match can improve efficiency, it might require productions to be written in a "fairly different manner," and the full extent of this impact on expressive adequacy needs further investigation.
- Exploring other consistency algorithms: The paper hints at further possibilities by mentioning that more constraining consistency algorithms than arc-consistency could be used with tokenless match, potentially leading to formulations that perform better on expressive adequacy but require higher polynomial bounds.
- Generalizability beyond Soar: While the framework is presented as relevant to other rule-based systems, further work is needed to demonstrate this explicitly.
Summary updated