Conditional Performance Guarantee for Large Reasoning Models

• URL: http://arxiv.org/abs/2601.22790v1
• Date: Fri, 30 Jan 2026 10:09:41 GMT
• Title: Conditional Performance Guarantee for Large Reasoning Models
• Abstract summary: Group PAC (G-PAC) and Clustered PAC (C-PAC) reasoning for unknown groupings are presented.<n>G-PAC and C-PAC successfully achieve group-conditional risk control while maintaining substantial computational savings.
• Score: 33.71268958080582
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large reasoning models have shown strong performance through extended chain-of-thought reasoning, yet their computational cost remains significant. Probably approximately correct (PAC) reasoning provides statistical guarantees for efficient reasoning by adaptively switching between thinking and non-thinking models, but the guarantee holds only in the marginal case and does not provide exact conditional coverage. We propose G-PAC reasoning, a practical framework that provides PAC-style guarantees at the group level by partitioning the input space. We develop two instantiations: Group PAC (G-PAC) reasoning for known group structures and Clustered PAC (C-PAC) reasoning for unknown groupings. We prove that both G-PAC and C-PAC achieve group-conditional risk control, and that grouping can strictly improve efficiency over marginal PAC reasoning in heterogeneous settings. Our experiments on diverse reasoning benchmarks demonstrate that G-PAC and C-PAC successfully achieve group-conditional risk control while maintaining substantial computational savings.

Related papers

• Too Correct to Learn: Reinforcement Learning on Saturated Reasoning Data [55.84428098924793]
  We propose Constrained Uniform Top-K Sampling (CUTS), a parameter-free decoding strategy enforcing structure-preserving exploration.<n>We integrate this into Mixed-CUTS, a training framework synergizing exploitative and exploratory rollouts to amplify intra-group advantage variance.<n> Notably, Mixed-CUTS improves Pass@1 accuracy on the challenging AIME25 benchmark by up to 15.1% over standard GRPO.
  arXiv  Detail & Related papers  (2026-04-20T16:43:28Z)
• Conditional Factuality Controlled LLMs with Generalization Certificates via Conformal Sampling [7.974834731988445]
  We propose emphConditional Factuality Control (CFC) for large language models (LLMs)<n>CFC defines a continuous, feature-conditional acceptance threshold through augmented quantile regression on a latent success'' score.<n>We show that CFC satisfies a conditional coverage guarantee under exchangeability and analyze its emphefficiency<n>We derive a PAC-style variant, CFC-PAC, which shrinks the nominal risk level based on a stability bound.
  arXiv  Detail & Related papers  (2026-03-28T20:48:13Z)
• DARC: Disagreement-Aware Alignment via Risk-Constrained Decoding [59.16244104797919]
  We propose **Disagreement-Aware Alignment via Risk-Constrained Decoding (DARC)**.<n>DARC frames response selection as distributionally robust, risk-sensitive decision making.<n>Experiments on alignment benchmarks show that DARC reduces disagreement and tail risk while maintaining competitive average quality.
  arXiv  Detail & Related papers  (2026-03-09T09:21:29Z)
• PAC-Bayesian Generalization Guarantees for Fairness on Stochastic and Deterministic Classifiers [8.438034474012044]
  We propose a PAC-Bayesian framework for deriving generalization bounds for fairness.<n>Our framework has two advantages: (i) It applies to a broad class of fairness measures that can be expressed as a risk discrepancy, and (ii) it leads to a self-bounding algorithm.
  arXiv  Detail & Related papers  (2026-02-12T08:49:34Z)
• Outcome-Grounded Advantage Reshaping for Fine-Grained Credit Assignment in Mathematical Reasoning [60.00161035836637]
  Group Relative Policy Optimization has emerged as a promising critic-free reinforcement learning paradigm for reasoning tasks.<n>We introduce Outcome-grounded Advantage Reshaping (OAR), a fine-grained credit assignment mechanism that redistributes advantages based on how much each token influences the model's final answer.<n>OAR-G achieves comparable gains with negligible computational overhead, both significantly outperforming a strong GRPO baseline.
  arXiv  Detail & Related papers  (2026-01-12T10:48:02Z)
• On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference [71.09125259964684]
  Test-time compute (TTC) has become an increasingly prominent paradigm for enhancing large language models (LLMs)<n>We study reward-filtered sequential inference, a simple procedure that selectively incorporates only high-reward generations into the context.<n>On the theoretical side, we show that reward-filtered sequential inference yields strictly stronger guarantees than standard TTC paradigms.
  arXiv  Detail & Related papers  (2025-12-04T08:21:33Z)
• A note on the impossibility of conditional PAC-efficient reasoning in large language models [2.9174099783289296]
  We show that conditional PAC efficiency guarantees are impossible in the distribution-free setting.<n> Specifically, for non-atomic input spaces, any algorithm achieving conditional PAC efficiency must be trivial.
  arXiv  Detail & Related papers  (2025-11-25T17:08:08Z)
• C$^2$GSPG: Confidence-calibrated Group Sequence Policy Gradient towards Self-aware Reasoning [54.705168477975384]
  Group Sequence Policy Gradient (GSPG) framework for learning reasoning models.<n>C$2$GSPG simultaneously enhances reasoning performance while suppressing overconfidence.
  arXiv  Detail & Related papers  (2025-09-27T05:24:51Z)
• Breaking the Gaussian Barrier: Residual-PAC Privacy for Automatic Privatization [27.430637970345433]
  We show that the upper bound obtained by PAC Privacy algorithms is tight if and only if the perturbed mechanism output is jointly Gaussian with independent noise.<n>We introduce Residual-PAC (R-PAC) Privacy, an f-divergence-based measure to quantify privacy that remains after adversarial inference.<n>Our approach achieves efficient privacy budget utilization for arbitrary data distributions and naturally composes when multiple mechanisms access the dataset.
  arXiv  Detail & Related papers  (2025-06-06T20:52:47Z)
• PixelThink: Towards Efficient Chain-of-Pixel Reasoning [70.32510083790069]
  PixelThink is a simple yet effective scheme that integrates externally estimated task difficulty and internally measured model uncertainty.<n>It learns to compress reasoning length in accordance with scene complexity and predictive confidence.<n> Experimental results demonstrate that the proposed approach improves both reasoning efficiency and overall segmentation performance.
  arXiv  Detail & Related papers  (2025-05-29T17:55:49Z)
• Towards Efficient Contrastive PAC Learning [6.209600119671225]
  We study contrastive learning under the PAC learning framework.<n>In this paper, we consider contrastive learning of the fundamental concept of linear representations.<n>We establish guarantees based on Rademacher complexity, and connect it to PAC guarantees under certain contrastive large-margin conditions.
  arXiv  Detail & Related papers  (2025-02-21T21:51:01Z)
• PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison [38.76324445090305]
  PAC-Bayes has recently re-emerged as an effective theory with which one can derive principled learning algorithms with tight performance guarantees. Many decision-making problems in healthcare, finance and natural sciences can be modelled as bandit problems. This survey provides an overview of PAC-Bayes bounds for bandit problems and an experimental comparison of these bounds.
  arXiv  Detail & Related papers  (2022-11-29T11:34:35Z)
• PAC Verification of Statistical Algorithms [0.10878040851637999]
  We develop the setting of PAC verification, where a hypothesis (machine learning model) that purportedly satisfies the agnostic PAC learning objective is verified using an interactive proof. We present a protocol for PAC verification of unions of intervals over $mathbbR$ that improves upon their proposed protocol for that task, and matches our lower bound's dependence on $d$. Our final result is a protocol for the verification of statistical algorithms that satisfy a constraint on their queries.
  arXiv  Detail & Related papers  (2022-11-28T23:57:27Z)
• Robust Optimization for Fairness with Noisy Protected Groups [85.13255550021495]
  We study the consequences of naively relying on noisy protected group labels. We introduce two new approaches using robust optimization. We show that the robust approaches achieve better true group fairness guarantees than the naive approach.
  arXiv  Detail & Related papers  (2020-02-21T14:58:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.