Wang, Shijie, et al. "Efficient Attention in Partially Relevant Video Retrieval: A Benchmarking Study on Accuracy-Efficiency Trade-Offs." 2025 6th International Conference on Computer Engineering and Application (ICCEA). IEEE, 2025.

Efficient Attention in Partially Relevant Video Retrieval

정확도-효율성 Trade-off에 대한 벤치마킹 연구

Shijie Wang School of Computer Engineering and Science Shanghai University Shanghai, China 1091702808@qq.com Jue Gao* School of Computer Engineering and Science Shanghai University Shanghai, China *gaojue@shu.edu.cn

Huahu Xu School of Computer Engineering and Science Shanghai University Shanghai, China hhxu25@shu.edu.cn Dikai Fang School of Computer Engineering and Science Shanghai University Shanghai, China 499812210@qq.com

Abstract

**Partially Relevant Video Retrieval (PRVR)**에서 Transformer 기반 모델의 표준 attention mechanism이 가지는 quadratic complexity는 특히 긴 비디오 시퀀스를 처리할 때 여전히 중요한 병목 현상으로 작용한다. 본 논문은 PRVR을 위한 효율적인 attention mechanism에 대한 최초의 체계적인 연구를 제시하며, Charades-STA 벤치마크에서 Linear Attention, Agent Attention, FFT Attention이라는 세 가지 대표적인 접근 방식을 평가한다. 우리는 검색 정확도와 계산 오버헤드 간의 trade-off를 정량화하기 위해 새로운 **Harmonic Performance-Efficiency Score (HPES)**를 도입하여, 기존의 단일 지표 평가의 한계를 해결한다. 실험 결과, FFT Attention이 가장 높은 **HPES (1.13)**를 달성했으며, Softmax baseline보다 1.3배 빠른 속도와 더 높은 SumR을 보여주어, 전역 컨텍스트 모델링의 균형을 맞추는 데 있어 우수함을 입증했다. 우리의 연구 결과는 PRVR 모델에서 attention mechanism을 선택하기 위한 원칙적인 프레임워크를 제공한다.

키워드: Efficient Attention Mechanisms; FFT; Accuracy-Efficiency Trade-off; PRVR;

I. Introduction

**Partial Relevant Video Retrieval (PRVR)**은 대규모 untrimmed 비디오 컬렉션에서 관련 비디오를 검색하는 것을 목표로 한다. 정확한 일치(exact matches)를 식별하는 데 중점을 두는 기존 비디오 검색 task와 달리, PRVR은 모델이 비디오 간의 의미론적 관계(semantic relationships)와 부분적 유사성(partial similarities)을 포착해야 하므로, 더욱 도전적이고 복잡한 문제이다.

이러한 문제를 완화하기 위해 최근 몇 년간 linear attention, agent attention, fast Fourier transform-based attention과 같은 다양한 효율적인 attention 메커니즘이 등장했으며, 이들은 강력한 feature 표현 능력을 유지하면서도 계산 비용을 절감한다. 그럼에도 불구하고, 현재 PRVR task에서 이러한 효율적인 attention 메커니즘의 성능을 비교하는 체계적인 연구는 존재하지 않는다.

본 논문은 PRVR에 대한 다양한 효율적인 attention 메커니즘의 영향을 탐구하고 포괄적인 평가를 제공하는 것을 목표로 한다. 전반적으로 우리의 주요 기여는 다음과 같다:

Charades-STA 데이터셋에서 Partial Relevant Video Retrieval (PRVR) task를 위해 다양한 **효율적인 attention (linear attention, agent-based attention, Fourier transform-based attention)**으로 대체 실험을 수행한다.
PRVR 시나리오에서 다양한 attention 메커니즘의 종합적인 성능을 평가하기 위한 포괄적인 평가 프레임워크를 개발한다.
PRVR task에서 최적의 attention을 선택하기 위한 체계적인 가이드라인을 제공하고, 이 분야의 향후 연구 및 실제 응용을 위한 새로운 통찰력을 제시한다.

II.Related Work

Text-to-Video Retrieval [1, 2, 3, 4, 5]. 온라인 비디오 콘텐츠의 급격한 증가와 함께, 비디오 분석 분야는 Text-to-Video Retrieval에 대한 관심이 높아지고 있다. 이 task는 주어진 텍스트 쿼리에 의미론적으로 일치하는 사전 분할된 비디오 클립을 찾아내는 것을 목표로 한다. 널리 사용되는 접근 방식은 비디오와 텍스트 표현을 통합된 잠재 공간(unified latent space)으로 매핑하고, 이 공간에서 유사도 측정(similarity measure)을 사용하여 호환성을 평가하는 것이다.

Partially Relevant Video Retrieval (PRVR) [6]. PRVR 모델의 일반적인 전략은 attention mechanism을 활용하여 텍스트 쿼리와 비디오 세그먼트 간의 정렬(alignment)을 강화하는 것이다. 대부분의 기존 방법은 Softmax 기반 attention에 의존하는데, 이는 텍스트 쿼리와의 유사도를 기반으로 다른 비디오 프레임에 관련성 점수를 할당한다. 이 접근 방식을 통해 모델은 가장 유익한 영역에 집중하고 덜 관련성 있는 콘텐츠를 걸러낼 수 있다. 그러나 Softmax attention은 시퀀스 길이에 대해 본질적으로 이차 복잡도(quadratic complexity)를 가지므로, 특히 긴 형식의 비디오의 경우 계산 비용이 많이 든다. 또한, 몇몇 지배적인 프레임에만 집중하는 경향이 있어, 시퀀스 전체에 분산된 귀중한 맥락 정보(contextual information)를 간과할 수 있다. 이러한 한계점들은 계산 효율성과 검색 정확도 사이의 균형을 맞추는 더 효율적인 attention mechanism의 필요성을 강조한다.

Transformer [7]. Transformer는 2017년 [7]에 제안된 self-attention mechanism 기반의 신경망 아키텍처로, 자연어 처리 및 컴퓨터 비전과 같은 분야에서 널리 사용된다. 순환 신경망(RNN) 또는 합성곱 신경망(CNN)과 같은 기존의 순차 모델에서 벗어나, Transformer는 순환 또는 지역성(locality)과 관련된 귀납적 편향(inductive biases)을 제거하여 병렬 계산과 현대 하드웨어에서의 더 효율적인 학습을 가능하게 한다. 그 설계 원칙은 대규모 사전학습 모델(예: BERT, GPT, ViT)의 기반이 되었으며, 멀티모달 및 비디오 이해 task로 확장되었다.

III. Methodology

PRVR task는 주어진 텍스트 쿼리 $q$ 에 대해 untrimmed 비디오에서 가장 관련성 높은 비디오 순간 $K^{*}=\left\{k_{t}\right\}_{t=s}^{L_{k}}$ 을 검색하는 것을 목표로 한다. 이는 언어적 의미와 시공간적 시각 패턴 간의 정확한 cross-modal 정렬을 필요로 한다.

Figure 1. Base Model (MS-SL)의 프레임워크.

A.Base Model [6]

Multi-Scale Similarity Learning (MS-SL) 모델은 PRVR(Phrase-grounding in Videos and Referring Expressions)을 위한 선구적인 프레임워크로서, 제약 없는 비디오 순간(unconstrained video moments)을 지역화하는 데 내재된 불확실성을 해결하기 위해 multi-instance learning 패러다임을 채택한다. Fig.1에 나타난 바와 같이, 이 모델은 네 가지 핵심 단계를 통해 cross-modal 상호작용을 계층적으로 처리한다:

Feature representation
Dimensionality reduction
Attention computation
Multi-scale similarity learning

표준 Transformer 기반 접근 방식은 이러한 상호작용을 모델링하기 위해 stacked self/cross-attention layer를 사용하지만, 밀집된 쌍별 유사도 계산(Softmax $\left(Q K^{T} / \sqrt{d}\right)$ , Fig.2 참조)에 의존하여 $O\left(L_{q} L_{k}\right)$ 의 엄청난 복잡도를 야기한다. 여기서 $L_{v}$ 와 $L_{t}$ 는 각각 비디오 및 토큰 시퀀스 길이를 나타낸다. 이러한 quadratic scaling은 긴 비디오( $L_{k}>$ 500)를 처리할 때 특히 치명적이며, 실제 배포에 있어 중요한 도전 과제가 된다.

우리는 계산 오버헤드를 줄이면서 cross-modal 상호작용의 충실도를 유지하는 효율적인 attention 메커니즘에 대한 원칙적인 탐구를 제안한다. 우리의 연구는 세 가지 대표적인 패러다임에 초점을 맞춘다:

Linear Attention [8]: kernel decomposition을 사용하여 full attention을 선형 복잡도로 근사한다.
Agent Attention [9]: 학습 가능한 프록시(proxy)를 통해 상호작용 노드를 압축한다.
FFT Attention [10]: 시공간 모델링을 주파수 도메인으로 변환한다.

중요하게도, 모든 변형은 baseline PRVR 모델(Fig.1)의 표준 attention 모듈에 대한 drop-in 대체(drop-in replacement)로 구현되어, 핵심 유사도 계산 메커니즘을 제외하고는 아키텍처 일관성을 보장한다. Section B에서는 이들의 수학적 공식, 구현 세부 사항, 그리고 Section C에서 vanilla Softmax attention에 대한 비교 우위를 자세히 설명한다.

Figure 2. Softmax Attention $O\left(N^{2} d\right)$

B.Efficient Attention Mechanisms

1) Unified Implementation Framework

다양한 attention 메커니즘의 구조적 차이를 수용하면서도 공정한 비교를 보장하기 위해, 우리는 표준 및 확장된 파라미터화(parameterization)를 모두 지원하는 계층적 인터페이스 프로토콜을 설계한다.

a)Modular Interface Definition

기본 attention interface는 다음과 같이 일반화된다:

\text { AttnInterface }(Q, K, V ; \Theta) \rightarrow O \in \mathbb{R}^{N \times d}

여기서 $\Theta$ 는 선택적인 메커니즘별 파라미터를 나타낸다. 이를 통해 다음이 가능하다:

Standard Attention (Softmax/Linear/FFT): 최소한의 triplet $(Q, K, V)$ 를 사용하며 $\Theta=\varnothing$ 이다.
Agent Attention: quadruplet $(Q, A, K, V)$ 로 확장되며, 여기서 $A \in \mathbb{R}^{M \times d}$ 는 학습 가능한 proxy vector이다 ( $M \ll N$ ). 이 $A$ 는 $\Theta=\{A\}$ 에 캡슐화된다.

b)Implementation Consistency

입력/출력 불변성 (Input/Output Invariance): 모든 메커니즘은 내부 파라미터화와 관계없이 $O$ 의 차원( $N \times d$ )을 엄격하게 유지한다.
프록시 통합 (Proxy Integration): Agent Attention의 경우, 프록시 증강(proxy-augmented) 계산은 attention 모듈 내부에 국한된다:

O_{\text {agent }}=f_{\text {attend }}(Q, A) \cdot f_{\text {aggregate }}(A, K, V)

여기서 $f_{\text {attend}}$ 와 $f_{\text {aggregate}}$ 는 **프록시 매개 상호작용 함수(proxy-mediated interaction functions)**이다.

2)Formulations

a)Linear Attention [8]

Fig. 3에서 보여주듯이, linear attention의 핵심 아이디어는 커널 기법을 사용하여 기존 self attention 메커니즘의 Softmax 계산을 근사하는 것이다. 이를 통해 계산 복잡도를 $O\left(n^{2}\right)$ 에서 $O(n)$ 으로 줄인다. 이 방법은 입력 query, key, value를 저차원 공간으로 매핑하고, 커널 함수의 작용 하에 attention score를 계산하여 효율적인 contextual information aggregation을 달성한다. 해당 공식은 다음과 같이 표현된다:

\text { LinearAttention }(Q, K, V)=\phi(Q)\left(\phi(K)^{T} V\right)

Figure 3. Linear Attention $O\left(N d^{2}\right)$

b)Agent Attention[9]

Fig. 4에서 보여주듯이, $n$ 개의 학습 가능한 proxy vector $\boldsymbol{A} \in \mathbb{R}^{n \times d}$ ( $n=32$ 로 실험적으로 설정)를 도입하여, cross-modal attention을 두 단계의 압축된 연산으로 재구성한다:

\text { Agent Attention }=\sigma\left(Q A^{T}\right) \sigma\left(A K^{T}\right) V

여기서 $\sigma(\cdot)$ 는 Softmax 함수를 나타낸다. 이 방식은 $O(N n)$ 의 복잡도를 달성하며 ( $n \ll N$ ), proxy는 전역 컨텍스트 요약(global context summarization)을 위한 잠재적 앵커(latent anchors) 역할을 한다.

Figure 4. Agent Attention $O(N n d)$

c)FFT Attention[10]

Convolution Theorem을 활용하여, 우리는 spatial attention을 주파수 영역(frequency-domain)의 pointwise 곱셈으로 변환한다:

\begin{aligned} \mathcal{F}(Q), \mathcal{F}(K) & =F F T(Q), F F T(K) \\ \operatorname{Attn}_{F F T}(Q, K, V) & =\mathcal{F}^{-1}\left(\mathcal{F}(Q) \odot \mathcal{F}(K)^{*}\right) V \end{aligned}

여기서 $\odot$ 는 element-wise 곱셈을 나타내고, $*$ 는 **복소 켤레(complex conjugate)**를 의미한다. 이 방식은 **Fast Fourier Transform (FFT)**을 통해 복잡도를 $O(N \log N)$ 으로 감소시킨다.

C. Comparison with Softmax Attention

Tab.1에서 보여주듯이, 우리는 기존 Softmax attention과 **세 가지 대안적인 attention 방법(linear attention, agent attention, fast Fourier transform 기반 attention)**을 시간 복잡도(time complexity), 공간 복잡도(space complexity), 그리고 주요 한계점(key limitation) 측면에서 비교한다. 이론적인 복잡도 분석은 이러한 메커니즘들 간에 다양한 효율성-정확도 trade-off가 존재함을 시사하며, 우리는 이를 Charades-STA 벤치마킹을 통해 Chapter IV에서 경험적으로 검증한다.

TABLE I. 세 가지 유형의 Attention과 Softmax Attention 비교

Mechanis m	TC	SC	Key Limitation
Softmax (Baseline)	$O\left(N^{2}\right)$	$O\left(N^{2}\right)$	Quadratic scaling
Linear	$O(N d)$	$O(N)$	Low-rank approximation error
Agent	$O(N n)$	$O(N+n)$	Proxy representation bias
FFT	$O(N \log N)$	$O(N)$	Local detail loss

IV. Experiments

A. Datasets and Metrics

1)Datasets

Charades-STA 데이터셋은 비디오 temporal retrieval task를 위해 설계되었으며, 다양한 인간 활동을 묘사하는 6,670개의 비디오와 16,128개의 쿼리 설명을 포함한다. 각 비디오는 평균 30초 길이이며, 약 2.4개의 temporal moment와 해당 텍스트 쿼리에 연결되어 있다. 본 연구에서는 공식 가이드라인에 정의된 표준 데이터셋 분할 방법을 따른다.

2)Comprehensive Evaluation Metrics

검색 정확도와 계산 효율성 간의 trade-off를 종합적으로 평가하기 위해, 우리는 다음과 같이 정의되는 **Harmonic Performance-Efficiency Score (HPES)**를 제안한다:

\text { HPES }=\frac{\left(1+\beta^{2}\right) \cdot \text { Perf }_{\text {ratio }} \cdot \text { Eff }_{\text {ratio }}}{\beta^{2} \cdot \text { Perf }_{\text {ratio }}+\text { Eff }_{\text {ratio }}}

여기서:

**Perf $_{\text{ratio}} = \frac{\text{sumR}_{\text{variant}}}{\text{sumR}_{\text{softmax}}}$ **는 상대적인 정확도 유지율을 나타낸다.
**Eff $_{\text{ratio}} = \frac{\text{Latency}_{\text{softmax}}}{\text{Latency}_{\text{variant}}}$ **는 속도 향상 비율을 측정한다.
** $\beta=0.75$ **는 정확도-효율성 우선순위의 균형을 맞춘다 (grid search를 통해 검증됨).

B.Experimental Result

TABLE II. 어텐션 메커니즘의 성능-효율성 종합 비교

Mechanism	TT (min)	SumR	Perf_Ratio	Eff_Ratio	HPES
Softmax	39	68.4	1	1	1
Linear	28.8	60.2	0.88	1.35	0.98
Agent	32.4	69.7	1.02	1.2	1.11
FFT	30.3	69.1	1.01	1.29	1.13

Table 2에서 볼 수 있듯이, Charades-STA에 대한 우리의 종합적인 평가는 어텐션(attention) 변형들 간의 효율성과 정확도 상호작용에 대한 중요한 통찰력을 제공한다. FFT Attention은 검색 성능과 계산 효율성을 조화롭게 결합하여 가장 높은 HPES인 1.13을 달성하며 최적의 메커니즘으로 부상한다. 이는 69.1의 SumR 점수와 1.3배 더 빠른 추론 속도를 달성하며, 스펙트럼 처리(spectral processing)를 통해 전역적인 시간적 일관성(global temporal coherence)을 유지하는 능력을 보여준다. 이는 특히 긴 비디오에 효과적이다. 이러한 장점은 FFT의 주파수 도메인 모델링에서 비롯되는데, 이는 장면 전환에 해당하는 저주파 구성 요소를 우선시하고 학습 가능한 커널을 통해 고주파 노이즈를 적응적으로 필터링한다.

Figure 5. HPES의 파레토 다이어그램

Agent Attention은 국소적인 정렬(localized alignment)에서 약간 우수하지만, 프록시 최적화(proxy optimization) 중 gradient 전파 오버헤드로 인해 FFT보다 더 높은 GPU 메모리 소비를 초래한다. 압축된 상호작용 공간(32개의 프록시)이 FLOPs를 줄이지만, 빈번한 쿼리 의미(frequent query semantics)에 대한 내재된 편향은 일반화 가능성을 제한한다. Linear Attention은 가장 짧은 학습 시간(28.8분, Softmax보다 35% 빠름)을 달성했음에도 불구하고, 검색 품질을 치명적으로 저해한다(SumR: 60.2, baseline 대비 -18.2%). 이는 저랭크 근사(low-rank approximation)가 판별적인 비디오-텍스트 상관관계를 포착하지 못하기 때문이다.

제안된 HPES 메트릭(Fig.5)은 이러한 trade-off를 정량화한다: FFT는 모든 비디오 길이에서 파레토 프론티어(Pareto frontier)를 차지하는 반면, Linear는 최적이 아닌 영역에 뒤처진다. 이러한 결과는 효율적인 어텐션 설계가 스펙트럼 또는 공간 근사(spectral or spatial approximations)를 task별 세분성(task-specific granularity)에 맞춰야 함을 강조한다. FFT의 전역적 우선순위(global prioritization)는 PRVR의 장거리 종속성 모델링(long-range dependency modeling) 요구 사항에 적합한 반면, 공격적인 국소 압축(aggressive local compression, Linear) 또는 고정된 프록시(fixed proxies)는 의미론적 드리프트(semantic drift)의 위험을 초래한다.

V.Conclusions

Agent Attention이 국소적인 정밀도를 제공하고 Linear Attention이 속도를 위해 정확도를 희생하는 반면, FFT는 균형 잡힌 성능-효율성 프로파일로 두각을 나타낸다. 본 연구는 FFT Attention이 PRVR을 위한 최적의 선택임을 입증하며, 스펙트럼 효율성과 정확도의 균형을 통해 가장 높은 HPES 점수(1.13)를 달성한다. Softmax Attention보다 1.4% 더 높은 SumR과 1.3배 빠른 추론 속도를 가진 FFT는 **주파수 영역에서의 전역적 추론(frequency-domain global reasoning)**을 통해 장거리 의존성(long-range dependencies) 모델링에 탁월하다. 우리의 연구는 PRVR task에서 attention mechanism을 선택하기 위한 원칙적인 프레임워크를 제공한다.