Comparison of the Rete and Treat Production Matchers for Soar

P. Pandurang Nayak, Anoop Gupta, Paul S. RosenbloomAAAI 1988

This paper, originally presented at AAAI-88, provides a classic deep dive into the "space-time tradeoff" of production system matchers. While the TREAT algorithm was once hailed as a more efficient successor to the venerable RETE algorithm, Nayak, Gupta, and Rosenbloom demonstrate that for complex cognitive architectures like Soar, the old guard (RETE) still holds the crown.

The Challenge of Production Matching

In rule-based AI systems (production systems), the "match" phase—finding which rules apply to the current state of memory—is the primary computational bottleneck, often consuming over 90% of execution time. For years, the RETE algorithm was the industry standard. It utilizes a dataflow network to save intermediate match results (state) in "beta memories" to avoid redundant work when memory changes.

The Rete network structure uses alpha and beta memories to store intermediate results, reducing redundant computation.

However, the TREAT algorithm challenged this paradigm, arguing that the overhead of maintaining that state was too high. TREAT suggested that recomputing matches from scratch using a "seed" change was faster for many programs. This paper investigates whether TREAT’s supposed superiority holds up in Soar, a sophisticated cognitive architecture that utilizes rules differently than the simpler OPS5 systems previously studied.

Comparative Methodology

The authors conducted a head-to-head comparison between RETE and two versions of TREAT (one using static join ordering and one using dynamic ordering). To ensure a fair comparison independent of specific hardware or low-level coding optimizations, they used a hardware-independent metric: total token changes.

A "token" represents a partial match of a rule. By counting how many tokens are generated or deleted, the authors could measure the fundamental "work" each algorithm performs. They also measured actual execution time per token to account for implementation overhead across four distinct Soar programs: Eight Puzzle (EP), Missionaries and Cannibals (M&C), R1-Soar (expert system configuration), and Neomycin-Soar (medical diagnosis).

Key Insights: Why Rete Prevails

The study identified several architectural reasons why RETE outperforms TREAT within the Soar environment:

The Long Chain Effect

Soar rules are significantly "deeper" than standard OPS5 rules, averaging 9 condition elements per rule versus 3. In TREAT, every time a rule fires, the algorithm must re-join the entire chain of conditions. In RETE, because intermediate joins are stored, only the "delta" (the change) is processed through the network.

RETE processes changes incrementally through the network (a), while TREAT must recompute the entire join chain (b) for every update.

Static and Monotonic Structures

Soar frequently matches against "static" structures (like a goal description that never changes) or "monotonic" structures (knowledge added but never removed). RETE matches these once and saves the result. TREAT, lacking memory of intermediate joins, must re-match these static structures every time a related piece of memory changes.

The Cost of Flexibility

TREAT allows for dynamic join ordering, which theoretically finds the most efficient path to a match. However, the authors found that the computational overhead of calculating this order at runtime (between 21% and 41% of total match time) often outweighed the benefits.

Results and Performance

The empirical data strongly favored RETE in the context of Soar:

  • Workload: In almost all cases (except the tiny Eight Puzzle), RETE generated significantly fewer token changes. For the largest system, Neomycin-Soar, RETE produced ~80,000 token changes, while TREAT with dynamic ordering produced ~134,000.
  • Execution Speed: RETE was consistently faster per token change (1.77ms to 3.11ms) compared to TREAT (4.82ms to 8.06ms).
  • Combinatorial Joins: TREAT is more susceptible to "combinatorial explosions" during recomputation. Because RETE stores results, it only performs an expensive combinatorial join once; TREAT might re-perform it multiple times.

Conclusion

While TREAT might be superior in systems with very short rules or extremely high "deletion" rates—where memory is cleared so often that storing state becomes a liability—it fails to match RETE's performance in complex architectures like Soar. The authors suggest that the ultimate matcher might be a hybrid approach (jokingly referred to as "TRETE"). This hypothetical algorithm would analyze rules at load time and decide, rule-by-rule, whether it is more efficient to save the state (RETE-style) or recompute it (TREAT-style).

Summary updated

BibTeX
@inproceedings{nayak1988comparison,
  author = {P. Pandurang Nayak and Anoop Gupta and Paul S. Rosenbloom},
  title = {{Comparison of the Rete and Treat Production Matchers for Soar}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure