From “rewrite the query” to “program the search”

Most “agentic search” systems today look the same under the hood: the model:

  1. Reads the current question and retrieved snippets.
  2. Emits a refined natural-language query.
  3. Calls a search API.
  4. Repeats until it decides to answer.

The only real control is query wording. The rest of the stack—how candidates are ranked, filtered, deduplicated, and which passages are actually shown—lives inside the search engine or a thin retrieval wrapper.

The Programmatic Search Agent (PSA) paper argues this is leaving performance on the table and empirically shows why. A trajectory analysis of query-based agents shows that:

  • Supporting passages can be retrieved, yet never delivered to the agent 1.
  • A “same-page oracle” intervention—changing only which evidence is returned for the same page—reduces how much subsequent search is needed 1.

So the bottleneck isn’t just “write a better query.” It’s which candidates get surfaced and how they’re processed between searches.

PSA’s answer: make “a local executable computation over candidates” the unit of a search action 1. Instead of emitting yet another query string, the agent emits a small program that:

  • Reads from a persistent candidate workspace.
  • Applies composable primitives over those candidates.
  • Selects what evidence to inspect next, under the agent’s explicit control.

The runtime resolves data dependencies inside each program cell; the policy learns how to adapt its overall search strategy cell-by-cell as new evidence arrives 1.

For builders, the core shift is: stop treating the search API as the only locus of control; give the agent a programmable substrate over retrieved candidates.

---

What PSA actually is

The PSA interface has three key ingredients 1:

  1. Persistent candidate workspace

There is a shared workspace that accumulates “candidates”—e.g., pages or passages returned by the common search substrate. This workspace:

  • Persists across the whole trajectory.
  • Lets later steps reuse earlier candidates instead of re-querying or discarding them.
  • Decouples *retrieval* from *presentation*: many things can be retrieved, only some get surfaced to the model.
  1. Flexible primitive composition

PSA exposes a set of primitives that operate on workspace candidates. While the paper does not enumerate their full list, it emphasizes that:

  • PSA “makes a local executable computation over candidates the unit of a search action” 1.
  • These primitives are flexibly composable into “program cells” that can reuse candidates and execute dependent operations 1.

Conceptually, think in terms of:

  • Basic operations like “fetch more candidates via the shared search substrate”, “filter by some property”, “combine or transform candidate content”, etc.
  • The agent doesn’t just call tools sequentially; it writes a small program that ties tools and workspace reads/writes together for a single step.
  1. Selective evidence presentation

A core design goal is controlling what the agent inspects next.

PSA’s program cells culminate in selecting which candidates’ evidence is fed into the model at the next step, instead of letting an opaque ranker decide 1.

This directly addresses the failure mode observed in the trajectory analysis: candidates that could close the task are retrieved but never shown to the agent 1.

---

How PSA’s control flow works

The PSA paper describes a two-layer separation of concerns: agent policy vs runtime.

  1. Agent policy: writes program cells over the workspace

At each high-level step, the policy:

  • Observes its current context (including selected evidence from previous steps).
  • Emits a program cell—a small, structured specification of:
  • Which workspace candidates it wants to use.
  • Which primitives to run, and in what dependency order.
  • Which resulting candidates should be surfaced as evidence for the next step.

These per-step programs are generated incrementally, allowing the agent to refine strategy as evidence accumulates 1.

  1. Runtime: resolves data dependencies and executes the cell

The runtime then:

  • Resolves the specified data dependencies within each cell 1.
  • Executes the primitives in an order that respects these dependencies.
  • Updates the persistent workspace with any new or modified candidates.
  • Produces the selected evidence the agent will see at the next step.

The runtime is deliberately narrow in scope: it doesn’t choose the strategy or which candidates matter—that’s the policy’s job. It only ensures the small program per step is executed correctly and deterministically.

  1. Strategy across cells

The policy, in turn, adapts across cells as new evidence is selected and inspected 1.

  • Within a cell: the runtime enforces the small computation.
  • Across cells: the agent decides whether to seek more breadth, drill down on promising candidates, or move toward answering.

This architecture essentially gives you a query planner over candidates, not just a query generator.

---

How PSA fits into a broader search stack

The PSA work is careful to control for underlying retrieval infrastructure:

  • PSA, the Query-based Agent, and the Tool-based Agent all share the same search substrate 1.
  • The Tool-based Agent also shares PSA’s primitives and persistent workspace 1.

The difference is how those capabilities are exposed:

  • Query-based Agent: can only change the query.
  • Tool-based Agent: can call tools (primitives) and use the workspace, but not as a structured per-step program.
  • PSA: makes the structured, executable program cell the basic unit of action.

This isolates the effect of moving control from “which tool to call” to “what program to run over the workspace”.

In terms of where PSA would slot into a production stack:

  • Below PSA: a search substrate that returns candidate pages/passages and stores them into the workspace. All agent variants use the same substrate in the paper 1.
  • At PSA level: the agent policy and runtime coordinating program cells over the workspace.
  • Above PSA: the task environment (e.g., question-answering benchmarks like InfoSeek-Eval and BrowseComp-Plus) and any outer orchestration that chooses which agent interface to use.

This is comparable in spirit to other agentic pipelines that factor their work into stages with explicit responsibilities and validation. For example, an independent work on flowchart relayout uses an agentic pipeline split into Parse, Style, and Layout stages, each paired with a critic that checks connectivity and uses VLM feedback to avoid silently breaking the graph 3. PSA is doing something analogous for search: factoring the “processing and presentation of retrieved evidence” into a programmable, checkable layer.

---

Why it matters: numbers, not slogans

PSA is evaluated against two baselines—Query-based Agent and Tool-based Agent—on two benchmarks:

  • InfoSeek-Eval
  • BrowseComp-Plus

All three agent interfaces share the same search substrate, and five different policy backbones are tested without task-specific training 1.

Key reported results:

  • Relative to the Query-based Agent, PSA improves macro-averaged task success by:
  • +4.00 percentage points on InfoSeek-Eval.
  • +7.56 percentage points on BrowseComp-Plus 1.
  • Within each backbone, PSA also reduces final-step tokens by:
  • 28.3% on InfoSeek-Eval.
  • 33.9% on BrowseComp-Plus 1.

These are non-trivial gains, especially considering:

  • The search substrate is held constant.
  • Tool-based agents already have access to PSA’s primitives and workspace; the main extra thing PSA adds is the program-cell formulation 1.
  • There is no task-specific fine-tuning of the policy backbones.

The paper’s authors interpret these results as evidence that extending agent control beyond query reformulation to the processing and presentation of retrieved evidence improves both success and efficiency 1.

For practitioners, the token reduction is particularly interesting: it suggests that smarter evidence selection doesn’t just help accuracy; it can materially cut compute costs at inference-time.

---

Design implications if you’re building agents today

The paper is focused on the PSA interface and empirical results, not on implementation guidance. But a few design patterns are clear from its interface choices 1:

  1. Introduce an explicit candidate workspace

Don’t just pass the last search result into the model and throw the rest away. Instead, persist all candidates you touch in a structured store. Even if you don’t immediately move to fully programmatic steps, this sets you up to reuse retrieved evidence later.

  1. Separate “search substrate” from “evidence selection”

The paper shows that even when “supporting passages can be retrieved yet never delivered to the agent,” changing only what evidence is returned from the same page can reduce how much further search is needed 1. That argues for:

  • Keeping your search/index layer simple and robust.
  • Focusing agent innovation on the selection and transformation of candidates already in-hand.
  1. Treat each step as a program, not a tool call

PSA’s central idea is that a search action is a “local executable computation” that can read and write the workspace, compose multiple primitives, and end in a deliberate evidence selection 1.

In practical terms, you can think about:

  • Letting the model specify multi-primitive plans that run without another LLM call.
  • Making intermediate steps (filtering, scoring, grouping) explicit and inspectable.
  • Having a narrow, deterministic runtime layer to enforce data dependencies.
  1. Measure both success and token costs

PSA’s results highlight that interface design alone (holding model and search substrate fixed) can improve both task success and token usage by double-digit percentages 1.

If you’re evaluating search agents, don’t only track final accuracy; track:

  • Number of search actions.
  • Number of tokens at the final step.
  • How many retrieved candidates are never surfaced to the model.

Those metrics can show whether better evidence selection is actually happening.

---

What to watch next

PSA opens a direction where agent interfaces look more like embedded programming languages over shared workspaces than simple tool menus.

In parallel, other agentic systems are also moving toward:

  • Factored pipelines with explicit checking, like the Parse–Style–Layout agent+critic pipeline for flowchart relayout, which reaches 68.6% content fidelity compared to 11.2–41.4% for prior work on a curated benchmark 3.
  • More structured internal state, such as normalized storage layers in verification-oriented agents (e.g., relational databases over simulation dumps in other work 7).

The common thread is: move complexity out of the language model’s hidden state and into explicit, inspectable substrates plus small, verifiable programs. PSA is one concrete instantiation of that idea for web/search-style tasks.

---

What is not documented

From the available text, the PSA paper does not document:

  • The exact list and semantics of the primitives exposed to the Programmatic Search Agent.
  • The internal schema or implementation details of the persistent candidate workspace.
  • The precise structure, syntax, or representation of the “program cells” the agent generates.
  • The specific policy backbones used (model families, sizes, or providers).
  • Wall-clock runtime overheads, latency breakdowns, or compute costs of PSA vs baselines.
  • Detailed failure cases or ablation studies beyond the headline performance and token results.
  • Any concrete API design, code snippets, or implementation recommendations for production systems.

Any implementation details or design patterns beyond what’s explicitly stated above should be treated as extrapolation, not as claims about the PSA paper itself.