How I Built Relay: Shared Graph Memory & Multi-Agent Coordination on FalkorDB

The Illusion of Agent "Memory" in 2026

If you connect three autonomous LLM agents to a standard RAG pipeline (a flat vector database), you will quickly discover a hard truth: chat history is not memory, and cosine similarity is not understanding.

In production multi-agent environments—such as autonomous site reliability, incident triage, or code remediation—flat vector stores suffer from three catastrophic design flaws:

1. Temporal Amnesia: Vector search flattens documents into isolated similarity chunks, obliterating causality and chronological order. An agent searching for "database cluster status" retrieves contradictory fragments from three days ago and twenty minutes ago with equal similarity scores.

2. Coordination Collisions & Race Conditions: When five agents attempt to resolve alerts concurrently, they lack transactional coordination primitives. Without atomic locking, multiple agents claim the identical task or trigger conflicting interventions simultaneously.

3. Procedural Stagnation: When an agent executes a runbook that fails due to an environmental edge case, that failure disappears into a discarded context window. The next agent dispatched will blindly repeat the identical mistake.

4. Prompt Injection Data Leakage: In multi-tenant environments, soft-filtering namespaces via prompt instructions ("Only answer using Tenant A's data") crumbles under basic prompt injection attacks.

To solve this, we built Relay for the WeMakeDevs x FalkorDB Graph Hack (Track 02: Agent Memory and Coordination).

Relay replaces flat vector namespaces with a multi-tenant knowledge graph engine powered entirely by FalkorDB.

The Architecture: Five Native Graph Memory Layers

Rather than dumping unstructured tokens into a vector index, Relay structures multi-agent memory into five directed, queryable graph layers inside FalkorDB:

                        ┌───────────────────────────────┐
                        │      Relay Live Studio /      │
                        │      Showcase UI (D3.js)      │
                        └───────────────▲───────────────┘
                                        │ REST & SSE Streams

┌──────────────────────┐ ┌───────────────┴───────────────┐
│ Agent Fleet │ │ FastAPI Memory Engine │
│ (Triage, Remediator,│───>│ • Auth & Tenant Resolver │
│ Investigator, Comms) │ • 5 Graph Memory Controllers │
└──────────────────────┘ └───────────────┬───────────────┘
│ openCypher
┌───────────────▼───────────────┐
│ FalkorDB │
│ ┌─────────────┬─────────────┐ │
│ │control graph│tenant_acme │ │
│ ├─────────────┼─────────────┤ │
│ │shared_rnbook│tenant_globex│ │
│ └─────────────┴─────────────┘ │
└───────────────────────────────┘

1. Episodic Memory (Session -> Event -> Event)

An append-only, causal timeline of agent perceptions, decisions, and tool executions. Each event contains a deterministic sequence number and deduplication hash. When an agent crashes or disconnects, a replacement agent restarts the session and immediately re-traverses the event chain to restore full situational awareness.

1. Semantic Memory (Entity -> Fact with SUPERSEDES Lineage)

Infrastructure topology and operational facts modeled as entities (payments-svc, redis-cache) and facts. Crucially, every fact carries valid_from and valid_to epoch timestamps. When a fact changes—such as service ownership transferring from Team Core to Team Billing—Relay does not overwrite the node. It closes the previous fact's valid_to window, creates the new fact, and establishes a directed [:SUPERSEDES] edge.

This enables true bi-temporal time-travel: agents can query what the system believes now, or pass an as_of timestamp to reconstruct what was believed at 14:00 before the outage began.

1. Procedural Memory (Procedure -> Step with Laplace Ranking)

Operational runbooks are modeled as graph sequences. Candidate runbooks are ranked dynamically using Laplace smoothing, balancing proven success against exploration.

When a procedure fails (e.g., executing restart-redis v1 during a cache spike caused by an unannounced deploy), Relay forks the procedure into v2, links it via [:PREVIOUS_VERSION], and synthesizes a new mandatory precondition: "Check deploy history within 30 minutes before restarting cache."

1. Coordination Memory (Incident -> Task -> Approval)

Autonomous agents coordinate via an atomic Compare-and-Set (CAS) task board in openCypher. Tasks maintain lease expirations. If an agent dies mid-execution, its lease expires, and surviving teammates automatically reclaim the orphaned task. For destructive operations (rollback_deploy, restart_service), the graph enforces a mandatory [:REQUIRES]->(Approval) safety gate requiring human signoff before execution.

1. Insight Memory (Deterministic Provenance & Graph Centrality)

By querying graph reachability over [:DERIVED_FROM], [:SUPERSEDES], and [:EVIDENCE_FOR] edges, Relay provides a "Click-to-Explain" graph path that justifies any alert or decision with zero LLM hallucination. Furthermore, Relay runs native FalkorDB algorithms (CALL algo.pageRank('Entity', 'DEPENDS_ON')) to compute service centrality and calculate blast radius across complex microservices.

Deep Dive: The Cypher Queries Powering Agent Coordination

1. Atomic Compare-and-Set (CAS) Task Claiming

Eliminating race conditions between 20 autonomous agents requires sub-millisecond atomic transactions:

cypher
MATCH (t:Task {id: $task_id})
WHERE t.status = 'open'
OR (t.status = 'claimed' AND t.lease_expires_at < $now)
SET t.status = 'claimed',
t.owner = $agent_id,
t.version = t.version + 1,
t.lease_expires_at = $now + $lease_ms
RETURN t.id AS id, t.version AS version

Because FalkorDB executes this check-and-set in a single graph transaction, exactly one agent claims the node; all concurrent attempts receive null or conflicting version responses.

1. Bi-Temporal Fact Correction & Time-Travel cypher // Superseding a stale fact without destroying history MATCH (e:Entity {id: $entity_id}) OPTIONAL MATCH (e)-[:HAS_FACT]->(old:Fact {predicate: $predicate}) WHERE old.valid_to IS NULL SET old.valid_to = $now, old.status = 'closed' CREATE (e)-[:HAS_FACT]->(new:Fact { id: $fact_id, predicate: $predicate, value: $value, confidence: $confidence, valid_from: $now, valid_to: null, status: 'active', owner_agent: $agent_id }) MERGE (new)-[:SUPERSEDES]->(old) RETURN new.id AS id

Querying point-in-time beliefs at any arbitrary millisecond ($as_of):

cypher
MATCH (e:Entity)-[:HAS_FACT]->(f:Fact)
WHERE f.valid_from <= $as_of AND (f.valid_to IS NULL OR f.valid_to > $as_of)
RETURN e.name AS service, f.predicate AS property, f.value AS historical_value

Why FalkorDB Was Critical to This Architecture

Sub-Millisecond Graph Traversal: FalkorDB’s low-latency execution allowed our agents to traverse 4-hop causal dependency paths in under 6 milliseconds, keeping agent tool calls fast and responsive.
Physical Multi-Tenancy: Instead of logical table filters, FalkorDB allows spinning up dedicated named graph instances per tenant (tenant_acme, tenant_globex). Cross-tenant graph traversal is syntactically and physically impossible.
Graph-Native Algorithms: Built-in algorithms like PageRank enabled instant topological centrality scoring without shipping graph structures over the wire to external network libraries.
Conclusion & What’s Next

Agent memory cannot remain a bag of unstructured vector embeddings. As autonomous agent fleets take over mission-critical infrastructure, they demand transactional guarantees, causal provenance, and adaptive procedural learning.

Relay proves that graphs are the natural data structure for agent cognition and coordination.

Code & Test Suite (94 passing tests): Github
Live Showcase & Interactive Studio: Built with FastAPI, D3.js, OpenVINO™ local LLM acceleration, and FalkorDB.