How do you detect and handle livelocks in multi-agent systems?

A livelock happens when multiple agents remain active—retrying, handing tasks back and forth, or changing plans—but make no useful progress. Unlike a deadlock, where work is blocked, livelocked agents keep doing work that fails to move the shared goal closer to completion.

Beginner-friendly example: API test-generation agents

A requirements agent and a test generator disagree about the expected input:

• Requirements agent: Sends a security requirement without an authentication scheme.
• Test generator: Rejects it and sends it back for clarification.
• Requirements agent: Resends the unchanged requirement.
• Test generator: Rejects it again.

Both agents are responding, yet no test suite is produced.

Observe repeated handoffs → Measure progress → Stop the cycle → Diagnose the missing dependency → Escalate or choose a bounded recovery action

Simple numerical example

Suppose a workflow allows at most 5 handoffs for a given requirement, and each handoff costs 2 seconds.

• After 5 handoffs, the system has spent 10 seconds.
• The count of validated requirements remains 0.
• The coordinator marks the task as STALLED, records the repeated state, and requests a missing authentication scheme rather than starting the same exchange again.

A useful signal is not merely that many messages occurred; it is that progress stayed unchanged while the same states or errors recurred. The thresholds are illustrative and should reflect task complexity.

How can you detect a livelock?

1. Define measurable progress: Examples include validated fields, completed subtasks, accepted artifacts, or reduced unresolved errors.
2. Track state transitions: Record handoffs, retries, decisions, and whether they changed the useful task state.
3. Recognize repeated states: Detect cycles such as A → B → A with identical inputs, version numbers, or unresolved errors.
4. Set bounded budgets: Limit retries, handoffs, elapsed time, model calls, and token expenditure.
5. Alert on no progress: Trigger review when the system remains active but a progress metric is unchanged beyond a defined threshold.

Do not confuse a legitimate multi-step refinement loop with livelock. Revisions that genuinely improve an artifact or reduce validation errors may represent meaningful progress.

How do you break a livelock?

• Change the recovery action: Request missing data, choose a different approved strategy, or escalate to a human instead of replaying the same message.
• Introduce asymmetric coordination: Let a designated supervisor make a final routing decision when peers repeatedly defer to one another.
• Use randomized backoff where relevant: Prevent agents contending for the same resource from repeatedly yielding in sync.
• Apply a termination policy: End with a clear STALLED or FAILED status and preserve usable intermediate results.
• Require evidence of improvement: Permit another attempt only when an input, plan, dependency, or version has materially changed.

LangGraph and Celery considerations

In LangGraph, track a structured progress marker and handoff count in graph state. Add a conditional route that stops repeated A↔B transitions when a budget or no-progress threshold is reached. Graph recursion limits can bound execution but do not by themselves diagnose the reason for a livelock.

In Celery, repeated retries or rapidly resubmitted tasks can produce a livelock-like cycle while workers remain busy. Keep shared retry budgets and task-state records in a durable store; avoid allowing each worker to reset the retry count independently.

Deadlock vs. starvation vs. livelock

• Deadlock: Agents wait on each other and cannot proceed.
• Starvation: Other tasks progress, but one task repeatedly loses access to resources.
• Livelock: Agents continue taking actions, but those actions fail to advance the shared task.

In short

Detect livelocks by tracking useful progress, not just agent activity. Break repeating cycles with explicit budgets, changed strategies, supervisor decisions, and truthful stalled-task reporting.