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

arXiv: https://arxiv.org/abs/2602.03432 · HTML: https://mlsanity.com/paper/2602.03432/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Web, search, and research agents, one of 16 directions in LLM agents and tool use.
- Builds on 20 of its 33 references that are in the map.
- First posted on arXiv 3 Feb 2026.

## Placed in

- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 20 of 20)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection](https://mlsanity.com/paper/2310.11511/) (2023)
- [Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions](https://mlsanity.com/paper/2212.10509/) (2022)
- [NV-Embed: Improved Techniques for Training LLMs as Generalist Embedding Models](https://mlsanity.com/paper/2405.17428/) (2024)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [VisRAG: Vision-based Retrieval-augmented Generation on Multi-modality Documents](https://mlsanity.com/paper/2410.10594/) (2024)
- [MultiModalQA: Complex Question Answering over Text, Tables and Images](https://mlsanity.com/paper/2104.06039/) (2021)
- [MM-Embed: Universal Multimodal Retrieval with Multimodal LLMs](https://mlsanity.com/paper/2411.02571/) (2024)
- [Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering](https://mlsanity.com/paper/1911.10470/) (2019)
- [M3DocRAG: Multi-modal Retrieval is What You Need for Multi-page Multi-document Understanding](https://mlsanity.com/paper/2411.04952/) (2024)
- [WebQA: Multihop and Multimodal QA](https://mlsanity.com/paper/2109.00590/) (2021)
- [Dense X Retrieval: What Retrieval Granularity Should We Use?](https://mlsanity.com/paper/2312.06648/) (2023)
- [Hierarchical Graph Network for Multi-hop Question Answering](https://mlsanity.com/paper/1911.03631/) (2019)
- [Generate-on-Graph: Treat LLM as both Agent and KG in Incomplete Knowledge Graph Question Answering](https://mlsanity.com/paper/2404.14741/) (2024)
- [Enhancing Multi-modal and Multi-hop Question Answering via Structured Knowledge and Unified Retrieval-Generation](https://mlsanity.com/paper/2212.08632/) (2022)
- [Mix-of-Granularity: Optimize the Chunking Granularity for Retrieval-Augmented Generation](https://mlsanity.com/paper/2406.00456/) (2024)
- [Unified Language Representation for Question Answering over Text, Tables, and Images](https://mlsanity.com/paper/2306.16762/) (2023)
- [LLM Abstention Can Be a Prompt Artifact, in Addition to Genuine Uncertainty](https://mlsanity.com/paper/2507.16199/) (2025)
- [MARA: A Multimodal Adaptive Retrieval-Augmented Framework for Document Question Answering](https://mlsanity.com/paper/2604.16313/) (2026)
- [MMAPG: A Training-Free Framework for Multimodal Multi-hop Question Answering via Adaptive Planning Graphs](https://mlsanity.com/paper/2508.16051/) (2025)

## Built on by (most cited first, 1 of 1)

- [Towards Reliable AI Data Scientists: Data Agents with Workflow Harnesses](https://mlsanity.com/paper/2609.35255/) (2026)

## Abstract (arXiv)

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 (FiF), 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. Extensive experiments show that FiF achieves state-of-the-art retrieval on the benchmarks of MultimodalQA, MMCoQA and WebQA.