SlimCaching: Edge Caching of Mixture-of-Experts for Distributed Inference

이 논문은 엣지 디바이스의 저장 공간 제약 하에서 분산 추론을 위한 MoE(Mixture-of-Experts) 모델의 전문가 캐싱을 최적화하여 추론 지연 시간을 최소화하는 새로운 알고리즘을 제안하고 그 유효성을 입증합니다.

핵심

1. 문제 상황: 거대한 도서관과 작은 책장

비유:
마치 **거대한 도서관 (AI 모델)**이 있다고 상상해 보세요. 이 도서관에는 수천 권의 책 (전문가 네트워크, Expert) 이 있습니다. 하지만 우리가 한 번에 읽는 책은 단 한 권뿐입니다. 그런데 문제는 이 도서관의 모든 책을 내 집 (스마트폰이나 엣지 서버) 에 다 가져다 놓으려면 책장이 너무 작아서 들어가지 않는다는 점입니다.

• 기존 방식 (U-Shape): 책을 다 가져오지 못하면, 필요한 책을 찾으러 매번 도서관 본사 (클라우드) 로 연락을 해야 합니다. 책을 요청하고, 도서관에서 찾아서 다시 내게 보내는 과정이 반복되니 시간이 너무 오래 걸립니다.
• 기존의 다른 방식 (그리디 알고리즘): "가장 많이 읽히는 책"만 골라 책장에 꽂아두는 방식입니다. 하지만 AI 는 책 한 권을 읽을 때, 여러 권의 책을 동시에 참고해야 하는 경우가 많습니다 (Top-K 전략). 이때 "가장 인기 있는 책"만 따로따로 모아두면, 필요한 책들이 서로 떨어져 있어 다시 한 번 연락해야 하는 번거로움이 생깁니다.

2. 해결책: 슬림캐싱 (SlimCaching) 의 마법

이 논문이 제안하는 SlimCaching은 다음과 같은 지혜를 담고 있습니다.

비유: "맞춤형 팀 빌딩"
AI 가 작업을 할 때는 매번 **여러 명의 전문가 (Expert)**가 팀을 이루어 일합니다. 예를 들어, "과학 질문"을 받으면 '물리학자'와 '화학자'가 함께 일하고, "요리 질문"을 받으면 '셰프'와 '영양사'가 팀을 잡는 식입니다.

• 핵심 아이디어: 단순히 인기 있는 전문가를 따로따로 모아두는 게 아니라, **"함께 일하는 팀"**을 고려해서 저장해야 합니다.
• 어떻게 하나요?
  1. 사용자 (내 손): 내가 가장 자주 쓰는 전문가들 (예: 요리 전문가) 을 내 책장에 미리 둡니다.
  2. 엣지 서버 (근처 도서관): 내가 자주 쓰는 전문가들이 함께 일하는 팀이 어디에 있는지 계산해서, 그 팀 전체가 한곳에 모이도록 배치합니다.
  3. 결과: 질문이 들어오면, 내 손에서 바로 해결되거나, 아니면 근처 도서관에서 팀 전체가 모여서 순식간에 해결해 줍니다. 멀리 있는 본사 (클라우드) 에 연락할 필요가 거의 없어집니다.

3. 기술적 난제와 해법: "동시성"의 함정

이 문제는 수학적으로 매우 까다롭습니다.

• K=1 인 경우 (단독 작업): 전문가가 혼자 일하면, "가장 많이 찾는 책"부터 꽂으면 됩니다. (기존의 그리디 알고리즘으로 해결 가능)
• K≥1 인 경우 (팀 작업): 전문가들이 팀을 이루어 일하면 상황이 복잡해집니다.
  • 비유: "물리학자"를 책장에 꽂는 것만으로는 부족하고, 그와 함께 일하는 "화학자"도 같은 책장에 있어야 효율이 나옵니다. 하지만 책장 공간은 한정되어 있습니다.
  • 난제: "누구를 먼저 꽂을까?"를 결정할 때, 혼자서만 보면 좋은 전문가가 나중에 팀을 이루기 위해 다른 전문가를 필요로 할 때 오히려 방해가 될 수 있습니다. (이걸 수학적으로 '비-서브모듈러'라고 합니다.)

해결책:
저자들은 이 복잡한 문제를 작은 조각으로 나누어 해결했습니다.

1. 순차적 분해: 모든 서버를 한 번에 결정하는 게 아니라, 서버 1 번, 2 번, 3 번 순서대로 하나씩 문제를 쪼개서 풉니다.
2. 다이나믹 프로그래밍 (DP): 각 서버에 어떤 전문가 팀을 넣을지, 공간이 얼마나 남았을 때 가장 효율적인지 모든 경우의 수를 계산해 최적의 조합을 찾습니다.
3. 가속화: 계산이 너무 오래 걸리면, 책의 크기가 비슷한 것끼리 묶어서 빠르게 계산하는 방법을 썼습니다.

4. 실험 결과: 얼마나 빨라졌나?

시뮬레이션 결과, 제안한 방법은 기존 방식들보다 지연 시간 (Latency) 을 획기적으로 줄였습니다.

• 저장 공간이 부족할 때: 특히 저장 공간이 좁을수록 효과가 큽니다. (가장 필요한 팀을 효율적으로 배치했기 때문)
• 사용자가 많을 때: 많은 사람이 동시에 질문을 해도, 서버들이 서로 협력해서 처리하므로 속도가 느려지지 않습니다.
• 계산 속도: 이 복잡한 계산을 하는 데도 기존 방식보다 훨씬 빠르고 가볍게 작동했습니다.

요약

이 논문은 **"AI 를 엣지 (단말기) 에서 돌릴 때, 단순히 인기 있는 부품만 저장하는 게 아니라, 부품들이 어떻게 짝을 이루는지 (팀워크) 를 고려해서 저장해야 속도가 빨라진다"**는 것을 증명했습니다.

마치 요리사가 일할 때, 혼자서 모든 재료를 구하러 다니는 대신, 함께 일하는 조수들과 함께 주방에 배치되어 있으면 훨씬 빠르게 요리를 완성할 수 있는 것과 같은 원리입니다. 이 기술은 앞으로 스마트폰에서 더 똑똑하고 빠른 AI 를 사용하는 데 큰 도움을 줄 것입니다.

기술 요약

1. 문제 정의 (Problem Definition)

배경:
대형 언어 모델 (LLM) 의 확장성을 높이기 위해 혼합 전문가 (Mixture-of-Experts, MoE) 아키텍처가 널리 사용되고 있습니다. MoE 는 입력 토큰당 소수의 관련 전문가 (Expert) 네트워크만 활성화하여 계산 효율성을 높입니다. 그러나 MoE 모델은 전체 파라미터 수가 방대하여 저장 공간이 제한된 엣지 디바이스 (예: 스마트폰) 에서는 모든 전문가를 로컬에 저장하기 어렵습니다.

기존 접근법의 한계:
기존의 분산 추론 방식 (예: U-shaped Split Inference) 은 모델 레이어를 사용자와 엣지 서버/클라우드 사이에 분할합니다. 하지만 MoE 의 경우, 각 토큰마다 Top-K 전략에 따라 여러 전문가가 동시에 활성화되는 특성이 있습니다.

• 저장/메모리 부담: 엣지 디바이스에 모든 전문가를 캐싱할 수 없어, 필요한 전문가가 없을 때마다 엣지 서버나 클라우드로 숨은 상태 (Hidden State) 를 전송해야 하므로 통신 지연이 발생합니다.
• 복잡한 의존성: $K \ge 1$일 때, 같은 레이어 내에서 활성화된 전문가들 간의 공활성화 (Co-activation) 의존성이 발생합니다. 이는 기존 콘텐츠 캐싱 이론에서 가정하는 '독립성'을 깨뜨려, 단순한 그리디 (Greedy) 알고리즘이나 서모듈러 (Submodular) 최적화 기법이 더 이상 유효하지 않게 만듭니다.

핵심 문제:
제한된 저장 용량을 가진 분산 엣지 서버들에 MoE 전문가들을 어떻게 배치 (Placement) 해야 전체 사용자의 평균 추론 지연 시간 (Inference Latency) 을 최소화할 수 있는가?

---

2. 방법론 (Methodology)

저자들은 SlimCaching이라는 새로운 프레임워크를 제안하며, 이를 해결하기 위해 다음과 같은 수학적 모델링과 알고리즘을 설계했습니다.

A. 시스템 모델 및 지연 시간 분석

• 구조: 사용자 디바이스, 엣지 서버, 클라우드 (전체 모델 보유) 로 구성됩니다. 사용자는 선호하는 전문가를 로컬에 캐싱하고, 엣지 서버는 나머지 전문가를 분산 캐싱합니다.
• 지연 시간 계산: 토큰이 로컬, 엣지, 클라우드 중 어디에서 처리되느냐에 따라 통신 (상향/하향) 및 계산 지연이 결정됩니다.
  • 로컬 캐시 히트: 통신 지연 0.
  • 엣지/클라우드 미스: 숨은 상태 전송 및 결과 수신에 따른 지연 발생.
  • Top-K 전략의 영향: $K=1$일 때는 단일 전문가만 찾으면 되지만, $K>1$일 때는 $K$개의 전문가가 모두 배치된 서버 (또는 여러 서버 간 협력) 에서 처리되어야 하므로 지연 시간이 단순 합이 아닌 복잡한 함수가 됩니다.

B. 최적화 문제 공식화

• 목적 함수: 평균 추론 지연 시간 최소화를 위해, 캐싱 전략 $X$에 따른 지연 감소량 (Latency Reduction) 을 최대화합니다.
• 제약 조건: 각 엣지 서버의 저장 용량 (Knapsack Constraint).
• 문제 특성 분석:
  • $K=1$인 경우: 문제가 단조 증가 서모듈러 (Monotone Submodular) 최대화 문제로 귀결됩니다.
  • $K \ge 1$인 경우: 전문가 간의 의존성으로 인해 비서모듈러 (Non-submodular) 및 비초모듈러 (Non-supermodular) 문제가 됩니다. 이는 기존 그리디 알고리즘이 근사 해를 보장하지 못하게 만드는 핵심 장벽입니다.

C. 제안된 알고리즘

1. $K=1$ 경우 (Special Case):

   • 그리디 기반 알고리즘: 서모듈러 최대화 문제에 적용 가능한 그리디 알고리즘을 사용하여 $(1 - 1/e)$-근사 보장을 제공합니다.

2. $K \ge 1$ 경우 (General Case):

   • 연속적 그리디 분해 (Successive Greedy Decomposition): 전체 문제를 엣지 서버 인덱스 순서대로 $N$개의 하위 문제 (Subproblem) 로 분해합니다.
   • 동적 계획법 (DP) 기반 알고리즘: 각 하위 문제는 모듈러 함수와 초모듈러 함수의 합으로 표현되며, 이를 DP 를 통해 해결합니다.
   • 가속화 알고리즘 (Accelerated Algorithm): MoE 모델 내 전문가들의 데이터 크기가 동일하거나 소수 종류로 그룹화될 수 있다는 점을 활용하여, 최대 합성 (Max-convolution) 기법을 도입합니다. 이를 통해 다항 시간 내에 $(1 - \kappa_g)/2$-근사 해를 구할 수 있으며, 여기서 $\kappa_g$는 초모듈러 곡률 (Supermodular Curvature) 입니다.
   • 근사 비율 보장: 단일 엣지 서버 환경에서는 $1/2$, 다중 서버 환경에서는 $1/4$의 근사 비율을 이론적으로 보장합니다.

---

3. 주요 기여 (Key Contributions)

1. 새로운 문제 정의: 분산 MoE 추론을 위한 '전문가 캐싱 (Expert Caching)' 문제를 최초로 정의하고, Top-K 활성화 전략으로 인한 비서모듈러 특성을 규명했습니다.
2. 이론적 알고리즘 설계:
   • $K=1$에 대해 $(1-1/e)$ 근사 보장을 갖는 그리디 알고리즘을 제시.
   • $K \ge 1$에 대해 비서모듈러 문제를 해결하기 위한 연속적 분해 및 DP 기반 알고리즘을 제안하고, 다항 시간 내 근사 해의 이론적 보장을 증명했습니다.
3. SlimCaching 프레임워크: 사용자 로컬 캐싱과 엣지 서버 분산 캐싱을 협력적으로 최적화하여, U-shaped 분할 추론보다 통신 효율성을 극대화하는 아키텍처를 제안했습니다.

---

4. 실험 결과 (Experimental Results)

저자들은 SQA(Science Question Answering) 및 VQA-v2 데이터셋을 사용하여 다양한 MoE 모델 (Switch Transformer, MoE-LLaVA, LLaMA-MoE 등) 로 시뮬레이션을 수행했습니다.

• 지연 시간 성능:
  • 제안된 알고리즘은 기존 그리디, LFU(Least Frequently Used), 랜덤, U-shaped 분할 추론 기법보다 일관되게 낮은 평균 토큰당 지연 시간을 기록했습니다.
  • 엣지 서버 저장 용량이 2.5GB 일 때, 제안 방법은 기존 그리디 대비 16.7%, LFU 대비 19.5% 지연 시간을 감소시켰습니다.
  • 사용자 로컬 캐싱 용량이 작을 때 (전문가 수가 적을 때) 제안 방법의 성능 우위가 특히 두드러졌습니다.
• 확장성 및 계산 효율성:
  • 엣지 서버 수, 사용자 수, 모델 수, 저장 용량이 증가할수록 기존 그리디 알고리즘의 실행 시간이 기하급수적으로 증가하는 반면, 제안된 알고리즘은 선형적 또는 낮은 다항식 시간으로 확장되어 계산 효율성이 뛰어났습니다.
• 통신 효율성:
  • U-shaped 방식은 토큰당 고정된 통신 오버헤드를 가지지만, SlimCaching 은 활성화된 전문가가 로컬/엣지에 모두 있을 경우 통신을 생략하여 저장 용량이 증가함에 따라 지연 시간이 급격히 감소하는 것을 확인했습니다.

---

5. 의의 및 결론 (Significance)

이 논문은 에지 AI 에서는 MoE 모델의 대규모 파라미터를 어떻게 효율적으로 분산 배치할 것인가라는 근본적인 질문에 답을 제시했습니다.

• 이론적 기여: MoE 의 Top-K 활성화 메커니즘으로 인해 발생하는 비서모듈러 최적화 문제를 해결하기 위한 새로운 알고리즘적 접근법 (분해 및 DP 기반 근사 알고리즘) 을 제시하여, 기존 캐싱 이론의 한계를 극복했습니다.
• 실용적 가치: 제한된 저장 공간과 대역폭을 가진 엣지 환경에서도 고사양 LLM 을 저지연으로 구동할 수 있는 실용적인 프레임워크 (SlimCaching) 를 제공하며, 프라이버시 보호 (로컬 데이터 유지) 와 통신 비용 절감 효과를 동시에 달성할 수 있음을 입증했습니다.
• 미래 전망: 이 연구는 엣지 네트워크에서의 MoE 배포 전략을 위한 새로운 기준을 제시하며, 향후 사용자 스케줄링, GPU 리소스 공유, 전문가 프리페칭 (Prefetching) 등과의 결합을 통해 더욱 발전할 수 있는 기반을 마련했습니다.