arXiv:2302.01425

Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective

Michael E. Sander, Joan Puigcerver, Josip Djolonga, Gabriel Peyré, Mathieu Blondel

제출 2023-02-02

원문 초록

The top-k operator returns a sparse vector, where the non-zero values correspond to the k largest values of the input. Unfortunately, because it is a discontinuous function, it is difficult to incorporate in neural networks trained end-to-end with backpropagation. Recent works have considered differentiable relaxations, based either on regularization or perturbation techniques. However, to date, no approach is fully differentiable and sparse. In this paper, we propose new differentiable and sparse top-k operators. We view the top-k operator as a linear program over the permutahedron, the convex hull of permutations. We then introduce a p-norm regularization term to smooth out the operator, and show that its computation can be reduced to isotonic optimization. Our framework is significantly more general than the existing one and allows for example to express top-k operators that select values in magnitude. On the algorithmic side, in addition to pool adjacent violator (PAV) algorithms, we propose a new GPU/TPU-friendly Dykstra algorithm to solve isotonic optimization problems. We successfully use our operators to prune weights in neural networks, to fine-tune vision transformers, and as a router in sparse mixture of experts.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.34077v2cs.LG공통 태그 GPU, Mixture-of-Experts

MaskCoFT: 메모리 효율적인 MoE 추론을 위한 마스크 기반 공적응 미세조정

MaskCoFT: Masked Co-Adaptive Fine-Tuning for Memory-Efficient MoE Inference

전문가 혼합(MoE) 언어 모델은 종종 단일 GPU의 메모리를 초과합니다. 전문가 오프로딩은 대부분의 전문가를 호스트 메모리에 유지하고 필요에 따라 로드하므로, 디코딩 속도는 각 토큰이 가져와야 하는 전문가 수에 따라 달라집니다. 캐싱과 프리페칭은 라우팅이 허용하는 범위 내에서만 이러한 비용을 줄여줍니다. 라우터 전용 미세조정은 전문가를 재사용하도록 라우팅을 재구성할 수 있지만, 전문가가 동결된 상태로 유지되므로 새로운 라우팅이 전송하는 토큰에 전문가가 적응할 수 없습니다. 본 연구에서는 교차 엔트로피 손실만으로 라우터와 전문가를 함께 학습시키는 마스크 기반 공적응 미세조정 방법인 MaskCoFT를 제안합니다. 미세조정 중에 학습 가능한 이진 마스크는 각 층의 Top-K 라우팅을 전문가의 하위 집합으로 제한하며, 전문가는 자신에게 재지정된 토큰에 적응합니다. 추론 시 학습된 마스크는 전문가의 순위를 다시 매기는 소프트 사전 확률(soft prior)이 되어 모든 전문가가 여전히 선택 가능한 상태로 유지됩니다. 본 연구는 Mixtral-8x7B에 대해 층당 4개 전문가, DeepSeek-V2-Lite에 대해 12개 전문가의 GPU 캐시를 시뮬레이션합니다. MaskCoFT는 베이스 모델 대비 토큰당 전문가 페치 횟수를 각각 23.7%와 10.1% 줄입니다. 실제 오프로딩 시스템 서빙에서 출력 토큰당 시간을 각각 최대 16.4%와 5.5% 낮춥니다. 9개 벤치마크에 대한 평균 정확도는 베이스 모델보다 각각 0.92포인트와 0.53포인트 높게 유지됩니다.

arXiv:2609.35882v2cs.CR공통 태그 GPU, Mixture-of-Experts

GenomeOcean Anywhere: 게놈 MoE 모델을 위한 비공개 WebGPU 추론

GenomeOcean Anywhere: Private WebGPU Inference for Genome MoEs

게놈 파운데이션 모델(foundation model)은 시퀀스(sequence)가 생성되는 곳에서 가장 유용하지만, 가장 큰 모델들은 데이터센터급 가속기와 민감한 DNA 정보를 전송할 장소를 필요로 한다. 본 연구는 150억 개 매개변수(parameter) 규모의 게놈 전문가 혼합(MoE) 모델이 전문가(expert)들을 여러 신뢰할 수 없는(untrusted) 기기들에 분산시킨 채, 예측 결과를 바꾸지 않고도, 그리고 어떤 단일 기기에도 시퀀스를 노출하지 않으면서 자원봉사자들의 웹 브라우저에서 대신 실행될 수 있는지를 묻는다. 우리는 신뢰할 수 있는 코디네이터(coordinator)가 어텐션(attention)과 라우팅(routing)을 수행하고, 브라우저 워커(worker)들이 손수 작성한 WebGPU 커널을 통해 모든 전문가의 순전파 신경망(feed-forward network)을 실행하는 시스템을 구축했으며, 실수값 라그랑주 코딩 계산(real-valued Lagrange coded computing)으로 전문가 입력을 보호한다: 각 워커는 가우시안 패딩(Gaussian-padded) 처리된 공유값(share)만을 받아 전문가의 선형 변환(linear map)을 계산하고, 코디네이터는 세 워커 중 임의의 두 워커로부터 결과를 복호화(decode)한다. GenomeOcean-MoE(전문가 8개, top-2 라우팅, 24개 레이어)에서, 브라우저 경로는 모든 양자화(quantization) 수준에서 네이티브(native) llama.cpp와 일치하며, 분산 경로는 BF16 수치 노이즈 바닥(numerical noise floor) 수준을 유지하고(토큰당 KL 0.0036 나트(nats)), 별도로 피팅하지 않은(unfitted) 지연시간 모델은 에뮬레이션된 광역망(wide-area link) 환경에서 디코드(decode) 시간을 0.74%(중앙값) 오차 내로 예측한다. 우리는 먼저 평문(plaintext) 상태의 전문가 입력이 프라이버시를 보장하지 못함을 보인다: 프로브(probe)는 모든 깊이(depth)에서 단일 벡터로부터 토큰을 복원하며, 한 워커는 순서 없는(unordered) 300개의 토큰으로부터 92%의 정확도로 원본 게놈을 식별할 수 있다. 코딩된(coded) 전문가를 사용하면, 공유값으로 학습된 적응형 공격자(adaptive attacker)의 성능은 최다 빈도 토큰 기준선(most-frequent-token baseline) 수준으로 떨어지고, 각 토큰에 대해 한 워커가 얻는 정보는 순전파(forward pass)당 1비트 미만으로 제한되며, 정확도(fidelity) 손실은 BF16 노이즈 바닥 이하로 유지된다. Chrome에서 코딩된 디코딩은 라우팅 정보가 얼마나 은닉되는지에 따라 토큰당 220~376ms로 실행되며, 워커 하나가 실패해도 복제본(replica) 없이 계속 동작한다.

arXiv:2609.35883v2cs.CR공통 태그 GPU, Mixture-of-Experts

CipherGenome: 유전체 전문가 혼합 모델을 위한 동형 추론

CipherGenome: Homomorphic Inference for Genomic Mixture-of-Experts

유전체 파운데이션 모델은 서열을 보유한 기기에 전문가 가중치가 더 이상 들어가지 않을 정도로 희소 전문가 혼합(MoE) 네트워크로 성장하고 있으나, 대여한 가속기에 비공개 유전체를 전송하는 것은 이를 노출시킵니다. 본 논문에서는 하나의 전문가를 호스팅하는 단일 서버만으로도 입력 뉴클레오타이드를 99.8%의 top-1 정확도로 복원할 수 있음을 보여줍니다. 저자들은 신뢰할 수 있는 씬 클라이언트에 15.1B 매개변수 MoE 유전체 모델의 임베딩, 어텐션, 라우터를 유지하고, 매개변수의 95.8%에 달하는 모든 전문가 프로젝션을 Module-LWE 암호화 하에서 신뢰할 수 없고 공모 가능성이 있는 GPU 서버로 외주화하는 프로토콜인 CipherGenome을 제안합니다. 이 설계는 세 가지 구조적 사실을 활용합니다. 즉, 전문가 층은 두 개의 SwiGLU 게이트 사이에서 선형적이고, 전문가 가중치는 공개되어 있으며, GPU 정수 텐서 코어는 단일 GEMM에서 모듈로 $2^{48}$에 대해 암호문-가중치 곱을 정확하게 평가할 수 있다는 점입니다. 클라이언트가 비선형성을 정확하게 평가하고 새로운 비밀값으로 재암호화하므로, 다항식 근사나 부트스트래핑이 전혀 필요하지 않습니다. 12개 박테리아 유전체의 72개 윈도우에서 암호화는 토큰당 $2.54 \times 10^{-4}$ nats의 KL 발산(95% CI 상한 $3.95 \times 10^{-4}$)만을 추가하여 사전 등록된 비열등성 마진 미만이자 bf16 추론과 구별할 수 없는 수준을 보였으며, 동일한 역전 공격은 무작위 추측 수준으로 떨어집니다. 재사용 가능한 공개 힌트는 종단 간 지연 시간을 3.54배 단축하고, 유선 압축은 트래픽을 6.8배 줄이며, 층별 패딩은 라우팅 유출 정확도를 54.9%에서 8.9%로 낮추고, HE 호환 int4 전문가는 평문 전문가와 동등한 비열등성을 유지합니다. 전문가 및 토큰당 서버 측 비용은 CKKS 기준선보다 6 자릿수 이상 낮습니다.

arXiv:2610.02241v1cs.AR공통 태그 GPU, Mixture-of-Experts

조 단위 규모 전문가 혼합 모델을 위한 하드웨어 네이티브 통합 희소-양자화

Hardware-Native Joint Sparse-Quantization for Trillion-Scale Mixture-of-Experts

전문가 혼합(MoE) 아키텍처를 통해 프론티어 언어 모델을 수조 개 파라미터 규모로 확장할 수 있게 되었지만, 방대한 메모리 사용량과 메모리 대역폭의 한계로 인해 실제 배포에는 제약이 따릅니다. 최신 가속기는 저정밀도 반구조화 희소성을 통해 가중치 저장 공간을 줄이고 처리량을 높여주는 희소 텐서 코어(SpTC)를 제공하지만, 상당한 모델 품질 저하와 그룹화된 희소 GEMM 프리미티브의 부재로 인해 MoE에 이를 활용하는 것은 여전히 어렵습니다. 본 논문에서는 전문가 가중치를 하드웨어 네이티브 저정밀도 희소 표현으로 압축하고 SpTC에서의 실행을 가속하는 엔드투엔드 하드웨어-소프트웨어 통합 설계 프레임워크를 제안합니다. 알고리즘 측면에서, 본 프레임워크는 연속적 재매개변수화를 통해 이산적인 반구조화 서포트 선택을 완화함으로써 라우터 가중치 재구성 목표 하에서 양자화된 가중치와의 미분 가능한 통합 최적화 및 확장 가능한 전문가 병렬 압축을 가능하게 합니다. 시스템 측면에서는 SpTC 상의 저정밀도 희소 MoE 추론에 맞춘 커스텀 그룹화 희소 GEMM 커널을 개발합니다. 300억 개에서 1조 개 파라미터에 이르는 MoE 모델 전반에 걸쳐, 제안하는 프레임워크는 기존 최고 수준(SOTA)의 통합 희소-양자화 정확도를 최대 4.35%p 향상시키면서 원래 모델 성능의 96.09%를 보존합니다. NVIDIA B200 GPU에서 개발한 커널은 벤더 기준선 대비 최대 1.65배 뛰어난 성능을 보이며 서빙 처리량을 1.18배 증가시키고 엔드투엔드 지연 시간을 최대 4.03배 단축합니다. 이러한 결과는 하드웨어-소프트웨어 통합 설계가 확장 가능하고 효율적인 MoE 배포를 향한 실용적인 경로임을 입증합니다.

arXiv:2607.19539v1cs.DC공통 태그 GPU, Mixture-of-Experts

타일 수준 신호 및 스케줄링을 통한 전문가 혼합(MoE)의 세밀한 계산-통신 중첩

Fine-grained Computation-Communication Overlap via Tile-level Signaling and Scheduling for Mixture-of-Experts

전문가 혼합(MoE) 아키텍처는 계산 비용을 비례적으로 늘리지 않으면서 모델 용량을 키우며, 대규모 언어 모델(LLM)을 수조 매개변수 규모로 스케일링하는 핵심 구성 요소가 되었다. 이러한 MoE 모델의 효율적인 배포는 다중 GPU에 걸친 분산 실행에 의존하며, 각 MoE 층은 두 번의 all-to-all 통신을 수반한다: 토큰을 전문가 랭크로 디스패치하고 전문가 출력을 소스 랭크로 되돌리는 것이다. 기존 MoE 구현은 전문가 계산이 완료된 뒤 이 반환 all-to-all을 시작하여, 통신 지연을 크리티컬 패스에 노출시키고 GPU 활용률을 낮춘다. 우리는 타일 수준 신호 및 스케줄링을 통해 전문가 계산과 두 번째 all-to-all을 중첩하는 세밀한 접근법을 제시한다. 우리의 생산자-소비자 공동 설계는 다음을 결합한다: (1) 반복적인 커널 실행 오버헤드를 제거하고 원격-중요 타일을 우선 처리하는, 랭크 내 모든 로컬 전문가를 포괄하는 지속적인 per-rank 계산 커널(생산자), 및 (2) 타일이 준비되는 대로 세그먼트 단위 전송을 발행하는 스트리밍 멀티프로세서(SM)의 소규모 전용 파티션 상의 지속적인 통신 커널(소비자). 우리의 공동 설계는 기본 계산 연산자나 통신 원시 연산에 대한 침습적 변경을 피하여, 다중 GPU 시스템에서 분산 MoE 실행 효율을 개선하는 데 실용적이다. 4-A100 GPU 플랫폼에서 세 가지 MoE 모델에 대해 네 가지 최첨단 MoE 시스템과 비교 평가한 결과, 우리 접근법은 최대 2.64배 end-to-end 속도 향상과 2.74배 MoE-층 속도 향상을 달성한다. 기존의 비중첩 기준선과 비교하여, 우리 접근법은 다양한 GEMM 형태, 라우터 모드, 그리고 넓은 범위의 생산자/소비자 SM 파티션에 걸쳐 연산자 및 MoE-층 수준 성능을 일관되게 개선하면서 정확성을 보존한다.

arXiv:2607.14647v1cs.CL공통 태그 GPU, Mixture-of-Experts

D-Cut: 배치 투기적 디코딩을 위한 적응형 검증 깊이 가지치기

D-cut: Adaptive Verification Depth Pruning for Batched Speculative Decoding

투기적 디코딩(speculative decoding)은 출력 품질을 저하시키지 않으면서 대규모 언어 모델(LLM) 추론을 가속한다. 최근 병렬 드래프팅 방법은 드래프트 길이를 드래프팅 지연시간과 분리함으로써 단일 요청 성능을 더욱 향상시키며, 더 긴 드래프트와 더 높은 평균 수락 토큰(MAT, mean accepted tokens)을 가능하게 한다. 그러나 높은 요청 동시성 하에서는 긴 드래프트가 거부된 토큰에 상당한 연산을 낭비하여 검증 비용을 증가시키고, 잠재적으로 투기적 디코딩을 자기회귀(autoregressive) 디코딩보다 느리게 만들 수 있다. 우리는 배치 전체에 걸쳐 드래프트 토큰을 공동으로 선택하고 검증 예산을 수락될 가능성이 가장 높은 토큰에 집중하는 적응형 가지치기 방법인 D-Cut을 제안한다. D-Cut은 두 가지 관찰에 기반한다. 첫째, 수락 길이는 동시 요청 간에 상당히 달라진다. 따라서 D-Cut은 요청 간 가지치기를 수행하여 드래프트 신뢰도에 따라 검증 예산을 적응적으로 할당한다. 둘째, 검증 비용은 GPU 아키텍처 및 병렬화 전략을 포함한 배포 환경에 크게 의존한다. D-Cut은 런타임 비용 모델을 통합하여 대상 환경에 맞게 가지치기 깊이를 적응시킨다. 밀집(dense) 모델과 전문가 혼합(MoE) 모델에 대한 실험은 높은 동시성 하에서 D-Cut이 평균 속도 향상을 \(1.26\times\)에서 \(1.65\times\)로 개선하고, 긴 드래프트 베이스라인이 자기회귀 디코딩보다 느린 밀집 모델 구성에서 가속을 회복하며, MoE 모델에서 자기회귀 디코딩 대비 최대 \(3.0\times\)의 속도 향상을 달성함을 보여준다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.