TreeWalker: 그룹화된 트리 앙상블 추론을 위한 부분 평가

많은 추론 워크로드는 피처 값을 공유하는 로우 그룹에 대해 학습된 트리 앙상블을 평가합니다. 이산 시간 생존 모델은 각 환자를 $G$개의 시간 단계로 확장하고, 클릭률(click-through-rate) 모델은 검색 세션의 모든 항목에 점수를 매기며, 시나리오 분석은 나머지 입력값은 고정한 채 몇 가지 입력을 변화시킵니다. 표준 추론 방식은 각 로우를 독립적으로 처리하여 공유되는 작업을 $G$번 반복합니다. 우리는 그룹화된 추론에 부분 평가(partial evaluation)를 적용하는 TreeWalker를 제시합니다: 상수 피처는 정적이고, 가변 피처는 동적입니다. 이는 각 트리를 그룹당 한 번씩 순회하고, 가변 분기점에서 로우 비트마스크를 분할하며, 빈 서브트리는 건너뜁니다. 학습 과정은 변경되지 않습니다: TreeWalker는 표준 LightGBM 및 XGBoost 모델을 읽습니다. 우리는 구조적 작업 분해(structural work decomposition)를 증명합니다: 트리당 작업은 상수 투영된 서브트리 크기 $|T_c|$, $G$개의 리프 쓰기, 그리고 술어 마스크 프로비저닝 비용 $Q$로 나뉩니다. 트레이스 평가기(trace evaluator)의 경우, 로우당 작업량은 $G o ext{무한대}$일 때 로우 독립적 순회 작업량의 $(d_v+1)/(d+1)$ 비율에 근접합니다. Intel 환경에서 TreeWalker는 참조 구성($T=500$, $L=8$) 대비 로우 독립적 순회보다 2.53.2배 빠르며, 생존 데이터셋에서 $G=128$일 때 6.87.8배 빠르고, Arm 환경에서는 더 큰 성능 향상을 보입니다. 시나리오 분석 벤치마크에서는 두 아키텍처 모두에서 16개 구성 모두에서 더 빠른 속도를 보여줍니다. f64 모델의 경우, 출력값은 합산 순서까지 treelite의 GTIL과 일치하며; f32 모델의 경우, f64 누적값은 99.98%의 로우에서 네이티브 f32보다 Kahan 보정 참조값에 더 가깝고, 절대 멀어지지 않습니다.