Abstract
Large Language Models (LLMs) using chain-of-thought reasoning have demonstrated great potential for solving complex reasoning and planning tasks. However, their outputs remain unreliable and need careful verification. Even as LLMs get more accurate over time, learned verifiers can help increase trust, enforce safety constraints, and ensure alignment with personal preferences. A major challenge in learning verifiers, especially when they are used to guide generation, is that the feedback loop between generator and verifier may induce substantial distribution shift. Motivated by this challenge, we propose a framework for online learning chain-of-thought verifiers, which given a problem statement and a reasoning trace check the correctness of each reasoning step. Highlighting the asymmetric role of soundness errors (failing to flag an incorrect reasoning step) and completeness errors (incorrectly flagging a correct step as wrong), we introduce novel extensions of the Littlestone dimension which tightly characterize the mistake bounds for learning in the realizable setting. We provide optimal algorithms for finding the Pareto-frontier as well as for minimizing a linear combination of asymmetric costs. We further show how our learned verifiers can be used to boost the accuracy of a collection of weak generators and enable generation of proofs beyond what they were initially trained on. Under the mild assumption that one of the generators can generate a correct next step with a small success probability, we show how to learn a strong generator with small error and abstention rates. We additionally establish a separation between our approach and learning from offline expert demonstrations. In particular, we show that learning from offline demonstrations cannot in general achieve the soundness-completeness guarantees produced by our interactive learning approach.