CORGI: Efficient Pattern Matching With Quadratic Guarantees

AI summary

Overview

Research area: Symbolic AI / knowledge-based systems — specifically pattern matching algorithms for production rule systems (forward-chaining rule engines) used in cognitive architectures and database querying.

Technical level: Advanced. The paper assumes familiarity with production systems, the RETE algorithm, alpha/beta memories, partial matches, working memory elements, and asymptotic complexity analysis.

Scope: The paper introduces CORGI (Collection-Oriented Relational Graph Iteration), a matching algorithm with quadratic time and space guarantees for finding single satisficing matches, and compares it against RETE implementations in OPS5 and SOAR on a combinatorial matching task.

What This Paper Is About

Production systems that use RETE-based matching can blow up exponentially — O(N^K) in time and memory, where N is working memory size and K is the number of literals in a rule's preconditions — when rules contain many underconstrained variables or produce combinatorial intermediate partial matches. This is manageable for hand-written rules using knowledge-engineering tricks, but when AI systems automatically induce or synthesize rules (for example through aggressive anti-unification-based generalization), worst-case patterns appear routinely and can slow or halt execution. CORGI eliminates RETE's beta-memory of accumulated partial matches by maintaining a grounded relation graph in a forward pass and generating matches on demand by iterating backward through that graph.

Key Contributions

1. A new matching algorithm, CORGI, that never commits partial matches or full conflict sets to memory. Maintaining the relation graph and selecting a next match is O(KN^2), where K is the number of objects in the matching pattern and N is the size of working memory.

2. A two-pass architecture with bounded memory: a forward pass builds and maintains a graph of grounded relations where each beta-node only stores a mapping M(a_i) → {b_0, …, b_n} between satisficing pairs of bindings (quadratic at most), and edges carry only collections of WME identifiers — never combinatorially expanded sets.

3. A backward-pass iterator (Relational Graph Iteration) that streams matches on demand starting from terminal nodes, so systems can determine that matches exist before instantiating them all explicitly, avoiding the high-latency delays and memory overflows of populating full conflict sets.

4. An empirical comparison against RETE in OPS5 and SOAR, demonstrating that CORGI completes in milliseconds a task where RETE-based implementations take seconds or crash.

Main Findings

• Match phase dominates runtime: In RETE-based production systems, the match phase can consume 90 percent or more of typical runtime (citing Forgy, 1981).

• RETE's worst case is exponential: Almost all variations of RETE scale as O(N^K) in memory and time. The paper's toy example: with N=100, K=5, and 8-byte addressing, RETE has a memory overhead of at least (5 * 8 bytes) * 100^5 = 400 GB.

• Collection-oriented RETE only partially helps: It alleviates combinatorial explosions only when collections within a match entry are fully unconstrained. If uniqueness conditions such as AND(A.id != B.id, B.id != C.id, A.id != C.id) are imposed, its beta-memory entries "fragment" and it suffers the same worst-case combinatorial memory requirements as regular RETE. The authors could not locate a collection-oriented RETE implementation for comparison.

• CORGI is under 2 milliseconds across the Valentine's task variants: In the evaluation, CORGI is considerably faster than RETE and completes the matching task in 2 milliseconds or less for all numbers of Valentines tested.

• OPS5 crashes, SOAR stalls: The OPS5 implementation takes 3.0 milliseconds at 1 Valentine, but a full 2.0 seconds at 3 Valentines, and fails completely with a memory overflow at 4 Valentines. SOAR's RETE implementation takes 3 ms, 800 ms, and 665 seconds for 1, 2, and 3 Valentines respectively.

• Scaling with working memory size: For V=2 Valentines, OPS5 and SOAR runtimes increase dramatically as the number of objects in working memory increases, while CORGI's runtime remains quadratic. Using AIC-based model selection, a quadratic model minimized the AIC fit over a comparison of linear, quadratic, cubic, and exponential models.

• SOAR becomes impractical: At N=50 and V=4 Valentines, SOAR was left running for 10 hours before termination. SOAR is similarly unresponsive at V=2 Valentines and N=200 objects in working memory or greater.

• SOAR's memory is low but its runtime is not: Inspection of SOAR's process memory at these points showed a relatively low footprint of less than 1 gigabyte — its beta-memory implementation stores candidate matches with a much lower memory footprint than conventional RETE, but this does not translate into a practical reduction in runtime for this task.

• Enumeration is optional: If a pattern has O(N^K) matches and all must be enumerated (usually unnecessary), CORGI has the same asymptotic performance as RETE.

Methodology in Plain English

The authors replace RETE's "remember every partial match" strategy with two passes over a relation graph.

Forward pass: Unary predicates (like D.city == "Houston") and binary relations (like V1.num < E.num) are handled by different node types, with unary nodes filtering candidates before join nodes. But unlike RETE, each join node does not output sets of partial matches that grow combinatorially deeper. Each join node just keeps a mapping from one variable's bindings to the bindings of another variable that satisfy the relation. The edges between nodes store only collections of working memory element identifiers that have not been ruled out as contributing to at least one match. Rather than hash maps or binary tree maps, the implementation can use a bit matrix as a truth table for each relation over its inputs, growing by doubling along each dimension and marking removed objects' rows or columns empty for reuse. This keeps data contiguous and improves CPU cache locality.

Backward pass: Iteration begins by picking a binding from a terminal node's output collection, then follows all reachable paths backward through the node mappings to produce a full match. Variables must be assigned a strict order, which dictates graph organization, mapping direction (earlier ← later), and selection order during iteration. Natural order is the order variables appear in the pattern, but sorting variables in descending order of relation degree (the number of other variables sharing at least one relation; E in the example has degree 3) culls candidates earlier. If two nodes share a variable pair, mapping results are intersected. Separable graphs are iterated over in all combinations. CORGI returns an iterator object, not an enumeration, so production systems can ask for just the next match.

Evaluation setup: The authors use an expanded Valentine's scenario with 26 employees, 12 projects, and 12 departments (50 objects, a variation of the dataset used by Kang & Cheng, 2004), evaluate N ∈ [1,5] unique Valentines instead of one, and increase working memory by increments of 50 by duplicating the original dataset. Duplicate objects get unique identifier attributes where appropriate. They compare against RETE in OPS5 (Xiaofeng Yang's 2013 quicklisp port of the 19-OCT-92 version) and SOAR (SoarSuite 9.6.4). CORGI is implemented in Python and compiled with the Numba just-in-time compiler, as part of a larger toolset called CRE (Cognitive Rule Engine). Runtimes were measured on a Lenovo Yoga Pro 9 16IMH9 laptop with 32 GiB RAM and an Intel Core Ultra 9 185H × 22 processor. Source code is linked on GitHub.

Why This Matters

Impact on research: The paper's motivating context is online AI systems that generate rules automatically — for example, interactively teachable agents that induce rules from examples. The authors report that agents in their own prior work regularly produce challenging matching patterns as part of normal learning, and that reasonable inductive mistakes like anti-unifying two seemingly related (but actually unrelated) rules can produce highly unconstrained worst-case patterns that would quickly crash conventional RETE, as well as collection-oriented RETE. CORGI removes the requirement that a human knowledge engineer intervene to make learned rules tractable, and it imposes no functional constraints on selection between productions, so preference-based selection (SOAR) and activation-based competition (ACT-R) remain possible.

Real-world applications:

• Real-time planning and reactive control for AI agents in continuous control scenarios like robotics and games, where agents may need to decide next actions timestep by timestep, necessitating latencies of tens of milliseconds or less (Langley & Katz, 2022).
• Low-latency relational database querying: matching systems are used for retrieval, inference, and condition checking in database systems, where low-latency and low-memory-footprint algorithms reduce delays for end-users and make better use of computational resources.
• Interactive task learning systems where rules are learned or synthesized rather than hand-authored (Laird et al., 2017; Kirk & Laird, 2014; Lawley & Maclellan, 2024).
• Cognitive architectures and symbolic AI agents that test sets of complex rules simultaneously against comparatively small working memories, such as SOAR (Laird, 2019) and ACT-R (Anderson et al., 1997).

Industry relevance: Production systems are long-standing infrastructure in knowledge-based AI, and RETE is the dominant matching approach, with a lineage of optimizations including hash map-based indexing (Nayak et al., 1988), multi-threading (Gupta et al., 1988), TREAT (Miranker, 1987), and heuristics for join ordering (Ishida, 2002). CORGI's quadratic guarantees offer a predictable-performance alternative for deployments where unpredictable latency or memory exhaustion is unacceptable. Its implementation as a Python extension compiled with Numba targets modern software engineering languages rather than historical LISP-like DSLs, which the authors argue improves interoperability and rapid development.

Future Directions

• Incremental evaluation over multiple match cycles. The paper evaluates CORGI on just a single match cycle; the authors plan to evaluate its performance as it is updated incrementally over multiple match cycles as working memory is modified in full production systems, and expect similar performance benefits.

• Heuristic and activation-based biases inside the graph. Currently CORGI's match iteration order depends on the variable order in matching patterns, and later variables' iterators increment only after all candidate matches for earlier variables are exhausted. The authors conjecture there are simple and efficient ways to impose heuristic or activation-based biases on relation graphs directly, influencing which matches are generated first without sorting an enumeration — which would make heuristic or competitive activation-based execution practical even in worst-case matching scenarios.

• Weighting schemes for match selection. There is, in principle, the possibility of sorting match candidates at each iteration level to let selection criteria depend on particular objects in working memory (such as ACT-R chunks with specific retrieval costs), and of including weights over pairs of objects like connection strengths between connected chunks. The authors note that tertiary or higher-order weights would be difficult to accommodate without compromising efficiency benefits.

• Comparator for collection-oriented RETE. The authors conjecture that this task would also create high levels of fragmentation in collection-oriented RETE, leading to similar asymptotic performance as RETE, but were unable to locate a collection-oriented RETE implementation for comparison — leaving that comparison open.

Target Audience

Researchers and engineers working on production systems, cognitive architectures, and rule-based AI agents; developers of interactive task learning and program-synthesis systems whose generated rules may contain worst-case matching patterns; database researchers interested in query matching under tight latency and memory budgets; and performance-focused practitioners who need predictable matching guarantees rather than heuristically mitigated exponential blowups. Readers should already be familiar with RETE, alpha/beta memories, and working memory, as the paper's arguments are framed almost entirely in those terms.

Authors’ abstract

Rule-based systems must solve complex matching problems within tight time constraints to be effective in real-time applications, such as planning and reactive control for AI agents, as well as low-latency relational database querying. Pattern-matching systems can encounter issues where exponential time and space are required to find matches for rules with many underconstrained variables, or which produce combinatorial intermediate partial matches (but are otherwise well-constrained). When online AI systems automatically generate rules from example-driven induction or code synthesis, they can easily produce worst-case matching patterns that slow or halt program execution by exceeding available memory. In our own work with cognitive systems that learn from example, we've found that aggressive forms of anti-unification-based generalization can easily produce these circumstances. To make these systems practical without hand-engineering constraints or succumbing to unpredictable failure modes, we introduce a new matching algorithm called CORGI (Collection-Oriented Relational Graph Iteration). Unlike RETE-based approaches, CORGI offers quadratic time and space guarantees for finding single satisficing matches, and the ability to iteratively stream subsequent matches without committing entire conflict sets to memory. CORGI differs from RETE in that it does not have a traditional $β$-memory for collecting partial matches. Instead, CORGI takes a two-step approach: a graph of grounded relations is built/maintained in a forward pass, and an iterator generates matches as needed by working backward through the graph. This approach eliminates the high-latency delays and memory overflows that can result from populating full conflict sets. In a performance evaluation, we demonstrate that CORGI significantly outperforms RETE implementations from SOAR and OPS5 on a simple combinatorial matching task.