Conditional Factuality Controlled LLMs with Generalization Certificates via Conformal Sampling

Large language models (LLMs) need reliable test-time control of hallucinations. Existing conformal methods for LLMs typically provide only marginal guarantees and rely on a single global threshold, which can under-cover hard prompts, over-cover easy ones, and produce oversized prediction sets. We propose Conditional Factuality Control (CFC), a black-box conformal framework that returns set-valued outputs with conditional coverage guarantees. CFC learns a continuous, feature-conditional acceptance threshold via augmented quantile regression on a latent ``success'' score (the best score among correct candidates), and uses it to filter samples at inference time. Theoretically, we show that CFC satisfies a conditional coverage guarantee under exchangeability and analyze its efficiency, proving that, under mild assumptions on the score distributions, the conditional rule is strictly more sample-efficient than marginal conformal prediction at the same target coverage. We further derive a PAC-style variant, CFC-PAC, which shrinks the nominal risk level based on a stability bound, yielding a finite-sample certificate that the conditional miscoverage deviates from the target by at most $O(\sqrt{\log(1/\delta)/N})$. Empirically, on synthetic data and real-world reasoning and QA benchmarks, CFC and CFC-PAC consistently attain near-target coverage across difficulty groups while using smaller prediction sets than CP and non-CP baselines.