CoEvoWhen: Policy-Tool Coevolution for Ultra-Long Video Temporal Grounding

Ultra-long video temporal grounding requires balancing long-range evidence search with fine-grained event understanding under a limited visual budget, yet existing agentic methods still rely largely on predefined policies and tool capabilities. The proposed framework jointly evolves high-level policies and executable media tools from the agentic reasoning trajectories of a VLM, forming a reusable skill without updating model parameters.

How it works

The core of CoEvoWhen is a policy–tool coevolution framework that iteratively improves an external skill, which consists of high-level policies and executable media tools. This process starts with a minimal base skill providing only the basic grounding protocol, initial observation instructions, and primitive image and video observation operations. The frozen Vision-Language Model (VLM) executes tasks using this evolving skill autonomously at inference time without needing a separate, stronger planning model.

Skill Representation and Coevolution Mechanism

At each evolution round, the external skill is represented as a set of high-level policies, denoted as Π(k), and executable media tools, denoted as T(k). The policy guides task planning and observation orchestration—specifying what visual evidence is needed—while the tools provide the executable media processing capabilities. The skill update mechanism involves distilling transferable experience from execution trajectories to refine these components:

1. For policy evolution, ∆Π(k) refines the strategies for task planning and observation orchestration with reusable experience distilled from the feedback.

2. For tool evolution, ∆T(k) adapts and expands the media processing capabilities available to the model by upgrading existing executable tools or creating new ones.

The formal update is expressed as: Π(k+1) = Π(k) ⊕ ∆Π(k), T(k+1) = T(k) ⊕ ∆T(k).

Coordinated Observation Strategy

A key insight of the framework is that tool-use policies and tool design are interdependent. High-level policies determine what evidence is needed, when to acquire it, and how to organize the search, while media tools dictate the form and granularity of the evidence the tools can present. The system coordinates image-based search with video-based verification:

: "comparing temporally distant candidates calls for image-based observations that compactly cover long temporal ranges while preserving their temporal correspondence, whereas judging action order, state changes, and event continuity may require local video-based observations."

The resulting skill supports image-based search, candidate refinement, and selective video verification, allowing the VLM to acquire evidence autonomously.

Evaluation and Results

Systematic evaluations across five benchmarks (VUE-LVTR held-out set, ExtremeWhenBench, CoMET-Bench) and three VLMs demonstrate that coevolution improves grounding accuracy while reducing visual token cost. Key findings include:

1. Performance gains: On ExtremeWhenBench, evolving the base skill for Qwen3.5-27B raises mIoU by 74.9%, and on CoMET-Bench, it yields gains of 0.0280 in mIoU and 10.93 points in Rejection-F1.

2. Efficiency improvements: Average visual tokens per query drop from 202.6k to 141.9k on the VUE-LVTR held-out set, with reductions of 30% fewer tokens overall, demonstrating a reallocation of the visual budget between modalities.

3. Generalizability: The evolved skill shows cross-VLM generalizability, improving ExtremeWhenBench mIoU by 99.2% and transferring effectively to general long-video QA without additional task-specific evolution.

Ablations and Insights

Ablation studies confirm the necessity of joint adaptation:

: freezing the policies during evolution leads to a larger accuracy loss than freezing the tools, suggesting that stronger observation capabilities can yield substantial gains in ultra-long video temporal grounding when strategically organized into an efficient and accurate evidence search process.

Image–video coordination ablations show that the evolved skill outperforms single-modality skills, underscoring that image-based and videobased observations are suited to different contexts and that strategically coordinating the two makes better use of their complementary strengths. The final evolved skill successfully combines image-based global search with selective video verification.

Inference at Test Time

At inference, the fixed evolved skill is applied to the VLM. The process is formalized as: at = (jt, ηt) ∼ Mθ (· qi, Ht−1; Π∗, T∗), Ht = Ht−1 ∥ at, f ∗ jt(Vi; ηt). The VLM autonomously invokes tools based on the query and accumulated evidence guided by the evolved policy.

Based on the provided research paper COEVOWHEN: POLICY-TOOL COEVOLUTION FOR ULTRA-LONG VIDEO TEMPORAL GROUNDING, here are specific, actionable improvements for AI systems, categorized by capability:

) 1. Enhanced Temporal Grounding Accuracy in Ultra-Long Videos (Extreme Precision)

The improved system can achieve significantly higher temporal localization accuracy than current methods by dynamically adapting its observation strategy based on the evidence needs of the query.

Specific Improvements:

• Implement a policy that explicitly coordinates image-based global search with fine-grained, selective video verification. This allows the system to perform Global Image-Based Search for distant candidates while reserving high visual cost video inspection only for local boundary refinement or action verification on promising regions (as demonstrated in Figure 6).

• Evolve media tools to support richer observation modalities. Tools should be upgraded to generate compact temporal summaries, motion-aware frames, and scene boundary indicators, enabling the system to distinguish between visually similar but temporally distinct events.

Improved AI System Capability:

The improved system can accurately localize target events in videos spanning hours (e.g., 76 minutes) by intelligently balancing long-range evidence search with fine-grained local detail inspection, leading to near-perfect temporal overlap (IoU of 1.00 demonstrated).

) 2. Significant Reduction in Visual Token Cost and Inference Latency

The system can achieve high accuracy at a substantially lower computational cost per query compared to current agentic methods that rely on monolithic, exhaustive visual scanning.

Specific Improvements:

• Employ efficient tool policies that minimize redundant observation calls by leveraging pre-computed or summarized evidence (e.g., contact sheets) before initiating expensive video inspections.

• Evolve tools to be more compact and targeted, ensuring that image observations are used for broad candidate pruning while video observations are strictly reserved for verifying the specific temporal boundaries of the final answer, drastically reducing total visual token consumption (up to 51.27% reduction shown in Case Study).

Improved AI System Capability:

The system can perform complex ultra-long video grounding tasks with a 30% reduction in cumulative visual token cost per query, making high-accuracy understanding feasible for real-time or resource-constrained applications.

) 3. Autonomous, Self-Optimizing Agentic Reasoning (No External Planner Needed)

The system gains the ability to operate autonomously under a fixed, frozen VLM backbone without requiring a separate, stronger planning model for multi-step reasoning.

Specific Improvements:

• Implement an evolved skill that integrates high-level policy guidance directly into the VLM's system prompt and registers evolved tools as callable functions.

• The skill updater (e.g., Codex) autonomously distills transferable task experience from execution trajectories to refine both the agent's planning strategy (policy) and its execution capabilities (tools).

Improved AI System Capability:

The agent can autonomously decide the next observation step—whether to search globally, refine a specific candidate using images, or verify dynamics using video—based on accumulated evidence and refined task experience, effectively acting as its own superior planner for long-video tasks.

) 4. Cross-Task Reusability and Generalization

The learned expertise is not task-specific but transferable across different types of long-video understanding problems (e.g., grounding vs. general QA).

Specific Improvements:

• The coevolution process is designed to distill a reusable skill rather than just a solution for one query type.

• The framework demonstrates that the evolved grounding skill can be directly applied to general long-video QA tasks (like LVBench or LSDBench) without requiring any additional task-specific evolution, proving the robustness and generality of the learned experience.

Improved AI System Capability:

The system can rapidly adapt its learned temporal grounding expertise to new, related video understanding challenges with minimal or zero retraining on new data, showcasing a highly generalizable knowledge base for long-video comprehension.

) 5. Dynamic Adaptation to Query Complexity (Multi-Event Handling)

The system can effectively handle complex queries involving multiple events or target absences within the same video context.

Specific Improvements:

• The policy is refined to handle dynamic ambiguities and uncertain continuity by explicitly targeting action order, state changes, and event transitions during video inspection.

• Tools are adapted to provide evidence that helps discriminate between similar but distinct visual patterns (e.g., distinguishing a chute transfer from a skimmer action).

Improved AI System Capability:

The system can accurately count multiple events in a single video and correctly reject queries where the target event is absent, significantly boosting performance on benchmarks like CoMET-Bench.

Ultra-long video temporal grounding requires balancing long-range evidence search with fine-grained event understanding under a limited visual budget, yet existing agentic methods still rely largely on predefined policies and tool capabilities. Motivated by this, we propose a novel policy-tool coevolution framework that jointly evolves high-level policies and executable media tools from the agentic reasoning trajectories of a VLM, forming a reusable skill without updating model parameters. During evolution, an external skill updater distills transferable task experience in long-video temporal grounding, accordingly refining the orchestration of long-range image-based and fine-grained video-based observations. Alongside these policy updates, the updater employs its coding capabilities to upgrade existing tools or create new ones, adapting the tools to long-video evidence acquisition. Equipped with the evolved skill, the VLM autonomously orchestrates tools under the guidance of the evolved policy, coordinating image and video observations for agentic inference without relying on a separate, stronger planning model. Extensive experiments spanning five benchmarks and three VLMs show that policy-tool coevolution consistently improves temporal grounding accuracy in ultra-long videos while reducing visual token cost at inference, and that the evolved skill yields substantial performance gains on general long-video QA without additional task-specific evolution, demonstrating the effectiveness and generalizability of our framework for long-video understanding.