문맥 귀속(Context attribution)은 프롬프트의 일부를 제거했을 때 언어 모델의 출력이 어떻게 변하는지를 묻는 것입니다. 우리는 $n$ 토큰으로 구성된 프롬프트와 고정된 측정 함수에 대한 leave-one-out (LOO) 귀속을 연구합니다. 모든 LOO 값을 직접 계산하려면 $n$개의 모델 평가가 필요합니다.
안정성 가정(stability assumption) 하에서, 우리의 알고리즘은 $O(\sqrt{\log(1/\varepsilon)}/\varepsilon)$개의 평가 호출만을 사용하여 상수 확률로 $\varepsilon$에 비례하는 오차를 갖는 모든 LOO 값을 추정합니다. 상한(upper bound)을 보완하기 위해, 우리는 오라클 모델에서 평가 호출 수에 대한 일치하는 하한($\Omega(\sqrt{\log(1/\varepsilon)}/\varepsilon)$)을 증명합니다.
경험적으로(Empirically), 우리는 안정성과 일치하는 계수 감쇠를 검증하고 소규모 언어 모델 검색 작업에 대한 우리의 스케칭 알고리즘 성능을 평가합니다. 기술적으로, 우리의 결과는 Taylor 계수가 Gunn [Gun26]이 최근 도입한 안정성 조건을 만족하는 산술 회로(arithmetic circuits)에 대한 스케칭 알고리즘에 기반합니다. 그들의 순방향 미분 스케치(forward differentiation sketches)를 직접 적용하려면 $\widetilde{O}(\log(n)/\varepsilon^2)$개의 평가 호출이 필요할 것입니다. 우리의 핵심 관찰은 동일한 Taylor 차수의 순방향 스케치에 비해 상수 오버헤드만으로 역전파 회로(backpropagation circuit)에 순방향 미분을 적용할 수 있다는 것입니다. 이는 스케치의 분산(variance)을 줄이고 개선된 평가 상한의 핵심 요소입니다.
우리의 하한은 무작위 행렬(random matrices)의 대각 요소(diagonal elements)를 추정하기 위한 행렬-벡터 쿼리(matrix-vector queries) 수에 대한 하한을 설정하는 Amsel, Chen, Duman Keles, Halikias, Musco, 및 Musco [ACDH+26, SIAM Journal on Matrix Analysis and Applications]의 기술에 기반합니다.