Can programmatic search agents extend agentic search beyond query reformulation?

The bottleneck is not only finding evidence

A fixed search(query) interface lets an agent rewrite its query but not decide which candidates are retained, how they are ranked, or which passages come back. The paper's motivating trajectory analysis on BrowseComp-Plus found that supporting passages could reach the extraction stage without ever appearing in the agent's observations, and that later search recovered only some of these omissions.

The authors separate complete omissions, where the target response returns no verified support, from partial omissions, where it returns some but omits other supporting passages. In a same-page oracle intervention, delivering a supporting passage from the same retrieved page raised judge-based task success by 16.7 percentage points and reduced mean subsequent search decisions by 64.0% for complete omissions. Partial omissions showed no net success gain, which the authors read as evidence that changing presentation matters most when the target response otherwise exposes no verified support. This is a controlled intervention on an analyzed cohort, not a claim that every omission is repairable.

What a program cell changes

PSA replaces the query or the single tool call with a program cell: an incremental, executable computation over candidates submitted through run_program(code). Successful named variables persist between cells, so candidates remain available as read-only records carrying source identifiers, content, and query provenance. Collection operations transform views without modifying the source records.

The runtime resolves specified data dependencies inside a cell, while the agent adapts strategy across cells as new evidence arrives. A cell can filter retained candidates, conditionally retrieve and merge more, then rerank and extract within one action. The paper's illustrated cell does exactly this: filter the retained pool, check whether it is large enough, retrieve and dedupe if not, then rerank and extract. Only extraction adds to the cumulative evidence ledger, and the runtime neither summarizes the cell output nor imposes a character limit on it.

Three interfaces share one search substrate

The comparison is deliberately narrow. All three interfaces share the same search substrate and primitive semantics, and the Tool-based Agent also shares PSA's primitives and persistent workspace. The runtime enforces a 20/10/10 per-call funnel: retrieve returns at most 20 documents, rerank retains at most 10, and extract selects one passage per document from at most the first 10 input documents. Because a cell may compose several calls, these caps and the 50-decision budget do not equate total primitive work across interfaces.

The evaluation uses InfoSeek-Eval and BrowseComp-Plus with five policy backbones and no task-specific training. That design isolates the interface as the variable of interest, but it also means the reported gains are tied to these benchmarks, these backbones, and this shared substrate rather than to search agents in general.

Success gains come with fewer final-step tokens

On InfoSeek-Eval, PSA's macro-averaged success rate is 81.53%, against 77.53% for the Query-based Agent and 79.73% for the Tool-based Agent, gains of 4.00 and 1.80 percentage points. On BrowseComp-Plus the rates are 55.45%, 47.90%, and 48.12%. PSA has the highest task success for all five backbones on InfoSeek-Eval and four of five on BrowseComp-Plus; the exception is GPT-5.6-Luna, where the Tool-based Agent leads.

Token savings move in the same direction. Macro-averaging relative reductions within each backbone gives 28.3% and 46.3% savings on InfoSeek-Eval, and 33.9% and 54.5% on BrowseComp-Plus, relative to the Query-based Agent and the Tool-based Agent respectively. With Qwen3.8-Flash on InfoSeek-Eval, PSA cuts final-step tokens from 93.9K to 23.5K versus the Query-based Agent while raising task success from 72.67% to 82.00%. Primitive-level accounting for the complete DeepSeek-V4.1-Flash runs indicates the gains do not require uniformly increasing search-substrate computation.

Recall and success measure different things

Supporting-document Recall measures coverage of annotated supporting documents, not whether the final answer is correct. On BrowseComp-Plus, PSA reaches macro-averaged Recall of 56.87%, against 52.41% for the Query-based Agent and 55.44% for the Tool-based Agent, gains of 4.46 and 1.42 percentage points. PSA has the highest reported Recall for four of five backbones; the exception is Qwen3.8-Flash, where the Tool-based Agent reaches 68.02% versus PSA's 65.82%. The largest gain over the Query-based Agent appears with Hunyuan-4-Preview, from 55.63% to 65.49%.

The two metrics can diverge, and the paper reports them separately for that reason. A higher Recall means more annotated supporting documents were covered; it does not by itself establish a higher answer-level success rate, and the backbone-level exceptions show the two orderings are not identical.

Separating retention from presentation

A paired experiment on 128 BrowseComp-Plus tasks, run once per arm with GLM-5.3-Flash, tests presentation directly. Both arms share the PSA prompt, feedback-format notice, persistent workspace, 20/10/10 funnel, and 50-decision budget. Selected feedback displays the program-selected result; full-view feedback additionally exposes all current-cell extracted rows with complete source notes.

Selected feedback reduced returned text by 37.2% (paired bootstrap 95% CI: 7.7–56.6%). Point estimates also show 3.91 percentage points higher task success and 24.5% lower final-step tokens, 27.9K versus 36.9K. The authors read this as support for separating retention from presentation: candidates stay reusable without placing every extracted note in the policy's context. The success and token differences here are point estimates, and the interval reported for returned text is the one the paper quantifies.

The advantage depends on decision budget

A budget sweep compares the Query-based Agent and PSA on 128 uniformly sampled BrowseComp-Plus tasks with Qwen3.8-Flash at 10, 20, 30, 40, and 50 decisions. Runs at each limit are independent and share the budget notice and the 20/10/10 funnel; the Query-based Agent supports parallel searches per decision.

PSA exceeds the Query-based Agent's task success by 11.72–13.28 percentage points at limits of 30–50 while using 38.3–40.9% fewer final-step tokens. It also achieves higher success at limits of 20–50. At 10 decisions, however, PSA's success is 35.16% versus 39.06% for the Query-based Agent. Across the tested limits the baseline's task success stays within 31.25–39.06% while its final-step token use grows from 31.7K to 141.6K. The pointwise 95% intervals for the PSA-minus-baseline success difference include zero at limits 10 and 20 and lie above zero at 30–50; those intervals capture task-sampling uncertainty, not repeated-run variation, and are not adjusted for multiple comparisons.

Where the interface claim holds

The paper's own framing is that these results support extending agent control beyond query reformulation to the processing and presentation of retrieved evidence. The evidence for that claim is bounded: five policy backbones, two benchmarks, no task-specific training, a shared search substrate, and a 50-decision budget. The Tool-based Agent shares PSA's primitives and persistent workspace, so the comparison that isolates the program-cell unit is PSA versus the Tool-based Agent, while the headline 4.00- and 7.56-point gains are measured against the Query-based Agent.

The most decision-relevant split is the decision budget. Below roughly 20 decisions PSA does not lead on this cohort, and the reported advantage appears at 30–50 decisions, where it combines higher success with 38.3–40.9% fewer final-step tokens. For a reader weighing whether to give an agent control over candidate processing, the paper's priority is that threshold: the interface pays off when the agent has enough decisions for reuse and reprocessing of retained candidates to matter, not as a uniform improvement at every interaction limit.

Sources used in this answer