기술 요약: Kalypso: 관계형 LLM 서빙

1. 문제 정의

대규모 언어 모델(LLM)은 비정형 데이터를 필터링, 추출, 순위 지정, 조인 및 변환하는 현대적 데이터 관리 시스템 내의 시맨틱 연산자(semantic operators)로서 점점 더 많이 활용되고 있습니다. 현재의 시맨틱 쿼리 처리 시스템(SQPS)은 요청 중심(request-centric) 서빙 시스템(예: vLLM, SGLang)을 통해 추론 요청을 호출함으로써 LLM을 통합합니다. 이러한 서빙 시스템은 paged attention 및 prefix caching과 같은 기술을 통해 개별 요청을 최적화하지만, 더 넓은 범위의 시맨틱 쿼리 계획(semantic query plan)에 대해서는 인지하지 못합니다.

이러한 구조적 단절은 심각한 성능 병목 현상을 초래합니다:

• 비효율적인 KV-캐시 사용: 기존 SQPS는 일반적으로 한 번에 하나의 연산자를 실행하며, 단계 사이에 중간 결과를 구체화(materialize)합니다. 이러한 "연산자 단위(operator-at-a-time)" 전략은 LLM 서빙 엔진이 다운스트림 연산자가 재사용하기 전에 중간 튜플에 대한 키-값(KV) 캐시 항목을 제거(evict)하게 만듭니다.
• 중복 계산: 튜플이 업스트림 연산자(예: 필터)에서 다운스트림 연산자(예: 맵)로 흐를 때, 공유된 프롬프트 접두사(시스템 지침 + 튜플 컨텍스트)는 메모리 압박으로 인해 KV 캐시가 제거되었기 때문에 다시 계산되어야 합니다.
• 최적화되지 않은 병렬성: 요청 중심 스케줄러는 연산자 간의 의존성을 고려하지 않습니다. 이들은 GPU를 바쁘게 유지하기 위해 충분한 업스트림 작업을 실행하는 것과, 다운스트림 작업에 필요한 재사용 가능한 접두사를 보존하기 위해 메모리 압박을 피하는 것 사이의 트레이드오프를 조절할 수 없습니다.

2. 방법론: Kalypso

본 논문은 SQPS와 기본 LLM 엔진 사이에 위치하는 관계형 LLM 서빙(relational LLM serving) 시스템인 Kalypso를 소개합니다. Kalypso는 LLM 서빙을 관계형 문제로 취급하여, 쿼리 의미와 출력 정확도를 유지하면서 파이프라인 실행을 가능하게 하도록 서빙 레이어가 시맨틱 쿼리 구조를 인지하도록 만듭니다.

2.1 핵심 아키텍처

Kalypso는 시맨틱 쿼리 계획을 위한 API를 노출하며, 적응형 메모리 인식 스케줄링 알고리즘을 사용하여 이를 실행합니다. 주요 구성 요소는 다음과 같습니다:

• 쿼리 파서(Query Parser): 연산자들을 파이프라인(비차단 연산자의 시퀀스)과 스테이지(차단 연산자 또는 카테시안 곱에 의해 구분되는 하위 시퀀스)로 그룹화합니다.
• 스케줄러(Scheduler): 파이프라인 실행을 조율하는 핵심 구성 요소입니다. 가용 GPU 메모리에 따라 태스크(튜플을 스테이지를 통해 처리하는 원자적 단위)를 실행합니다.
• 메모리 추정기(Memory Estimator): 과도한 할당이나 할당 부족을 방방지하기 위해 각 연산자의 요청에 대한 토큰 수를 예측합니다.
• KV 캐시 관리자(KV Cache Manager): 메모리 블록을 관리하기 위해 기본 LLM 엔진(예: vLLM)과 인터페이스하며, 명시적 고정(explicit pinning)(특정 블록의 제거 방지) 및 가상 고정(virtual pinning)(접두사를 암시적으로 보존하기 위해 실행 속도를 제어)을 모두 지원합니다.

2.2 핵심 메커니즘

접두사 재사용을 통한 파이프라인 실행

중간 테이블을 구체화하는 전통적인 SQPS와 달리, Kalypso는 튜플을 한 연산자에서 다음 연산자로 직접 스트리밍합니다.

• 접두사 공유: 튜플이 필터에서 맵으로 전달될 때, 프롬프트 접두사(System Prompt + Tuple Content)는 동일하게 유지됩니다. Kalypso는 업스트림 연산자가 완료된 직으로 다운스트림 연산자를 스케줄링하여, 이 접두사에 대한 KV 캐시가 여전히 GPU 메모리에 상주하도록 보장합니다.
• 태스크 세분도(Task Granularity): 실행은 스테이지와 태스크로 조직됩니다. 태스크는 일련의 연산자를 통해 하나의 튜플을 처리합니다. 스케줄러는 대기 중인 태스크 큐와 실행 중인 태스크 집합을 관리합니다.

적응형 메모리 인식 스케줄링

중앙 과제는 병렬성(GPU 활용도 극대화)과 메모리 압박(캐시 제거 유발) 사이의 균형을 맞추는 것입니다. Kalypso는 다음과 같은 동적 스케줄링 알고리즘을 채택합니다:

1. 동적 예산 할당: 각 스테이지에는 메모리 예산이 할당됩니다. 스케줄러는 스테이지에 충분한 잔여 예산이 있는 경우에만 태스크를 수락합니다.
2. 기아(Starvation) 및 포화(Saturation) 감지:
   • 기아: 스테이지의 대기 큐가 너무 작으면(다운스트림이 유휴 상태이면), 스케줄러는 더 많은 작업을 생성하기 위해 다운스트림 스테이지에서 업스트림 스테이지로 메모리 예산을 이동시킵 mankind.
   • 포화: 스테이지의 큐가 너무 크면(업스트립이 파이프라인을 범람시키고 있으면), 스케줄러는 백로그를 소비하고 메모리를 해제하기 위해 예산을 다운스트림 스테이지로 이동시킵니다.
3. 온라인 재균형: 알고리즘은 큐 크기와 메모리 가용성에 따라 이러한 예산을 지속적으로 조정하여 필터 선택도(selectivity) 및 조인 팬아웃(join fanout)과 같은 워크로드 특성에 적응합니다.

메모리 관리 기술

• 토큰 경계 추정(Token Bound Estimation): Kalypso는 연산자가 생성할 최대 토큰 수를 추정합니다. 요청이 이 경계를 초과하면 실행이 중단되고, 경계가 증가된 후 태스크가 다시 큐에 삽입됩니다. 이는 예측 불가능한 메모리 급증을 방지합니다.
• 고정 전략:
  • 명시적 고정: 스케줄러가 KV 블록을 해제할 때까지 블록을 잠그는 LLM 엔진의 지원이 필요합니다.
  • 가상 고정: 스케줄러가 실행 속도를 제어하여 엔진의 기본 LRU 정책에 의해 접두사가 제거되기 전에 소비되도록 하는 최선 노력(best-effort) 방식입니다. 논문에서는 이 방식이 엔진 수정 없이도 명시적 고정과 거의 동일한 성능을 달성한다고 언급합니다.
• 데드락 핸들링: 시스템에는 데드락 모니터가 포함되어 있습니다. 순환 대기(예: 업스트림이 다운스트림이 필요로 하는 메모리를 보유함)가 발생하면, Kalypso는 메모리의 고정을 해제하고 가상 고정 방식으로 전환하여 사이클을 끊습니다.

3. 주요 기여

1. 관계형 LLM 서빙 추상화: SQPS와 LLM 엔진 사이를 연결하여 쿼리 계획을 서빙 레이어에 노출함으로써 파이프라이닝을 가능하게 하는 새로운 아키텍처 및 API.
2. 적응형 스케줄링 알고리즘: 종속된 연산자 간의 KV-캐시 재사용을 극대화하기 위해 GPU 메모리 압박을 관리하고, 기아 및 포화를 피하기 위해 메모리 예산을 동적으로 재균형하는 혁신적인 온라인 스케줄러.
3. 강력한 메모리 관리: 제한된 GPU 메모리 하에서도 효율적으로 작동할 수 있도록 하는 토큰 경계 추정, 가상 고정 및 데드락 감지/복구 기술.
4. 실증적 검증: 다양한 시맨틱 워크로드에 대해 상당한 지연 시간 감소를 보여주는 종합적인 평가.

4. 결과

저자들은 네 가지 시맨틱 쿼리 워크로드인 FEVER(사실 검증), MEDEC(의료 오류 수정), BioDEX(생물 의학 엔티티 매칭), ContractNLI(계약 함의)에 대해 Kalypso를 평가했습니다. 이들은 요청 중심 LLM 서빙과 연산자 단위 실행을 사용하는 두 기존 SQPS인 Lotus 및 Palimpzest와 비교했습니다.

• 성능 향상: Kalypso는 베이스라인 대비 엔드 투 엔드 쿼리 완료 시간을 1.49배에서 4.57배까지 단축했습니다.
  • 가장 높은 속도 향상(4.57배)은 긴 계약 접두사를 조인 및 맵 연산자 전반에 걸쳐 재사용할 수 있는 ContractNLI 워크로드에서 관찰되었습니다.
  • 이득은 주로 LLM 호출 횟수의 감소보다는 실행 효율성(KV-캐시 재사용을 통한 프리필 비용 감소)에 의해 주도되었습니다.
• 절제 연구(Ablation Studies):
  • 파이프라이닝 vs. 블로킹: 파이프라인 실행을 활성화하는 것(블로킹, 연산자 단위 방식 대비)이 지연 시간을 1.20배에서 1.83배 개선하여, 교차 연산자 접두사 재사용의 가치를 확인했습니다.
  • 적응형 vs. 정적 스케줄링: 정적 메모리 할당 비율은 다양한 워크로드에서 잘 작동하지 않았습니다. 적응형 알고리즘은 실시간 파이프라인 압력에 따라 예산을 이동시킴으로써 최적의 정적 설정보다 일관되게 우수한 성능을 보였습니다.
  • 가상 vs. 명시적 고정: 가상 고정(실행 속도 제어)은 명시적 고정과 유사한 성능을 달성하여, 핵심적인 이점을 얻기 위해 복잡한 엔진 수정이 반드시 필요하지 않음을 시사했습니다.
• 강건성: Kalypso는 GPU 메모리 예산이 크게 줄어든 경우(90%에서 50%로)에도 성능 우위를 유지한 반면, 베이스라인은 캐시 스래싱(thrashing)으로 인해 심각한 지연 시간 증가를 겪었습니다.

5. 의의 및 주장

본 논문은 **쿼리 인식 LLM 서빙(query-aware LLM serving)**이 시맨틱 데이터 처리를 위한 중요한, 그러나 충분히 활용되지 못한 최적화 기법이라고 주장합니다. 쿼리 계획을 서빙 엔진에 인지시킴으로써, Kalypso는 시맨틱 쿼리 실행을 메모리 인식 파이프라인으로 변환합니다.

저자들은 이 접근 방식이 모델 캐스케이딩(model cascading)이나 쿼리 계획 재정렬과 같은 기존 최적화와 **직교(orthogonal)**함을 강조합니다. LLM 호출 횟수를 줄이거나 모델을 근사하는 대신, Kalypso는 수행되는 호출의 효율성을 최적화합니다. 이 시스템은 적절한 스케줄링과 메모리 관리가 있다면 LLM 추론의 높은 비용을 KV-캐시 재사용을 통해 실질적으로 완화할 수 있음을 입증하며, 비정형 데이터에 대한 복잡한 시맨틱 쿼리의 효율적인 실행을 가능하게 합니다.