arXiv:2606.03946v2 cs.DB

MLSkip: 경량 메타데이터를 통한 ML 필터용 데이터 스킵핑

MLSkip: Data Skipping for ML Filters via Lightweight Metadata

Mihail Stoian, Mark Gerarts, Pascal Ginter, Andreas Zimmerer, Jan Van den Bussche, Andreas Kipf

제출 2026-09-24

한국어 초록

데이터베이스 벤더들이 최근 필터 predicate에서 사용할 수 있는 AI 함수를 출시했다. 이러한 함수는 종종 비용이 큰 블랙박스 ML 모델에 의존하므로 새로운 데이터 관리 과제를 드러낸다. 구체적으로, 정수 및 문자열 데이터에 대한 기존 데이터 스킵핑 기법은 새로운 필터 유형에는 적용되지 못한다. 실제로 blob storage에서 파일을 읽을 때와 같이, 조건을 만족하지 않는 row group을 가지치기할 알려진 메커니즘이 없다. 본 연구에서는 ML 필터를 위한 데이터 스킵핑 기법 연구를 시작한다. Parquet의 기본 min-max 메타데이터만으로도 가지치기를 가능하게 하기에 충분하다고 주장한다. 이를 위해 (i) 최근 제안된 ML 모델용 쿼리 언어와 (ii) 신경망 검증이라는 두 연구 계열과의 연관을 맺는다. 렐루 아키텍처에 대한 예비 결과는 TPC-H 및 TPC-DS의 테이블에서 선택도가 0.1% 미만인 필터에 대해 평균 가지치기 효과가 27.4%에 달함을 보여준다. 마지막으로 공간 조인 연구에서 영감을 받아 향상된 메타데이터 구조, 즉 검증 도구가 더 잘 활용할 수 있는 크기 제한 2D 볼록 껍질(convex hull)을 제안하며, row group 및 column pair당 최대 45바이트만 차지하면서 가지치기 효과를 38.31%로 높인다. DuckDB에서 PyTorch 대비 end-to-end 속도 향상 1.07$\times$를 관측한다.

원문 초록

Database vendors recently released AI functions that can be used in filter predicates. As such functions often rely on costly, black-box ML models, they unveil new data management challenges. Concretely, traditional data skipping techniques for integer and string data fail to be applicable to the new filter type. Indeed, there is no known mechanism for pruning non-qualifying row groups, e.g., when reading files from blob storage. In this work, we initiate the study of data skipping techniques for ML filters. We make the case that Parquet's default min-max metadata is enough to enable pruning. To this end, we draw connections to two lines of research: (i) the recently proposed query language for ML models and (ii) neural network verification. Our preliminary results on ReLU architectures show that on tables from TPC-H and TPC-DS, the average pruning effectiveness for filters of selectivity below 0.1% amounts to 27.4%. Finally, inspired by research on spatial joins, we propose an enhanced metadata structure: a size-bounded 2D convex hull that verification tools can make better use of, increasing the pruning effectiveness to 38.31%, while occupying at most 45 bytes per row group and column pair. We observe an end-to-end speedup of 1.07$\times$ over PyTorch in DuckDB.

제출 이력

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

  1. arXiv:2606.03946v2제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2610.08089v2cs.DB공통 태그 query optimization

실행 계획이 결과를 바꿀 때: 시맨틱 쿼리를 위한 비용-정확도 최적화 공식화

When Plans Change Answers: Formalizing Cost-Accuracy Optimization for Semantic Queries

시맨틱 쿼리 엔진에서는 머신러닝 모델을 통해 술어(predicate)가 평가되므로, 쿼리 실행 계획의 선택이 쿼리 비용뿐만 아니라 그 결과에도 영향을 미칩니다. 기존 시스템들은 조인을 거치며 오차가 어떻게 전파되는지 고려하지 않은 채, 각 시맨틱 연산자에 고정된 임계값을 적용하거나 연산자별로 정확도를 튜닝합니다. 본 논문에서는 이러한 쿼리에 대한 비용-정확도 최적화 문제를 공식적으로 정의합니다. 우리의 출발점은 Jev와 같은 의사결정 모델이 각 결정에 부여하는 보정된 신뢰도(calibrated confidence)입니다. 이는 모든 결정에 대한 기대 오차를 산출하며, 각 결정이 출력에 미치는 기여도(가장 단순한 경우 팬아웃(fan-out))로 이 오차들에 가중치를 부여하면 레이블이 지정된 데이터 없이도 계획의 기대 출력 품질을 얻을 수 있습니다. 또한 동일한 계산을 역으로 수행하면 출력 수준의 정확도 목표를 각 기본 튜플 또는 중간 튜플에 대한 비용으로 변환할 수 있습니다. 이를 바탕으로 우리는 시맨틱 연산자를 포함하는 관계 대수를 위한 오라클 의미론, 논리적 계획과 결정 정책의 쌍으로 이루어진 물리적 계획, 선언적 출력 수준 목표, 그리고 계획 동등성 계층 구조를 정의합니다. 우리는 점별 결정론적(pointwise-deterministic) 정책 하에서는 정확도가 계획에 불변함을 보이고, 승격 대역(escalation band)이 계획 자체의 후보군에 맞춰 보정될 때 셀렉션 푸시다운(selection pushdown)이 품질 건전성(quality-soundness)을 보장하지 않음을 보입니다. 기대 품질은 백 의미론(bag semantics) 하에서는 다항 시간에 계산될 수 있으며, 세트 의미론(set semantics) 하에서는 모든 릴레이션이 시맨틱 술어를 가질 때 튜플 독립적 확률적 데이터베이스의 이분법을 따릅니다. 어떤 튜플을 삭제할지 선택하는 것은 NP-난해인 반면, 최적화 문제는 두 개의 라그랑주 승수를 통해 튜플별 결정으로 분해되며, 우리가 신뢰도 중심 건너뛰기(confidence-centric skipping)라고 부르는 기법을 통해 목표에 더 이상 영향을 미치지 않는 튜플은 점수를 매기지 않고 건너뜁니다. 합성 워크로드에 대한 시뮬레이션은 이러한 효과들을 보여주며, 실제 엔진에서의 평가는 향후 과제로 남겨둡니다.

arXiv:2609.34457v2cs.LG공통 태그 neural network verification

ZonoGPT: 대규모 GPT 모델 검증을 위한 추상 도메인을 향하여

ZonoGPT: Towards An Abstract Domain for Verifying Large GPT Models

트랜스포머(Transformer) 기반 모델은 추론, 코딩 및 멀티모달 에이전트 작업에 널리 사용됩니다. 강건성(robustness), 안전성(safety), 공정성(fairness)과 같이 요구되는 동작에 대한 정형적 보장(formal assurance)을 제공하기 위해, 신경망(neural network) 검증 기법은 배포 전에 필수적인 속성을 증명하고 감사 가능한 보증을 제공합니다. 그러나 이전 연구는 소규모이거나 제한된 트랜스포머에 머물러 있으며, 심층 모델 전반에 걸쳐 정밀도(precision)를 유지하는 것은 여전히 어려운 과제입니다. 본 연구에서는 네트워크 깊이와 무관한 공간 복잡도를 유지하면서 대규모 트랜스포머를 검증하기 위한 추상 도메인인 ZonoGpt를 소개합니다. ZonoGpt는 구조화된 조노토프(zonotope)와 생성자 축소(generator reduction) 메커니즘을 사용하여 상관관계를 효율적으로 보존합니다. 정밀도를 유지하기 위해, 특징(feature) 관계를 보존하는 어텐션(Attention) 및 LayerNorm 전용 융합 변환과 함께, 생성자 관계를 보존하는 GELU용 아핀 변환(affine transform)을 도입합니다. 이러한 메커니즘을 통해 ZonoGpt는 표준 아키텍처를 검증하는 최초의 접근법이 되었으며, 최대 GPT-2 Medium(24개 블록, 3억 개 이상의 파라미터)에 달하는 공식 HuggingFace 모델로 확장하여 텍스트 및 비전 작업 전반에서 1,339개의 인스턴스를 성공적으로 검증했습니다.

arXiv:2609.34628v2cs.SE공통 태그 neural network verification

CLAD: 신경망 검증을 위한 제약 추상 도메인

CLAD: Constrained Abstract Domain for Neural Network Verification

신경망 검증(NNV)은 정의된 영역 내의 모든 입력에 대해 네트워크가 지정된 속성을 만족하는지 정형 검증합니다. 최신 NNV 도구는 추상 도메인(abstract domain)을 활용하여 주어진 입력 영역으로부터 네트워크 동작의 안전한 과근사(sound over-approximation)를 계산하므로, 이러한 추상화의 정밀도(tightness)가 효율성을 근본적으로 결정합니다. 점점 더 정밀해지는 일련의 도메인들이 개발되어 왔으나, 이들은 모두 유효한 입력 영역을 Lp-노름 볼(Lp-norm ball)과 같은 동일하게 제한적인 방식으로 기술합니다. 실제 환경의 입력 영역은 단순한 Lp 볼인 경우가 드물며, 오히려 추가적인 제약 조건이 결합된 Lp 볼 형태를 띱니다. 기존 추상화를 사용해 이러한 영역에서 신경망을 검증하면 느슨한 과근사가 생성되어, 속성 검증에 실패하거나 가짜 반례(spurious counterexample)가 발생하는 결과로 이어집니다. 본 논문에서는 볼록 제약(convex constraint)의 조합으로 정의된 입력 영역에서 신경망의 안전한 과근사를 계산하는 새로운 추상 도메인인 Constrained Lagrangian Abstract Domain(CLAD)을 소개합니다. CLAD는 이러한 제약 조건을 전파하고 실제 실현 가능한 영역에 대해 경계를 강화합니다. 그러나 이러한 제약 조건들의 교집합에서 뉴런의 경계를 구하는 것은 닫힌 형식의 해(closed-form solution)가 없기 때문에, CLAD는 라그랑주 승수(Lagrange multiplier)를 사용해 각 제약 조건을 목적 함수로 완화(relax)하고, 입력에 대한 투영 그래디언트 단계와 승수 업데이트를 번갈아 수행하는 사영 원쌍대(projected primal-dual) 방법으로 결과적인 맥스-민(max-min) 문제를 해결합니다. CLAD는 자동 미분 등을 통해 서브그래디언트(subgradient)를 갖는 모든 볼록 제약을 지원합니다. 저자들은 반공간(halfspace) 또는 L2-볼 제약이 있는 모션 블러 구조화 섭동(motion-blur structured perturbation)을 갖는 4개의 합성곱 신경망 전반에 걸친 1,944개 인스턴스에서 CLAD를 평가합니다. 표준 비제약 Linf 속성에서 CLAD는 유사한 실행 시간으로 GCPCROWN만큼 많은 인스턴스를 검증합니다. 제약된 속성에서 CLAD는 L2-볼 속성에서 GCPCROWN보다 60% 더 많은 인스턴스를 검증하며, 전체적으로는 22% 더 많이 검증합니다.

arXiv:2607.21756v1cs.DB공통 태그 query optimization

프롬프트를 데이터 타입으로: 데이터베이스 내 LLM 프롬프트 관리 및 재작성

Prompt as a Data Type: In-Database LLM Prompt Management and Rewriting

대규모 언어 모델(LLM)은 데이터베이스 기반 애플리케이션에서 튜플 분류, 의미적 술어를 이용한 레코드 필터링, 구조화된 속성 추출, 쿼리 결과 보강 등에 점점 더 많이 사용되고 있다. 그러나 이러한 연산을 시작하는 프롬프트는 일반적으로 DBMS 외부의 비구조화 형식으로 저장되어, 쿼리 실행, 메타데이터 관리, 최적화에 보이지 않게 된다. Stonebraker의 'QUEL as a Data Type'과 반성적 프로그래밍(reflective programming) 원칙에 기초하여, 본 논문은 프롬프트를 튜플 수준의 데이터베이스 값으로 취급하는 데이터베이스 시스템 PromptDB를 소개한다. PromptDB는 템플릿, 튜플 속성에 대한 바인딩, 모델 메타데이터, 태스크 메타데이터를 저장하는 논리적 PROMPT 데이터 타입을 제공한다. 릴레이션은 기본 테이블에 PROMPT 속성을 직접 포함하거나, 조인된 튜플에 대한 뷰를 통해 이를 노출할 수 있다. 사용자는 생성된 평가 뷰를 통해 프롬프트 값 속성을 쿼리하고, 시스템은 내부적으로 EVAL 연산자를 통해 프롬프트를 렌더링, 재작성, 최적화, 실행한다. 프롬프트를 데이터베이스에서 볼 수 있게 하면 새로운 최적화 공간이 생긴다. 핵심 아이디어는 옵티마이저 사고방식을 프롬프트에 가져오는 것이다. 쿼리 옵티마이저가 데이터베이스 메타데이터를 활용해 SQL 계획을 재작성하는 것처럼, PromptDB는 데이터베이스 메타데이터를 활용해 프롬프트를 재작성한다. 다양한 태스크에 걸친 합성 및 실제 데이터 워크로드에서 PromptDB를 평가했다. 결과는 데이터베이스 기반 재작성이 출력 유효성을 어떻게 개선하고, 정적·수동 작성 프롬프트에 비해 유리한 비용-품질 트레이드오프를 제공하는지 보여준다.

arXiv:2607.14375v1cs.CC공통 태그 neural network verification

무작위 매개변수 노이즈는 정확한 렐루 검증을 쉽게 만들지 않는다

Random Parameter Noise Does Not Make Exact ReLU Verification Easy

우리는 적대적 스무딩 모델에서 렐루 네트워크의 정확한 검증을 연구한다. 모든 네트워크 가중치와 바이어스는 가우시안 노이즈로 독립적으로 섭동되고, $[-2,2]$로 클리핑되며, 입력 비트 복잡도에 의해 결정되는 정확한 이진 소수(dyadic) 격자로 반올림된다. 우리는 표준 가정 $\mathrm{NP}\not\subseteq\mathrm{BPP}$ 하에서, 모든 기본 인스턴스에 대해 기대 실행 시간이 네트워크 크기, 비트 복잡도, 및 역 노이즈 수준에 대해 다항식인 건전하고 완전한 검증기가 존재하지 않음을 보인다. 이 결론은 이미 고정 노이즈 수준 $σ_\star=2^{-11}$에서, 단위 박스 위의 단일 은닉층 네트워크에 대해, 은닉층 fan-in이 최대 3이고 기본 계수가 $[-1,1]$에 있을 때 성립한다. 증명은 정확한 간격 임베딩과 정량적 견고성 논증을 결합한다. $m$개 절을 갖는 모든 E3SAT 공식 $Φ$에 대해, 절당 4개의 렐루를 사용하는 구성은 $\max_{x\in[0,1]^n} g_Φ(x)=(m-\operatorname{unsat}(Φ))/3$을 만족하며, 좌표별 임계값 반올림은 목적함수를 결코 감소시키지 않는다. 가중 매개변수 민감도 부등식과 가우시안 집중은 검증 간격이 $m$에 선형적으로 남아, 모든 계수의 집합적 섭동 이후에도 확률 최소 $1-e^{-m/8}$로 유지됨을 보인다. 증명에는 클리핑, 정확한 이진 소수 반올림, 출력층 섭동, 반올림된 가우시안 분포의 다항 비트 샘플링, 그리고 기대 스무딩 실행 시간에서 BPP 알고리즘으로의 변환이 포함된다. 계산 검증은 정확한 항등식을 시험하고, 광범위한 간격과 상수 간격의 서로 다른 스케일링을 보여준다. 이들은 복잡도 정리에 대한 증거라기보다 진단용이다. 이 결과는 명시된 절대 노이즈 모델에서 최악의 경우 기본 네트워크에 관한 것이지만, 매개변수 비퇴화(nondegeneracy)만으로는 정확한 검증에 대한 보편적인 스무딩-다항식 보장이 주어지지 않음을 보여준다.

arXiv:2607.08773v1cs.AI공통 태그 neural network verification

격자 순회를 통한 다층 퍼셉트론의 구간 인증

Interval Certifications for Multilayered Perceptrons via Lattice Traversal

본 연구에서는 AI 안전성의 근본적인 문제인 적대적 견고성(adversarial robustness)에 대한 엄밀한 이론적 프레임워크를 제시한다. 특히, 적대적 견고성 문제가 격자 순회(lattice traversal) 문제로 환원될 수 있음을 보인다. 이 격자의 각 원소는 입력 점 $\mathbf{x}$를 포함하는 구간, 즉 축 정렬 초직사각형(axis-aligned hyper-rectangle)에 해당한다. 다층 퍼셉트론(MLP) 분류기를 고려할 때, $\mathbf{x} \in I$이고 $\mathbf{x}$가 구간 $I$ 내에서 MLP의 예측을 변경하지 않고 자유롭게 교란될 수 있다면, 구간 $I$는 건전한 인증(sound certification)을 구성한다. 반면, $\mathbf{x} \in I$이고 $\mathbf{x}$가 $I$ 밖으로 이동할 때 MLP의 예측이 반드시 변한다면, 구간 $I$는 완전한 인증(complete certification)을 구성한다. 건전한 인증 문제는 잘 연구된 적대적 견고성에 해당하는 반면, 완전한 인증은 문헌에서 검토된 바 없다. 우리는 격자 순회 연산자를 개발하여 정제 및 검증(refine & verify) 반복 방식에 적용한다. 형식적 MLP 검증기(verifier)를 사용하여 건전 최대성(sound maximality)과 완전 최소성(complete minimality)이 보장된다. 또한, 목적 최적화 문제를 검토하는 과정에서 흥미로운 비대칭성을 발견한다. 완전한 인증의 경우 최솟값 해가 다항식 횟수의 오라클 호출로 얻어지지만, 건전한 인증에서는 이것이 성립하지 않으며, 강한 난해성(intractability) 결과를 증명한다. 더불어 대칭 구간(즉, $\ell_\infty$-구)에서의 최적화 문제를 검토하여 로그 복잡도 알고리즘을 제시한다. 마지막으로, 새로운 ParallelepipedoNN 시스템을 사용한 실증적 평가를 제시한다.

토론

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