한국어 초록
문맥 귀속은 프롬프트의 일부를 제거하면 언어 모델의 출력이 어떻게 변하는지를 묻는다. 우리는 $n$개의 토큰으로 이루어진 프롬프트와 고정된 측정 함수에 대한 leave-one-out(LOO) 귀속을 연구한다. 모든 LOO 값을 직접 계산하려면 $n$번의 모델 평가가 필요하다. 안정성 가정 하에서, 우리의 알고리즘은 $O(\sqrt{\log(1/\varepsilon)}/\varepsilon)$번의 평가 호출만으로 상수 확률로 $\varepsilon$에 비례하는 오차 이내에서 모든 LOO 값을 추정한다. 상한을 보완하기 위해, 우리는 오라클 모델에서 평가 호출 횟수에 대한 일치하는 $Ω(\sqrt{\log(1/\varepsilon)}/\varepsilon)$ 하한을 증명한다. 실험적으로는 안정성과 부합하는 계수 감쇠를 확인하고, 소규모 언어 모델 검색 과제에서 스케칭 알고리즘의 성능을 평가한다. 기술적으로 우리의 결과는 Gunn [Gun26]이 최근 도입한 안정성 조건을 테일러 계수가 만족하는 산술 회로에 대한 스케칭 알고리즘에 기반한다. 이들의 순방향 미분 스케치를 직접 적용하면 $\widetilde{O}(\log(n)/\varepsilon^2)$번의 평가 호출이 필요하다. 우리의 핵심 관찰은 역전파 회로에 순방향 미분을 적용할 수 있으며, 이때 동일한 테일러 차수의 순방향 스케치 대비 오버헤드가 상수 수준에 그친다는 점이다. 이는 스케치의 분산을 줄여 주며 개선된 평가 한계의 핵심이 된다. 우리의 하한은 무작위 행렬의 대각 원소를 추정하는 데 필요한 행렬-벡터 질의 횟수의 하한을 다룬 Amsel, Chen, Duman Keles, Halikias, Musco, Musco [ACDH+26, SIAM Journal on Matrix Analysis and Applications]의 기법에 기반한다.
원문 초록
Context attribution asks how removing parts of a prompt changes a language model's output. We study leave-one-out (LOO) attribution for a prompt of $n$ tokens and a fixed measurement function. Computing all LOO values directly requires $n$ model evaluations. Under a stability assumption, our algorithm estimates all LOO values to error proportional to $\varepsilon$ with constant probability using $O(\sqrt{\log(1/\varepsilon)}/\varepsilon)$ evaluation calls. To complement our upper bound, we prove a matching $Ω(\sqrt{\log(1/\varepsilon)}/\varepsilon)$ lower bound on the number of evaluation calls in an oracle model. Empirically, we verify coefficient decay consistent with stability and evaluate the performance of our sketching algorithm on a small language-model retrieval task. Technically, our result is based on a sketching algorithm for arithmetic circuits whose Taylor coefficients satisfy the stability condition recently introduced by Gunn [Gun26]. A direct adaptation of their forward differentiation sketches would require $\widetilde{O}(\log(n)/\varepsilon^2)$ evaluation calls. Our key observation is that we can apply forward differentiation to the backpropagation circuit, with only constant overhead over a forward sketch of the same Taylor degree. This reduces the variance of the sketches and is key to our improved evaluation bound. Our lower bound builds on the techniques of Amsel, Chen, Duman Keles, Halikias, Musco, and Musco [ACDH+26, SIAM Journal on Matrix Analysis and Applications] for lower bounding the number of matrix-vector queries to estimate the diagonal elements of random matrices.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.