Cover Image

Online Learnability of Chain-of-Thought Verifiers: Soundness and Completeness Trade-offs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Balcan, Maria-Florina, Blum, Avrim, Fragkia, Kiriaki, Li, Zhiyuan, Sharma, Dravyansh
Format:	Preprint
Published:	2026
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Learning Verifiers and Implications to Chain-of-Thought Reasoning
by: Balcan, Maria-Florina, et al.
Published: (2025)

Learning in Structured Stackelberg Games
by: Balcan, Maria-Florina, et al.
Published: (2025)

Learning accurate and interpretable tree-based models
by: Balcan, Maria-Florina, et al.
Published: (2024)

Distribution-dependent Generalization Bounds for Tuning Linear Regression Across Tasks
by: Balcan, Maria-Florina, et al.
Published: (2025)

Accelerating ERM for data-driven algorithm design using output-sensitive techniques
by: Balcan, Maria-Florina, et al.
Published: (2022)

Subsidy design for better social outcomes
by: Balcan, Maria-Florina, et al.
Published: (2024)

Sample complexity of data-driven tuning of model hyperparameters in neural networks with structured parameter-dependent dual function
by: Balcan, Maria-Florina, et al.
Published: (2025)

Algorithm Configuration for Structured Pfaffian Settings
by: Balcan, Maria-Florina, et al.
Published: (2024)

Provably tuning the ElasticNet across instances
by: Balcan, Maria-Florina, et al.
Published: (2022)

Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem
by: Blum, Avrim, et al.
Published: (2025)

The Complexity of Proper Equilibrium in Extensive-Form and Polytope Games
by: Zhang, Brian Hu, et al.
Published: (2026)

PAC Learning with Improvements
by: Attias, Idan, et al.
Published: (2025)

The Active and Noise-Tolerant Strategic Perceptron
by: Balcan, Maria-Florina, et al.
Published: (2025)

New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs
by: Balcan, Maria-Florina, et al.
Published: (2023)

Gradient Descent with Provably Tuned Learning-rate Schedules
by: Sharma, Dravyansh
Published: (2025)

The Complexity of Equilibrium Refinements in Potential Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

What Does Preference Learning Recover from Pairwise Comparison Data?
by: Pukdee, Rattana, et al.
Published: (2026)

Replicable Online Learning
by: Ahmadi, Saba, et al.
Published: (2024)

Reward Learning from Best-of-$N$ Preference Data: Targets, Tradeoffs, and Design Principles
by: Pukdee, Rattana, et al.
Published: (2026)

Fundamental Bounds on Online Strategic Classification
by: Ahmadi, Saba, et al.
Published: (2023)

Regret Minimization in Stackelberg Games with Side Information
by: Harris, Keegan, et al.
Published: (2024)

Recovering from Biased Data: Can Fairness Constraints Improve Accuracy?
by: Blum, Avrim, et al.
Published: (2019)

Offline-to-online hyperparameter transfer for stochastic bandits
by: Sharma, Dravyansh, et al.
Published: (2025)

Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances
by: Khodak, Mikhail, et al.
Published: (2023)

Spectrally Transformed Kernel Regression
by: Zhai, Runtian, et al.
Published: (2024)

A Model for Combinatorial Dictionary Learning and Inference
by: Blum, Avrim, et al.
Published: (2024)

Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
by: Blum, Avrim, et al.
Published: (2024)

Competitive strategies to use "warm start" algorithms with predictions
by: Srinivas, Vaidehi, et al.
Published: (2024)

Regularized Robustly Reliable Learners and Instance Targeted Attacks
by: Blum, Avrim, et al.
Published: (2024)

Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning
by: Sharma, Dravyansh, et al.
Published: (2025)

Learning Actionable Counterfactual Explanations in Large State Spaces
by: Naggita, Keziah, et al.
Published: (2024)

Tuning Algorithmic and Architectural Hyperparameters in Graph-Based Semi-Supervised Learning with Provable Guarantees
by: Du, Ally Yalei, et al.
Published: (2025)

Loong: Synthesize Long Chain-of-Thoughts at Scale through Verifiers
by: Huang, Xingyue, et al.
Published: (2025)

Strategic Classification under Unknown Personalized Manipulation
by: Shao, Han, et al.
Published: (2023)

Proofs as Explanations: Short Certificates for Reliable Predictions
by: Blum, Avrim, et al.
Published: (2025)

FinChain: A Symbolic Benchmark for Verifiable Chain-of-Thought Financial Reasoning
by: Xie, Zhuohan, et al.
Published: (2025)

Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
by: Li, Zhiyuan, et al.
Published: (2024)

OPV: Outcome-based Process Verifier for Efficient Long Chain-of-Thought Verification
by: Wu, Zijian, et al.
Published: (2025)

Verifying Chain-of-Thought Reasoning via Its Computational Graph
by: Zhao, Zheng, et al.
Published: (2025)

When Is Compositional Reasoning Learnable from Verifiable Rewards?
by: Barzilai, Daniel, et al.
Published: (2026)