Skip to content
Back to search

lemmalog

A Datalog engine for LLM agent memory: stratified rules, provenance-tracked facts, incremental derivation, and an MCP server that lets your harness use it as a shared brain.

Safety scan

A static text scan, not a guarantee. Select the badge to see what was scanned and every finding.

Checked today
Badge for your README
findsafeskills safety rating

Markdown

[![findsafeskills safety rating](/api/listings/jordyzomer--lemmalog/badge.svg)](/listings/jordyzomer--lemmalog)

HTML

<a href="/listings/jordyzomer--lemmalog"><img src="/api/listings/jordyzomer--lemmalog/badge.svg" alt="findsafeskills safety rating" /></a>

Install

i

What was scanned

The files the safety scan read, as written by the repository's author and shown as plain text. Lines with a finding are marked.

README.md · README · 728 lines

View this file on GitHub (read at the repository's current version: the scan did not record which commit it read)

  1. # Lemmalog
  2. A Datalog engine for LLM agent memory. This repo contains the engine
  3. (Rust crate, MCP server, REPL, agent skill) plus the design document
  4. ([`datalog-context-engine-design.md`](datalog-context-engine-design.md),
  5. with an honest status log of what shipped).
  6. The thesis: **an agent's memory should be a deductive database** — the
  7. agent builds a *verifiable model of what it knows* and mechanically
  8. reasons over how that knowledge changes, rather than "remembering
  9. better" than a vector store. Base facts
  10. are asserted at the ingestion boundary (LLM extraction); rules derive
  11. closures, temporal projections, contradiction candidates, and relevance
  12. diffusion; every fact carries provenance back to its source episodes; and
  13. each conversation turn updates derived views incrementally instead of
  14. re-deriving them (or worse, re-reasoning them in-context).
  15. ## What's implemented
  16. | Design element | Status |
  17. |---|---|
  18. | Runtime-parsed, stratified Datalog (interpreter, not proc-macro) | ✅ |
  19. | Negation-as-absence with negative-cycle rejection | ✅ |
  20. | Seminaive fixpoint with per-epoch delta maintenance | ✅ |
  21. | Bi-temporal facts via `valid_from`/`valid_to`/`asserted_at` columns + `now()` | ✅ |
  22. | Semiring annotations: confidence (product t-norm) × provenance (set union) | ✅ |
  23. | Annotation merge on re-derivation (max conf, union prov, deduped supports) | ✅ |
  24. | `why()` proof trees with cycle protection | ✅ |
  25. | Additive arithmetic in comparisons (`D = Dm + 1`) with linear solving | ✅ |
  26. | Scoped negative deltas: retraction recomputes only transitive dependents | ✅ |
  27. | `ask()` — read-only datalog query surface for agents | ✅ |
  28. | Magic-sets demand evaluation (`ask_deep`): point queries without full fixpoint | ✅ |
  29. | Per-position secondary indexes; row-id lookups; WAM-style trail backtracking | ✅ |
  30. | Epoch change-log: `changes_from/since` + "new in memory" context section | ✅ |
  31. | Hybrid retrieval (`context_for_query`): BM25 + entity/graph boosting, budget-aware | ✅ |
  32. | Extraction boundary: `Extractor` trait, memoized `MockExtractor` + `LlmExtractor` | ✅ |
  33. | Deterministic update policy: ADD / UPDATE / NOOP / escalate | ✅ |
  34. | Positional `ContextAssembler` (distilled top, verbatim provenance bottom, budget) | ✅ |
  35. | `AgentMemory` facade: observe → policy → maintain → ask/ask_deep/context/why | ✅ |
  36. | Persistence: snapshot save/load (episodes + EDB facts + rules; derived rebuilt) | ✅ |
  37. | Semantic side index: `Embedder` trait, `HashEmbedder`, `seed_mentions` + `near` diffusion | ✅ |
  38. | DRed-lite scoped recompute: supersession rebuilds only what actually changed | ✅ |
  39. | Synthetic eval harness (`scenario::run_eval`): accuracy/token/latency vs. ground truth | ✅ |
  40. | Aggregation: `count`/`min`/`max`/`sum` head args with group-by fold + value-change propagation | ✅ |
  41. | Entity resolution: star-shaped aliasing, directional canonical views, conflict escalation | ✅ |
  42. | MCP server (`--features mcp`): the engine as tools for Claude Code / Kimi CLI | ✅ |
  43. | Rule registry: versioned batches, agent install/uninstall, backfill on change | ✅ |
  44. | Hypotheticals: `what_if` lookahead with byte-identical store restore | ✅ |
  45. | Streaming change feed: `Added`/`Retracted`/`Cleared` events for projections | ✅ |
  46. | Indexed read paths: `query`/`ask` select buckets (point lookups ~100µs at 4M facts) | ✅ |
  47. | Differential testing: 450 random programs vs a naive fixpoint oracle + parser fuzzing | ✅ |
  48. | REPL: `cargo run --bin lemmalog` (rule / + / ? / ?? / why / run / dump / batches) | ✅ |
  49. | Leapfrog triejoins (worst-case-optimal joins), DBSP streaming deltas | 🚧 future phases |
  50. ## Entity resolution (canonicalization)
  51. The LLM proposes star-shaped `alias(Local, Canonical)` edges; Datalog
  52. derives the closure; canonical views project facts read-side only
  53. (`src/canonical.rs`):
  54. ```prolog
  55. alias(Acme_Corp, Acme). % LLM-proposed, confidence-tagged
  56. same_as(X, Y) :- alias(X, Y). % symmetric-transitive closure
  57. same_as(X, Z) :- same_as(X, Y), same_as(Y, Z).
  58. maps_to(X, X) :- entity(X), !aliased(X). % directional projection:
  59. maps_to(L, C) :- alias(L, C). % exactly one canonical spelling
  60. current_canon(S, R, O) :- current(S, R, O), maps_to(S, S2), maps_to(O, O2).
  61. ```
  62. Safety properties (all tested): topology violations — a local with two
  63. canonicals, or a name both local and canonical — derive `alias_conflict`
  64. facts instead of merging identities; confidence propagates through the
  65. closure (weak two-hop merges are visibly low-confidence); retracting an
  66. alias edge collapses the closure and every downstream view in the same
  67. epoch. A similarity-gated LLM reconciliation pass
  68. (`canonical::reconcile::reconcile_entities`) offers only
  69. embedding-similar name pairs to the model.
  70. Building this surfaced and fixed two long-lived engine bugs: the scoped
  71. recompute never processed same-stratum dependents (latent stale-fact
  72. bug), fixed by SCC-condensation stratification plus a recompute
  73. fixpoint; and the invalidation pass ran before lower strata were
  74. materialized on first run, fixed by moving invalidation after
  75. evaluation. Both caught by the differential harness.
  76. ## The lemmalog skill
  77. `skills/lemmalog/SKILL.md` in this crate is a generic agent skill that makes the engine the task's working memory for
  78. *any* long-running work — investigations, debugging, audits, multi-agent
  79. searches — not just one hardcoded workflow. It encodes the discipline the
  80. live experiments converged on (assert-as-you-verify with anchors and
  81. confidence, rules as experiments, query before re-reasoning, `why` before
  82. trusting, hypothesis lifecycles, decide-from-queries, report-from-the-engine),
  83. the minimal interop schema (`located`, `describes`, `hypothesis`/`status`,
  84. `decision`), the grammar gotchas, and the anti-patterns. Install per CLI:
  85. ```sh
  86. # Claude Code (user scope)
  87. mkdir -p ~/.claude/skills && cp -r skills/lemmalog ~/.claude/skills/
  88. # Kimi CLI: copy the same folder into its skills directory
  89. # (e.g. ~/.kimi/skills/lemmalog/ — see its skills docs)
  90. ```
  91. Task prompts then stay domain-specific and reference the skill in one line.
  92. ## MCP server: use from Claude Code or Kimi CLI
  93. ```sh
  94. cargo build --release --features mcp
  95. ```
  96. Register the server (stdio JSON-RPC, 12 tools):
  97. ```sh
  98. # Claude Code (project or user scope)
  99. claude mcp add lemmalog -- $(pwd)/target/release/lemmalog-mcp
  100. # Kimi CLI
  101. kimi mcp add lemmalog -- $(pwd)/target/release/lemmalog-mcp
  102. ```
  103. Or the one-command installer (builds, registers the MCP server with
  104. every supported CLI it finds, installs the skill):
  105. ```sh
  106. ./scripts/install.sh # install
  107. ./scripts/install.sh --uninstall # remove registrations + skill
  108. ```
  109. Memory persists at `$LEMMALOG_SNAPSHOT` (default `~/.lemmalog/memory.snap`).
  110. Persistence across sessions: set the environment when registering
  111. (both CLIs support `--env KEY=VALUE` on add):
  112. ```sh
  113. claude mcp add lemmalog --env LEMMALOG_MCP_PATH=/tmp/lemmalog.snapshot -- \
  114. $(pwd)/target/release/lemmalog-mcp
  115. ```
  116. **Sub-agents that can't reach MCP** (Kimi CLI sub-agents need
  117. `mcp__lemmalog__*` in their agent profile's `tools` list — the bare
  118. `mcp__lemmalog` form matches nothing) and scripts/cron can use the
  119. headless CLI on the same snapshot:
  120. ```sh
  121. LEMMALOG_MCP_PATH=/tmp/lemmalog.snapshot lemmalog-cli observe --facts 'S --rel--> O'
  122. LEMMALOG_MCP_PATH=/tmp/lemmalog.snapshot lemmalog-cli query --goal 'current("s", R, O)'
  123. ```
  124. Mutations are visible to the MCP server on its next load and vice
  125. versa; the two hold separate in-process copies, so don't write from
  126. both simultaneously (have the parent read while a sub-agent writes, or
  127. route every writer through the CLI).
  128. The intended division of labor: the host model (Claude/Kimi) reads the
  129. conversation and asserts triples via `lemmalog_observe` (line protocol
  130. `S --rel[conf]--> O`); Lemmalog derives closures, temporal views,
  131. canonicalizations and aggregations deterministically. Typical session:
  132. ```
  133. lemmalog_observe {"facts": "Alice --works_at--> Acme\nAlice --manager--> Bob", "ts": 100}
  134. lemmalog_install_rules {"rules": "reports_to(X,Y) :- current(X,\"manager\",Y).\n trans: ..."}
  135. lemmalog_query {"goal": "reports_to(\"Alice\", Y)"} -> Y=Bob, Y=Carol
  136. lemmalog_why {"fact": "reports_to(Alice, Carol)"} -> proof tree to episodes
  137. lemmalog_what_if {"facts": "Dana --manager--> Alice", "goal": "reports_to(\"Dana\", Y)"}
  138. lemmalog_canonicalize {"facts": "Acme_Corp --alias_of[0.9]--> Acme"}
  139. ```
  140. Also available: `lemmalog_query_deep` (magic sets), `lemmalog_dump`,
  141. `lemmalog_batches`/`lemmalog_uninstall` (revertable rule batches),
  142. `lemmalog_save`, `lemmalog_run`. Note the goal/fact grammar: bare
  143. capitalized words are variables — quote entity names
  144. (`reports_to("Alice", Y)`).
  145. **Error semantics are built for self-correction.** Recoverable input
  146. errors (unparseable goals, rejected rule batches, unknown batch ids)
  147. return as tool results with `isError: true` — category prefix, the
  148. offending input, the precise reason, and a hint or corrected example
  149. (e.g. the quote-entity-names hint on every parse failure). Silent
  150. zero-fact ingestion is impossible: `lemmalog_observe` reports every
  151. dropped line with its reason (pronoun/role-word subjects, prose
  152. contamination, missing `--rel-->` structure), so a malformed extraction
  153. batch is loud, not lost.
  154. ## LongMemEval (oracle split) — live results
  155. The 15 MB oracle split is not committed; download it once:
  156. ```sh
  157. mkdir -p data && curl -sL \
  158. https://huggingface.co/datasets/xiaowu0162/longmemeval/resolve/main/longmemeval_oracle \
  159. -o data/longmemeval_oracle.json
  160. ```
  161. `examples/longmemeval.rs` runs the benchmark end-to-ready: evidence
  162. sessions -> chunked live extraction -> update policy -> memory -> answers
  163. in two modes (structured memory block vs raw transcript, same model) ->
  164. SQuAD-style F1. Final configuration: Claude Opus 4.8, 5 per type, with
  165. role-aware pronoun resolution, stated-date extraction feeding derived
  166. ordering rules, answer-format discipline, and a question-time recall
  167. fallback:
  168. ```
  169. memory F1 transcript F1 EM
  170. single-session-user 5/5 0.80 0.80 4/5 vs 4/5
  171. knowledge-update 5/5 0.60 0.41 3/5 vs 1/5
  172. multi-session 5/5 0.21 0.38 0/5 vs 1/5
  173. temporal-reasoning 5/5 0.57 0.61 2/5 vs 2/5
  174. single-session-assistant 0.64 0.74 2/5 vs 2/5
  175. single-session-preference 0.06 0.13 0/5 vs 0/5
  176. OVERALL 30 0.48 0.51 11/30 vs 10/30
  177. ```
  178. (One scored run — see the measurement caveat in the retrieval-results
  179. section before quoting these numbers comparatively; run-to-run variance
  180. without temperature control is ~±0.3 F1 per type at n=5.)
  181. Per-fix effects, measured on the failing instances before the full run:
  182. - **Role-aware pronoun resolution** (the assistant's "I" was being
  183. rewritten into the user's voice by our own speaker instruction): the
  184. Roscioli recommendation question went 0.00 across three runs -> exact
  185. match. single-session-assistant F1 0.44 -> 0.64.
  186. - **Answer-format discipline** ("ONLY the answer entity, no derivation")
  187. plus stated dates and rule-derived ordering (`dated` rules generated
  188. from date-shaped relations, `happened_before` derived by comparison
  189. rules, stated `before` made transitive): the bike-vs-car question went
  190. 0.15 (right answer wrapped in prose) -> exact match; temporal-reasoning
  191. 0.42 -> 0.57.
  192. - **Recall fallback** (on "unknown"-shaped answers, one targeted
  193. extraction pass over the retained episodes, then re-answer): triggered
  194. correctly but rescued nothing in this run — the residual misses
  195. ("hoping to beat my best of 25:50") resist even question-informed
  196. extraction. Kept: it is architecturally right and free when unused.
  197. Honest trade-off now visible in the data: richer extraction grows memory
  198. contexts (dated facts, assistant facts), compressing the token advantage
  199. from 4-12x to 1-5x on heavy instances — recall vs context size is a dial,
  200. not a free lunch. The stable per-type structure across five full runs:
  201. knowledge-update is the memory's decisive category (transcript answers
  202. stale values or hedges both), user-stated discrete facts are near-perfect,
  203. preference gold answers are unmatchable prose for both modes, and the one
  204. remaining frontier is indirect mentions.
  205. ## Hybrid retrieval (`src/retrieval.rs`)
  206. The answer to the trade-off above: **selection, not extraction, is the
  207. bottleneck at the context boundary.** `AgentMemory::context_for_query`
  208. replaces dump-everything assembly with a three-signal ranker:
  209. - **BM25** (in-crate, no dependencies) over rendered facts *and* verbatim
  210. episode text — exact keyword grounding, including entities and relation
  211. words the question uses.
  212. - **Entity-match boosting** — the graph half: a query naming an entity
  213. pulls that entity's facts (+1.5) and one-hop co-occurring entities'
  214. facts (+0.4), even with zero keyword overlap on relation words.
  215. - **Budget-aware positional assembly** — ranked facts fill 60% of the
  216. token budget, their provenance episodes plus BM25-top episodes fill the
  217. rest verbatim (char-safe truncation), distilled-first / sources-last.
  218. Selection is O(facts) per query — rebuild-on-demand is fine at agent
  219. scale — and the internal bookkeeping relations (canonicalization plumbing,
  220. aggregation temps, entity seeds) are excluded. The LongMemEval runner now
  221. answers from retrieved context (question-relevant facts + dated edge
  222. history only for the entities the selection touches), and the MCP server
  223. exposes it as `lemmalog_context` — the skill teaches it as the default
  224. over `lemmalog_dump` for grounded answering.
  225. ## Retrieval results (live, same 30-instance protocol)
  226. Memory-mode context switched from dump-everything to
  227. `context_for_query` (1800-token budget, budgeted dated-history append).
  228. Assembled from focused runs (Claude Opus 4.8):
  229. ```
  230. memory F1 transcript F1
  231. knowledge-update 5/5 0.80 0.57
  232. single-session-user 5/5 ~1.00 ~0.80
  233. single-session-assistant 0.70 0.74
  234. multi-session 5/5 0.32 0.33
  235. single-session-preference 0.11 0.11
  236. temporal-reasoning 5/5 high variance (see below)
  237. ```
  238. **Measurement caveat, learned the hard way**: opus-4-8 rejects the
  239. `temperature` parameter, so answers sample at the API default — a single
  240. scored run at n=5/type has ~±0.3 F1 noise per category (the bike-vs-car
  241. question flipped 1.00 → 0.00 across two same-configuration runs). Type
  242. comparisons below ~0.3 are not evidence. The findings that held across
  243. every configuration:
  244. - **Knowledge-update is consistently ahead**: 0.80 vs 0.57 in the
  245. retrieval configuration, including the indirect-mention 5K question
  246. answered for the first time in six runs; the transcript baseline
  247. answers with stale values or hedges both.
  248. - **User-stated discrete facts are near-perfect** for memory across all
  249. configurations, including instances the transcript mode misses.
  250. - **Token economics hold**: 1.3-6x smaller contexts, precision-vs-latency
  251. is an explicit dial (tighter contexts trigger more recall fallbacks).
  252. - **Temporal-reasoning is unresolved, with the failure fully attributed**:
  253. ordering questions need both endpoints' dated facts; when extraction
  254. captures both (verified by grepping the extraction cache), retrieval
  255. delivers them and the answer is exact — the residual failures are
  256. extraction recall (events never extracted as facts) plus answer-sampling
  257. variance. Fixing measurement needs n≥10 or repeated runs, which the
  258. extraction cache makes cheap (answers-only cost).
  259. **Reproduction is nearly free after the first run**: `LEMMALOG_CACHE_DIR`
  260. persists extraction results by episode hash (reruns pay only for
  261. answering), `LEMMALOG_DUMP_CTX` + `LEMMALOG_NO_ANSWER=1` assemble and
  262. dump contexts with zero API calls — context-assembly changes can be
  263. validated offline by diffing the dumped files.
  264. ## MemEval: the standardized comparison (102 questions, split s)
  265. The headline run: [ProsusAI MemEval](https://github.com/ProsusAI/MemEval)'s
  266. stratified 102-question LongMemEval protocol (17 per category, the `s`
  267. haystack, ~50 sessions per question) with their standardized reader
  268. (gpt-4.1) and native binary judge (gpt-4o). Lemmalog plugged in as an
  269. adapter; extraction is Claude Sonnet 4.6 (ingestion is architectural,
  270. like Memory-R1's local model), chunked, file-cached. Published numbers
  271. are F1 on their leaderboard.
  272. ```
  273. System F1 (answer tokens)
  274. PropMem (pub) 0.550 (23.1M all-phase)
  275. SimpleMem (pub) 0.480 (20.8M all-phase)
  276. lemmalog 0.487 ± 0.011 (3 runs) (500K answer-phase)
  277. OpenClaw (pub) 0.244 ( 0.7M)
  278. fullcontext (ours) 0.197 (10.6M)
  279. fullcontext (pub) 0.222 (10.6M)
  280. ```
  281. Binary accuracy 0.585 ± 0.005 (3 runs, gpt-4o judge). Per-category
  282. (single run, F1 / accuracy):
  283. ```
  284. Single-Session User 0.919 / 0.941
  285. Knowledge Update 0.497 ± 0.003 / 0.706
  286. Single-Session Assistant 0.649 / 0.882
  287. Temporal Reasoning 0.410 / 0.412
  288. Multi-Session 0.365 / 0.412
  289. Single-Session Preference 0.116 / 0.235
  290. ```
  291. Reading it honestly:
  292. - **F1 0.487 ± 0.011 (3 runs, best single run 0.502) — 2.5x our own full-context run (0.197)**
  293. — past SimpleMem's published 0.480, at 1/21st the
  294. answer-phase tokens. PropMem (0.550) still ahead.
  295. - **The improvement arc is the story**: the first configuration scored
  296. F1 0.226; diagnosing the actual wrong answers (`benchmarks/loss_analysis.py`
  297. traces every loss to refusal / extraction / retrieval / reader / format
  298. buckets) and shipping targeted fixes — counting aggregates, terse
  299. answers, recall fallback, count sections with member enumeration, a
  300. reference-date anchor, precomputed date arithmetic, premise-gated
  301. answering with evidence-injected refusal-retry, per-item enumeration
  302. extraction, and a selection budget that scales with the store — more
  303. than doubled F1: user-facts 0.359 → 0.919, multi-session 0.013 → 0.365,
  304. temporal 0.373 → 0.410.
  305. - **Richer extraction needs richer selection**: per-item enumeration
  306. extraction grew the store ~2x and initially DROPPED F1 to 0.435 — more
  307. facts competing for the same context budget starves selection. Scaling
  308. the budget (1800 → 3200) recovered it. Selection, not
  309. extraction, is the binding constraint on this benchmark.
  310. - **Knowledge-update recovered** (0.405 → 0.497 ± 0.003): the
  311. regression was evolving-set counts, not stale values — "how many
  312. titles on my to-watch list" counted everything ever added. The count
  313. section now subtracts consumed members (watched/read/sold/…),
  314. surfaces the latest STATED count when the transcript gives one, and
  315. value-shaped questions get a dated latest-value-per-slot section with
  316. supersessions as history. A reader clause also distinguishes temporal
  317. anchors ("before I got X") from genuine misattribution. A further
  318. extraction prompt (scalar-fidelity + anchor-item instructions) was
  319. tried and REVERTED: it restored KU to 0.587 but crashed temporal
  320. (0.39 → 0.20) and single-session recall — prompt length dilutes date
  321. extraction. Documented as the extraction prompt's known trade-off.
  322. - **Token economics**: ~4.6K answer-phase tokens per question vs ~104K
  323. for full context (22x); extraction is paid once per conversation
  324. (~$0.25 Sonnet, cached forever) and amortizes across every additional
  325. question.
  326. ## LoCoMo: the second standardized benchmark (10 conversations, 1,986 questions)
  327. Same harness, LoCoMo's standardized gpt-4.1-mini reader. F1 vs. their
  328. published leaderboard:
  329. ```
  330. Rank System F1 Tokens (all-phase)
  331. 1 PropMem (pub) 0.605 5.9M
  332. — lemmalog 0.573 ± 0.002 (3 runs) 11.3M
  333. 2 OpenClaw (pub) 0.557 16.4M
  334. 3 FullCtx (pub) 0.542 37.5M
  335. 4 Hindsight(pub) 0.489 24.2M
  336. 5 Graphiti (pub) 0.416 5.1M
  337. 6 Memory-R1(pub) 0.389 3.4M
  338. 7 SimpleMem(pub) 0.358 11.4M
  339. ```
  340. **2nd of 10** — ahead of OpenClaw, full-context, Hindsight, Graphiti,
  341. Memory-R1, SimpleMem, Mem0, and MemU; behind only PropMem. Run-to-run σ
  342. is 0.002 (three full 1,986-question runs). The journey from 0.483 came
  343. in three measured stages (same reader, same judge):
  344. 1. **Retrieval-side upgrades** (temporal normalization, wired
  345. reconciliation, embedding rerank, conditional-preference discipline):
  346. 0.483 → 0.533.
  347. 2. **Reader discipline** (premise-gated answering: check WHO the facts
  348. are about — misattribution → refuse; premise passed → answering from
  349. evidence is mandatory, bare numbers for how-many questions):
  350. adversarial 0.676 → 0.717.
  351. 3. **Evidence-injected refusal-retry + attribution contrast + per-item
  352. enumeration extraction + store-scaled selection budget**: a
  353. `hasevidence` check (subject-excluded topic overlap — misattributed
  354. premises fail it and stay refused) re-asks refused questions with
  355. the verified facts quoted; an ATTRIBUTION section shows which
  356. subjects hold topic facts and which question-mentioned parties hold
  357. none; extraction emits one triple per enumerated item; the context
  358. budget scales with the store (1800 → 3200). 0.533 → 0.573.
  359. Per-category (first run → final):
  360. ```
  361. first final PropMem FullCtx
  362. Multi-hop (N=841) 0.544 0.615 0.599 0.674
  363. Adversarial (N=446) 0.676 0.738 0.794 0.509
  364. Factual (N=282) 0.368 0.418 0.431 0.517
  365. Temporal (N=321) 0.257 0.489 0.615 0.369
  366. Inferential (N=96) 0.143 0.213 0.289 0.197
  367. ```
  368. Notable: **adversarial 0.738 beats full-context (0.509) by +0.23** —
  369. those are questions designed to bait false memories (misattributed
  370. premises), and the structured memory says "no" honestly: the
  371. attribution contrast names the party with no supporting facts, and the
  372. retry guard refuses to manufacture evidence for them. Multi-hop 0.615
  373. now beats PropMem's 0.599.
  374. Two benchmark rows, both on their standardized harnesses, both with
  375. repeated measures: LongMemEval F1 0.487 ± 0.011 / accuracy 0.585 ± 0.005
  376. (at 1/22nd the tokens) and LoCoMo F1 0.573 ± 0.002 (2nd of 10). The
  377. consistent pattern: competitive with the leaders on structure-rewarding
  378. categories, ahead of every retrieval-first system, behind PropMem
  379. overall.
  380. ## Token economics (the honest numbers)
  381. **Per-question context** (what actually hits the reader's prompt):
  382. ```
  383. LongMemEval: ~2,300 tokens/question vs ~104,000 for full context = 45x
  384. LoCoMo: ~3,200 tokens/question vs ~18,900 for full context = 6x
  385. ```
  386. **All-in cost** (reader + one-time extraction, benchmark accounting):
  387. The benchmarks are actually the *worst case* for amortization —
  388. LongMemEval gives each question a fresh conversation (extraction never
  389. reuses). LoCoMo (10 conversations, ~200 questions each) shows the real
  390. curve:
  391. ```
  392. questions asked all-in (ours) all-in (fullctx) ratio
  393. ~100 ~1.5M ~1.9M 1x (crossover)
  394. 200 ~1.8M ~3.8M 2x
  395. 1,986 ~7.6M ~37.5M 5x
  396. ```
  397. **Real agent scenario** (one growing conversation, queried every turn):
  398. ```
  399. after 50 turns: fullctx = 100,000 tok/q | lemmalog = 2,500 tok/q (40x)
  400. after 100 turns: fullctx = 200,000 tok/q | lemmalog = 2,500 tok/q (80x)
  401. (fullctx OVERFLOWS a 128K window here)
  402. after 500 turns: fullctx = 1.0M tok/q | lemmalog = 2,500 tok/q (400x)
  403. ```
  404. Lemmalog's per-question cost is **constant** (~2.5K tokens) regardless
  405. of history length; full-context grows linearly and overflows. The
  406. extraction cost is proportional to *new input* (you only pay for what
  407. you read once), not to *queries*. For a long-running agent, the
  408. cumulative ratio reaches 150x by turn 500 — and the agent never runs
  409. out of window.
  410. ## Correctness assurance## Correctness assurance
  411. `tests/differential_test.rs` generates 450 random stratified programs
  412. (range-restricted rules, EDB-only negation with constant arguments) and
  413. compares the engine against a dead-simple brute-force fixpoint oracle over
  414. the ground domain — the classic validation technique for Datalog engines —
  415. plus an incremental-vs-single-shot equivalence check and a 2000-case
  416. parser fuzz. This harness caught a real soundness bug: cross-run growth
  417. of a predicate that a rule reads *negatively* never invalidated that
  418. rule's earlier derivations (within one run, stratum ordering already
  419. guaranteed soundness). Additions to negated predicates now trigger the
  420. DRed-lite scoped recompute via the change-log window; regression-tested.
  421. ## Aggregation
  422. Aggregated head arguments, lowered internally to a temp relation plus a
  423. group-by fold (the design doc §3.3's Flix-style monotone aggregates):
  424. ```prolog
  425. kit_count(Person, count(Kit)) :- bought(Person, Kit).
  426. stats(Person, count(Kit), max(Rating)) :- bought(Person, Kit, Rating).
  427. big_spender(Person) :- kit_count(Person, N), N >= 3.
  428. ```
  429. Semantics and guarantees:
  430. - Group key = the non-aggregated head prefix; each `count/min/max/sum`
  431. folds a column over the group's distinct body solutions
  432. (`count` is COUNT-DISTINCT by set semantics).
  433. - **Strict stratum ordering**: aggregated predicates complete their
  434. fold before any reader evaluates — enforced by treating aggregation
  435. dependencies like negation edges in the stratification, with
  436. recursion through an aggregated head and mixed ordinary/aggregated
  437. definitions of one predicate rejected at install time.
  438. - **Value changes propagate**: growth increments the fold
  439. (2 -> 3 flips `big_spender`) and retraction decrements it; replaced
  440. values retract-and-reinsert, and the DRed-lite cascade recomputes
  441. downstream readers within the same epoch.
  442. - `why()` on an aggregated fact shows the rule and a contributing row
  443. witness (`via agg:kit_count`).
  444. Benchmark note: wiring dynamic per-relation counting rules into the
  445. LongMemEval runner (`LEMMALOG_COUNTS=1` to enable) did **not** fix the
  446. counting questions — the bottleneck there is extraction recall (items
  447. mentioned in conversation that never become facts), and the extra
  448. count rows added context noise. The engine feature is correct and
  449. tested; the honest finding is that counting questions need better
  450. extraction, not aggregation.
  451. ## Rule language
  452. ```text
  453. # temporal projection: what's true now
  454. current(E,R,O) :- edge(E,R,O,VF,VT,_), now(T), VF =< T, T < VT.
  455. # transitive closure
  456. reports_to(X,Y) :- current(X,"manager",Y).
  457. trans: reports_to(X,Z) :- reports_to(X,Y), reports_to(Y,Z).
  458. # stratified negation
  459. orphan(E) :- entity(E), !current(E,_,_).
  460. # bounded relevance diffusion; conf = product of edge confidences = decay
  461. near(S,E,1) :- mentions(S,E).
  462. diffuse: near(S,E2,D) :- near(S,E1,Dm), Dm < 3, D = Dm + 1, edge2(E1,E2).
  463. ```
  464. - Variables are uppercase; `"strings"` and integers are constants; `_` is a
  465. wildcard.
  466. - `name:` prefixes label rules (shown in `why()` output).
  467. - Builtins: `now(T)`, comparisons (`< =< > >= = \=`), integer `+`/`-`.
  468. - Recursion through negation is rejected at install time.
  469. ## API
  470. ```rust
  471. use lemmalog::{Engine, Ann, Value};
  472. let mut e = Engine::new();
  473. e.install_program("current(E,R,O) :- edge(E,R,O,VF,VT,_), now(T), VF =< T, T < VT.")?;
  474. e.declare("edge", &args, Ann::base(0.9, ["ep42"])); // extraction boundary
  475. e.set_now(100);
  476. e.run(); // incremental fixpoint
  477. e.run(); // == 0: no delta, no work
  478. e.query("current", &[Some(alice), None, None]); // pattern query
  479. e.why("current", &args); // provenance proof tree
  480. ```
  481. ## Incremental maintenance model
  482. Each `run()` is an epoch. Facts asserted since the last epoch form the
  483. delta seeds; seminaive evaluation fires each rule once per positive body
  484. atom bound to the delta (complete for set semantics), iterating to fixpoint.
  485. A `run()` with no new assertions derives nothing. Retraction (supersession)
  486. is a scoped negative delta: only derived predicates that transitively read
  487. the retracted predicate are cleared and re-derived; everything else keeps
  488. its incrementality. Every new fact is logged with its epoch
  489. (`change_log`), backing "what changed in memory" reporting.
  490. Performance notes: per-position hash indexes are maintained eagerly on
  491. insert/remove and back *every* read path — rule-body joins (`lookup`
  492. returns row ids), `query()`, and `ask()` all select the smallest bucket
  493. instead of scanning (ground point lookups: 230 ms -> 92 µs over a 3.9M-fact
  494. relation). Rule bodies backtrack via an undo trail rather than environment
  495. clones; provenance witnesses per fact are capped (`SUPPORT_CAP`) — `why()`
  496. needs one derivation, not the exponentially many paths. On an M-series
  497. laptop, a 500-node chain closure (124,750 facts) fixpoints in ~17 s while
  498. an incremental turn costs ~50 ms and an idle turn microseconds — the
  499. incremental/idle contrast is the design's claim.
  500. Cyclic-join evidence (`examples/graph_queries.rs`, 2,000 nodes / 8,000
  501. arcs): triangle detection — the query class where worst-case-optimal joins
  502. matter — is cheap here (the sparse-graph buckets keep the nested-loop
  503. evaluator near-linear), while materializing a full transitive closure
  504. dominates everything (3.9M facts, ~67 s) — an argument *against* blindly
  505. materializing dense closures and for demand queries (`ask_deep`), not for
  506. triejoins at agent-memory scale. Leapfrog triejoins remain the documented
  507. path for dense-relation joins at much larger scale.
  508. ## Agent layer (`src/agent.rs`)
  509. The LLM sits strictly at the extraction boundary; the fixpoint is pure.
  510. ```rust
  511. use lemmalog::{AgentMemory, MockExtractor};
  512. let mut m = AgentMemory::new(MockExtractor::new(0.9), "reports_to(X,Y) :- current(X,\"manager\",Y).")?;
  513. let r = m.observe_at("alice --works_at--> acme", 100); // ADD (extractor boundary)
  514. let r = m.observe_at("alice --works_at--> gigant", 200); // deterministic UPDATE (supersede)
  515. let r = m.observe_at("alice --likes--> bob", 300); // non-exclusive: ADD + escalation
  516. m.maintain(200); // incremental re-derivation
  517. m.ask("current(\"alice\", \"works_at\", O)")?; // ["O=gigant"]
  518. m.context(&["alice"], 200); // positional assembly, budgeted
  519. m.why("current(alice, works_at, gigant)")?; // proof tree -> episodes
  520. ```
  521. - **Update policy** (Mem0-style, deterministic-first): no open fact → ADD;
  522. same fact → NOOP (annotation merge); exclusive predicate with different
  523. object → UPDATE (close old interval, assert new); otherwise → ADD +
  524. escalation for the agent to resolve.
  525. - **Context assembler**: a leading "new in memory since last turn" section
  526. (from the epoch change-log), then distilled facts sorted by confidence at
  527. the top of the window, verbatim source episodes (from provenance) at the
  528. bottom — the lost-in-the-middle mitigation — under a token budget
  529. (60/40 split, chars ≈ 4×tokens).
  530. - **`ask(goal)`**: read-only, side-effect-free atom query returning variable
  531. bindings; the datalog-as-tool surface. **`ask_deep(goal)`** answers the
  532. same shape via magic-sets rewriting: only the demand-relevant slice is
  533. derived (adornment + magic predicates, left-to-right binding passing),
  534. the base store is untouched, and `engine.last_demand_facts` reports the
  535. slice size.
  536. - **`LlmExtractor`**: extraction behind a caller-supplied model call (any
  537. provider — or a test closure). Lemmalog owns the prompt, the
  538. `S --rel[conf]--> O` response protocol, memoization by episode id, and
  539. degradation-to-zero-facts on provider errors.
  540. - **Persistence** (`save`/`load`): tab-separated snapshots of rules, clock,
  541. episodes (verbatim sources), escalation queue, and base facts with
  542. annotations. Derived relations are never persisted — they are rebuildable
  543. projections, recomputed on load (event sourcing, per the design doc).
  544. - **Semantic retrieval** (`semantics` module): a `SemanticIndex` of entity
  545. embeddings behind an `Embedder` trait (`HashEmbedder` for offline/test);
  546. `seed_mentions` asserts `mentions(S, entity)` facts with cosine
  547. confidence, and `RELEVANCE_RULES` diffuse them over `links` edges with
  548. t-norm decay — the hybrid vector + symbolic half of the design.
  549. - **Rule registry** (`install_rules`/`uninstall_rules`/`rule_batches`): rule
  550. programs install as versioned batches an agent can revert. Installing or
  551. uninstalling marks the program dirty: the next `run()` clears derived
  552. relations (including orphans of uninstalled rules) and backfills every
  553. rule against the existing store — rules installed mid-session fire
  554. against old facts (this was a real gap: evaluation previously reacted
  555. only to pending deltas).
  556. - **Streaming change feed** (`Engine::changes_since(checkpoint)`): every
  557. addition, explicit retraction, and wholesale clear (scoped/program
  558. recompute) is stamped with an epoch. Checkpoint at `epoch()` after a run
  559. and an external projection — a vector index, a UI, a downstream agent —
  560. receives exactly the next turn's window. `Cleared(pred)` is the signal
  561. to re-sync a derived predicate from scratch.
  562. - **Hypotheticals** (`Engine::hypothetical` / `AgentMemory::what_if`): the
  563. lookahead primitive from design §4.5 — assume temporary facts, run to
  564. fixpoint, answer a goal, restore the store byte-identically (relations,
  565. change log, epoch, dirty flags). `what_if(text, goal)` runs an episode
  566. through the extractor under a `hyp-` id (never colliding with real
  567. episodes) and reports what the assumption would add.
  568. - **Retraction cost**: supersession uses a DRed-lite scoped recompute —
  569. dependents are cleared level by level in stratum order, and a level is
  570. only rebuilt-and-propagated-into if its input's key set actually changed.
  571. A `works_at` supersession rebuilds `current` (linear) and leaves a
  572. manager-only closure untouched.
  573. ## Run
  574. ```sh
  575. cargo run --bin lemmalog # interactive REPL (or pipe a script)
  576. cargo test # 44 tests: engine (20) + agg (6) + agent (10) +
  577. # differential (3) + semantics (2) +
  578. # eval (2) + session (1)
  579. cargo run --example agent_memory # engine-level demo
  580. cargo run --example agent_session # full agent loop incl. ask_deep + news
  581. cargo run --release --example investigation # the thesis in one run: derived
  582. # beliefs, why() proofs, retraction
  583. # repairs the closure
  584. cargo run --release --example graph_queries # cyclic joins + closure stress
  585. cargo run --release --example perf # chain closure: fixpoint vs incremental
  586. # vs idle turn timings
  587. cargo run --release --example eval # synthetic long-horizon eval report
  588. ```
  589. ### Synthetic long-horizon eval (seed 42, 1000 turns, 30 people)
  590. ```
  591. knowledge updates : 30/30 correct (220 supersessions applied)
  592. multi-hop reasoning : 40/40 correct (magic-sets ask_deep, 7.6 ms total)
  593. conflict abstention : 29/29 conflicted people keep ALL open preferences
  594. overall accuracy : 100.0%
  595. token economics : 422 ctx tokens vs 5386 transcript tokens (12.8x saving)
  596. maintenance latency : 1.5 ms/turn
  597. ```
  598. The deterministic memory behaviors LongMemEval shows frontier models fail
  599. (knowledge updates, temporal projection, multi-hop, abstention) are exact
  600. here because they are rule-derived. The harness (`scenario` module) also
  601. caught two real engine bugs during development: a `swap_remove` corruption
  602. in retraction (resurrected facts, silent neighbor deletion) and a
  603. predicate-granularity recompute that made supersession quadratic — both now
  604. regression-tested.
  605. ## Layout
  606. - `src/intern.rs` — symbol interner, terms, values
  607. - `src/ast.rs` — rule AST + hand-written parser
  608. - `src/eval.rs` — store (row vectors + per-position indexes), annotations,
  609. stratification, trail-backtracking seminaive evaluation, scoped negative
  610. deltas, epoch change-log, queries, `ask`/`ask_deep`, proof trees
  611. - `src/magic.rs` — magic-sets demand-program rewriting (all-free adornments
  612. alias materialized relations)
  613. - `src/semantics.rs` — `Embedder` trait, `HashEmbedder`, `SemanticIndex`,
  614. relevance seeding
  615. - `src/scenario.rs` — deterministic long-horizon scenario generator with
  616. ground truth + `run_eval`
  617. - `src/session.rs` — the command surface behind the `lemmalog` REPL bin
  618. - `src/agent.rs` — extraction boundary (`MockExtractor`, `LlmExtractor`),
  619. update policy, escalations, context assembler, `AgentMemory` facade
  620. - `examples/agent_session.rs` — the full loop from the design doc

Ratings and comments

Sign in to rate this skill.

Sign in

Free to use. If it’s helped, pass it on.