Why Our CLI Deadlock Detector for Multi-Agent LLMs Timed Out: A Post-Mortem on Naive Jaccard Heuristics

When designing orchestrations for autonomous multi-LLM workflows, one of the most frustrating failure modes is semantic deadlock—where multiple agents fall into circular reasoning, context divergence, or redundant conversational loops.

In an attempt to catch these divergence states early in automated continuous-integration workflows and long-running daemons, we built a standalone, stateless CLI tool: the Asynchronous Semantic Deadlock Checker. The goal was simple: consume execution traces, calculate semantic alignment across all collaborating agents, and trigger recovery interventions within a strict 10-second SLA.

However, during high-concurrency QA stress tests involving 20+ active agents, the tool collapsed with an unhandled timeout.

Here is the complete technical breakdown of the architecture, the production code, the profiling post-mortem, and the architectural anti-patterns exposed by this failure.

To ensure zero daemon overhead and easy integration into CI/CD pipelines, pre-commit hooks, and cron-based monitoring scripts, we designed the checker around a strictly stateless Unix-philosophy pipeline:

stdin), containing recent execution traces, agent identifiers, operational states, and raw text outputs.looping, stuck, repeating, contradicting). stdout), detailing deadlock verdicts, offending agent IDs, and automated mitigation directives (FORCE_RESET_CONTEXT_AND_CONVERGE).

graph TD
    subgraph InputStage ["Input Processing"]
        A["Agent Logs: JSON Stream via STDIN"] --> B["Token Extraction: Naive Whitespace Splitting"]
    end

    subgraph MetricStage ["Pairwise Analysis"]
        B -- "O(N^2) Matrix Generation" --> C["Jaccard Distance Matrix"]
        C -- "Threshold < 0.15" --> D["Divergence Flag"]
        C -- "Outlier Distance" --> E["Culprit Identification"]
    end

    subgraph DecisionStage ["Resolution & Recovery"]
        D --> F["Deadlock Decision Engine"]
        E --> F
        F -- "Emit Payload" --> G["Recovery Instructions / Reset Trigger"]
    end

Below is the complete Python implementation deployed into the test environment.

import sys
import json
from collections import defaultdict

def tokenize(text):
    if not text:
        return set()
    return set(str(text).lower().split())

def jaccard_similarity(set_a, set_b):
    if not set_a or not set_b:
        return 0.0
    intersection = len(set_a.intersection(set_b))
    union = len(set_a.union(set_b))
    return intersection / union if union > 0 else 0.0

def main():
    try:
        input_data = sys.stdin.read()
        if not input_data.strip():
            print(json.dumps({"error": "Empty input"}, ensure_ascii=False))
            return
        logs = json.loads(input_data)
    except Exception as e:
        print(json.dumps({"error": f"Invalid JSON: {str(e)}"}, ensure_ascii=False))
        return

    agents = defaultdict(list)
    for entry in logs:
        aid = entry.get("agent_id", "unknown")
        agents[aid].append(entry)

    agent_latest = {}
    agent_tokens = {}
    for aid, history in agents.items():
        latest = history[-1]
        agent_latest[aid] = latest
        agent_tokens[aid] = tokenize(latest.get("output", ""))

    agent_ids = list(agent_latest.keys())
    n = len(agent_ids)
    similarity_matrix = {}
    deadlock_suspects = []
    divergence_detected = False

    for i in range(n):
        id_a = agent_ids[i]
        tokens_a = agent_tokens[id_a]
        for j in range(i + 1, n):
            id_b = agent_ids[j]
            sim = jaccard_similarity(tokens_a, agent_tokens[id_b])
            similarity_matrix[f"{id_a}-{id_b}"] = sim
            if sim < 0.15:
                divergence_detected = True

    for aid, latest in agent_latest.items():
        state = latest.get("state", "idle")
        if state in ["looping", "stuck", "repeating", "contradicting"]:
            deadlock_suspects.append(aid)

    if not deadlock_suspects and divergence_detected and n > 1:
        avg_sims = {}
        for id_a in agent_ids:
            sims = [
                jaccard_similarity(agent_tokens[id_a], agent_tokens[id_b]) 
                for id_b in agent_ids if id_a != id_b
            ]
            avg_sims[id_a] = sum(sims) / len(sims) if sims else 1.0
        if avg_sims:
            culprit = min(avg_sims, key=avg_sims.get)
            deadlock_suspects.append(culprit)

    suspect_set = list(set(deadlock_suspects))
    result = {
        "status": "DEADLOCK_DETECTED" if (divergence_detected or deadlock_suspects) else "NORMAL",
        "divergence_detected": divergence_detected,
        "culprit_agents": suspect_set,
        "similarity_matrix": similarity_matrix,
        "correction_instruction": {
            "target_agents": suspect_set,
            "action": "FORCE_RESET_CONTEXT_AND_CONVERGE",
            "message": "Semantic deadlock or context divergence detected. Refocus on the primary objective and abandon circular arguments."
        }
    }

    print(json.dumps(result, ensure_ascii=False, indent=2))

if __name__ == "__main__":
    main()

💡 For immediate deployment: The complete source code suite (ZIP) for this architecture is available on Gumroad for $0+ (Pay What You Want).

In our QA stress-testing environment, we simulated an orchestration topology with 24 concurrent agents, where each agent generated long-form diagnostic dumps, chain-of-thought traces, and structured code snippets totaling several thousand tokens per turn.

Under these conditions, execution terminated with the following unhandled exception:

TimeoutExpired: Command '['python3', 'deadlock_checker.py']' timed out after 10 seconds.

The script contained no infinite loops (while True or unbounded recursion). The timeout was triggered entirely by an algorithmic and memory management bottleneck.

For $N$ agents, calculating the full similarity matrix requires evaluating $\frac{N(N - 1)}{2}$ unique pairs. When $N = 24$, this yields 276 pairwise evaluations.

Furthermore, during the culprit isolation phase:

sims = [
    jaccard_similarity(agent_tokens[id_a], agent_tokens[id_b]) 
    for id_b in agent_ids if id_a != id_b
]

The script recalculates Jaccard similarities from scratch rather than referencing the previously populated similarity_matrix hash table, adding an extra $N(N - 1) = 552$ evaluations. While 828 set operations might appear trivial on paper, the underlying payloads turned this into a massive bottleneck.

Calling str(text).lower().split() across 24 distinct multi-thousand-token strings creates hundreds of thousands of intermediate string instances. Converting these arrays into hashable Python set structures triggers significant allocation overhead.

During nested set intersections (set_a.intersection(set_b)), the Python runtime repeatedly hashes and traverses large lookup tables in memory. The sheer volume of ephemeral objects triggered continuous Garbage Collection (GC) s, destroying CPU throughput inside the single-threaded CPython interpreter.

Beyond raw compute bottlenecks, the core premise proved semantically defective.

The Jaccard index measures purely lexical, surface-level token overlap:

$$J(A, B) = \frac{|A \cap B|}{|A \cup B|}$$

In complex LLM dialogue systems, agents frequently enter circular arguments while employing completely different phrasing, terminology, or syntactical structures (e.g., "We must redesign the REST contract" vs. "The API endpoint interface requires refactoring").

Because the lexical intersection was near zero, the algorithm reported false-positive context divergence (sim < 0.15). In an attempt to patch these false positives, we had layered additional outlier-detection heuristics onto the script, expanding execution complexity and accelerating the performance collapse.

This failed experiment highlights critical architectural constraints when building runtime monitors for multi-agent systems:

text-embedding-3-small, mini-LM models, or quantized on-device encoders) paired with Cosine Similarity or Approximate Nearest Neighbor (ANN) search. Treating complex semantic arbitration as a one-shot CLI text-manipulation script was an oversimplification of the problem space. The Asynchronous Semantic Deadlock Checker failed its operational requirements as a sub-10-second CLI tool and was officially shelved.

However, this failure provided an unambiguous architectural boundary: Reliable multi-agent oversight cannot be achieved through ad-hoc string comparisons. Monitoring multi-agent consensus requires an embedded vector-state pipeline, streaming sliding-window telemetry, and dedicated vector-distance indexing.

When designing guards against LLM deadlocks, do not settle for lexical shortcuts. Build your monitoring infrastructure on genuine embedding spaces from day one.

If this engineering log saved your production server (and your sanity), consider supporting our architecture on GitHub Sponsors.