Maieutic Prompting: Logically Consistent Reasoning with Recursive Explanations

In plain words

Language models often contradict themselves. A model may call a statement true and also call its negation true, and the explanations it writes can be just as shaky. Maieutic Prompting takes its name from Socrates' method of questioning, which removes hypotheses that lead to contradictions. The idea is to have the model argue both sides instead of picking one.

For a yes/no statement, the model writes a reason that the statement is true and a reason that it is false. Each reason is then treated as a new statement and argued both ways, which builds a small tree of claims. A branch is kept only when the model's verdicts on a claim and on its negation disagree, a sign that the model holds that claim with some confidence. Pairs of claims are then checked for support or contradiction by a small language-inference model. Last, a constraint solver looks for the set of true and false labels that best fits all the claims and their links, and the label of the original statement is the answer.

The language model itself is not trained for this, and the authors call the approach unsupervised. The checker model that judges the links is trained on another task, so the method is not training-free end to end.

TL;DR

Maieutic Prompting asks a few-shot language model to argue both True and False for a yes/no claim, recursively to depth 2, then solves a weighted MAX-SAT over belief and NLI-based consistency to pick the answer. It targets commonsense reasoning and fact verification. With GPT-3 text-davinci-001, the authors report 72.5 on Com2Sense dev, above every prompting baseline in their table, and 85.3 on CREAK test. The official code is Apache-2.0, but its scripts do not run as shipped (see Paper vs code).

Problem

Explanation-based prompting asks a model to write an explanation before its answer, which helps on several reasoning tasks §1 §2. The authors inspected 100 GPT-3 answers to CSQA 2.0 questions and found three failure types: the explanation does not lead to the inferred answer, the model gives the same label to a statement and its negation, and the model contradicts its own explanation fig. 1 §1.

Three formulations frame the problem. Standard few-shot prompting picks the more likely of True or False given the question and k demonstrations eq. 1 §2. Explanation-based prompting marginalises over an explanation E eq. 2 and in practice samples one explanation and conditions the answer on it eq. 3 §2. Sampling several explanations and taking a majority over answers is brittle, because each answer still depends on single-step explanations being correct §3.1.2.

The method is inspired by the maieutic method of Socrates, which eliminates hypotheses that lead to contradictions §1. Its key claim is that inference should depend on the depth of reasoning, meaning whether reasoning paths are consistent with each other, and not only on how many explanations were sampled §3.1.2.

Scope: the experiments only validate a given statement as true or false. Multiple-choice tasks would need binarised options, which the authors leave to future work [Limitations].

Method

Notation. Q is a statement, E a generated explanation, ¬E its negation, and C the few-shot demonstrations. Each node of the tree is one proposition. The method has four parts: tree generation, integrity and belief, pairwise relations, and inference.

1. Abductive explanations §3.1.1. The model is prompted with Q and the phrase "True, because" to produce E_T, and with "False, because" to produce E_F. Both come from eq. 5. Giving the label before the explanation is meant to elicit more specific reasons than writing an explanation first and then choosing a label §3.1.1.

2. Recursive spanning in depth §3.1.2. Each explanation becomes the question for the next level, so the level sets follow eq. 6. Several samples per (question, answer) pair give breadth through nucleus sampling §3.1.2. The result is a tree.

3. When to stop §3.1.3 alg. 1 app. A. A branch stops growing once it reaches an integral proposition. The tree is built to a maximum depth, and then every leaf that is still non-integral is removed together with its ancestors, so only branches ending in an integral leaf remain.

4. Logical integrity §3.1 eq. 4. A proposition E is integral when the model answers True for E and False for ¬E, or False for E and True for ¬E. The negation is made by prefixing a phrase such as "It is wrong to say that", or by asking the model to negate the statement §3.1, footnote 1.

5. Belief §3.2 eq. 7. The belief w_E is a signed, normalised difference between the model's True probabilities for E and for ¬E. The probabilities were already computed for the integrity test, so no extra prompts are needed §3.2.

6. Consistency §3.2 eq. 8. The paper also defines a likelihood-based consistency. It compares how likely E is under its own answer with how likely it is under the opposite answer. The main method does not use it. The ablation replaces it with the NLI version below §3.4 tab. 2.

7. NLI relations §3.4 eq. 13. Because the likelihood check only compares a parent with its child, a verifier model is used for every ordered pair of distinct nodes, across branches too. An NLI model labels the pair as entailment, contradiction or neutral. Entailment gives the clause E1 → E2, contradiction gives E1 → ¬E2, and neutral gives no clause. The weight of each NLI clause is fixed to 1; using the NLI probability as weight gave worse results §3.4, footnote 2.

8. Inference as weighted MAX-SAT §3.3 eq. 9 eq. 10 eq. 11 eq. 12. Each leaf gives a unary belief clause: the leaf itself if it is integral and True, its negation if it is integral and False. Each edge gives a binary consistency clause. The objective is to choose truth values for all nodes, including the root Q, that maximise the total weight of satisfied clauses. The problem is solved with an off-the-shelf weighted MAX-SAT solver §3.3. The answer is the truth value given to Q §3.3.

The method needs no fine-tuning of the language model and runs with any few-shot prompt-able model §1. The experiments use GPT-3 text-davinci-001 as that model §4.

Pseudocode for tree generation (paper's depth and width; see Paper vs code for the code's choices):

# Maieutic tree generation  [alg. 1] [app. A]
# Input: statement Q, max depth D (2 in the paper)
# Output: tree whose leaves are all logically integral

def build_maieutic_tree(Q, max_depth):
    # The root holds the statement  [§3.1]
    tree = new_tree(root=Q)
    for depth in range(1, max_depth + 1):
        # Expand only leaves that are not yet integral  [§3.1.3]
        for node in non_integral_leaves(tree):
            # Abduce a True and a False explanation  [§3.1.1] [eq. 5]
            # Samples per answer: 3 at depth 1, 1 at depth 2  [§4]
            for answer in ["True", "False"]:
                for explanation in abduce(node.text, answer, depth):
                    # Score the new node: belief and integrity  [§3.1]
                    add_child(tree, node, explanation)
    # Keep only branches that end in an integral leaf  [§3.1.3] [alg. 1]
    return prune_non_integral_leaves(tree)

Pseudocode for integrity and belief of one statement:

# Belief and integrity of one statement E  [§3.1] [eq. 4] [eq. 7]
# Input: statement E; the LM with few-shot demonstrations C
# Output: belief w_E, integrity flag, and the verdict on E

def belief_and_integrity(statement):
    # Negation by a prefix or an LM rewrite  [§3.1, footnote 1]
    negated = negate(statement)
    # Probability the LM answers True for each  [§3.1] [eq. 7]
    p_true_statement = p_true(statement)    # p(T | E, C)
    p_true_negated = p_true(negated)        # p(T | not E, C)
    # Verdict = argmax over {True, False} for each  [eq. 4]
    verdict_statement = answer(statement)
    verdict_negated = answer(negated)
    # Integral when the two verdicts differ  [eq. 4]
    integral = verdict_statement != verdict_negated
    # Signed, normalised difference of the two probabilities  [eq. 7]
    belief = (p_true_statement - p_true_negated) / (
        p_true_statement + p_true_negated
    )
    return belief, integral, verdict_statement

Pseudocode for inference over the pruned tree:

# Inference over the pruned tree  [§3.2] [§3.3] [§3.4]
# Every node, including the root Q, is one boolean variable
# Input: tree T, NLI verifier; Output: truth value of Q

def infer_root_label(tree, nli_model):
    clauses = []
    for leaf in leaves(tree):
        # Unary belief clause from the verdict  [eq. 9]
        literal = leaf.var if leaf.verdict == "True" else -leaf.var
        # Weight is the belief magnitude; the sign rule is not stated  [eq. 12]
        clauses.append(soft([literal], weight=abs(leaf.belief)))
    for first, second in ordered_pairs(all_nodes(tree)):
        # NLI label for the ordered pair  [§3.4] [eq. 13]
        label = nli_model.predict(first.text, second.text)
        if label == "entailment":
            # first -> second, weight fixed to 1  [§3.4]
            clauses.append(soft([-first.var, second.var], weight=1))
        if label == "contradiction":
            # first -> not second, weight fixed to 1  [§3.4]
            clauses.append(soft([-first.var, -second.var], weight=1))
    # Maximise the total weight of satisfied clauses  [§3.3] [eq. 12]
    assignment = weighted_max_sat(clauses)
    # The root's truth value is the answer  [§3.3]
    return assignment[tree.root.var]

Key equations, in the paper's notation §2 §3:

\hat{A} = \underset{A \in \{T, F\}}{\arg\max}\, p_{LM}(A \mid Q, C) eq. 1

\hat{A} = \underset{A \in \{T, F\}}{\arg\max} \int_{E} p_{LM}(A \mid Q, E, C)\, p_{LM}(E \mid Q, C) eq. 2

E \sim p_{LM}(E \mid Q, C), \quad \hat{A} = \underset{A \in \{T, F\}}{\arg\max}\, p_{LM}(A \mid Q, E, C) eq. 3

\mathtt{integral}(E) = 1 \text{ iff } \big(\arg\max_A p_{LM}(A \mid E, C) = T \text{ and } \arg\max_A p_{LM}(A \mid \neg E, C) = F\big) \text{ or } \big(\arg\max_A p_{LM}(A \mid E, C) = F \text{ and } \arg\max_A p_{LM}(A \mid \neg E, C) = T\big) eq. 4

\mathtt{abduction}(Q) = (E_T, E_F), \quad E_A \sim p_{LM}(E \mid Q, A, C) eq. 5

S_i \subseteq \bigcup_{l \in \{T,F\}^{i-1}} \{E_{lT}, E_{lF}\}, \quad (E_{lT}, E_{lF}) = \mathtt{abduction}(E_l) eq. 6

w_E = \frac{p_{LM}(T \mid E, C) - p_{LM}(T \mid \neg E, C)}{p_{LM}(T \mid E, C) + p_{LM}(T \mid \neg E, C)} eq. 7

w_{E,Q,A} = \frac{p_{LM}(E \mid Q, A, C)}{p_{LM}(E \mid Q, A, C) + p_{LM}(E \mid Q, \neg A, C)} eq. 8

c_{blf} = \begin{cases} E & \text{if } E \text{ is integral and True} \\ \neg E & \text{if } E \text{ is integral and False} \end{cases} eq. 9

\mathcal{C}_{blf} = \{\, c_{blf} \mid E \in \mathrm{leaf}(\mathcal{T}) \,\} eq. 10

c_{con} = \begin{cases} E_{lA} \rightarrow E_l & \text{if } A = T \\ E_{lA} \rightarrow \neg E_l & \text{if } A = F \end{cases}, \quad \mathcal{C}_{con} = \{\, c_{con} \mid (E_l, E_{lA}) \in \mathrm{edge}(\mathcal{T}) \,\} eq. 11

\max \sum_{c \in \mathcal{C}_{blf} \cup \mathcal{C}_{con}} w_c \cdot \mathbb{1}[c = \text{True}] eq. 12

\mathrm{Entail}(E_1, E_2): E_1 \rightarrow E_2; \qquad \mathrm{Contradict}(E_1, E_2): E_1 \rightarrow \neg E_2 eq. 13

Equation numbers follow the order of the numbered equations in the LaTeX source; the compiled PDF was not checked.

Hyperparameters

Values marked "not stated" do not appear in the paper. Code values come from the official repository at code_commit.

Results

Author-reported. Setup: binary QA on Com2Sense, CSQA 2.0 and CREAK; dev and test splits; GPT-3 text-davinci-001 for all prompting rows; supervised rows are fine-tuned models taken from prior work §4 tab. 1. Hardware: not stated. Pairwise accuracy (Com2Sense test) and contrast-set accuracy (CREAK) pair each question with its near-opposite §4.2.

Source: tab. 1 §4.1. The paper's own statements: the method beats all prompting methods, and it is the only prompting method that beats the smallest supervised baseline (RoBERTa-large) on Com2Sense and CREAK §4.1.

Gaps against the best prompting baseline in the table, computed from the table: Com2Sense dev +10.7 (GKP 61.8), CSQA 2.0 dev +8.7 (Self-consistency 60.8), CREAK dev +9.8 (GKP 75.4), CREAK contrast +9.2 (GKP 68.2) tab. 1.

Ablation on Com2Sense dev tab. 2 §4.3:

Tree size on Com2Sense dev tab. 3 §4.3. The table gives depth values (width not stated for this row) and width values; which setting fixes the other dimension is not stated.

The authors say accuracy saturates past a threshold, which they attribute to topic drift at greater depth and to overlap between samples at greater width §4.3.

StrategyQA dev, multi-hop extension tab. 5 app. C. Standard 56.3; chain of thought 58.2; Maieutic Prompting 60.7; chain of thought with decomposition 57.9; Maieutic Prompting with decomposition 61.4. The benchmark setting assumes Wikipedia access, which the authors say makes it a weak test for few-shot methods app. C.

Robustness fig. 4 §4.2: on Com2Sense dev, the method is run with 3 few-shot sets and 5 permutations. The text says Self-consistency and Maieutic Prompting are much more stable than the other two methods, and that Maieutic has slightly less variance; figure values are not tabulated.

Human evaluation fig. 5 §4.4: six NLP experts rated 100 CSQA 2.0 dev examples, half answered correctly and half not. Over 99% of the true explanations are grammatical. Among wrongly answered examples, 42% of the true explanations are fully factual and 23% are fully helpful for the correct answer. Krippendorff's alpha is 0.64.

Figure 6 shows case studies with correct and wrong answers fig. 6. Figures 7 to 10 in Appendix D show inference trees for two correct and two wrong examples app. D. No image is used here.

Paper vs code

Official code: jaehunjung1/Maieutic-Prompting, linked from a footnote to the abstract; the owner is the first author. Commit bf8bbbf9dfd8e743aa4d8317fa526ce999358344. Apache-2.0 LICENSE. The discrepancies below were checked by reading the code; none were run, because the scripts need the legacy OpenAI completion API and cannot run as shipped.

1. Depth-2 decoding. Paper: greedy, one explanation per answer and parent §4. Code: temperature 0.5 with one sample per answer and parent generation.py. The paper's depth-2 setting is therefore sampling in the code.
2. Where the answer comes from. Paper: the root Q is a MAX-SAT variable and its truth value is the answer §3.3 eq. 12. Code: Q is excluded from the solver inference.py. The answer is the sign of the summed NLI scores between the nodes the solver accepts and Q, or Q̃ inference.py main_inference.py. The paper's root-variable scheme is not what the code runs.
3. Integrity test. Paper: argmax verdicts on E and ¬E must disagree eq. 4. Code: the absolute gap between the two "true" probabilities must exceed 0.45 generation.py, using the exponentiated log-probability of the token " true" alone generation.py. A node is non-integral if the phrase "Therefore, the statement is" is missing or if " true" is not among the returned top logprobs generation.py.
4. Verdicts versus belief sign. Paper: the leaf clause uses the integral verdict, True or False eq. 9. Code: the sign comes from comparing the two probabilities inference.py and the NLI clauses use the negated text for nodes whose negation is more believed inference.py. Both choices change the clauses for some nodes; the paper does not say the code's choices are equivalent.
5. Expansion rule in Algorithm 1 versus the text. Algorithm 1 expands a node when integral(E) = 1 alg. 1 line 12 app. A. The text says integral nodes stop growing and non-integral leaves are expanded §3.1.3. The code expands non-integral leaves generation.py, as the text says. Follow the text, not the algorithm box.
6. Likelihood-based consistency. Paper defines it eq. 8 and reports it as an ablation tab. 2. The code has no implementation of eq. 8; it only computes NLI consistency inference.py.
7. Filtering of generated explanations. Not in paper. Code keeps only explanations ending in ".", capitalises the first letter, falls back to the first sample if none qualify, and removes duplicates generation.py.
8. Question rewriting and Q̃. Not in paper. Code can rewrite the question into a declarative statement and generate its negation with the LM generation.py. The main script uses the precomputed Q and Q̃ from the data files main_generate.py.
9. Degenerate trees. Not in paper. If pruning leaves only the root, the answer is p(True | Q) ≥ p(True | Q̃) main_inference.py. A tie in the summed scores is read as True main_inference.py.
10. Prompt paths. The prompt path table names generator/prompts/..., but the directory is generation/prompts/... generation_config.py generation_config.py generation_config.py. As shipped, prompt loading fails.
11. Script bugs. main_generate.py and main_inference.py read args.datset_name, a typo for dataset_name main_generate.py main_inference.py. main_inference.py imports NLIModel from inference.nli, but the class is in inference/verifier.py main_inference.py verifier.py.
12. Verifier checkpoint. Paper: RoBERTa fine-tuned on MNLI, 90.2% MNLI dev accuracy §4. Code: loads roberta-large-mnli main_inference.py. The paper does not name the checkpoint, so the 90.2% figure is not tied to a specific file.

Pre-generated trees for the three dev sets are in the repository, so inference can be reproduced without the generation step README.md dev.G.pkl. This was not checked beyond file presence.

Pitfalls

• Dev-set tuning. Hyperparameters, including depth and width, were chosen on dev-set performance §4. Table 1 also reports dev numbers next to test numbers. Treat the test column as the cleaner comparison.
• "Unsupervised" needs context. The authors say the method runs unsupervised with any few-shot model §1. The NLI verifier is a RoBERTa model fine-tuned on MNLI §3.4 §4. The few-shot prompts, six hand-written examples per dataset, are part of the method belief.prompt.txt.
• Cost per question. The paper does not state a call count. From the code's call pattern, a full tree needs about 70 LM completions: two for the root's belief, and per node one negation plus two belief calls, with two generation calls per parent at each level. The filtering loop in the code can add retries generation.py. NLI checks run over every ordered pair of nodes, up to 306 for 18 nodes.
• Probability access. Integrity needs the True probability, which the code reads from top-5 log-probabilities generation.py generation.py. A missing token counts as non-integral. Any API that does not expose logprobs cannot run this as coded, and the paper does not state the top-k.
• Legacy endpoint and model. The code uses the legacy openai.Completion interface and the text-davinci-001 engine name generation.py generation.py. Other models would change the probabilities that the thresholds and weights depend on; the paper gives no guidance for that case.
• Belief weight sign. Eq. 12 takes a weight w_c per clause, but the paper does not say what to do when a belief is negative for a True-integral leaf eq. 7 eq. 12. The code uses the magnitude as the weight inference.py.
• Empty sum. If the solver accepts no node, or the scores sum to zero, the answer defaults to True main_inference.py. The paper does not state this rule.
• Statement form. The code strips the final punctuation and re-adds "?" or "." for each prompt generation.py generation.py. Implementers must do the same, or the prompts will differ from the paper's.
• Stochastic results. Depth-1 sampling is not seeded in the code, and the paper reports no run-to-run variance for the main table. Figure 4 shows variance only over few-shot sets and orders fig. 4.
• Scope. Only binary true/false tasks are tested. Relations are modelled inside one tree and not across questions [Limitations].
• Figure and table numbers follow the LaTeX source order (see the equation note above). The compiled PDF was not checked.

Lineage

• Builds on: Chain-of-thought prompting, the explanation-based baseline the paper extends §2; Self-consistency, whose sampling and voting idea the paper contrasts with its tree §3.1.2; abductive commonsense reasoning, which motivates the abductive generation step §3.1.1 (no card).
• Compared against: standard prompting, chain of thought, self-consistency, generated knowledge prompting (GKP), and supervised T5, UnifiedQA, Unicorn and RoBERTa-large baselines §4 tab. 1.
• Uses: NLI with a RoBERTa model fine-tuned on MNLI §3.4 §4; RC2 as the MAX-SAT solver §4. No cards exist for these.