The Instruction Provenance Problem in Autonomous AI Agents

Abstract

Autonomous AI agents — systems that plan, call external tools, browse content, and take multi-step actions with limited human supervision — are moving from research demos into production workflows that touch email, calendars, code repositories, and payment systems. This expansion has outpaced a foundational security question: when an agent decides to act, can it reliably tell whether the instruction driving that action came from the person who authorized it, or from something the agent merely read along the way? We describe this as the instruction provenance problem in autonomous AI agents, and argue that most current defenses operate at the wrong layer — filtering content or restricting tools — rather than tracking where an instruction actually originated as it flows through an agent's reasoning. We propose Provenance-Bound Instruction Graphs (PBIG), a conceptual framework for tagging instruction origin, tracing causal lineage through an agent's reasoning steps, and gating high-consequence tool calls on that lineage rather than on content inspection alone. This article presents the problem, the proposed architecture, and an evaluation protocol; it is a research proposal, not a report of an implemented or benchmarked system.

Keywords: autonomous AI agents, agentic AI security, indirect prompt injection, instruction provenance, tool-augmented large language models, authority propagation, AI agent architecture, cybersecurity research.

1. Problem Definition

An autonomous agent built on a large language model typically assembles a single working context from several sources within one turn: the operator's original request, the system instructions defining its role, and — increasingly — the outputs of tools it has just called: a webpage it fetched, a file it opened, an email it read, a response returned by another agent it delegated work to. The model then reasons over that combined context and decides what to do next, including which tool to call and with what arguments.

The security gap here is structural, not incidental. Once content from an external source enters the agent's context window, it is represented the same way as an instruction from the authorized user — as text the model conditions its next action on. If that external content contains language phrased as a command, a sufficiently capable agent can treat it as one, because nothing in the architecture marks that text as having come from an untrusted source rather than from the principal who is supposed to be in control. This pattern is documented as indirect prompt injection [1], and the broader outcome — an agent taking actions its operator never actually authorized — is catalogued as a distinct risk category in current LLM application security guidance [2]. What remains largely unresolved is a general mechanism for an agent to reason about instruction origin at the moment it decides to act, which is the focus of this article.

We define the instruction provenance problem precisely: given an agent about to execute an action a with real-world side effects, does the agent's runtime hold a verifiable record of which upstream content — principal-authored or externally sourced — causally contributed to the decision to take a, and does its policy for permitting a depend on that record rather than on the content of a alone?

2. Why Current Defenses Are Insufficient

Three broad defense families are in common use today, and each addresses a layer adjacent to, but distinct from, the provenance question.

Content-based filtering — classifiers or heuristic rules that scan incoming text for injection-like patterns — treats the symptom rather than the structural cause. Natural language has no fixed syntax for "this is a command," so a classifier trained on known injection phrasing can be evaded by rephrasing, encoding, or splitting the instruction across multiple retrieved fragments, producing a continuing arms race rather than a structural fix [1,2].

Tool sandboxing and allow-listing — restricting which tools an agent may call, or isolating tool execution — reduces the blast radius of a compromised decision but does not resolve the underlying confused-deputy scenario. If "send a message" is a legitimate, allow-listed capability the operator genuinely wants the agent to have, sandboxing does nothing to stop that same capability from being invoked by an instruction the operator never gave, because the tool itself is not the vulnerability — the unverified origin of the instruction to use it is.

Human-in-the-loop confirmation before consequential actions is effective when actually exercised, but it does not scale to the stated value proposition of an autonomous agent, which is to reduce the number of decisions a human must review. Confirmation prompts that appear on every externally-influenced action tend to either be disabled for convenience or approved without real scrutiny once a user habituates to them.

None of these three approaches maintains a structural record of where an instruction came from as it propagates through an agent's multi-step reasoning — which is exactly what a provenance-aware policy would need in order to make a principled decision rather than a heuristic one.

3. Proposed Solution: Provenance-Bound Instruction Graphs (PBIG)

We propose treating instruction origin as a first-class, propagated property of an agent's reasoning process — conceptually related to how information flow control tracks the confidentiality label of data as it moves through a program, but applied here to the causal ancestry of a decision to act, not to data secrecy.

The central idea is an instruction-lineage graph: every discrete unit entering the agent's context — the operator's request, a system instruction, a retrieved document, a tool's return value, a message from a delegated sub-agent — is tagged at ingestion with a provenance label describing its origin. As the agent reasons, whether through explicit chain-of-thought, a "thought, action, observation" loop such as ReAct [5], or an internal planning structure, each new reasoning step records which upstream context units it drew on, forming a directed acyclic graph whose leaves are provenance-labeled sources and whose root is the candidate action.

A policy engine then evaluates a proposed tool call not by inspecting the call's content in isolation, but by inspecting the lineage graph behind it: does at least one principal-labeled node lie on a path that independently justifies this action, or can the action be fully explained by untrusted-only ancestry? Tools are assigned a risk tier in advance by the operator or system integrator — for example, a read-only lookup might be low risk, while sending a communication, spending funds, or modifying external state would be high risk — and the policy requires stronger provenance guarantees as the tier increases. Formally, for an action a of risk tier r, let anc(a) denote its ancestor set in the lineage graph; PBIG requires that for high-tier actions, anc(a) must contain at least one Principal-labeled node whose removal would make a no longer derivable from the remaining, untrusted-only ancestors.

This does not replace sandboxing, allow-listing, or content filtering — it is a complementary layer answering a question those layers cannot: not "is this tool call safe in isolation," but "did the right party actually ask for it."

4. System Architecture

The framework has five components, shown in Figure 1. An Instruction Tagger wraps every point where content enters the agent's working context — the initial request, tool results, retrieved documents, and sub-agent messages — attaching a provenance label at ingestion, before the model ever reasons over the content. A Context Composer assembles the tagged units into the model's working context for the current step. A Causal Lineage Tracker instruments the agent's reasoning loop to record, for each intermediate decision, which tagged context units it drew on, building the instruction-dependency graph described above. A Policy Enforcement Point intercepts every proposed tool call before execution, evaluates its lineage graph against the risk tier assigned to that tool, and either permits, blocks, or escalates the call for human review. An Audit Ledger appends every decision — permitted or blocked — together with its lineage graph, to an immutable log usable for incident forensics and later policy tuning.

Figure 1. Proposed Provenance-Bound Instruction Graph (PBIG) framework — a conceptual architecture for gating agent tool calls on instruction origin, not a deployed or benchmarked system.

5. Methodology

We outline how this framework would be built and evaluated, without claiming any of it has been implemented.

Constructing the lineage graph precisely requires instrumenting the agent's control loop rather than the underlying model, since current large language models do not expose a reliable internal signal for which input tokens caused a given output. A pragmatic middle ground — proposed here, not yet tested — is turn-level lineage: record which tagged context units were present in the working context at each reasoning step and treat all of them as candidate ancestors of the decision made at that step, accepting some over-approximation in exchange for tractable instrumentation. Token-level attribution via attention-weight analysis is a possible refinement but is itself unresolved, since attention weights are not guaranteed to correspond to causal influence.

We propose a three-phase evaluation. Phase one instruments an existing open agent framework with the Instruction Tagger and Causal Lineage Tracker at turn-level granularity, without enforcing any policy yet, to measure the overhead and coverage of tagging alone. Phase two adds the Policy Enforcement Point with a small set of hand-authored authority-propagation rules and measures its effect on a benchmark of both legitimate multi-tool tasks and adversarial indirect-injection scenarios. Phase three runs ablations varying lineage granularity, risk-tier definitions, and propagation-rule strictness, to characterize the trade-off between attack prevention and legitimate task completion. This protocol is proposed for future work; no results under it currently exist.

6. Threat Model

We assume an adversary who cannot modify the agent's model weights, system prompt, or the operator's own authenticated requests, but who can control content the agent will read during normal operation: a web page it browses, a document it is asked to summarize, an email in a mailbox it manages, or a response returned by a third-party API or tool server. The adversary's goal is to cause the agent to perform an action with real consequences — exfiltrating data, sending unauthorized communications, modifying records, or invoking a paid or destructive tool — that the operator did not intend and would not have approved if asked directly.

We assume the agent has genuine, legitimate access to the tools being misused; the vulnerability is not a missing permission but a permission exercised on the wrong party's behalf. We assume the operator's own instructions are trustworthy but that the operator cannot review every intermediate document the agent reads. We explicitly exclude from this threat model attacks on the model's training data or weights, infrastructure-level attacks on multi-tenant hosting, and scenarios where the adversary already has direct access to the operator's authenticated session — those require different defenses and sit outside PBIG's intended scope.

7. Evaluation Metrics

• Action-Level Attack Success Rate — the proportion of adversarial indirect-injection scenarios in which the agent still executes the attacker's intended action despite the defense being active; the primary security metric.
• Utility Preservation Rate — task completion rate on a benchmark of legitimate multi-tool tasks, comparing the framework enabled versus disabled, to quantify usability cost.
• Legitimate-Action Block Rate — the proportion of intended, operator-authorized actions incorrectly blocked or escalated by the Policy Enforcement Point.
• Provenance Coverage — the proportion of context units correctly tagged at ingestion; an untagged unit is treated as untrusted-or-unknown by the policy engine and can distort both attack and utility metrics.
• Lineage Construction Overhead — added latency and token cost per reasoning step from maintaining the instruction-dependency graph, relevant to whether the approach is practical at production scale.
• Cross-Agent Propagation Accuracy — in multi-agent settings, whether provenance labels survive correctly when one agent's output becomes another agent's input, since mislabeling here would silently launder untrusted content into a trusted category.

8. Research Challenges

Several open technical difficulties sit between this proposal and a working system. Causal attribution inside a transformer-based agent is fundamentally approximate: without a reliable way to say which parts of the input caused a given output, turn-level lineage risks both over-blocking — treating benign context as tainted because it shared a turn with untrusted content — and under-blocking — missing genuine causal paths that span multiple turns. Adversaries aware of a provenance-based defense could attempt semantic laundering: phrasing an injected instruction so the model's own subsequent reasoning "re-derives" the same conclusion in wording that appears self-generated, effectively erasing the paper trail the lineage tracker depends on; whether this is reliably detectable is itself unresolved. Defining risk tiers per tool is a policy exercise, not a purely technical one, and mis-tiered tools would leave the framework's guarantees only as strong as that manual classification. Finally, PBIG assumes cooperative instrumentation of the agent's control loop; it offers no protection if a component in the pipeline — a poorly instrumented plugin, a third-party sub-agent — fails to propagate or fabricates provenance tags, which points toward a need for tag integrity guarantees, not just tag presence.

9. Open Problems

Beyond PBIG specifically, the field currently lacks a shared vocabulary and benchmark for instruction-provenance attacks as a category distinct from general prompt injection, which makes it difficult to compare defenses across research groups. It remains unclear whether provenance tracking and the growing use of retrieval-augmented and multi-agent architectures are compatible at scale, since every additional hop — agent to agent, agent to tool to agent — is another point where labels must be carried forward correctly. There is also no settled answer for how much of this problem is solvable at the architecture layer at all, versus requiring model-level advances in faithful reasoning transparency — a question this proposal does not resolve and flags as a genuine open research direction rather than a solved problem.

10. Future Research

Promising directions include a standardized, framework-agnostic schema for instruction-provenance metadata, so tagging is interoperable across different agent runtimes and vendors; exploring cryptographic or hardware-backed attestation of instruction origin for the highest-consequence tool calls, where a probabilistic lineage graph alone may not be a strong enough guarantee; combining provenance-aware policy with complementary least-privilege tool scoping, so that even a successfully laundered instruction has a smaller space of actions available to it; and longitudinal red-teaming programs specifically targeting semantic laundering and cross-agent label propagation, since these are the failure modes most likely to undermine the framework in practice rather than the simpler single-hop injection case.

11. Conclusion

As autonomous agents take on tasks with real consequences, the question of whether an action traces back to an authorized instruction — rather than to content the agent merely happened to read — is becoming a central, underexamined part of agent security. Filtering content and restricting tools address adjacent problems but leave this specific gap open. Provenance-Bound Instruction Graphs are offered here as a concrete, structurally motivated direction for closing it: tag instruction origin at ingestion, track its causal lineage through an agent's reasoning, and gate consequential actions on that lineage rather than on content inspection alone. The framework has not been implemented or benchmarked; this article is a proposal intended to invite scrutiny, replication attempts, and refinement from the security research community, not a claim of a solved problem.

FAQ

Is this the same thing as prompt injection?

Indirect prompt injection [1] is the attack technique — getting an agent to treat externally sourced content as an instruction. The instruction provenance problem is the underlying architectural gap that makes the technique work: the absence of a mechanism for the agent to distinguish instruction origin at decision time. PBIG targets that underlying gap rather than any single injection technique.

Can't existing sandboxing or allow-listed tools already prevent this?

Sandboxing limits what a compromised decision can do; it does not prevent the decision from being made on behalf of the wrong party in the first place, especially when the tool being misused is one the agent is legitimately allowed to use. The two approaches are complementary, not substitutes.

Has PBIG been built or tested?

No. This article describes a proposed architecture, a threat model, and an evaluation protocol. No implementation, benchmark results, or empirical validation currently exist for this framework, and any performance figures would be hypotheses until that work is done.

Does this apply only to complex multi-agent systems?

The core mechanism — tagging instruction origin and gating high-consequence actions on lineage — applies to any agent that both reads external content and calls tools with real side effects, including a single-agent system with one tool. Multi-agent and multi-hop retrieval settings simply make correct label propagation across hops a harder version of the same problem.

Is provenance tracking a complete solution to agentic AI security?

No single mechanism is. PBIG is proposed as one layer addressing one specific structural gap; it should be combined with least-privilege tool scoping, content filtering, human review for the highest-risk actions, and ongoing red-teaming, consistent with the layered-defense principle already established in general LLM application security guidance [2].

References

1. Greshake, K., Abdelnabi, S., Mishra, S., Endres, C., Holz, T., & Fritz, M. (2023). Not What You've Signed Up For: Compromising Real-World LLM-Integrated Applications with Indirect Prompt Injection. arXiv:2302.12173.
2. OWASP Foundation. (2025). OWASP Top 10 for Large Language Model Applications (LLM01: Prompt Injection; LLM08: Excessive Agency).
3. National Institute of Standards and Technology. (2024). Artificial Intelligence Risk Management Framework: Generative AI Profile (NIST AI 600-1).
4. Debenedetti, E., Zhang, J., Balunović, M., Beurer-Kellner, L., Fischer, M., & Tramèr, F. (2024). AgentDojo: A Dynamic Environment to Evaluate Prompt Injection Attacks and Defenses for LLM Agents. arXiv:2406.13352.
5. Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., & Cao, Y. (2023). ReAct: Synergizing Reasoning and Acting in Language Models. International Conference on Learning Representations (ICLR).

This is a ScienceTrace research proposal. It presents a conceptual architecture, a threat model, and a planned evaluation protocol for a proposed defense against instruction provenance attacks in autonomous AI agents. It does not report an implemented system, benchmark results, or empirical validation of any kind.