[2025 NIPS] HoliTom : Holistic Token Merging for Fast Video Large Language Models

안녕하세요. 이번에 소개할 논문은 video LLM의 추론 효율성을 개선하기 위한 token merging 방법을 제안한 논문입니다. 기존 연구들은 LLM에 입력되기 전에는 temporal merging과 spatial merging을 통해 visual token 수를 줄이거나 LLM 입력 후 토큰을 줄이는 방법을 제안하였는데, 이 논문은 LLM 입력 전 merging과 LLM 내부 merging 함께 사용하는 통합 framework를 제안합니다.

1. Introduction

Video large language models(video LLM)은 복잡한 비디오 콘텐츠를 이해하는 데 큰 가능성을 보여주고 있습니다. 하지만 이러한 모델이 실제 활용으로 이어지기 위해서는 계산 비용이라는 중요한 문제가 해결되어야 합니다. 비디오는 여러 프레임을 포함하고, 각 프레임은 다시 많은 visual token으로 변환됩니다. 그 결과 긴 비디오에서는 입력 토큰 수가 수만 개까지 늘어날 수 있습니다. 특히 LLM의 attention 연산은 토큰 수에 대해 제곱 복잡도를 가지기 때문에, 토큰 수가 증가할수록 inference 비용도 급격히 커집니다.

기존 연구들도 이 문제를 해결하기 위해 model compression이나 token pruning을 시도해 왔습니다. 그러나 비디오 이해에 필요한 핵심 semantic information을 유지하면서 계산량을 크게 줄이는 것은 여전히 쉽지 않습니다. 단순히 많은 토큰을 제거하는 것만으로는 충분하지 않고, 중복된 정보는 줄이되 중요한 시각적 단서는 보존하는 방식이 필요합니다.

이 논문은 기존 token pruning 방법들이 video token의 중복성을 충분히 통합적으로 다루지 못했다는 점에 주목합니다. 기존 방법은 크게 두 가지로 나눌 수 있습니다. 첫째는 LLM 내부에서 토큰을 줄이는 inner-LLM pruning입니다. FastV, TopV, PDrop과 같은 방법들이 여기에 해당합니다. 이 방식은 LLM layer 안에서 중요하지 않은 토큰을 제거하거나 병합하지만, pruning이 일어나기 전 초기 layer에서는 여전히 많은 토큰을 처리해야 합니다. 따라서 전체 FLOPs를 줄이는 데 한계가 있습니다.

둘째는 LLM에 입력되기 전에 visual token을 줄이는 outer-LLM pruning입니다. VisionZip이나 PruMerge는 주로 spatial redundancy를 줄이고, DyCoke나 PruneVid는 temporal redundancy를 다룹니다. 하지만 이들 방법도 제한이 있습니다. 일부는 공간적 중복에 초점을 맞추고, 일부는 제한된 temporal window 안에서만 중복을 제거하기 때문에, 비디오 전체의 global temporal dynamics를 충분히 고려하지 못합니다.

이러한 차이는 Table 1에서도 정리됩니다. 기존 방법들은 주로 spatial redundancy, temporal redundancy, 또는 inner-LLM 단계 중 일부만을 다루는 반면, 제안 방법은 LLM에 입력되기 전의 spatio-temporal compression과 LLM 내부의 compression을 함께 수행합니다. 즉, 비디오 토큰의 중복성을 외부(outer)와 내부(ㅑ 양쪽에서 동시에 줄이는 방식이라는 점에서 기존 방법들과 구분됩니다.

이를 해결하기 위해 저자들은 video LLM을 위한 holistic token pruning framework를 제안합니다. 핵심은 LLM 외부와 내부에서 토큰 중복을 함께 줄이는 것입니다. 먼저 LLM에 입력되기 전, 비디오 전체를 기준으로 temporal redundancy를 분석하는 global redundancy-aware video segmentation을 수행합니다. 이후 spatio-temporal merging을 통해 visual token을 병합합니다. 이 outer-LLM 단계는 visual token 수를 원래의 10% 미만으로 줄여, 이후 LLM이 처리해야 하는 계산 부담을 크게 낮춥니다.

여기에 더해 저자들은 LLM 내부에서 사용할 수 있는 similarity-based token merging 방법을 제안합니다. outer-LLM pruning 이후에도 LLM 내부에는 여전히 중복된 token representation이 남아 있을 수 있기 때문입니다. 이 inner-LLM merging은 외부 pruning과 함께 작동하도록 설계되었으며, 두 단계가 서로 보완적으로 계산량을 줄이도록 합니다.

실험 결과는 위 그림의 결과에서 볼 수 있듯이, LLaVA-OneVision-7B에서 제안 방법은 원래 FLOPs의 6.9%만 사용하면서도 원래 모델 성능의 99.1%를 유지합니다. 또한 Time-To-First-Token은 2.28배 감소하고, decoding throughput은 1.32배 향상됩니다. 즉, 계산량 감소뿐 아니라 실제 inference 속도 측면에서도 분명한 이점이 있음을 확인할 수 있습니다.

정리하면 이 논문의 contribution은 다음과 같습니다.

1. Video LLM에서 temporal redundancy가 발생하는 현상을 분석하고, LLM 처리 이전에 이를 줄이기 위한 global redundancy-aware temporal merging 방법을 제안
2. outer-LLM pruning과 함께 사용할 수 있는 inner-LLM similarity-based merging 방법을 제안하여, 외부와 내부 pruning이 상호 보완적으로 작동하도록 함
3. LLaVA-OneVision과 LLaVA-Video를 대상으로 한 실험을 통해, 제안한 통합 pruning framework가 계산 비용과 inference 시간을 크게 줄이면서도 기존 모델의 성능을 거의 유지할 수 있음을 보임

2. Method

2.1 Background on Video LLMs Inference

이제 저자들은 제안 방법을 설명하기 위해 먼저 video LLM의 inference 과정부터 설명드리겠습니다.

Video LLM의 추론은 크게 세 단계로 나눌 수 있습니다. 첫째는 LLM에 입력되기 전 단계, 둘째는 prefilling 단계, 셋째는 decoding 단계입니다.

(1) Before LLM

먼저 LLM에 들어가기 전 단계에서는 입력 비디오가 여러 프레임으로 샘플링되고, 각 프레임은 vision encoder를 통해 visual embedding으로 변환됩니다. 이후 이 visual embedding은 projector를 거쳐 text embedding space로 프로젝션됩니다. 동시에 사용자의 text prompt도 tokenizer를 통해 text token으로 변환됩니다. 마지막으로 visual token과 text token이 하나로 연결되어 LLM의 입력이 됩니다.

(2) Prefilling

그다음 prefilling 단계에서는 LLM의 각 transformer layer가 입력 전체에 대해 self-attention을 수행합니다. 이 과정에서 query, key, value가 계산되고, 생성에 필요한 key-value pair는 KV cache에 저장됩니다. 문제는 이 단계에서 입력 토큰 전체를 한 번에 처리해야 한다는 점입니다. 비디오 입력이 길어져 visual token 수가 많아지면, prefilling 단계의 attention 비용이 크게 증가합니다.

(3) Decoding

마지막 decoding 단계에서는 모델이 토큰을 하나씩 autoregressive하게 생성합니다. 이때는 이전에 계산된 KV cache를 사용하기 때문에, 매번 전체 입력을 다시 계산하지 않아도 됩니다. 새로운 token에 대해서만 key와 value를 계산하고 이를 기존 cache에 추가합니다. 따라서 decoding 자체는 KV cache 덕분에 비교적 효율적으로 진행될 수 있지만, 처음에 많은 visual token을 처리해야 하는 prefilling 비용과 cache 크기가 문제가 되는 구간이라 볼 수 있습니다.

2.2 Global Redundancy-Aware Temporal Merging

이러한 분석을 바탕으로 저자들은 video LLM의 비효율성을 줄이기 위해 HoliTom이라는 통합적인 token merging 방법을 제안합니다. 전체 구조는 Figure 2에 정리되어 있습니다. HoliTom은 세 단계로 구성됩니다. 첫째는 temporal merging, 둘째는 spatial merging, 셋째는 inner-LLM merging입니다. 앞의 두 단계는 LLM에 들어가기 전 visual token을 줄이는 outer-LLM compression에 해당하고, 마지막 단계는 LLM 내부에서 남은 token redundancy를 줄이는 inner-LLM compression입니다.

먼저 temporal merging은 연속된 프레임에서 같은 공간 위치의 feature가 거의 변하지 않고 반복되는 현상을 줄이는 단계입니다. 프레임 (m)과 (m+1)의 같은 위치 (k)에 있는 feature를 각각 (h_m,k), (h_m+1,k)라고 할 때, 두 feature의 유사도가 threshold tau보다 크면 시간적으로 중복된 token으로 판단합니다.

그리고 단순히 인접한 두 프레임만 보는 것이 아니라, 비디오를 여러 temporal segment로 나누고 각 segment 안에서 얼마나 많은 token을 제거할 수 있는지 계산을 합니다. 구체적으로 temporal segment [t_s,t_e)가 주어졌을 때, segment 전체에서 계속 중복되는 feature를 찾고, 이후 프레임에 반복해서 등장하는 token들을 첫 번째 등장 위치로 병합합니다. 이때 제거 가능한 token 수는 다음과 같이 계산됩니다.

여기서 I(·)는 indicator function입니다. 곱셈 항은 해당 feature가 segment 안의 모든 인접 프레임 쌍에서 계속 중복되는지를 확인합니다. 마지막의 (t_e-t_s-1)은 시작 프레임을 제외하고 병합 가능한 후속 프레임 수를 의미합니다.

중요한 점은 segment를 단순히 고정된 window로 나누지 않는다는 것입니다. 저자들은 비디오 전체에서 제거 가능한 token 수가 최대가 되도록 아래와 같이 temporal segmentation을 찾습니다.

즉, 전체 비디오를 여러 segment로 나누되, 각 segment에서 병합 가능한 temporal redundant token의 총합이 최대가 되도록 하는 것입니다. 이 최적화는 dynamic programming으로 최적화 할 수 있는데, (dp[i])를 frame (1)부터 (i-1)까지 고려했을 때 얻을 수 있는 최대 제거 가능 token 수라고 하면,수식은 다음과 같습니다.

이때 최적의 segment 시작점은 prev[i]에 저장하고, 마지막에 이를 역추적하여 최적의 temporal segmentation을 복원합니다.

Spatial Merging

Temporal merging 이후에는 token이 크게 두 종류로 나뉩니다. 하나는 시간적으로 중복되지 않는 non-redundant token이고, 다른 하나는 시간적으로 중복된 redundant temporal token입니다. 저자들은 이 두 token을 같은 방식으로 처리하지 않습니다.

먼저 non-redundant token에 대해서는 attention-based spatial selection을 수행합니다. 핵심 아이디어는 vision encoder 내부의 attention 정보를 이용해 어떤 spatial token이 중요한지 판단하는 것입니다. Attention matrix는 다음과 같이 계산됩니다.

여기서 (Q)와 (K)는 vision tower에서 계산된 query와 key이고, (d)는 hidden dimension입니다. 이 attention matrix를 이용하면 각 frame 안에서 어떤 token이 다른 token들로부터 얼마나 attention을 받는지 알 수 있습니다. 저자들은 각 token이 받는 attention weight를 평균하여 중요도 score를 계산합니다.

이후 A_avg를 downsampling하고, 최종적으로 score가 높은 token을 대표 spatial token으로 선택하고, 나머지는 제거합니다. 이 과정이 Figure 2의 spatial merging에서 attention-based select에 해당합니다.

반면 redundant temporal token에는 attention-based selection을 그대로 적용하지 않습니다. Vision tower의 attention은 기본적으로 frame 내부에서 계산되기 때문에, 이를 여러 frame에 걸쳐 평균하는 것은 적절하지 않기 때문입니다. 그래서 저자들은 redundant temporal token에 대해 cluster-based merging을 사용합니다.

구체적으로 redundant temporal token 집합을 [v₁, v₂,…, v_N])이라고 할 때, 각 token v_i에 대해 local density ρi, 더 높은 density를 가진 token까지의 거리 δi, 그리고 density score γi = ρi × δi를 계산합니다.

여기서 ρi는 주변 token들과 얼마나 밀집되어 있는지를 나타내고, δi는 자신보다 density가 높은 token까지의 거리를 의미합니다. 따라서 γi가 높은 token은 cluster center로 선택됩니다. 이후 나머지 token들은 가장 가까운 cluster center에 할당되고, 각 cluster의 평균 feature가 대표 token으로 사용됩니다.

이렇게 얻은 compressed feature는 non-redundant token에서 선택된 feature와 다시 결합됩니다. 이때 원래 spatial order를 고려해 token을 연결하기 때문에, token 수를 줄이면서도 공간적 위치 정보를 어느 정도 유지할 수 있습니다.

Inner-LLM Merging

마지막 단계는 inner-LLM merging입니다. 기존 inner-LLM pruning 방법들은 attention score가 낮은 visual token을 그대로 제거하는 경우가 많습니다. 하지만 저자들은 단순 제거가 정보 손실을 만들 수 있다고 보고, 낮은 attention score를 가진 token을 버리는 대신 유지되는 token에 병합합니다.

구체적으로 LLM의 K-번째 layer에서 visual token을 (R%)만큼 줄이고자 할 때, 마지막 token의 attention weight를 기준으로 visual token의 중요도를 정렬합니다. attention score가 낮은 (R%)의 token은 merging candidate가 되고, 각 candidate는 유지될 token 중 가장 유사한 token에 할당됩니다.

Retained token을 (v_r), 여기에 병합될 low-attention token 집합을 V_m=v_m1, v_m2,…,v_mn이라고 하면, 업데이트된 token은 다음과 같이 계산됩니다.

즉, token 수는 줄어들지만 제거될 token의 정보는 가장 유사한 retained token에 흡수됩니다. 따라서 HoliTom은 단순 pruning보다 정보 손실을 줄이면서 LLM 내부의 visual token 수를 줄일 수 있습니다.

3. Experiment

저자들은 HoliTom의 효과를 검증하기 위해 MVBench, EgoSchema, LongVideoBench, VideoMME의 네 가지 video understanding benchmark에서 실험을 수행합니다.

Table 2는 LLaVA-OneVision-7B에서 HoliTom과 기존 방법들을 비교합니다. FastV와 PDrop 같은 inner-LLM pruning 방법은 낮은 token retention ratio에서 성능과 효율성의 균형을 맞추는 데 한계를 보입니다. 이는 pruning이 LLM 내부에서 일어나기 때문에, 초기 layer에서는 여전히 많은 visual token을 처리해야 하기 때문입니다. VisionZip처럼 spatial compression에만 의존하는 방법도 aggressive compression에서는 성능 저하가 크게 나타납니다. 반면 HoliTom은 outer-LLM compression만으로도 기존 방법보다 좋은 성능을 보이며, inner-LLM merging까지 추가하면 원래 FLOPs의 6.9%만 사용하면서 baseline 성능의 99.1%를 유지합니다.

Table 3은 다른 backbone에서의 결과를 보여줍니다. LLaVA-OneVision-72B에서는 계산 비용을 11.3%까지 줄이면서 96%의 성능을 유지합니다. LLaVA-Video-7B에서는 FLOPs를 9.5%까지 줄이면서 95.8%의 성능을 유지합니다. 이는 HoliTom이 특정 모델에만 의존하지 않고, 다양한 video LLM에서도 효과적으로 작동함을 보여줍니다.

Figure 3에서는 outer-LLM compression이 적용된 상황에서 HoliTom의 inner-LLM merging과 FastV를 비교합니다. Outer-LLM compression 이후에는 visual information이 이미 압축되어 있기 때문에, attention score가 낮은 token을 단순히 제거하면 정보 손실이 커질 수 있습니다. HoliTom은 이러한 token을 버리지 않고 유사한 retained token에 병합하기 때문에, FastV보다 안정적인 성능을 보입니다.

그리고 Figure 4는 입력 frame 수가 증가할 때의 결과를 보여줍니다. 더 많은 frame을 사용하면 중요한 장면을 포착할 가능성이 높아지지만, token 수와 계산 비용도 함께 증가합니다. HoliTom은 token compression을 통해 더 많은 frame을 처리할 수 있게 하며, 64 frames에서는 vanilla model보다 더 높은 효율성과 성능을 보입니다. 128 frames에서는 vanilla model이 context length 한계에 부딪히는 반면, HoliTom은 이를 완화할 수 있습니다.은

흥미롭게도 Table 2, Table 4, Figure 4에서는 token compression 이후 원래 모델보다 성능이 좋아지는 경우도 나타납니다. 저자들은 이를 불필요하거나 중복된 visual token이 noise처럼 작용할 수 있기 때문이라고 해석합니다. 즉, 모든 정보를 넣는 것보다 중요한 정보를 남기고 중복 정보를 줄이는 것이 더 나은 이해로 이어질 수 있다는 것입니다.

Figure 5는 실제 inference efficiency를 보여줍니다. HoliTom은 LLM prefilling time을 원래의 13.7%까지 줄입니다. Token preprocessing으로 인한 추가 시간이 존재하지만, 전체 Time-To-First-Token은 2.28배 감소하고 decoding throughput은 1.32배 향상됩니다. 이는 평가된 방법들 중 가장 높은 수준의 효율성 개선을 보여주고 있습니다.

Table 4는 각 merging module의 ablation 결과입니다. Temporal merging만 적용해도 baseline 대비 100.7%의 성능을 유지하면서 FLOPs를 75.7%까지 줄입니다. Temporal merging과 spatial pruning을 함께 사용하면 aggressive spatial pruning에서 발생하는 성능 저하가 완화됩니다. 여기에 inner-LLM merging을 추가하면 최종적으로 원래 FLOPs의 10.5%만 사용하면서 99.7%의 성능을 유지하는 모습을 보여주네요.