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 graph-based retrieval approaches typically rely on a uniform similarity metric that overlooks hop-specific 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 Feedback, which casts subgraph retrieval as a sequential decision process and introduces two key innovations. (i) We introduce a history-aware 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 economically-rational 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. The project page is available at failureisfeedback.github.io.

When we ask an AI a question, it often must gather scattered evidence (e.g., a paragraph here, a table or image there) spread across many linked web pages. Existing systems follow a fixed route and grab whatever looks superficially similar, so one wrong turn leads to a dead end with no way back, and they tend to think too little on the hard steps while overspending on the easy ones. We built Failure is Feedback (FiF), an agentic system that searches more like a careful detective. Instead of following a rigid script, it keeps a running notebook of what it has tried and, crucially, what failed. When a path does not pan out, FiF treats that failure as a clue: it backtracks to the most promising earlier point and tries a smarter move, paying for expensive reasoning only when a cheap attempt has fallen short. As a result, FiF finds the right evidence more often and surfaces the best of it first, which leads to more accurate answers while keeping computation in check. It outperforms existing systems on three question-answering benchmarks and keeps working across many different underlying AI models, pointing toward more reliable and cost-aware AI search.