Lemmalog: Using Datalog to Give LLM Agents Incremental, Fact‑Based Memory for Vulnerability Research

TL;DR

Lemmalog is a Datalog‑based memory layer for LLM agents that stores observations as structured facts, derives conclusions with logical rules, and automatically retracts invalidated facts, resulting in far smaller query contexts (2–3 k tokens vs. >100 k) and competitive benchmark scores on LongMemEval and LoCoMo.

The Problem: LLMs Lose Track of What Is Currently True

When an LLM agent assists with vulnerability research, it can correctly navigate large codebases and suggest attack vectors. However, after a few hours the model starts to forget which assumptions have been disproven. It may:

  • Re‑suggest an approach that was already ruled out.
  • Continue reasoning from a false observation.
  • Treat a corrected fact as still true because it appears earlier in the transcript.

Traditional memory solutions store the entire conversation or embed past messages and retrieve the most relevant snippets. This works for finding past information but does not guarantee that the retrieved facts reflect the current state of knowledge.

Reframing Memory as Program Analysis

Program analysis maintains a set of facts (e.g., calls(foo, bar)) and rules (e.g., transitive call reachability). A fixed‑point computation derives all possible conclusions, and incremental algorithms update only the affected facts when an input changes.

Applying this to LLM agents gives a clear goal:

  • Maintain a set of current facts.
  • Derive conclusions automatically.
  • Retract facts when new evidence disproves them, propagating the change to dependent conclusions.

Introducing Lemmalog

Lemmalog (https://github.com/JordyZomer/lemmalog) implements the above idea:

  1. Fuzzy front‑end – an LLM parses natural‑language inputs (debugger output, source code, notes) into atomic facts.
  2. Deterministic back‑end – a Datalog engine stores those facts, applies user‑defined rules, and computes derived facts.
  3. Incremental updates – adding a fact triggers forward inference; removing a fact triggers backward retraction, preserving any still‑valid derivations.
  4. Provenance tracking – each derived fact records the exact chain of supporting facts and rules, enabling "why?" queries.
  5. Temporal intervals – facts can be annotated with validity windows, allowing queries such as "Is primitive_a viable now?" and "Why did we think it was viable earlier?".

Handling Retractions and Multiple Derivations

A Datalog engine must know why a fact is true. Consider:

a.
b.
c :- a.
c :- b.

If a is removed, c remains true because b still derives it. Lemmalog tracks all derivation paths, so removal only eliminates conclusions whose last supporting fact disappears.

This mirrors vulnerability research where a candidate exploit may have several independent primitives; the candidate stays viable until all supporting primitives are invalidated.

Provenance: Asking "Why?"

Because Lemmalog records dependency graphs, a user can request the justification for any derived fact. Example output:

candidate_3_is_exploitable
|
+-- attacker_controls_pointer
|   |
|   +-- observation_41
+-- pointer_reaches_target
+-- observation_57
+-- rule_12

If observation_41 later proves false, the system automatically retracts the top‑level conclusion.

Temporal Facts and Validity Intervals

Facts can change over time without being outright deleted. Lemmalog represents this as:

viable(primitive_a) [10:14, 12:37)
not_viable(primitive_a) [12:37, ...)

Queries can ask about the current state or the historical reasoning that led to a past decision, all without storing contradictory facts in the same logical world.

Why Not Just a Vector Database?

Vector stores excel at retrieving relevant past snippets, but they cannot:

  • Detect that a retrieved fact has been retracted.
  • Propagate the impact of a retraction to dependent conclusions.
  • Answer "what is currently true?" without additional logic.

Lemmalog solves the second problem, while a vector store can still be used for the first (semantic retrieval of raw snippets). The two layers complement each other and are often combined in practice.

Benchmark Evaluation

LongMemEval (102 questions)

Metric Lemmalog PropMem SimpleMem Full‑Context GPT‑4.1
F1 0.463 ± 0.010 0.550 0.480 0.197
Accuracy 0.575 ± 0.004 – – –
Tokens per query ~2.7 k – – ~104 k

Knowledge‑Update (the category most similar to vulnerability research) scored 0.579, beating PropMem (0.528) and far exceeding full‑context (0.202).

LoCoMo (1,986 questions)

System F1
PropMem 0.605
OpenClaw 0.557
Full‑Context 0.542
Lemmalog 0.533 ± 0.001
Hindsight 0.489
Graphiti 0.416
Memory‑R1 0.389
SimpleMem 0.358

Lemmalog ranks third among dedicated memory systems, while using ~6× fewer tokens per query (3.4 k vs. 18.9 k).

Lessons Learned from the Benchmarks

  • Entity resolution – canonicalizing mentions (e.g., “Honda Civic” vs. “the Civic”) prevented spurious separate facts.
  • Date handling – converting extracted dates to comparable integers fixed a major temporal‑reasoning bug.
  • Aggregation visibility – counting lines were being filtered out by an over‑aggressive stemmer; exposing them restored correct answers.
  • Reader instruction – an over‑strict “refuse if no single fact contains the answer” caused many false negatives; separating “unsupported premise” from “requires aggregation” fixed it.

All improvements were engineering‑level fixes, not model scaling.

Front‑End Matters More Than You Think

The biggest performance jumps came from better information extraction and entity reconciliation, not from a smarter Datalog evaluator. Accurate parsing of natural language into the right predicates is the bottleneck; once the facts are clean, the logical engine does the heavy lifting for free.

Where the Approach Still Falls Short

  • Conditional or probabilistic knowledge – pure Datalog is monotonic; nuanced statements like “prefer quiet restaurants unless traveling with friends” lose nuance when flattened.
  • Inference / soft reasoning – Lemmalog’s F1 on LoCoMo’s Inferential category (0.164) lags behind PropMem (0.289). Adding conditional rules or hybrid fuzzy‑logic layers could bridge this gap.
  • Multi‑session extraction – failures were often due to missing facts rather than faulty reasoning; improving the extractor’s coverage is essential for real‑world long‑running agents.

Architectural Overview

LLM (fuzzy front‑end) ──► extract facts ──► Lemmalog (Datalog engine)
      ▲                                 │
      │                                 ▼
   natural language ◄─── render facts & provenance ──► answer generation
  • Agent memory = structured facts + provenance.
  • Episodic memory = original snippets, embeddings, BM25/graph boosts.
  • Query path = retrieve relevant facts → run a tiny Datalog slice → let the LLM turn the result back into natural language.

Community Reactions (selected HN comments)

"LLMs should sit at the terminals of request fulfilment; the middle layer should be a rigorous representation like Datalog." – @sim04ful

"I tried indexing Claude notes in SQLite and only querying what the model needs; Datalog looks like a great next step." – @akkad33

"This mirrors older AI attempts (Cyc, knowledge graphs) but with a modern LLM front‑end for fuzzy extraction." – @keeda

"The biggest pain point is removing information; Lemmalog’s explicit retraction solves a problem I see daily with Claude forgetting disproved facts." – @iamflimflam1

These comments reinforce that the community sees the separation of fuzzy extraction and deterministic reasoning as a promising direction.

Token Savings Over Time

Turns Full‑Context Tokens/query Lemmalog Tokens/query
50 ~100 k ~2.5 k
100 ~200 k ~2.5 k
500 ~1 M ~2.5 k

Because Lemmalog’s query size stays constant, it scales to arbitrarily long investigations without hitting context‑window limits.

Conclusion

Lemmalog demonstrates that program‑analysis techniques—facts, rules, incremental fixed‑point computation, and provenance—can replace naïve transcript replay for LLM agents. The system:

  • Keeps the current state accurate by automatically retracting invalidated facts.
  • Provides cheap, explainable queries with orders‑of‑magnitude fewer tokens.
  • Improves knowledge‑update performance on standardized memory benchmarks.

The results are not yet state‑of‑the‑art (PropMem still leads overall), but the gains come from engineering concrete CS solutions rather than larger models. The next step is to run Lemmalog in a real, multi‑hour vulnerability investigation and measure whether it truly prevents resurrected dead hypotheses and reduces hallucinated relationships.

The source code is available at https://github.com/JordyZomer/lemmalog.

Sources

Related