Probabilistic Soundness Guarantees in LLM Reasoning Chains

1 Introduction

• Errors in reasoning chains include ungrounded claims, invalid derivations, and propagated errors that follow logically from an incorrect earlier claim.Source: §1 · p. 1
• Current methods that evaluate reasoning steps together can incorrectly judge a downstream step by relying on an earlier invalid step.The resulting need is to assess each step without being distracted by prior errors.Source: §1 · pp. 1–2
• ARES evaluates each reasoning step using only previously verified sound claims, retaining entailed claims and discarding non-entailed ones.For uncertain claims, retention is probabilistic based on the entailment model.Source: §1 · p. 2
• ARES uses a computationally and sample-efficient autoregressive algorithm to provide entailment certifications with rigorous statistical guarantees.Source: §1 · p. 2
• ARES accurately certifies sound and unsound steps, excels on long chains prone to propagated errors, and surpasses existing approaches across diverse reasoning tasks.Source: §1 · p. 2

2.1 Claims and Sequences of Claims

• A reasoning chain comprises claims that may range from atomic statements to extensive segments such as entire theorems or proofs.Source: §2.1 · pp. 2–3

2.2 Probabilistic Entailment of Claims

• Probabilistic entailment maps a sequence of premise claims and a hypothesis to a scalar probability, accommodating ambiguity beyond Boolean entailment.A non-entailed claim is not necessarily provably false.Source: §2.2 · p. 3

2.3 Reasoning Chains and Soundness

• A reasoning chain consists of base claims and autoregressively generated derived claims, with base claims assumed factually accurate through external validation.The method assesses whether each derived claim is soundly inferred from preceding statements.Source: §2.3 · p. 3
• Hard soundness requires every derived claim to be perfectly entailed by its predecessors, making it a strict benchmark that lacks nuanced measurement for error-prone long chains.Source: §2.3 · p. 3

3.1 Entailment with Probabilistic Premises

• Probabilistic entailment handles uncertain premises by averaging over their possible inclusion and exclusion configurations, weighted by each configuration’s probability.Each configuration is represented by a binary vector; its probability depends on the base and derived claims and the entailment model.Source: §3.1 · p. 4
• Humans’ tendency to discount dubious statements and the use of filtered contexts motivate modeling entailment over premise subsets.These observations motivate ARES’s probabilistic premise framework.Source: §3.1 · p. 4

3.2 Autoregressive Reasoning Entailment Stability with Efficient Sampling

• ARES scores each derived claim by averaging its entailment across possible soundness combinations of preceding claims.For each step, it accounts for the soundness of earlier claims rather than treating all of them as reliable.Source: §3.2 · p. 4
• Monte Carlo sampling estimates stability instead of summing over all 2^(n+k−1) premise combinations.Figure 3 depicts sequential sampling and claim inclusion, run in parallel across N instances.Source: §3.2 · p. 5, Figure 3 · p. 5
• With N ≥ log(2m/δ)/(2ε²), all estimated stability scores have error at most ε with probability at least 1−δ.The guarantee applies to any entailment model and reasoning chain.Source: §3.2 · p. 5
• A low stability score indicates a more likely error, and thresholding estimated scores can flag derived claims as erroneous.The threshold is prescribed for the error-detection procedure.Source: §3.2 · p. 5

4.1 RQ1: Does ARES work better than baseline methods on Benchmarks?

• ARES is top-performing in 5/8 benchmark settings, with no other single method a consistent challenger; it achieves the best Macro-F1 on both PRMBench and DeltaBench with GPT-4o-mini.For Qwen3-4B, Entail-Base performs slightly better while the other methods lag behind.Source: Table 1 · p. 6, §4.1 · p. 6

4.2 RQ2: In what setting does ARES identify more errors than baselines?

• ARES maintains at least 89% Macro-F1 on ClaimTrees chains up to 50 steps, while baselines fall to 30–40% after only a few steps.The controlled datasets remove a key base claim to create unsound derivations and track how the resulting error propagates.Source: §4.2 · p. 7, Figure 4 · p. 7

4.3 RQ3: Is ARES computationally efficient?

• ARES uses 0.03x–0.31x of the theoretical sample bound in practice, and its performance remains stable with fewer samples.For sequence length m = 10, increasing ε to 0.4 reduces samples from 265 to 17 per step without significant performance change.Source: Figure 5 · p. 7, §4.3 · pp. 7–8, Table 3 · p. 8

4.4 RQ4: Is ARES useful for selecting Best-of-N generations?

• ARES significantly outperforms all other methods at selecting the correct chain when selection uses the final-step score.This stricter metric contrasts with averaging all step scores; Entail-Prev collapses on it.Source: Table 4 · p. 8, §4.4 · p. 8

4.5 Ablations

• ARES remains stable across ClaimTrees widths and depths, whereas baselines degrade more with depth than with width.This supports filtering irrelevant claims and identifies long-chain error propagation as a primary reason other approaches fail.Source: §4.5 · p. 8
• With probabilistic entailment, p = 1 performs best and avoids resampling base claims; binary models sometimes benefit from p < 1.The p = 1 choice is often accurate and efficient, though ambiguity in entailment can change the outcome.Source: §4.5 · pp. 8–9
• All methods perform equally well on benign errors, unlike the irrelevant-claim setting where baselines degrade.Source: §4.5 · pp. 8–9

4.6 Discussion of Errors

• ARES can improve only entailment models that already perform correct entailment; other methods have distinct failure patterns across tasks.Entail-Base struggles on long math derivations and very long chains; pairwise methods miss complex errors requiring multiple premise claims.Source: §4.6 · p. 9

Guarantees for Single-Step Explanations

• Interpretability research includes inherently interpretable models and post-hoc methods with guarantees such as optimality, faithfulness, conservation, precision, and stability.Source: §5 · p. 9

Guarantees and Verification for Multi-Step Reasoning

• ARES extends stability guarantees to LLM reasoning chains, addressing a literature in which statistical reliability methods focus on isolated predictions within a chain.Source: §5 · p. 9
• Multi-step error detection includes self-consistency checkers, LLM judges, process reward models, entailment models, and logic-based verifiers, often without formal guarantees or with pairwise and propagation limitations.Source: §5 · p. 9

• Current methods cannot reliably detect propagation errors in LLM reasoning chains.Source: §6 · p. 9
• ARES quantifies each claim’s soundness through autoregressive sampling, providing a fine-grained inductive guarantee on overall chain reliability.Source: §6 · p. 9
• ARES robustly identifies errors in lengthy, complex reasoning chains where existing methods fail due to error propagation.Source: §6 · p. 9

Limitations

• ARES depends on entailment-model quality: poor calibration can make its scores unreliable.The authors note that better-calibrated components, including through temperature scaling, can be substituted.Source: Limitations · p. 10
• ARES is more computationally intensive than simpler approaches, despite an efficient sampling algorithm.The approach also assumes claims are already decomposed and does not detect errors at the sub-claim level; addressing this is left for future work and would increase computational costs.Source: Limitations · p. 10
• Evaluation across four datasets and two models demonstrates effectiveness across domains but is not exhaustive.The authors also note that better LLM prompts could improve performance.Source: Limitations · p. 10

Ethical Considerations

• Probabilistic sampling may limit accessibility, while undetected errors could create false confidence and propagate bias; the authors recommend human oversight in high-stakes use.They name healthcare and legal applications as examples and call for evaluation across diverse domains.Source: Ethical Considerations · p. 10

Potential Risks

• ARES’s probabilistic sampling adds computational overhead, although an efficient algorithm mitigates it.The required computing resources may limit accessibility to well-resourced institutions.Source: Potential Risks · p. 10
• Undetected errors may create false confidence in LLM reasoning, and biases may propagate through certified reasoning chains.The authors call for evaluation across diverse domains and say human oversight remains essential in high-stakes applications such as healthcare and law.Source: Potential Risks · p. 10

A Proofs

• With N ≥ log(2m/δ)/(2ε^2), all m stability estimates have error at most ε with probability at least 1 − δ.The proof invokes Boole’s and Hoeffding’s inequalities.Source: A Proofs · p. 13

B Method

• ARES is the only evaluated method that satisfies the robust, causal, and sufficient error-detection desiderata.The table defines these as resistance to previous errors, independence from downstream steps, and inclusion of all relevant claims as premises.Source: B Method · p. 13, Table A5 · p. 14

C.1 Entailment Model

• The entailment model scores whether a premise supports a hypothesis, with binary or seven-point Likert outputs and an inverted mapping for contradiction judgments.The model returns a scalar probability for entailment.Source: §C.1 · pp. 13–14

C.2 Hyperparameters for ARES

• ARES experiments use δ = 0.1, ε = 0.1, and a base-claim inclusion rate of p = 0.95.The prompts were manually tuned, with simpler prompts preferred for DeltaBench and more specified prompts for other datasets.Source: §C.2 · p. 14

C.3 Experiment Details

• Reported experiment results use five-fold cross-validation, validation-selected Macro-F1 thresholds, and test scores averaged across folds.Standard deviations are reported over the five folds.Source: §C.3 · p. 14

C.4 Licenses for Artifacts

• Released code and evaluation scripts use the MIT license, while reused artifacts retain their original authors’ terms.The authors say created artifacts may be freely used, modified, and redistributed under MIT.Source: §C.4 · p. 14

C.5 Controllable Datasets

• ClaimTrees varies chain length and error position, while CaptainCookRecipes induces unsound claims by dropping required ingredients and propagating their effects.On an example with propagated errors, only ARES captures all errors.Source: §C.5 · p. 15

C.6 Computing Resources / C.7 Best-of-N Results

• GPT-4o-mini prototyping and experiments cost approximately 600 USD total; Table A6 presents PRMBench best-of-N results with standard deviations and describes ARES as a strong, robust predictor of downstream task performance.Source: §C.6 · p. 15, §C.7 · p. 15, Table A6 · p. 15

C.8 Ablations

• In depth-5 trees with 3 sources, other methods drop more than ARES; as depth increases, their error rates rise while ARES remains stable.On wide trees, other methods drop less; ARES is especially stable against greater depth.Source: §C.8 · p. 16, Table A9 · p. 18
• All methods perform equally well when inserted errors do not cause downstream propagation.These are non-existing rules inserted into reasoning chains that do not affect later steps.Source: §C.8 · p. 16, Table A10 · p. 19
• With probabilistic entailment, p = 1 consistently outperforms p = 0.95; including all base claims reduces computation because effective sample size depends only on derived-claim entailment.A binary entailment model sometimes benefits from p = 0.95.Source: §C.8 · p. 16

C.9 ARES Also Improves PRMs

• ARES significantly improves a specialized PRM on ClaimTrees with many propagated errors and performs on par with PRM on out-of-domain CaptainCook4D.The PRM is a strong baseline on its in-domain PRMBench dataset.Source: §C.9 · p. 16, Table A7 · p. 16

D AI Assistants in Research

• The authors used AI assistants to support coding frameworks, generate visualizations, and revise writing for clarity and readability.Source: D AI Assistants in Research · p. 16