BranchMem: Branch-Structured Memory for Long-Horizon Search Agents

Long-horizon search agents accumulate evidence across retrieval rounds, form in- termediate judgments, and use earlier findings to guide subsequent actions. As the interaction history grows beyond a single context window, memory must preserve a state that remains useful for future decisions. An executed search trajectory can support several unresolved candidate interpretations, each with its own in- termediate judgments. We introduce BranchMem, a branch-structured memory framework that maintains each task-relevant candidate interpretation as a persis- tent branch. New observations can extend a branch or revise its local judgments; subsequent decisions read the candidate branches and their associated evidence to reassess unresolved interpretations. We evaluated BranchMem on all 221 Memo- ryArena Search task groups.