acceptodds
Under review as a conference paper at ICLR 2027

VISTA: Learning Wide Search Agents with Verifiable Intermediate States and Turn-Level Credit Assignment

102 views

Abstract

Wide search requires agents to explore many target items, track which ones they have covered, and combine their findings. Yet existing systems largely rely on designed multi-agent systems. Training capable open-source wide-search agents is challenging because reinforcement learning with verifiable rewards (RLVR) typically assigns credit to an entire trajectory, making it difficult to identify the few decisions that matter most in long interactions. We propose VISTA (Verifiable Intermediate States for Turn-level Attribution), a reinforcement learning framework that transforms sparse outcome supervision into fine-grained turn-level credit. Our key insight is to make otherwise latent search progress explicit and verifiable through intermediate table states that track the agent's accumulated discoveries. VISTA uses changes across consecutive states to attribute credit to the responsible turns, while preserving the terminal outcome as the dominant learning signal. Across six benchmarks and seven models, ranging from 4B to 27B, VISTA consistently outperforms outcome-only GRPO and step-wise RL baselines. On WideSearch, VISTA improves Item F1 by 13.84% relative over outcome-only GRPO on Qwen3-4B, with consistent gains across other model families and scales, and further generalizes to standard multi-hop QA benchmarks. Extensive ablations show that the gains come not merely from adding process supervision, but from making intermediate progress verifiable and assigning credit to the responsible turns. These results highlight that where and how credit is assigned is critical for training long-horizon search agents.

Primary area:
reinforcement learning
Keywords:
Agentic search, Reinforcement Learning, Search Agent, Credit Assignment

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_EE8GOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes VISTA, a RL framework for wide-search tasks. VISTA works by prompting the policy model to output a table at each search turn, allowing intermediate reward signals during RL. These signals are used to redistribute credit within the trajectory, keeping the final outcome as the primary reward signal. Experiments on a wide variety of model families show strong performance, and show that VISTA training also transfers well to multi-hop QA evaluations.

Critical strengths
  1. Experimentation seems thorough, with a wide range of model families and evaluations tested.
  2. The key idea behind the method (output partial progress at each stage) is fairly straightforward and reasonable, and the ablations around reward shaping (ensuring dominant terminal state, etc) are useful. I like the comparisons of keeping intermediate answers in/not in the context too, which feels a bit different to recent popular meta-RL work (e.g., https://arxiv.org/abs/2603.11327, https://arxiv.org/pdf/2602.13949).
  3. The results in Appendix B are especially interesting, digging further into how to correctly structure the process rewards.
Critical weaknesses
  1. In Figure 3, it seems to show that the GRPO baseline drops after training, and this is reflected also in the Qwen3-8B results table, which feels a bit odd and potentially a sign of poor baseline tuning (e.g., some KL penalty, or adjusting the LR could help perf). Especially since GRPO seems to improve for all other base models.
  2. VISTA costs more compute to run (extra judge, ignoring decode costs), and reaches the final quality values in Table 19 far slower than GRPO. But there is (AFAIK) no compute-matched comparison of VISTA to GRPO (this could be especially interesting given the VISTA-trained models seem to be more token efficient - does this offset the extra judge cost?). Could it be that a well-tuned GRPO baseline given the same training compute as VISTA performs just as well, if not better? Especially for larger models where VISTA’s relative gains are smaller? What happens at different training budgets?
  3. This method seems very domain specific, with evaluations limited to agentic search tasks, limiting impact.
Questions for authors
  1. How were hyperparameters tuned/chosen, and did authors attempt to fix the collapsing/poor later performance in WebLeaper+Format GRPO results, seen in Figure 3?
  2. What is the standard deviation / error bars on the evaluations? Alot rests on WideSearch, with only ~200 questions, so I’m curious how noisy the evaluation is. The gaps in performance do seem wide, so I think the method is probably effective, but it could be that e.g. the better performance of VISTA on Qwen3.8-27B is within noise.
  3. What model training curves is Figure 3 showing? I am curious what these curves look like for all models, especially ones where VISTA does not drastically improve over the GRPO baseline.
Reviewer_864MOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

VISTA studies how to train agents for wide search: finding many entities and organizing their attributes into a complete answer table. Standard outcome-only GRPO gives every action in a trajectory the same advantage, providing little guidance about which search steps were useful.

Its main contributions are:

  • Explicit intermediate states: After each interaction, the framework extracts and scores a partial answer table. VISTA-Inc keeps it outside the agent’s context; VISTA-Mem also exposes it as working memory.
  • Turn-level credit assignment: Intermediate-state signals modify each turn’s advantage. A terminal-dominant projection bounds nonterminal advantage magnitudes below the final-answer turn’s magnitude.
  • An empirical finding: Intermediate states and turn-level attribution work best together; adding memory or process rewards alone is insufficient.

Validation spans three wide-search benchmarks, three multi-hop QA benchmarks, and multiple model families and sizes. On WideSearch with Qwen3-4B, VISTA-Mem improves Item F1 from 32.16 to 36.61 over GRPO+Format—a 4.45-point absolute / 13.84% relative gain. Component and credit-placement ablations support the combined design; replacing the LLM state scorer with deterministic matching retains much of the benefit. Behavioral analyses show less repeated search, and cost measurements indicate higher training cost but lower inference cost than that GRPO baseline.

The evidence is promising but qualified: improvements are not universal across backbones or metrics, exact-table success remains low, and QA transfer varies by model. Most importantly, the manuscript inconsistently defines process credit as either state-quality differences or centered, length-scaled state quality, leaving the precise implemented attribution mechanism unclear.

Critical strengths
  • The paper offers a useful, task-grounded approach to process supervision. Explicit partial answer tables make otherwise latent search progress measurable, while terminal-dominant credit assignment keeps intermediate supervision anchored to answer completion. This combination addresses a practical difficulty in training search agents: collecting useful evidence does not necessarily translate into producing a correct final answer.
  • Controlled ablations provide substantive evidence for the combined design. On WideSearch-EN, combining memory and turn-level attribution achieves 40.17 Item F1, versus 35.00 with memory alone and 37.34 with attribution alone. Holding the reward and memory mechanism fixed, terminal-dominant attribution also outperforms reward-to-go (35.90) and terminal-preserved attribution (36.96). These comparisons are consequential because they support a specific methodological contribution beyond simply adding memory or richer rewards.
Critical weaknesses

The experiments support the combined method’s effectiveness, but do not directly establish the importance of assigning state-derived credit to the corresponding turns. Tables 2 and 12 demonstrate the benefits of intermediate states and terminal-dominant advantage assignment, but do not test whether the particular correspondence between credit values and turns matters. A useful diagnostic would randomly permute local credits among nonterminal turns while leaving the trajectory reward, memory states, terminal credit, and projection procedure unchanged. For example, if three search turns receive local credits (-0.06, 0.02, 0.04), the control could assign them (0.04, -0.06, 0.02) instead. This preserves the credit values but breaks their association with the original turns. A substantial performance drop would support the importance of that association; little change would weaken the attribution interpretation. Such a test would not establish causal attribution by itself, but would strengthen the evidence for the paper’s central mechanism beyond the effectiveness of its overall weighting scheme.

Questions for authors

Please refer to the Weaknesses.

Reviewer_RezZOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces VISTA, a GRPO-based framework for long-horizon wide-search agents. VISTA externalizes search progress as structured intermediate answer tables, scores these states against the ground-truth table, and uses the resulting process signals for turn-level credit assignment. To prevent intermediate rewards from overwhelming the final task objective, it further proposes a terminal-dominant projection that keeps the final-answer turn as the strongest learning signal. The paper studies two variants, VISTA-Inc and VISTA-Mem, where the latter also feeds the intermediate table back to the agent as working memory. Experiments across multiple model scales and wide-search benchmarks show consistent improvements over related methods.

Critical strengths

The paper is generally well-written. The proposed method seems reasonable and effective. The experimental results are comprehensive.

Critical weaknesses

The reward-weight sensitivity analysis may be difficult to interpret and possibly unreliable for the following two reasons.

The terminal state appears to be emphasized through multiple pathways. In particular, the terminal state appears to receive supervision through multiple pathways: the final-answer reward R o u t R out , its contribution Q T Q T ​ to R p r o c R proc , and the centered local credit ℓ T ℓ T ​ , after which terminal-dominant projection further preserves it as the strongest advantage. λ p r o c λ proc ​ appears to scale only the trajectory-level process reward R p r o c R proc , while the local process credit ℓ t ℓ t ​ is added directly to the turn-level advantage without the same coefficient. As a result, varying λ p r o c λ proc ​ may not substantially change the overall strength of process supervision, which could partly explain the reported insensitivity to reward weights. The current sensitivity results therefore do not fully establish robustness to the true outcome–process trade-off. Given the relatively large number of interacting hyperparameters and design choices in the proposed method, the reliability of the ablation and sensitivity analyses is particularly important and become my major concern of this paper.

Questions for authors

Could the authors provide an ablation that excludes Q T Q T ​ from the process reward and local process credit, so that process supervision is applied only to non-terminal turns?

Could the authors additionally evaluate a variant where ℓ t ℓ t ​ is also multiplied by λ p r o c λ proc ​ , to test whether the method is truly insensitive to the overall strength of process supervision?

1 comment

Thank you for the rebuttal. It addressed most of my concerns. I therefore raised my rating from 2 to 3.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions and Responses to Reviewer Feedback

Dear Area Chairs and Reviewers,

We sincerely thank all reviewers and the Area Chair for the careful reading, constructive feedback, and continued engagement. We summarize the recognized strengths and clarify how we addressed the main concerns. We have uploaded our revised manuscript with all changes highlighted in blue. 

We are grateful that several key strengths were recognized:

  • The key idea is "straightforward and reasonable" (Reviewer EE8G), and the process supervision approach is "useful"(Reviewer 864M).
  • The proposed method "addresses a practical difficulty in training search agents" (Reviewer 864M) and "seems reasonable and effective" (Reviewer RezZ).
  • The experiments are "thorough" (Reviewer EE8G) and comprehensive (Reviewer RezZ). Ablations are "useful" (Reviewer EE8G) and provide "substantive evidence" (Reviewer 864M). The preliminary analysis are "especially interesting" (Reviewer EE8G).
  • "The paper is generally well-written" (Reviewer RezZ).

Below is a summary of the revisions and how we addressed the reviewers' concerns:

  1. Clarification of the terminal state entering pathways (Reviewer RezZ, Weakness 1 and Question 2): We have corrected the mathematical descriptions of the trajectory-level process reward and the per-turn process reward.

  2. Ablation studies on the process reward, including excluding QTQ_T from the local process credit (Reviewer RezZ, Question 1) and the random permutation study (Reviewer 864M, Weakness 1):

    • We added Table 23: Ablation of terminal-aware centering for the local credits (Appendix D.8.1).
    • We added a random permutation row to Table 2 (Component ablation of VISTA on WideSearch-EN). The result supports the importance of matching state-derived credits to their corresponding turns.
  3. Noise evaluation (Reviewer EE8G, Question 2): We report three analyses, covering evaluation noise, training-seed noise, and the noise in the empirical gains. All results and analyses are included in Appendix D.8.2.

We also added a discussion beyond WideSearch (Reviewer EE8G, Weakness 3) in Appendix D.7. In addition to the revisions above, we respond to the questions of baseline tuning and hyperparameter selection (Reviewer EE8G, Weakness 1, Questions 1 and 3) and the compute-matched comparison (Reviewer EE8G, Weakness 2) in our individual rebuttal responses.

We are encouraged that Reviewer 864M indicated the rebuttal addressed their main concerns and that they would maintain their positive rating, and that Reviewer EE8G indicated they would keep their score and recommend acceptance.

Thank you all again for your reviews and for bringing these points to our attention!

Best,

Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.