CAFE: Self-Improving Search Agents Need Co-Evolving...

CAFE: Self-Improving Search Agents Need Co-Evolving... | AI Research

Key Takeaways

CAFE (Coupled Agent–Feedback Evolution) is a framework designed to improve how search agents handle long-horizon tasks by integrating learnable, in-trajector...
Outcome-supervised search agents learn when and how to retrieve evidence, but terminal rewards neither localize intermediate errors nor redirect an ongoing trajectory before those errors compound.
We introduce CAFE (Coupled Agent--Feedback Evolution), a framework in which a shared-parameter model alternates between search-agent and critic roles.
CAFE initializes feedback-conditioned recovery from trajectories built around the base agent's own failures, then couples online and offline optimization.
During online RL, a comparative feedback estimate uses a prompt-level call--skip success gap to shape request returns, while feedback-aware advantage shaping reweights token advantages before and after feedback.

Paper AbstractExpand

Outcome-supervised search agents learn when and how to retrieve evidence, but terminal rewards neither localize intermediate errors nor redirect an ongoing trajectory before those errors compound. Treating corrective feedback as a learned in-trajectory intervention couples the two roles: the agent must decide when to request and use feedback, while the critic must infer useful corrections from outcome-confounded rollouts whose failure patterns shift as the agent improves. We introduce CAFE (Coupled Agent--Feedback Evolution), a framework in which a shared-parameter model alternates between search-agent and critic roles. CAFE initializes feedback-conditioned recovery from trajectories built around the base agent's own failures, then couples online and offline optimization. During online RL, a comparative feedback estimate uses a prompt-level call--skip success gap to shape request returns, while feedback-aware advantage shaping reweights token advantages before and after feedback. Offline, rollout-derived preference optimization learns feedback from matched successful and unsuccessful trajectories. On seven agentic search benchmarks, CAFE outperforms the evaluated RL-based search agents on average, retains its gains across all six out-of-domain benchmarks, and reduces answer-level hallucinations. One-sided ablations show that improving only the agent or only the critic eventually plateaus, whereas alternating the two updates continues to improve performance. These findings suggest that a self-improving search agent needs feedback that co-evolves with the policy it guides.

CAFE (Coupled Agent–Feedback Evolution) is a framework designed to improve how search agents handle long-horizon tasks by integrating learnable, in-trajectory corrective feedback. Instead of relying solely on terminal rewards—which often fail to pinpoint where a search went wrong—CAFE uses a shared-parameter model that alternates between acting as a search agent and a critic to diagnose and correct errors in real time.

Addressing Search Errors

Search agents often encounter "compounding errors," where a small mistake early in a search leads to unproductive actions that are difficult to reverse. Traditional outcome-supervised agents receive a reward only at the very end of a task, making it impossible to identify the specific step that caused a failure. CAFE addresses this by allowing the agent to request feedback during the search process. When a request is made, the model switches to its critic role to provide a corrective step, which is then appended to the search history to guide the agent back on track.

The Co-Evolution Mechanism

The framework relies on a shared-parameter model to perform both agent and critic duties, which the authors argue must "co-evolve" to remain effective. As the agent improves its search strategy, the types of failures it encounters change; therefore, the critic must also adapt to provide relevant guidance. CAFE manages this through two primary optimization strategies:

Online RL: The agent learns when to request feedback using a "comparative feedback estimate," which compares the success rates of rollouts that use feedback against those that do not. It also uses "feedback-aware advantage shaping" to redistribute credit, ensuring the agent is rewarded for the recovery that follows a correction rather than just the initial mistake.
Offline Refinement: The framework uses "rollout-derived preference optimization" (RDPO) to refine the critic. By comparing successful trajectories that used helpful feedback against failed ones that used ineffective feedback, the model continuously updates its ability to generate better corrections.

Performance and Generalization

In evaluations across seven agentic search benchmarks, including 2WikiMultihopQA, HotpotQA, and MuSiQue, CAFE outperformed existing RL-based search agents. Using a Qwen2.5-7B-Instruct backbone, the framework achieved an average of 52.5 EM (Exact Match) and 60.7 F1 scores, surpassing the next-best RL-based baseline by 2.1 EM and 1.3 F1. The authors report that these performance gains were consistent across six out-of-domain benchmarks and resulted in a reduction of answer-level hallucinations from 17.6% to 12.6%.

Why It Matters

The findings suggest that the performance of self-improving agents is limited if the feedback mechanism remains static. The authors’ ablations show that improving only the agent or only the critic leads to a performance plateau. By alternating updates between the two roles, CAFE maintains alignment between the agent’s evolving policy and the critic’s feedback, demonstrating that sustained improvement in search agents requires a coupled approach where both capabilities evolve in tandem.