How Graph Serialization Format Affects GraphRAG Cost and Accuracy

The format is part of the retrieval system

GraphRAG combines retrieval with graph structure so that an answer can follow relationships instead of relying only on text similarity. A typical request retrieves a subgraph, serializes it, and places that text in a model prompt. The serializer therefore sits on the critical path between retrieval and reasoning.

The graph database may store compact identifiers and typed relationships, but a prompt often expands them into repeated field names:

{
  "source": {"id": "svc-api", "type": "service"},
  "relationship": {"type": "depends_on"},
  "target": {"id": "svc-auth", "type": "service"}
}

Repeated keys, braces, quotes, commas, type labels, and duplicated node properties all consume tokens. That syntax is not automatically waste: explicit structure can prevent ambiguity. The engineering question is whether each token improves the probability of a correct traversal enough to justify its cost.

A smaller representation can fail too. The line A B C is cheap, but it does not say whether A depends on B, owns B, or replaced B. The useful objective is therefore not minimum tokens. It is the best measured answer quality under a fixed context window, latency target, and budget.

Three distinct accuracy layers

Do not collapse every error into “the model got it wrong.” Measure these layers independently:

1. Serialization fidelity: can a parser reconstruct the original nodes, edges, directions, labels, and required properties?
2. Traversal fidelity: can the reconstructed graph answer deterministic path queries correctly?
3. Answer quality: can a language model use the serialized evidence to produce the expected multi-hop answer?

If layer one fails, changing the prompt cannot repair missing information. If layers one and two pass but layer three fails, ordering, verbosity, model behavior, or instructions are more plausible causes.

Concrete case: dependency impact analysis

Consider an internal service graph. Nodes represent services and databases. Directed depends_on edges point from a consumer to its dependency. A second relationship, owned_by, connects a service to its team.

The operational question is:

Which customer-facing services are transitively affected if db-identity fails, and which teams own those services?

Answering it requires at least two operations: traverse dependency edges in the reverse direction from the failed database, then follow ownership edges from affected services. A representation that drops direction, omits relationship types, or loses the ownership records cannot support the answer even when every remaining line is syntactically valid.

This is also where truncation becomes dangerous. A large JSON document may place the closing edges or ownership section beyond the available budget. The prompt remains readable, but the evidence needed for the last hop is absent.

Formats under test

The benchmark below compares five lossless representations of the same directed, typed graph. All formats retain node identifiers, node types, edge types, and direction.

Do not include an intentionally lossy format in the main ranking without labeling it. For example, an untyped pair list may win on tokens only because it removed information required by the questions.

Experimental design

Control variables

Keep the following fixed for every format:

• the graph and the order in which records are supplied;
• the query set and expected answers;
• the tokenizer and model version;
• the prompt instructions and output schema;
• the maximum input budget and truncation policy;
• generation settings, including temperature and maximum output tokens;
• the number of repeated runs and the scoring code.

Primary measurements

Serialized bytes

UTF-8 byte length. Useful for storage and transport, but not a substitute for model-specific token measurement.

Token count

The count produced by the exact tokenizer used for the evaluated model.

Round-trip fidelity

Whether decoding the representation yields the canonical node and edge sets.

Traversal accuracy

The fraction of deterministic graph queries whose decoded answers equal the gold answers.

Budget survival

The fraction of required evidence records remaining after applying the same token budget.

Multi-hop exact match

The fraction of model answers that normalize to the expected set of identifiers.

Recommended hypotheses

Write hypotheses before running the test. For example:

• Compact JSON will use fewer tokens than pretty JSON while preserving identical deterministic results.
• A typed edge list will reduce syntax overhead, but may require stronger format instructions.
• Under a tight budget, record-aware truncation will outperform raw character or token slicing.
• Ordering edges by relevance to the query will matter more as the budget becomes smaller.

These are hypotheses, not results. The benchmark is designed to confirm or reject them on your graph, tokenizer, model, and query distribution.

Reference implementation

The following single-file program creates a deterministic synthetic graph, serializes it in five formats, decodes every format, validates round trips, runs reachability queries, and measures tokens. The default graph is deliberately small enough to inspect. Increase --services and --noise-edges for context-pressure tests.

Environment

python -m venv .venv
. .venv/bin/activate
python -m pip install tiktoken

Pin the installed dependency after choosing the version used in your experiment:

python -m pip freeze > requirements-lock.txt
python --version
python -m pip show tiktoken

Save as benchmark_graph_formats.py

#!/usr/bin/env python3
import argparse
import csv
import io
import json
import random
from collections import defaultdict, deque
from dataclasses import dataclass, asdict

import tiktoken


@dataclass(frozen=True, order=True)
class Node:
    id: str
    type: str


@dataclass(frozen=True, order=True)
class Edge:
    source: str
    relation: str
    target: str


def make_graph(service_count, noise_edges, seed):
    rng = random.Random(seed)

    nodes = [
        Node("db-identity", "database"),
        Node("team-core", "team"),
        Node("team-growth", "team"),
        Node("svc-web", "service"),
        Node("svc-api", "service"),
        Node("svc-auth", "service"),
        Node("svc-profile", "service"),
    ]
    edges = [
        Edge("svc-web", "depends_on", "svc-api"),
        Edge("svc-api", "depends_on", "svc-auth"),
        Edge("svc-profile", "depends_on", "svc-auth"),
        Edge("svc-auth", "depends_on", "db-identity"),
        Edge("svc-web", "owned_by", "team-growth"),
        Edge("svc-api", "owned_by", "team-core"),
        Edge("svc-auth", "owned_by", "team-core"),
        Edge("svc-profile", "owned_by", "team-growth"),
    ]

    extra_services = [
        Node(f"svc-noise-{i:04d}", "service")
        for i in range(max(0, service_count - 4))
    ]
    nodes.extend(extra_services)

    all_services = [n.id for n in nodes if n.type == "service"]
    existing = set(edges)
    attempts = 0
    while len(existing) < len(edges) + noise_edges and attempts < noise_edges * 50 + 100:
        attempts += 1
        source = rng.choice(all_services)
        target = rng.choice(all_services)
        if source != target:
            existing.add(Edge(source, "depends_on", target))

    edges = sorted(existing)
    return sorted(nodes), edges


def canonical(nodes, edges):
    return (
        tuple(sorted((n.id, n.type) for n in nodes)),
        tuple(sorted((e.source, e.relation, e.target) for e in edges)),
    )


def encode_pretty_json(nodes, edges):
    value = {
        "nodes": [asdict(n) for n in nodes],
        "edges": [asdict(e) for e in edges],
    }
    return json.dumps(value, indent=2, ensure_ascii=False)


def decode_pretty_json(text):
    value = json.loads(text)
    nodes = [Node(x["id"], x["type"]) for x in value["nodes"]]
    edges = [
        Edge(x["source"], x["relation"], x["target"])
        for x in value["edges"]
    ]
    return nodes, edges


def encode_compact_json(nodes, edges):
    value = {
        "n": [[n.id, n.type] for n in nodes],
        "e": [[e.source, e.relation, e.target] for e in edges],
    }
    return json.dumps(value, separators=(",", ":"), ensure_ascii=False)


def decode_compact_json(text):
    value = json.loads(text)
    nodes = [Node(*x) for x in value["n"]]
    edges = [Edge(*x) for x in value["e"]]
    return nodes, edges


def encode_jsonl(nodes, edges):
    records = []
    records.extend(
        json.dumps(
            {"k": "n", "id": n.id, "t": n.type},
            separators=(",", ":"),
            ensure_ascii=False,
        )
        for n in nodes
    )
    records.extend(
        json.dumps(
            {"k": "e", "s": e.source, "r": e.relation, "t": e.target},
            separators=(",", ":"),
            ensure_ascii=False,
        )
        for e in edges
    )
    return "\n".join(records)


def decode_jsonl(text):
    nodes, edges = [], []
    for line in text.splitlines():
        if not line.strip():
            continue
        value = json.loads(line)
        if value["k"] == "n":
            nodes.append(Node(value["id"], value["t"]))
        elif value["k"] == "e":
            edges.append(Edge(value["s"], value["r"], value["t"]))
        else:
            raise ValueError(f"Unknown record kind: {value['k']}")
    return nodes, edges


def encode_csv_records(nodes, edges):
    output = io.StringIO(newline="")
    writer = csv.writer(output, lineterminator="\n")
    writer.writerow(["kind", "a", "b", "c"])
    for n in nodes:
        writer.writerow(["N", n.id, n.type, ""])
    for e in edges:
        writer.writerow(["E", e.source, e.relation, e.target])
    return output.getvalue()


def decode_csv_records(text):
    reader = csv.reader(io.StringIO(text))
    header = next(reader)
    if header != ["kind", "a", "b", "c"]:
        raise ValueError("Unexpected CSV header")
    nodes, edges = [], []
    for kind, a, b, c in reader:
        if kind == "N":
            nodes.append(Node(a, b))
        elif kind == "E":
            edges.append(Edge(a, b, c))
        else:
            raise ValueError(f"Unknown CSV record kind: {kind}")
    return nodes, edges


def escape_atom(value):
    return (
        value.replace("\\", "\\\\")
             .replace("|", "\\p")
             .replace("\n", "\\n")
    )


def unescape_atom(value):
    result = []
    i = 0
    while i < len(value):
        if value[i] != "\\":
            result.append(value[i])
            i += 1
            continue
        i += 1
        if i >= len(value):
            raise ValueError("Trailing escape")
        result.append({"p": "|", "n": "\n", "\\": "\\"}[value[i]])
        i += 1
    return "".join(result)


def split_escaped(line):
    fields, current = [], []
    escaped = False
    for char in line:
        if escaped:
            current.extend(["\\", char])
            escaped = False
        elif char == "\\":
            escaped = True
        elif char == "|":
            fields.append(unescape_atom("".join(current)))
            current = []
        else:
            current.append(char)
    if escaped:
        raise ValueError("Trailing escape")
    fields.append(unescape_atom("".join(current)))
    return fields


def encode_typed_edges(nodes, edges):
    lines = ["#graph-v1"]
    lines.extend(
        f"N|{escape_atom(n.id)}|{escape_atom(n.type)}"
        for n in nodes
    )
    lines.extend(
        f"E|{escape_atom(e.source)}|{escape_atom(e.relation)}|{escape_atom(e.target)}"
        for e in edges
    )
    return "\n".join(lines)


def decode_typed_edges(text):
    lines = text.splitlines()
    if not lines or lines[0] != "#graph-v1":
        raise ValueError("Missing graph format declaration")
    nodes, edges = [], []
    for line in lines[1:]:
        fields = split_escaped(line)
        if fields[0] == "N" and len(fields) == 3:
            nodes.append(Node(fields[1], fields[2]))
        elif fields[0] == "E" and len(fields) == 4:
            edges.append(Edge(fields[1], fields[2], fields[3]))
        else:
            raise ValueError(f"Invalid record: {line!r}")
    return nodes, edges


FORMATS = {
    "pretty_json": (encode_pretty_json, decode_pretty_json),
    "compact_json": (encode_compact_json, decode_compact_json),
    "jsonl": (encode_jsonl, decode_jsonl),
    "csv": (encode_csv_records, decode_csv_records),
    "typed_edges": (encode_typed_edges, decode_typed_edges),
}


def reachable_dependencies(edges, start, max_hops):
    adjacency = defaultdict(list)
    for edge in edges:
        if edge.relation == "depends_on":
            adjacency[edge.source].append(edge.target)

    seen = {start}
    queue = deque([(start, 0)])
    answer = set()
    while queue:
        node, distance = queue.popleft()
        if distance == max_hops:
            continue
        for target in adjacency[node]:
            if target not in seen:
                seen.add(target)
                answer.add(target)
                queue.append((target, distance + 1))
    return sorted(answer)


def affected_services(nodes, edges, failed_node):
    reverse = defaultdict(list)
    for edge in edges:
        if edge.relation == "depends_on":
            reverse[edge.target].append(edge.source)

    seen = {failed_node}
    queue = deque([failed_node])
    affected = set()
    service_ids = {n.id for n in nodes if n.type == "service"}

    while queue:
        node = queue.popleft()
        for consumer in reverse[node]:
            if consumer not in seen:
                seen.add(consumer)
                queue.append(consumer)
                if consumer in service_ids:
                    affected.add(consumer)
    return sorted(affected)


def owners_of(services, edges):
    owners = defaultdict(set)
    wanted = set(services)
    for edge in edges:
        if edge.relation == "owned_by" and edge.source in wanted:
            owners[edge.source].add(edge.target)
    return {
        service: sorted(owners[service])
        for service in sorted(wanted)
    }


def query_suite(nodes, edges):
    affected = affected_services(nodes, edges, "db-identity")
    return {
        "api_dependencies_3_hops":
            reachable_dependencies(edges, "svc-api", 3),
        "identity_failure_affected_services":
            affected,
        "owners_of_affected_services":
            owners_of(affected, edges),
    }


def token_count(encoding, text):
    return len(encoding.encode(text))


def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("--services", type=int, default=40)
    parser.add_argument("--noise-edges", type=int, default=80)
    parser.add_argument("--seed", type=int, default=7)
    parser.add_argument("--encoding", default="o200k_base")
    parser.add_argument("--output", default="benchmark-results.json")
    args = parser.parse_args()

    encoding = tiktoken.get_encoding(args.encoding)
    nodes, edges = make_graph(
        args.services,
        args.noise_edges,
        args.seed,
    )
    gold_graph = canonical(nodes, edges)
    gold_queries = query_suite(nodes, edges)

    report = {
        "parameters": vars(args),
        "graph": {
            "nodes": len(nodes),
            "edges": len(edges),
        },
        "gold_queries": gold_queries,
        "formats": {},
    }

    for name, (encoder, decoder) in FORMATS.items():
        text = encoder(nodes, edges)
        decoded_nodes, decoded_edges = decoder(text)
        decoded_graph = canonical(decoded_nodes, decoded_edges)
        decoded_queries = query_suite(decoded_nodes, decoded_edges)

        query_checks = {
            key: decoded_queries[key] == expected
            for key, expected in gold_queries.items()
        }
        report["formats"][name] = {
            "utf8_bytes": len(text.encode("utf-8")),
            "characters": len(text),
            "tokens": token_count(encoding, text),
            "round_trip_equal": decoded_graph == gold_graph,
            "query_checks": query_checks,
            "traversal_accuracy": (
                sum(query_checks.values()) / len(query_checks)
            ),
        }

        with open(f"graph.{name}.txt", "w", encoding="utf-8") as handle:
            handle.write(text)

    with open(args.output, "w", encoding="utf-8") as handle:
        json.dump(report, handle, indent=2, ensure_ascii=False)

    print(json.dumps(report, indent=2, ensure_ascii=False))


if __name__ == "__main__":
    main()

Why the benchmark begins with deterministic parsing

A model is not a parser conformance test. Before spending inference budget, prove that every supposedly lossless format can reconstruct the same graph. The program compares canonical tuples rather than serialized strings, so harmless ordering and whitespace differences do not count as failures.

The query suite then operates on the decoded graph. A traversal score below 1.0 means the serialization or decoder changed usable graph semantics. Stop there and fix the representation before evaluating a language model.

Running the benchmark

Baseline

python benchmark_graph_formats.py \
  --services 40 \
  --noise-edges 80 \
  --seed 7 \
  --encoding o200k_base \
  --output baseline.json

Scale sweep

for size in 40 100 250 500
do
  python benchmark_graph_formats.py \
    --services "$size" \
    --noise-edges "$((size * 2))" \
    --seed 7 \
    --encoding o200k_base \
    --output "results-${size}.json"
done

Use the encoding required by your selected model. Do not copy an encoding name merely because it appears in this example. Record it alongside the model identifier and dependency lock file.

Inspect the generated representations

wc -c graph.*.txt
sed -n '1,30p' graph.pretty_json.txt
sed -n '1,30p' graph.typed_edges.txt
python -m json.tool baseline.json

Record-aware budget tests

Raw token slicing can cut a JSON object or CSV record in half. That measures corruption as much as compactness. Run two policies and report them separately:

1. Raw budget: encode the complete representation, keep the first B
2. Record-aware budget: append complete records while the next record still fits. For monolithic JSON, build the largest valid object that fits.

Use several budgets rather than one convenient threshold:

budgets = [512, 1024, 2048, 4096, 8192]

For each budget, store:

• whether the truncated representation parses;
• the retained node and edge counts;
• whether every gold path remains present;
• deterministic traversal accuracy;
• model answer score, if model evaluation is enabled.

Test more than one ordering

Serialization format and record order interact. Compare at least:

• canonical identifier order;
• deterministically shuffled order using recorded seeds;
• query-relevant edges first;
• breadth-first order from the query entities;
• nodes followed by edges, and interleaved node-edge records where supported.

A format should not receive an ordering advantage that other formats are denied. Either use an equivalent order everywhere or treat ordering as a separate experimental factor.

Multi-hop model evaluation

After all formats pass deterministic checks, test whether a model can use them. A multi-hop answer should depend on multiple linked facts, not on a label that directly reveals the result.

Prompt template

You answer only from the graph data below.

Graph semantics:
- "A depends_on B" means A is a consumer of B.
- If B fails, A may be affected.
- Dependency impact propagates transitively in the reverse direction.
- "A owned_by T" identifies the team responsible for A.

Return JSON only:
{
  "affected_services": ["service-id"],
  "owners": {
    "service-id": ["team-id"]
  }
}

Question:
If db-identity fails, which services are transitively affected,
and which teams own those services?

GRAPH_FORMAT:
{{format_name}}

GRAPH_DATA:
{{serialized_graph}}

Keep these instructions byte-for-byte identical between formats except for format_name and serialized_graph. If a format needs a grammar explanation, include the grammar in its token accounting. Otherwise, a compact custom format receives an unfair advantage by hiding instructions outside the measured input.

Gold answers

Generate expected answers with deterministic graph code, not with another model. Normalize both gold and candidate outputs before comparison:

• parse JSON strictly;
• reject missing required fields;
• deduplicate and sort identifier arrays;
• compare identifiers exactly rather than using semantic similarity;
• score affected services and ownership mappings separately.

Suggested scoring

For set-valued answers, report precision, recall, and F1. Let P be the predicted identifier set and G the gold set:

precision = |P ∩ G| / |P|
recall    = |P ∩ G| / |G|
F1        = 2 × precision × recall / (precision + recall)

Define behavior for empty sets before running the experiment. Also report strict exact match, because an F1 score can hide one unsupported service in an otherwise long correct list.

Repeated trials

Even low-temperature generation may vary. Use the same number of attempts per format and query. Store every raw request, raw response, parse outcome, normalized answer, latency, and usage value returned by the provider. Do not reconstruct token usage later when the API already supplied it.

Result schema

{
  "run_id": "locally-assigned-id",
  "graph_hash": "sha256-of-canonical-graph",
  "format": "typed_edges",
  "ordering": "bfs_from_query",
  "budget_tokens": 4096,
  "model": "exact-model-identifier",
  "tokenizer": "exact-tokenizer-identifier",
  "prompt_tokens_reported": 0,
  "completion_tokens_reported": 0,
  "parse_success": false,
  "exact_match": false,
  "affected_services_f1": 0.0,
  "owners_exact_match": false,
  "latency_ms": 0,
  "raw_response_path": "responses/run-id.txt"
}

The zeros above are placeholders defining fields, not benchmark findings.

Cost calculation

Store token usage first. Apply pricing later from an explicitly recorded price table:

input_cost =
  prompt_tokens / 1_000_000 * input_price_per_million

output_cost =
  completion_tokens / 1_000_000 * output_price_per_million

total_cost = input_cost + output_cost

Pricing changes, and cached-input rules may differ. Keeping raw usage separate from price assumptions makes historical runs comparable without rewriting the evidence.

Verification and interpretation

Pre-flight verification

• Every format has round_trip_equal: true.
• Every untruncated format has traversal accuracy of 1.0.
• The same canonical graph hash appears in every run.
• The tokenizer corresponds to the evaluated model.
• Grammar instructions are included in measured prompt tokens.
• All random seeds, package versions, budgets, and model settings are recorded.
• Gold answers come from deterministic traversal.

Use a Pareto comparison

A single weighted score can conceal important trade-offs. First identify the Pareto frontier: a format is dominated if another format uses no more tokens and achieves equal or better accuracy at every tested budget, with at least one strict improvement.

Then choose among non-dominated formats using operational constraints. For example, a team may accept a modest token increase for standard parsing, better observability, and fewer escaping bugs.

Report uncertainty

Deterministic token counts need no confidence interval, but model answer scores do. Report the number of queries and repeated trials. For proportions such as exact match, use a suitable binomial interval or bootstrap the query-level results. Avoid presenting a difference of one successful answer as a general format advantage.

Separate these conclusions

• Format efficiency: tokens required for the complete graph.
• Budget robustness: answer quality as the graph is constrained.
• Reasoning usability: quality when all required evidence fits.
• Engineering reliability: parse failures, escaping errors, schema drift, and debugging cost.

Minimum results table

Failure cases worth testing explicitly

Duplicate identifiers

If two node records share an identifier but disagree on type or properties, decide whether decoding rejects the graph or applies a documented merge rule. Silent last-write-wins behavior can make format ordering change the answer.

Delimiter collisions

Custom edge lists often work until an identifier contains a pipe, tab, newline, backslash, or arrow-like sequence. Add adversarial fixtures and verify round trips. A compact grammar without an escaping specification is not a production format.

Direction reversal

A depends_on B and B is_dependency_of A describe the same relation from different viewpoints. Mixing the two conventions reverses impact analysis. Put semantics in the prompt and encode direction unambiguously.

Relationship-type collapse

If depends_on, owned_by, and deployed_in are serialized as unlabeled pairs, deterministic reachability may return syntactically connected but semantically invalid paths.

Orphan edges

An edge may reference a node omitted by retrieval or truncation. Decide whether the model needs the node record, whether the identifier alone is sufficient, and whether the decoder rejects or retains the edge.

Broken monolithic JSON

Cutting a JSON document at a token boundary commonly produces invalid syntax. Record-aware construction or JSONL can preserve valid prefixes, but a valid prefix may still omit decisive evidence. Track parse validity and evidence completeness separately.

Schema verbosity disguised as evidence

Repeated natural-language property descriptions may dominate the graph. Measure structural records separately from node content. In production, retrieve long descriptions only for nodes on candidate paths.

Tokenizer mismatch

Byte size, character count, and tokens are correlated but not interchangeable. Punctuation-heavy encodings, long identifiers, Unicode labels, and whitespace can tokenize differently. Measure with the deployed tokenizer.

Identifier leakage

A node named service-affected-by-identity gives away the answer. Use neutral identifiers or test whether labels alone solve the question without traversal.

Random graph shortcuts

Noise edges can accidentally create shorter paths or change the gold affected set. Always compute gold answers after graph generation and store the canonical graph used for the run.

From benchmark to production design

Prefer query-shaped subgraphs

Serialization cannot compensate for retrieving an unnecessarily large graph. Extract candidate paths, retain relationship direction and provenance, and serialize only the evidence required for the question plus a controlled amount of neighboring context.

Use stable dictionaries when repetition is high

A dictionary can map repeated types and relation names to short codes:

REL: d=depends_on, o=owned_by
TYPE: s=service, t=team, b=database

N|svc-api|s
N|svc-auth|s
E|svc-api|d|svc-auth

Include the dictionary and its explanation in token measurements. Version it, reject unknown codes, and avoid codes that are easy to confuse.

Place decisive evidence deliberately

Under hard budgets, order records by relevance or path structure instead of database insertion order. Keep the policy deterministic and evaluate it as its own factor. A useful sequence is query entities, their node records, candidate path edges, intermediate nodes, terminal evidence, then optional context.

Preserve provenance without repeating it everywhere

If every edge cites the same document, assign the source a short identifier and provide a source table once. If provenance varies by edge, retain the mapping required for answer verification. Removing provenance may reduce tokens while making grounded answers impossible to audit.

Version the grammar

Custom formats should begin with a version marker such as #graph-v1. Store the encoder, decoder, grammar description, and benchmark fixtures together. Treat a grammar change as a data-contract change, not a prompt tweak.

Recommended decision rule

Select the simplest representation that meets all of these conditions:

1. lossless round trip for required graph semantics;
2. perfect deterministic traversal on the test suite;
3. acceptable multi-hop quality at the production budget;
4. no unacceptable degradation across orderings and seeds;
5. documented escaping, schema, and version behavior;
6. operationally acceptable cost, latency, and debugging effort.

Limitations

This experiment does not establish a universally best graph format. Results depend on graph density, identifier length, property volume, language, tokenizer, model, prompt, question type, retrieval policy, and context budget.

The reference graph emphasizes directed dependency and ownership queries. Knowledge graphs with qualifiers, temporal validity, confidence scores, hyperedges, nested properties, or multiple provenance records require additional fixtures and possibly different encodings.

Exact-match scoring is appropriate for identifier sets but insufficient for open-ended explanations. If explanations matter, score factual claims against graph-derived evidence and keep that evaluation separate from identifier retrieval.

Synthetic scale tests reveal mechanical behavior but cannot replace a sanitized sample of the production distribution. Real graphs often contain irregular identifiers, missing properties, duplicate facts, skewed degrees, multilingual labels, and long text fields.

Finally, token savings do not guarantee lower end-to-end cost. A format that needs more retries, produces invalid output, or requires a larger model may cost more despite a shorter prompt.

Reproduction checklist

1. Freeze one canonical graph and compute its hash.
2. Define multi-hop queries and generate gold answers deterministically.
3. Implement an encoder and decoder for every format.
4. Require lossless round trips before model testing.
5. Measure UTF-8 bytes and exact model-tokenizer counts.
6. Test multiple budgets, orderings, graph sizes, and seeds.
7. Apply both raw and record-aware truncation policies.
8. Keep prompts and generation settings fixed.
9. Include grammar instructions in token accounting.
10. Store raw requests, responses, usage, latency, and parse outcomes.
11. Report exact match, precision, recall, F1, and uncertainty.
12. Publish configuration and unfilled result templates alongside conclusions.