Prof-K: 효율적인 Top-k 선택을 위한 확률론적 단일 패스 필터링
Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection
한국어 초록
Top-k 선택은 데이터베이스, 정보 검색, 신호 처리뿐만 아니라 희소 활성화 및 어텐션(attention) 가지치기(pruning)를 포함한 현대 머신러닝 워크로드 전반에 활용되는 핵심적인 기본 연산(computational primitive)입니다. 데이터 규모가 커짐에 따라 기존 접근법은 비효율적이 됩니다. 정확한(exact) 방식은 높은 메모리 및 연산 오버헤드를 유발하며, 근사(approximate) 방식은 취약한 휴리스틱에 의존하는 경우가 많아 적대적이거나 두터운 꼬리(heavy-tailed) 분포를 갖는 입력에서 성능이 저하됩니다. 본 논문에서는 정확한 Top-k 선택을 위한 빠르고 확장 가능하며 분포에 구애받지 않는(distribution-agnostic) 알고리즘인 Prof-K를 소개합니다. Prof-K는 단일 패스 필터링 절차를 수행합니다. 즉, 작은 무작위 표본을 통해 적응형 임계값을 추정한 후, N개의 입력 요소를 컴팩트한 버퍼로 한 번 스트리밍하며, 이 버퍼에 대해 정확한 Top-k 루틴을 수행하여 사용자가 지정한 $\varepsilon>0$에 대해 최소 $1-\varepsilon$의 확률로 첫 번째 시도에서 실제 Top-k 요소를 복원합니다. 본 연구는 N과 k의 함수로서 오버헤드를 최소화하는 대략적으로 최적화된 표본 크기와 함께, 정확도 및 버퍼 크기에 대한 높은 확률 보장(high-probability guarantees)을 도출합니다. 실증적으로 Prof-K는 고도로 최적화된 PyTorch topk 및 최근의 RadiK 구현 대비 1.5배~15배의 속도 향상을 달성하며, 기존 방법들이 가장 취약했던 대규모이면서 작거나 중간 크기의 k 영역에서 가장 큰 성능 향상을 보입니다. 이전 접근법과 달리 이러한 보장은 입력 분포와 무관하게 유지되므로 적대적 설정에 대한 견고성을 보장합니다. 런타임 검사를 통해 드물게 발생하는 실패를 감지하고 재시도를 트리거하므로, 반환되는 집합은 항상 정확하며 $\varepsilon$은 추가 패스가 필요할 확률만을 제한합니다. 나아가 Top-k 선택이 학습 비용의 상당 부분을 차지하는 BatchTopK 희소 오토인코더(SAE) 학습(training)에서 Prof-K의 효과를 입증합니다.
원문 초록
Top-k selection is a fundamental computational primitive with applications spanning databases, information retrieval, signal processing, and modern machine learning workloads, including sparse activations and attention pruning. As data sizes grow, existing approaches become inefficient: exact methods incur high memory and compute overhead, while approximate methods often rely on brittle heuristics that degrade under adversarial or heavy-tailed inputs. In this paper, we introduce Prof-K, a fast, scalable, and distribution-agnostic algorithm for exact top-k selection. Prof-K performs a single-pass filtering procedure: a small random sample estimates an adaptive threshold, the N input elements are streamed once into a compact buffer, and an exact top-k routine on this buffer recovers the true top-k elements on the first attempt with probability at least $1-\varepsilon$, where $\varepsilon>0$ is user specified. We derive high-probability guarantees for correctness and buffer size, together with an approximately optimal sample size that minimizes overhead as a function of N and k. Empirically, Prof-K achieves 1.5x-15x speedups over the highly optimized PyTorch topk and recent RadiK implementations, with the largest gains in the large-scale, small-to-moderate-k regime where prior methods struggle most. Unlike previous approaches, these guarantees hold independently of the input distribution, ensuring robustness to adversarial settings. A run-time check detects the rare failures and triggers a retry, so the returned set is always exact and $\varepsilon$ bounds only the probability of requiring an additional pass. We further demonstrate its impact on training BatchTopK Sparse Autoencoders (SAEs), where top-k selection constitutes a significant portion of the training cost.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2608.12573v2
- arXiv:2608.12573v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
PACE-dLLM: 확산 언어 모델을 위한 신뢰도 절벽 추정 기반 탄력적 블록 디코딩
PACE-dLLM: Elastic Block Decoding via Confidence Cliff Estimation for Diffusion Language Models
정교한 축출 정책이 실패할 때: LLM 접두 문맥 재사용을 위한 캐시 교체 정책의 재고
When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse
KDFP: 대규모 언어 모델의 지식 증류를 위한 제1원리적 접근법
KDFP: A first-principles approach to knowledge distillation in large language models
지식 증류(knowledge distillation)는 더 크고 성능이 뛰어난 교사 모델의 표현(representation)을 활용해 작고 효율적인 학생 모델을 학습(training)시킴으로써 그 역량을 향상시키는 잘 정립된 기법입니다. 대규모 언어 모델(LLM) 증류에 관한 최근 연구의 상당수는 지시사항 준수(instruction following), 사고의 연쇄(Chain-of-Thought) 추론, 도구 사용 등 사후 학습(post-training) 과정에서 습득된 능력을 증류하는 데 집중되어 왔습니다. 이로 인해 엣지 기기 배포에 적합한 효율적이고 프라이버시가 보장되는 시스템을 개발하는 데 필수적인 LLM의 일반 지식 증류 연구에는 큰 공백이 남게 되었습니다. 본 연구에서는 이전 연구들의 교훈을 평가하고 새로운 탐색을 수행하는 제1원리적(first-principles) 접근법을 취하여 현대 LLM에 적합한 증류 방법론을 개발합니다. 본 논문에서는 LLM의 화이트박스 일반 지식 증류를 위한 새로운 방법론인 KDFP를 제시합니다. 실험을 통해 KDFP가 임시 매개변수(parameter) 감축을 통해 학습 효율성을 최대 99.1%까지 향상시키면서, 9개 벤치마크 전반에서 기존 기법들을 1.6% $-$ 4.9% 능가함을 입증합니다.
SLICEChat: 전슬라이드 병리 언어 모델을 위한 점진적 인코더 내 토큰 가지치기
SLICEChat: Progressive In-Encoder Token Pruning for Whole-Slide Pathology Language Models
전슬라이드 병리 이미지(WSI)는 기가픽셀 규모의 시각 정보를 담고 있어, 슬라이드 수준 멀티모달 대규모 언어 모델(MLLM)의 확장성에 큰 난제를 만든다. 기존 접근은 수천 개의 패치 토큰을 처리하고, 보통 슬라이드 인코딩 이후에만 압축을 적용하여 멀티모달 어텐션이 계산적으로 비싸게 남는다. 우리는 하이브리드 Mamba–트랜스포머 슬라이드 인코더 안에 점진적 토큰 가지치기를 통합한 슬라이드 수준 MLLM인 SLICEChat을 제안한다. Mamba 레이어는 효율적인 장거리 전파를 가능하게 하고, 트랜스포머 레이어는 시퀀스가 점진적으로 짧아지는 동안 전역 상호작용을 유지한다. 단계 사이에서는 언어 지도 하의 영역 인식 가지치기가 제어된 유지율(keep-rate) 스케줄 하에서 공간적으로 일관된 저유용 영역을 제거하여, 멀티모달 융합 전에 압축된 슬라이드 표현을 만든다. SlideBench VQA에서 SLICEChat은 TCGA에서 79.84%, BCNB 코호트에서 59.09% 정확도를 달성해 기존 슬라이드 수준 병리 MLLM을 능가했으며, WSI-Bench 전체 지표에서도 최고 성능을 기록했다. 또한 평가된 모델 중 경쟁력 있는 메모리 사용량과 추론 지연 시간을 보였다. 이 결과는 기가픽셀 WSI에 대한 정확하고 계산적으로 효율적인 멀티모달 추론을 보여 준다.
에이전시 총비용: 멀티 에이전트 LLM 워크플로에서 메모리 주입 비용의 정확한 귀속
Total Cost of Agency: Exact Attribution of Memory Injection Cost in Multi-Agent LLM Workflows
멀티 에이전트 대규모 언어 모델(LLM) 워크플로의 모든 노드는 메모리에서 컨텍스트를 검색하여 프롬프트에 주입하며, 주입된 토큰은 시스템 프롬프트와 사용자 쿼리와 동일한 토큰당 단가로 입력 토큰으로 청구된다. 프로덕션 관측(observability) 도구는 총 토큰 비용을 보고하지만 노드가 생성하는 토큰과 전달받은 토큰을 구분하지 않으므로, 청구서의 이 항목은 비용을 지불하는 팀에게는 보이지 않는다. 우리는 멀티 에이전트 워크플로 비용을 기본 프롬프트, 추론, 메모리 주입, 미스 페널티, 컨텍스트 누적 구성요소로 분해한 Total Cost of Agency(TCA)와, 단어 수 프록시로 추정하지 않고 주입 토큰을 직접 측정하는 2-pass 비청구 토큰 카운트 기반의 정확한 귀속 방법을 제안한다. 실제 모델 API에 대해 실행한 200개 태스크 기업 벤치마크에서 메모리 주입은 컴파일 타임 옵티마이저가 개입할 수 있는 가변 비용의 13.6%, 전체 청구 비용의 약 12%를 차지하며, 워크플로 깊이 1에서의 구조적 0에서 깊이 6에서 27.6%까지 그 비중이 증가한다. 측정 구간(깊이 2~6)에서 주입 토큰은 깊이에 대해 선형적으로 증가한다(R^2 = 0.9974); 2차 피팅의 leading coefficient가 음수이므로, 해당 깊이에서 데이터는 볼록(convex) 성장을 보이지 않는다. 고정된 모델 tier에서 이 구성요소가 제어 가능함을 보인다: 검색 윈도우 용량을 32개 항목에서 2개로 줄이면 주입 토큰이 28.7% 감소하고 정확도 변화는 시드(seed) 수준 변동 범위 내이다. 그래프 재작성(graph-rewriting) 변환이 단독으로는 대체로 비용 중립적임을, 다섯 분해 항 중 두 항이 이 하네스(harness)에서 구조적으로 0임을, 총 워크플로 비용이 모델 tier 할당에 의해 지배되며 이를 고정하고 선행 연구로 취급함을 전면 보고한다. 프롬프트 캐싱(prompt caching)은 평가하지 않았으며 모든 수치는 캐시 미사용(uncached) 경우에 대한 것이다.
LazyAgent: 수요 기반 구체화 및 에이전트 프로그램의 물리적 최적화
LazyAgent: Demand-Driven Materialization and Physical Optimization of Agentic Programs
토론
이 논문과 연결된 포럼 글이 아직 없습니다.