Choosing an Agent Memory Store: Vector DBs, Key-Value, and Graphs

Choosing the right memory store for your agent isn’t a one-size-fits-all decision. Vector databases excel at semantic search, key-value stores are fast for exact lookups, and graph databases shine at traversing relationships. Most production agents need a combination of all three. This guide helps you match memory patterns to the right backend.

Memory Store Landscape

Vector Databases

Best for: Semantic search, similarity matching, finding “related” memories.

How they work: Store high-dimensional vectors (embeddings) and support nearest-neighbor search.

Examples: Qdrant, Pinecone, Weaviate, Milvus, pgvector

# Vector DB: Find semantically similar memories
results = vector_store.search(
    query_embedding=[0.23, -0.45, ...],  # "How to optimize API performance"
    top_k=5
)
# Returns memories about latency, caching, database queries
# even if they don't use the exact words "API performance"

Strengths:

• Find relevant memories by meaning, not keywords
• Handle fuzzy, conceptual queries well
• Scale to millions of vectors

Weaknesses:

• Slower than key-value for exact lookups
• No native support for complex queries (joins, aggregations)
• Can be expensive at scale

Key-Value Stores

Best for: Fast exact lookups, caching, session state, simple metadata.

How they work: Map keys directly to values with O(1) lookup time.

Examples: Redis, DynamoDB, SQLite, BoltDB

# Key-Value: Get exact memory by ID
memory = kv_store.get("session:user123:current")
# Returns the specific session state instantly

# Or get by composite key
memory = kv_store.get("fact:preference:database-choice")
# Returns the stored fact about database preference

Strengths:

• Extremely fast (microsecond latency)
• Simple to implement and operate
• Great for caching and session state

Weaknesses:

• No semantic search capability
• Requires exact key knowledge
• Complex queries require application-level logic

Graph Databases

Best for: Relationship traversal, causal chains, exploring connections between memories.

How they work: Store nodes (entities) and edges (relationships), support graph traversal queries.

Examples: Neo4j, Amazon Neptune, ArangoDB

# Graph DB: Find all memories related to a decision
cypher_query = """
MATCH (decision:Decision)-[:LED_TO]->(outcome:Outcome)
WHERE decision.topic = 'database-selection'
RETURN decision, outcome
"""
# Returns the decision node and all outcomes it led to

# Or traverse the causal chain
cypher_query = """
MATCH path = (start:Memory)-[:CAUSED_BY*]->(origin:Memory)
WHERE start.id = 'memory_123'
RETURN path
"""
# Returns the full causal chain of how this memory came to be

Strengths:

• Natural representation of relationships
• Efficient traversal of connected data
• Support for complex graph queries

Weaknesses:

• Higher operational complexity
• Slower for simple lookups
• Steeper learning curve

Decision Matrix

Use Case	Best Backend	Why
”Find similar past conversations”	Vector DB	Semantic similarity search
”Get current session state”	Key-Value	Fast, exact lookup
”What decisions led to this outcome?”	Graph DB	Relationship traversal
”Cache recent query results”	Key-Value	Speed and simplicity
”Search memories by topic”	Vector DB	Semantic understanding
”Track cause-and-effect chains”	Graph DB	Natural graph traversal
”Store user preferences”	Key-Value	Simple get/set pattern
”Find all related memories”	Vector DB + Graph	Semantic + relational

Hybrid Architecture

Most production agents use a hybrid approach:

class HybridMemoryStore:
    def __init__(self):
        self.vector_store = QdrantVectorStore(
            collection_name="memories"
        )
        self.kv_store = Redis(url="redis://localhost:6379")
        self.graph_store = Neo4jGraph(
            url="bolt://localhost:7687"
        )

    async def store_memory(self, memory: Memory):
        # Store in all three backends
        embedding = await self.embed(memory.content)

        # Vector: for semantic search
        await self.vector_store.upsert(
            vector=embedding,
            payload=memory.model_dump()
        )

        # Key-Value: for fast exact lookups
        await self.kv_store.set(
            f"memory:{memory.id}",
            memory.model_dump_json(),
            ex=86400 * 30  # 30-day TTL
        )

        # Graph: for relationship tracking
        await self.graph_store.run_query(
            """
            CREATE (m:Memory {id: $id, content: $content})
            WITH m
            UNWIND $related_ids AS rel_id
            MATCH (r:Memory {id: rel_id})
            CREATE (m)-[:RELATED_TO]->(r)
            """,
            id=memory.id,
            content=memory.content,
            related_ids=memory.related_ids
        )

    async def recall(self, query: str, mode: str = "semantic"):
        if mode == "semantic":
            # Use vector store for meaning-based search
            embedding = await self.embed(query)
            results = await self.vector_store.search(
                vector=embedding,
                top_k=10
            )
        elif mode == "exact":
            # Use key-value for precise lookup
            results = [await self.kv_store.get(f"memory:{query}")]
        elif mode == "relational":
            # Use graph for relationship-based discovery
            results = await self.graph_store.run_query(
                """
                MATCH (m:Memory)-[:RELATED_TO*1..3]-(related:Memory)
                WHERE m.content CONTAINS $query
                RETURN related
                LIMIT 10
                """,
                query=query
            )
        elif mode == "hybrid":
            # Combine all three
            semantic = await self.recall(query, "semantic")
            relational = await self.recall(query, "relational")
            return self._deduplicate_and_rank(semantic + relational)

        return results

When to Use What

Start with Key-Value if:

• You need fast session state storage
• Your memory patterns are simple (get by ID, list by prefix)
• You’re prototyping and want minimal complexity

Add Vector DB when:

• You need semantic search (“find related memories”)
• Your queries are conceptual, not exact
• You have more than a few hundred memories

Add Graph DB when:

• You need to trace relationships (cause-effect, parent-child)
• Your data has complex interconnections
• You need to answer questions like “what led to this?”

Go Hybrid when:

• You have diverse memory patterns
• Different parts of your agent need different query types
• You’re building a production system that needs to be robust

Best Practices

1. Don’t over-engineer early — Start with the simplest backend that meets your needs. Add complexity only when you hit limitations.

2. Use each backend for what it’s good at — Don’t force vector search when you need exact lookup. Don’t use a graph database when a key-value store suffices.

3. Keep data synchronized — When using multiple backends, implement idempotent writes and eventual consistency to handle partial failures.

4. Monitor storage costs — Vector databases can be expensive at scale. Implement tiering: hot data in fast stores, cold data in cheaper storage.

5. Plan for migration — Design your memory interface so you can swap backends without changing application code.

Conclusion

The right memory store depends on your agent’s access patterns. Vector databases excel at semantic search, key-value stores dominate for exact lookups, and graph databases are unmatched for relationship traversal. Most production agents benefit from a hybrid approach that combines all three. Start simple, measure your actual access patterns, and add complexity only when you need it.

References:

• LlamaIndex Vector Store Integrations
• LlamaIndex Key-Value Stores