TGMS — Agent-Native Bi-Temporal Graph Management System

A temporal graph database whose query surface is built for LLM agents — and whose answers can be audited claim by claim.

Project page & blog: https://zxf-work.github.io/tgms/ · Paper: paper/main.pdf

LLM agents are unreliable at exactly the things temporal graph analytics requires: arithmetic, identifiers, and asserting only what the evidence shows. TGMS's answer is architectural — give the model no opportunity to do any of them:

• a bi-temporal property graph (valid time × transaction time) that distinguishes evolution ("the edge ended") from correction ("we were wrong"), so agents can answer "what did we believe on March 1?" — a question latest-state snapshots and the RAG configurations we evaluated cannot express. Bi-temporality itself is inherited, not invented here — it has a four-decade literature, a place in SQL:2011, and production databases built around it. We measure against the clearest of those, XTDB: fed the same operation stream, the two systems agree on believed state at 400 of 400 probe points, with TGMS 3.9–4.7× faster at correction-heavy ingest on 23–27× less disk (the head-to-head);
• and because a belief can be corrected after you've already acted on an answer, TGMS now tells you when that happened: tgms trace check reads a saved answer's dependency scope against the event log — no recompute, no store lock required — and returns FRESH / POSSIBLY_STALE / UNDECIDABLE, sound in the direction that matters (it never calls a stale answer fresh). Measured across two injection campaigns, 6,978 trials: 0 false-fresh verdicts of 898 changed answers, where the obvious cheap check — "did the correction touch a row in the stored result?" — is wrong on 47.4% of the same trials;
• and a saved result you want to keep, not just check, can now maintain itself: tgms artifact register/check/refresh turns it into a named, generation-numbered artifact — refresh recomputes only what you ask, the old generation stays byte-identical on disk, and a refresh propagates one hop to whatever else was built on top of it, even when that dependent's own scope was never touched. Measured across the M5 maintenance campaign: 0 false-fresh in 37,371 trials, 0 false-safe over 5,867 propagation decisions (99.0% resolved without recomputing anything), and a 600/600 pinned-answer exemption;
• 15 verified temporal operators (reachability over time-respecting paths, δ-motifs, snapshot diffs, burst detection, interval joins, grouped aggregation over edge events, and the belief log itself) — typed, deterministic, bounded, cost-guarded, exposed as tools (MCP or in-process); identifiers must come from a resolver, arithmetic from a compute operator;
• a Planner–Executor–Verifier loop: the LLM only plans and reports; plans are statically validated (including a grounding rule that makes fabricated identifiers impossible and output-field contracts that reject invented result paths), executed deterministically with content-addressed traces, and every claim in the written answer is machine-checked against the trace that produced it — including truncation taint, so "correct arithmetic over incomplete evidence" is caught too;
• a purpose-built native storage engine (Rust, PyO3): bi-temporal columnar segments, a temporal-CSR traversal index, group commit, and a single-writer / many-reader concurrency mode — 24.6 bytes per edge version, versus 78.4 on ClickHouse and 549.7 on PostgreSQL for the same 1M-event log.

Quickstart

pip install tgms
tgms demo

No GPU, no API key, no dataset download. tgms demo builds a small store of its own in a temp directory and runs the arc every TGMS answer follows: what the graph currently believes, what it believed before a correction landed, and the trace that backs both claims up. Clean environment to first temporal result: under 5 minutes.

Once you want your own graph data, the native test suite, the MCP server, or an agent wired to a real LLM, see Full setup below — this quickstart is deliberately the smallest possible first step, not a tour of the operator surface.

Next steps, in the order most people need them: bring your own temporal graph data · give TGMS to an agent over MCP · audit an answer · maintain derived results · what you can rely on across versions · what's coming

Does it work?

Three different questions, three different answers. All three are reported because the third is the least flattering.

1. Does the agent layer beat the alternatives? Dev-split campaign (CollegeMsg, open-source models served locally on one 24 GB GPU. "Answer accuracy" is normalized typed-answer accuracy — counts and values scored strictly, interval answers credited at IoU ≥ 0.5. Full receipts ship with the paper and the eval records in benchmarks/results-v1/):

• vs static-graph RAG: +36 points, paired-bootstrap 95% CI [0.18, 0.59]
• verifier fault injection: 500/500 injected false claims caught, 0 false positives; on the frozen campaign, 0 of 199 emitted answers contained an unsupported claim with gating (21 of 220 without it) — coverage is 199/282, so some of that is bought by declining to answer
• accuracy tracks planner capability where baselines stay flat: 13.8% / 34.0% / 62.8% at Qwen2.5 7B / 14B / 32B fp16, correction probes saturating at 100% at 32B

2. Is the engine competitive? Six systems answer one 13-query registry — TGMS native, TGMS-on-DuckDB, PostgreSQL, ClickHouse, Neo4j, Memgraph — with every cell hash-verified before it was timed:

The last row is the one we cannot close: ClickHouse keeps a factor of 2.2 on whole-window aggregation at both 1M and 10M, and it is a constant of the shape rather than something that grows with scale. Three rounds of profiling took that gap from 12× to 2.2× and each round found our own implementation rather than the workload. Single latency cells reproduce to about ±20% between days, which is stated everywhere they are quoted.

At 10M events the full query suite runs inside 1.76 GB of peak RSS, 16 concurrent readers get 10.2× the throughput of one, and a live writer costs those readers 0–3% of per-query latency.

3. Can it answer the questions people actually ask? This is the honest one, and it now has a sequel. 110 questions were written by people who saw a plain-language description of two public datasets and never saw the operator list. Of those, 94 were expressible under the fixed 15-operator catalog — 10 were expressible when the study was pre-registered. Of LDBC SNB's 41 read templates, 3 executed — the operator-execution axis (does a plan compile, load, admit and run at all), a lower bar than the stricter ECQR result-contract axis, which stood at 7 of 41 — and that number had not moved in eight sessions, because 35 of the 38 misses needed labelled multi-way pattern matching: a deliberately deferred design decision, not a missing operator.

That deferred decision shipped. TGIR, a 12-primitive compositional temporal-graph IR, now runs the entire 15-operator catalog as byte-identical leaves and additionally compiles some question shapes — including labelled multi-way pattern matching — into chains of those primitives. Both axes were forecast before TGIR was built, frozen before the first row was measured, and moved to exactly the predicted level: LDBC operator-execution coverage 3 → 24 of 41, independent-question coverage 94 → 102 of 110, delivered/predicted 29/29 on the full 52-row forecast (28/28 on the 51 scoreable rows — one row was excluded by name in the freeze because its canonical corpus carries no corrections to find), 0 over-deliveries, 0 misses.