Technical Summary: Abductive Reasoning with Probabilistic Commonsense

1. Problem Statement

The paper addresses the limitations of current neurosymbolic approaches to reasoning in Large Language Models (LLMs). While existing methods successfully translate natural language into formal logic and utilize solvers, they often fail because formal solvers lack access to necessary commonsense world knowledge (e.g., "white is a color").

Prior attempts to bridge this gap (e.g., LLM-Tres, ARGOS) rely on an abductive reasoning framework where the LLM generates missing premises ($L$) to make a query ($c$) logically entailed by the context ($S$). However, these methods implicitly assume a monolithic commonsense: that there exists a single, universally agreed-upon set of facts $L$ that everyone accepts as true.

The authors argue this assumption is flawed. In reality, commonsense beliefs vary across individuals. Two people may disagree on a query not due to reasoning errors, but because they hold different, yet defensible, sets of commonsense beliefs ($L_1$ vs. $L_2$) that lead to contradictory conclusions. Furthermore, assuming a monolithic commonsense makes the probability of a proposition's truth difficult to interpret, often reducing it to an uninterpretable confidence score rather than a true probability.

The Core Problem: How to determine the truth value of a query $c$ given premises $S$ when the necessary commonsense assumptions are not universally agreed upon, but vary across a population of reasoners?

2. Methodology: Probabilistic Abductive CommonSense (PACS)

The authors propose PACS, a framework that models commonsense as a probabilistic distribution over a population of reasoners rather than a single static set of facts.

2.1 Theoretical Framework

The authors define the Abductive Probability of a query $c$ being true as the expected value over the set of all humans ($R$):
$$AP(S, c) \equiv \mathbb{E}_{R} [ \mathbb{1}[S \land L(R) \vdash c] ]$$
where $L(R)$ represents the set of commonsense beliefs held by reasoner $R$. A query is considered "abductively true" if the majority of reasoners would conclude it is true.

Since the full belief vector $L$ for any individual is inaccessible, the method approximates this expectation by sampling individual "thoughts" (epistemic statements) sequentially.

2.2 The Sampling Algorithm

The algorithm treats the search for a proof as a process of sampling individual elements of a belief vector $L = (L_1, L_2, \dots, L_{|D|})$.

1. Chain Rule Sampling: The process samples beliefs one by one using the chain rule: $p(L) = p(L_1)p(L_2|L_1)\dots$.
2. Early Stopping: The sampling does not require generating the full belief vector. It stops as soon as the accumulated beliefs $\hat{l}$ combined with premises $S$ logically entail the query ($S \land \hat{l} \vdash c$) or its negation ($S \land \hat{l} \vdash \neg c$).
3. Optimization as MDP: Finding the optimal order to sample beliefs to minimize computational cost (stopping time) is formulated as a Markov Decision Process (MDP).
   • State: The current set of sampled beliefs.
   • Action: Selecting the next belief proposition to sample.
   • Reward: Minimizing the expected number of future steps to reach a conclusion.

2.3 Surrogate Score Function

Calculating the exact expected reward requires knowledge of the full distribution $p(L)$, which is intractable. The authors derive a tractable surrogate score based on model counting (the number of possible worlds satisfying the logic).
The proposed score to minimize greedily is:
$$\text{Score}(\phi(t)|S) = \#\sigma_{S \land l_{\phi(1:t)}} \times (v_{S \land \hat{l}_t} - b_{S \land \hat{l}_t}) + 1$$
Where:

• $\#\sigma$ is the number of fully constrained states reachable.
• $v$ is the total number of variables in the problem.
• $b$ is the number of variables already constrained.
  This score approximates the reduction in uncertainty, guiding the search toward the most informative commonsense assumptions.

2.4 Implementation

• LLM as Sampler: The LLM acts as a conditional sampler for the next belief proposition $l_i$.
• Beam-like Search: The algorithm samples $n$ candidate thoughts at each step but retains the top $m$ scoring paths (a beam search variant).
• Aggregation: Unlike standard beam search which selects the single highest-scoring path, PACS aggregates the results of all completed search paths. The final answer is determined by a majority vote across the conclusions of these diverse paths.

3. Key Contributions

1. Probabilistic Commonsense Framework: The paper introduces a formal definition of abductive reasoning that explicitly models the heterogeneity of human commonsense beliefs, moving away from the assumption of a monolithic truth.
2. PACS Algorithm: A novel algorithm that combines LLMs and formal logic solvers to sample diverse reasoning paths, using model counting to guide the search for minimal explanations.
3. Empirical Validation: Demonstration that modeling belief variation and aggregating diverse paths leads to higher accuracy than methods that assume a single "correct" reasoning path or rely solely on LLM confidence scores.

4. Experimental Results

The authors evaluated PACS on three datasets: FOLIO (logical reasoning), CosmosQA, and QUAIL (reading comprehension converted to true/false).

• Performance: PACS outperformed Chain-of-Thought (COT), Self-Consistency (SC), and prior neurosymbolic methods (LoT, LLM-Tres, ARGOS) on FOLIO and QUAIL.
  • On FOLIO, PACS achieved 88% accuracy (using Llama 3.3 70B), compared to 78% for the next best neurosymbolic method (ARGOS) and 73% for COT.
  • On QUAIL, PACS achieved 91%, outperforming the heuristic beam-search baseline (If-Beam) by 6%.
• Diversity and Robustness: PACS significantly reduced the percentage of problems where no correct reasoning path was found (e.g., 3% on FOLIO vs. 16% for If-Beam). This indicates PACS explores the solution space more effectively.
• Comparison with "Thinking" Models: Even when using a smaller, non-thinking model (Llama 3 8B), PACS outperformed a modern 120B "Thinking" model (GPT-OSS-120B) on FOLIO (82% vs 82% on QUAIL, but 88% vs 82% on FOLIO), suggesting that principled search algorithms can be more effective than scaling model size alone.
• Path Length: PACS found shorter reasoning paths (average length 4.6 on FOLIO) compared to If-Beam (6.7), indicating better planning and less "overthinking."

5. Significance and Claims

The paper claims that the success of PACS validates two core insights:

1. Heterogeneity is Key: Reasoning systems should not ask "What is the correct answer?" but "What would most people say is correct?" This requires summing over diverse sample rationales rather than seeking a single monolithic proof.
2. Goal-Oriented Search: Systems should not ask "What are some true statements?" but "What true statements will help me solve this problem?" This necessitates a minimization strategy (finding the shortest, most direct path) rather than exhaustive generation.

The authors conclude that their framework, despite using relatively naive assumptions (e.g., uniform distribution of solutions), demonstrates that designing concrete, principled search algorithms is a more efficient path to improving reasoning capabilities than simply fine-tuning LLMs or relying on their implicit confidence.

6. Limitations

The authors acknowledge several limitations:

• Uniformity Assumption: The derivation of the surrogate score assumes a uniform model for the distribution of reachable states ($p(\sigma_i|l)$), which is likely unrealistic.
• Translation Errors: The method relies on a pre-trained LLM to translate natural language to logic. Errors in this translation step introduce noise, particularly noted in the CosmosQA dataset where translation mistakes were more frequent.
• Scope: The paper does not explore fine-tuning a dedicated logical translation model, nor does it propose a more complex model for the belief distribution, deeming these outside the current scope.