ClueFlow: Solving Long-Horizon Search with Attributed State Transitions

Long-horizon search tasks require AI agents to continuously gather evidence in open environments and integrate fragmented information into an evolving research state. Existing methods either maintain a state solely to guide exploration, or assign a progress signal to each interaction round—but few ask: which specific state change should these signals actually be attached to? ClueFlow's answer is to make every evidence acquisition and every state update attributable and traceable.

The Supervision Dilemma of Long-Horizon Search: Signals Exist, but Attribution Is Unclear

On benchmarks like BrowseComp that require multi-step retrieval, agents often need to perform dozens of browser operations to piece together an answer. The traditional approach maintains a "research state" that records collected evidence and candidate answers, then uses it to guide the next exploration step. The problem is that when the final answer is correct or incorrect, it's hard to determine which specific retrieval actions played a role.

ClueFlow's starting point is straightforward: if every state change can be traced back to the browser action that triggered it, and to the final answer's dependence on that change, then supervision signals and credit assignment have a clear target. The paper calls this structure the "Source-State-Final attribution chain"—a verifiable causal chain linking source actions, state updates, and final answers.

Credit assignment is a core challenge in reinforcement learning and sequential decision-making: when a trajectory containing dozens of action steps ultimately receives a single scalar reward, how do we determine which steps truly contributed to that outcome and assign them appropriate learning signals? In long-horizon search scenarios, this problem is especially acute—rewards are typically given only at the end of the trajectory, while the dozens of intermediate retrieval, click, and page-turn actions lack immediate feedback, resulting in extremely sparse gradient signals. Traditional approaches either optimize the entire trajectory as a whole or distribute advantage values evenly across rounds, but this gives truly critical retrieval actions the same weight as irrelevant redundant operations. What ClueFlow emphasizes as "attribution" is essentially reconstructing the credit assignment path at the action granularity, enabling each state change to be traced back to a specific source action—thereby decomposing sparse terminal rewards into finer-grained learning objectives.

How the Attribution Chain Works: A Closed Loop from Execution to Verification

When executing searches, ClueFlow records two types of information: typed state changes (Evidence updates, Candidate updates) and the browser actions that may support these changes. After execution, the system uses "gold-standard conditional semantic verification" and "source tracing" to determine which state changes are genuinely useful.

This attribution mechanism serves both training stages simultaneously. In the supervised fine-tuning (SFT) stage, attribution results determine which decisions should be supervised—learning only from state changes consistent with the gold standard and their original interaction contexts, rather than treating all rounds equally. In the Turn-PPO stage, the same attribution chain is used to augment outcome-based turn advantages, precisely distributing credit along the Source-State-Final chain.

One easily overlooked but valuable detail in the paper is that even if the final answer of an entire trajectory is wrong, as long as some state changes within it are consistent with the gold standard, transition-level verification can still recover useful supervision signals from them. This effectively leverages locally correct behaviors within "failed trajectories."

Turn-PPO is a variant of PPO (Proximal Policy Optimization) in turn-based interaction scenarios: it treats a complete interaction turn of the agent (e.g., one search plus one state update) rather than individual tokens as the basic unit of policy optimization, with turn advantage values inferred from the final outcome after that turn. Standard Turn-PPO uses only outcome rewards to estimate each turn's advantage, with all turns sharing the same signal based on the final answer. ClueFlow's approach superimposes transition-level signals provided by the Source-State-Final attribution chain on top of this outcome advantage value, effectively adding a correction term aligned with the gold standard to each turn's advantage estimate. This way, even if two trajectories have the same final answer, the attribution chain can distinguish which turns' evidence acquisition genuinely advanced the research state, concentrating policy updates on high-value turns and reducing reinforcement of ineffective exploration.

Empirical Performance: Fewer Tokens, Higher Accuracy

ClueFlow was evaluated on two Qwen backbone models and four search benchmarks, covering both live-web and fixed-corpus settings. According to the paper, the SFT stage brings consistent improvements, and the PPO stage further improves upon them. On Qwen3.5-35B-A3B, ClueFlow achieves 60.0% accuracy on BrowseComp and 72.0% on BrowseComp-Plus.

More noteworthy are the comparative data from controlled experiments. On BrowseComp-Plus, attribution-guided SFT matches the performance of full-round exact-context SFT using only about 30% of the training tokens, while attribution-guided PPO outperforms outcome-only PPO by 4.1 percentage points. These two numbers show that the attribution mechanism brings not just performance gains, but also significant training efficiency advantages.

BrowseComp and BrowseComp-Plus are representative benchmarks for evaluating long-horizon web search agents. BrowseComp, proposed by OpenAI, features questions designed as obscure factual questions requiring multi-hop retrieval and cross-verification to answer—the answers are unique but the retrieval paths are open-ended, directly testing the agent's sustained exploration and information integration capabilities in real web environments. BrowseComp-Plus is a controlled version built on top of it, using fixed corpora instead of live web pages to eliminate evaluation noise from network fluctuations and page changes, facilitating reproducible comparative experiments. Together, they cover exactly the two settings mentioned in the paper—"live web" and "fixed corpus": the former tests performance under real deployment conditions, while the latter is used for rigorous ablation and efficiency comparisons, which is the premise for ClueFlow to provide precise data on token efficiency and percentage-point gains.

Why State Transition Attribution Deserves Attention

ClueFlow's core contribution is pushing "credit assignment" down from the turn granularity to the state-change granularity. For long-horizon search agents, this means training signals are sparser but more precise—the model learns "which types of evidence acquisition actions led to which types of state evolution" rather than broadly imitating entire trajectories.

From an engineering perspective, building the attribution chain relies on post-execution semantic verification and source tracing, which introduces some additional computational overhead. However, the paper's token efficiency data shows that this overhead is worthwhile during training. For teams deploying search agents, ClueFlow provides a reproducible path: first define clear state types, then let the attribution mechanism automatically filter high-value supervision signals.

Paper address: Search for "ClueFlow: Learning Long-Horizon Search through Attributed Research-State Transitions" on arXiv.

One-line Summary

ClueFlow uses a Source-State-Final attribution chain to push supervision signals down to state changes, enabling more token-efficient long-horizon search training.

Paragraph Summary

ClueFlow addresses the unclear attribution of supervision signals in long-horizon search agents by proposing a Source-State-Final attribution chain that links browser actions, typed research state updates, and final answers into a verifiable causal chain. After execution, gold-standard conditional semantic verification and source tracing determine which state changes are genuinely useful, and attribution results are used both to filter supervision targets in the SFT stage and to augment turn advantages in the Turn-PPO stage. Experiments show that attribution-guided SFT matches full-round exact-context SFT using only about 30% of training tokens, and attribution-guided PPO outperforms outcome-only PPO by 4.1 percentage points; on Qwen3.5-35B-A3B, BrowseComp reaches 60.0% and BrowseComp-Plus reaches 72.0%. Transition-level verification can also recover locally correct behaviors from erroneous trajectories as supervision signals.