10만 개 영상 기록을 O(1)로 읽는 Douyin 추천 시스템의 원리

한 줄 요약: ByteDance의 SequenceO1은 10만 개의 상호작용 시청 기록을 주머니 크기의 스케치로 압축하고, 상수 시간(constant time)에 이를 읽어내면서도 여전히 +2.3% 더 많은 영상을 추천합니다 — 현재 Douyin에서 전체 트래픽으로 라이브 중입니다.

Douyin의 1년은 사용자당 대략 10만 개의 상호작용을 의미합니다. 지구상의 모든 추천 시스템은 이 모든 기록을 읽고 싶어 합니다 — 당신의 지속적인 취향이 바로 그 안에 담겨 있으며, 단순히 지난 화요일의 기분만 반영하는 것이 아닙니다. 하지만 거의 아무도 그렇게 하지 못합니다. 모든 후보 영상을 점수 매기는 정교한 랭킹(fine-ranking) 단계는 결정을 내릴 시간이 밀리초 단위에 불과하며, 10만 개 항목에 대한 순진한 어텐션(attention)은 이차적인 화재와 같습니다: 비용이 기록 길이의 _제곱_에 비례하여 증가합니다. 게다가 사용자당, 후보별, 요청별로 10만 개의 피처 벡터를 저장하고 전송하는 비용은 계산조차 하지 않았습니다.

그래서 프로덕션 시스템들은 속임수를 썼습니다. 그들은 마지막 1~2K 항목으로 잘라내거나(truncated), 별도의 2단계 파이프라인을 실행했습니다 (평생 기록을 오프라인에서 클러스터링하고, 온라인에서 소수의 '관련' 항목을 검색). 이 방식은 최종 랭킹 목표에 맞춰 최적화된 적이 없습니다. 유용하긴 하지만, 손실(lossy)되고, 오래되었으며(stale), 구조적으로 어색합니다.

ByteDance의 RecSys '26 논문 — SequenceO1: End-to-End Ultra-Long (100K) Sequence Modeling in Recommendation with Low-Rank Caching (arXiv:2609.08443, 2026년 9월 8일) — 이 속임수를 끝냅니다. 이는 Douyin과 Douyin Lite에서 전체 트래픽으로 배포되었으며, 기존의 2단계 TWIN V2 평생 기록 모듈을 완전히 대체하고, 이전 접근 방식을 10만 개까지 순진하게 확장하는 것보다 학습 비용이 49.9배 저렴하고 서비스(serve) 비용이 63.9배 저렴하다는 장점을 가지면서 이를 수행합니다. 여기서는 일반적인 영어로 먼저 설명하겠습니다.

초등학생도 이해할 수 있도록 (ELI5): 당신의 시청 기록은 도서관이고, 스케치는 색인 카드입니다

추천 시스템이 다음 책을 추천하는 사서라고 상상해 보세요. 당신의 도서관에는 10만 권의 책이 있습니다 — 당신이 본, 좋아요를 누른, 건너뛴, 또는 끝까지 본 모든 영상들입니다. 매번 추천할 때마다 전체 도서관을 읽는 것은 불가능합니다: 사서가 다 읽을 때쯤이면 당신은 앱을 닫아버릴 테니까요.

세 가지 오래된 전략, 세 번의 실패:

1. Truncation(절단) — 쌓여 있는 책들 중 맨 위에 있는 것만 본다 (최근 1~2K). 빠르지만, 사서가 당신이 2023년에 천문학을 좋아했다는 사실은 잊어버린다.
2. Two-stage retrieval(2단계 검색) — 다른 직원이 당신의 도서관을 미리 레이블이 붙은 상자에 분류해 놓는다. 요청이 오면 누군가 달려가 몇 개의 상자를 가져온다. 작동은 하지만, 그 직원의 분류 작업이 실제로 당신이 머물며 시청하게 만드는 요인과 일치하는지 확인된 적은 없다.
3. Just read faster(그냥 더 빠르게 읽기) — 하드웨어를 최대치로 투입하여 모든 주의를 집중한다. 100K 규모에서는 수학적 연산량(그리고 데이터 이동)이 시스템을 마비시킨다.

SequenceO1은 더 스마트한 방식으로 작동한다: 도서관 전체를 한 번에 요약하여 인덱스 카드로 만든 다음, 그 카드를 읽는다.

• 학습된 '프로토타입(prototype)' 슬롯의 작은 집합 — 예를 들어 요리, 축구, 천문학, 코미디 스케치 같은 취향 버킷(taste buckets)이라고 부를 수 있다 — 각각은 자신에게 속하는 역사적 항목들을 흡수한다. 그 결과물은 고정된 크기의 **스케치(sketch)**가 된다: 10만 개의 모든 항목을 대신하는 몇백 개에서 몇천 개의 요약 벡터이다.
• 이 카드들은 현재 점수를 매기고 있는 비디오에 의존하지 않기 때문에, 사용자당 한 번 계산하여 캐시(cache)할 수 있다. 요청이 도착하면 랭커는 도서관 전체를 읽지 않고 캐시를 읽는다. 이것이 이름의

각 10만 개 기록 항목은 k개의 학습 가능한 프로토타입에 걸쳐 부드럽게 할당됩니다 (논문에서 k는 수백 개에서 수천 개까지 범위가 있습니다). 프로토타입별 정규화(Prototype-wise normalization)란 모든 항목이 자신의 질량(mass)을 여러 프로토타입에 분산시킨다는 의미입니다. 아무것도 완전히 버려지는 것이 아니라, 요약되는 것입니다. 그 결과물은 k × d 스케치: 길이 차원(length dimension)을 따라 암묵적인 **저랭크 표현(low-rank representation)**이 됩니다. 이는 미분 가능하므로 최종 랭킹 손실(ranking loss)에서 나온 기울기가 압축 과정을 통해 역전파됩니다. 이전의 2단계 파이프라인과 달리, 이 요약 정보는 오프라인으로 고정되는 것이 아니라 랭킹 작업에 맞춰 학습됩니다.

2. STCA가 두 가지 시간 규모(time scales)에서 작동하는 이유

타겟 조건부 추론(Target-conditioned reasoning) (Stacked Target-to-History Cross Attention, 즉 연구실의 이전 STCA 설계)은 두 번 실행됩니다:

• 최근 분기(Recent branch): 후보 항목이 **최근 10K 길이의 접미사(suffix)**에 주의를 기울입니다. 이는 최근성(recency)-민감 신호이며, 정확하고 최신 정보입니다.
• 스케치 분기(Sketch branch): 후보 항목이 고정 크기의 스케치에 주의를 기울입니다. 이는 지속적이고 초장기적인 선호도를 나타냅니다.
• 가벼운 융합(fusion) 과정이 이 두 가지 정보를 결합한 후, 다운스트림 랭커(downstream ranker) 점수를 산출합니다.

Compress-then-reason pipeline

_하나의 스케치, 두 가지 시간 규모: 10K 접미사는

• 저랭크 캐싱(Low-rank caching). 스케치(sketch)는 사용자 전용이며 타겟에 구애받지 않기 때문에 학습 과정(로컬 KV 캐시는 동일 사용자의 반복된 인스턴스에서 스케치를 재사용함)과 연속적인 서빙 요청 동안 캐시됩니다. 히트(hit)가 발생하면 시스템은 원본 100K 시퀀스를 저장, 전송 및 처리하는 과정을 완전히 건너뜁니다.
• 다중 요청 사용자 레벨 배치(Multi-request user-level batching, MRLB). 한 사용자의 여러 후보군이 각각 읽는 대신 하나의 스케치를 공유하여 읽습니다.
• FlashSA. 플래시어텐션 계열(FlashAttention lineage)의 융합 커널(fused kernel)을 사용하여 불규칙 배치(ragged batches) 하에서 거대한 중간 결과물을 메모리화하지 않고도 스케칭 단계를 계산하며, 리콜(recall)과 캐시 미스(cache-miss) 연산을 오버랩(overlap)하여 파이프라인 리프트(pipeline lift)를 구현합니다.

Cost scaling

전체 어텐션(Full attention)은 2차 함수적으로 증가하며, 심지어 선형 접미사 어텐션(linear suffix attention)도 요청당 100K 항목을 끌고 옵니다. 캐시된 스케치는 n에 대해 평탄합니다 — 이것이 핵심입니다.

수치 비교 (ByteDance 보고, Douyin/Douyin Lite)

무작정 STCA를 100K로 확장했을 때(제거 설정, ablation setting) 대비:

• 훈련 FLOPs 비용 49.9배 절감 (MRLB 작동 지점 R=40, 캐시 히트 p=0.5)
• 추론 FLOPs 비용 63.9배 절감 (서빙 재사용 R=300, p=0.6)
• 품질 향상분의 83% 유지: 직접적인 100K 확장 대비 Finish AUC가 +1.07% 상승하여 +1.29%에 도달합니다(평균 절단 길이 85K 기준). 성능 개선분 중 17%를 포기하지만, 비용은 약 50~64배 절감됩니다.

전체 프로덕션 오프라인 평가 (STCA 10K + TWIN V2 대비, TWIN V2 제거 시):

• 모든 10개 목표 지표가 개선됨. Finish AUC +0.29%, Favourite UAUC +1.47%, Dislike UAUC +3.63% — 장기적인 취향이 반영되는 영역에서 가장 큰 개선을 보였습니다.

한 달간의 온라인 A/B 테스트, Douyin 및 Douyin Lite (모두 통계적으로 유의미함):

Signal vs cost trade-off

도식: 고전적인 접근 방식들이 신호(signal) 대 비용(cost) 상에 어디에 위치하는지, 그리고 캐시된 스케치(cached sketch)가 어디에 위치하는지를 보여줍니다. 백분율은 측정값이 아닌 논문에서 보고한 순서의 예시입니다.

최신 기술 동향: 논문의 배경이 되는 패턴

SequenceO1은 단지 하나의 앱을 넘어 세 가지 이유로 중요합니다.

1. 추천 시스템에 '장기 컨텍스트(long context)'가 현실화되고 있습니다. LLM 분야 사람들은 128K 토큰 대 1M 토큰으로 논쟁하고 있습니다. 하지만 추천 시스템은 프로덕션 환경에서 사용자당 100K 이상의 이벤트를 조용히 넘어서고 있으며, 그 지연 시간(latency) 예산은 초 단위가 아닌 밀리초 단위입니다. 승리하는 방법은 더 큰 어텐션 창(attention window)을 사용하는 것이 아니라, 긴 부분을 고정 크기의 캐시 가능한 상태로 압축하는 것이었습니다. 평생의 시퀀스(lifelong sequence)가 지연 시간 예산과 만나는 모든 곳에서

3. 캐시가 아키텍처다. KV-캐시(KV-cache) 방식은 트랜스포머를 벗어났다. 여기서 캐싱된 객체는 위치별 상태(길이에 따라 증가함)가 아니라, 고정 크기의 사용자 스케치이다. 따라서 캐시의 흔적(footprint)이 n에 독립적이다. 이것이 "캐싱이 도움이 된다"와 "캐싱이 가능한 것을 바꾼다"의 차이다: 수백만 규모의 히스토리가 이제 재작성(rewrite) 문제가 아니라 스케치 크기 결정 문제인 것이다.

솔직히 주의할 점. 이 수치들은 ByteDance가 자체 랭커(ranker)에 대해 제시한 수치이다. 83% 유지율은 제거 설정(ablation setting)에서 나온 것이며, FLOPs 승수는 명시된 캐시 적중률(50–60%)을 가정한다. k 값이 수백~수천인 스케치는 희귀하고 긴 꼬리(long-tail) 관심사를 흐릿하게 만들 것이다—논문의 답변은 10K 접미사가 최신성을 커버하며 대부분의 손실은 허용 가능하지만, 사용자별 꼬리 재현율(per-user tail recall)은 분리되어 제시되지 않았다는 점이다. 그리고 Douyin의 행동 밀도(1년 ≈ 10만 건 이벤트)는 전자상거래 구매와 같은 희소 도메인보다 압축에 더 적합하다. 상수(constants)가 아닌 패턴을 복사하라.

노트북: 보조 파일 files/sequenceo1-sketch-attention.ipynb는 NumPy로 장난감(toy) 스케치 어텐션(Sketch Attention)을 구축한다—10만 건의 히스토리, k=256 프로토타입, 그리고 캐시가 승리하는 이유를 보여주는 요청별 행 계산(390배 적은 스케치 행; 300개 후보 요청당 10배 적게 접촉되는 행). 모든 셀이 GPU 없이 몇 초 만에 실행된다.

주요 시사점

• 긴 부분을 압축합니다. 고정 크기의 학습된 스케치(sketch)를 사용하여 10만 건의 상호작용 기록을 유지하면서도, 전체 기록 순위 예측 성능의 83%를 약 50분의 1~64분의 1 FLOPs로 달성합니다.
• 시간 스케일을 분리합니다. 스케치에서 장기적인 취향(taste)을 추출하고, 새로 추가된 1만 건의 접미사(suffix)에서 단기적인 의도(intent)를 파악합니다. 하나의 어텐션 예산으로 두 가지 작업을 수행합니다.
• 사용자 전용 상태를 캐시합니다. 목표와 무관한 표현(Target-agnostic representations)은 한 번 계산하여 후보군(candidates), 요청(requests), 학습 인스턴스 전반에 걸쳐 재사용됩니다. 이는 기록 길이와 관계없이 히트당 O(1)의 비용을 가집니다.
• 실제 손실 함수로 압축기를 훈련합니다. 오프라인 방식의 2단계 TWIN V2를 엔드투엔드 스케치 방식으로 대체함으로써, 모든 10가지 프로덕션 목표 지표가 개선되었으며, 온라인 환경에서 Finish는 +2.33%, Dislike는 -6.98% 향상되었습니다.
• 이 패턴은 일반화됩니다. 평생의 시퀀스(sequence)가 낮은 지연 시간 예산과 만나는 모든 곳 — 피드, 광고, 에이전트 메모리 등 — 에서 해답은 '스케치하고, 캐시하고, 스케치 위에서 추론하는 것'으로 정립되고 있습니다.

_출처: Guan et al.,