arXiv:2606.20740v1 cs.CL

VeriBound: 형식 검증 도구로 학습한 프로세스 보상 모델의 PAC-Bayesian 일반화 경계

VeriBound: PAC-Bayesian Generalization Bounds for Process Reward Models Trained with Formal Verification Tools

Amirul Rahman, Mohammed Sabih Alsharari

제출 2026-06-17

한국어 초록

프로세스 보상 모델(PRM)은 대규모 언어 모델(LLM) 추론에 대한 단계 수준 검증을 제공하지만, 학습 데이터 확보는 여전히 병목이다. 사람 어노테이션은 비용이 많이 들고 Monte Carlo rollout 추정은 노이즈가 많다. 최근 접근법인 FOVER는 Z3, Isabelle 등 형식 검증(formal verification) 도구로 자동 어노테이션된 단계 수준 오류 레이블로 PRM을 학습하고, 기호(symbolic) 과제에서 다양한 추론 벤치마크로의 과제 간 일반화를 경험적으로 관찰했다. 그러나 이러한 일반화 현상에 대한 이론적 설명은 없으며, 이러한 PRM의 일반화 오류, 표본 복잡도(sample complexity), 수렴 속도, 또는 downstream Best-of-K 성능에 대한 공식적 경계도 존재하지 않는다. 우리는 형식 검증 도구로 학습된 PRM에 대한 PAC-Bayesian 일반화 경계를 제공하는 이론적 프레임워크인 VeriBound를 제안한다. 우리는 네 가지 주요 결과를 확립한다: (i) 형식 검증으로 어노테이션된 학습 데이터上的 경험적 검증 오류를 보지 못한 추론 과제上的 기대 오류와 연결하는 PAC-Bayesian 일반화 경계로, 이 경계는 형식 검증 정확도와 학습·테스트 과제 분포 간 발산(divergence)에 의존한다; (ii) PRM 가설 클래스의 복잡도 $d$에 대해 일반화 오류 $ε$를 확률 $1-δ$로 달성하기 위해 $O(d \log(d/δ) / ε^2)$개의 형식 검증 어노테이션 예시면 충분하다는 표본 복잡도 결과; (iii) $L$-smoothness 및 분산 유계(bounded variance) 조건 하에서 형식 검증 레이블로 PRM 학습이 선형 속도로 수렴함을 증명하는 수렴 분석; (iv) 단계 수준 검증 오류를 Best-of-K 성능 저하와 연결하는 오류 전파 경계.

원문 초록

Process Reward Models (PRMs) provide step-level verification for Large Language Model (LLM) reasoning, yet their training data acquisition remains a bottleneck: human annotation is costly and Monte Carlo roll-out estimates are noisy. A recent approach, FOVER, trains PRMs on step-level error labels automatically annotated by formal verification tools such as Z3 and Isabelle, and empirically observes cross-task generalization from symbolic tasks to diverse reasoning benchmarks. However, this generalization phenomenon lacks any theoretical explanation, and no formal bounds exist on the generalization error, sample complexity, convergence rate, or downstream Best-of-K performance of such PRMs. We propose VeriBound, a theoretical framework that provides PAC-Bayesian generalization bounds for PRMs trained with formal verification tools. We establish four main results: (i) a PAC-Bayesian generalization bound that relates the empirical verification error on formal-verification-annotated training data to the expected error on unseen reasoning tasks, with the bound depending on the formal verification accuracy and the divergence between training and test task distributions; (ii) a sample complexity result showing that $O(d \log(d/δ) / ε^2)$ formal-verification-annotated examples suffice to achieve generalization error $ε$ with probability $1-δ$, where $d$ is the complexity of the PRM hypothesis class; (iii) a convergence analysis proving that PRM training with formal verification labels converges at a linear rate under $L$-smoothness and bounded variance conditions; and (iv) an error propagation bound that relates step-level verification error to Best-of-K performance degradation.

제출 이력

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

  1. arXiv:2606.20740v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2610.02695v1cs.LG공통 태그 Uncertainty Quantification, Math, Large Language Model

대규모 언어 모델(LLM) 추론을 위한 테스트 시점 캘리브레이션 학습

Test-time Calibration Learning for Large Language Model Reasoning

신뢰할 수 있는 대규모 언어 모델(LLM)은 정확한 답변을 생성하는 것뿐만 아니라, 정답일 확률을 충실히 반영하는 신뢰도(confidence)를 표현해야 한다. 이러한 캘리브레이션(calibration)은 불확실한 예측을 식별하고 실제 배포 환경에서의 신뢰할 수 있는 의사결정을 지원하는 데 필수적이다. 최근 연구들은 캘리브레이션 학습을 강화학습에 결합하여, 정답 여부에 대한 정답(ground-truth) 정확성 감독(supervision)을 이용해 답변 정확성과 언어로 표현된 신뢰도(verbalized confidence)를 공동으로 최적화한다. 그러나 이러한 접근법은 레이블이 있는 데이터에 의존하기 때문에, 정답 레이블을 사용할 수 없고 캘리브레이션이 새롭게 접하는 목표 과제(target task)에 적응해야 하는 실제 테스트 시점(test-time) 환경에서의 적용 가능성이 제한된다. 이러한 문제를 해결하기 위해, 우리는 레이블이 없는 목표 과제 데이터에서 직접 추론 정확도와 언어로 표현된 신뢰도를 공동으로 적응시키는 레이블-프리(label-free) 프레임워크인 테스트 시점 캘리브레이션 학습(Test-Time Calibration Learning, TTCL)을 제안한다. 구체적으로, TTCL은 다수의 모델 생성 응답으로부터 정답 여부와 캘리브레이션 모두에 대한 자기 감독(self-supervision) 신호를 도출하여, 정답 레이블 없이도 테스트 시점에서의 캘리브레이션 학습을 가능하게 한다. 이론적 분석을 통해 TTCL이 이상적인 캘리브레이션 목적함수에 대한 경계가 있는(bounded) 대체 목표(surrogate)임을 추가로 입증한다. 수학적 추론과 사실 기반 질의응답(factual question answering)에 대한 광범위한 실험을 통해, TTCL이 다양한 모델과 과제에서 정확도와 캘리브레이션을 일관되게 향상시킨다는 것을 보인다. 기본 모델(base model)에서 TTCL은 8개의 벤치마크에서 평균 상대 정확도 개선 +40.13%와 ECE(Expected Calibration Error) 감소 +70.80%를 달성한다. 더불어 TTCL은 이미 캘리브레이션된 모델에 대해서도 도메인 변화(domain shift) 상황에서 정확도와 캘리브레이션을 더욱 개선할 수 있으며, 특히 소스 도메인(source-domain)의 캘리브레이션이 목표 과제로 잘 전이되지 않는 경우에 효과적이다. 수학-사실 기반 질의응답(math-to-factQA) 설정에서 TTCL은 평균 상대 정확도 향상 +20.35%를 달성하고 ECE를 +53.83% 감소시킨다. 소스 코드는 https://github.com/tmlr-group/TTCL 에서 공개되어 있다.

arXiv:2610.13672v2cs.CL공통 태그 Math, Large Language Model

토큰이 아닌 턴 주입하기: 자기 수정을 위해 LLM 추론을 리디렉션할 위치 학습

Inject a Turn, Not a Token: Learning Where to Redirect LLM Reasoning for Self-Correction

대규모 언어 모델(LLM)은 자신의 추론 과정에서 발생한 오류를 안정적으로 식별하고 수정하는 데 어려움을 겪는다. 수정이나 피드백을 생성하도록 LLM을 미세조정하는 기존의 학습 기반 접근법과 달리, 우리는 실패한 롤아웃에서 어디에 개입할지를 학습하고 이를 어떻게 리디렉션할지를 결정한다. 개입 위치를 선택하기 위해, 우리는 최종 답안의 정답 여부만을 이용해 고정된 인코더 위에 130K개의 매개변수를 가진 MLP 헤드를 학습시킨다. 리디렉션의 경우, 고정된 생성 예산 하에서 테스트한 인라인 주입(inline injection)은 추론을 안정적으로 리디렉션하지 못하는 반면, 동일한 지시문을 새로운 사용자 턴(user turn)으로 제시하면 모델의 진행 방향이 바뀐다는 것을 발견했다. 그 결과로 만들어진 수정 프레임워크인 UPTURN(User-Prompt TURN injection at a learned position)은 LLM의 미세조정을 전혀 요구하지 않는다: 선택된 접두 문맥(prefix)을 유지하고, 지시문을 새로운 사용자 턴으로 주입한 뒤, 나머지 부분을 재생성한다. 네 가지 추론 모델과 여섯 가지 수학 벤치마크 전반에서, UPTURN은 32회 롤아웃 기준선(baseline) 대비 모든 설정에서 평균 정확도를 향상시킨다. 동일한 수정 예산 하에서 자기 수정(self-correction) 및 리플렉션 토큰(reflection-token) 주입 기준선을 능가하며, 재학습 없이도 다른 추론 모델과 GPQA-Diamond로 전이되고, GRPO 및 자기 수정 기법과도 상호보완적이다.

arXiv:2610.15948v1cs.AI공통 태그 Bayesian Inference, Uncertainty Quantification

비전: "사용자 선호에 대해 내가 모르는 것은 무엇인가?" 불확실성 추정이 능동형 어시스턴트 정렬을 향상시키는 방법

Vision: "What Don't I Know About User's Preferences?" How Uncertainty Estimation Improves Proactive Assistant Alignment

능동형 스마트 어시스턴트(Proactive Smart Assistant, PSA)는 사용자가 선호할 행동을 예측하기 위해 일반 지식, 그룹 수준 데이터에서 학습된 패턴, 개별 사용자 데이터의 패턴, 그리고 최근 센서 관측값을 점점 더 많이 활용하고 있다. 기존 시스템은 일반적으로 예측된 사용자 선호 가능도(likelihood)로부터 행동을 선택하지만, 이러한 가능도만으로는 예측이 얼마나 신뢰할 수 있는지, 어떤 근거가 이를 지지하는지, 또는 왜 모호성이 남아 있는지를 드러내지 못한다. 본 비전 논문에서 우리는 불확실성 추정(uncertainty estimation)이 이러한 누락된 정보를 제공할 수 있으며, 이후의 적절한 행동을 상당히 변화시킬 수 있다고 주장한다. 홈 어시스턴트의 예를 사용하여, 우리는 불확실성 추정이 답하고자 하는 질문들을 소개한다. 즉, 어시스턴트가 예측된 선호 가능도에 대해 얼마나 확신하는지, 그 확신이 그룹 수준의 가정에서 오는 것인지 아니면 개별 사용자의 데이터에서 오는 것인지, 그리고 가능도의 모호성이 사용자의 본질적인 선호 변동성을 반영하는 것인지 아니면 특정 상황에 대한 데이터 부족을 반영하는 것인지이다. 우리는 또한 인간 궤적 예측(human trajectory prediction), 개인화된 행동 인식(personalized activity recognition), 정보 수집(information-collection), 모델 기반 제어(model-based control)와 같은 인접 분야에서의 불확실성 추정 응용 사례를 소개한다. 마지막으로, 우리는 인접 분야의 통찰을 바탕으로 미래의 불확실성 인지(uncertainty-aware) 능동형 어시스턴트가 능동형 상호작용에서의 주요 과제들을 어떻게 해결할 수 있을지를 전망한다.

arXiv:2610.13397v1stat.ML공통 태그 Bayesian Inference, Uncertainty Quantification

모델 프리 베이지안 클러스터링 및 다봉 사후분포 요약

Model-free Bayesian Clustering and Multimodal Posterior Summarisation

본 논문에서는 예측 베이지안(predictive Bayesian) 관점에서 클러스터링에 대한 마팅게일 사후분포(martingale posterior)를 구성하는 모델 프리(model-free) 노이즈 인식 베이지안 클러스터링 프레임워크를 개발합니다. 이 방법은 명시적인 가능도(likelihood)-사전분포 모델 명시, 비용이 큰 MCMC 샘플링, 모드 탐색적 변분 근사를 피하는 동시에 불규칙한 클러스터 형태를 수용하고 사후분포 표본의 병렬 생성을 가능하게 합니다. 고차원 노이즈 인식 클러스터링에 대한 사후분포를 해석하기 위해 와서스테인(Wasserstein) 유형의 요약 방법을 도입합니다. 새로운 노이즈 인식 손실(loss)을 활용하여 대규모 사후분포 표본 집합을 소수의 가중치 기반 대표 집합으로 압축함으로써 서로 다른 클러스터 구조와 노이즈 할당을 포착합니다. 또한 밀도 수준의 불확실성을 주변화(marginalize)하여 특정 선택에 의존하지 않도록 합니다. 제안된 손실의 이론적 성질과 수준 주변화 사후분포 근사에 대한 보장을 규명합니다. 실험 결과는 클러스터링 및 노이즈 불확실성을 포착하는 데 있어 본 프레임워크의 효과성을 입증합니다.

토론

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