MultiHaystack: Benchmarking Multimodal Retrieval and Reasoning over 40K Images, Videos, and Documents

Multimodal large language models (MLLMs) achieve strongperformance on benchmarks that evaluate text, image, or video un-derstanding separately. However, these settings do not assess a criticalreal-world requirement, which involves retrieving relevant evidence fromlarge, heterogeneous multimodal corpora prior to reasoning. Most ex-isting benchmarks restrict retrieval to small, single-modality candidatesets, substantially simplifying the search space and overstating end-to-end reliability. To address this gap, we introduce MultiHaystack, thefirst benchmark designed to evaluate both retrieval and reasoning underlarge-scale, cross-modal conditions. MultiHaystack comprises over 46,000multimodal retrieval candidates across documents, images, and videos,along with 747 open yet verifiable questions. Each question is groundedin a unique validated evidence item within the retrieval pool, requiringevidence localization across modalities and fine-grained reasoning. In ourstudy, we find that models perform competitively with evidence, but per-formance drops sharply when retrieving evidence from the full corpus.Additionally, even the strongest retriever, E5-V, achieves only 40.8%Recall@1, while state-of-the-art MLLMs such as GPT-5 experience asignificant drop in reasoning accuracy from 80.86% when provided withthe corresponding evidence to 51.4% under top-5 retrieval. These resultsindicate that multimodal retrieval over heterogeneous pools remains aprimary bottleneck for MLLMs, positioning MultiHaystack as a valuabletestbed that highlights underlying limitations obscured by small-scaleevaluations and promotes retrieval-centric advances in multimodal sys-tems. Our code and benchmark are available at link.