From Atomic Evidence to Logical Composition: Structured Compositional Reasoning over Compound Answer Options

Technical Summary: Structured Compositional Reasoning over Compound Answer Options

Problem Statement
Large Language Models (LLMs) frequently fail when tasked with selecting answer options that require combining atomic judgments under explicit logical operators (AND, OR, NEITHER/NOR). While models often correctly evaluate individual atomic propositions, they struggle to compose these judgments into a coherent final decision. This "compositionality gap" suggests the failure stems not from a lack of knowledge, but from the difficulty in representing and combining logical possibilities. Standard prompting methods fuse atomic evaluation and logical composition into a single generation step, leaving no mechanism to diagnose errors or enforce logical constraints. Furthermore, models often degrade significantly on disjunctive compositions and negated structures (e.g., NEITHER/NOR), a pattern consistent with mental-model theories of human reasoning where difficulty scales with the number of possibilities a reasoner must maintain.

Methodology
The authors propose a framework that decouples atomic evidence elicitation from logical composition, ensuring the model never processes a compound option as a whole. The framework operates in three stages:

1. Option Decomposition: Each compound answer option is deterministically parsed into its constituent atomic answers and the explicit boolean operator connecting them. Atomic answers shared across multiple options are treated as a single unique entity ($U_C$), ensuring consistent scoring for a proposition regardless of where it appears.
2. Contrastive Evidence Elicitation: For each unique atomic answer, the system constructs a pair of opposing natural language hypotheses conditioned on the context: one stating the atom is supported ($h^+$) and one stating it is not ($h^-$). The LLM is prompted to choose the more plausible hypothesis. The raw evidence score is derived from the log-probabilities of the choice tokens, normalized to produce a relative preference score between the two hypotheses.
3. Score Calibration: Raw scores are calibrated to improve reliability. The authors introduce Relative Calibration, a method that maps raw scores to calibrated probabilities using a logistic regression model. Unlike standard post-hoc methods (Platt scaling, Isotonic calibration) that rely only on absolute score values, Relative Calibration incorporates features representing the atom's standing within the specific instance (e.g., its rank among other atoms and its distance from the maximum score). This allows the system to account for the fact that the validity of an option depends on how atoms compare to one another.
4. Globally Constrained Inference: The calibrated scores are fed into an Operator-Constrained Integer Linear Program (ILP). The ILP defines binary decision variables for the status of each atomic answer and the validity of each compound option. It enforces strict constraints that encode the semantics of the logical operators (e.g., for AND, the option is valid only if both atoms are true; for NEITHER/NOR, valid only if both are false). The objective function maximizes the total evidence (supporting minus opposing) for the atomic assignments subject to these constraints, ensuring exactly one compound option is selected as the final prediction.

Key Contributions

1. Structured Framework: A novel approach that elicits contrastive evidence for individual atomic answers and combines them via operator-constrained ILP inference, effectively isolating logical composition from comprehension.
2. Relative Calibration: A calibration technique that scores atomic answers based on both their confidence and their relative standing among other atoms in the same instance, addressing the limitations of independent calibration in multi-option tasks.
3. LOGICAL-SATA Benchmark: A new reading-comprehension benchmark derived from SATA-Bench, specifically designed to evaluate compound answer reasoning with explicit logical operators.
4. Empirical Evaluation: Comprehensive evaluation across two distinct benchmarks (LOGICAL-COMMONSENSEQA and LOGICAL-SATA) demonstrating that the framework significantly outperforms direct prompting, particularly on operators that typically cause model failure.

Results
The framework was evaluated using Llama-3.1-8B-Instruct.

• Overall Performance: On the human-validated split of LOGICAL-COMMONSENSEQA, the framework improved Macro-F1 from 48.3 (best direct prompting) to 77.0. On LOGICAL-SATA, it improved from 47.0 to 75.6.
• Operator-Specific Gains: The most significant improvements were observed on NEITHER/NOR, where Macro-F1 rose from 14.0 to 76.8 on LOGICAL-COMMONSENSEQA and from 12.6 to 73.4 on LOGICAL-SATA. Improvements were also substantial for OR and MIXED settings, while gains on AND were more modest.
• Calibration Impact: Relative calibration yielded the best performance, particularly in MIXED settings where options employ different operators. It reduced atomic Brier scores and log loss more effectively than Platt or Isotonic scaling, indicating better handling of overconfidence and relative ordering.
• Error Analysis: When provided with gold atomic statuses, the ILP inference layer achieved 100% accuracy, confirming that the logical constraints are perfectly encoded. The remaining errors were attributed to failures in the initial atomic evidence elicitation (e.g., misinterpreting modifiers or passage topics).

Significance and Claims
The paper claims that the observed failures in logical reasoning tasks are often due to difficulties in composing local judgments rather than a lack of relevant knowledge. By explicitly separating the evaluation of atomic facts from the logical combination of those facts, the framework bridges the compositionality gap. The results suggest that LLMs retain useful evidence about individual atomic answers even when they fail to combine them correctly in a single pass. The introduction of relative calibration highlights that the validity of an atomic judgment in a multiple-choice setting is often context-dependent on the other available options. The authors conclude that structured inference under explicit constraints is a viable path to improving logical reasoning in LLMs, particularly for complex negated and disjunctive structures.