Execution Strategies

Core Concepts

The Inference Direction Problem

When a rules engine evaluates your rules, it has to make a fundamental choice: where does it start? Does it begin with what it already knows and work outward, or does it begin with a specific question and work backward to find the answer?

This is the choice between forward chaining and backward chaining — and it shapes everything about how the engine behaves.

Forward Chaining: Start with Facts, Work Toward Conclusions

Forward chaining is a data-driven inference approach. The engine starts with the known facts currently in working memory, scans its rules to find any whose IF conditions match those facts, fires those rules, and then adds any newly derived facts back into working memory. This process repeats — newly derived facts trigger more rules — until no more rules can fire.

Forward chaining asks: "Given what I know right now, what else can I conclude?"

This is a bottom-up, reactive model. When a new fact enters the system — say, a transaction event, a sensor reading, or an updated customer record — the engine immediately re-evaluates rules to discover newly applicable ones, triggering a chain of activations. That reactive characteristic makes forward chaining the natural fit for production systems where facts continuously change and new inferences must be automatically discovered.

Forward chaining is the most common execution strategy in practical rules engines. The Rete algorithm, which sits at the heart of engines like Drools, was designed specifically to optimize forward-chaining pattern matching.

Because individual rule evaluations in a forward chaining system do not maintain persistent state between executions, rules can run in parallel without concerns about state conflicts. This makes forward chaining particularly well-suited for distributed and concurrent execution.

Backward Chaining: Start with a Goal, Work Toward Evidence

Backward chaining inverts the direction. The engine starts with a specific goal or hypothesis — "Is this customer eligible for this offer?" — and works backward through the rule network to determine what facts and rules would need to be true to prove it. It is a top-down, hypothesis-testing approach.

Backward chaining asks: "What would have to be true for this conclusion to hold?"

Unlike forward chaining which explores all possible inferences from known facts, backward chaining focuses the search on what is needed to prove a specific conclusion. This makes it more efficient for targeted queries — it executes fewer rules overall and provides leaner performance when the objective is to answer a specific question rather than derive every possible conclusion.

Backward chaining is particularly well-suited for diagnostic and troubleshooting applications: medical diagnosis systems where a physician suspects a condition and needs to verify it through evidence; IT troubleshooting where the system must isolate root causes from observed symptoms; eligibility checks where you need to verify whether a specific set of criteria are all satisfied.

Hybrid: Use Both in the Same Engine

Modern engines like Drools support hybrid chaining — forward and backward chaining can coexist within the same rule set. You can write rules that react to incoming data events using forward chaining, while querying the engine with specific goals using backward chaining. The Drools Expert User Guide documents this as a first-class feature. CLIPS (developed at NASA in 1985) and its Java descendant Jess implement similar strategies.

This hybrid capability is what makes production-grade engines significantly more expressive than simple rule lists.

---

Conflict Resolution: The Non-Determinism Risk

Forward chaining creates a practical problem: what happens when multiple rules have their conditions satisfied simultaneously? The engine has to pick one to fire first. The mechanism that makes this choice is called conflict resolution.

Common conflict resolution strategies include:

• Salience (explicit priority) — rules are assigned numeric priority values; higher salience fires first.
• Specificity — more specific rules (matching more conditions) fire before more general ones.
• Recency — rules matching more recently asserted facts take precedence.
• Rule ordering — a predefined sequence determines execution order.

The Drools rule engine documentation covers these strategies in depth, including how the agenda manages competing activations.

Unresolved rule conflicts also make testing unreliable: a test suite that passes today may fail after a rule is added because the firing order shifts. Tools like OpenRules treat conflict detection as a first-class concern.

---

Execution Strategy: First Match, All Matches, Every Rule

Beyond inference direction, rules engines also differ in their execution strategy — how many rules they fire once matches are found.

Rules engines support different execution strategies that determine whether the engine:

• Returns the first matching rule and stops.
• Returns all matching rules and their combined actions.
• Evaluates every rule regardless of prior matches.

This distinction is especially visible in decision tables. A "first match wins" strategy is appropriate for mutually exclusive rule sets (routing to a single destination); an "all matches apply" strategy is appropriate when multiple rules can legitimately fire on the same input (applying multiple discounts). The right choice depends on your problem domain.

---

Stateful vs. Stateless Sessions

How the engine handles state between calls is one of the most consequential architectural choices you will make when integrating a rules engine into a service.

Stateless Sessions

In a stateless session, a new session is created for each request. Facts are inserted, rules are evaluated once, results are returned, and the session is discarded. There is no working memory carried between calls. The session behaves like a pure function: same inputs, same outputs, no side effects on internal state.

A stateless engine does not support automatic inference — it cannot fire rules triggered by facts asserted by other rules during the same evaluation, because those derived facts are not propagated back through the rule network.

The calling application is responsible for managing state externally — deciding which facts to provide with each invocation and retrieving any persisted state from a database or cache before calling the engine.

Stateless sessions are the natural choice for validation, routing, and filtering: validating loan eligibility criteria, routing incoming events to processing queues, filtering records based on attribute conditions. These use cases require a single pass through the rules and do not need multi-step reasoning.

Stateless sessions are also simpler to scale horizontally. Each invocation is independent, so load balancers can route requests to any available instance. A single engine instance can handle concurrent requests without creating a pool of session objects.

Stateful Sessions

In a stateful session, the session persists across multiple invocations. Facts are inserted and removed over time while the working memory remains intact. The engine maintains accumulated context, so rules can reference facts asserted in previous rule firings and modify accumulated state through iterative reasoning.

This enables complex patterns: multi-step approval workflows where each step depends on the outcome of previous ones; shopping cart total calculations where rules accumulate line items and apply progressive discounts; state machines where execution depends on a sequence of events over time.

The memory cost of stateful sessions is proportional to the number of accumulated facts in working memory and the complexity of the Rete network. Stateful engines typically require one session per user or context, rather than a single shared engine instance.

Truth Maintenance in Stateful Sessions

Stateful sessions unlock a capability that has no equivalent in stateless evaluation: truth maintenance.

Truth maintenance allows the engine to track which facts were asserted as a direct result of specific rules firing. If the conditions that caused a rule to fire later become false — because an underlying fact was retracted or modified — the engine automatically retracts the facts that rule derived.

This keeps the working memory logically consistent as the underlying facts change. Without truth maintenance in a long-running stateful session, stale derived facts accumulate and produce incorrect inferences.

Truth maintenance is essential in stateful sessions but not applicable to stateless engines, since stateless engines do not retain state between invocations.

---

Compare & Contrast

Fig 1

Fig 2

---

Worked Example

Scenario: Fraud Screening vs. Fraud Investigation

Consider a payments platform with two distinct problems:

Problem 1 — Real-time transaction screening as each payment arrives. Problem 2 — Fraud investigation to determine whether a specific account has been compromised.

These two problems call for different execution strategies.

Problem 1: Transaction Screening (Forward Chaining, Stateless)

Each incoming transaction is a self-contained event. The engine receives the transaction facts, evaluates a rule set for risk signals, and returns a risk score or action (approve, decline, flag for review). There is no need to remember previous transactions inside the engine — the calling service fetches account history from a database and injects relevant context as facts before each call.

This is a stateless session. The engine acts like a pure function: insert facts, fire rules once, get result, discard session. Because sessions are ephemeral, the engine can handle concurrent requests without creating a pool of session objects and can be horizontally scaled across any number of instances without session affinity constraints.

The inference direction is forward chaining: when a transaction is inserted, rules react to its attributes, derive intermediate facts (high velocity, unusual merchant category, card-not-present), and combine them into a final risk score.

Problem 2: Account Investigation (Backward Chaining, Stateful)

An analyst suspects an account is compromised. The system needs to answer: "Is account #12345 exhibiting fraud patterns?" It queries the engine with this specific goal, and the engine works backward to determine which rules and facts are required to prove or disprove it.

Backward chaining is more efficient here because it focuses rule traversal only on what is needed to prove the hypothesis, rather than deriving all possible inferences from all known facts.

If the investigation spans multiple interactions — the analyst adds new evidence, and the engine must re-evaluate its conclusions — a stateful session is appropriate. Truth maintenance ensures that if an earlier piece of evidence is retracted (turns out to be erroneous), all facts derived from it are automatically revoked.

The Conflict Resolution Layer

Both problems share a risk: if multiple rules fire simultaneously, the order in which they fire must be predictable. For the screening case, rule salience should be set explicitly to ensure high-severity checks (velocity limits, geographic anomalies) are evaluated before lower-priority ones. Without explicit conflict resolution, the same transaction could yield different risk scores depending on engine state — a production defect that will be extremely difficult to reproduce.

---

Common Misconceptions

"Forward chaining is always stateful." Forward chaining naturally aligns with stateful evaluation because it is data-driven and benefits from accumulated working memory. However, forward chaining rules can also run in stateless configurations — the rules fire in a single pass without chaining derived facts back through the network. The alignment is natural, not mandatory.

"Stateless means the engine is simpler." Stateless sessions shift complexity out of the engine and into the caller. The calling application must manage state externally, deciding what facts to assemble before each call and where to persist results. The engine is simpler; the integration code is not necessarily simpler.

"Conflict resolution only matters in complex rule sets." Even small rule sets can produce non-deterministic behavior if two rules can match the same fact and their order is not specified. The problem scales with the number of rules, but it can appear even in five-rule systems. Assign salience or order rules explicitly from the start.

"A stateful session and a stateless session have the same inference capabilities." They do not. Stateless sessions cannot support automatic inference — a fact derived by one rule cannot trigger another rule in the same evaluation. If your problem requires chained inferences, you need a stateful session.

---

Boundary Conditions

Stateful sessions in Kubernetes. Stateful sessions require session affinity — all requests belonging to a session must route to the same pod. Kubernetes supports this via sessionAffinity: ClientIP, but it undermines rolling deployments and auto-scaling events that kill pods. Stateful rules engines in Kubernetes require careful pod lifecycle management, and sticky session routing has known failure modes during scale-in events.

Truth maintenance with high fact churn. Truth maintenance tracks justification chains. In sessions with very high rates of fact assertion and retraction, the overhead of maintaining those chains can become significant. If facts change continuously at high frequency, benchmark truth maintenance overhead explicitly before committing to it in a high-throughput path.

Backward chaining with circular rules. Backward chaining can enter infinite loops if the rule graph contains cycles — a goal that can only be proven by a rule whose conditions include the goal itself. Production rule engines include loop detection, but the configuration and behavior vary. Test for cycles explicitly in diagnostic rule sets.

Execution strategy and decision table semantics. Execution strategies for decision tables (first match, all matches, evaluate all) are not the same concept as inference direction. A first-match decision table uses forward chaining internally but stops after the first matching row. Understanding which layer of the engine each configuration controls prevents misconfigured rule sets.

Salience is not a substitute for rule design. Conflict resolution via salience patches ordering problems but does not eliminate the underlying design issue. Deeply overlapping rules with complex salience hierarchies become difficult to reason about and test. If you find yourself assigning salience values to many rules, consider whether the rules should be restructured to reduce overlap.