# How Does the ReteEngine in Semantica Perform Rule Matching?

> Discover how Semantica's ReteEngine performs rule matching using a network of nodes that cache partial matches and incrementally process new facts for efficient condition evaluation.

- Repository: [Semantica /semantica](https://github.com/semantica-agi/semantica)
- Tags: internals
- Published: 2026-09-08

---

**The Semantica ReteEngine implements the classic Rete algorithm to match rules against facts by constructing a network of nodes that cache partial matches, incrementally propagating new facts through AlphaNodes for single-condition matching and BetaNodes for multi-condition joins.**

The `semantica-agi/semantica` repository provides a compact forward-chaining reasoner that uses this network-based approach for high-performance rule evaluation. Understanding how the **ReteEngine** performs rule matching requires examining its node hierarchy, incremental propagation mechanisms, and efficient caching strategies. This implementation avoids brute-force recomputation by only processing new facts and their directly affected partial matches.

## Core Architecture of the ReteEngine

The engine orchestrates network construction and fact propagation through specialized node types defined in [`semantica/reasoning/rete_engine.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/rete_engine.py).

### The ReteNode Hierarchy

All nodes inherit from the base `ReteNode` class (lines 82‑88), which tracks a unique `node_id` and child relationships. The network consists of three specialized implementations:

- **`AlphaNode`** (lines 90‑99): Matches single conditions against incoming facts. Each node pre-compiles a regex pattern during initialization and emits a **Token** when a fact unifies with its condition via the `_matches` method (lines 29‑38).
- **`BetaNode`** (lines 60‑72): Serves as a join node that enforces variable binding consistency across multiple conditions. It maintains separate token caches for left and right inputs and performs joins via the `join` method (lines 74‑84).
- **`TerminalNode`** (lines 91‑99): Represents the final rule activation point. When tokens reach this node, they convert into **Match** objects stored in the node's `activations` list.

### Token and Match Objects

Tokens flow through the network as immutable data carriers. The `Token` dataclass (lines 54‑66) stores a list of matched facts and current variable bindings. When a token reaches a TerminalNode, it becomes a `Match` instance (lines 72‑79) containing the rule reference, matched facts, final bindings, and confidence score.

## Building the Network from Rules

When `ReteEngine.build_network(rules)` is invoked, the engine transforms rule condition lists into an optimized directed graph stored in `self.network: Dict[str, ReteNode]` (line 34).

The construction process chains nodes through `_add_rule_to_network`:

1. **Alpha nodes** are instantiated for every individual condition in the rule.
2. **Beta nodes** are inserted between successive alpha nodes to join their partial matches and enforce shared variable consistency.
3. A **Terminal node** caps the chain to capture final activations.

This compile-time optimization ensures that runtime evaluation follows a predetermined path optimized for the specific rule set.

## Incremental Fact Propagation and Matching

The ReteEngine achieves performance through incremental evaluation. When a new fact enters the system via `engine.add_fact(fact)`, three operations occur:

1. The fact is stored in `self.facts`.
2. `_propagate_fact` scans all **AlphaNode** instances, invoking `AlphaNode.add_fact` when the `_matches` method returns true.
3. Generated tokens flow downstream through `_propagate_token`.

### Alpha Matching and Token Generation

AlphaNode instances test facts using pre-compiled regex patterns established in `__init__` (lines 4‑6). Successful matches create Token objects that enter the network's downstream propagation path.

### Beta Joining and Variable Binding

When tokens arrive at **BetaNode** instances, the engine stores them in either `left_tokens` or `right_tokens` lists depending on their source. The `join` method (lines 74‑84) then attempts to merge each new token with every token on the opposite side. Successful joins—where variable bindings remain consistent—generate new merged tokens that continue downstream. This caching mechanism avoids recomputing joins for unchanged facts.

### Terminal Activation

Upon reaching a **TerminalNode**, the token converts into a **Match** object and appends to the node's `activations` list. This design isolates completed matches from the active propagation stream.

## Retrieving and Executing Matches

The `match_patterns()` method (lines 28‑31) walks the network and aggregates all `TerminalNode.activations` into a consolidated list of Match objects.

If the engine binds to a **Reasoner** via `engine.bind_reasoner()`, calling `execute_matches()` fires each matched rule's actions through the reasoner interface. This guarantees that side effects—such as inferred fact updates—remain consistent with the forward-chaining execution path.

## Performance Optimizations in the ReteEngine

Three key optimizations maximize throughput:

- **Pre-compiled regexes**: AlphaNode conditions compile regex patterns once during initialization rather than per-fact evaluation.
- **Token memories**: BetaNode instances cache partial results in `left_tokens` and `right_tokens`, enabling efficient O(n+m) joins rather than Cartesian products.
- **Selective propagation**: The incremental algorithm ensures only the new fact and its dependent partial matches trigger computation, avoiding full network resets.

## Code Example: Using ReteEngine for Rule Matching

```python
from semantica.reasoning import Rule, Fact
from semantica.reasoning import ReteEngine

# Define a rule with a variable condition

rule = Rule(
    rule_id="person_rule",
    conditions=["Person(?x)"],
    conclusion="Person detected",
    actions=[],
)

# Initialize engine and build the network

engine = ReteEngine()
engine.build_network([rule])

# Insert facts into the working memory

engine.add_fact(Fact("f1", "Person", ["John"]))
engine.add_fact(Fact("f2", "Location", ["Paris"]))

# Retrieve all current matches

matches = engine.match_patterns()
for m in matches:
    print(m.rule.rule_id, m.bindings)   # Output: person_rule {'x': 'John'}

# Optional: Execute matched rule actions via a bound Reasoner

# engine.bind_reasoner(my_reasoner)

# results = engine.execute_matches()

```

This example demonstrates network construction, fact insertion, token propagation through the Rete network, and match retrieval using the actual API surface from [`semantica/reasoning/rete_engine.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/rete_engine.py).

## Summary

- The **ReteEngine** uses a network of **AlphaNodes**, **BetaNodes**, and **TerminalNodes** defined in [`semantica/reasoning/rete_engine.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/rete_engine.py) to implement the Rete algorithm for efficient forward-chaining.
- **Incremental propagation** via `add_fact()` ensures only new facts trigger recomputation, caching partial matches in BetaNode token memories (`left_tokens` and `right_tokens`).
- **Pre-compiled regex patterns** in AlphaNode conditions eliminate redundant pattern compilation during the matching phase.
- The network construction process chains nodes automatically via `build_network()`, creating optimized join paths for multi-condition rules without manual intervention.
- Matches are collected through `match_patterns()` and executed via `execute_matches()` when bound to a Reasoner instance, maintaining consistency between the matching and action phases.

## Frequently Asked Questions

### What algorithm does the Semantica ReteEngine use for rule matching?

The ReteEngine implements the classic **Rete algorithm**, a forward-chaining inference method that constructs a network of nodes to cache partial matches. According to the source code in [`semantica/reasoning/rete_engine.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/reasoning/rete_engine.py), this design avoids brute-force evaluation by maintaining state across AlphaNodes and BetaNodes, enabling efficient incremental updating when new facts arrive rather than re-evaluating all rules from scratch.

### How does the ReteEngine handle new facts incrementally?

When `engine.add_fact(fact)` is called, the engine stores the fact and invokes `_propagate_fact` to scan all **AlphaNode** instances. Matching nodes generate **Token** objects that flow downstream through `_propagate_token`. **BetaNode** instances cache these tokens in `left_tokens` or `right_tokens` lists and perform joins only with tokens from the opposite side, ensuring only affected partial matches are recomputed rather than the entire rule set.

### What is the difference between AlphaNode and BetaNode in Semantica?

**AlphaNode** classes (lines 90‑99) handle single-condition matching against individual facts using pre-compiled regex patterns in their `_matches` method (lines 29‑38). **BetaNode** classes (lines 60‑72) serve as join nodes that enforce variable binding consistency across multiple conditions by merging tokens from two upstream sources. While AlphaNodes initiate token creation upon fact insertion, BetaNodes perform the `join` operation (lines 74‑84) to combine partial matches into complete rule activations.

### How are rule actions executed after the ReteEngine finds matches?

After `match_patterns()` collects **Match** objects from **TerminalNode** activations, the optional `execute_matches()` method fires rule actions. If a **Reasoner** is bound via `engine.bind_reasoner()`, the engine invokes the reasoner to process each match's actions, ensuring side effects like inference updates remain consistent with the forward-chaining execution path defined in the network.