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

> Source: <https://dev.to/toai/why-our-cli-deadlock-detector-for-multi-agent-llms-timed-out-a-post-mortem-on-naive-jaccard-4caa>
> Published: 2026-10-11 00:48:07+00:00

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.

``` python
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

    # Pairwise similarity calculation: O(N^2)
    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)

    # Culprit isolation via mean similarity thresholding
    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](https://phenox.gumroad.com/l/ozvtlz) 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) pauses, 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.*