Failure is Feedback: History-Aware Backtracking for Agentic Traversal in Multimodal Graphs

Open-domain multimodal document retrieval aims to retrieve specific components (paragraphs, tables, or images) from large and interconnected document corpora. Existing graphbased retrieval approaches typically rely on a uniform similarity metric that overlooks hopspecific semantics, and their rigid pre-defined plans hinder dynamic error correction. These limitations suggest that a retriever should adapt its reasoning to the evolving context and recover intelligently from dead ends. To address these needs, we propose FAILURE IS FEED-BACK (FIF), which casts subgraph retrieval as a sequential decision process and introduces two key innovations. (i) We introduce a historyaware backtracking mechanism; unlike standard backtracking that simply reverts the state, our approach piggybacks on the context of failed traversals, leveraging insights from previous failures. (ii) We implement an economicallyrational agentic workflow. Unlike conventional agents with static strategies, our orchestrator employs a cost-aware traversal method to dynamically manage the trade-off between retrieval accuracy and inference costs, escalating to intensive LLM-based reasoning only when the prior failure justifies the additional computational investment. Extensive experiments show that FIF achieves state-of-the-art retrieval on the benchmarks of MULTIMODALQA, MMCOQA and