A note on the impossibility of conditional PAC-efficient reasoning in large language models

• URL: http://arxiv.org/abs/2512.03057v1
• Date: Tue, 25 Nov 2025 17:08:08 GMT
• Title: A note on the impossibility of conditional PAC-efficient reasoning in large language models
• Abstract summary: 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.
• Score: 2.9174099783289296
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove an impossibility result for conditional Probably Approximately Correct (PAC)-efficient reasoning in large language models. While recent work has established marginal PAC efficiency guarantees for composite models that switch between expensive expert models and cheaper fast models, we show that conditional (pointwise) guarantees are impossible in the distribution-free setting. Specifically, for non-atomic input spaces, any algorithm achieving conditional PAC efficiency must be trivial in the sense that it defers to the expert model with probability at least $1-α$ for almost every input.

Related papers

• Mitigating Bias in Locally Constrained Decoding via Tractable Proposals [73.78736135699953]
  Existing locally constrained decoding approaches enforce constraints by myopically masking out next tokens.<n>Recent work uses sequential Monte Carlo methods to mitigate such biases, but designing effective proposal distributions or potential functions remains a key challenge.<n>We propose a generic approach to construct proposals and potentials for SMC sampling from $p_mathrmlm( cdot mid mathrmconstraint)$.
  arXiv  Detail & Related papers  (2026-06-01T08:58:18Z)
• Conditional Performance Guarantee for Large Reasoning Models [33.71268958080582]
  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.
  arXiv  Detail & Related papers  (2026-01-30T10:09:41Z)
• C3PO: Optimized Large Language Model Cascades with Probabilistic Cost Constraints for Reasoning [24.65381108650337]
  Large language models (LLMs) have achieved impressive results on complex reasoning tasks, but their high inference cost remains a major barrier to real-world deployment.<n>Existing cascade methods rely on supervised training with labeled data, offer no theoretical generalization guarantees, and provide limited control over test-time computational cost.<n>We introduce C3PO, a self-supervised framework for optimizing LLM cascades under probabilistic cost constraints.
  arXiv  Detail & Related papers  (2025-11-10T18:50:27Z)
• Syntactic Control of Language Models by Posterior Inference [53.823006836309695]
  Controlling the syntactic structure of text generated by language models is valuable for applications requiring clarity, stylistic consistency, or interpretability.<n>We argue that sampling algorithms based on the posterior inference can effectively enforce a target constituency structure during generation.<n>Our approach combines sequential Monte Carlo, which estimates the posterior distribution by sampling from a proposal distribution, with a syntactic tagger that ensures that each generated token aligns with the desired syntactic structure.
  arXiv  Detail & Related papers  (2025-06-08T14:01:34Z)
• Provably Sample-Efficient Robust Reinforcement Learning with Average Reward [4.530028899565083]
  We propose a new algorithm designed for robust Markov Decision Processes (MDPs) with transition uncertainty characterized by $ell_p$-norm and contamination models.<n>Our algorithm operates without requiring any prior knowledge of the robust MDP.<n>Our work provides essential theoretical understanding of sample efficiency of robust average reward RL.
  arXiv  Detail & Related papers  (2025-05-18T15:34:45Z)
• Improving Large Models with Small models: Lower Costs and Better Performance [81.55672406002715]
  We propose Data Shunt$+$ (DS$+$), a general paradigm for collaboration of small and large models. For instance, ChatGPT achieves an accuracy of $94.43%$ on Amazon Product sentiment analysis, and DS$+$ achieves an accuracy of $95.64%$, while the cost has been reduced to only $31.18%$.
  arXiv  Detail & Related papers  (2024-06-15T14:44:43Z)
• Faster Cascades via Speculative Decoding [66.16909847419198]
  Cascades and speculative decoding are approaches to improving language models' inference efficiency. We propose new speculative cascading techniques that implement their deferral rule through speculative execution. We show that our approach yields better cost quality trade-offs than cascading and speculative decoding baselines.
  arXiv  Detail & Related papers  (2024-05-29T16:55:08Z)
• Probabilistic Circuits with Constraints via Convex Optimization [2.6436521007616114]
  The proposed approach takes both a PC and constraints as inputs, and outputs a new PC that satisfies the constraints. Empirical evaluations indicate that the combination of constraints and PCs can have multiple use cases.
  arXiv  Detail & Related papers  (2024-03-19T19:55:38Z)
• 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)
• Training and Inference on Any-Order Autoregressive Models the Right Way [97.39464776373902]
  A family of Any-Order Autoregressive Models (AO-ARMs) has shown breakthrough performance in arbitrary conditional tasks. We identify significant improvements to be made to previous formulations of AO-ARMs. Our method leads to improved performance with no compromises on tractability.
  arXiv  Detail & Related papers  (2022-05-26T18:00:02Z)
• PSD Representations for Effective Probability Models [117.35298398434628]
  We show that a recently proposed class of positive semi-definite (PSD) models for non-negative functions is particularly suited to this end. We characterize both approximation and generalization capabilities of PSD models, showing that they enjoy strong theoretical guarantees. Our results open the way to applications of PSD models to density estimation, decision theory and inference.
  arXiv  Detail & Related papers  (2021-06-30T15:13:39Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)

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.