Lemmalog: Turning LLM Memory into Program Analysis with Datalog

Maintaining a consistent state over long-term investigations is a primary failure mode for LLM agents. In complex tasks like vulnerability research, models often forget previously ruled-out hypotheses or continue reasoning from observations that have been disproven. Lemmalog addresses this by treating LLM memory not as a retrieval problem, but as a program analysis problem, using a Datalog engine to maintain a deterministic deductive state.

The Problem: State Decay in LLM Memory

Standard LLM memory systems typically rely on vector databases and semantic search (RAG). While effective for retrieving relevant past conversations, these systems struggle with "truth" and state updates. If an agent establishes that object_a points to object_b, and later discovers this is false, a vector database will simply store both contradictory statements. The LLM is then left to reconcile these contradictions in its prompt, often leading to hallucinations or the resurrection of dead hypotheses.

Lemmalog's Architecture: Separating Fuzzy and Deterministic Logic

Lemmalog splits the memory problem into two distinct components: a probabilistic front-end for extraction and a deterministic back-end for reasoning.

1. The Fuzzy Front-End (LLM)

The LLM is used as a parser to convert unstructured data—such as source code, debugger output, and natural language notes—into structured facts. For example, a statement like "LLDB shows that the freed object is later reused" is converted into formal facts: freed(object_a) and reused_as(object_a, write_target).

2. The Deterministic Back-End (Datalog)

Once facts are structured, Lemmalog uses Datalog, a declarative logic programming language, to derive new facts based on predefined rules. This ensures that conclusions are logically sound and automatically updated.

Key capabilities include:

• Incremental Evaluation: When an input fact changes, only the affected conclusions are updated, rather than rerunning the entire investigation.
• Automatic Retractions: If a fact used to derive a conclusion is removed, the conclusion is automatically invalidated unless it is supported by another independent derivation path.
• Provenance Tracking: The system maintains a dependency graph for every derived fact, allowing the agent to answer "why" a specific conclusion is true by tracing it back to its original observations.
• Temporal Validity: Facts are associated with validity intervals (e.g., viable(primitive_a) [10:14, 12:37)), allowing the system to track how knowledge evolved over time without maintaining contradictory states.

Performance Benchmarks

Lemmalog was tested against the LongMemEval and LoCoMo benchmarks to evaluate its ability to handle long-term conversational memory.

LongMemEval Results

Lemmalog achieved an F1 score of 0.463 +/- 0.010 and an accuracy of 0.575 +/- 0.004. While slightly behind some specialized memory systems like PropMem, it significantly outperformed full-context prompting (GPT-4.1), which scored 0.197 F1.

Crucially, Lemmalog reduced the context window requirements drastically. For LongMemEval, the answering model received approximately 2,700 tokens per question, compared to 104,000 tokens for the full-context approach—a 38x reduction in context size.

LoCoMo Results

On the larger LoCoMo benchmark (1,986 questions), Lemmalog achieved an F1 of 0.533 +/- 0.001, placing it third among dedicated memory systems. It performed particularly well in adversarial questions (0.707 F1) compared to full-context models (0.509 F1), as the structured memory could explicitly recognize the absence of a supporting fact rather than being misled by semantic similarity.

Comparison: Deductive State vs. Episodic Memory

Lemmalog proposes a hybrid architecture for agent memory that distinguishes between deductive state and episodic memory:

Feature	Deductive State (Lemmalog)	Episodic Memory (Vector DB)
Nature	Facts, Rules, Time	Fuzzy Context
Mechanism	Provenance & Retractions	Semantic Retrieval
Storage	Maintained State	Source Text
Strength	Logical Consistency, Truth	Relevance, Nuance

Community Insights and Counterpoints

Discussion among technical peers highlights both the potential and the historical context of this approach:

"LLMs should only really sit at the terminals of request fulfilment... Between those terminals, the work should be mechanical reasoning over some ontology or formal knowledge structure."

Some contributors noted that this approach mirrors "Good Old Fashioned AI" (GOFAI) and symbolic AI, warning that the system may eventually face the classic challenges of symbolic logic, such as the need for quantifiers and the difficulty of handling "fuzzy" or opinion-based information. Others suggested exploring Answer Set Programming (ASP) for more robust non-monotonic logic to handle the "unlearning" of facts.

Conclusion

Lemmalog demonstrates that maintaining a formal analysis state is more effective than increasing context windows for tasks requiring logical consistency and state tracking. By treating the LLM as a probabilistic parser for a deterministic Datalog engine, the system reduces token costs and prevents the resurrection of disproven hypotheses, providing a scalable path for long-term autonomous research agents.