다중 프로브 제로 충돌 해시(MPZCH): 대규모 추천 시스템에서 임베딩 충돌 완화 및 모델 최신성 향상
Multi-Probe Zero Collision Hash (MPZCH): Mitigating Embedding Collisions and Enhancing Model Freshness in Large-Scale Recommenders
한국어 초록
임베딩 테이블은 대규모 추천 시스템의 핵심 구성 요소로, 고차수 범주형(high-cardinality categorical) 특성을 밀집 벡터 표현으로 효율적으로 매핑할 수 있도록 지원합니다. 그러나 고유 ID의 양이 증가함에 따라 기존의 해시 기반 인덱싱 방식은 충돌 문제를 겪으며, 이는 모델 성능과 개인화 품질을 저하시킵니다. 본 논문에서는 선형 탐사(linear probing)를 기반으로 하여 임베딩 충돌을 효과적으로 완화하는 새로운 인덱싱 메커니즘인 다중 프로브 제로 충돌 해시(MPZCH, Multi-Probe Zero Collision Hash)를 제시합니다. 합리적인 테이블 크기 설정을 통해 프로덕션 수준의 효율성을 유지하면서 이러한 충돌을 완전히 제거하는 경우가 많습니다. MPZCH는 보조 텐서와 고성능 CUDA 커널을 활용하여 구성 가능한 탐사 및 능동적 축출(active eviction) 정책을 구현합니다. 노후화된 ID를 폐기하고 재할당된 슬롯을 초기화함으로써, MPZCH는 해시 기반 방식에서 전형적으로 발생하는 오래된 임베딩 상속을 방지하고 새로운 특성이 처음부터 효과적으로 학습되도록 보장합니다. 충돌 완화 오버헤드에도 불구하고, 본 시스템은 기존 방식과 견줄 만한 학습 QPS 및 추론 지연 시간을 유지합니다. 엄격한 온라인 실험을 통해 MPZCH가 사용자 임베딩에 대해 제로 충돌을 달성하고 아이템 임베딩의 최신성과 품질을 대폭 향상함을 입증합니다. 이 솔루션은 더 넓은 커뮤니티를 위해 오픈소스 TorchRec 라이브러리에 공개되었습니다.
원문 초록
Embedding tables are critical components of large-scale recommendation systems, facilitating the efficient mapping of high-cardinality categorical features into dense vector representations. However, as the volume of unique IDs expands, traditional hash-based indexing methods suffer from collisions that degrade model performance and personalization quality. We present Multi-Probe Zero Collision Hash (MPZCH), a novel indexing mechanism based on linear probing that effectively mitigates embedding collisions. With reasonable table sizing, it often eliminates these collisions entirely while maintaining production-scale efficiency. MPZCH utilizes auxiliary tensors and high-performance CUDA kernels to implement configurable probing and active eviction policies. By retiring obsolete IDs and resetting reassigned slots, MPZCH prevents the stale embedding inheritance typical of hash-based methods, ensuring new features learn effectively from scratch. Despite its collision-mitigation overhead, the system maintains training QPS and inference latency comparable to existing methods. Rigorous online experiments demonstrate that MPZCH achieves zero collisions for user embeddings and significantly improves item embedding freshness and quality. The solution has been released within the open-source TorchRec library for the broader community.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
정교한 축출 정책이 실패할 때: LLM 접두 문맥 재사용을 위한 캐시 교체 정책의 재고
When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse
반복 데이터 사전학습 스케일링: 배치 크기, 정규화 및 GPU-시간 트레이드오프
Scaling Repeated-Data Pretraining: Batch Size, Regularization, and GPU-Time Tradeoffs
본 연구에서는 연산량은 풍부하지만 고유한 학습(training) 데이터가 유한하여 동일한 데이터에 대한 반복 학습이 필요한 환경에서의 사전학습(pre-training)을 다룹니다. 먼저 무한 연산량 사전학습(Kim et al. 2026)을 재검토하여, 그 프론티어가 기존에 고정되었거나 개별적으로만 연구되었던 선택 사항들에 결정적으로 의존함을 보입니다. 특히 에포크(epoch) 수와 함께 배치(batch) 크기를 최적화하면 검증 손실(validation loss)과 배치 크기 사이에 U자형 관계가 나타나 일반적인 사전학습보다 더 작은 배치를 선호하게 됨을 밝히며, 이는 소배치 그래디언트(gradient) 노이즈가 암묵적 정규화(implicit regularization)를 제공하기 때문인 것으로 보입니다. 나아가 기존에 단일 패스 가정 하에서 최적화되었던 학습 레시피를 조정할 수 있음을 확인했습니다. 예를 들어 에포크마다 문서를 새로운 시퀀스로 재패킹하는 것, 가중치 공유(weight tying), 그리고 양의 임베딩 가중치 감쇠(positive embedding weight decay) 등이 있습니다. 이후 무한 연산량 가정을 완화합니다. 특히 일반적인 경우보다 작은 배치 크기는 지나치게 긴 순차적 학습 시간을 요구할 수 있으므로, GPU와 시간을 별개의 자원으로 다루어야 할 필요성이 발생합니다. 마감 기한이 촉박할수록 더 큰 배치가 유리하며, 지연 시간 중심의 병렬 처리를 통해 추가 GPU를 투입하여 학습 시간을 단축할 수 있습니다. 그럼에도 불구하고 고정된 시간 예산 내에서도 더 적은 수의 GPU와 작은 배치를 사용하는 것이 더 많은 GPU와 큰 배치를 사용하는 것보다 더 낮은 검증 손실을 달성할 수 있으며, 이는 마감 기한 내에서 GPU 활용도를 극대화하기 위해 데이터 병렬 처리를 늘리는 일반적인 관행에 도전합니다. 종합적으로 본 연구 결과는 반복 데이터 학습에서 충분히 탐구되지 않았던 요인들을 식별하고, 단일 패스 사전학습 대비 학습 레시피와 자원 할당이 어떻게 변화해야 하는지에 대한 구체적인 지침을 제공합니다.
BLOKS: 스케치된 블록 전처리를 통한 커널 솔버의 스케일링
BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning
커널 리지 회귀(Kernel Ridge Regression, KRR)는 비매개변수적 학습(nonparametric learning)을 위한 이론적으로 타당한 알고리즘이며, 심층 학습(deep learning)의 특성을 연구하는 데에도 자주 사용된다. 그러나 정확한(exact) KRR 수식은 대규모 데이터셋(dataset)에 적용할 수 없을 정도의 시간 및 메모리 비용을 발생시키며, 이는 근사 솔버(approximate solver) 개발의 동기가 되었다. 이러한 알고리즘들은 (i) 직접적인 해법의 계산 부담을 피하기 위한 반복적 방법(iterative method), (ii) 문제 크기를 줄이기 위한 스케칭(sketching) 또는 배치화(batching), (iii) 수렴(convergence)을 가속화하기 위한 전처리(preconditioning)에 의존한다. 빠른 수렴을 위해 필수적이지만, 전처리는 메모리 비용을 발생시키며, 이는 모델(model)의 자유 매개변수 수를 줄임으로써 관리할 수 있으나 그 대가로 표현력, 나아가 정확도가 저하될 수 있다. 이러한 문제를 해결하기 위해, 우리는 블록 자코비(Jacobi) 근사와 스케칭을 결합한 새로운 프리컨디셔너(preconditioner)를 중심으로 구축된, Nyström 방식으로 스케치된 KRR을 위한 컨주게이트 그래디언트(Conjugate Gradient) 기반 솔버인 BLOKS를 제안한다. BLOKS의 프리컨디셔너는 데이터셋 크기와 매개변수 수 모두와 무관한 메모리 비용을 가지므로, 대규모 모델로의 스케일링(scaling)이 가능하다. 우리는 메모리 효율적이고 GPU로 가속화된 구현을 제공하며, BLOKS가 우수한 시간/메모리 복잡도를 유지하면서도 뛰어난 정확도를 달성함을 보인다. 실제로, 커널 솔버를 벤치마킹(benchmark)하는 데 사용되는 표준 대규모 데이터셋에서 BLOKS는 최신(state-of-the-art) 기법들과 비교할 만하거나 그보다 더 나은 성능을 달성한다.
Adaptive DHiSparse: 부하 적응형(Load-Adaptive) KV 계층 구조에서의 추측 디코딩(Speculative Decoding)
Adaptive DHiSparse: Speculative Decoding over a Load-Adaptive KV Hierarchy
롱 컨텍스트(long-context) 서빙은 하드웨어가 유효 처리량(throughput)에 도달하기 전에 KV 메모리가 먼저 소진된다. HiSparse는 히스토리를 호스트 메모리에 저장하고 선택된 항목만 가져오지만, 모든 로드(load)에서 단일 캐시 예산(budget)을 사용하며 DSpark 및 DFlash2와 같은 드래프트 모델(draft-model) 추측 디코딩(speculative decoding)을 처리하지 못한다. 우리는 계층적 희소(hierarchical sparse) KV 위에서 추측 디코딩을 지원하고 상주(residency)를 부하(load)에 맞춰 적응시키는 Adaptive DHiSparse를 제시한다. 이 방법은 필요한 작업 집합(working set)을 보호하고, GPU 메모리가 여유 있을 때 추가 히스토리를 유지하며, 나머지는 정확한 융합 검색(fused retrieval)을 통해 복구한다. DSpark와 DFlash2는 각자의 제안(proposal) 및 수락(acceptance) 규칙을 그대로 유지한다: 쿼리는 누락된 행(missing-row) 검색을 공유하고, 드래프트 KV는 윈도우 경계(window-bounded) 링을 사용하며, 검증(verification) 스테이징은 층(layer) 그룹 간에 재사용된다. 100K 컨텍스트와 동시성(concurrency) 128에서, DFlash2를 사용한 GLM-5.3은 디코드 GPU당 793 출력 토큰(token)/s를 달성하며, 이는 HiSparse의 1.45배, 추측 디코딩을 사용하지 않는 적응형 서빙의 1.27배이다. HiSparse와 동일한 지연 시간(latency) 한계를 유지할 때, 이 방법은 동시성을 최대 4배까지, 출력을 토큰당 한계에 따라 2.3배에서 3.7배까지 유지한다. 500K 컨텍스트와 동시성 512에서 DeepSeek-V4.1-Flash에 대해, DSpark를 사용한 Adaptive DHiSparse는 DSpark를 사용한 상주(resident) 서빙의 출력보다 1.85배 높은 출력을 달성한다. 로드 단계(load step)에서, 선택적 상주(residency)는 저부하 상황에서 호스트 페치(fetch) 비율을 선택된 행의 14.2%에서 1.4%로 줄이고, 압박(pressure) 상황에서는 메모리를 해제한다.
FORTE: 산업용 추천 시스템을 위한 특징 평가 및 폐기 프로덕션 프레임워크
FORTE: A Production Framework for Feature Evaluation and Deprecation in Industrial Recommender Systems
프로덕션 추천 시스템에는 특징(feature) 생애주기의 비대칭성이 존재한다: 새로운 특징을 추가할 때는 어떤 지표에서든 성능 향상을 만들어내야 하지만, 특징을 제거할 때는 어떤 지표도 저하시키지 않아야 한다. 실제로는 특징 폐기의 우선순위를 정하기가 어려운데, 특징이 다른 특징들과 상호작용하는 경우, 그 중요도가 매일 변하는 경우, 프로덕션 모델이 변경되거나 데이터 드리프트가 발생하기 전에는 평가할 수 없는 경우, 다른 출시 건들과 A/B 테스트 공간을 두고 경쟁하는 경우, 온라인 A/B 테스트에서 회귀(regression)를 일으키는 경우, 또는 폐기를 조율해야 하는 여러 모델에서 소비되는 경우에는 해당 특징을 제거하지 못할 수 있기 때문이다. 우리는 특징을 발견, 검증, 제거하기 위한 모델에 구애받지 않는(model-agnostic) 프로덕션 프레임워크인 FORTE를 제시한다. 효율적인 교란(perturbation) 구현을 통해 매일 특징 평가가 가능하다. 상호작용을 고려하기 위해, FORTE는 그룹화된 제거(ablation)를 통해 모든 저랭크(low-rank) 특징으로부터 구성된 후보 특징 집합을 평가하며, 이 오프라인 결과는 온라인 A/B 테스트를 충분히 예측할 수 있어 폐기 작업을 자신 있게 온라인 테스트로 진행할 수 있게 한다. 계보 추적(lineage tracing)은 학습 데이터셋에서 특징을 제거함으로써 얻는 전체 절감 효과를 실현하기 위해 모든 다운스트림 소비 모델을 식별한다. 우리는 2개의 대규모 추천 시스템에서 FORTE를 검증하였으며, FORTE가 온라인 회귀를 일으키지 않는 폐기 가능한 특징 집합을 식별함을 확인하였다. 다만 효율성에 대한 영향은 모델 특성에 따라 달라진다. 검색 관련성(search-relevance) 모델에서 FORTE는 32개, 48개, 59개 특징으로 구성된 3개의 중첩된 후보 집합을 도출하였다. 온라인 가드레일은 가장 큰 처리(treatment)를 거부하였다. 48개 특징 집합이 폐기 대상으로 선정되어 해당 모델 특징의 43.3%가 제거되었다. 대규모 랭킹(ranking) 모델에서는 FORTE가 제거 후보로 8개를 식별하였다. 재학습과 A/B 테스트를 통해 회귀가 없음을 확인하였다. 이 배포로 학습 가능한 파라미터가 29.9% 감소하였고, 서빙 처리량(serving throughput)이 19.8~25.5% 향상되었으며, 연간 학습 비용이 수십만 달러 절감되었다.
AI를 위한 진정한 장기 기억: 재계산보다 더 빠르고 저렴한 5,000만 토큰 윈도우
Real Long-Term Memory for AI: A 50-Million-Token Window That Is Faster and Cheaper Than Recompute
대규모 언어 모델(LLM)은 컨텍스트 윈도우에 들어가는 텍스트만 사용할 수 있으며, 프롬프트가 전송될 때마다 해당 프롬프트에 대한 내부 키-값(KV) 상태를 다시 계산합니다. 본 연구에서는 약 16,000개 토큰 블록의 KV 상태를 암호화된 로컬 NVMe 디스크에 저장하고, 이후 재계산 없이 바이트 단위로 정확하게(byte-exact) 다시 로드하는 메모리 층인 공개 패키지 galahad-kv를 테스트합니다. 단일 NVIDIA H100에서 vLLM을 통해 서빙되는 50,000,000개 토큰의 실제 공개 텍스트를 대상으로 Gemma 4 12B 및 Gemma 4 31B와 함께 이를 실행했습니다. 조사한 모든 블록은 두 모델 모두에서 재계산 없이 암호화된 저장소로부터 다시 로드되었습니다(0부터 5,000만 토큰 깊이에서 100회 중 100회). 블록을 로드하는 것은 재계산하는 것보다 2.8배에서 4.3배 더 빨랐고 GPU 에너지를 8.8배에서 12.3배 적게 사용했으며, 전체 5,000만 토큰 스트림 동안 GPU 메모리는 일정하게 유지되었습니다. 수백만 토큰 앞서 심어둔 사실에 대한 질문에서 12B 모델은 100회 중 82회, 31B 모델은 100회 중 98회 올바른 답변을 제시했습니다. 두 모델 모두 답을 지어내지 않았습니다. 한계점은 다음과 같습니다. 이는 더 넓은 어텐션 윈도우가 아니라 저장된 상태를 재사용하는 것입니다. 즉, 한 번에 하나의 블록이 로드되며, 질문에 얼마나 잘 답하는지는 모델에 달려 있습니다. 메모리 쓰기는 일회성 비용이며 저장소는 수 테라바이트의 로컬 NVMe 디스크를 차지합니다. 본 논문에서는 롱 컨텍스트 벤치마크를 왜곡하는 일반적인 방식에 대응하도록 설계된 테스트 프로토콜을 설명하고, 공개 소프트웨어 및 해당 패키지의 무료 라이선스를 활용하는 단일 GPU 재현 방안을 제공합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
10 pages, 6 figures