Why 1 + 1 < 1 in Visual Token Pruning: Beyond Naive Integration via Multi-Objective Balanced Covering

이 논문은 시각 토큰 가지치기에서 프롬프트 정렬과 시각적 보존 간의 상충 관계를 정량화하고, 이를 해결하기 위해 다목적 균형 커버링 (MoB) 기법을 제안하여 다양한 멀티모달 모델에서 성능 저하 없이 효율성을 극대화하는 방법을 제시합니다.

핵심

이 논문은 **"시각적 토큰 가지치기 (Visual Token Pruning)"**라는 기술에 대해 다루고 있습니다. 어렵게 들리지만, 쉽게 비유하자면 **"멀티미디어 대본 (MLLM) 을 읽을 때, 불필요한 장면을 잘라내어 속도를 높이는 방법"**을 연구한 것입니다.

이 연구의 핵심은 **"1+1 이 항상 2 가 아니다"**라는 통찰에서 시작합니다. 기존 방법들은 '화면의 중요 정보'와 '질문 (프롬프트) 과의 관련성'이라는 두 가지 목표를 단순히 합치면 좋다고 생각했지만, 실제로는 상황에 따라 오히려 성능이 떨어지기도 했습니다.

이 논문은 이를 해결하기 위해 **MoB (Multi-Objective Balanced Covering)**라는 새로운 방법을 제안했습니다. 내용을 쉽게 풀어서 설명해 드릴게요.

---

1. 문제 상황: 왜 1+1 이 1 보다 작을 수 있을까?

멀티미디어 AI 는 이미지를 볼 때 수천 개의 작은 조각 (토큰) 으로 나눕니다. 하지만 모든 조각이 중요한 건 아닙니다.

• 목표 A (화면 보존): 이미지의 전체적인 맥락과 디테일을 잘 남기는 것.
• 목표 B (질문 맞춤): 사용자의 질문과 직접 관련된 부분만 남기는 것.

기존 연구들은 이 두 가지를 무조건 다 챙기려고 했습니다. 하지만 상황에 따라 중요도가 달라집니다.

• 예시 1 (약한 연결): "이 사진에 고양이 눈이 몇 개인가요?"라고 물었을 때, 고양이가 사진 한 구석에 작게 있다면 전체 화면을 다 보는 것보다 질문 (고양이 눈) 에 딱 맞는 부분만 집중하는 게 중요합니다.
• 예시 2 (강한 연결): "이 사진의 분위기는 어떤가요?"라고 물었을 때는 특정 부분보다 전체적인 풍경이 더 중요합니다.

기존 방법들은 이 차이를 무시하고 똑같은 방식으로 두 목표를 섞다 보니, 상황에 따라 오히려 성능이 떨어지는 '1+1<1' 현상이 발생했습니다.

2. 해결책: MoB (균형 잡힌 커버링)

저자들은 이 문제를 지리학적 비유로 해결했습니다.

• 비유: 도시 지도와 등대
  • **질문 (프롬프트)**은 "우리가 가고 싶은 목적지"입니다.
  • **이미지 (비주얼)**는 "거대한 도시 지도"입니다.
  • 가지치기는 "이 도시에서 우리가 실제로 방문할 몇 개의 핵심 장소를 고르는 것"입니다.

MoB 의 핵심 전략은 "예산 (Budget) 나누기"입니다.
우리가 가진 시간 (예산) 이 한정되어 있을 때, 목적지 (질문) 에 얼마나 집중할지, 그리고 도시 전체 (이미지) 를 얼마나 넓게 볼지 상황에 따라 비율을 조절해야 합니다.

• 질문과 이미지가 멀리 떨어진 경우 (약한 연결): 목적지 (질문) 를 찾기 위해 질문 관련 장소를 더 많이 뽑아야 합니다. (등대 70%, 지도 30%)
• 질문과 이미지가 가까이 있는 경우 (강한 연결): 이미 전체가 질문과 관련이 있으므로 전체 지도를 더 넓게 보는 게 좋습니다. (등대 30%, 지도 70%)

MoB 는 이 비율을 자동으로 계산하여, **질문에 맞는 핵심 정보 (Prompt Alignment)**와 **전체적인 맥락 (Visual Preservation)**을 가장 효율적으로 섞어줍니다.

3. MoB 가 어떻게 작동하나요? (간단한 과정)

1. 상황 진단: 먼저 질문과 이미지가 얼마나 밀접하게 연결되어 있는지 (거리) 를 측정합니다.
2. 예산 배분:
   • 연결이 약하면 → 질문 관련 토큰을 더 많이 뽑습니다.
   • 연결이 강하면 → 이미지 전체를 더 넓게 뽑습니다.
3. 선택 실행:
   • 질문 관련 토큰: 질문의 각 단어와 가장 잘 맞는 이미지 조각들을 찾아냅니다. (가장 가까운 이웃 찾기)
   • 이미지 관련 토큰: 나머지 이미지 조각 중에서 서로 너무 겹치지 않고 골고루 퍼진 것들을 선택합니다. (가장 먼 점 찾기)

4. 왜 이 방법이 특별한가요?

• 학습 불필요 (Training-free): 새로운 모델을 따로 가르칠 필요 없이, 기존 모델에 바로 적용할 수 있습니다.
• 압도적인 속도: 이미지의 토큰 수를 88.9% 줄여도 성능은 거의 떨어지지 않습니다. (예: 100 점짜리 시험을 11 점만 보고도 96 점 이상 맞음)
• 빠른 처리: LLaVA-Next 같은 최신 모델의 속도를 1.3~1.5 배나 빠르게 만들었습니다.
• 유연성: 이미지뿐만 아니라 비디오 (동영상) 분석에서도 뛰어난 성능을 보여줍니다.

5. 결론: "적게 보고 더 잘 이해하기"

이 논문은 **"무조건 많이 보는 게 좋은 게 아니다"**라고 말합니다. 상황에 따라 무엇을 얼마나 볼지 지혜롭게 선택하는 것이 AI 의 속도와 정확도를 동시에 높이는 비결입니다.

MoB 는 마치 현명한 가이드처럼, 사용자의 질문을 듣고 "이때는 이 부분만 자세히 보고, 저때는 전체를 훑어보는 게 좋겠군"이라고 판단하여 AI 가 불필요한 정보에 시간을 낭비하지 않도록 도와줍니다.

한 줄 요약:

"질문과 이미지의 관계를 분석해, '질문 관련 정보'와 '전체 이미지 정보'의 비율을 상황에 맞게 자동으로 조절함으로써, AI 를 더 빠르고 정확하게 만드는 새로운 방법입니다."

기술 요약

1. 문제 정의 (Problem)

• 배경: MLLM 은 시각 데이터의 공간적 중복성으로 인해 매우 많은 수의 시각 토큰을 처리해야 하며, 이는 계산 비용과 지연 시간의 주요 원인이 됩니다.
• 기존 방법의 한계: 기존 가지치기 방법들은 주로 두 가지 목표 중 하나에 집중하거나 이를 단순하게 결합했습니다.
  • 시각 보존 (Visual Preservation, VP): 시각적 중요도나 중복성 최소화를 기반으로 토큰을 선택.
  • 프롬프트 정렬 (Prompt Alignment, PA): 프롬프트와 가장 관련성이 높은 토큰을 선택.
• 핵심 문제: 기존 연구들은 다양한 작업 (Task) 에서 VP 와 PA 의 상대적 중요도가 달라질 수 있음을 간과했습니다. 단순히 두 목표를 통합한다고 해서 항상 성능이 향상되는 것은 아니며, 오히려 단일 목표 방법보다 성능이 떨어지는 경우도 발생했습니다. 이는 **프롬프트 - 시각 결합 (Prompt-Visual Coupling)**의 특성에 따라 최적의 가지치기 전략이 달라지기 때문입니다.

2. 방법론 (Methodology)

A. 이론적 분석: 프롬프트 - 시각 결합과 오차 한계

• 하우스도르프 거리 (Hausdorff Distance) 기반 오차 한계: 저자는 시각 토큰 가지치기의 오차를 정량화하기 위해 하우스도르프 거리를 도입했습니다. 이를 통해 가지치기 오차의 상한선을 유도하는 첫 번째 폐형식 (closed-form) 오차 한계를 제시했습니다.
• 결합 패턴의 발견: 프롬프트와 시각 토큰 간의 거리 (결합 강도) 에 따라 두 가지 패턴이 존재함을 발견했습니다.
  • 약한 결합 (Weak Coupling): 프롬프트와 시각 정보가 멀리 떨어져 있는 경우 (예: TextVQA). 이 경우 **프롬프트 정렬 (PA)**이 더 중요합니다.
  • 강한 결합 (Strong Coupling): 프롬프트와 시각 정보가 밀접하게 연결된 경우 (예: MMB). 이 경우 **시각 보존 (VP)**이 더 효율적입니다.
• 내재적 트레이드오프: 고정된 예산 (가지치기 후 남는 토큰 수) 하에서 VP 와 PA 는 서로 상충되는 관계에 있으며, 결합 강도 ($\eta$) 에 따라 각 목표의 최적 달성 수준이 결정됨을 수학적으로 증명했습니다.

B. 제안 알고리즘: MoB (Multi-Objective Balanced Covering)

이론적 통찰을 바탕으로 훈련이 필요 없는 (Training-free) 가지치기 알고리즘 MoB를 제안했습니다.

• 이중 목표 커버링 문제: 가지치기를 프롬프트 중심 (Prompt Center) 과 시각 중심 (Visual Center) 의 두 가지 불연속 집합으로 나누어 커버링 문제로 재정의했습니다.
• 그리디 반경 거래 (Greedy Radius Trading):
  • 프롬프트 중심 선택 ($S_p$): 프롬프트 토큰과 가장 잘 정렬된 시각 토큰을 선택하기 위해 k-겹 최근접 이웃 (k-fold Nearest-Neighbor) 커버링을 사용합니다. 약한 결합 환경에서 중요한 영역을 누락하지 않도록 k-겹 샘플링을 통해 후보를 확보한 후 최상위 토큰을 선택합니다.
  • 시각 중심 선택 ($S_v$): 나머지 토큰 중에서 시각적 정보를 고르게 분포시키기 위해 **가장 먼 점 샘플링 (Farthest Point Sampling, FPS)**을 적용합니다.
• 예산 할당: 프롬프트 결합 강도 ($\eta$) 를 추정하여, 약한 결합에는 프롬프트 정렬 예산 ($K_p$) 을 늘리고, 강한 결합에는 시각 보존 예산 ($K - K_p$) 을 늘리는 방식으로 동적으로 예산을 분배합니다.

3. 주요 기여 (Key Contributions)

1. 이론적 혁신: 시각 토큰 가지치기에 대한 최초의 폐형식 오차 한계를 유도하고, 프롬프트 - 시각 결합이 가지치기 성능에 미치는 영향을 정량화했습니다.
2. 트레이드오프 정량화: 고정된 예산 하에서 VP 와 PA 의 최적 달성 수준을 결정하는 수학적 모델을 제시했습니다.
3. MoB 알고리즘: 훈련 없이 적용 가능하며, 이론적으로 보장된 성능 하한과 선형 (Multilinear) 확장성을 가진 가지치기 방법을 제안했습니다.
4. 성능 입증: 다양한 벤치마크에서 기존 최첨단 방법 (SOTA) 을 능가하는 결과를 보여주었습니다.

4. 실험 결과 (Results)

• LLaVA-1.5-7B: 시각 토큰을 88.9% (576 개 $\to$ 64 개) 줄였음에도 불구하고, 원본 모델 성능의 **96.4%**를 유지했습니다. 이는 기존 2 위 방법보다 2.7% 더 높은 성능입니다.
• LLaVA-Next-7B: 1.3~1.5 배의 속도 향상을 달성하면서 성능 저하는 미미했습니다.
• Qwen2-VL 및 Video-LLaVA: 고해상도 이미지 및 비디오 이해 작업에서도 MoB 가 뛰어난 성능을 보였으며, Video-LLaVA-7B 의 경우 시각 토큰을 93.4% 줄여도 평균 성능의 **97.9%**를 유지했습니다.
• 효율성: MoB 는 어텐션 점수를 계산하지 않아 Flash Attention 과 호환되며, 기존 어텐션 기반 방법들보다 계산 오버헤드가 낮습니다.

5. 의의 및 결론 (Significance)

• 이론과 실용의 결합: 단순히 경험적으로 토큰을 줄이는 것을 넘어, 수학적 이론 (커버링 이론, 하우스도르프 거리) 에 기반하여 왜 특정 상황에서 어떤 전략이 필요한지 설명하고 이를 구현했습니다.
• 적응형 가지치기: 작업의 특성 (결합 강도) 에 따라 자동으로 최적의 가지치기 전략을 선택할 수 있는 프레임워크를 제공하여, 다양한 MLLM 과 작업에 적용 가능한 범용성을 입증했습니다.
• 실시간 적용 가능성: 낮은 계산 복잡도 ($O(N(L+K)d)$) 로 인해 에지 디바이스나 저지연 애플리케이션에서도 고품질 멀티모달 모델의 실시간 구동을 가능하게 합니다.

요약하자면, 이 논문은 **"1+1 이 1 보다 작을 수 있다 (단순 통합이 항상 좋은 것은 아니다)"**는 통찰에서 출발하여, 프롬프트와 시각 정보의 관계 (결합 강도) 를 분석하고 이를 기반으로 예산을 지능적으로 할당하는 MoB를 제안함으로써 멀티모달 모델의 효율성과 성능을 동시에 극대화했습니다.