From Atomic Evidence to Logical Composition: Structured Compositional Reasoning over Compound Answer Options
Obed Junias, Maria Leonor Pacheco
cs.CL, cs.AI
2026-08-13
Decompose compound options into atoms, score opposing hypotheses, calibrate, then solve an operator-constrained ILP; on Llama-3.1-8B, Macro-F1 rises from 48 to 77, with NEITHER/NOR up about 63 points.
LLMs fail at logical reasoning, and they fail unevenly. Hold the commonsense knowledge fixed: join two judgments with AND and the model still gets it right, switch to OR and it slips, switch to NEITHER/NOR and it collapses. The paper frames this as a composition problem. The model can judge each atomic answer (the smallest unit inside a compound option that cannot be split further) correctly, but it cannot recombine them under the operator into the right option. The authors call the gap between those two abilities the compositionality gap.
The ordering is not unique to AI. Mental-model theory in psychology predicts exactly this: a conjunction (AND) holds a single joint possibility, a disjunction (OR) forces several alternatives to be kept alive at once, and negation adds the burden of remembering a proposition while rejecting it. NEITHER/NOR carries both burdens and is hardest for humans too. The model shows the same signature.
Standard prompting fuses comprehension and composition into one generation. The model must judge every atom and combine them under the operator in the same pass. A failure anywhere cannot be attributed, and asking a model to satisfy hard constraints in free generation lets it silently violate them.
The framework splits the pipeline into three stages: decompose the options, gather evidence per atom, and hand the evidence to a solver that cannot violate the logic.
First, each compound option is parsed into an atom1-operator-atom2 triplet. An atom is scored once per instance; when it appears in several options, its status applies to all of them.
Second, for each atom the system builds a pair of opposing hypotheses: it satisfies the context, or it does not. Both go into one prompt as choices A and B, and the model picks the more plausible one. The first-token log-probabilities are normalized into an evidence score. Comparing the positive and negative readings side by side is more reliable than asking whether a single statement is true. This stage produces evidence and never touches logic.
The scores are then calibrated. Standard methods such as Platt scaling and isotonic calibration look only at the absolute value of a score. But exactly one option per instance is valid, so whether an atom gets selected depends on where it stands relative to the others. The authors introduce relative calibration, whose feature vector holds the within-instance standardized score, the rank, and the gap to the top score, mapped back to a calibrated score by logistic regression.
The third stage is an operator-constrained integer linear program (ILP). It assigns each atom a status variable and each option a validity variable, encodes AND, OR, and NEITHER/NOR exactly as linear inequalities, and requires exactly one of the four options to be valid. The objective maximizes the total evidence of the atoms that are adopted. The ILP only composes, accepts only atomic scores, and cannot violate operator semantics.
All experiments use Llama-3.1-8B-Instruct at temperature 0.7, averaged over five runs, reporting Macro-F1.
| Benchmark | Best direct prompting | Structured inference | relative calibration |
| Logical-CommonsenseQA (human-validated) | 48.3 | 75.8 | 77.0 |
| Logical-SATA | 47.0 | 72.2 | 75.6 |
The gains concentrate on the hardest operator. NEITHER/NOR rises from 14.0 to 76.8 on LCQA and from 12.6 to 73.4 on LSATA, about 60 points in each case. Gains on AND are far smaller because the model already handles it. Explicit composition pays off most when the decision requires managing alternatives, jointly rejecting atoms, or mixing operators across options.
Feed the inference layer gold atomic statuses and accuracy is 1.00 on both benchmarks, by construction. The informative quantity is how much atomic error survives composition: atomic accuracy is 0.830 and 0.824, while compound accuracy falls to 0.758 and 0.723. On calibration, relative calibration is best on both Brier score and log loss, with a larger drop in log loss, which says the raw scores are overconfident rather than merely out of order.
The paper splits logical-reasoning failure into two attributable stages: the atom judgment was wrong, or the composition was wrong. Standard prompting cannot tell them apart. For practitioners, the practical point is that the solver guarantees the final prediction respects the operator semantics exactly. The class of errors where free generation quietly breaks a constraint is closed off.
The evidence points one way: some failures billed as the model cannot reason are really the model cannot compose. The knowledge is present, the individual judgments are correct, and the composition step breaks. That relocates the blame from knowledge to the inference pipeline.
The cost is engineering overhead. Each question needs several contrastive-hypothesis prompts, a calibration pass, and an ILP solve, so token use and latency run higher than direct prompting. The method trades speed for controllability and accuracy.
The whole evaluation uses a single model, Llama-3.1-8B-Instruct, and the paper does not check whether the gains hold across model families or at larger scale. Operators cover only AND, OR, and NEITHER/NOR, with exactly two atoms per option; implication, exclusive disjunction, nesting, and longer expressions are out of scope.
Both benchmarks enforce exactly one valid option. Real tasks often allow multiple correct answers or none, so this construction likely overstates how usable the method is off the shelf.
The ILP discards atomic uncertainty at assignment time and returns a single choice. The authors list a probabilistic version that propagates atomic uncertainty to the options as future work.
The ceiling sits at atomic evidence quality. Open-ended commonsense interpretation, passage grounding, and source-annotation errors all propagate through the logical constraints to the final prediction. The constraints cannot make the atomic judgments themselves correct.