저렴한 검사를 언제 신뢰할 것인가: 추론을 위한 약한 검증과 강한 검증

When to Trust the Cheap Check: Weak and Strong Verification for Reasoning

LLM을 활용한 추론은 점점 더 광범위한 검증 루프 내에서 전개되고 있다. 내부적으로 시스템은 자기 일관성이나 프록시 보상과 같이 비용이 적게 드는 검사를 사용하며, 우리는 이를 약한 검증이라고 부른다. 외부적으로 사용자는 출력 결과를 검토하고 결과가 신뢰할 수 있는 수준이 될 때까지 피드백을 통해 모델을 조종하는데, 우리는 이를 강한 검증이라고 부른다. 이러한 신호들은 비용과 신뢰성 면에서 극명한 차이를 보인다. 강한 검증은 신뢰를 구축할 수 있지만 자원 집약적인 반면, 약한 검증은 빠르고 확장 가능하지만 노이즈가 있고 불완전하다. 우리는 약한 검증을 기반으로 수락 또는 거절할 시점과 강한 검증으로 판단을 넘길 시점을 결정하는 '약한-강한 검증 정책'을 통해 이러한 긴장 관계를 공식화한다. 또한 잘못된 수락, 잘못된 거절, 강한 검증의 빈도를 측정하는 지표를 도입한다. 모집단 전반에 걸쳐, 우리는 최적의 정책이 이중 임계값 구조를 가지며, 보정(calibration)과 선명도(sharpness)가 약한 검증기의 가치를 좌우한다는 것을 보여준다. 이를 바탕으로 우리는 쿼리 스트림, 언어 모델 또는 약한 검증기에 대한 어떠한 가정 없이도 수락 및 거절 오류를 입증 가능하게 제어할 수 있는 온라인 알고리즘을 개발하였다.

Reasoning with LLMs increasingly unfolds inside a broader verification loop. Internally, systems use cheap checks, such as self-consistency or proxy rewards, which we call weak verification. Externally, users inspect outputs and steer the model through feedback until results are trustworthy, which we call strong verification. These signals differ sharply in cost and reliability: strong verification can establish trust but is resource-intensive, while weak verification is fast and scalable but noisy and imperfect. We formalize this tension through weak--strong verification policies, which decide when to accept or reject based on weak verification and when to defer to strong verification. We introduce metrics capturing incorrect acceptance, incorrect rejection, and strong-verification frequency. Over population, we show that optimal policies admit a two-threshold structure and that calibration and sharpness govern the value of weak verifiers. Building on this, we develop an online algorithm that provably controls acceptance and rejection errors without assumptions on the query stream, the language model, or the weak verifier.