A Datalog engine for LLMs: turning agent memory into incremental program analysis

During long vulnerability-research sessions with LLM agents, the author hit a recurring failure: the model would lose track of what had actually been established, revive ruled-out approaches, or keep reasoning from observations later shown to be false. Telling the model something is wrong rarely propagates — it doesn’t reliably drop the downstream conclusions that depended on the bad assumption. Conventional embed-and-retrieve memory systems store what was said but don’t maintain what is currently known, so the LLM must reconstruct valid state from a noisy transcript every time.

The fix reframes agent memory as a classic program-analysis problem. Facts (attacker controls object_a, object_a points to object_b, object_b is a kernel object) plus rules derive new facts (attacker can control a kernel object), and when an input fact is retracted, incremental evaluation invalidates only the affected conclusions instead of rerunning everything. This became Lemmalog, a Datalog engine that splits the work: the LLM handles the fuzzy translation of source, debugger output, and prose into structured facts, while the deterministic database maintains all consequences. Retraction is the hard part — a conclusion like ‘candidate 3 is exploitable’ may have multiple independent derivations, so the engine tracks how each fact was supported and only drops a conclusion when all its support is gone.

That dependency tracking yields a second payoff: provenance. Because Lemmalog knows why each derived fact is true, you can query the chain of observations and rules behind any conclusion — and if a supporting observation is retracted, dependent conclusions vanish automatically. It also counters a common LLM failure mode: when a model insists ‘we already established this pointer is attacker-controlled,’ you can check whether that fact has real provenance in the maintained state, and if none exists, it was never actually established. The broader point is that offloading knowledge maintenance from the model to a logic engine makes multi-hour agentic security work more trustworthy.