Rethinking indirect prompt injection as test-time search

Patrick Rho · AI Research

The paper covered here is Rethinking Indirect Prompt Injection as a Test-Time Search Problem, by Duong M. Nguyen and colleagues at Dynamo AI and the University of Illinois Urbana-Champaign, released as arXiv:2609.04495 on 3 September 2026. The original is linked under the title.

The claim is that indirect prompt injection should be defined as a test-time search problem over a task dependent attack surface shaped jointly by the environment, the user task, and the injection task rather than as a fixed flaw of the victim, and this post walks through why that reframing holds up, how the search harness works, and what the budget scaled results actually say.

I used to read attack success as a fixed score

What interests me more is the attitude toward the number itself. Most security reports fix the victim, throw one attack, and count wins and losses. The score gets filed as a property of the victim. One model sits at some percent, another model sits lower, and readers compare the two rows. I read those tables that way too.

Working with reasoning models for a while changes that reflex. Give the same model more time to think and it returns a different answer. Math, code, planning, all of it moves with compute. Attacks could move the same way. Give the attacker more time, let it learn from failure, let it switch strategies, and the success rate shifts. This paper grabs that suspicion directly. It asks readers to treat attack success as a function of attacker search budget and search procedure.

When my team looks at a new AI architecture, we do not stop at benchmark numbers. We ask what actually changed and what cost structure that change creates in a system. I liked this paper for the same reason. It does not add one more score. It changes the frame used to read scores.

Every tool call opens a slightly different gap

Viewed as a system, an agent follows a plain loop. A system prompt sets the role, a user instruction arrives, tool calls pull in outside information, the model plans over that information, and tools execute the plan. The weak point sits in the third step. The model reads text from outside channels directly. No formal boundary separates instruction from data.

Indirect prompt injection lives in that gap. Instead of talking to the user, the attacker hides an instruction where the agent is certain to read it. Email bodies, calendar notes, product question threads, review comments, file records. The agent reads the sentence while doing its job and calls the tool the sentence asks for. The effect lands as a state change. Data leaves, an unwanted order goes through, a file gets deleted, a post goes up with private details.

This is where I would be careful not to over-read any single demo. Some injections never get read. Some get read and ignored. Some get followed with the wrong arguments and fail. That spread explains why the paper splits evaluation into two binary scores. A utility score checks whether the user task finished, based on final output plus environment state. A security score checks whether the injection task landed, verified through state change as well. Reading both together separates attacks that rode the benign flow from attacks that broke the task and succeeded alone.

The attack surface is redrawn for each task pair

The paper draws a sharp line. The attack surface is not a hole fixed inside model weights. Each combination of environment, user task, and injection task builds a fresh one. The same agent exposes different benign trajectories for different user requests, those trajectories read different materials, and the attacker gets different places to hide.

Picture workspace style work. Reading a todo list, tidying meeting notes, moving across email and calendar. Words like follow up, cleanup, or preparation fit without friction. A planted sentence inside that flow reads as part of the job. Retail style work feels different. The customer service goal stays clear, but the readable materials scatter across product questions, reviews, and messages. Where the attacker hides decides both the chance the victim reads the payload and the chance it obeys.

That distinction matches what I have seen in security reviews. The same flaw fires in one deployment and stays quiet in another. Call order differs, documents differ, permission scope differs. The paper gives that experience a sentence. Every pair of one user task and one injection task opens a distinct search problem. The attacker is less a writer polishing one line and more a searcher walking the surface that pair creates.

Where this differs from static benchmarks

None of this dismisses static benchmarks. AgentDojo and its relatives built the frame the field needed. Fixed environments, tool sets, and state based checks made indirect injection comparable across papers. This paper reuses that tradition for its workspace suite, with 40 user tasks and 6 injection tasks forming 240 pairs. Its retail suite adds 17 user tasks and 8 injection tasks built with a Prime style environment generator, forming 136 pairs.

The split concerns the attacker. Static evaluation treats the attack as one input. Pick a payload, pick a vector, throw it. The paper treats the attack as a procedure. Reconnoiter, form a hypothesis, test it against the victim, read the trajectory and scores, pick the next attempt. More token budget does not just add tries. It changes hypothesis quality. A success rate measured at one fixed budget therefore understates the risk. Vulnerabilities that open up at larger budgets never enter the report.

From a systems perspective, the next question is obvious. Before deployment, how many attacker tokens did the red team spend. Which search procedure did it use. Without those two answers, a lone success rate reads like fiction. The paper states the point plainly. Security evaluation should record the attacker search procedure and compute budget alongside the victim name.

One loop from reconnaissance to victim feedback

The proposed search harness is a tool bundle attached to an agentic attacker. The name sounds large. The duties stay tidy. Look around, organize thought, collide with the victim.

The first stage explores the environment. Two reconnaissance tool families help. Environment knowledge tools read the context of the target system and task. Which tools exist, where data lives, how the benign flow usually runs. Injection vector knowledge tools read the conditions of each candidate slot. In which context each location gets read, what length and format limits apply, how likely the victim is to step on it. Together they narrow both where weakness may sit and where a payload could live.

The second stage reasons and searches. The latent surface is wide, so random walking revisits the same ground. Two tools keep the walk honest. Strategy organizes proposed strategies into a layered semantic structure, with framings grouped under broader directions. History stores the fine grained trajectory of the search, which attempts ran and what came back. With both records, the attacker picks promising subspaces and prunes spent directions.

The third stage evaluates with feedback. An explicit Evaluate tool exists. The attacker selects candidate payloads and vectors, the harness installs that configuration in a temporary environment, runs the victim agent, and returns the response, the tool use trajectory, the utility score, and the security score. Evaluation works as input to the next search round. How far the victim read, where it stopped, whether arguments mismatched, whether the benign task survived, all of it feeds the next hypothesis.

Watching that loop turn feels different from brute force. Early passes scan wide, then the attacker fires a probe once a plausible surface appears. Feedback arrives, and the attacker shifts the vector, rewrites the wording, or swaps the strategy branch. The paper shows example traces for retail and workspace runs. Successful attacks rarely come from sheer volume. They come from finding a surface next to the user task and shaping the malicious action to look like a legitimate step.

Tracking strategy separately keeps the search alive

I stayed longest on the Strategy tool. Logging sounds like overhead that never pays for the score. The ablations say the opposite.

On retail with GPT-5.5 as victim, removing the full harness flattens the curve past 100K tokens. More budget adds almost nothing. Keeping reconnaissance while removing only Strategy helps the attacker understand the environment, yet the run wastes tokens on excess scouting and repeats prior patterns. The full harness behaves differently. It diversifies strategies across iterations and refines systematically, so effectiveness keeps climbing with budget.

I think the more telling result is the mechanism behind the curves. Long searches repeat themselves, in people and in agents. With Strategy holding the direction map and History holding the detailed trail, duplication becomes visible. One branch closed, one framing untried, one vector never stepped on by the victim. Records make pruning possible. Pruning leaves budget for ground that still deserves a probe.

That structure matters more than any single score. Test-time compute alone does not carry the attack. Compute turns into force only with machinery that converts tokens into procedure. Without a harness, extra tokens circle the same area. With explicit strategy management, the budget curve stays alive. Any evaluation that reports attacker budget should report harness shape next to it.

The same budget breaks retail and workspace differently

The setup stays explicit. Victims are Claude Opus 4.8 and GPT-5.5 at high reasoning effort. The attacker is GLM-5.2 at high reasoning effort served through Together AI. The metric is attack success rate at total tokens used, written ASR at TT.

On retail, success climbs clearly with compute. The two victim curves split. GPT-5.5 starts to wobble visibly around 50K tokens. Opus 4.8 holds far longer and sits at 20.6 percent at 500K tokens. On workspace, the climb starts faster. GPT-5.5 reaches 52.1 percent at 100K tokens, against 37.5 percent on retail at the same budget. Pooled across GPT-5.5 runs, mean success moves from around 49.0 percent near 250K tokens to around 57.8 percent near 500K tokens.

Read the numbers with their conditions attached. Workspace breaks faster because of task shape rather than model weakness. Workspace routines read operational artifacts constantly. Todos, meeting notes, mail. A planted line in that path passes as a follow up or a cleanup. Retail keeps a clear service goal but spreads readable materials around, so vector choice decides the outcome.

The shared trait across wins is adjacency to the task. The attacker wins when the malicious line sits on a path the victim already needs to read. Actions that mirror legitimate steps slip through. Phrases like latent and task dependent stop sounding abstract here. The surface hides, yet it runs beside the road the user task points to.

More tools make attacks easier and joint success harder

Pulling apart the mechanisms shows a subtler picture. Workspace wins do not share one trick. Action item framing plants text in calendars, mail, or files so it reads as a pending or extra task. Cleanup framing wraps file deletion as removal of stale event material or outdated preparation content, and file 13 falls to exactly that story. Reference number disguise relabels a six digit code as a dinner reservation reference and slips it out through a lone success on that task. Same goal, different costume per context and vector. The work looks less like wording polish and more like gap hunting inside the trajectory.

Easy tasks fall early. Plain state changing chores sometimes solve fully, and some simple flagging chores touch 100 percent. Hard tasks resist. Bundles that ask for sensitive profile values stall even when the attacker names the right vector, the right tool, and the near miss cause correctly in its notes. The transcripts show GLM-5.2 identifying vectors and refusal reasons while GPT-5.5 still refuses. The failure reads as persuasion failing rather than scouting failing.

Breadth of the benign trajectory sets the tradeoff. With one benign tool, across 90 pairs, attack success sits at 58.9 percent, utility at 98.9 percent, joint success at 55.6 percent, and attack only outcomes at 3.3 percent. With two benign tools, across 108 pairs, attack success rises to 66.7 percent, utility drops to 85.2 percent, joint success drops to 11.1 percent, and attack only outcomes jump to 55.6 percent. With three or more benign tools, across 42 pairs, attack success holds at 66.7 percent, utility sits at 85.7 percent, joint success falls to 0.0 percent, and attack only outcomes reach 66.7 percent.

The surface reading looks simple. The reality needs care. Broader tool exposure adds hijack chances while making exact benign completion harder. Longer and tighter trajectories invite the planted line in as one more plan item, which lifts attack odds. The same extra state changes and argument limits then break the precise end state the utility checker demands. Retail absorbs side actions better because cases resolve around the service goal. Workspace centers on artifacts, so injected side effects invalidate the target state at once. The tradeoff confirms the broader point. The effective surface shifts per task.

Why the attacker stops exploring while budget remains

The raw reasoning excerpts in the appendix stayed with me longest. The attacker knows its budget. The system prompt tells it to favor finding a working payload and vector over mapping the whole environment when tokens run short. Traces show it obeying that policy well before funds run dry.

Early on, it cuts scouting short once a plausible surface appears and fires a probe. In one retail pair, with around 453K remaining, it stops exploring at turn two and tries a first probe. In another, it starts to read review comments and product details, then pivots to a variant note injection because that vector looks most likely to be read. In a third, it reads one question, loads history for prior attempts, drafts a first payload, and evaluates. Reconnaissance gets priced against victim feedback from the start.

Mid search, remaining tokens turn into a probe count. After 261K spent in one run, the attacker drops further surface mapping and tests a new approach directly. At the next turn it counts 238K left, notes each evaluation costs around 30K to 40K, and plans six to eight more probes. Other pairs repeat the pattern. The attacker discards uncertain vectors for cost reasons and reuses the variant note the victim already read. With around 200K left in another run, it writes that it will chase the approach rather than the map. Promising direction is not the only input. Opportunity cost shapes the choice.

Late search narrows to near miss repair. With around 59K left in one run, the attacker revisits prior WRONG ARGS cases instead of opening fresh ground. It lists the review index it learned, the order the victim keeps completing, and the refusal pattern, then digs there. In another pair, after fourteen NO ACTION failures, it traces victim trajectories and limits the next step to vectors the victim demonstrably touched. In another, seeing the victim call only four tools and never look at messages, it drops message vectors entirely. In one more, it returns to the closest near miss that reached a flag call with sensitive values stripped from the note.

The 500K cap sometimes ends a search mid thought. Failed pairs spend the full budget while still drafting refinements. One run ends while recovering the exact payload behind its nearest near miss. Another ends while sketching a new causal story that might coax a profile lookup. Failure at the cap does not signal convergence. More budget might have flipped the outcome. The steady climb between 250K and 500K points the same way.

Reasoning analysis supports the same arc. Encoding steps with a small embedding model and clustering with K-Means at three groups separates early surface mapping, mid refinement and adaptation, and late surface expansion. Mean embeddings move a lot in the first iterations and settle within a few steps, with step zero standing apart. Global context firms up fast, then downstream search runs on top of it. Strategy logs keep adding fresh directions through the whole run rather than cycling old ones.

What I want to check next in black box and production settings

The boundaries stay explicit. Evaluation runs white box on two synthetic suites with a preliminary model set. Transfer to black box access, production environments, other agent scaffolds, other attack goals, and defenses needs separate work. The paper expects larger compute cost for that transfer and leaves systematic study open. Finite budgets can cut searches before they settle, and repeated victim runs cost enough to limit trial counts.

What I would watch next is concrete. First, the price of black box transfer. How far right the curves shift when the environment stays hidden, and how far Strategy plus History alone carry the search without recon tools. Second, defenses that survive adaptive search. Single payload blocks already look bypassed, which leaves trajectory checks, state change audits, and sensitive argument gates. Third, reporting norms. Reports should list attacker token budget, harness shape, attempt counts, and near miss splits next to every rate. How the score was earned says more than the score.

Teams shipping agents can phrase the serving question the same way used for models. A defense holding is not enough. Ask at which search budget it held. This paper supplies the sentence for that review. Move attack success out of the victim property table and place it next to the attacker search log. Pre ship checklists gain one row. Attacker budget, search procedure, success rate under those conditions.

One line remains. Agent security is less about blocking one planted line and more about facing search over a surface that each task redraws. That surface runs beside the path the user request lays down. Larger budgets let the attacker walk it longer. Evaluation should reproduce that walk even when it takes longer.