PaperlayerView exact revision on arXiv

Source-linked AI summary

Quipu: A Governed Bitemporal Knowledge Graph Store

Steve Brown

arXiv:2608.16813v1cs.AIcs.DB

TL;DR

Knowledge-graph stores retain defaults designed for human curators even as software agents produce plausible, sometimes wrong facts at scale. Quipu reverses those defaults through gated, bitemporal, trust-aware governance, and its evaluations show evidence remains answerable exactly when warranted, with zero overclaim.

  • Problem

    Knowledge-graph stores retain defaults designed for human curators while software agents produce plausible, sometimes wrong facts at rates review cannot match.

  • Method

    Quipu combines gated writes, bitemporal governance facts, partitioned non-widening trust composition, and in-store signed audit evidence.

  • Results

    Every property-level governance question remained answerable exactly when evidence warranted it, with zero overclaim; the benchmark reconstructed 512 of 512 property cells.

  • Takeaways & Limitations

    The results support historical replay, recorded refusals, and safe trust composition without sacrificing answerability when the evidence warrants it.

  • Takeaways & Limitations

    The agent-arm evaluation covers one task, one model family, three trials per model, and uses the scripted scenario as its only quality oracle.

Abstract

from arXiv · show

Agents now write knowledge graphs, but knowledge-graph stores still carry defaults set when humans curated them: accept writes now and clean later, keep one time axis or none, treat every writer's facts as equally trustworthy, and leave governance to dashboards and middleware. These four defaults are individually convenient and jointly untenable under agent workloads. We present Quipu, an embeddable store that inverts all four: no fact enters except through a gate whose predicates evaluate the pending post-state; data, trust labels, verdicts, and the rules themselves are bitemporal; named graphs are the unit of authority and trust, composed under a lattice whose one invariant is that composition never widens; and the governance specification $Σ$, the trace, and signed verdicts are facts in the store they govern, making the audit $T \models Σ$ a query. We evaluate with Census, a deterministic multi-writer lifecycle whose single seeded run scores every research question against planted ground truth: the gated store ends with 0 of 6 planted defects versus 6 of 6 ungated; all 7 composition probes uphold the lattice contract; 50 of 50 satisfied verdicts re-derive faithfully as of their instant while all 50 would be misreported under a latest-only rule set; and the SARC reference checker agrees with the in-store audit verdict-for-verdict, differing only on coverage semantics. A recorded trace from a governed writer surfaces a live enforcement gap the audit names with its remediation. On DEMM-Bench, an external decision-evidence sufficiency benchmark, a content-only reading of the exported records answers all 512 property-level governance questions correctly with zero overclaim under all eight degradation conditions, while container-presence baselines overclaim on up to 87.5% of them -- and the run surfaced, and led us to close, a gap in what a denial's verdict attests.

1 Introduction

Agent-written knowledge graphs expose four legacy store defaults as liabilities: accept-then-clean validation, incomplete temporal history, equal treatment of writers, and perimeter governance. Quipu inverts these defaults through strict gated writes, bitemporal governance, authority-partitioned trust, and an in-store governance plane.

  • Motivation: Agent writers produce plausible, well-formed, sometimes wrong facts faster than review can process, turning conventional defaults into liabilities.The identified defaults include post-hoc validation, limited temporal tracking, equal treatment of writers, and perimeter policy.
  • Contribution: Quipu inverts all four defaults, making signed verdicts, trust labels, governance rules, and audit history permanent bitemporal facts.The inversions reinforce one another: verdicts become trustworthy, authority partitions enforce labels, governance-as-data makes audits decidable, and bitemporality preserves history.
  • Operating posture: Strict refusal of invalid, untagged, unauthorized, or policy-violating writes shifts retry work from curators to agents through structured feedback.The paper states that the retry loop converges in one revision (§8.6).
  • System: Quipu is a single-file, embeddable store combining a bitemporal EAVT log, three-valued writes, named-graph authority partitions, a machine-checked label lattice, and signed in-store governance.Its governance plane includes escalation, authority intersection, and deterministic audit.
  • Benchmark: Census provides a deterministic multi-writer lifecycle whose single seeded run measures all four inversions against planted ground truth, with repeatable manifests and a real governed-writer trace replay.The benchmark is presented alongside the GS1–GS6 design principles, which specify guarantees required before agent-written knowledge can be trusted.

2 Background and Requirements

The background frames governance as an architectural, auditable agent-loop concern and identifies gaps in bitemporal history and trust-aware graph composition. It therefore requires a store that gates writes, records decisions, narrows authority, prevents trust laundering, supports in-store audits, and reproduces historical decisions.

  • Governance by architecture: SARC makes constraints first-class specifications with predicates, verification points, responses, and four enforcement points in the agent loop.The enforcement points are a Pre-Action Gate, Action-Time Monitor, Post-Action Auditor, and Escalation Router.
  • Governance by architecture: SARC’s checker decides T |= Σ in O(|T| · |C|), but its reference artifact keeps Σ outside the governed system.The checker uses trace records of constraint times and does not access the model or its prompts.
  • Bitemporal data: Conventional bitemporal stores track transaction and valid time for facts, while trust annotations, policy decisions, and validation rules remain latest-only.This leaves historical governance questions about belief, trust, and requirements at a given time beyond the store’s model.
  • Named graphs and trust: SPARQL named-graph composition is silent union, so standard machinery neither refuses nor degrades compositions involving undeclared trust.Named graphs have long carried provenance and trust semantics, while information-flow lattices provide older foundations for authority reasoning.
  • Requirements: A governed multi-writer store must evaluate writes against their pending post-state, permanently record every gate decision, narrow delegated authority, prevent trust laundering, audit from stored contents, and reproduce past decisions.These requirements include recording refusals and applying the rules in force when each decision occurred.

3 Design Principles: the Governed Store

Quipu defines six interlocking principles that make governance enforceable, trustworthy, non-widening, auditable, and reproducible over time. Together, they replace accept-then-clean, flat trust, log-grepping, and latest-only governance with store-level guarantees.

  • Gated writes: Gated writes evaluate predicates against the pending post-state, preventing individually valid writes from becoming invalid in combination.Writes touching no governed target incur no policy-evaluation cost, preventing D1’s accept-then-clean debt.
  • Verdict permanence: Every allow, deny, and unknown outcome persists as a signed, time-indexed fact, including after rollback of the judged write.No signing identity means no verdict; signatures verify against a human-authored root of trust.
  • Partitioned authority and composition: Authority attaches to partitions, delegation narrows by intersection, and non-widening composition folds freshness and trust by meet while obligations fold by join.Empty intersections refuse, partial coverage fails enforcement floors, and undeclared values are not silently ordered.
  • In-store decidable audit: The governance specification Σ, trace T, and verdicts reside in the governed store, where T |= Σ is decidable in O(|T| · |C|).Violations are distinguished from incompleteness because they demand different responses.
  • As-of replay: As-of replay reproduces each governance decision using the facts, labels, and rules in force at its transaction.Latest-only shapes and policies cannot replay what was required, making mid-lifecycle amendments observable.
  • Interlocking principles: The principles interlock: permanent signed verdicts support gated writes, partitioned trust supports lattice enforcement, store-resident traces enable audits, and as-of replay makes every guarantee historical.GS6 makes the other guarantees historical rather than merely current.

4 Data Model

Quipu models knowledge as an append-only bitemporal fact log partitioned by named graphs, with three-valued operations that preserve history and support sound layered composition. Labels, graph bindings, and cross-store attachments are governed by explicit invariants, including non-widening composition and immutable attachment boundaries.

  • Bitemporal fact log: The substrate is an append-only bitemporal EAVT fact log whose records include entity, attribute, value, named graph, transaction, valid interval, and operation.Transaction time is carried by a transactions table recording actor and source; current state is the open-interval subset.
  • Operations: The three-valued operation distinguishes assert, retract, and tombstone, with retract preserving history and tombstone hiding a triple in composed views without mutating its underlying layer.Tombstone enables layered composition in a way Datomic-style logs and RDF do not.
  • Named graphs and overlays: Named graphs partition the log; overlay graphs bind once to committed parent branches, making rebinding an error and enabling nearest-overlay-wins resolution without trusting overlay claims.Committed graphs are self-rooted, while datasets name arbitrary graph-sets distinct from the branch tree.
  • Label lattice: Labels are bitemporal facts on freshness, trust, durability, and policy, and composition never widens: freshness and trust use meet, while obligations use join.The composed result is a (fold, coverage) pair with coverage in {Empty, None, Partial, Full}; Empty is distinct from None.
  • Composition across stores: Read-only cross-store attachment preserves existing query results, prevents host writes into attachments, and verifies and refuses attachments rather than migrating them.Term identifiers are globally unique by construction, using each store’s own allocation space, so opaque reference values require no query-time remapping.

5 The Governance Plane

Quipu makes governance executable and self-auditing: policies and verdicts are stored as facts, while writes are admitted only after claims evaluate the pending post-state. Denials roll back attempted data but preserve signed decisions, and the audit re-derives governance from the store’s own specification and trace.

  • Durable governance records: Every gate decision preserves a signed, attributed verdict after savepoint resolution, even when denial rolls back the attempted delta.The verdict seals the actor and principal chain through the evidence hash and signature.
  • Policy-gated writes: Policies are SHACL-validated facts, and the gate evaluates their claims against the staged pending post-state before admitting a write.Claims are indexed by target type, so writes touching no governed type run zero claims.
  • Escalation: Require-approval refusals mint durable decision requests bound to policy, target, evidence hash, and expiry, with the agent retrying rather than the engine waiting.A human decision bound to the same evidence hash enables the next attempt; rejection outranks approval, and expired or zero windows refuse.
  • Self-auditing governance: The audit reads Σ from the store and deterministically checks coverage, class-placement, outcome consistency, and attribution without using a model.Violation and incompleteness remain distinct: an ungoverned executable tool class is a violation without a reason, while an unattributed trace is incomplete.

6 Implementation

Quipu is an embeddable Rust crate built around a single SQLite file, with custom temporal SPARQL evaluation and interfaces for local and served use. Its measured engineering costs provide context rather than performance comparisons: storage grows linearly, while write-time SHACL cost is flat in delta size.

  • Implementation: ∼67 kLOC and 1,000+ tests characterize Quipu’s Rust implementation, packaged as a single SQLite file.The store is embeddable and can be served through CLI, REST, and MCP tool handlers.
  • Implementation: Custom SPARQL 1.1 evaluation operates directly over the fact log, adding valid-at, as-of-transaction, RDFS widening, and graph-scoped label reads.The evaluator exists because conventional engines assume mutable triple stores without temporal columns.
  • Engineering characterization: ∼8.3 KB per ingested episode shows linear storage growth from 1k to 20k episodes, while write-time SHACL cost is flat in delta size.The SHACL cost is dominated by a fixed per-write parse; the paper reports these measurements as engineering characterization, not comparative query-performance claims.

7 The Census Benchmark

Census is a deterministic, seeded multi-writer lifecycle that compares identical gated and ungated runs against planted ground truth, while exercising governance, composition, amendment, reload, and audit. Its reproducibility is measured directly, and a replay of five real governed-writer decisions tests the audit beyond the synthetic benchmark.

  • Benchmark design: Census runs the same scripted lifecycle with gates enabled and disabled, using deterministic writers and planted defects as its oracle.No LLM, judge, or rubric appears in the core loop; every metric is a count or latency.
  • Benchmark design: Six labeled defects are interleaved with 100 clean writes across three district graphs, authority grants, governance policies, corrections, composition probes, amendment, reload, and audit.The planted defects include authority, provenance, policy, post-state, and fabricated-predicate failures.
  • Composition: Seven lattice probes test degraded coverage, trust incompatibility, expiry, cross-set obligations, clean composition, bind-once overlays, and stable imported packs.The probes include clean compositions passing with zero false refusals and an undeclared member failing the coverage floor.
  • Reproducibility: Three consecutive repeat runs per (seed, arm) produce byte-identical manifests with one hash, and the external-checker export is byte-stable.A discovered absolute output path in an observed string was fixed, and scorers read the manifest rather than phase scripts.
  • External validity: Five genuine Pre-Action Gate decisions from a real governed writer—two denies and three allows—were replayed unmodified through the same audit.The decisions came from Yupana2’s enforce-mode pre-edit guard and covered a blast-radius scope.

8 Evaluation … 8.6 The agent arm: strictness borne by the writer

Quipu’s seeded Census evaluation tests governed-write cost, defect prevention, auditability, non-widening composition, bitemporal replay, and agent behavior. Across these tests, the gated design prevents planted defects, preserves governance distinctions and historical verdicts, and makes refusal-driven convergence depend on the gate rather than model capability.

  • 8 Evaluation: All numbers come from the deterministic seed-42 Census run, with byte-identical manifests across repeats and each research question scored against planted ground truth.The evaluation also includes an external decision-evidence sufficiency benchmark over exported records.
  • 8.1 RQ1 — does enforcement cost scale only with governed writes?: 1.3 ms median clean governed-type writes versus 2.7 ms compliant governed writes and 0.7 ms ungated-control writes show abstention is cheap only at the policy-gate scope.Authority intersection still runs on every graph-scoped write, including ungoverned writes.
  • 8.2 RQ2 — does the gated store end cleaner than the ungated one?: 0 of 6 planted defects remain in the gated arm versus 6 of 6 in the ungated control arm.Refusals identify missing provenance, authority chains, graph holdings, policy grounds, combined-state failures, or fabricated predicates.
  • 8.3 RQ3 — is the audit decidable in-store, and does an external checker agree?: The in-store audit preserves planted distinctions, reporting 1 violation and 1 incompleteness in dispatch inventory, versus 0 violations and 1 incompleteness in the five-record trace window.Against SARC, Quipu’s faithful export yields 168 coverage discrepancies, while verdicts agree verdict-for-verdict and placement also agrees.
  • 8.4 RQ4 — does composition never widen?: 7 of 7 composition probes uphold the lattice contract: undeclared members, cross-chain trust, expired labels, no-export obligations, rebinding, and imported packs never widen enforcement.Clean compositions pass the enforcement floor, while unsafe compositions are refused or degraded as specified.
  • 8.6 The agent arm: strictness borne by the writer: 12 of 12 agent trials fix every label and vocabulary refusal in one revision without inventing predicates, while authority refusals produce routing, abstention, evasion-caught, or evasion-landed behaviors.The weakest haiku attempts improved from 2/5 to full acceptance; three opus trials rejected workarounds as falsification.
  • 8.6 The agent arm: strictness borne by the writer: SARC-DQ finds defective evidence converted into costly actions at a rate flat across four model tiers spanning ∼15× in price, whereas this study’s convergence is attributed to the gate.The agent result is bounded by one task, one model family, three trials per model, and a scripted scenario oracle.

8.7 In the wild · 8.8 Evidence sufficiency against an external benchmark

The wild-trace audit exposed actionable enforcement and attribution gaps that were absent from the authored policy. On DEMM-Bench, content-level evidence reading avoided the overclaiming of container-presence baselines and drove a store change for denial attribution and verdict writer binding.

  • 8.7 In the wild: The recorded Yupana trace violated the shipped policy catalog with 2 violations and 6 incompleteness findings over 5 records.The violations concerned an unauthored blast-radius rule; incompleteness included unexercised constraints, undeclared placement, and partial runtime attribution.
  • 8.7 In the wild: The audit identified an enforcement gap: author locally enforced rules in the store so they can be audited, or stop enforcing them.The wild trace surfaced the same kind of unstaged enforcement gap that synthetic Census defects are designed to catch.
  • 8.8 Evidence sufficiency against an external benchmark: DEMM-Bench tests whether emitted records reconstruct eight decision-level properties under eight controlled degradation conditions, using Overclaim Rate as its lead diagnostic.The benchmark asks whether evidence suffices, rather than whether decisions were correct.
  • 8.8 Evidence sufficiency against an external benchmark: 87.5% of cases were overclaimed by trace-, ledger-, and schema-presence baselines because content degradation leaves every evidence container present.Quipu’s three evidence planes remain present even when their contents no longer support a required property.
  • 8.8 Evidence sufficiency against an external benchmark: A richer oracle, camayoc, is in progress to score agent-written facts against competency-question suites instead of the scripted scenario.This marks a limitation and planned replacement for the current evaluation setup.
  • 8.8 Evidence sufficiency against an external benchmark: Quipu’s records decide actor identity and action boundary because guard traces name the tool, target, graph, and principal chain, while signed verdicts name the policy and decision instant.Deleted evidence is detectable as absent, so sufficiency is not inferred from container presence.
  • 8.8 Evidence sufficiency against an external benchmark: The self-administered run uses the benchmark’s unmodified published construction oracle and supports rerunning the seeded census, export, degradation, and scoring chain.Independent readers can be substituted on the same manifests, and the claim extends only as far as reruns agree.
  • 8.8 Evidence sufficiency against an external benchmark: The benchmark exposed two evidence gaps, both closed by Q-VERDICT-ATTRIB: verdicts now bind writer attribution cryptographically, and denials retain the refusing actor.The attempted delta still does not survive rollback, while the improved-store numbers were re-verified end-to-end.

9 Related Work

Quipu extends prior work on bitemporal storage, named-graph provenance, validation, and agent-governance systems by moving time-indexed governance machinery into the store and enforcing it on the write path. It also targets LLM-driven knowledge-graph construction, where plausible fabricated structure motivates requiring construction tools to convince the store.

  • Bitemporal stores: Quipu extends bitemporal storage by time-indexing labels, verdicts, decisions, authority grants, and validation rules, making governance replay a query.Datomic established transaction time, while XTDB added valid time; Quipu’s distinction is the reach of bitemporality.
  • Named graphs, provenance, and information flow: Quipu operationalizes named-graph provenance and lattice-based information flow with explicit coverage, cross-chain name refusal, expiry-as-absence, and query-time floor enforcement.Its composition homomorphism is machine-checked rather than merely described.
  • Validation-centric stores: Quipu turns SHACL-like validation and policy claims into episode-scoped write-path gates, combining open-world shape validation with closed-world vocabulary policies.This catches fabricated terms that open-world validation silently accepts, a failure mode measured at scale by Rovai.
  • Governance for agentic systems: Quipu compiles SARC’s specification objects, enforcement points, and decidable audit into store-resident facts, gates, and signed verdicts, alongside three-valued and weakest-link approaches in agent runtimes.The related work identifies Quipu’s relocation of governance machinery into the store as its distinguishing move.
  • LLM-driven knowledge-graph construction: LLM-driven ontology-engineering work motivates strictness because agents generate plausible, well-formed, sometimes fabricated structures at rates no curation pass matches.Quipu builds the store that construction tools must convince, rather than another construction tool.

10 Conclusion

Quipu inverts four conventional knowledge-graph defaults by enforcing gated writes, bitemporality, partitioned trust, and in-store governance, evaluated through Census against planted ground truth and a recorded writer trace. The conclusion finds these controls practical and auditable while stating limits around performance, access control, and denial replay, and identifies controlled-agent evaluation and portable contracts as future work.

  • Contributions: Quipu inverts four conventional defaults: refuse at the gate, make everything bitemporal, compose partitioned trust without widening, and place governance inside the store.Census measures each inversion against planted ground truth and a real writer’s recorded trace.
  • Findings: Strictness is affordable when agents can read refusals and retry, while signed refusal facts preserve audit events and historical rules enable replay of requirements.The conclusion also states that safe composition need not be silent.
  • Boundaries: The paper makes no comparative query-performance claims, treats labels as distinct from access control, and replays denials as attestation checks rather than re-derivations.Refusal-by-rollback keeps the verdict while discarding the attempted write.
  • Future work: Future work targets controlled agent-arm experiments across tasks and models, plus a portable governed-store contract that elevates GS1–GS6 from principles to a benchmarkable specification.The proposed contract would extend SARC’s compilation.
Loading 2608.16813v1…