Search Algorithms for Multi-Agent AIOps RCA:
A Complete Technical Guide

What it does

Standard Dijkstra explores nodes in order of cumulative cost from the source — expanding all neighbors uniformly. In multi-agent terms, this means spawning a parallel agent per graph region and letting each one query all available data sources. An LLM supervisor collects results and synthesises a root cause.

The token math problem

When you connect MCP servers to Claude Code agents, the protocol automatically loads all tool schemas into context. One developer reported 66,000 tokens consumed at conversation start — a third of Claude Sonnet's 200k context window — before typing the first prompt. BSWEN, 2026

For your 6-MCP setup with 20 agents: 20 × 66,000 = 1.32M tokens before any reasoning begins. At Sonnet 4.6 pricing ($3/$15 per million), that's ~$4 in input tokens per incident before a single line of reasoning.

Why it still gets used

It's easy to build. No shared state management, no heuristic design, no beam pruning logic. For teams just starting with multi-agent AIOps, it's often the first thing that gets built. Use it only for prototyping or when incidents are rare (<5/day) and cost is not a constraint.

The algorithm

Bidirectional Dijkstra runs two simultaneous searches: one forward from the anomaly node, one backward from a known-healthy baseline state. It terminates when the two frontiers meet — provably requiring only ~√N node expansions versus N for single-direction search. Haeupler et al., 2024 — Bidirectional Dijkstra is Instance-Optimal

How it maps to your agent setup

• Forward agents traverse the knowledge graph downstream from the anomaly — exploring which services are affected, what the blast radius looks like, which Dynatrace metrics correlate.
• Backward agents traverse upstream from the incident time window — exploring change requests, Bitbucket deploys, config changes that preceded the symptom.
• Convergence is detected when both frontiers have visited the same node (e.g., a specific service version in a specific deployment window).

The critical blind spot: static edge weights

Bidirectional Dijkstra assumes the knowledge graph has static edge weights. But in your AIOps context, discovering that a deploy happened at T-26min (upstream) should immediately make db-pool-config edges more expensive to ignore (downstream). The two frontiers cannot communicate this discovery — they operate independently until convergence.

When to use it

Use bidirectional Dijkstra when incidents have well-separated cause and effect chains with minimal co-dependency between investigations, and when you need a significant improvement over naive fan-out without the complexity of shared state management.

The blackboard pattern — the missing primitive

The blackboard pattern provides a shared knowledge base that agents use to post and retrieve information, enabling agents to collaborate asynchronously without direct communication. It is especially useful for solving complex problems requiring incremental, multi-agent contributions. Confluent: Four Design Patterns for Event-Driven Multi-Agent Systems, 2025

Critically: this is what solves your cross-frontier dependency problem. Upstream agents write discoveries to the blackboard. Downstream agents read those discoveries before choosing their next hop. No direct agent-to-agent messaging, no supervisor context explosion.

The blackboard schema for your stack

{
  "incident_id": "P1-20260425-001",
  "symptom_node": "service:checkout-api",
  "temporal_anchor": {
    "symptom_start": "2026-04-25T14:23:11Z",
    "search_window": "T-45min to T+5min",
    "change_events": [
      {"type": "deploy", "service": "checkout-api",
       "version": "v2.3.1", "at": "T-26min"},   // from Bitbucket MCP
      {"type": "config", "key": "db.pool.max",
       "old": 50, "new": 20, "at": "T-31min"}    // from change request MCP
    ]
  },
  "hypotheses": [
    {
      "id": "H1",
      "claim": "DB connection pool exhausted on orders-db",
      "confidence": 0.72,
      "evidence_for": ["splunk:ERR_POOL_TIMEOUT x847"],
      "evidence_against": ["dynatrace:rds_cpu=18% (healthy)"],
      "agents": ["log-agent-3", "dynatrace-agent-1"]
    },
    {
      "id": "H2",
      "claim": "checkout-api v2.3.1 deploy at T-26min",
      "confidence": 0.84,
      "evidence_for": ["bitbucket:cf8a2d1 T-26min",
                       "dynatrace:p99 spike T-24min"],
      "evidence_against": []
    }
  ],
  "search_constraints": {
    "redirect_instructions": {
      "upstream_agents": "Focus on orders-db upstream chain. 
                          Deprioritise network layer.",
      "downstream_agents": "Focus on payment-svc post-T-26min.
                            Check v2.3.1 client code changes."
    },
    "ruled_out": ["auth-service", "cdn-layer"]
  },
  "halt": false
}

How cross-frontier propagation actually works

The redirect_instructions field is the mechanism that solves your dependency problem. Here's the concrete flow:

1. Upstream Beam 2 (deploy path agent) finds deploy v2.3.1 at T-26min. It writes H2.confidence += 0.2 and updates redirect_instructions.downstream_agents to focus on payment-svc post-T-26min.
2. Downstream Beam 1 (service call agent) polls the blackboard before its next hop. It sees the redirect instruction, pivots from generic call-graph traversal to specifically checking payment-svc behavior after T-26min.
3. Downstream Beam 1 finds payment-svc p99 latency jumped from 80ms to 3,400ms at T-24min — matching the deploy boundary. It writes this as H2.evidence_for. Confidence rises to 0.84.
4. Arbiter reads blackboard. H2 at 0.84. Prunes low-confidence beams. Redirects freed agent to fetch the v2.3.1 Bitbucket diff via targeted MCP call.

Research backing: MA-RCA

The MA-RCA framework (Springer, November 2025) implements this exact pattern — a Retrieval Agent grounds hypotheses in external knowledge, a Validation Agent tests them against runtime data, and findings propagate through shared state. Results: 95.8% accuracy (F1=0.952) on the Nezha cloud-native benchmark, outperforming single-agent baselines by a large margin. MA-RCA, Complex & Intelligent Systems 2025

Flow-of-Action: SOP-constrained traversal

The Flow-of-Action paper (WWW 2025) shows that encoding expert Standard Operating Procedures into the traversal — so agents follow a defined checklist per node rather than free-form reasoning — raises accuracy from 35.50% to 64.01%. Flow-of-Action, WWW 2025 The checklist per node in your context looks like:

For each knowledge graph node visited:
  1. Does this node have an anomaly signal in T±45min? [Splunk/Dynatrace MCP]
  2. Was there a deployment/config change touching this node? [Bitbucket/CR MCP]
  3. Does this node's error rate correlate with the symptom timeline? [Dynatrace]
  4. What is this node's upstream dependency? → next hop candidates
  5. Confidence score update → write to blackboard
  6. Check blackboard halt signal before continuing

Beam pruning strategy

Run 3 beams per frontier (upstream and downstream). After every 2 hops, the Arbiter reads confidence scores and prunes the lowest-confidence beam. The freed agent gets reassigned to targeted signal fetching for the leading hypothesis. This keeps your active agent count at 6-8 rather than 20-30, while maintaining parallel hypothesis coverage.

The core formula

Why h(n) matters and how it solves your dependency problem

In Beam Search + Blackboard (Architecture 3), agents still explore neighbors in a somewhat uninformed order. The Arbiter then corrects them with redirect_instructions — but there's a lag between the discovery and the redirect. In A*, each agent computes f(n)=g(n)+h(n) before choosing the next hop, so it never starts walking a dead-end path.

The critical upgrade: h(n) is computed from the live blackboard state. When the upstream agent writes a deploy discovery, the heuristic weights in the blackboard update. Both frontiers recompute h(n) before their next hop — automatically prioritising nodes connected to the deploy event. This eliminates the arbiter lag entirely.

Admissibility: the correctness guarantee

A* is guaranteed to find the optimal (minimum cost) path if and only if h(n) never overestimates the true cost to goal. For your RCA use case:

• Overestimating = skipping the actual root cause node because you thought a shorter path existed. This produces wrong RCA answers.
• Underestimating = exploring a few extra nodes unnecessarily. This costs a small amount of compute but never gives wrong answers.
• Rule of thumb: Start h weights conservative (w1=0.3, w2=0.3, w3=0.2, w4=0.2). Only increase aggressively after you have 3+ months of incident data to validate the heuristic doesn't skip true root causes.

The h(n) function mapped to your MCPs

Temporal anchoring: cuts 60-80% of the graph for free

The single cheapest optimisation in your entire stack. Nodes with no change events, anomalies, or incidents in the T±45min window get h(n)=0. Agents skip them entirely without any MCP call. For a typical 200-node service graph with a single deployment event, this eliminates ~160 nodes from consideration before any reasoning begins.

The Adversarial Validator (ACH) — your accuracy insurance

Analysis of Competing Hypotheses (ACH) is an intelligence analysis technique. Instead of trying to confirm the leading hypothesis, you systematically try to disprove each candidate root cause. The root cause that survives the most rigorous disproof attempts wins. eCrimeLabs: ACH in Incident Response

In your architecture: once the bidirectional A* frontiers converge on the top-2 candidates, spawn a dedicated Opus 4 agent whose system prompt is: "Your job is to find the strongest evidence AGAINST hypothesis H2. Do not try to confirm it. Use all available tools to find contradicting data." If this agent cannot disprove H2 but can disprove H1, H2 is confirmed as root cause. This step eliminates the most common failure mode: LLM agents hallucinating plausible-sounding root causes that aren't actually supported by data.