Query-Aware Adaptive Sampling — AKS & BOLT

Chapter 2에서 본 uniform·fps·shot-detection baseline은 긴 비디오에서 두 가지 방식으로 무너졌다 — 정보 손실이 query와 무관하게 일어나거나, 반대로 query와 무관한 redundancy를 그대로 LLM에 떠넘기거나. 이 chapter는 2025년 CVPR에서 동시에 등장한 두 plug-and-play training-free sampler, AKS(Adaptive Keyframe Sampling, Tang et al., arXiv:2502.21271)와 BOLT(Liu et al., arXiv:2503.21483)를 다룬다. 두 방법은 같은 문제 — 질문 텍스트가 있을 때 어느 frame을 LLM의 context에 통과시킬 것인가 — 를 서로 다른 수학적 어법으로 푼다. AKS는 이를 constrained discrete optimization으로, BOLT는 importance-weighted stochastic sampling으로 정식화한다. 둘 다 frozen CLIP encoder만 호출하고, downstream VLM에는 손대지 않으며, 64–768 frame budget이 아니라 8–16 frame budget 안에서도 작동한다는 점에서 production-friendly한 첫 세대 query-aware sampler다. 이 chapter의 목표는 (a) 두 방법을 정식화하고, (b) AKS recursive partition을 직접 Python으로 구현해 보며, (c) 어떤 조건에서 둘이 uniform에 진다는 사실까지 솔직하게 정리하는 것이다.

3.1 The Objective — Relevance vs. Coverage as a Constrained Selection Problem

비디오를 N개의 frame f_1, ..., f_N, 질문을 텍스트 q라고 하자. Sampler의 임무는 부분집합 S ⊆ {1, ..., N}을 고르는 것인데, 제약은 |S| = K로 LLM의 vision context 한계가 강제한다. 두 가지 효용을 동시에 키워야 한다. 첫째 relevance R(S; q) = Σ_{i ∈ S} sim(φ_v(f_i), φ_t(q)) — frozen CLIP/SigLIP encoder가 주는 query-frame cosine similarity의 총합. 둘째 coverage C(S) = spread({t_i : i ∈ S}) — 선택된 frame들의 timestamp가 비디오 전체를 얼마나 고르게 덮는가. AKS는 이를 명시적으로 max_{|S|=K} R(S; q) + λ · C(S) 형태의 joint objective로 푼다. λ → 0 극단은 top-K CLIP score 그대로 (지난 chapter의 anti-pattern: 한 장면에 score가 몰리면 8 frame 전부 같은 2초 구간에서 뽑힘), λ → ∞ 극단은 uniform sampling. 이 트레이드오프가 chapter 전체를 관통하는 축이다. BOLT는 같은 문제를 결정적(greedy)으로 풀지 않고, frame별 relevance score를 PDF로 해석한 뒤 inverse-transform sampling으로 stochastic하게 뽑는다 — 동일한 트레이드오프를 확률 분포 차원에서 표현하는 방식이다. 두 정식화의 공통점은 질문 텍스트가 sampling 단계 안으로 들어왔다는 것이고, 차이점은 결정성 대 확률성, 명시적 partition 대 묵시적 CDF reweighting이다.

3.2 AKS — Recursive Partition for Coverage-Aware Top-K

AKS(Tang et al., CVPR 2025, arXiv:2502.21271, repo: github.com/ncTimTang/AKS)의 핵심 아이디어는 단순하다. 비디오를 시간축 위에서 recursive하게 절반으로 자르고, 각 절반에 frame budget을 분배한 뒤, 그 절반 안에서만 CLIP relevance score 기준 top-1을 뽑는다. 알고리즘은 세 단계다. (1) CLIP relevance scoring: 전체 N개 frame을 frozen CLIP visual encoder로 임베딩하고, query q의 text embedding과 cosine similarity를 계산해 score vector s ∈ R^N을 얻는다. (2) Recursive partition: 함수 AKS(s[l:r], k)가 들어오면 — k=1이면 구간 [l, r)에서 score 최댓값 인덱스 하나만 반환하고, k>1이면 구간을 중간점 m에서 둘로 자른 뒤 budget을 절반씩(⌊k/2⌋, ⌈k/2⌉) 나눠 양쪽 재귀호출 결과를 union한다. (3) Adaptive top-up: 원논문은 또한 한 partition 안에서 score가 너무 균일(모두 낮거나 모두 비슷)할 때 그 partition을 더 쪼개지 않고 그 자리 uniform으로 대체하는 가벼운 fallback을 둔다 — 이는 'ambiguous query'에서 AKS가 uniform으로 우아하게 degrade되도록 만든다. 결과적으로 selected frame들은 시간축 위에서 (a) 비디오 전체를 덮으면서 (b) 각 구간 내부에서는 query 관련도가 가장 높은 frame을 고르는 Pareto-front 근사가 된다. 가장 인상적인 empirical 결과는 LLaVA-Video-7B + AKS가 LLaVA-Video-72B + uniform baseline을 LongVideoBench와 Video-MME long split에서 상회한다는 점이다 — 즉 10× 작은 모델이 더 똑똑한 sampler 하나로 더 큰 모델을 이긴다. Production 함의는 명확하다: VLM size를 키우기 전에 sampler를 query-aware로 바꿔라.

3.3 BOLT — Inverse-Transform Sampling on Query–Frame CDF

BOLT(Liu et al., CVPR 2025, arXiv:2503.21483, repo: github.com/sming256/BOLT)는 AKS와 정반대의 mental model에서 출발한다. AKS가 'partition 안 결정적 argmax'라면 BOLT는 'relevance가 만든 분포에서의 확률적 뽑기'다. 절차는 다음과 같다. (1) frozen CLIP/SigLIP으로 모든 frame의 query alignment score s_i를 구한다. (2) 이를 양수화·정규화해 frame-level PDF p_i = softmax(s_i / τ)로 만든다 — 여기서 temperature τ가 chapter 3.1의 λ 역할을 한다 (τ → 0이면 결정적 top-K, τ → ∞이면 uniform). (3) PDF를 누적합해 CDF F_i = Σ_{j ≤ i} p_j를 만들고, u ∼ Uniform(0,1) K번을 뽑은 뒤 각 u에 대해 i = min{i : F_i ≥ u}를 찾는다 — 표준 inverse-transform sampling이다. 이 한 줄짜리 트릭이 BOLT의 전부지만, 의미는 깊다. CDF가 high-relevance 구간에서 가파르게 올라가므로 sampling mass가 자연스럽게 그쪽으로 쏠리되, 모든 frame이 0이 아닌 확률을 갖기 때문에 시간축의 전역 coverage가 확률적으로 유지된다. AKS의 recursive partition이 'coverage를 hard constraint으로' 강제했다면, BOLT는 'coverage를 stochastic regularizer로' 녹였다. 보고된 숫자는 결정적이다: 8-frame budget에서 Video-MME가 53.8→56.1, MLVU가 58.9→63.4 — uniform 대비 같은 비용으로 +2.3, +4.5 포인트를 그냥 얻는다. BOLT의 또 다른 장점은 stochastic*이라는 점 자체다. 같은 query에 다른 sample을 뽑아 ensemble하면 추가 정확도를 살 수 있다 — AKS는 결정적이라 이 trick이 안 먹힌다.

3.4 Empirical Comparison and Where Each Wins

두 sampler의 보고된 wins를 한 표로 요약한다. AKS: downstream VLM을 LLaVA-Video-7B로 고정하고 sampler만 uniform→AKS로 바꿨을 때 LongVideoBench/Video-MME long split에서 LLaVA-Video-72B+uniform을 상회 — 7B 모델이 72B를 이긴다는 것은 sampling이 model scale의 일부를 대체 가능하다는 강한 진술이다. BOLT: LLaVA-OneVision/LLaVA-Video 위에서 8-frame budget만으로 Video-MME 53.8→56.1(+2.3), MLVU 58.9→63.4(+4.5). 두 paper 모두 frame budget이 늘어날수록 uniform과의 격차가 줄어든다는 점은 솔직하게 보고한다 — 64 frame을 다 쓸 수 있다면 더 똑똑한 sampler의 marginal return은 작다. 그래서 두 방법의 진짜 자리는 frame budget이 빡빡한 환경이다: 모바일 inference, edge VLM, 또는 비디오 길이가 한 시간이라 8-frame 안에 모든 evidence를 우겨넣어야 하는 long-video setting. 반대로 짧은 클립(30초 미만)이나 ambiguous query('describe this video' 류)에서는 두 방법 모두 uniform과 통계적으로 무차별해지거나 미세하게 진다. AKS는 partition fallback 덕에 ambiguous query에 좀 더 우아하게 degrade되고, BOLT는 stochastic ensemble로 variance를 흡수할 수 있다는 부차적 차이가 있다.

3.5 Why Training-Free Wins for Plug-and-Play

두 방법이 2025년에 동시에 SOTA를 깬 진짜 이유는 알고리즘적 우아함이 아니라 인터페이스적 결정이다. 둘 다 downstream VLM, vision encoder, text encoder 어느 것도 fine-tuning하지 않는다. Chapter 9에서 정식화할 Sampler.select(video, query, K) -> indices 계약 안에 깔끔하게 들어맞고, frozen LLaVA-Video, frozen Qwen2.5-VL, frozen InternVL3 어느 것 위에서도 동일하게 동작한다. Production 함의는 세 가지다. 첫째, deployment cost가 0이다 — model weight를 새로 분배하지 않고, kv-cache 호환성도 안 깨지고, vLLM-Omni 같은 disaggregated serving graph에서 sampler stage만 갈아끼우면 된다. 둘째, encoder 재사용이 자연스럽다 — Twelve Labs Embed API나 자체 SigLIP cache로 frame embedding을 미리 만들어 뒀다면, sampler는 그 cache 위에서 cosine score만 계산하면 끝이다. 비디오 1회 디코드·임베드 비용을 query 수에 amortize할 수 있다. 셋째, A/B test 비용이 싸다 — 같은 frozen VLM에 AKS와 BOLT를 동시에 붙여 traffic split만 나누면 그대로 비교 가능하다. Chapter 4의 learned sampler들(Frame-Voyager, M-LLM Frame Selection, GenS)은 더 높은 ceiling을 보여주지만, 그 대가로 별도 학습 데이터·별도 model weight·별도 serving lane을 요구한다. AKS·BOLT가 'first deploy, then learn'의 첫 번째 단계인 이유다.