How to Perform Reasoning with Semantica's ReteEngine: A Complete Guide to Rule-Based Inference

Semantica's ReteEngine implements a classic Rete algorithm that accelerates rule-based reasoning through a network of Alpha, Beta, and Terminal nodes that incrementally propagate facts and generate rule activations.

The ReteEngine in the semantica-agi/semantica repository provides a production‑quality forward‑chaining reasoner optimized for incrementally matching large rule sets against dynamic facts. Unlike naive pattern matching that re‑evaluates all rules on every change, the engine compiles rules into a discrimination network that shares work across conditions and remembers partial matches.

This guide explains the internal architecture of the ReteEngine and demonstrates how to build networks, feed facts, retrieve matches, and execute rule conclusions.

Core Data Structures in the Rete Network

Three dataclasses carry information through the network, each defined in semantica/reasoning/rete_engine.py:

• Fact – represents a predicate and its arguments; defined in semantica/reasoning/reasoner.py
• Token – carries matched facts and current variable bindings (lines 54–70)
• Match – a concrete rule activation containing the rule, matched facts, and bindings (lines 72–80)

These structures enable incremental evaluation: once a fact matches a condition, the resulting token persists and participates in downstream joins without re‑matching the original fact.

Node Types: Alpha, Beta, and Terminal

The Rete algorithm partitions rule matching into three node types, each responsible for a specific computation.

AlphaNode: Single-Condition Matching

An AlphaNode tests one condition against incoming facts. The node compiles the condition into a single regex at construction time and reuses it for every fact, avoiding expensive repeated compilation (lines 90–106).

When AlphaNode.activate(fact) finds a match, it emits an Alpha token containing the fact and any variable bindings extracted from the condition.

BetaNode: Token Joining and Consistency Checking

A BetaNode receives tokens from two input sides (left and right). It maintains separate memory lists for tokens arriving on each side and attempts to merge every new token with all stored tokens from the opposite side (lines 122–135).

The join succeeds only when variable bindings are consistent across both tokens—conflicting bindings cause immediate rejection. Successful joins produce a Beta token whose fact list preserves the original order of conditions in the rule.

TerminalNode: Rule Activation Generation

The TerminalNode sits at the leaf of each rule's path. When any token reaches a terminal node, the engine creates a Match object and stores it in TerminalNode.activations (lines 144–152). These activations represent fully satisfied rules ready for execution.

Building the Rete Network from Rules

Network construction happens in ReteEngine.build_network() (lines 150–176), which accepts a list of Rule objects and performs the following for each rule:

1. Creates one AlphaNode per condition
2. Chains consecutive BetaNodes to join Alpha tokens when multiple conditions exist
3. Terminates the chain with a TerminalNode that references the original rule

This compilation step shares AlphaNodes across rules when conditions are identical, reducing memory and matching overhead.

from semantica.reasoning.reasoner import Rule, Fact
from semantica.reasoning.rete_engine import ReteEngine

# Define a rule with two conditions

rule = Rule(
    rule_id="r1",
    name="child rule",
    conditions=["Person(?x)", "Parent(?x, ?y)"],
    conclusion="Child(?y, ?x)",
)

# Build the network

engine = ReteEngine()
engine.build_network([rule])  # ← network compilation happens here

Propagating Facts Through the Network

Facts enter the network via engine.add_fact(fact). The engine stores the fact in working memory and broadcasts it to all AlphaNodes. Matching AlphaNodes forward their tokens to child nodes, triggering recursive propagation through _propagate_token() (lines 184–206).

# Add facts in any order—the network handles incremental matching

engine.add_fact(Fact("f1", "Person", ["John"]))
engine.add_fact(Fact("f2", "Parent", ["John", "Mary"]))

The design guarantees order‑independent reasoning: whether you add Person(John) or Parent(John, Mary) first, the final activations are identical. The BetaNode memories ensure partial matches persist until completing conditions arrive.

Retrieving and Executing Rule Matches

After populating facts, extract activations with engine.match_patterns():

matches = engine.match_patterns()
print(matches[0].bindings)   # → {'x': 'John', 'y': 'Mary'}

Each Match provides:

• match.rule: the original Rule object
• match.facts: list of Fact objects that satisfied the conditions
• match.bindings: dictionary mapping variables to bound values

To fire rule conclusions, bind a Reasoner instance and call execute_matches():

from semantica.reasoning.reasoner import Reasoner

engine.bind_reasoner(Reasoner())
results = engine.execute_matches()  # de-duplicates via _executed_activations

The execute_matches() method uses an internal hash set (_executed_activations) to prevent duplicate rule firings during a single execution cycle.

Resetting Engine State

Call engine.reset() to clear all state:

• Working memory (added facts)
• Token memories in every AlphaNode and BetaNode
• TerminalNode activations
• Executed activation tracking

This ensures subsequent reasoning runs start from a clean, deterministic state.

Performance Characteristics

The Semantica ReteEngine delivers several optimization benefits:

Aspect	Implementation Detail
Condition compilation	Regex compiled once per AlphaNode, reused forever
Partial match sharing	BetaNode memories avoid re‑matching completed conditions
Structural sharing	Identical conditions across rules share AlphaNodes
De‑duplication	Hash‑set tracking prevents redundant rule execution

These characteristics make the engine suitable for large rule bases with frequent fact updates, where naive re‑evaluation would be prohibitively expensive.

Summary

• ReteEngine compiles rules into a network of Alpha, Beta, and Terminal nodes for efficient incremental matching
• AlphaNodes match single conditions using pre‑compiled regexes
• BetaNodes join tokens from multiple conditions while enforcing binding consistency
• TerminalNodes collect complete matches for rule execution
• Facts can be added in any order; the network maintains partial matches until rules are fully satisfied
• Use build_network(), add_fact(), match_patterns(), and optionally execute_matches() to perform complete reasoning cycles

Frequently Asked Questions

What is the Rete algorithm and why does Semantica use it?

The Rete algorithm is a pattern‑matching algorithm designed for production systems. Semantica uses it because it avoids redundant computation by remembering partial matches and sharing condition evaluation across rules. As implemented in semantica/reasoning/rete_engine.py, this delivers significant speedups when processing large fact bases with many overlapping rule conditions.

How does the ReteEngine handle variable bindings across multiple conditions?

BetaNodes manage variable consistency during joins. Each BetaNode maintains separate memory lists for left and right inputs. When a new token arrives, the node attempts to merge it with every stored token from the opposite side, rejecting any combination where the same variable binds to different values. Only consistent merges propagate downstream.

Can I add facts after calling match_patterns()?

Yes. The ReteEngine supports fully incremental operation. After retrieving matches with match_patterns(), you can call add_fact() again with new data. The network will propagate the new fact through existing nodes, potentially generating additional matches without re‑evaluating previously added facts. Call match_patterns() again to retrieve the updated activation set.

What happens if multiple rules share the same condition?

The network construction logic in build_network() automatically shares AlphaNodes across rules when conditions are identical. This structural sharing reduces memory consumption and ensures the condition is evaluated only once per incoming fact, regardless of how many rules reference it.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}