Token Compression for Streaming

Chapter 4-5에서 streaming context와 visual encoder를 다뤘다면, 이 챕터는 그 사이에 끼는 token compression layer를 다룬다. General Video LLM에서는 압축이 'offline 후처리'였다. HiCo(VideoChat-Flash)나 offline TokenMerge처럼 전체 frame을 다 본 뒤 redundancy 분석을 한 번 돌려서 token budget에 맞춘다. Hour-scale에서는 episodic memory의 일부로 '이미 본 chunk를 압축해 저장'하는 게 핵심이었다 — 시간이 흘러도 과거는 변하지 않으므로 한 번 압축하면 끝이다.

Real-time은 둘 다 깨진다. 첫째, 미래를 모른다. 지금 도착한 frame이 30초 뒤 query에 결정적일지 노이즈일지 알 수 없다. 둘째, commitment이 즉시 일어난다. Offline은 전체를 본 뒤 무엇을 버릴지 결정하지만, streaming은 frame이 들어올 때마다 'memory에 넣을지, 어떤 압축 수준으로 넣을지, 누구를 evict할지'를 그 자리에서 결정해야 한다. 셋째, 압축 자체도 latency budget을 먹는다. Offline은 압축에 1분이 걸려도 quality만 좋으면 된다. 스트리밍은 per-frame budget의 일부를 압축에 써야 하므로 compression cost가 1급 metric이 된다.

그래서 이 챕터의 멘탈 모델은 'token을 더 잘 줄이는 알고리즘'이 아니라 '시간을 따라 token budget을 어떻게 분배할 것인가'다. STAR hierarchy, online TokenMerge, cluster-center memory는 모두 이 질문에 대한 서로 다른 답이다.

1. 왜 offline 압축이 streaming에 직접 적용되지 않는가

먼저 offline 압축이 무엇을 가정하는지 정리하자. HiCo(VideoChat-Flash, arXiv:2501.00574)는 frame sequence 전체에 hierarchical clustering을 돌려서 1/50까지 token을 줄인다. TokenMerge offline은 모든 token pair의 similarity를 한 번에 계산해서 bipartite matching으로 merge한다. 두 알고리즘 모두 전체 sequence가 주어졌다는 batch assumption 위에 서 있다.

이 가정이 깨지면 세 가지 문제가 생긴다. (1) Future 정보 부재: HiCo가 'A frame이 cluster centroid가 되는 게 좋다'고 판단하려면 전체 distribution을 봐야 한다. 스트리밍에서는 t=10초 시점에 t=60초의 frame을 모른다. 그래서 centroid 선택이 online estimation이 된다. (2) 재배치 불가: offline TokenMerge는 시퀀스를 여러 번 패스하며 merge를 refine할 수 있다. 스트리밍에서는 한 번 merge한 token을 되돌릴 수 없다 — pipeline 다음 stage로 흘러갔기 때문. 결정이 final이라는 commitment 비용이 크다. (3) Latency budget 분배: offline 압축이 5분 영상에 30초를 써도 무방하지만, 실시간 33ms budget(30fps)에서 압축이 10ms 먹으면 encoder/LLM의 budget이 사라진다.

결론: offline 압축의 'quality at any cost' 가정을 'quality under streaming constraint'로 다시 써야 한다. 그래서 streaming-friendly 압축은 (a) per-frame O(1)/O(log N) cost, (b) irreversible commit 가능, (c) future-blind decision 하에서도 합리적 — 이 세 invariant를 만족해야 한다.

2. Flash-VStream STAR memory hierarchy

Flash-VStream(Zhang et al., arXiv:2406.08085)이 이 문제에 대한 가장 깔끔한 답을 줬다. 핵심은 STAR: Spatial / Temporal / Abstract / Retrieval 4-tier memory다. 단일 buffer가 아니라 시간 스케일이 다른 4개 layer가 협력한다.

Spatial tier는 '지금 무엇이 일어나고 있는가' 질문에 fidelity를 보장한다. Temporal tier는 '몇 초 전 무슨 일이 있었는가'에 대응하고 sliding window로 운영된다. Abstract tier는 분 단위의 semantic gist를 cluster centroid로 보관한다. Retrieval tier는 전체 history를 retrieval-friendly한 embedding index로 보관하고, query가 들어오면 abstract tier로는 부족할 때만 활성화된다.

핵심 micro-design decision: 각 tier로 token이 자동으로 강등(demotion)된다. Spatial buffer가 가득 차면 oldest token이 temporal로 내려가면서 4-8개씩 묶여 평균된다. Temporal이 가득 차면 abstract로 내려가면서 K-means cluster center 하나로 줄어든다. 이건 Atkinson-Shiffrin의 sensory→working→long-term memory와 정확히 같은 패턴이지만, 시간이 흘러 자동으로 강등된다는 게 streaming의 핵심 차별점이다. Hour-scale 시스템은 chunk 단위로 한 번에 처리해서 memory bank에 적재하지만, Flash-VStream은 frame이 도착할 때마다 STAR pipeline을 한 칸씩 shift시킨다.

또 하나의 결정: tier 간 transition이 deterministic schedule이다. 'salience score가 높으면 spatial에 더 오래 둔다'가 아니다. 시간만 보고 결정한다. 왜? Salience 기반 retention은 evaluation이 필요해서 per-frame cost가 늘어난다. Streaming budget 안에서는 'simple but wrong sometimes'가 'optimal but slow'를 이긴다.

3. Online TokenMerge — incremental clustering의 invariant

TokenMerge offline(Bolya et al., ICLR 2023, arXiv:2210.09461)은 ViT의 매 layer에서 token pair를 bipartite matching으로 merge한다. 시퀀스 전체를 보고 가장 비슷한 pair부터 줄인다. Streaming에서는 이 알고리즘이 그대로는 안 굴러간다 — 미래 token이 없기 때문이다.

Online variant의 핵심 아이디어는 incremental cluster maintenance다. 도착한 token을 기존 cluster 중 가장 비슷한 곳에 흡수(absorb)시키거나, 충분히 다르면 새 cluster를 만든다. 알고리즘 sketch:

for t in stream:
  emb = encoder(frame_t)
  for token in emb:
    sim, k = nearest_cluster(token, clusters)
    if sim > merge_threshold:
      clusters[k] = ema_update(clusters[k], token, alpha=0.1)
    elif len(clusters) < CAP:
      clusters.append(token)
    else:
      evict(least_recently_used)
      clusters.append(token)

여기서 깨지는 offline invariant 세 개. (1) Optimal merge order: offline은 global similarity ranking으로 가장 비슷한 pair부터 처리한다. Online은 도착 순서대로 처리해서 suboptimal. 대신 per-token cost가 O(K) (cluster 수)로 고정. (2) Reversibility: offline은 'A와 B를 merge했는데 나중에 C가 들어왔으니 A-C가 더 어울린다'를 다시 할 수 있다. Online은 EMA update로 부드러운 보정만 가능. (3) Cluster count: offline은 target token 수를 정확히 맞춘다. Online은 CAP을 두고 eviction policy로 운영. K-means streaming 변종(BIRCH, online K-means)의 정신과 같다.

실전에서는 threshold + CAP + eviction 세 hyperparameter가 streaming 압축의 dial이 된다. Threshold가 너무 낮으면 cluster가 폭발하고, 너무 높으면 모든 token이 하나로 뭉뜬다. CAP은 LLM context budget으로 결정. Eviction은 LRU(시간 기반) vs salience(query-aware)의 선택이 있다.

4. Cluster center as memory — fidelity / ratio / latency 3축

Cluster-based summarization은 streaming 압축의 주류 패턴이 됐다. Flash-VStream의 Abstract tier, MovieChat의 short-term memory, 심지어 Gemini Live의 video token consolidation도 모두 cluster center 운영의 변종이다. 그러나 cluster 운영을 어떻게 tune하느냐에 따라 세 축이 trade-off된다.

실전 숫자 감각: VideoLLM-online은 frame당 SigLIP 256 token을 그대로 LLM에 넣지만 frame rate를 2 FPS로 제한한다. Flash-VStream은 Spatial 32 + Temporal 32 + Abstract 16 ≈ 80 token만 LLM context에 둔다 — 압축 비율 ~10x. 같은 budget으로 30 FPS를 받을 수 있다. 대신 정밀한 visual fact-checking('이 사람 셔츠에 작은 로고가 보이나')은 spatial tier가 잠깐 갖고 있다가 잃는다.

여기서 시니어 결정 포인트: '무엇을 잃을 것인가'를 product 요구로부터 역산하는가. Sports 실시간 해설은 short-term fidelity가 결정적(Spatial tier 키워야 함). Long meeting summarization은 abstract gist가 결정적(Abstract tier 키워야 함). 같은 STAR architecture라도 tier capacity 배분이 product에 따라 다르다. 'STAR을 썼다'는 framework choice일 뿐 답이 아니다.

5. Token budget을 시간을 따라 분배하기 — eviction policy의 정치학

Streaming 압축의 가장 까다로운 부분은 eviction policy다. Cluster CAP, STAR tier 모두 고정 budget이므로 새 token이 들어올 때 누구를 내보낼지 결정해야 한다. 두 주류 정책.

LRU (Least Recently Used). 가장 오래된 token부터 demote/evict. 단순하고 빠르다 (O(1) with deque). 모든 token을 동등한 시간 가치로 본다는 가정 위에 있다. Sliding window의 자연스러운 일반화다. 단점: query가 '20분 전에 무슨 일이 있었나'면 이미 evict됐다.

Salience-aware. 각 token에 'salience score'를 매기고 낮은 점수부터 evict. Score는 (a) encoder의 attention magnitude, (b) 이전 query에 의해 attend된 정도, (c) cluster centroid로서의 representative power 등으로 계산. 단점: 평가 자체가 cost. 또 'salience를 정확히 매길 수 있다'는 가정은 future-blind 환경에서 깨진다.

중간 지점이 있다. Tiered demotion: LRU로 빠르게 강등하되, demotion 시점에 cluster center로 압축. 이게 STAR의 실제 동작이다. 'evict'를 binary로 보지 않고 'compress harder'로 다룬다. LRU의 O(1) 비용으로 운영하면서, fidelity는 compression schedule로 점진적 손실시킨다.

Production 관점에서 하나 더: eviction 결정이 reproducible해야 한다. Debugging이나 incident replay에서 'p99 latency가 튄 frame이 왜 evict됐는가'를 추적하려면 결정 함수가 deterministic이어야 한다. Salience-aware 정책이 stochastic하거나 model state에 의존하면 production에서 다루기 힘들다. 이게 industry에서 STAR 같은 'simple-but-deterministic' 압축이 'salience-aware optimal' 변종보다 많이 채택되는 이유다.