🤖 AI

Quipu: A Governed Bitemporal Knowledge Graph Store

This paper introduces Quipu, an embeddable bitemporal knowledge graph store that enforces strict governance through gated writes, lattice-based trust composition, and self-auditing traces, demonstrating superior defect detection and decision-evidence reliability compared to conventional ungated systems.

Original authors: Steve Brown

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Steve Brown

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the modern digital world, a new kind of writer has emerged: software agents. These are programs that read documents, analyze code, and automatically build massive maps of facts known as knowledge graphs. For decades, these maps were curated by humans who could spot errors, verify sources, and decide what to keep. But when software agents write these maps, they do so at a speed and volume that human reviewers cannot match. They produce facts that look perfect but may be wrong, and they do it faster than any cleanup crew can fix them. The traditional systems designed to store this information were built for human patience; they accept everything first and hope to clean it up later. This approach, which worked when a human was in the driver's seat, creates a dangerous bottleneck when a machine is writing the story.

Researchers have now proposed a different way to handle this flood of automated writing. They argue that instead of accepting everything and hoping for the best, a storage system must be strict from the very beginning. It must act as a gatekeeper that refuses to let in anything that does not meet specific rules, and it must keep a permanent, unchangeable record of every single decision it makes, including the rejections. This new approach treats the rules themselves as part of the data, allowing the system to look back in time and see exactly what was required at any specific moment. By shifting the burden of strictness onto the software agents, which can instantly retry and correct their mistakes, the system ensures that the final map of facts remains trustworthy, even when written by machines.

Steve Brown and his team have built a system called Quipu to test this idea. They created a specialized storage engine that inverts the standard habits of database management. Instead of letting data in and cleaning it later, Quipu refuses to accept a fact unless it passes a strict set of checks against the state of the world it would create. If a piece of information violates a rule, the system rejects it immediately. Crucially, the system does not just say "no"; it writes down a signed, time-stamped record of that rejection, proving exactly why the fact was turned away. This record survives even if the attempt to write the fact is rolled back, ensuring that the history of what was tried and why it failed is never lost.

The researchers also redesigned how the system handles time and trust. In many databases, time is a simple line, and trust is a flat label applied to everything equally. Quipu treats time as two separate tracks: one for when the system learned something, and another for when that fact is actually true in the real world. It applies this same double timeline to the rules and the trust labels themselves. This means the system can answer questions like "what was considered trustworthy at this specific moment in the past?" or "what rule was in force when this decision was made?" It also organizes trust into separate, non-overlapping groups. When these groups are combined, the system ensures that the resulting trust level never accidentally becomes stronger than the weakest part of the group, preventing a weak or unverified source from boosting the credibility of the whole.

To prove that this strict approach works, the team ran a controlled experiment called Census. They created a scenario where multiple software writers tried to add facts to the system, deliberately planting six specific types of errors, such as missing information, unauthorized access, or fabricated details. They ran the same script twice: once with the strict gatekeeper active, and once with it turned off. The results were clear. The system without the gatekeeper accepted all six planted errors. The strict system, however, rejected every single one. It caught the unauthorized writes, the missing details, and the facts that were only valid when looked at in isolation but failed when combined with other facts. The system did this without slowing down the process for facts that were already correct, proving that strictness does not have to mean inefficiency.

The study also showed that the system can replay history perfectly. Because the rules and the data are both stored with a double timeline, the researchers could go back to any point in the experiment and ask, "What would the system have decided if this fact had been submitted right then?" The system answered correctly every time, even when the rules had changed in the meantime. This is something standard databases cannot do; they usually only remember the current rules, making it impossible to know what was required in the past. In this new system, the audit trail is not a separate log that someone has to dig through; it is a query the system can run on its own data to verify its own history.

When the researchers tested the system against a real-world trace from a different project, they found that the strict rules caught a gap in enforcement that had been missed before. The system identified that a rule was being enforced locally but was not written down in the official policy, and it flagged this discrepancy. This led the team to update the system so that it now records exactly who was refused and why, closing a small but important hole in the audit trail. The experiment demonstrated that when software agents are the writers, the cost of strictness is affordable because the agents can instantly learn from a rejection and try again. The system does not need a human to clean up the mess; the gatekeeper prevents the mess from happening in the first place, and the permanent record of every decision ensures that the history of the knowledge graph remains accurate and trustworthy.

Technical Summary: Quipu – A Governed Bitemporal Knowledge Graph Store

1. Problem Statement

Knowledge graphs are increasingly authored by software agents (LLMs, code analyzers, pipelines) rather than human curators. However, underlying storage systems retain design defaults optimized for human curation, which become liabilities under agent workloads. The paper identifies four specific defaults that fail in this context:

Accept-then-Clean (D1): Stores accept writes immediately and rely on post-hoc review. Agents generate plausible but incorrect facts faster than humans can review them, causing "cleanup debt" to compound and allowing downstream readers to consume unverified data.
Single or No Time Axis (D2): Conventional bitemporal stores track data validity but not the history of trust, policy decisions, or rules. This makes it impossible to answer governance questions like "what was trusted or allowed at time T," reducing audits to "log archaeology."
Flat Trust (D3): While named graphs exist, composition is a "silent union." Querying a mix of attested and quarantined graphs results in the query inheriting the prestige of the trusted source, effectively laundering untrusted data.
Governance Outside (D4): Policy lives in dashboards, prompts, or middleware separate from the store. The specification and the data drift independently, with no mechanical mechanism to verify that the store's state satisfies the governance specification.

2. Methodology: The Quipu System

Quipu is an embeddable knowledge-graph store (implemented as a single-file SQLite-based Rust crate) designed to invert the four defaults above. It compiles the governance machinery of the SARC framework (which treats constraints as first-class specification objects) directly into the store's write path.

Core Architectural Inversions

Gated Writes (Inverting D1): No fact enters the store except through a gate. The gate evaluates predicates against the pending post-state (the state after the write is staged), not just the pre-state. This prevents valid individual facts from creating invalid combinations.
Bitemporality for Everything (Inverting D2): The store extends bitemporality (transaction time and valid time) beyond data to include trust labels, verdicts, and the rules ( $\Sigma$ ) themselves. This allows the system to replay governance decisions exactly as they were at a specific instant.
Partitioned Authority & Non-Widening Composition (Inverting D3): Authority attaches to partitions (named graphs). Composition follows a lattice where the resulting label is the "meet" (intersection) of its parts. Crucially, composition never widens; a composed view cannot have higher trust than its least-trusted component. Cross-chain trust comparisons are explicitly refused rather than silently ordered.
In-Store Decidable Audit (Inverting D4): The governance specification ( $\Sigma$ ), the execution trace ( $T$ ), and the verdicts are all stored as facts within the graph. Auditing becomes a query ( $T \models \Sigma$ ) decidable in $O(|T| \cdot |C|)$ without external tools or model access.

Data Model & Mechanisms

Bitemporal EAVT Log: Facts are stored as (entity, attribute, value, graph, transaction, valid_from, valid_to, operation). Operations include assert, retract (logical close), and tombstone (marks absence in a view without mutating the base layer).
Three-Valued Verdicts: Gate outcomes (Allow, Deny, Unknown) are signed, time-indexed facts. A denial triggers a rollback of the attempted delta but persists the verdict record, ensuring an auditable trail of refusals.
Label Lattice: Labels cover freshness, trust, durability, and policy. Composition folds these labels; if coverage is partial or empty, enforcement floors fail safely.
Escalation: Refusals requiring approval mint decision requests as facts. The "hold" is the agent retrying, not an engine waiting.

3. Design Principles (GS1–GS6)

The system is built on six interlocking principles:

GS1 (Gated Writes): Evaluation against post-state; zero-cost abstention for non-governed targets.
GS2 (Verdict Permanence): Denials are signed, permanent facts; the attempt is rolled back, but the record remains.
GS3 (Partitioned Authority): Authority intersects along delegation chains; empty intersections refuse.
GS4 (Non-Widening Composition): Trust/freshness folds by meet; obligations by join. Undeclared is not a value; partial coverage fails enforcement.
GS5 (In-Store Decidable Audit): $\Sigma$ and $T$ are data; violation and incompleteness are distinct.
GS6 (As-Of Replay): Decisions are reproducible against the rules and data in force at the time of the transaction.

4. Evaluation: The Census Benchmark

The author introduces Census, a deterministic, multi-writer lifecycle benchmark. It runs a single seeded script with two arms: a "gated" arm (enforcing all rules) and a "control" arm (gates off). The benchmark plants ground-truth defects and measures outcomes without using LLMs in the core loop (writers are deterministic drivers).

Key Results

Defect Prevention (RQ2): The gated store ended with 0 of 6 planted defects, whereas the ungated store contained 6 of 6. Defects included missing provenance, authority violations, and fabricated predicates.
Audit Decidability (RQ3): The in-store audit correctly identified planted violations and incompleteness. An external SARC reference checker agreed verdict-for-verdict, differing only on coverage semantics (whether abstention must be materialized).
Composition Safety (RQ4): All 7 of 7 composition probes upheld the lattice contract. Undeclared members degraded coverage; cross-chain comparisons were refused; expired labels were treated as absent.
Temporal Replay (RQ5): 50 of 50 satisfied verdicts re-derived faithfully as of their instant. Crucially, all 50 would have been misreported under a "latest-only" rule set, proving the necessity of bitemporal rules.
Agent Convergence (RQ6): When LLM agents (Haiku, Sonnet, Opus, Fable) were given refusal feedback, 12 of 12 label/vocabulary refusals were fixed in one revision. Authority refusals (unfixable by editing) sorted agents by disposition (e.g., some refused to falsify, others attempted evasion which was caught).
Evidence Sufficiency (DEMM-Bench): Against an external benchmark testing if records suffice to reconstruct decision properties under degradation, the content-only reader achieved PSA 1.0 (Perfect Sufficient Answer) with 0% overclaim. In contrast, baselines relying on container presence (trace/ledger existence) overclaimed on up to 87.5% of cases.

5. Significance and Claims

The paper claims that Quipu is the first store to simultaneously implement all four inversions of conventional defaults, creating a system where "start strict; use agents to bear the cost of strictness" is viable.

Affordability of Strictness: The cost of strictness (latency, retries) is affordable because agents can absorb the feedback loop (converging in one revision), whereas human curators cannot.
Audit as Data: By making governance rules, traces, and verdicts first-class facts, the audit becomes a decidable query rather than a manual forensic process.
Safety of Composition: The lattice-based composition ensures that trust cannot be laundered through views, and coverage gaps are explicitly reported rather than silently ignored.
Self-Correction: The evaluation process itself improved the system; the DEMM-Bench run revealed that denial verdicts lacked writer attribution, leading to a patch (Q-VERDICT-ATTRIB) that sealed attribution into the signed hash.

The author explicitly states they make no comparative query-performance claims (focusing on guarantees over throughput) and acknowledge boundaries: labels are not access control (they refuse queries rather than hide rows), and denials replay as attestation checks, not re-derivations of the attempt. The work positions Quipu as a necessary substrate for trustworthy agent-written knowledge, moving governance from the "perimeter" into the "core."