Fast Exact Nearest-Neighbor Learning for High-Frequency Financial Time Series

기술 요약: 고빈도 금융 시계열을 위한 고속 정밀 최근접 이웃 학습

문제 정의
금융 AI는 실시간 트레이딩, 리스크 관리 및 파생상품 가격 결정을 지원하기 위해 방대한 역사적 코퍼스(주식, ETF, FX, 옵션)를 흡수해야 하는 스케일링 시대에 진입하고 있습니다. 현재의 스택에는 핵심적인 병목 현상이 존재합니다. Python 기반 도구(NumPy, scikit-learn)는 유연성을 제공하지만, 인터프리터 오버헤드, 메모리 대역폭 포화, 그리고 수십만 개의 과거 상태를 쿼리할 때 발생하는 열악한 캐시 지역성(cache locality) 문제로 인해 어려움을 겪습니다. 반대로, C++ 및 FPGA 솔루션은 속도는 빠르지만, 별도의 코드베이스와 수동 최적화가 필요하기 때문에 "연구에서 프로덕션으로의 전환(research-to-production)" 과정에서 간극을 만듭니다. 본 연구가 다루는 구체적인 과제는 고빈도 시계열에 대한 정밀 최근접 이웃(exact nearest-neighbor, KNN) 추론입니다. 여기서 브루트 포스(brute-force) 탐색의 선형 비용($O(n \cdot d)$)은 실시간 레이턴시 예산 내에서 실행하기에 너무 비싸며, 근사 방법(HNSW 등)은 특정 금융 애플리케이션에 요구되는 정밀성을 희생합니다.

방법론
저자들은 금융 시계열 코퍼스에 특화되어 설계된 Mojo SIMD k-d 트리를 제안합니다. Python과 호환되는 문법을 가진 컴파일형 시스템 언어인 Mojo는 사용자가 Python 생태계를 벗어나지 않으면서도 알고리즘, 메모리 레이 레이아웃, 하드웨어를 공동 설계(co-design)할 수 있게 해줍니다. 방법론은 세 가지 핵심 최적화를 통합합니다:

1. 분산 기반 분할(Variance-Based Splitting): 표준 중앙값 기반 분할과 달리, 이 트리는 최대 분산($j^* = \arg\max \text{Var}(\{x_{i,j}\})$)을 가진 차원을 기준으로 분할 축을 선택합니다. 이는 가장 변별력이 높은 금융 특징(수익률, 변동성, 모멘텀)에 조기 가지치기(pruning)를 집중시켜 더 타이트한 서브리전(subregion)을 생성합니다.
2. 연속적 플랫 버퍼 저장(Contiguous Flat-Buffer Storage): 훈련 벡터는 치환된 배열에 의해 인덱싱된 행 우선(row-major) 플랫 버퍼($X \in \mathbb{R}^{n \times d}$)에 저장됩니다. 리프 노드는 정수 오프셋으로 정의되어, 후보군을 연속적인 메모리 블록으로 읽을 수 있게 합니다. 이를 통해 포인터 체이싱(pointer-chasing) 오버헤드를 제거하고 캐시 라인 정렬을 보장합니다.
3. 컴파일 타임 벡터화 커널(Compile-Time Vectorized Kernels): 거리 계산은 SIMD(Single Instruction, Multiple Data) 벡터화를 활용합니다. 커널은 특정 차원(예: $d=16$ 또는 $d=24$) 및 SIMD 폭에 맞춰 컴파일 타임(comptime)에 특화되어, 완전히 언롤링(unrolled)된 스칼라 프리(scalar-free) 코드를 생성합니다. 제곱 유클리드 거리는 병렬 레지스터 폭 블록으로 분해됩니다.

본 시스템은 두 가지 하드웨어 아키텍처(x86: Intel/AMD, ARM64: Apple M3)에서 8개의 금융 데이터셋(미국 주식, ETF, FX)을 대상으로 평가되었습니다. 비교 대상은 scikit-learn의 브루트 포스 및 k-d 트리 구현, 그리고 Mojo 자체의 SIMD 브루트 포스 방식입니다.

핵심 기여

1. Mojo SIMD k-d 트리 구현: 분산 기반 가지치기, 플랫 버퍼 메모리 레이아웃, 컴파일 타임 벡터화 거리 커널을 결합하여 대규모 금융 데이터셋에 대한 정밀 KNN을 수행하는 새로운 구현체입니다.
2. 이론적 런타임 분석: 표준 가지치기 가정하에서, Mojo k-d 트리가 고정된 주식 종목, 대규모 $n$, 중간 차원 환경에서 Mojo SIMD 브루트 포스 및 scikit-learn의 k-d 트리보다 점근적으로 우위에 있음을 입증하는 증명을 제시합니다.
3. 금융-하드웨어 공동 설계: OHLCV 유도 특징들이 SIMD 폭(16 및 24 float32 값이 각각 2개 및 3개의 레지스터 폭에 매핑됨)과 일치하도록 하는 표준화된 피처 엔지니어링 접근 방식을 통해, 금융적 해석력을 유지하면서 처리량을 극대화합니다.
4. 실증적 검증: 다양한 자산 클래스와 하드웨어 플랫폼에 걸친 종합적인 벤치마크를 통해 통계적 유의성(Wilcoxon signed-rank test로 확인)을 갖춘 속도 향상을 보여줍니다.
5. 확장성 입증: Extra Trees를 이용한 내재 변동성(implied-volatility) 가격 결정 실험을 통해, 처리량 이득이 10배 더 많은 데이터 학습을 가능하게 하여 예측 정확도를 직접적으로 개선함을 보여줍니다.

결과

• x86 ($d=16$)에서의 속도 향상: Mojo k-d 트리는 143K에서 277K 샘플 범위의 데이터셋에 대해 scikit-learn의 k-d 트리 대비 17.5–21.6배, scikit-learn의 브루트 포스 대비 1.2–1.3배의 속도 향상을 달old했습니다.
• ARM64 ($d=24$)에서의 속도 향상: 이 방법은 Apple M3에서 scikit-learn의 브루트 포스 대비 28.1–43.5배의 속도 향상을 달성했습니다. 특히 ARM64에서 Mojo SIMD 브루트 포스 커널은 컴파일 타임 SIMD 폭(x86 256비트 레지스터에 최적화됨)과 네이티브 128비트 ARM 레지스터 간의 불일치로 인해 k-d 트리보다 780–1549배 느렸습니다. 그러나 k-d 트리의 알고리즘적 가지치기($O(n^{1-1/d})$)는 이러한 하드웨어 특화 페널티로부터 자유로워 압도적인 이득을 유지했습니다.
• 스케일링 지수: 런타임 복잡도 $T(n) = Cn^\alpha$의 경험적 피팅 결과, Mojo k-d 트리(쿼리 전용)의 지수는 1.755였으며, 이는 브루트 포스의 1.885, scikit-learn k-d 트리의 2.320과 대조됩니다. 이는 데이터셋 크기가 커질수록 격차가 벌어지는 부적정 이차(sub-quadratic) 스케일링을 확인시켜 줍니다.
• 예측 품질: Extra Trees 실험에서 200,000개의 샘플로 학습했을 때(Python 베이스라인 한계의 10배), 풋 옵션 내재 변동성(IV) RMSE가 8.0%(0.361에서 0.333으로) 감소했습니다. 콜과 풋을 분리하여 학습했을 때는 RMSE가 27–31% 더 감소했습니다.
• 통계적 유의성: Wilcoxon signed-rank test 결과, Mojo k-d 트리가 8개 데이터셋 모두에서 scikit-learn의 k-d 트리보다 엄격하게 빠름을 확인했습니다 ($p < 0.01$). 기하 평균 속도 향상은 10.8배였습니다 (95% CI: [5.94$\times$, 16.62$\times$]).

의의 및 주장
본 논문은 최초의 오픈 소스이자 Python 호환이 가능한 시스템 레벨의 금융 AI 추론 효율성 연구라고 주장합니다. 주요 의의는 알고리즘, 메모리 레이아웃, 하드웨어, 그리고 언어 간의 공동 설계가 정밀성을 희생하거나 Python 호환성을 깨뜨리지 않고도 운영 가능한 수준의 가속을 이끌어낼 수 있음을 입증했다는 데 있습니다.

저자들은 Mojo가 Python 연구의 유연성과 C++ 프로덕션 시스템의 성능 사이의 간극을 메운다고 주장합니다. 단일 코드베이스로 최적화된 C++ 속도의 약 60%에 도달하는 동시에 표준 Python 라이브러리보다 10배 빠른 성능을 구현함으로써, Mojo를 확장 가능하고 프로덕션 준비가 된 금융 AI 스택으로 포지셔ning 합니다. 결과에 따르면 금융 데이터가 틱(tick) 단위 규모로 증가함에 따라, 이 접근 방식의 부적정 이차 스케일링은 실시간 레이턴시 제약을 유지하는 데 있어 점점 더 중요해질 것입니다. 또한 이러한 원칙은 유전학이나 사이버 보안과 같이 정밀한 최근접 이웃 검색을 필요로 하는 다른 데이터 집약적 분야에도 적용 가능하다고 주장합니다.