Autonomous agents have become adept at searching and synthesising text, but video has been left out of this shift. The authors formalise Agentic Video Browsing as a task where an agent must query a video search engine, decide which returned videos to watch, and answer questions grounded in what the videos actually show. To make this setting reproducible, they release Video-BrowseComp, a benchmark with 660 human-annotated questions at three difficulty levels, paired online and offline evaluation tracks, and a fixed search stack of about 12,000 videos spanning over 2,000 hours.
Their analysis identifies the main bottleneck: agents often fail to find the answer-bearing video in the first place. Video search engines index textual metadata such as titles and tags, but many questions target visual or cross-source evidence that never appears in those surface forms. At the same time, exhaustively inspecting every returned video is too expensive for practical agents.
To address this, the proposed Video-Browser agent works on both sides of the problem. A Translation Memory helps the planner phrase queries by analogy to past question-to-query transformations that successfully surfaced target videos, while a Watcher performs sparse visual screening over candidates, retaining only videos that plausibly contain answer-bearing evidence for later dense verification. On the offline track, Video-Browser raises overall accuracy from 11.6% to 27.3% with Qwen3-VL-8B and from 39.8% to 45.1% with Gemini-3.1-Pro compared with ReAct search agents, showing that better query formulation and post-search selection can substantially improve end-to-end video browsing.