Most grounded systems answer a query and cite a source: “trust this, it was
retrieved.” Kremis takes a different approach. A query result can carry a
Verifiable Query Certificate (VQC) — an object that a third party
re-executes against the same graph state to obtain the identical answer,
offline, without trusting the server that produced it. Re-verification ties
the result to state_hash, so the verifier needs a graph whose canonical
export hashes to that value; the certificate is not a standalone proof in
isolation.
A citation says this exists. A certificate says here is how to re-derive
it.
The Verifiable Query Certificate
The certificate is a pure function of (graph state, query). It contains no
timestamp, no randomness, and no floating-point value.
| Field | Content |
|---|
query | The query in canonical form |
evidence_nodes | The minimal set of nodes the result depends on, sorted |
evidence_edges | The minimal set of edges the result depends on, sorted |
traversal_trace | The ordered, deterministic steps taken |
state_hash | BLAKE3 hash of the canonical (KREX) export of the graph state |
grounding | The honest verdict: fact, inference, or unknown |
grounding field is not omitted when the answer is absent — see
Proof of Absence.
Reproducible by construction
Reproducibility here is structural, not a logging side effect. It follows
from the same constraints documented in the
Graph Engine:
- All core collections use
BTreeMap — iteration order is deterministic, no
HashMap anywhere in kremis-core.
- The canonical export (
KREX, magic b"KREX", version 2, postcard) is
bit-exact; the same state serializes to the same bytes.
GET /hash returns a BLAKE3 hash over that canonical form.
Because the answer is a deterministic function of the serialized state, the
certificate is too. Re-running it yields the same bytes.
Independent re-verification
A verifier does not need Kremis. Any implementation that reproduces the
canonical KREX bytes for a given state can recompute the certificate and
compare. Correctness is therefore falsifiable by anyone: a divergent
implementation that produces different bytes proves a defect, the way a
mismatched hash does.
The published certificate specification freezes
this format and ships test vectors (a frozen graph, a set of queries, and the
expected certificate bytes) so the property can be checked, not assumed.
Proof of absence
When a query has no answer, grounding is unknown. The certificate over an
absent result, together with state_hash, is a verifiable assertion: the
graph at this state does not contain X. A probabilistic retriever cannot
demonstrate a negative; a complete, deterministic store can. Absence is
treated as a first-class, certifiable result, not a silent empty response.
Scope and honesty
This page describes a verification substrate, not a retrieval engine. Kremis
deliberately does not provide:
- ontology-constrained or LLM-based extraction (authoring is the caller’s job)
- vector or hybrid retrieval
- a temporal / bi-temporal model
These are out of scope by design, not pending features.
Deterministic, auditable knowledge graphs for agents are an active area:
canonical-primitive APIs for auditable reasoning over temporal knowledge
graphs (arXiv:2510.06002), cryptographic deletion receipts (ForgetAgent), and
reproducible KG construction (OPTIMUS). These provide auditable logs or
reproducible construction. Kremis differs on a narrow, checkable point: the
query result itself is reproducible by construction and re-verifiable by an
independent implementation, delivered as a single local binary over MCP.
The defensible claim is intentionally narrow and falsifiable: no combination
of (reproducible-by-construction query results) + (independently
re-verifiable certificate) + (proof of absence) + (single local binary over
MCP) is covered by the work above. Overstating beyond this is a defect, the
same as a wrong hash. Last modified on June 2, 2026
