Deadlock Detection and Resolution Prompt for Agent Pipelines

This prompt is designed for AI reliability engineers and platform teams who operate multi-agent pipelines where agents can deadlock waiting on each other's outputs or resource locks. Use it when your agent orchestrator detects a cycle in the dependency graph and needs a structured recovery plan. The prompt expects a pre-computed wait-for graph as input and returns a specific victim agent to abort or roll back, along with a justification and a step-by-step resolution sequence.

This is not a prompt for live-lock detection, performance degradation, or single-agent timeouts. It assumes the deadlock has already been detected by your infrastructure and the model's job is to decide the least disruptive way to break it. Do not use this prompt when you need real-time cycle detection—that belongs in your orchestrator code, not in the model. Do not use it when agents are merely slow or retrying; deadlock means a provable cycle in the dependency graph where no agent can make progress without external intervention. The prompt also assumes you have already ruled out transient network issues, queue backpressure, and resource exhaustion as root causes.

Before invoking this prompt, ensure your infrastructure has computed a complete wait-for graph with agent IDs, requested resources, current holders, and timestamps. The prompt will fail silently or produce dangerous output if given an incomplete graph. If your system cannot construct this graph reliably, invest in observability instrumentation first. For high-risk pipelines where an incorrect victim selection could cause data loss or financial impact, always route the model's output through a human approval step before executing the abort or rollback. The prompt includes a [RISK_LEVEL] parameter to adjust the conservatism of the resolution strategy.

This prompt template is designed to be injected into your agent orchestrator's deadlock recovery path. When a multi-agent pipeline stalls—detected by a cycle in the wait-for graph or a timeout on resource acquisition—this prompt receives the current dependency snapshot and returns a structured resolution plan. The plan identifies which agent should be rolled back (the victim), what state must be discarded, and how to re-queue the work to avoid immediate re-deadlock. The template uses square-bracket placeholders that your harness must populate from live runtime data before sending the request to the model.

textCopy
You are a deadlock resolution specialist for a multi-agent pipeline. Your job is to analyze a wait-for graph, select a victim agent for rollback, and produce a safe recovery plan that minimizes wasted work and prevents immediate re-deadlock.

## INPUT

### Wait-For Graph
[WAIT_FOR_GRAPH]
# Format: Each line is "AGENT_ID -> RESOURCE_ID" meaning the agent is blocked waiting for that resource.
# Resources can be locks, queue slots, tool availability, or agent completion signals.

### Agent State Snapshot
[AGENT_STATE_SNAPSHOT]
# Format: JSON object mapping AGENT_ID to { "status": "BLOCKED"|"RUNNING"|"IDLE", "holding": [RESOURCE_ID...], "waiting_for": RESOURCE_ID, "progress": "description of work completed so far", "priority": 1-10, "retry_count": integer }

### Resource Ownership Map
[RESOURCE_OWNERSHIP_MAP]
# Format: JSON object mapping RESOURCE_ID to { "owner": AGENT_ID|null, "type": "LOCK"|"QUEUE_SLOT"|"TOOL"|"COMPLETION_SIGNAL", "timeout_seconds": integer }

### Pipeline Context
[PIPELINE_CONTEXT]
# Description of the overall pipeline goal, agent roles, and any ordering constraints that must be preserved.

## CONSTRAINTS
- You must select exactly one victim agent for rollback unless the graph shows no cycle (then respond with NO_DEADLOCK).
- Prefer victims with the lowest priority, highest retry count, or least progress completed.
- The rollback plan must release all resources held by the victim and re-queue the victim's work after a backoff delay.
- Do not select an agent that is holding a resource required by more than [MAX_DEPENDENTS] other agents unless no other choice exists.
- If any agent has exceeded [MAX_RETRY_LIMIT] retries, escalate instead of rolling back.

## OUTPUT SCHEMA
Return a JSON object with exactly this structure:
{
  "deadlock_detected": true|false,
  "cycle_description": "string describing the cycle found, or null if none",
  "victim_agent_id": "AGENT_ID or null",
  "victim_selection_reason": "string explaining why this agent was chosen",
  "rollback_plan": {
    "release_resources": ["RESOURCE_ID..."],
    "discard_progress": "description of what work must be undone",
    "requeue_instruction": "how to re-submit the agent's task after backoff",
    "backoff_seconds": integer
  },
  "escalation_required": true|false,
  "escalation_reason": "string or null",
  "post_rollback_graph_state": "description of expected resource state after rollback"
}

## EXAMPLES

### Example 1: Simple Two-Agent Deadlock
Input Wait-For Graph:
agent_A -> lock_1
agent_B -> lock_2
Agent State: agent_A holds lock_2 waiting for lock_1, agent_B holds lock_1 waiting for lock_2
Output:
{
  "deadlock_detected": true,
  "cycle_description": "agent_A waits for lock_1 held by agent_B; agent_B waits for lock_2 held by agent_A",
  "victim_agent_id": "agent_B",
  "victim_selection_reason": "agent_B has lower priority (3 vs 7) and less progress completed",
  "rollback_plan": {
    "release_resources": ["lock_1"],
    "discard_progress": "Discard partial data transformation on batch_42",
    "requeue_instruction": "Re-submit agent_B task to queue with 5-second delay",
    "backoff_seconds": 5
  },
  "escalation_required": false,
  "escalation_reason": null,
  "post_rollback_graph_state": "agent_A acquires lock_1 and proceeds; agent_B will retry after backoff"
}

### Example 2: No Deadlock
Input Wait-For Graph:
agent_C -> tool_X
Agent State: agent_C waiting for tool_X, tool_X owner is agent_D which is RUNNING
Output:
{
  "deadlock_detected": false,
  "cycle_description": null,
  "victim_agent_id": null,
  "victim_selection_reason": null,
  "rollback_plan": null,
  "escalation_required": false,
  "escalation_reason": null,
  "post_rollback_graph_state": "No deadlock; agent_C is waiting for a running agent to release tool_X"
}

## RISK LEVEL
[RISK_LEVEL]
# HIGH: Require human approval before executing rollback.
# MEDIUM: Execute rollback automatically but log for review.
# LOW: Execute rollback automatically with standard logging.

If RISK_LEVEL is HIGH, set escalation_required to true and include a human-readable summary for the approval queue.

To adapt this template, your harness must populate the five input placeholders from the agent runtime before each invocation. The [WAIT_FOR_GRAPH] should be built by traversing the orchestrator's resource-wait table; the [AGENT_STATE_SNAPSHOT] should pull from the agent status store; and the [RESOURCE_OWNERSHIP_MAP] should reflect the current lock manager state. The [PIPELINE_CONTEXT] placeholder should include enough semantic information about agent roles and ordering constraints that the model can reason about which rollback causes the least disruption. The [MAX_DEPENDENTS] and [MAX_RETRY_LIMIT] thresholds should be set from your pipeline configuration, not hardcoded. Before executing the returned rollback plan, validate that the victim_agent_id actually exists in the current runtime and that the release_resources list matches what the victim currently holds—never trust the model's output without this structural validation.

After receiving the model's response, your harness must parse the JSON and run at least three validation checks before acting: confirm that deadlock_detected matches your own cycle-detection algorithm's result (the model can hallucinate cycles), verify that the selected victim holds the resources listed in release_resources, and check that escalation_required is consistent with your retry-budget policy. For high-risk pipelines, route the resolution plan to a human approval queue before executing the rollback. Log every deadlock event, the model's victim selection, and the final outcome to build an evaluation dataset for tuning the prompt or switching to a deterministic resolution algorithm if the model proves unreliable over time.

The deadlock detection prompt is not a standalone tool; it is a recovery component inside an agent orchestrator's error-handling loop. When a workflow stalls—no agent progress for a configurable timeout window—the orchestrator should collect the current wait-for graph, agent states, held resources, and pending actions, then invoke this prompt. The prompt's output is a structured resolution plan: a selected victim agent, rollback instructions, and a safe resumption order. The orchestrator must then execute that plan programmatically, not ask the model to perform the rollback itself. This separation keeps the model in a decision-support role while the harness enforces safety constraints like resource release ordering and state persistence.

Wire the prompt into a recovery pipeline with these concrete stages. First, stall detection: a watchdog timer or heartbeat monitor identifies that no agent has transitioned state within [STALL_TIMEOUT_SECONDS]. Second, graph construction: the harness builds a JSON wait-for graph from the orchestrator's internal state store, including agent IDs, requested resources, current holders, and timestamps. Third, prompt invocation: send the graph and [CONSTRAINTS] (e.g., 'minimize disruption', 'prefer read-only victims') to the model with a strict [OUTPUT_SCHEMA] requiring victim_agent_id, rollback_steps, resumption_order, and rationale. Fourth, output validation: before acting, validate that the victim exists in the graph, that the rollback steps reference real resources, and that the resumption order does not reintroduce the detected cycle. Reject and retry with added context if validation fails. Fifth, execution: the harness preempts the victim agent, releases its held resources in the specified order, queues rollback compensation actions, and resumes waiting agents per the plan. Log every step for postmortem analysis.

For high-risk production pipelines, add a human approval gate when the model's confidence is below a threshold or when the victim is a critical agent (e.g., payment processor, safety monitor). The harness should serialize the resolution plan, pause execution, and notify an on-call engineer via your incident management system. Do not let the model autonomously kill agents that hold financial or safety-critical state. Additionally, implement a retry budget for the detection prompt itself: if validation fails three times, escalate the entire stall to human operators rather than looping. Model choice matters here—use a model with strong reasoning capabilities (GPT-4o, Claude 3.5 Sonnet, or equivalent) because cycle detection in large graphs requires multi-hop reasoning that smaller models frequently get wrong.

Finally, treat this prompt as part of a broader reliability stack. Pair it with the Distributed Lock Acquisition Retry Prompt and the Concurrent Agent Plan Merge Conflict Resolution Prompt from this pillar. When a deadlock is resolved, the orchestrator should increment a deadlock_count metric, record the graph snapshot and resolution plan, and feed both into your observability pipeline. Over time, these traces will reveal whether deadlocks stem from resource contention patterns that should be fixed at the architecture level rather than repeatedly resolved at runtime. The prompt is a safety net, not a substitute for sound concurrency design.