Content
# Lemmalog
A Datalog engine for LLM agent memory. This repo contains the engine
(Rust crate, MCP server, REPL, agent skill) plus the design document
([`datalog-context-engine-design.md`](datalog-context-engine-design.md),
with an honest status log of what shipped).
The thesis: **an agent's memory should be a deductive database** — the
agent builds a *verifiable model of what it knows* and mechanically
reasons over how that knowledge changes, rather than "remembering
better" than a vector store. Base facts
are asserted at the ingestion boundary (LLM extraction); rules derive
closures, temporal projections, contradiction candidates, and relevance
diffusion; every fact carries provenance back to its source episodes; and
each conversation turn updates derived views incrementally instead of
re-deriving them (or worse, re-reasoning them in-context).
## What's implemented
| Design element | Status |
|---|---|
| Runtime-parsed, stratified Datalog (interpreter, not proc-macro) | ✅ |
| Negation-as-absence with negative-cycle rejection | ✅ |
| Seminaive fixpoint with per-epoch delta maintenance | ✅ |
| Bi-temporal facts via `valid_from`/`valid_to`/`asserted_at` columns + `now()` | ✅ |
| Semiring annotations: confidence (product t-norm) × provenance (set union) | ✅ |
| Annotation merge on re-derivation (max conf, union prov, deduped supports) | ✅ |
| `why()` proof trees with cycle protection | ✅ |
| Additive arithmetic in comparisons (`D = Dm + 1`) with linear solving | ✅ |
| Scoped negative deltas: retraction recomputes only transitive dependents | ✅ |
| `ask()` — read-only datalog query surface for agents | ✅ |
| Magic-sets demand evaluation (`ask_deep`): point queries without full fixpoint | ✅ |
| Per-position secondary indexes; row-id lookups; WAM-style trail backtracking | ✅ |
| Epoch change-log: `changes_from/since` + "new in memory" context section | ✅ |
| Hybrid retrieval (`context_for_query`): BM25 + entity/graph boosting, budget-aware | ✅ |
| Extraction boundary: `Extractor` trait, memoized `MockExtractor` + `LlmExtractor` | ✅ |
| Deterministic update policy: ADD / UPDATE / NOOP / escalate | ✅ |
| Positional `ContextAssembler` (distilled top, verbatim provenance bottom, budget) | ✅ |
| `AgentMemory` facade: observe → policy → maintain → ask/ask_deep/context/why | ✅ |
| Persistence: snapshot save/load (episodes + EDB facts + rules; derived rebuilt) | ✅ |
| Semantic side index: `Embedder` trait, `HashEmbedder`, `seed_mentions` + `near` diffusion | ✅ |
| DRed-lite scoped recompute: supersession rebuilds only what actually changed | ✅ |
| Synthetic eval harness (`scenario::run_eval`): accuracy/token/latency vs. ground truth | ✅ |
| Aggregation: `count`/`min`/`max`/`sum` head args with group-by fold + value-change propagation | ✅ |
| Entity resolution: star-shaped aliasing, directional canonical views, conflict escalation | ✅ |
| MCP server (`--features mcp`): the engine as tools for Claude Code / Kimi CLI | ✅ |
| Rule registry: versioned batches, agent install/uninstall, backfill on change | ✅ |
| Hypotheticals: `what_if` lookahead with byte-identical store restore | ✅ |
| Streaming change feed: `Added`/`Retracted`/`Cleared` events for projections | ✅ |
| Indexed read paths: `query`/`ask` select buckets (point lookups ~100µs at 4M facts) | ✅ |
| Differential testing: 450 random programs vs a naive fixpoint oracle + parser fuzzing | ✅ |
| REPL: `cargo run --bin lemmalog` (rule / + / ? / ?? / why / run / dump / batches) | ✅ |
| Leapfrog triejoins (worst-case-optimal joins), DBSP streaming deltas | 🚧 future phases |
## Entity resolution (canonicalization)
The LLM proposes star-shaped `alias(Local, Canonical)` edges; Datalog
derives the closure; canonical views project facts read-side only
(`src/canonical.rs`):
```prolog
alias(Acme_Corp, Acme). % LLM-proposed, confidence-tagged
same_as(X, Y) :- alias(X, Y). % symmetric-transitive closure
same_as(X, Z) :- same_as(X, Y), same_as(Y, Z).
maps_to(X, X) :- entity(X), !aliased(X). % directional projection:
maps_to(L, C) :- alias(L, C). % exactly one canonical spelling
current_canon(S, R, O) :- current(S, R, O), maps_to(S, S2), maps_to(O, O2).
```
Safety properties (all tested): topology violations — a local with two
canonicals, or a name both local and canonical — derive `alias_conflict`
facts instead of merging identities; confidence propagates through the
closure (weak two-hop merges are visibly low-confidence); retracting an
alias edge collapses the closure and every downstream view in the same
epoch. A similarity-gated LLM reconciliation pass
(`canonical::reconcile::reconcile_entities`) offers only
embedding-similar name pairs to the model.
Building this surfaced and fixed two long-lived engine bugs: the scoped
recompute never processed same-stratum dependents (latent stale-fact
bug), fixed by SCC-condensation stratification plus a recompute
fixpoint; and the invalidation pass ran before lower strata were
materialized on first run, fixed by moving invalidation after
evaluation. Both caught by the differential harness.
## The lemmalog skill
`skills/lemmalog/SKILL.md` in this crate is a generic agent skill that makes the engine the task's working memory for
*any* long-running work — investigations, debugging, audits, multi-agent
searches — not just one hardcoded workflow. It encodes the discipline the
live experiments converged on (assert-as-you-verify with anchors and
confidence, rules as experiments, query before re-reasoning, `why` before
trusting, hypothesis lifecycles, decide-from-queries, report-from-the-engine),
the minimal interop schema (`located`, `describes`, `hypothesis`/`status`,
`decision`), the grammar gotchas, and the anti-patterns. Install per CLI:
```sh
# Claude Code (user scope)
mkdir -p ~/.claude/skills && cp -r skills/lemmalog ~/.claude/skills/
# Kimi CLI: copy the same folder into its skills directory
# (e.g. ~/.kimi/skills/lemmalog/ — see its skills docs)
```
Task prompts then stay domain-specific and reference the skill in one line.
## MCP server: use from Claude Code or Kimi CLI
```sh
cargo build --release --features mcp
```
Register the server (stdio JSON-RPC, 12 tools):
```sh
# Claude Code (project or user scope)
claude mcp add lemmalog -- $(pwd)/target/release/lemmalog-mcp
# Kimi CLI
kimi mcp add lemmalog -- $(pwd)/target/release/lemmalog-mcp
```
Or the one-command installer (builds, registers the MCP server with
every supported CLI it finds, installs the skill):
```sh
./scripts/install.sh # install
./scripts/install.sh --uninstall # remove registrations + skill
```
Memory persists at `$LEMMALOG_SNAPSHOT` (default `~/.lemmalog/memory.snap`).
Persistence across sessions: set the environment when registering
(both CLIs support `--env KEY=VALUE` on add):
```sh
claude mcp add lemmalog --env LEMMALOG_MCP_PATH=/tmp/lemmalog.snapshot -- \
$(pwd)/target/release/lemmalog-mcp
```
**Sub-agents that can't reach MCP** (Kimi CLI sub-agents need
`mcp__lemmalog__*` in their agent profile's `tools` list — the bare
`mcp__lemmalog` form matches nothing) and scripts/cron can use the
headless CLI on the same snapshot:
```sh
LEMMALOG_MCP_PATH=/tmp/lemmalog.snapshot lemmalog-cli observe --facts 'S --rel--> O'
LEMMALOG_MCP_PATH=/tmp/lemmalog.snapshot lemmalog-cli query --goal 'current("s", R, O)'
```
Mutations are visible to the MCP server on its next load and vice
versa; the two hold separate in-process copies, so don't write from
both simultaneously (have the parent read while a sub-agent writes, or
route every writer through the CLI).
The intended division of labor: the host model (Claude/Kimi) reads the
conversation and asserts triples via `lemmalog_observe` (line protocol
`S --rel[conf]--> O`); Lemmalog derives closures, temporal views,
canonicalizations and aggregations deterministically. Typical session:
```
lemmalog_observe {"facts": "Alice --works_at--> Acme\nAlice --manager--> Bob", "ts": 100}
lemmalog_install_rules {"rules": "reports_to(X,Y) :- current(X,\"manager\",Y).\n trans: ..."}
lemmalog_query {"goal": "reports_to(\"Alice\", Y)"} -> Y=Bob, Y=Carol
lemmalog_why {"fact": "reports_to(Alice, Carol)"} -> proof tree to episodes
lemmalog_what_if {"facts": "Dana --manager--> Alice", "goal": "reports_to(\"Dana\", Y)"}
lemmalog_canonicalize {"facts": "Acme_Corp --alias_of[0.9]--> Acme"}
```
Also available: `lemmalog_query_deep` (magic sets), `lemmalog_dump`,
`lemmalog_batches`/`lemmalog_uninstall` (revertable rule batches),
`lemmalog_save`, `lemmalog_run`. Note the goal/fact grammar: bare
capitalized words are variables — quote entity names
(`reports_to("Alice", Y)`).
**Error semantics are built for self-correction.** Recoverable input
errors (unparseable goals, rejected rule batches, unknown batch ids)
return as tool results with `isError: true` — category prefix, the
offending input, the precise reason, and a hint or corrected example
(e.g. the quote-entity-names hint on every parse failure). Silent
zero-fact ingestion is impossible: `lemmalog_observe` reports every
dropped line with its reason (pronoun/role-word subjects, prose
contamination, missing `--rel-->` structure), so a malformed extraction
batch is loud, not lost.
## LongMemEval (oracle split) — live results
The 15 MB oracle split is not committed; download it once:
```sh
mkdir -p data && curl -sL \
https://huggingface.co/datasets/xiaowu0162/longmemeval/resolve/main/longmemeval_oracle \
-o data/longmemeval_oracle.json
```
`examples/longmemeval.rs` runs the benchmark end-to-ready: evidence
sessions -> chunked live extraction -> update policy -> memory -> answers
in two modes (structured memory block vs raw transcript, same model) ->
SQuAD-style F1. Final configuration: Claude Opus 4.8, 5 per type, with
role-aware pronoun resolution, stated-date extraction feeding derived
ordering rules, answer-format discipline, and a question-time recall
fallback:
```
memory F1 transcript F1 EM
single-session-user 5/5 0.80 0.80 4/5 vs 4/5
knowledge-update 5/5 0.60 0.41 3/5 vs 1/5
multi-session 5/5 0.21 0.38 0/5 vs 1/5
temporal-reasoning 5/5 0.57 0.61 2/5 vs 2/5
single-session-assistant 0.64 0.74 2/5 vs 2/5
single-session-preference 0.06 0.13 0/5 vs 0/5
OVERALL 30 0.48 0.51 11/30 vs 10/30
```
(One scored run — see the measurement caveat in the retrieval-results
section before quoting these numbers comparatively; run-to-run variance
without temperature control is ~±0.3 F1 per type at n=5.)
Per-fix effects, measured on the failing instances before the full run:
- **Role-aware pronoun resolution** (the assistant's "I" was being
rewritten into the user's voice by our own speaker instruction): the
Roscioli recommendation question went 0.00 across three runs -> exact
match. single-session-assistant F1 0.44 -> 0.64.
- **Answer-format discipline** ("ONLY the answer entity, no derivation")
plus stated dates and rule-derived ordering (`dated` rules generated
from date-shaped relations, `happened_before` derived by comparison
rules, stated `before` made transitive): the bike-vs-car question went
0.15 (right answer wrapped in prose) -> exact match; temporal-reasoning
0.42 -> 0.57.
- **Recall fallback** (on "unknown"-shaped answers, one targeted
extraction pass over the retained episodes, then re-answer): triggered
correctly but rescued nothing in this run — the residual misses
("hoping to beat my best of 25:50") resist even question-informed
extraction. Kept: it is architecturally right and free when unused.
Honest trade-off now visible in the data: richer extraction grows memory
contexts (dated facts, assistant facts), compressing the token advantage
from 4-12x to 1-5x on heavy instances — recall vs context size is a dial,
not a free lunch. The stable per-type structure across five full runs:
knowledge-update is the memory's decisive category (transcript answers
stale values or hedges both), user-stated discrete facts are near-perfect,
preference gold answers are unmatchable prose for both modes, and the one
remaining frontier is indirect mentions.
## Hybrid retrieval (`src/retrieval.rs`)
The answer to the trade-off above: **selection, not extraction, is the
bottleneck at the context boundary.** `AgentMemory::context_for_query`
replaces dump-everything assembly with a three-signal ranker:
- **BM25** (in-crate, no dependencies) over rendered facts *and* verbatim
episode text — exact keyword grounding, including entities and relation
words the question uses.
- **Entity-match boosting** — the graph half: a query naming an entity
pulls that entity's facts (+1.5) and one-hop co-occurring entities'
facts (+0.4), even with zero keyword overlap on relation words.
- **Budget-aware positional assembly** — ranked facts fill 60% of the
token budget, their provenance episodes plus BM25-top episodes fill the
rest verbatim (char-safe truncation), distilled-first / sources-last.
Selection is O(facts) per query — rebuild-on-demand is fine at agent
scale — and the internal bookkeeping relations (canonicalization plumbing,
aggregation temps, entity seeds) are excluded. The LongMemEval runner now
answers from retrieved context (question-relevant facts + dated edge
history only for the entities the selection touches), and the MCP server
exposes it as `lemmalog_context` — the skill teaches it as the default
over `lemmalog_dump` for grounded answering.
## Retrieval results (live, same 30-instance protocol)
Memory-mode context switched from dump-everything to
`context_for_query` (1800-token budget, budgeted dated-history append).
Assembled from focused runs (Claude Opus 4.8):
```
memory F1 transcript F1
knowledge-update 5/5 0.80 0.57
single-session-user 5/5 ~1.00 ~0.80
single-session-assistant 0.70 0.74
multi-session 5/5 0.32 0.33
single-session-preference 0.11 0.11
temporal-reasoning 5/5 high variance (see below)
```
**Measurement caveat, learned the hard way**: opus-4-8 rejects the
`temperature` parameter, so answers sample at the API default — a single
scored run at n=5/type has ~±0.3 F1 noise per category (the bike-vs-car
question flipped 1.00 → 0.00 across two same-configuration runs). Type
comparisons below ~0.3 are not evidence. The findings that held across
every configuration:
- **Knowledge-update is consistently ahead**: 0.80 vs 0.57 in the
retrieval configuration, including the indirect-mention 5K question
answered for the first time in six runs; the transcript baseline
answers with stale values or hedges both.
- **User-stated discrete facts are near-perfect** for memory across all
configurations, including instances the transcript mode misses.
- **Token economics hold**: 1.3-6x smaller contexts, precision-vs-latency
is an explicit dial (tighter contexts trigger more recall fallbacks).
- **Temporal-reasoning is unresolved, with the failure fully attributed**:
ordering questions need both endpoints' dated facts; when extraction
captures both (verified by grepping the extraction cache), retrieval
delivers them and the answer is exact — the residual failures are
extraction recall (events never extracted as facts) plus answer-sampling
variance. Fixing measurement needs n≥10 or repeated runs, which the
extraction cache makes cheap (answers-only cost).
**Reproduction is nearly free after the first run**: `LEMMALOG_CACHE_DIR`
persists extraction results by episode hash (reruns pay only for
answering), `LEMMALOG_DUMP_CTX` + `LEMMALOG_NO_ANSWER=1` assemble and
dump contexts with zero API calls — context-assembly changes can be
validated offline by diffing the dumped files.
## MemEval: the standardized comparison (102 questions, split s)
The headline run: [ProsusAI MemEval](https://github.com/ProsusAI/MemEval)'s
stratified 102-question LongMemEval protocol (17 per category, the `s`
haystack, ~50 sessions per question) with their standardized reader
(gpt-4.1) and native binary judge (gpt-4o). Lemmalog plugged in as an
adapter; extraction is Claude Sonnet 4.6 (ingestion is architectural,
like Memory-R1's local model), chunked, file-cached. Published numbers
are F1 on their leaderboard.
```
System F1 (answer tokens)
PropMem (pub) 0.550 (23.1M all-phase)
SimpleMem (pub) 0.480 (20.8M all-phase)
lemmalog 0.487 ± 0.011 (3 runs) (500K answer-phase)
OpenClaw (pub) 0.244 ( 0.7M)
fullcontext (ours) 0.197 (10.6M)
fullcontext (pub) 0.222 (10.6M)
```
Binary accuracy 0.585 ± 0.005 (3 runs, gpt-4o judge). Per-category
(single run, F1 / accuracy):
```
Single-Session User 0.919 / 0.941
Knowledge Update 0.497 ± 0.003 / 0.706
Single-Session Assistant 0.649 / 0.882
Temporal Reasoning 0.410 / 0.412
Multi-Session 0.365 / 0.412
Single-Session Preference 0.116 / 0.235
```
Reading it honestly:
- **F1 0.487 ± 0.011 (3 runs, best single run 0.502) — 2.5x our own full-context run (0.197)**
— past SimpleMem's published 0.480, at 1/21st the
answer-phase tokens. PropMem (0.550) still ahead.
- **The improvement arc is the story**: the first configuration scored
F1 0.226; diagnosing the actual wrong answers (`benchmarks/loss_analysis.py`
traces every loss to refusal / extraction / retrieval / reader / format
buckets) and shipping targeted fixes — counting aggregates, terse
answers, recall fallback, count sections with member enumeration, a
reference-date anchor, precomputed date arithmetic, premise-gated
answering with evidence-injected refusal-retry, per-item enumeration
extraction, and a selection budget that scales with the store — more
than doubled F1: user-facts 0.359 → 0.919, multi-session 0.013 → 0.365,
temporal 0.373 → 0.410.
- **Richer extraction needs richer selection**: per-item enumeration
extraction grew the store ~2x and initially DROPPED F1 to 0.435 — more
facts competing for the same context budget starves selection. Scaling
the budget (1800 → 3200) recovered it. Selection, not
extraction, is the binding constraint on this benchmark.
- **Knowledge-update recovered** (0.405 → 0.497 ± 0.003): the
regression was evolving-set counts, not stale values — "how many
titles on my to-watch list" counted everything ever added. The count
section now subtracts consumed members (watched/read/sold/…),
surfaces the latest STATED count when the transcript gives one, and
value-shaped questions get a dated latest-value-per-slot section with
supersessions as history. A reader clause also distinguishes temporal
anchors ("before I got X") from genuine misattribution. A further
extraction prompt (scalar-fidelity + anchor-item instructions) was
tried and REVERTED: it restored KU to 0.587 but crashed temporal
(0.39 → 0.20) and single-session recall — prompt length dilutes date
extraction. Documented as the extraction prompt's known trade-off.
- **Token economics**: ~4.6K answer-phase tokens per question vs ~104K
for full context (22x); extraction is paid once per conversation
(~$0.25 Sonnet, cached forever) and amortizes across every additional
question.
## LoCoMo: the second standardized benchmark (10 conversations, 1,986 questions)
Same harness, LoCoMo's standardized gpt-4.1-mini reader. F1 vs. their
published leaderboard:
```
Rank System F1 Tokens (all-phase)
1 PropMem (pub) 0.605 5.9M
— lemmalog 0.573 ± 0.002 (3 runs) 11.3M
2 OpenClaw (pub) 0.557 16.4M
3 FullCtx (pub) 0.542 37.5M
4 Hindsight(pub) 0.489 24.2M
5 Graphiti (pub) 0.416 5.1M
6 Memory-R1(pub) 0.389 3.4M
7 SimpleMem(pub) 0.358 11.4M
```
**2nd of 10** — ahead of OpenClaw, full-context, Hindsight, Graphiti,
Memory-R1, SimpleMem, Mem0, and MemU; behind only PropMem. Run-to-run σ
is 0.002 (three full 1,986-question runs). The journey from 0.483 came
in three measured stages (same reader, same judge):
1. **Retrieval-side upgrades** (temporal normalization, wired
reconciliation, embedding rerank, conditional-preference discipline):
0.483 → 0.533.
2. **Reader discipline** (premise-gated answering: check WHO the facts
are about — misattribution → refuse; premise passed → answering from
evidence is mandatory, bare numbers for how-many questions):
adversarial 0.676 → 0.717.
3. **Evidence-injected refusal-retry + attribution contrast + per-item
enumeration extraction + store-scaled selection budget**: a
`hasevidence` check (subject-excluded topic overlap — misattributed
premises fail it and stay refused) re-asks refused questions with
the verified facts quoted; an ATTRIBUTION section shows which
subjects hold topic facts and which question-mentioned parties hold
none; extraction emits one triple per enumerated item; the context
budget scales with the store (1800 → 3200). 0.533 → 0.573.
Per-category (first run → final):
```
first final PropMem FullCtx
Multi-hop (N=841) 0.544 0.615 0.599 0.674
Adversarial (N=446) 0.676 0.738 0.794 0.509
Factual (N=282) 0.368 0.418 0.431 0.517
Temporal (N=321) 0.257 0.489 0.615 0.369
Inferential (N=96) 0.143 0.213 0.289 0.197
```
Notable: **adversarial 0.738 beats full-context (0.509) by +0.23** —
those are questions designed to bait false memories (misattributed
premises), and the structured memory says "no" honestly: the
attribution contrast names the party with no supporting facts, and the
retry guard refuses to manufacture evidence for them. Multi-hop 0.615
now beats PropMem's 0.599.
Two benchmark rows, both on their standardized harnesses, both with
repeated measures: LongMemEval F1 0.487 ± 0.011 / accuracy 0.585 ± 0.005
(at 1/22nd the tokens) and LoCoMo F1 0.573 ± 0.002 (2nd of 10). The
consistent pattern: competitive with the leaders on structure-rewarding
categories, ahead of every retrieval-first system, behind PropMem
overall.
## Token economics (the honest numbers)
**Per-question context** (what actually hits the reader's prompt):
```
LongMemEval: ~2,300 tokens/question vs ~104,000 for full context = 45x
LoCoMo: ~3,200 tokens/question vs ~18,900 for full context = 6x
```
**All-in cost** (reader + one-time extraction, benchmark accounting):
The benchmarks are actually the *worst case* for amortization —
LongMemEval gives each question a fresh conversation (extraction never
reuses). LoCoMo (10 conversations, ~200 questions each) shows the real
curve:
```
questions asked all-in (ours) all-in (fullctx) ratio
~100 ~1.5M ~1.9M 1x (crossover)
200 ~1.8M ~3.8M 2x
1,986 ~7.6M ~37.5M 5x
```
**Real agent scenario** (one growing conversation, queried every turn):
```
after 50 turns: fullctx = 100,000 tok/q | lemmalog = 2,500 tok/q (40x)
after 100 turns: fullctx = 200,000 tok/q | lemmalog = 2,500 tok/q (80x)
(fullctx OVERFLOWS a 128K window here)
after 500 turns: fullctx = 1.0M tok/q | lemmalog = 2,500 tok/q (400x)
```
Lemmalog's per-question cost is **constant** (~2.5K tokens) regardless
of history length; full-context grows linearly and overflows. The
extraction cost is proportional to *new input* (you only pay for what
you read once), not to *queries*. For a long-running agent, the
cumulative ratio reaches 150x by turn 500 — and the agent never runs
out of window.
## Correctness assurance## Correctness assurance
`tests/differential_test.rs` generates 450 random stratified programs
(range-restricted rules, EDB-only negation with constant arguments) and
compares the engine against a dead-simple brute-force fixpoint oracle over
the ground domain — the classic validation technique for Datalog engines —
plus an incremental-vs-single-shot equivalence check and a 2000-case
parser fuzz. This harness caught a real soundness bug: cross-run growth
of a predicate that a rule reads *negatively* never invalidated that
rule's earlier derivations (within one run, stratum ordering already
guaranteed soundness). Additions to negated predicates now trigger the
DRed-lite scoped recompute via the change-log window; regression-tested.
## Aggregation
Aggregated head arguments, lowered internally to a temp relation plus a
group-by fold (the design doc §3.3's Flix-style monotone aggregates):
```prolog
kit_count(Person, count(Kit)) :- bought(Person, Kit).
stats(Person, count(Kit), max(Rating)) :- bought(Person, Kit, Rating).
big_spender(Person) :- kit_count(Person, N), N >= 3.
```
Semantics and guarantees:
- Group key = the non-aggregated head prefix; each `count/min/max/sum`
folds a column over the group's distinct body solutions
(`count` is COUNT-DISTINCT by set semantics).
- **Strict stratum ordering**: aggregated predicates complete their
fold before any reader evaluates — enforced by treating aggregation
dependencies like negation edges in the stratification, with
recursion through an aggregated head and mixed ordinary/aggregated
definitions of one predicate rejected at install time.
- **Value changes propagate**: growth increments the fold
(2 -> 3 flips `big_spender`) and retraction decrements it; replaced
values retract-and-reinsert, and the DRed-lite cascade recomputes
downstream readers within the same epoch.
- `why()` on an aggregated fact shows the rule and a contributing row
witness (`via agg:kit_count`).
Benchmark note: wiring dynamic per-relation counting rules into the
LongMemEval runner (`LEMMALOG_COUNTS=1` to enable) did **not** fix the
counting questions — the bottleneck there is extraction recall (items
mentioned in conversation that never become facts), and the extra
count rows added context noise. The engine feature is correct and
tested; the honest finding is that counting questions need better
extraction, not aggregation.
## Rule language
```text
# temporal projection: what's true now
current(E,R,O) :- edge(E,R,O,VF,VT,_), now(T), VF =< T, T < VT.
# transitive closure
reports_to(X,Y) :- current(X,"manager",Y).
trans: reports_to(X,Z) :- reports_to(X,Y), reports_to(Y,Z).
# stratified negation
orphan(E) :- entity(E), !current(E,_,_).
# bounded relevance diffusion; conf = product of edge confidences = decay
near(S,E,1) :- mentions(S,E).
diffuse: near(S,E2,D) :- near(S,E1,Dm), Dm < 3, D = Dm + 1, edge2(E1,E2).
```
- Variables are uppercase; `"strings"` and integers are constants; `_` is a
wildcard.
- `name:` prefixes label rules (shown in `why()` output).
- Builtins: `now(T)`, comparisons (`< =< > >= = \=`), integer `+`/`-`.
- Recursion through negation is rejected at install time.
## API
```rust
use lemmalog::{Engine, Ann, Value};
let mut e = Engine::new();
e.install_program("current(E,R,O) :- edge(E,R,O,VF,VT,_), now(T), VF =< T, T < VT.")?;
e.declare("edge", &args, Ann::base(0.9, ["ep42"])); // extraction boundary
e.set_now(100);
e.run(); // incremental fixpoint
e.run(); // == 0: no delta, no work
e.query("current", &[Some(alice), None, None]); // pattern query
e.why("current", &args); // provenance proof tree
```
## Incremental maintenance model
Each `run()` is an epoch. Facts asserted since the last epoch form the
delta seeds; seminaive evaluation fires each rule once per positive body
atom bound to the delta (complete for set semantics), iterating to fixpoint.
A `run()` with no new assertions derives nothing. Retraction (supersession)
is a scoped negative delta: only derived predicates that transitively read
the retracted predicate are cleared and re-derived; everything else keeps
its incrementality. Every new fact is logged with its epoch
(`change_log`), backing "what changed in memory" reporting.
Performance notes: per-position hash indexes are maintained eagerly on
insert/remove and back *every* read path — rule-body joins (`lookup`
returns row ids), `query()`, and `ask()` all select the smallest bucket
instead of scanning (ground point lookups: 230 ms -> 92 µs over a 3.9M-fact
relation). Rule bodies backtrack via an undo trail rather than environment
clones; provenance witnesses per fact are capped (`SUPPORT_CAP`) — `why()`
needs one derivation, not the exponentially many paths. On an M-series
laptop, a 500-node chain closure (124,750 facts) fixpoints in ~17 s while
an incremental turn costs ~50 ms and an idle turn microseconds — the
incremental/idle contrast is the design's claim.
Cyclic-join evidence (`examples/graph_queries.rs`, 2,000 nodes / 8,000
arcs): triangle detection — the query class where worst-case-optimal joins
matter — is cheap here (the sparse-graph buckets keep the nested-loop
evaluator near-linear), while materializing a full transitive closure
dominates everything (3.9M facts, ~67 s) — an argument *against* blindly
materializing dense closures and for demand queries (`ask_deep`), not for
triejoins at agent-memory scale. Leapfrog triejoins remain the documented
path for dense-relation joins at much larger scale.
## Agent layer (`src/agent.rs`)
The LLM sits strictly at the extraction boundary; the fixpoint is pure.
```rust
use lemmalog::{AgentMemory, MockExtractor};
let mut m = AgentMemory::new(MockExtractor::new(0.9), "reports_to(X,Y) :- current(X,\"manager\",Y).")?;
let r = m.observe_at("alice --works_at--> acme", 100); // ADD (extractor boundary)
let r = m.observe_at("alice --works_at--> gigant", 200); // deterministic UPDATE (supersede)
let r = m.observe_at("alice --likes--> bob", 300); // non-exclusive: ADD + escalation
m.maintain(200); // incremental re-derivation
m.ask("current(\"alice\", \"works_at\", O)")?; // ["O=gigant"]
m.context(&["alice"], 200); // positional assembly, budgeted
m.why("current(alice, works_at, gigant)")?; // proof tree -> episodes
```
- **Update policy** (Mem0-style, deterministic-first): no open fact → ADD;
same fact → NOOP (annotation merge); exclusive predicate with different
object → UPDATE (close old interval, assert new); otherwise → ADD +
escalation for the agent to resolve.
- **Context assembler**: a leading "new in memory since last turn" section
(from the epoch change-log), then distilled facts sorted by confidence at
the top of the window, verbatim source episodes (from provenance) at the
bottom — the lost-in-the-middle mitigation — under a token budget
(60/40 split, chars ≈ 4×tokens).
- **`ask(goal)`**: read-only, side-effect-free atom query returning variable
bindings; the datalog-as-tool surface. **`ask_deep(goal)`** answers the
same shape via magic-sets rewriting: only the demand-relevant slice is
derived (adornment + magic predicates, left-to-right binding passing),
the base store is untouched, and `engine.last_demand_facts` reports the
slice size.
- **`LlmExtractor`**: extraction behind a caller-supplied model call (any
provider — or a test closure). Lemmalog owns the prompt, the
`S --rel[conf]--> O` response protocol, memoization by episode id, and
degradation-to-zero-facts on provider errors.
- **Persistence** (`save`/`load`): tab-separated snapshots of rules, clock,
episodes (verbatim sources), escalation queue, and base facts with
annotations. Derived relations are never persisted — they are rebuildable
projections, recomputed on load (event sourcing, per the design doc).
- **Semantic retrieval** (`semantics` module): a `SemanticIndex` of entity
embeddings behind an `Embedder` trait (`HashEmbedder` for offline/test);
`seed_mentions` asserts `mentions(S, entity)` facts with cosine
confidence, and `RELEVANCE_RULES` diffuse them over `links` edges with
t-norm decay — the hybrid vector + symbolic half of the design.
- **Rule registry** (`install_rules`/`uninstall_rules`/`rule_batches`): rule
programs install as versioned batches an agent can revert. Installing or
uninstalling marks the program dirty: the next `run()` clears derived
relations (including orphans of uninstalled rules) and backfills every
rule against the existing store — rules installed mid-session fire
against old facts (this was a real gap: evaluation previously reacted
only to pending deltas).
- **Streaming change feed** (`Engine::changes_since(checkpoint)`): every
addition, explicit retraction, and wholesale clear (scoped/program
recompute) is stamped with an epoch. Checkpoint at `epoch()` after a run
and an external projection — a vector index, a UI, a downstream agent —
receives exactly the next turn's window. `Cleared(pred)` is the signal
to re-sync a derived predicate from scratch.
- **Hypotheticals** (`Engine::hypothetical` / `AgentMemory::what_if`): the
lookahead primitive from design §4.5 — assume temporary facts, run to
fixpoint, answer a goal, restore the store byte-identically (relations,
change log, epoch, dirty flags). `what_if(text, goal)` runs an episode
through the extractor under a `hyp-` id (never colliding with real
episodes) and reports what the assumption would add.
- **Retraction cost**: supersession uses a DRed-lite scoped recompute —
dependents are cleared level by level in stratum order, and a level is
only rebuilt-and-propagated-into if its input's key set actually changed.
A `works_at` supersession rebuilds `current` (linear) and leaves a
manager-only closure untouched.
## Run
```sh
cargo run --bin lemmalog # interactive REPL (or pipe a script)
cargo test # 44 tests: engine (20) + agg (6) + agent (10) +
# differential (3) + semantics (2) +
# eval (2) + session (1)
cargo run --example agent_memory # engine-level demo
cargo run --example agent_session # full agent loop incl. ask_deep + news
cargo run --release --example investigation # the thesis in one run: derived
# beliefs, why() proofs, retraction
# repairs the closure
cargo run --release --example graph_queries # cyclic joins + closure stress
cargo run --release --example perf # chain closure: fixpoint vs incremental
# vs idle turn timings
cargo run --release --example eval # synthetic long-horizon eval report
```
### Synthetic long-horizon eval (seed 42, 1000 turns, 30 people)
```
knowledge updates : 30/30 correct (220 supersessions applied)
multi-hop reasoning : 40/40 correct (magic-sets ask_deep, 7.6 ms total)
conflict abstention : 29/29 conflicted people keep ALL open preferences
overall accuracy : 100.0%
token economics : 422 ctx tokens vs 5386 transcript tokens (12.8x saving)
maintenance latency : 1.5 ms/turn
```
The deterministic memory behaviors LongMemEval shows frontier models fail
(knowledge updates, temporal projection, multi-hop, abstention) are exact
here because they are rule-derived. The harness (`scenario` module) also
caught two real engine bugs during development: a `swap_remove` corruption
in retraction (resurrected facts, silent neighbor deletion) and a
predicate-granularity recompute that made supersession quadratic — both now
regression-tested.
## Layout
- `src/intern.rs` — symbol interner, terms, values
- `src/ast.rs` — rule AST + hand-written parser
- `src/eval.rs` — store (row vectors + per-position indexes), annotations,
stratification, trail-backtracking seminaive evaluation, scoped negative
deltas, epoch change-log, queries, `ask`/`ask_deep`, proof trees
- `src/magic.rs` — magic-sets demand-program rewriting (all-free adornments
alias materialized relations)
- `src/semantics.rs` — `Embedder` trait, `HashEmbedder`, `SemanticIndex`,
relevance seeding
- `src/scenario.rs` — deterministic long-horizon scenario generator with
ground truth + `run_eval`
- `src/session.rs` — the command surface behind the `lemmalog` REPL bin
- `src/agent.rs` — extraction boundary (`MockExtractor`, `LlmExtractor`),
update policy, escalations, context assembler, `AgentMemory` facade
- `examples/agent_session.rs` — the full loop from the design doc
Connection Info
You Might Also Like
No recommendations available