What Makes Prompts a Graph: Why Prompt Graph Engineering Needs Architectural Governance

Sandeco Macedo's July 2026 paper What makes prompts a graph: necessary and sufficient conditions for prompt graph engineering defines the practice through explicit structure, separated prompt content, executable semantics, and a first-class graph artifact.

Prompt engineering is moving up a level

Prompt engineering improves the content of an individual model invocation. That remains useful. Graph engineering changes the scope around it.

Consider a coding workflow:

Once branching, parallelism, and retries enter the workflow, engineering decisions exist at two levels.

At the node level, teams decide:

• which prompt the model receives;
• which tools the node can use;
• which context it can see; and
• which model performs the work.

At the graph level, teams decide:

• which node runs next;
• which branches may run concurrently;
• what state crosses each edge;
• what causes a retry;
• which node can reject another node's output; and
• where execution terminates.

The important shift is that the graph stops being a retrospective diagram. It becomes an artifact the engineer authors and the runtime executes.

That creates a governance opportunity because explicit behavior can be inspected before it runs.

The four conditions make the graph governable

1. The structure is explicit

Nodes and edges must exist as something the system represents. A sequence that happens to call several models is not enough. The relationships must be inspectable rather than inferred after execution.

Implicit agent behavior is hard to review. Explicit behavior can expose the points where software is read, changed, evaluated, and accepted.

2. Structure and prompt content are separable

Changing the wording inside one node should not require redesigning the graph. Changing a routing rule should not require rewriting every prompt.

This separates the program's topology from the content that configures individual calls. It also means governance can target the transition where a risky action occurs without turning every prompt into a policy document.

3. The graph has executable semantics

An architecture diagram does not qualify. A runtime must schedule nodes, route outputs, manage shared state, and interpret branches or cycles.

For coding agents, that means a verification step can become part of the executable path instead of a box someone hopes a human remembers to perform later.

4. The graph is first-class

This condition has the largest governance implications. A first-class graph can be inspected, serialized, versioned, validated, evaluated, and potentially optimized independently of one run.

Once an agent graph becomes a versioned engineering artifact, teams can review not only application code but also the topology through which agents create application code.

The next question follows naturally:

What properties of the software system must that graph preserve?

An execution graph is not an architectural model

Imagine a graph that reads an issue, inspects the repository, plans a change, modifies a service, runs tests, and opens a pull request.

That graph explains execution. It says little about the architecture the resulting code should preserve.

Suppose the implementation directly connects a payments service to a production database, while an accepted ADR prohibits services from accessing that database outside an approved adapter.

The graph may run exactly as designed. The code may compile. Tests may pass. The pull request may open successfully.

The architectural decision can still be violated.

The execution graph answers: What can happen next?

Architectural governance answers: What must remain true when it happens?

This is why graph engineering does not replace the category boundary described in AI Agent Orchestration Is Not Software Engineering Governance. It makes that boundary easier to see.

Coding agents operate across several graphs

The word graph is already overloaded. Engineering leaders should separate at least three structures.

The execution graph

This represents how work progresses: planning, retrieval, implementation, testing, evaluation, and repair. Nodes may be agents, prompts, tools, deterministic functions, or evaluators. Edges encode control and data dependencies.

This is closest to Macedo's prompt graph engineering.

The knowledge graph

This represents relationships the system knows: a service depends on an API; one ADR supersedes another; a migration affected a component.

Knowledge graphs help because similarity is not the same as relationship. They can also preserve temporal and provenance information that vector retrieval alone does not express.

But knowledge is descriptive. It does not automatically produce governance.

The architectural constraint layer

This represents normative relationships: a service must not import a database driver; a public API must remain compatible with a contract; an accepted ADR requires a particular abstraction.

A fact says that Service A depends on package B. A constraint says that Service A must not depend on package B.

Authority, status, scope, and supersession all matter before a remembered relationship can become enforceable.

More graph structure does not guarantee better governance

Turning everything into nodes and edges is not the solution.

A graph can encode incorrect information. It can omit a relevant decision. It can route execution perfectly toward an architecturally invalid result. A graph-backed memory system can also make bad information more persistent.

If a model extracts the wrong relationship and writes it into durable state, later agents may retrieve it as evidence and create more state derived from the same error.

That is why graph ingestion needs validation, provenance, normalization, duplicate handling, temporal checks, and authority rules. A remembered statement should not quietly become policy.

First-class graphs create new verification points

The paper asks which properties of a prompt graph can be checked statically and which require semantic judgment. For coding agents, the verification surface is wider.

Teams need to separate four questions:

1. Did the graph execute correctly?
2. Did the agent complete the requested task?
3. Did the required engineering process run?
4. Did the resulting change preserve architectural intent?

An agent can pass the first three and still create drift.

A governed execution path therefore moves verification closer to the nodes that can change software:

Not every architectural judgment can become a deterministic rule. The goal is to identify decisions explicit enough to become part of a verification contract, then place their enforcement where violations can still be prevented.

Governance propagation becomes a graph problem

A planner may retrieve the right decision while an implementation agent never sees it. A backend agent may delegate work to another node whose context omits the constraint. Shared state can preserve task data while architectural intent decays across edges.

That is governance propagation: ensuring applicable decisions travel with delegated work and remain authoritative at each enforcement point.

The graph is useful because it exposes where information crosses boundaries. Those edges are potential governance boundaries too.

Flexible reasoning, explicit invariants

Coding agents need freedom to explore. Teams should not predefine every valid reasoning path.

A practical split is:

• Flexible: how the agent solves the task.
• Explicit: which architectural constraints the result must preserve.

An agent may choose whether to inspect tests first, search symbols, delegate research, or compare several implementations. An accepted dependency rule does not need to become probabilistic simply because the reasoning path is dynamic.

The graph defines possible execution. The verification contract constrains the outcomes that execution can produce.

From executable graphs to governed change

Prompt engineering focused on getting one model call right. Context engineering expanded the problem to the information around the call. Harness engineering expanded it to tools, permissions, and runtime. Prompt graph engineering makes the larger topology explicit.

For AI coding agents, one more step remains:

Macedo's paper gives engineering teams a rigorous way to identify when prompts have become a graph.

Once that graph is explicit, executable, and improvable, architectural intent should not remain implicit.

Graph engineering makes agent behavior inspectable. Architectural governance makes the consequences of that behavior accountable to the decisions governing the codebase.