Agentic Keyframe Search for Video Question Answering (arXiv 2025)
Abstract
VideoQA(Video Question Answering)은 자연어 상호작용을 통해 video로부터 핵심 정보를 추출하고 이해할 수 있도록 하며, 이는 지능을 달성하기 위한 중요한 단계이다. 그러나 video의 철저한 이해에 대한 요구와 높은 computational cost는 VideoQA의 적용을 제한하고 있다.이를 해결하기 위해서 해당 논문에서는 VideoQA task에서 핵심 frame을 식별하기 위한 간단하고 강력한 알고리즘인 Agentic Keyframe Search (AKeyS)를 제안한다. AKeyS는 현대의 언어 에이전트를 활용하여 고전적틴 탐색 알고리즘을 지시함으로써 중복되고 관련 없는 content로부터 핵심 정보를 효과적으로 구별할 수 있다.
먼저 video를 분할하고 이를 tree 구조로 구성한다. 이후 AKeyS는 language agent를 사용하여 node를 동적으로 확장하는 동안 heuristic과 movement cost를 추청한다. 마지막으로 agent는 종료 조건에 기반하여 충분한 핵심 frame이 수집되었는지를 판단하고 answer를 제공한다.
EgoSchema & NExT-QA datasets에 대한 실험 결과, AKeyS는 가장 높은 핵심 frame 탐색 효율로 기존의 모든 method를 능가함을 보여준다. 이는 최소한의 computational overhead로 핵심 정보를 정확히 식별하고 효과적인 시각적 추론을 수행할 수 있음을 의미한다.
EgoSchema subset에서 AKeyS는 VideoTree와 비교하여 전체 frame의 43.5%만을 처리하면서도 1.8% 더 높은 정확도를 달성함을 보여준다.
Introduction
MLLMs(Multimodal Large Language Models)의 급속한 발전은 일상생활에서의 image understanding task를 크게 단순화하였다. 사용자는 image를 GPT-4V나 Gemini에 쉽게 업로드하고, 이에 대해 질문을 던진 뒤, 자연어 상호작용을 통해 응답 받을 수 있다. 그러나 video understanding는 더 큰 도전이며, Video-LLMs(Video Large Language Models)는 종종 video의 세부 정보를 포착하는 데 어려움을 겪고, video contents에 대한 전체적인 이해가 부족하다. 또한 Video-LLMs의 computational cost는 LLMs이나 image 기반 MLLMs에 비해 훨씬 높아, 상용 배포를 저해하는 요인이 된다. 일상생활에서의 video understanding task를 보다 효과적으로 해결하기 위해, 해당 논문은 keyframes의 효율적인 추출에 초점을 맞추고, 이를 image 기반 MLLMs를 활용하여 분석함으로써 video understaning을 수행한다.
핵심 frame 추출의 주요 장점 중 하나는 필수적인 정보를 유지하면서도 computational overhead를 크게 줄일 수 있다는 점이다. Figure 2를 보면, 이 중 핵심 frame sampling 기반 방법만이 정확도와 효율성을 동시에 달성하며, 이는 VideoQA task에서 핵심 frame의 중요성을 강조한다. 그러나 중요한 challenge는 특정 question에 답하는 데 필요한 필수 정보를 포함하는 핵심 frame을 어떻게 효과적으로 식별할 것인가이다. 이러한 문제는 long-form video understanding의 맥락에서 더욱 두드러진다. 방대한 양의 관련 없는 정보 속에서 question에 기반하여 핵심 content를 정확하게 시간적으로 국소화해야 하기 때문이다. 효율성과 정확성을 모두 만족하는 핵심 frame 위치 추정 문제를 해결하는 것은 video understanding task에서 매우 중요하다.
해당 논문에서는 VideoQA task로 대표되는 video understanding 및 analyze 문제를 해결하기 위해 AKeyS라는 효율적인 알고리즘을 제안한다. 전통적인 탐색 알고리즘과 현대 언어 에이전트로부터 영감을 받은 본 접근법은 reasoning, planning, summarization, reflection과 같은 언어 에이전트의 인지적 능력을 활용하여 전통적인 탐색 알고리즘을 안내하고 피드백을 제공한다. 이러한 방법론은 중복된 정보로부터 핵심 content를 효과적으로 추출한다.
video가 주어지면 AKeyS는 이를 여러 segments로 나누고, 각 segment의 대표 frame으로부터 image captioner와 같은 VLM(Vision Language Model)을 사용하여 text information을 추출한다. 이후 언어 에이전트를 활용하여 시간적 비교를 수행하고, 종료 조건에 도달할 때까지 반복적이고 점진적인 과정으로 핵심 content를 식별한다. 이 과정은 question에 답하기에 충분한 핵심 정보가 발견될 때까지 video 전반에 걸쳐 tree 구조의 탐색을 수행하는 형태로 진행된다.
Method
Background: Vasic Searching Algorithms
AKeyS algorithm은 Algorithm 1에 제시된 기본 탐색 알고리즘을 기반으로 구축된다. 이 기본적인 과정에 따라, 탐색 알고리즘들은 node를 선택하기 위한 우선순위를 결정하는 방식에 따라 구분된다.
- DFS (Depth-First Search): 더 깊은 깊이를 가진 node를 우선시하며, 되돌아가기 전에 가능한 한 멀리까지 탐색
- BFS (Breadth-First Search): 다음 단계로 이동하기 전에 현제 level의 모든 이웃 node를 탐색
- GBFS (Greedy Best First Search): heuristic 평가 함수 h(n)을 cost function으로 사용함(f(n) = h(n)). h(n)은 현재 node에서 목적지까지의 cost를 나타냄. 이는 탐색 알고리즘을 목적지 방향으로 유도할 수 있지만, 최적 경로를 보장하지는 않음
- Dijkstra's Algorithm: movement cost function g(n)을 cost function으로 사용함(f(n) = g(n)). g(n)은 시작점에서 현재 node까지 이동하는 cost를 의미함. 이는 edge의 weight를 고려하여 시작 node로부터 모든 다른 node까지의 최단 경로를 찾음
- A*: Dijkstra's Algorithm + GBFS. cost funtion f(n) = g(n) + h(n). 이는 효율성과 최적성 사이의 균형을 이루어 경로 계획에서 매우 효과적임
AKEYS Algorithm
Search Objective
AKeyS에서 keyframe은 question과 관련된 핵심 정보를 포함하는 frame으로 정의된다. 탐색 목표는 해당 frame들의 결합된 정보가 question 에 답하기에 충분한 keyframe 집합을 식별하는 것이다.
VideoQA task를 위해 MLLMs를 사용할 때에도 keyframe이 아닌 frame을 제거하고 다음 두 가지 접근법 중 하나를 선택할 수 있다. 두 접근법은 본질적으로 동일하며, keyframe에 포함된 정보와 model이 학습한 사전 지식에 의존한다.
- keyframe image base MLLM에 직접 입력하여 답변 생성
- BLIP과 같은 VLM을 적용하여 keyframe에 대한 caption을 생성한 후, 해당 caption을 이용해 답변 도출
Nodes
AKeyS algorithm에서는 video를 여러 개의 segments로 나누며, 각 video segment는 하나의 node를 나타낸다. 초기 node는 전체 video이며, 이는 먼저 M(hyperparameter)개의 segment로 균일하게 분할된다. (실제 code에서는 10개의 frame을 하나의 segment로 지정. frame 갯수는 video의 길이와 동일 (1 FPS sampling)) 다음에 확장될 node(다음으로 처리될 video segment)는 정의한 cost function f(n)에 따라 선택된다. (실제 code에서는 A* algorithm을 사용) 확장 과정이란 선택된 video segment를 더 세분화하는 것을 의미한다. 본 연구에서는 node expension을 위해 해당 segment를 binary split한다.
Answer Prediction
현재의 모든 video segment의 first frame과 end frame을 Visible Frames Fv로 정의한다. 이 frames은 서로 연결되어 있는데, 즉 하나의 video segment의 마지막 frame이 다음 segment의 첫 frame이 된다. Visible Frames에 포함된 정보를 충분히 활용할 수 있지만, 나머지 frame의 정보는 일시적으로 접근할 수 없다. Visible Frames에 대해서는 다음 두 가지 접근 중 하나를 사용할 수 있다.
- frame을 MLLM에 직접 입력
- 먼저 caption을 생성한 뒤, text modality에서 reasoning을 수행
어떤 방식이든 Visible Frames의 정보를 기반으로 답변을 예측한다. 본 연구에서는 2번 접근법을 선택한다. 예측된 답변은 중간 단계에서의 잠정적인 추측이며, 탐색이 진행되고 더 많은 Visible Frames이 드러남에 따라 변경될 수 있다. 종료 조건이 충족되면 탐색 과정은 종료되고, 예측된 답변이 최종 답변이 된다. Visible Frames의 총 개수는 QA system의 frame 효율성을 나타내는 척도로 사용된다. Visible Frames이 적을수록 MLLMs가 처리해야 할 image 수가 줄어들어 효율성이 높아진다. 최종 Visible Frames은 탐색 과정을 통해 얻어진 keyframe을 의미한다.
Cost Function
AKEYS-GBFS
- 언어 에이전트가 현재 Visible Frames의 정보를 평가하고 question에 답하기 위해 어떤 시각 정보가 누락되어 있는지를 식별하도록 함
- 이 누락된 정보는 현재 node와 목적지 사이의 거리로 간주함
- 가장 작은 h(n)을 가진 node를 확장 대상으로 선택
- 누락된 시각 정보가 어느 두 특정 inVisible Frames 사이에 위치할 가능성이 높은지를 식별 → 어떤 video segment를 확장해야 하는지를 결정
AKEYS-DIJKSTRA
- cost function g(n)은 시작점에서 현재 node까지 이동하는 비용
- 언어 에이전트가 현재 Visible Frames의 정보를 평가 → 어떤 video segment가 가장 두드러진 장면 변화를 보이는지를 식별
- 다수의 장면 전환을 포함하는 장편 video를 segment로 만들고 keyframe을 추출할 때, 이상적인 상황은 각 장면을 개별 segment로 취급하는 것 → video의 시각적 요소들이 visible frames 내에서 겹치거나 누락되지 않도록 보장하며, 필요한 Visible Frames 수를 최소화하고 효율성을 극대화 함
- cost function은 목적지의 위치를 고려하지 않으며, question은 언어 에이전트에게 보이지 않
AKEYS-A*
- cost function f(n) = h(n) + g(n)
- 현재 node에서 목적지까지의 거리와 시작점에서 현재 node까지의 거리를 모두 고려함
- 어떤 video segment가 누락된 정보르 포함할 가능성이 높은지 + 어떤 video segment가 가장 두드러진 장면 변화를 보이는지 → 두 조건 모두 만족하는 video segment 확장 대상 우선시됨
AKEYS-BFS
- cost function을 평가하기 위해 언어 에이전트에 의존하지 않는 단순한 알고리즘
- BFS를 수행하여(가지치기가 없는 경우) 존재하는 모든 video segmens를 지속적으로 분할
- 언어 에이전트에 접근할 수 없거나, LLM으로 인해 발생하는 overhead가 덜 중요한 상황에서 정보 누락이 없도록 보장하는 데 더 큰 비중을 두는 경우에 적합
Termination Condition
전통적인 탐색 알고리즘은 일반적으로 탐색 목표에 도달했는지 여부와 같은 결정론적인 종료 조건을 가진다. 하지만 VideoQA를 위한 keyframe search algorithm에서는 종료 조건이 훨씬 더 모호하고 정의하기 어렵다. 충분한 정보가 수집되었는지, 혹은 핵심 정보가 누락되었거나 과도한 추론(over-inference)이 발생했는지를 판단하는 것은 어렵다. 언어 에이전트의 relection, summarization, self-evaluation 능력에서 영감을 받아, 기본 LLM을 사용하여 예측된 답변에 대한 신뢰도를 평가하고, 이에 따라 탐색을 종료할지 여부를 결정한다. 이러한 방식으로 AKEYS는 충분히 신뢰할 수 있는 예측이 이루어졌을 때 종료된다.
두 가지 신뢰도 평가 방법을 투표 machasim을 통해 결합한다.
Self-Evaluation and Self-Reflection
- LLM은 자신의 응답을 스스로 평가하고 잠재적인 결함을 반성하도록 지시될 수 있음
- 답변을 생성한 후 question, Visible Frame의 정보, LLM의 이전 추론 체인과 예측된 답변을 모델에 다시 입력함
- 이후 LLM은 자신의 이전 답변의 정확성과 신뢰성을 평과하고 신뢰도 첨수(c1)을 출력함
Temporal Summarization
- sampling된 frame의 caption은 이산적임. 이를 시간적 차원에서 통합하기 위해 LLM에게 해당 captions를 요약하여 video에 대한 일관된 개요를 형성하도록 지시
- 이 요약을 기반으로 LLM이 답변을 예측하고 신뢰도 점수(c2) 출력
이 두 가지 방법을 앙상블하기 위해 투표 메커니즘을 사용한다. 두 방법이 독립적으로 모두 충분한 신뢰도를 가진다고 판단할 때(c1과 c2 모두가 threshold 이상) 탐색 과정이 종료된다.
Experiments
이 연구는 VideoQA task의 reasoning, inference 모두 LLM을 사용했다. 여기서 사용한 reasoning 방법이 좋다고 생각이 되긴 하지만, 실제 code를 확인해봤을 때 default iteration의 기준이 무엇인지 조금 모호한 것 같다는 생각을 했다. 각 step에서 threshold를 넘지 않는 답변이 나온다면 최대 5번 iteration을 하게 되고, 이후에도 답이 나오지 않는다면 또 다른 step을 반복하는데, 이 과정이 너무 과하다고 생각했다. 단계가 1_s_r → 2_s_r → 3_s_r → 4_s_r → 5_s_r → final_direct_qa → post_s_r 7개로 구성되어 있고, 어떤 단계에서 종료될 지는 모른다. 이 부분을 조금 더 정리해서 체계적으로 step을 나눈다면 더 좋지 않을까라는 생각을 했다.