CAFE: Self-Improving Search Agents Need Co-Evolving Feedback
Boyang Liu, Senjie Jin, Peixin Wang, Zhangyue Yin, Yibo Wang, Yuhao Zhou, Xinbing Liang, Shizheng Zhu, Yuhui Wang, Jingqi Tong, Zhiheng Xi, Jiazheng Zhang, Clive Bai, Clarenceai, Blaze Chen, Tao Gui, Qi Zhang, Xuanjing Huang
cs.AI
2026-08-26
CAFE alternates a shared 7B model as search agent and critic; average EM is 52.5 on seven SearchQA sets, 2.1 above IGPO, with hallucinations down from 17.6% to 12.6%.
Outcome-supervised search agents such as Search-R1 learn when and how to retrieve from a terminal correctness bit. In a long search, an early wrong turn can poison every later query, and the final reward cannot say where. Reflexion, Self-Refine, and CRITIC can emit natural-language critiques, but they are mostly prompted after the fact. They do not teach the agent when to ask for help inside the live trajectory, or which tokens a rescued success should reinforce. ECHO co-evolves a critic, yet that critic only speaks once the trajectory is already finished.
The coupling is the real problem. The agent must learn when a request is worth making. The critic must write useful corrections from outcome-confounded rollouts whose failure modes shift as the policy improves. A frozen critic falls behind.
CAFE, from Fudan and Tencent, puts both roles in one shared-parameter model. Mid-trajectory the agent may emit <requestfeedback>. The same backbone then speaks as critic, names a corrective next step, and hands control back.
Bootstrap SFT does not replace a failed rollout with an ideal one. The base agent's own erroneous prefix is kept. Kimi-K2.5 marks the earliest stalled turn, inserts a request plus a repair, and only repaired trajectories that reach the gold answer are kept. The model therefore learns to ask for help in states its own policy actually visits.
Online RL adds two credit signals on top of GRPO. CFE estimates the prompt-level success gap between rollouts that request feedback and rollouts that skip it, then adds that gap to the request-side return and penalizes requests after the first. Feedback-aware advantage shaping splits a successful rescue: tokens before the request are down-weighted (they drove the search off course), tokens after it are up-weighted (they recovered). Without that split, the same terminal reward would reinforce both the mistake and the fix.
Offline, RDPO mines prefix-matched success/failure pairs from the latest on-policy rollouts and prefers the feedback text from the successful one. Because the two roles share weights, that update changes both sides for the next round. The default schedule is 100 online RL steps times five alternations.
The backbone is Qwen2.5-7B-Instruct. Only 2WikiMultihopQA is in-domain; the other six benchmarks are held out.
| Method | Avg EM | Avg F1 |
| Qwen2.5-7B backbone | 38.1 | 47.9 |
| SFT | 40.8 | 50.1 |
| SFT + GRPO | 49.7 | 58.0 |
| IGPO (strongest RL baseline) | 50.4 | 59.4 |
| CAFE | 52.5 | 60.7 |
That is +2.1 EM and +1.3 F1 over IGPO. Versus Search-R1, the lift is +7.4 EM on four multi-hop sets and only +1.3 on three single-hop sets, which matches the claim that mid-trajectory correction matters more when later retrievals depend on earlier ones. At 3B, CAFE reaches 48.8/57.4, above Search-R1-3B at 42.7/51.9. Answer-level hallucination falls from 29.9% (backbone) to 17.6% (GRPO) to 12.6% (CAFE), with the largest extra drop versus GRPO on NQ (10.8 points).
One-sided updates plateau. Feedback-only moves 67.7 to 71.3; agent-only peaks at 84.2 then ends at 83.6; alternating updates reach 86.6. From iterations 3 through 5, each agent scores best with the critic from the same round. The gain is alignment with the current failure distribution, not a uniformly stronger critic.
For anyone training a search agent, the usable claim is narrow: terminal rewards and post-hoc reflection are not enough. Correction has to be an in-trajectory action, and the writer of that correction has to move with the policy. CFE and advantage shaping are credit-assignment tools, not another prompt template. Sharing parameters saves a second model and also lets the two roles contaminate each other, which is why RDPO's relative objective beats SFT on successful feedback alone.
On BrowseComp-Plus the same 7B checkpoints move EM from 4.4 to 7.7. The trend holds. The absolute number does not. CAFE is credit engineering for search QA, not a general deep-research solver.
There is no dedicated limitations section. Cold-start SFT depends on a stronger teacher, Kimi-K2.5; how many failures it repaired, and at what scale, is not reported. IGPO was reproduced from the authors' SFT checkpoint, while Search-R1 and R-Search numbers are taken from the original papers, so the protocol is not fully matched. Hallucination is defined as an answer containing a claim unsupported by retrieved evidence, which can flag correct parametric knowledge. 7.7 EM on BrowseComp-Plus shows that long-horizon browsing is still barely touched. Only Qwen2.5 3B and 7B were trained.