Incremental Reachability Engine (IRE)

The Incremental Reachability Engine (IRE) is an execution-layer extension of the Graph Traversal Control Algorithm (GTCA).

While GTCA defines how to compute a reachable set from a static graph snapshot, IRE defines how to maintain that reachable set in real time under continuous change.

Instead of recomputing the entire graph after every update, the engine computes only the affected delta.

Do not recompute the world. Recompute only the change.

This enables low-latency, AI-native control systems.

2. Core Problem

In large-scale dynamic systems, the graph and its execution context change continuously.

Examples include:

• new approvals
• revoked permissions
• incident escalation
• role changes
• trust score updates
• time-based expiration

A full recomputation of:

ReachableSet(G, ...)

for every small change is computationally expensive.

update the reachable state space using only the minimal affected subgraph

3. Delta Model

System changes are represented as deltas.

3.1 Structural Delta

Graph topology changes.

ΔG

• edge addition
• edge removal
• node insertion
• node deactivation

3.2 State Delta

Metadata or runtime state changes.

ΔS

• status: Draft → Approved
• trust_score: 0.4 → 0.9
• incident severity updates
• timestamp expiration

3.3 Context Delta

Actor or environment changes.

ΔC

• role changes
• emergency mode activation
• audit context entry
• escalation handoff

4. Reachability Update Function

The updated reachable set is defined as:

R' = R ∪ ΔR_gain \ ΔR_loss

• R = previous reachable set
• ΔR_gain = newly reachable nodes
• ΔR_loss = invalidated nodes

This is the core formalism of incremental reachability.

5. Forward Propagation

Triggered when constraints are relaxed or new paths appear.

• edge added
• approval granted
• trust threshold satisfied

Rule

If the source node of a changed edge is already reachable:

u ∈ R

then traversal resumes from that node.

u → v

ΔR_gain

Flow

Changed edge
    ↓
Check source reachability
    ↓
Resume GTCA traversal
    ↓
Expand only new branch
    ↓
Merge into R

6. Invalidation and Pruning

Triggered when paths become invalid.

• approval revoked
• edge removed
• policy tightened
• time window expired

Rule

All nodes depending exclusively on the invalidated path are removed.

ΔR_loss

Flow

Invalidated edge
    ↓
Find dependent paths
    ↓
Temporarily remove descendants
    ↓
Check alternative valid paths
    ↓
Restore if reachable

7. Alternative Path Recovery

Removing one path does not necessarily make a node unreachable.

A → B → D
A → C → D

If:

B → D

is invalidated,

D may still remain reachable via:

C → D

path invalidation must be graph-aware, not tree-based

8. Dependency Tracking Graph

To support efficient incremental updates, IRE maintains a dependency structure.

Reverse Dependency Index

edge_id → dependent reachable nodes

This enables fast invalidation lookup.

Formal Definition

Dep(e) = {
  v ∈ R |
  every valid path to v uses e
}

9. Dirty Flag Propagation

For runtime state changes:

ΔS

affected policies are marked dirty.

dirty(edge)
dirty(node)

Only dirty regions are re-evaluated.

This dramatically reduces recomputation cost.

R_new(s) =
  R_old(s) ∪ ΔR(ΔG, s)

Only the affected subgraph is recomputed.

10. Computational Complexity

Full Recompute (GTCA)

O(V + E)

Incremental Update (IRE)

O(ΔV + ΔE)

Where ΔV = affected nodes and ΔE = affected edges.

This is the major performance advantage.

11. Integration with TraceOS

IntentReceived
ApprovalGranted
PolicyChanged
IncidentEscalated

Each event becomes a delta trigger.

TraceOS Event → Δ → Reachability Sync

This enables reactive execution boundaries.

12. AI Cognitive Boundary

the AI’s visible world changes in real time

reachable_subgraph(t)

This means the cognitive boundary of the agent is continuously synchronized with system reality.

13. Safety Interlock

Critical operations can be disabled instantly.

EmergencyStop → remove action path

The AI becomes structurally unable to execute the action.

This is much stronger than prompt-based safeguards.

14. Design Principle

GTCA defines:
what is reachable

IRE defines:
how reachability stays synchronized with change

15. Closing Principle

The world changes.
Reachability must change with it.

The Incremental Reachability Engine transforms GTCA from a static evaluation algorithm into a real-time causal control system.