Indirect Prompt Injection Is Becoming a Test-Time Search Problem

Introduction

Indirect prompt injection is often discussed as if the central question were whether a malicious instruction can persuade an agent to ignore its original task. For tool-using agents, however, the outcome depends on more than the wording of one injected message. The surrounding environment, the user’s objective, the available tools, and the attacker’s ability to explore different paths can all change the result.

The arXiv paper Rethinking Indirect Prompt Injection as a Test-Time Search Problem proposes a broader framing. It treats indirect prompt injection as a test-time search over an attack surface created by the environment, the user task, and the attacker’s injection task. This shifts attention from a static property of the victim to an interaction between attacker capability and system conditions.

Key points

• The attack surface is task-dependent. The paper argues that the relevant opportunities for injection are not fixed across all deployments. The environment and the task determine which content sources, tools, and interaction paths may become useful to an attacker.
• The attacker needs reconnaissance. To operationalize the idea, the researchers introduce an agentic attacker with a dedicated search harness. It inspects the environment, reasons about structured attack strategies, and uses feedback from the victim agent to decide what to try next.
• More test-time compute can improve attacks. Across heterogeneous tasks, increasing the attacker’s test-time compute improves the discovery and exploitation of vulnerabilities. This suggests that an evaluation result is incomplete if it reports only whether an attack succeeded without describing the search budget behind it.
• Strategy management matters at larger budgets. Ablation results indicate that explicitly tracking strategies helps avoid redundant attempts and preserves gains as the attacker receives more computation. Unstructured trial and error may waste budget, while managed exploration can cover a broader set of possibilities.

Why it matters

The paper’s main contribution is a change in how agent security evaluations can be interpreted. A system should not simply be labeled vulnerable or robust without specifying the conditions under which it was tested. The attacker’s search procedure, available computation, and ability to learn from the victim’s responses can materially affect the measured attack success.

This has direct implications for benchmarking. Future evaluations should document not only the victim agent and the injection task, but also the environment, the search algorithm, and the attacker’s test-time compute. Such reporting would make comparisons between defenses more informative and reduce the risk of treating a single attack result as a universal property of the model.

For defenders, the findings reinforce the need to look beyond isolated prompt examples. A capable attacker may inspect external content, form hypotheses about the agent’s behavior, try multiple routes, and use feedback to refine later attempts. Defenses therefore need to account for the boundary between data and instructions, unnecessary tool access, and the possibility that an agent’s behavior can be progressively probed.

The abstract does not present a complete mitigation recipe. Its broader warning is that adaptive search over the attack surface is itself an underexplored risk for tool-using agents. Indirect prompt injection is consequently better understood not as a single malicious string, but as an ongoing contest between an adaptive attacker and an agent operating in a complex environment.

arXiv