arXiv:2610.13382v1 cs.LG

BLOKS: 스케치된 블록 전처리를 통한 커널 솔버의 스케일링

BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning

Giordano Vitale, Giacomo Meanti, Marco Rando, Blanca Ayuso de Dios, Lorenzo Rosasco

제출 2026-10-09

저자 비고

arXiv Comments

29 pages, 7 figures, 9 tables

한국어 초록

커널 리지 회귀(Kernel Ridge Regression, KRR)는 비매개변수적 학습(nonparametric learning)을 위한 이론적으로 타당한 알고리즘이며, 심층 학습(deep learning)의 특성을 연구하는 데에도 자주 사용된다. 그러나 정확한(exact) KRR 수식은 대규모 데이터셋(dataset)에 적용할 수 없을 정도의 시간 및 메모리 비용을 발생시키며, 이는 근사 솔버(approximate solver) 개발의 동기가 되었다. 이러한 알고리즘들은 (i) 직접적인 해법의 계산 부담을 피하기 위한 반복적 방법(iterative method), (ii) 문제 크기를 줄이기 위한 스케칭(sketching) 또는 배치화(batching), (iii) 수렴(convergence)을 가속화하기 위한 전처리(preconditioning)에 의존한다. 빠른 수렴을 위해 필수적이지만, 전처리는 메모리 비용을 발생시키며, 이는 모델(model)의 자유 매개변수 수를 줄임으로써 관리할 수 있으나 그 대가로 표현력, 나아가 정확도가 저하될 수 있다. 이러한 문제를 해결하기 위해, 우리는 블록 자코비(Jacobi) 근사와 스케칭을 결합한 새로운 프리컨디셔너(preconditioner)를 중심으로 구축된, Nyström 방식으로 스케치된 KRR을 위한 컨주게이트 그래디언트(Conjugate Gradient) 기반 솔버인 BLOKS를 제안한다. BLOKS의 프리컨디셔너는 데이터셋 크기와 매개변수 수 모두와 무관한 메모리 비용을 가지므로, 대규모 모델로의 스케일링(scaling)이 가능하다. 우리는 메모리 효율적이고 GPU로 가속화된 구현을 제공하며, BLOKS가 우수한 시간/메모리 복잡도를 유지하면서도 뛰어난 정확도를 달성함을 보인다. 실제로, 커널 솔버를 벤치마킹(benchmark)하는 데 사용되는 표준 대규모 데이터셋에서 BLOKS는 최신(state-of-the-art) 기법들과 비교할 만하거나 그보다 더 나은 성능을 달성한다.

원문 초록

Kernel Ridge Regression (KRR) is a theoretically sound algorithm for nonparametric learning, which is also often used to investigate properties of deep learning. However, the exact KRR formulation incurs time and memory costs preventing applicability to large datasets, motivating the development of approximate solvers. These algorithms rely on (i) iterative methods, to avoid the computational burden of direct solutions; (ii) sketching or batching, to reduce the problem size; and (iii) preconditioning, to accelerate convergence. While crucial for fast convergence, preconditioning incurs memory costs that can be managed by lowering the number of free parameters of the model, potentially at the expense of expressivity and hence accuracy. To address this challenge, we propose BLOKS, a Conjugate Gradient-based solver for Nyström-sketched KRR built around a novel preconditioner that combines a block Jacobi approximation with sketching. The BLOKS preconditioner has memory cost independent of both the dataset size and the number of parameters, allowing scaling to large models. We provide a memory-efficient, GPU-accelerated implementation and show that BLOKS achieves excellent accuracy while retaining favorable time/memory complexity. Indeed, on standard large-scale datasets used to benchmark kernel solvers, BLOKS achieves comparable or better performances than state-of-the-art methods.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2610.13382v1

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.15965v1cs.LG공통 태그 GPU, Computational Efficiency

반복 데이터 사전학습 스케일링: 배치 크기, 정규화 및 GPU-시간 트레이드오프

Scaling Repeated-Data Pretraining: Batch Size, Regularization, and GPU-Time Tradeoffs

본 연구에서는 연산량은 풍부하지만 고유한 학습(training) 데이터가 유한하여 동일한 데이터에 대한 반복 학습이 필요한 환경에서의 사전학습(pre-training)을 다룹니다. 먼저 무한 연산량 사전학습(Kim et al. 2026)을 재검토하여, 그 프론티어가 기존에 고정되었거나 개별적으로만 연구되었던 선택 사항들에 결정적으로 의존함을 보입니다. 특히 에포크(epoch) 수와 함께 배치(batch) 크기를 최적화하면 검증 손실(validation loss)과 배치 크기 사이에 U자형 관계가 나타나 일반적인 사전학습보다 더 작은 배치를 선호하게 됨을 밝히며, 이는 소배치 그래디언트(gradient) 노이즈가 암묵적 정규화(implicit regularization)를 제공하기 때문인 것으로 보입니다. 나아가 기존에 단일 패스 가정 하에서 최적화되었던 학습 레시피를 조정할 수 있음을 확인했습니다. 예를 들어 에포크마다 문서를 새로운 시퀀스로 재패킹하는 것, 가중치 공유(weight tying), 그리고 양의 임베딩 가중치 감쇠(positive embedding weight decay) 등이 있습니다. 이후 무한 연산량 가정을 완화합니다. 특히 일반적인 경우보다 작은 배치 크기는 지나치게 긴 순차적 학습 시간을 요구할 수 있으므로, GPU와 시간을 별개의 자원으로 다루어야 할 필요성이 발생합니다. 마감 기한이 촉박할수록 더 큰 배치가 유리하며, 지연 시간 중심의 병렬 처리를 통해 추가 GPU를 투입하여 학습 시간을 단축할 수 있습니다. 그럼에도 불구하고 고정된 시간 예산 내에서도 더 적은 수의 GPU와 작은 배치를 사용하는 것이 더 많은 GPU와 큰 배치를 사용하는 것보다 더 낮은 검증 손실을 달성할 수 있으며, 이는 마감 기한 내에서 GPU 활용도를 극대화하기 위해 데이터 병렬 처리를 늘리는 일반적인 관행에 도전합니다. 종합적으로 본 연구 결과는 반복 데이터 학습에서 충분히 탐구되지 않았던 요인들을 식별하고, 단일 패스 사전학습 대비 학습 레시피와 자원 할당이 어떻게 변화해야 하는지에 대한 구체적인 지침을 제공합니다.

arXiv:2610.13708v1cs.AI공통 태그 GPU, Computational Efficiency

Adaptive DHiSparse: 부하 적응형(Load-Adaptive) KV 계층 구조에서의 추측 디코딩(Speculative Decoding)

Adaptive DHiSparse: Speculative Decoding over a Load-Adaptive KV Hierarchy

롱 컨텍스트(long-context) 서빙은 하드웨어가 유효 처리량(throughput)에 도달하기 전에 KV 메모리가 먼저 소진된다. HiSparse는 히스토리를 호스트 메모리에 저장하고 선택된 항목만 가져오지만, 모든 로드(load)에서 단일 캐시 예산(budget)을 사용하며 DSpark 및 DFlash2와 같은 드래프트 모델(draft-model) 추측 디코딩(speculative decoding)을 처리하지 못한다. 우리는 계층적 희소(hierarchical sparse) KV 위에서 추측 디코딩을 지원하고 상주(residency)를 부하(load)에 맞춰 적응시키는 Adaptive DHiSparse를 제시한다. 이 방법은 필요한 작업 집합(working set)을 보호하고, GPU 메모리가 여유 있을 때 추가 히스토리를 유지하며, 나머지는 정확한 융합 검색(fused retrieval)을 통해 복구한다. DSpark와 DFlash2는 각자의 제안(proposal) 및 수락(acceptance) 규칙을 그대로 유지한다: 쿼리는 누락된 행(missing-row) 검색을 공유하고, 드래프트 KV는 윈도우 경계(window-bounded) 링을 사용하며, 검증(verification) 스테이징은 층(layer) 그룹 간에 재사용된다. 100K 컨텍스트와 동시성(concurrency) 128에서, DFlash2를 사용한 GLM-5.3은 디코드 GPU당 793 출력 토큰(token)/s를 달성하며, 이는 HiSparse의 1.45배, 추측 디코딩을 사용하지 않는 적응형 서빙의 1.27배이다. HiSparse와 동일한 지연 시간(latency) 한계를 유지할 때, 이 방법은 동시성을 최대 4배까지, 출력을 토큰당 한계에 따라 2.3배에서 3.7배까지 유지한다. 500K 컨텍스트와 동시성 512에서 DeepSeek-V4.1-Flash에 대해, DSpark를 사용한 Adaptive DHiSparse는 DSpark를 사용한 상주(resident) 서빙의 출력보다 1.85배 높은 출력을 달성한다. 로드 단계(load step)에서, 선택적 상주(residency)는 저부하 상황에서 호스트 페치(fetch) 비율을 선택된 행의 14.2%에서 1.4%로 줄이고, 압박(pressure) 상황에서는 메모리를 해제한다.

arXiv:2610.10845v1cs.CL공통 태그 GPU, Computational Efficiency

AI를 위한 진정한 장기 기억: 재계산보다 더 빠르고 저렴한 5,000만 토큰 윈도우

Real Long-Term Memory for AI: A 50-Million-Token Window That Is Faster and Cheaper Than Recompute

대규모 언어 모델(LLM)은 컨텍스트 윈도우에 들어가는 텍스트만 사용할 수 있으며, 프롬프트가 전송될 때마다 해당 프롬프트에 대한 내부 키-값(KV) 상태를 다시 계산합니다. 본 연구에서는 약 16,000개 토큰 블록의 KV 상태를 암호화된 로컬 NVMe 디스크에 저장하고, 이후 재계산 없이 바이트 단위로 정확하게(byte-exact) 다시 로드하는 메모리 층인 공개 패키지 galahad-kv를 테스트합니다. 단일 NVIDIA H100에서 vLLM을 통해 서빙되는 50,000,000개 토큰의 실제 공개 텍스트를 대상으로 Gemma 4 12B 및 Gemma 4 31B와 함께 이를 실행했습니다. 조사한 모든 블록은 두 모델 모두에서 재계산 없이 암호화된 저장소로부터 다시 로드되었습니다(0부터 5,000만 토큰 깊이에서 100회 중 100회). 블록을 로드하는 것은 재계산하는 것보다 2.8배에서 4.3배 더 빨랐고 GPU 에너지를 8.8배에서 12.3배 적게 사용했으며, 전체 5,000만 토큰 스트림 동안 GPU 메모리는 일정하게 유지되었습니다. 수백만 토큰 앞서 심어둔 사실에 대한 질문에서 12B 모델은 100회 중 82회, 31B 모델은 100회 중 98회 올바른 답변을 제시했습니다. 두 모델 모두 답을 지어내지 않았습니다. 한계점은 다음과 같습니다. 이는 더 넓은 어텐션 윈도우가 아니라 저장된 상태를 재사용하는 것입니다. 즉, 한 번에 하나의 블록이 로드되며, 질문에 얼마나 잘 답하는지는 모델에 달려 있습니다. 메모리 쓰기는 일회성 비용이며 저장소는 수 테라바이트의 로컬 NVMe 디스크를 차지합니다. 본 논문에서는 롱 컨텍스트 벤치마크를 왜곡하는 일반적인 방식에 대응하도록 설계된 테스트 프로토콜을 설명하고, 공개 소프트웨어 및 해당 패키지의 무료 라이선스를 활용하는 단일 GPU 재현 방안을 제공합니다.

arXiv:2610.10924v1cs.AR공통 태그 GPU, Computational Efficiency

에뮬레이션 텐서-메모리 평형(TME) 모델에서 누락된 네 번째 항: 잔차 분해 비용

The Missing Fourth Term for the Emulation Tensor Memory Equilibrium (TME) Model: The Residue Deconstruction Cost

"FP8 is All You Need (Part 1)"의 텐서-메모리 평형(Tensor-Memory Equilibrium, TME) 모델은 fp64에 대한 Ozaki Scheme II 에뮬레이션의 실행 시간을 텐서 코어 항과 고대역폭 메모리(HBM) 트래픽 항 중 더 큰 값에 출력당 재구성(reconstruction) 항을 더한 값으로 계산한다. 그러나 이 모델은 입력당 분해(deconstruction) 비용을 누락하고 있다: 스트리밍되는 모든 fp64 피연산자는 행렬 곱셈이 실행되기 전에 SIMT 파이프에서 스케일링, 라운딩, 그리고 $r$개의 모듈러스(moduli) 각각에 대한 모듈로 축소(modulo reduction)를 거쳐야 한다. 이 노트에서는 이 네 번째 항을 추가하고, cuBLAS 에뮬레이션 경로로부터 그 상수를 보정(calibrate)하며, 텐서 코어 처리량과 무관하게 에뮬레이션이 네이티브 fp64 성능에 도달할 수 없는 연산 강도(operational intensity) 임계값을 $\mathrm{OI}^{*} = c_q r P_{\mathrm{fp64}}/(8P_{\mathrm{int}})$라는 닫힌 형태(closed-form)로 도출한다. NVIDIA B300 GPU에서 이 임계값은 $\mathrm{OI}^{*}\approx 0.56$ FLOP/B이다. 그 결과, 원 논문이 가속 대상으로 주장하는 메모리 바운드 커널인 GEMV, SpMV, 그리고 저배치(low-batch) GEMV는 네이티브 성능의 0.3~0.9배로 제한되며, 7점 스텐실(stencil)은 주장된 3.1배가 아닌 1.8배에 그친다. 예상대로 밀집(dense) GEMM은 영향을 받지 않는다. 또한 우리는 잔차(residue)를 미리 계산하여 저장하는 방식이 동일한 비용을 대역폭 항으로 이전시킨다는 것을 보이며, 이 경계(bound)를 무효화하기 위해 구현이 달성해야 하는 명령어 수(instruction count)를 제시한다.

arXiv:2610.10959v1cs.CV공통 태그 GPU, Computational Efficiency

이미지 데이터의 위상학적 분석을 위한 지속성 호몰로지 연산의 GPU 가속화

GPU-Accelerated Computation of Persistent Homology for Topological Analysis of Image Data

최근 몇 년 동안 지속성 호몰로지(persistent homology)는 심층 학습(deep learning)에서 빠르게 도입되었으나, 그 연산 과정은 네트워크 학습(training)에서 여전히 주요한 병목점으로 남아 있습니다. 본 논문에서는 2D 및 3D 이미지로부터 유도된 큐비컬 복합체(cubical complex)의 지속성 다이어그램(persistence diagram)을 계산하는 GPU 스트리밍 파이프라인인 TopoGPU를 소개합니다. TopoGPU는 입력 이미지를 청크 단위로 스트리밍하여 GPU 블록 그리드 상의 대규모 병렬 GPU 커널로 각 청크를 처리하며, 그 결과로 얻어지는 경계 관계는 호스트 메모리에 누적되어 CPU가 경계 행렬 축약(boundary matrix reduction)을 수행합니다. TopoGPU는 스트리밍 환경에서도 지속성 호몰로지를 증명 가능하게 보존하는 계층화 인식 이산 모스 매칭(stratification-aware discrete Morse matching)을 도입하고, GPU 상에서 모스 경계를 도출하기 위한 병렬 위상 정렬 알고리즘 및 병렬 V-경로 패리티(V-path parity) 알고리즘을 함께 제안합니다. TopoGPU는 평가된 모든 벤치마크에서 지속성 호몰로지 계산의 최신 기법인 Cubical Ripser를 능가하여 평균 53.24배, 최대 198.01배의 엔드투엔드 속도 향상을 달성했습니다. 나아가 TopoGPU를 위상 보존 딥 네트워크에 통합하여, 네트워크 학습 중 지속성 호몰로지 연산 비용을 대폭 줄일 수 있음을 입증했습니다. TopoGPU는 오픈 소스로 제공되며, 사전 빌드된 바이너리, Google Colab 노트북 및 Docker 이미지는 프로젝트 GitHub 페이지(https://github.com/seravee08/GPU-Computation-of-Persistent-Homology-for-Image-Data)에서 이용할 수 있습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.