전이 기반 검증: 엄밀한 정보 프론티어와 호출 비용
Verification with Transfer: Exact Information Frontiers and Their Price in Calls
한국어 초록
답변 전체를 수락하거나 거부하는 검증자(verifier)가 제공하는 정보는 극히 제한적입니다. $k$비트 답변에 대한 균등 사전 분포(flat prior) 하에서 오류율 0을 달성하려면 $2^k-1$번의 검증이 필요합니다. 이에 대한 일반적인 해결책은 커리큘럼처럼 관련 소스 태스크를 사전에 모두 해결하거나, 검증과 번갈아 수행(interleaving)하는 것입니다. 본 연구에서는 이 해결책의 비용을 정보량과 호출 횟수 관점에서 산정합니다. 정확한 검증자 환경에서 소스 호출과 $n$번의 검증을 임의로 번갈아 수행하여 성공 확률 $s$를 달성하는 데 필요한 최소 인과적 정보량은 리스트 율-왜곡 함수(list rate-distortion function)이며, 이는 어떠한 검증도 수행하기 전 단 한 번의 관측으로 도달할 수 있습니다. 이는 이진 소스 호출의 기댓값에 대한 하한을 제시하며, 설계된 소스는 고유한 정답에 대해 $1+\log_25$번 이내의 호출로, 일반적인 경우에는 가산 상수가 충분하지 않은 로그 항 오차 범위 내에서 이를 달성합니다. 정확한 검증자와 고정된 소스를 사용할 때, 모든 호출을 첫 번째 검증 이전으로 옮기더라도 호출에 대한 모든 엄격한 상한(hard cap)은 보존되지만, 호출을 번갈아 수행하면 기댓값 측면에서 호출 횟수를 무한히 절약할 수 있습니다. 반면 노이즈가 있는 검증자 하에서는 소스 우선 프로토콜이 정보량과 오류율에서 무한한 배수만큼의 손실을 초래할 수 있습니다. $\mathbb{F}_2$ 상의 선형 뱅크의 경우 최적 정확도는 닫힌 형태(closed form)를 가지며, 다항 시간 환원 후 $J$개의 소스와 불필요한 차원(nuisance dimension) $h$에 대해 예산 프로파일을 $2^{O(h^2)}\operatorname{poly}(J,k+h)$ 시간 내에 계산할 수 있습니다. 이러한 뱅크에서 엄격한 상한 하에 오류율 0을 달성하기 위해 올림된 정보 비용을 초과하여 소모되는 호출은 정확히 불필요한 차원에 사용된 호출과 일치합니다. 플래너에 관한 두 절을 제외한 모든 번호가 매겨진 결과는 기발표된 두 결과를 가정하여 Lean 4에서 기계 검증되었습니다. 이 프론티어를 척도로 활용한 결과, 고정된 학습(training) 예산 내에서 소형 트랜스포머(transformer)가 잠재 차원 5에서는 전달된 모든 비트를 활용하지만 11에서는 전혀 활용하지 못함을 보였습니다. 또한 학습 전 기록된 예측을 이용한 테스트에서는 타깃 비트의 낮은 XOR 차수만으로는 해당 비트의 활용을 보장하기에 충분하지 않았습니다.
원문 초록
A verifier that accepts or rejects whole answers reveals little: under a flat prior over $k$-bit answers, zero error needs $2^k-1$ verifications. The usual remedy is to solve related source tasks, either all first, as a curriculum does, or interleaved with verification. We price this remedy in information and in calls. With an exact verifier, the least causal information that any interleaving of source calls and $n$ verifications needs to succeed with probability $s$ is a list rate-distortion function, attained by one observation before any verification. It lower-bounds the expected number of binary source calls, which designed sources meet within $1+\log_25$ calls for unique answers and within a logarithmic term in general, where no additive constant suffices. With an exact verifier and fixed sources, moving every call before the first verification preserves all hard caps on calls, although interleaving can save unboundedly many expected calls; under a noisy verifier, source-first protocols can lose unbounded factors in information and in error. For linear banks over $\mathbb{F}_2$, optimal accuracy has a closed form, and after a polynomial-time reduction the budget profile is computable in time $2^{O(h^2)}\operatorname{poly}(J,k+h)$ for $J$ sources and nuisance dimension $h$. In these banks, for zero error under a hard cap, the calls beyond the rounded-up information price are exactly those spent on nuisance. Every numbered result apart from two clauses about the planner is machine-checked in Lean 4, assuming two published results. Used as a ruler, the frontier shows a small transformer using all delivered bits at latent dimension $5$ and none at $11$ within fixed training budgets; in a test with predictions recorded before training, low XOR degree of the target bits did not suffice for their use.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
46 pages, of which 8 pages main text. The Lean 4 formalization is in the ancillary files