FLoC: Facility Location-Based Efficient Visual Token Compression for Long Video Understanding

이 논문은 장기간 비디오 이해를 위한 대규모 멀티모달 모델의 확장성 문제를 해결하기 위해, 훈련 없이 모델과 쿼리에 구애받지 않고 시설 위치 함수와 지연 탐욕 알고리즘을 활용하여 효율적으로 시각 토큰을 압축하는 새로운 프레임워크인 FLoC 를 제안합니다.

핵심

🎥 긴 동영상을 한눈에 파악하는 'FLoC'의 마법: 지능형 요약의 비밀

이 논문은 **"긴 동영상을 볼 때, 컴퓨터가 너무 많은 정보를 처리하느라 지쳐버리는 문제"**를 해결한 새로운 방법 FLoC를 소개합니다.

상상해 보세요. 여러분이 1 시간짜리 긴 다큐멘터리를 볼 때, 컴퓨터는 매 프레임 (화면) 을 100 만 개의 작은 조각 (토큰) 으로 잘라내어 분석합니다. 하지만 이 조각들이 너무 많으면 컴퓨터는 "뇌가 터질 것" 같은 과부하를 겪게 되죠. 그래서 중요한 부분만 남기고 나머지를 버려야 하는데, 무작정 잘라내면 중요한 순간 (예: 범인의 얼굴, 숨겨진 단서) 을 놓칠 수 있습니다.

이때 등장한 FLoC 는 **"가장 핵심적이고 다양한 장면만 골라내는 지능형 비서"**와 같습니다.

---

🏨 핵심 비유: '호텔 시설 위치 선정' (Facility Location)

이 방법의 이름인 FLoC는 **'Facility Location(시설 위치 선정)'**이라는 수학적 개념에서 왔습니다. 이를 일상적인 예로 바꿔 설명해 드릴게요.

1. 상황: 도시 전체에 호텔을 몇 개만 지어야 해요! 🏙️

• 문제: 도시 전체 (긴 동영상) 에 호텔을 짓고 싶지만, 예산 (컴퓨터 처리 능력) 이 부족해서 100 개 도시 중 단 10 개 곳에만 호텔을 지을 수 있습니다.
• 나쁜 방법 (기존 기술):
  • 무작위 뽑기: 주사위를 굴려서 호텔을 짓습니다. (중요한 관광지가 빠질 수 있음)
  • 밀집 지역만 선택: 사람이 가장 많이 사는 동네 10 곳에만 호텔을 짓습니다. (인구 밀집 지역은 잘 커버되지만, 외곽의 중요한 산이나 공원은 무시당함)
• FLoC 의 방법:
  • **"전체 도시를 가장 잘 커버할 수 있는 10 곳"**을 찾습니다.
  • 예를 들어, 북쪽 끝의 산, 남쪽의 해변, 동쪽의 시장, 서쪽의 공항 등 서로 멀리 떨어져 있지만, 각각의 지역 주민들이 가장 가까운 호텔을 이용할 수 있도록 배분합니다.
  • 이렇게 하면 중복을 피하면서도 (다양성), 어디서나 호텔을 쉽게 찾을 수 있게 (대표성) 됩니다.

이처럼 FLoC 는 동영상 속 수많은 장면 조각들 중에서 "가장 중요한 핵심 장면"과 "다양한 상황"을 골고루 포함하는 조합을 수학적으로 찾아냅니다.

---

🚀 어떻게 그렇게 빠를까? '게으른 천재' 알고리즘

보통 이런 최선의 조합을 찾으려면 모든 경우의 수를 다 계산해야 해서 시간이 매우 오래 걸립니다 (컴퓨터가 미쳐버릴 정도). 하지만 FLoC 는 **'Lazy Greedy(게으른 탐욕)'**라는 clever 한 방법을 씁니다.

• 비유: 여러분이 최고의 선수를 뽑으려고 100 명을 면접 보려고 합니다.
  • 일반적인 방법: 100 명 모두를 꼼꼼히 면접 보고 점수를 매겨서 순위를 매깁니다. (시간 걸림)
  • FLoC 의 방법: 먼저 10 명 정도만 빠르게 스캔해 봅니다. "아, 이 사람은 확실히 최고군!"이라고 판단되면, 나머지 90 명을 다 볼 필요 없이 바로 뽑습니다. 만약 "아, 저 사람도 나쁘지 않은데?" 싶으면 그때 가서 다시 계산합니다.
  • 결과: 불필요한 계산을 대폭 줄여서 순식간에 최고의 조합을 찾아냅니다.

---

🌟 왜 이 기술이 중요한가요?

1. 학습 불필요 (Training-free): 새로운 AI 모델을 새로 가르칠 필요가 없습니다. 기존에 있는 어떤 비디오 AI 에도 플러그인처럼 바로 꽂아 쓸 수 있습니다.
2. 질문과 무관 (Query-agnostic): "이 비디오에서 범인은 누구야?"라고 물어야만 중요한 장면을 골라내는 게 아니라, 아무 질문도 없어도 가장 중요한 장면들을 미리 골라냅니다.
3. 실제 적용 가능: CCTV 감시, 안경형 AR 기기, 자율주행 로봇처럼 컴퓨터 성능이 제한된 곳에서도 실시간으로 긴 동영상을 분석할 수 있게 해줍니다.

📊 결론: "모든 것을 다 보지 않아도, 핵심은 놓치지 않는다"

FLoC 는 긴 동영상을 볼 때 **"눈을 감고 무작정 건너뛰는 것"**이 아니라, **"가장 중요한 순간과 다양한 상황을 놓치지 않고 골라내는 지능형 필터"**입니다.

기존 방법들이 "사람이 많은 곳만 보고" 중요한 사소한 단서 (예: 책상 위에 놓인 작은 열쇠) 를 놓쳤다면, FLoC 는 **"열쇠가 숨어 있을 법한 모든 곳"**을 골고루 훑어보며 정답을 찾아냅니다. 덕분에 컴퓨터는 훨씬 빠르게, 그리고 더 정확하게 동영상을 이해할 수 있게 되었습니다.

이 기술은 앞으로 우리가 수시간짜리 영상을 볼 때, AI 가 인간처럼 핵심을 파악하고 빠르게 답변해 주는 시대를 여는 열쇠가 될 것입니다. 🔑🎬

기술 요약

1. 문제 정의 (Problem Statement)

최근 대규모 멀티모달 모델 (LMMs) 은 긴 비디오 시퀀스를 처리하는 능력을 갖추고 있지만, 비디오 길이가 증가함에 따라 생성되는 시각 토큰 (visual tokens) 의 폭발적인 증가가 주요 병목 현상으로 작용합니다.

• 제한 사항: 대부분의 LLM 아키텍처는 4K~32K 토큰의 입력 컨텍스트만 지원하며, 고해상도나 장시간 비디오 (예: CCTV, 자율주행, 스마트 글래스) 를 처리할 때 모든 토큰을 엔드 - 투 - 엔드로 처리하는 것은 계산적으로 불가능합니다.
• 기존 방법의 한계:
  • 균일 샘플링/풀링: 중요한 시맨틱 정보를 놓치거나 불필요한 중복 정보를 제거하지 못함.
  • 클러스터링 (Clustering): 밀집된 영역의 토큰은 잘 선택하지만, 희귀하지만 중요한 정보 (예: 작은 물체, 미세한 동작) 가 포함된 희소 영역의 토큰을 놓치는 경향이 있음.
  • 쿼리 인식 (Query-Aware) 방식: 특정 쿼리에 의존하므로 범용性或 제로샷 (zero-shot) 시나리오에 적용하기 어려움.
  • 학습 기반 (Learnable) 방식: 대량의 데이터와 재학습이 필요하여 모델 독립적 (model-agnostic) 이기 어렵고 배포가 복잡함.

2. 제안 방법론: FLoC (Methodology)

저자들은 **시설 위치 함수 (Facility Location Function)**에 기반한 효율적인 시각 토큰 압축 프레임워크인 FLoC를 제안합니다. 이 방법은 훈련 없이 (training-free) 작동하며, 모델 및 쿼리에 독립적입니다.

핵심 알고리즘

1. 시설 위치 함수 (Facility Location Function):

   • 선택된 토큰 집합 $S$가 전체 토큰 집합 $V$를 얼마나 잘 대표하고 다양하게 포괄하는지를 측정하는 서모듈러 (submodular) 목적 함수를 사용합니다.
   • 수식: $f(S) = \sum_{v \in V} \max_{u \in S} \text{sim}(v, u)$
   • 이 함수는 선택된 토큰이 전체 비디오의 핵심 내용을 대표하면서도 (representativeness), 중복을 피하고 다양한 정보를 포함하도록 (diversity) 보장합니다.

2. 레이지 그리디 알고리즘 (Lazy Greedy Algorithm):

   • 시설 위치 함수 최적화는 NP-hard 문제이나, 레이지 그리디 알고리즘을 적용하여 계산 비용을 획기적으로 줄였습니다.
   • 서모듈러성 (diminishing returns) 속성을 활용하여, 이전 단계에서 계산된 마진 (marginal gain) 을 상한선으로 사용하여 불필요한 재계산을 방지합니다.
   • 우선순위 큐 (Priority Queue) 를 사용하여 각 단계에서 가장 이득이 큰 토큰을 효율적으로 선택합니다.

3. 프레임워크 구조:

   • 입력 비디오를 시각 인코더를 통해 토큰으로 변환합니다.
   • 계산 효율성을 위해 비디오를 시간적 블록 (temporal blocks) 으로 나눕니다.
   • 각 블록 내에서 FLoC 알고리즘을 적용하여 예산 (Budget, $K$) 내에서 최적의 토큰 서브셋을 선택합니다.
   • 선택된 토큰은 텍스트 프롬프트와 결합되어 비디오-LMM 에 입력됩니다.

3. 주요 기여 (Key Contributions)

• 훈련 불필요 및 범용성 (Training-free & Model-agnostic): 기존 LMM 의 구조를 변경하거나 재학습할 필요 없이 플러그 - 앤 - 플레이 (plug-and-play) 방식으로 통합 가능합니다.
• 대표성과 다양성의 균형: 기존 클러스터링 기반 방법이 놓치기 쉬운 희소하지만 중요한 정보 (Needle-in-a-haystack) 를 포착하면서도 전체적인 맥락을 유지하는 토큰을 선택합니다.
• 압도적인 효율성: 레이저 그리디 알고리즘을 통해 기존 클러스터링 방법 (K-means 등) 대비 약 10 배 이상의 압축 속도 향상을 달성했습니다.
• 쿼리 무관성 (Query-agnostic): 사용자의 질문이나 태스크에 관계없이 한 번만 토큰을 압축하여 저장하므로, 메모리 및 계산 효율성이 뛰어납니다.

4. 실험 결과 (Results)

대규모 벤치마크 (Video-MME, MLVU, LongVideoBench, EgoSchema) 에서 다양한 모델 (Qwen2.5-VL, InternVL3 등) 과 압축 비율 (1/8, 1/16, 1/32) 을 대상으로 평가했습니다.

• 성능 우위: FLoC 는 기존 최신 압축 기법 (TS-LLaVA, LongVU, DivPrune 등) 과 클러스터링 기반 방법들보다 일관적으로 높은 정확도를 기록했습니다. 특히 긴 비디오 이해 (Long Video Understanding) 와 미세한 세부 사항 파악 (Needle QA, Ego Reasoning) 작업에서 탁월한 성능을 보였습니다.
• 효율성:
  • 계산 시간: 클러스터링 기반 방법 (K-means, Spectral Clustering) 에 비해 압축 시간이 현저히 짧습니다 (예: 블록 크기 $T=32$에서 K-means 는 218 초, FLoC 는 0.527 초).
  • 메모리: 압축된 토큰만 저장하여 메모리 사용량을 크게 줄였습니다.
• 시각화 분석: t-SNE 시각화를 통해 FLoC 가 토큰 분포 전체를 고르게 커버하며, 밀집된 영역뿐만 아니라 희소한 영역의 토큰도 적절히 선택함을 입증했습니다.

5. 의의 및 중요성 (Significance)

• 실제 배포 가능성: 제한된 컴퓨팅 자원 (모바일 로봇, 스마트 글래스, 엣지 디바이스) 환경에서도 실시간으로 장시간 비디오를 이해할 수 있는 실용적인 솔루션을 제공합니다.
• 차세대 비디오-LMM 의 핵심: 비디오-LMM 이 더 긴 컨텍스트를 처리할 수 있도록 하는 핵심 기술로, 정보 손실 없이 계산 비용을 최적화하여 모델의 확장성을 높입니다.
• 미래 지향성: 고정된 블록 길이라는 제한점이 있지만, 장면 변화 감지 등을 통해 동적으로 블록 길이를 조절하는 방향으로의 발전 가능성을 제시하며, 장시간 비디오 이해 분야의 새로운 표준을 제시합니다.

결론적으로, FLoC 는 서모듈러 최적화 이론을 적용하여 긴 비디오의 시각 토큰 압축 문제를 해결한 획기적인 방법으로, 높은 정확도와 압도적인 효율성을 동시에 달성하여 실제 응용 분야에 즉시 적용 가능한 강력한 도구임을 입증했습니다.