Inference-Cost-Aware Dynamic Tree Construction for Efficient Inference in Large Language Models

본 논문은 GPU 구성 및 배치 크기 등 추론 비용을 고려하여 동적으로 트리 구조를 최적화하는 'CAST'라는 새로운 방식을 제안함으로써, 기존 최첨단 기법보다 5~20% 더 빠르고 최대 5.2 배까지 추론 속도를 향상시킨다고 설명합니다.

핵심

🚀 "CAST": AI 가 말을 더 빠르고 똑똑하게 하도록 돕는 새로운 비법

이 논문은 최근 가장 핫한 기술인 **거대 언어 모델 (LLM, 예: 챗봇)**이 말을 할 때 발생하는 '지연' 문제를 해결하기 위한 새로운 방법을 소개합니다.

기존의 AI 는 한 번에 한 마디씩 (토큰 하나씩) 생각해서 말하는데, 이 과정이 너무 느려서 사용자가 답답함을 느끼곤 합니다. 이 논문은 **"CAST"**라는 새로운 기술을 제안하며, 이를 통해 AI 의 응답 속도를 기존보다 최대 5.2 배까지 높였다고 합니다.

이 복잡한 기술을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 문제 상황: "혼자서 모든 걸 다 해야 하는 비효율적인 비서"

기존의 AI 는 마치 혼자서 모든 일을 처리하는 비서와 같습니다.

• "안녕하세요"라고 말하면, 그 다음 단어를 예측해서 쓰고, 그 다음 단어를 예측해서 쓰고... 이 과정을 반복합니다.
• 이 비서는 한 번에 한 가지 일만 할 수 있어서, 긴 글을 작성할 때 시간이 너무 오래 걸립니다.

2. 기존 해결책: "예상해서 미리 말하기 (Speculative Decoding)"

이 문제를 해결하기 위해 연구자들은 **"예상 비서 (Draft Model)"**를 도입했습니다.

• **주인 (본래 AI)**은 느리지만 정확합니다.
• 예상 비서는 빠르지만 가끔 틀립니다.
• 작동 방식: 예상 비서가 주인이 말할 다음 5 단어를 미리 예상해서 적어둡니다. 주인은 그걸 보고 "아, 맞아!"라고 승인하면 그대로 내보내고, "아니야"라고 하면 다시 처음부터 씁니다.

이 방식은 EAGLE-2, EAGLE-3 같은 최신 기술로 발전했습니다. 이들은 예상 비서가 나무 (Tree) 모양으로 여러 가지 가능성을 동시에 예상하게 하여, 틀려도 다른 가지 (다른 가능성) 는 살려두는 방식을 썼습니다.

3. 새로운 문제: "나무가 너무 크면 오히려 무거워진다"

하지만 여기서 새로운 문제가 생겼습니다.

• 나무 (예상 가능성) 가 너무 크면?
  • 예상 비서가 너무 많은 가지 (단어) 를 만들어내면, 주인이 모두 확인하는 데 시간이 더 걸립니다.
  • 특히 컴퓨터 (GPU) 의 성능이나 **동시에 처리하는 사람 수 (Batch Size)**에 따라 최적의 나무 크기가 다릅니다.
  • 기존 기술들은 "나무가 클수록 무조건 좋다"라고 생각해서, 컴퓨터가 감당하기 힘든 너무 큰 나무를 만들어내면 오히려 속도가 느려지는 경우가 있었습니다.

비유: 마치 택배 트럭을 생각해보세요.

• 트럭이 작을 때는 짐을 적게 실어야 빠릅니다.
• 트럭이 크고 도로가 넓을 때는 짐을 많이 실어야 효율이 좋습니다.
• 하지만 트럭 크기와 도로 상황에 맞춰 짐을 적절히 실지 않고, 무조건 "짐을 최대한 많이 실자!"라고 하면 트럭이 과부하가 걸려서 오히려 더 늦게 도착합니다.

4. CAST 의 해결책: "상황을 봐서 나무를 잘라내는 똑똑한 정원사"

이 논문에서 제안한 CAST는 바로 이 **'상황을 보는 눈'**을 가진 기술입니다.

• 상황 인식: CAST 는 지금 컴퓨터가 얼마나 강력한지, 동시에 몇 명을 상대하고 있는지 (배치 크기) 를 먼저 확인합니다.
• 동적 조절:
  • 컴퓨터가 여유롭고 한 번에 많은 일을 처리해야 한다면? → 나무를 크게 키웁니다. (더 많은 단어 예상)
  • 컴퓨터가 바쁘거나 한 명만 상대한다면? → 나무를 작게 잘라냅니다. (불필요한 예상 제거)
• 비용 계산: "이 단어를 예상하는 데 드는 시간 (비용)"과 "맞을 확률 (이득)"을 저울질해서, 가장 효율적인 나무 모양을 실시간으로 만듭니다.

비유: CAST 는 현명한 정원사입니다.

• 비가 오고 바람이 불면 (컴퓨터가 바쁘면) 가지를 너무 많이 자르지 않고, 햇살이 좋고 땅이 넓으면 (컴퓨터가 여유로우면) 가지치기를 더 과감하게 합니다.
• 항상 최적의 크기로 나무를 유지해서, 주인 (AI) 이 가장 빠르게 말을 끝낼 수 있게 도와줍니다.

5. 결과: 얼마나 빨라졌나요?

이 방법을 실험해 보니 놀라운 결과가 나왔습니다.

• 속도 향상: 기존 AI 보다 최대 5.2 배 더 빨라졌습니다. (예: 10 초 걸리던 게 2 초 만에 끝남)
• 기존 기술 대비: 최신 기술 (EAGLE-3 등) 보다도 5%~20% 더 빠릅니다.
• 범용성: 대화, 코딩, 수학 문제, 요약 등 다양한 상황에서 모두 잘 작동했습니다.

요약

이 논문은 **"AI 가 말을 할 때, 무조건 많이 예상하는 게 좋은 게 아니라, 컴퓨터의 상황 (하드웨어) 과 작업량 (배치 크기) 에 맞춰 적당히 예상하는 것이 가장 빠르다"**는 사실을 증명했습니다.

CAST는 이 원리를 바탕으로 AI 의 응답 속도를 획기적으로 높여, 우리가 더 빠르고 자연스럽게 AI 와 대화할 수 있게 해주는 스마트한 가속 장치라고 할 수 있습니다.

기술 요약

1. 문제 제기 (Problem)

대규모 언어 모델 (LLM) 은 자동회귀 (autoregressive) 방식의 설계와 방대한 파라미터 수로 인해 추론 지연 (inference latency) 이 심각한 문제입니다. 이를 해결하기 위해 도입된 Speculative Decoding(추측적 디코딩) 은 경량 드래프트 모델이 토큰을 생성하고, 타겟 모델이 이를 검증하는 방식으로 여러 토큰을 한 번의 프론트워드 패스로 처리하여 지연을 줄입니다.

최근 EAGLE-2 및 EAGLE-3와 같은 동적 트리 (dynamic tree) 구조를 활용한 접근법이 성능을 개선했으나, 다음과 같은 한계가 존재합니다:

• 시스템 변수 무시: GPU 장치 유형, 배치 크기 (batch size) 등 중요한 시스템 변수가 추론 비용에 미치는 영향을 고려하지 않음.
• 비효율적인 확장: 단순히 토큰 수를 늘리는 것이 항상 성능 향상으로 이어지지 않음. GPU 리소스 경쟁이나 동기화 오버헤드로 인해 오히려 전체 처리 속도가 느려질 수 있는 임계값을 넘어서는 경우가 발생함.

2. 제안 방법론: CAST (Cost-Aware Speculative Tree)

저자들은 추론 비용 (inference cost) 을 고려하여 동적으로 트리 구조를 최적화하는 새로운 방법인 CAST를 제안합니다. 이 방법은 EAGLE-2/3 를 기반으로 하되, 수용된 토큰 수 (accept length) 와 추론 비용 간의 트레이드오프를 균형 있게 조절합니다.

핵심 구성 요소:

1. 추론 비용 모델링:

   • 배치 크기 ($B$), 컨텍스트 길이 ($c$), 입력 시퀀스 길이 ($n$) 에 따른 추론 시간을 함수 $f(B, c, n)$로 모델링합니다.
   • 타겟 모델 ($f_T$) 과 드래프트 모델 ($f_D$) 에 대해 사전 계산된 룩업 테이블 (lookup table) 을 유지하여 실시간으로 비용을 추정합니다.

2. 동적 확장 단계 (Dynamic Expansion Stage):

   • 너비 가지치기 (Breadth Pruning): 각 레이어에서 유지할 노드 수를 결정합니다. 경제학의 '한계 효용 체감' 원리를 적용하여, 신뢰도 점수 (confidence score) 를 기반으로 토큰을 선택하되, 추가 토큰 생성에 따른 비용 증가가 효용 증가를 상회하지 않는 지점에서 선택을 중단합니다.
   • 깊이 가지치기 (Depth Pruning): 다음 레이어를 생성할지 여부를 결정합니다. 이전 레이어의 예측 품질 (예: 수용 확률) 과 비용 효율성을 기반으로 임계값을 설정하여 불필요한 깊은 트리의 생성을 방지합니다.

3. 동적 재순위화 단계 (Dynamic Reranking Stage):

   • 확장된 트리에서 검증할 토큰의 수를 결정합니다. 전체 트리의 누적 확률 점수와 추론 비용을 고려하여, 타겟 모델이 검증할 최적의 토큰 수를 알고리즘 1 을 통해 동적으로 산출합니다.

3. 주요 기여 (Key Contributions)

1. 비용 인식형 동적 트리 (CAST) 제안: 검증할 토큰 수와 추론 비용 간의 트레이드오프를 기반으로 한 새로운 동적 트리 기반 추측적 디코딩 방법론을 제시했습니다.
2. 기존 SOTA 방법의 일반화 및 확장: EAGLE-2 및 EAGLE-3 의 알고리즘을 특수한 경우로 포함시키며, 기존 문헌에서 충분히 논의되지 않았던 배치 처리 (batching) 와 GPU 하드웨어의 영향을 체계적으로 고려합니다.
3. 광범위한 실험 검증: 6 가지 다양한 작업 (대화, 코드 생성, 수학 추론 등) 과 6 가지 다른 LLM (Vicuna, LLaMA3, Qwen2, DeepSeek-R1 등) 을 대상으로 실험을 수행하여 방법론의 효과성을 입증했습니다.

4. 실험 결과 (Results)

저자들은 다양한 모델과 작업에서 CAST 를 기존 방법 (Standard Speculative Decoding, Medusa, PLD, Lookahead, EAGLE 시리즈 등) 과 비교했습니다.

• 단일 샘플 (Batch Size = 1) 환경:

  • CAST 는 기존 최첨단 방법인 EAGLE-3 보다 5%~20% 더 빠른 속도 향상을 보였습니다.
  • 특히 HumanEval 벤치마크에서 **최대 5.23 배 (약 5.2x)**의 속도 향상을 기록했습니다.
  • 모델 크기가 커질수록 (예: LLaMA-3.3-70B) CAST 의 성능 우위가 더욱 두드러졌습니다.

• 배치 처리 (Batch Size = 8) 환경:

  • 배치 처리 시에도 CAST 는 일관된 성능 개선을 보였습니다.
  • V13B-HumanEval (Temperature 0) 에서 3.12 배, V13B-MT-Bench (Temperature 1) 에서 2.51 배의 속도 향상을 달성했습니다.
  • 기존 방법들은 배치 증가 시 성능이 저하되거나 정체되는 경향이 있었으나, CAST 는 비용 인식을 통해 이를 극복하고 효율성을 유지했습니다.

5. 의의 및 결론 (Significance)

이 논문은 LLM 추론 가속화 분야에서 하드웨어 제약과 시스템 변수를 고려한 '비용 인식형' 접근법의 중요성을 강조합니다.

• 단순히 더 많은 토큰을 생성하는 것이 아니라, 어떤 상황에서 어떤 크기의 트리가 가장 효율적인지를 동적으로 판단함으로써, 실제 배포 환경 (실제 GPU 환경, 다양한 배치 크기) 에서 더 실용적인 성능 개선을 이끌어냈습니다.
• CAST 는 추론 지연을 획기적으로 줄이면서도 출력 품질을 유지하는 Lossless 가속화 기술로서, 대규모 LLM 의 실용적 배포에 중요한 기여를 할 것으로 기대됩니다.

코드 공개: https://github.com/EAGLE-Research/sglang-eagle4