arXiv:2605.05870v3 cs.LG

QuadraSHAP: 가우스-르장드르 구적법을 통한 곱 게임의 안정적이고 확장 가능한 샤플리 값 계산

QuadraSHAP: Stable and Scalable Shapley Values for Product Games via Gauss-Legendre Quadrature

Majid Mohammadi, Grigory Reznikov, Pavel Sinitcyn, Krikamol Muandet, Siu Lun Chau

제출 2026-09-24

한국어 초록

본 논문에서는 연합의 가치가 플레이어별 항들의 곱으로 분해되는 협력 게임인 곱 게임(product games)에 대한 샤플리 값(Shapley values)의 효율적인 계산을 연구합니다. 이러한 게임은 곱 커널을 사용하는 커널 기법이나 트리 기반 모델과 같이, 가치 함수가 기반 모델로부터 곱 구조를 물려받을 때 머신러닝 설명가능성(explainability) 분야에서 발생합니다. 본 연구의 핵심 결과는 곱 게임에서 각 플레이어의 샤플리 값이 정확한 1차원 적분 표현식을 갖는다는 점입니다. 즉, 지수적으로 많은 수의 특징 연합에 대한 가중 합이 $[0,1]$ 구간에서 $(d-1)$차 다항식의 적분으로 단순화되며, 여기서 $d$는 총 특징의 수입니다. 이를 통해 노드 수 $m_q$가 $m_q \geq \lceil d/2 \rceil$을 만족할 때마다 증명 가능하게 정확(provably exact)하며, 그렇지 않은 경우에도 오차가 $m_q$에 따라 기하급수적으로 감소함이 증명된 거의 정확한 근사를 제공하는 가우스-르장드르 구적법(Gauss-Legendre quadrature) 기법을 도출합니다. 실제 환경에서는 수천 개의 특징이 존재하더라도 수백 개의 노드만으로 고정밀 추정치를 얻을 수 있습니다. 이러한 정식화를 바탕으로, 본 논문은 로그 공간(log-space) 평가를 통한 수치적으로 안정한 구현과 함께, $O(d\,m_q)$의 총 작업량(work) 및 $O(\log d)$의 병렬 시간(parallel time)을 달성하는 결합 스캔(associative scan) 기본 연산 기반의 효율적인 병렬 구현을 유도합니다. 실험을 통해 QuadraSHAP이 테스트된 모든 구성에서 가장 빠른 수치적으로 안정한 방법임을 보여줍니다.

원문 초록

We study the efficient computation of Shapley values for \emph{product games} -- cooperative games in which the coalition value factorizes as a product of per-player terms. Such games arise in machine learning explainability whenever the value function inherits a multiplicative structure from the underlying model, as in kernel methods with product kernels and tree-based models. Our key result is that the Shapley value of each player in a product game admits an exact one-dimensional integral representation: the weighted sum over exponentially many feature coalitions collapses to the integral of a degree-$(d-1)$ polynomial over $[0,1]$, where $d$ is the total number of features. This yields a Gauss--Legendre quadrature scheme that is \emph{provably exact} whenever the number of nodes satisfies $m_q \geq \lceil d/2 \rceil$, and otherwise provides a \emph{near-exact} approximation with error provably decaying geometrically in $m_q$. In practice, a few hundred nodes can achieve highly precise estimates even with thousands of features. Building on this formulation, we derive a numerically stable implementation via log-space evaluation, together with an efficient parallel implementation based on associative scan primitives that achieves $O(d\,m_q)$ total work and $O(\log d)$ parallel time. Experiments show that \textsc{QuadraSHAP} is the fastest numerically stable method across all tested configurations.

제출 이력

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

  1. arXiv:2605.05870v3제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2610.15915v1cs.CV공통 태그 Computational Efficiency, Benchmarking

VIEWCRAFT: 멀티모달 에이전트가 보는 대상과 이를 읽는 방식의 공동 진화

VIEWCRAFT: Evolving What Multimodal Agents See and How They Read It

재사용 가능한 스킬은 모델(model) 가중치를 업데이트하지 않고도 멀티모달 에이전트(multimodal agent)를 향상시키지만, 그 효과는 제시되는 근거(evidence)와 이를 읽는 데 사용되는 절차 모두에 의존합니다. 본 논문에서는 실행 가능한 근거 인터페이스와 해당 인터페이스의 읽기 절차를 함께 공동 진화시키는 ViewCraft를 소개합니다. 인터페이스는 관측치를 선택, 변환, 구성하며, 리더(reader)는 그 결과로 생성된 뷰(view)를 해석합니다. 실패 추적(failure trace)은 수정을 안내하고, 리플레이 및 쌍체 평가(paired evaluation)는 유용한 변경 사항을 유지하며, 인터페이스 프로젝션은 적격한 기각 공동 제안으로부터 시각적 편집 내용을 복구합니다. 8개 벤치마크(benchmark) 전반에서 ViewCraft는 직접 실행 방식 대비 태스크 점수를 평균 $6.1$점 향상시켰으며, 모든 벤치마크에서 성능 향상을 달성했습니다. 이러한 이점은 일치된 입력 토큰(token) 예산 하에서도 유지됩니다. 5개의 모든 다중 소스 태스크에서 학습된 인터페이스는 초기 스킬보다 8%~15% 더 적은 입력 토큰을 사용합니다. 또한 학습된 스킬은 실행기(executor) 간에 전이되며 평가된 모든 전이 환경에서 직접 실행 방식을 능가하여, 결합된 재사용 가능 스킬로서의 근거 구축 및 읽기 접근법을 뒷받침합니다.

arXiv:2610.13563v1cs.SE공통 태그 Computational Efficiency, Benchmarking

모든 정답 수정이 같은 성능을 내지는 않는다: 저장소 수준 이슈 해결에서 패치 성능에 대한 실증적 연구

Not All Correct Fixes Run Alike: An Empirical Study of Patch Performance in Repository-Level Issue Resolution

SWE-bench와 같은 저장소 수준 이슈 해결(issue resolution) 벤치마크는 제출된 패치를 주로 정확성 테스트 통과 여부로 평가하며, 테스트를 통과한 서로 다른 패치들 간의 런타임 성능(runtime performance)은 대부분 탐구되지 않은 채로 남아 있다. 패치 성능을 평가하는 것은 필수적이지만, 각 벤치마크 인스턴스마다 성능 워크로드를 설계하는 데 비용이 많이 들어 어렵다. 그러나 이러한 벤치마크는 이미 자연스러운 후보를 제공하는데, 바로 이슈 수정으로 영향을 받는 동작을 실행하는 내장 FAIL_TO_PASS(F2P) 테스트이다. 따라서 우리는 제공된 F2P 테스트를 패치 성능 평가에 재활용할 수 있는지 조사한다. 전체적으로 우리는 Claude Opus 5, GPT 5.6, DeepSeek V4 Pro, Qwen 3.8 Max라는 네 가지 프런티어(frontier) 모델을 SWE-agent와 결합하여 SWE-bench 및 SWE-bench-Live의 검증된(verified) 분할에서 사전 필터링된 측정 가능한 코퍼스(corpus)를 해결하도록 하였으며, 그 결과 개발자의 정답(ground-truth) 패치를 포함해 최소 두 개 이상의 서로 다른 정답 해법을 가진 262개 사례를 얻었다. 이후 우리는 각 해법의 런타임 성능을 네이티브 F2P 테스트에서 명령어 수(instruction count)와 실제 경과 시간(wall-clock time)으로 측정하고, 더 강건한 통계적 판별 기준으로 선행 연구에서 제안된 RSD 대신 Welch ANOVA를 사용한다. 우리는 이 방법론이 런타임 성능에서 뚜렷한 판별 능력을 보이며, 거의 절반에 가까운 사례에서 패치 간 성능 차이를 식별해냄을 발견한다. 우리의 실증적 연구는 생성된 패치의 런타임 성능이 LLM의 이슈 해결률(resolution rate)과 무관하며, 모델 순위가 거의 뒤바뀐다는 것을 보여준다. 사례 연구(case study)는 또한 성능 분석이 정확성 평가에서는 간과된 일부 패치의 아키텍처적 회귀(architectural regression)를 드러낸다는 것을 보여준다. 이러한 발견은 해결률이 저장소 수준 이슈 해결에 대한 LLM의 능력을 충분히 특성화하지 못한다는 것을 시사하며, 향후 평가에서 해결률과 함께 패치 성능을 함께 고려하도록 동기를 부여한다.

arXiv:2610.13570v1cs.AI공통 태그 Computational Efficiency, Benchmarking

추론 모델의 오버씽킹에 대한 최적 추론 종료 기법의 파레토 프론티어 구축

Constructing Pareto Frontiers of Optimal Reasoning Termination Methods for Overthinking in Reasoning Models

추론 모델은 테스트 시간 스케일링(test-time scaling)의 이점을 얻을 수 있지만, 지속적인 추론은 비효율적이거나 오히려 해로울 수 있으며, 이를 오버씽킹(overthinking) 현상이라고 부릅니다. 전체 추론(full thinking)을 기준으로 한 평가는 정확도와 토큰 사용량을 비교하지만, 오버씽킹의 심각도 및 각 전략의 이론적 완화 잠재력에 대한 기준이 부족합니다. 모델-작업 수준에서 오버씽킹의 특성을 규명하기 위해, 본 연구에서는 먼저 고정된 샘플링 추론 궤적을 따라 보존된 여러 접두사(prefix)로부터 반복적으로 답변을 생성하는 단계별 절단 프로빙(Step-wise Truncation Probing, STP)을 도입합니다. 각 궤적에서 최대 실증적 정확도에 도달하는 가장 이른 측정 위치를 기준으로 삼아, 이후 생성된 추론 토큰의 비율을 오버씽킹 비율(Overthinking Ratio)로, 해당 기준점 대비 전체 추론까지의 정확도 하락을 정확도 저하(Accuracy Degradation)로 각각 정의합니다. 둘째로, 다양한 종료 전략의 이론적 완화 잠재력을 정량화하기 위해 동적 라우팅(dynamic routing), 고정 예산(fixed budgets), 동적 조기 종료(dynamic early exit)를 통합된 프레임워크 내에서 정식화합니다. 이 통합 프레임워크를 기반으로 완전한 STP 측정값을 활용하여 공통의 정규화된 추론 토큰 예산 하에서 각 전략에 대한 토큰-정확도 파레토 프론티어(Pareto frontier)를 구축합니다. 나아가 6개 모델과 4개 벤치마크 그룹에 걸쳐 705억 개의 추론 토큰 및 해당 프로빙 측정값을 생성한 STP 프로세스로부터 구축된 재사용 가능한 벤치마크인 OTBench를 개발합니다.

arXiv:2610.10642v1stat.ML공통 태그 shapley values, explainability

로그 오즈에서 샤플리 값까지: 가중 나이브 베이즈 분류기를 위한 설명 기하학

From Log-Odds to Shapley Values: An Explanatory Geometry for the Weighted Naive Bayes Classifier

본 논문에서는 가중 나이브 베이즈(weighted naive Bayes) 분류기 모델이 유도하는 지도 표현(supervised representation)으로부터 설명 공간을 구축하는 방법을 연구합니다. 조건부 로그 우도에 기반한 고전적인 지도 거리를 출발점으로 삼아, 분류 결정과 보다 직접적으로 연관되는 로그 오즈(log-odds) 기반의 판별적 재정식을 도입합니다. 이어 이러한 표현이 분석적 샤플리 값(Shapley value) 벡터 간의 $\ell_1$ 거리와 정확히 일치하는 거리를 유도함을 보여줌으로써, 모델이 유도하는 기하학에 대한 형식적인 설명적 해석을 제공합니다. 마지막으로, $k$-최근접 이웃 분류기를 사용하여 이러한 표현들로부터 파생된 여러 지도 거리를 실증적으로 비교합니다. 본 연구는 주로 방법론적 관점에서 지도 거리, 국소적 설명(local explanation), 그리고 예측 거동 사이의 밀접한 연관성을 조명합니다.

arXiv:2610.02488v2cs.LG공통 태그 Computational Efficiency, Benchmarking

LLM을 에이전트로 활용하기: 비용은 얼마인가?

Harnessing LLMs as Agents: What Does It Cost?

언어 모델 에이전트는 제한된 컨텍스트(bounded context), 영속 메모리(persistent memory), 도구, 검증, 반복 실행을 관리하는 하네스(harness)에 점점 더 의존하고 있지만, 기존의 모델 능력 개념은 이러한 메커니즘이 소비하는 계산 자원을 정량화하지 못한다. 우리는 기저 의미론적 모델(semantic model)은 고정한 채 하네스 수준의 자원을 명시적으로 과금하는 자원 제약 추상화인 언어 모델 에이전트 머신(Language Model Agent Machine, LAM)을 도입한다. 우리는 네 가지 범주의 결과를 확립한다. 통신(Communication): LAM 실행은 동시적인 호출-전송 예산(call-transfer budget) 하에서 적-청 페블링(red-blue pebbling)과 인스턴스 단위로 동등하며, 이는 고전적인 입출력 하한(I/O lower bound)을 컨텍스트-메모리 트래픽으로 전이시킨다. 접근(Access): 메모리 인터페이스는 포인터 체이싱(pointer chasing)에서 무작위 접근과 비추측적(non-speculative) 순차 접근 사이의 $Θ(n)$ 격차를 포함하여 점근적 분리(asymptotic separation)를 유발한다. 재계산(Recomputation): 비트 반전(bit-reversal) DAG는 컨텍스트 용량 $C$와 영속 메모리 용량 $S$ 하에서 $Θ(n^2/(C+S)+n)$회의 모델 호출을 필요로 하며, 이는 저장된 중간 상태가 반복적인 의미론적 계산을 언제 피할 수 있는지를 정량화한다. 신뢰성(Reliability): 우리는 엄밀한 단계별(stage-local) 샘플링 한계, 불완전 검증(imperfect-verification)의 정확한 비용, 그리고 닫힌 형태의 최적 검증 간격을 갖는 영-데일리(Young-Daly) 유형의 체크포인트 법칙을 유도한다. GPT-6 Astra에 대한 통제 실험과 홀드아웃(held-out) 실험은 체크포인트 최적값, 프로그래밍적 검사(programmatic checking) 하에서의 정책 선택, 그리고 연쇄 MATH 과제에서 호출 단위(call granularity), 논리적 입력 트래픽, 신뢰성 간의 트레이드오프를 포함하여 통신 및 신뢰성 예측을 검증한다. 종합적으로, 이 결과들은 언어 모델 에이전트 하네스의 계산 비용에 대한 자원 이론(resource theory)을 제공한다.

arXiv:2610.01116v1cs.AI공통 태그 Computational Efficiency, Benchmarking

최고 성능(SOTA)을 넘어서: AI 연구를 위한 환경 영향 지표 표준화

Beyond State-of-the-Art: Standardising Environmental Impact Metrics for AI Research

대규모 언어 모델(LLM)의 성능과 활용도가 증가함에 따라 환경적 발자국 역시 커지고 있습니다. 책임 있는 AI에 대한 요구에도 불구하고, 머신러닝 커뮤니티에는 탄소 회계(carbon accounting)를 위한 표준화된 관행이 부재합니다. NeurIPS 2025에 채택된 5,285편의 논문을 대상으로 진행한 자동화된 문헌 조사에 따르면, 환경 영향에 대한 보고는 거의 전무한 것으로 나타났습니다. 지속 가능한 AI로의 전환을 촉진하기 위해, 본 연구는 모델 학습 효율성을 평가하기 위한 표준화된 지속가능성 지표를 정의하고, LLM 추론의 탄소 비용을 추정하기 위한 간단한 휴리스틱을 함께 제시합니다. 또한 이러한 지표를 배출량 추적 및 보고를 위한 간편 적용 소프트웨어 솔루션인 carbonbenchmark에 구현하였습니다. 마지막으로, 과도한 환경적 비용을 치르며 미미한 정확도 향상만을 추구하는 흐름에 대응하기 위해, 전통적인 최고 성능(SotA) 정확도와 더불어 연산 효율성 및 환경적 책무성을 우선시하도록 연구 분야에 과제를 던지는 프레임워크인 '과업을 달성하는 최소 모델(SMAJ)'을 공식화합니다.

토론

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