SSR: Symbolic-Neural Soft Reasoning for Robust and Verifiable Thinking Chains¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/1240148048/SSR
Area: Model Compression and Efficient Inference
Keywords: Neuro-Symbolic Reasoning, Soft Logical Relaxation, MaxSAT, Verifiable Thinking Chains, LLM Reasoning
TL;DR¶
To tackle auto-formalization noise and the brittleness of strict determinism in neuro-symbolic inference, SSR integrates confidence-weighted MaxSAT relaxation, dual-system targeted retrieval under ambiguity, and verifiable forward/backward reasoning tree generation, delivering both high accuracy and fully verifiable thinking chains.
Background & Motivation¶
Large Language Models (LLMs) have achieved remarkable progress on complex multi-step reasoning tasks, largely fueled by the Chain-of-Thought (CoT) prompting paradigm that decomposes difficult problems into explicit intermediate rationales. Nevertheless, autoregressive neural generation remains fundamentally fragile due to its stochastic token-level prediction nature. Models frequently suffer from hallucinations, premature abandonment, repetitive loops, and unfaithful rationalizations that merely act as post-hoc justifications rather than reflecting true causal reasoning. To guarantee logical rigor, neuro-symbolic approaches marry LLMs with symbolic solvers, employing the neural model as a translator that maps natural language into formal logical programs, which are then solved deterministically by SMT or SAT solvers.
However, existing neuro-symbolic frameworks inherit an acute all-or-nothing brittleness rooted in strict logical determinism. Natural language is context-dependent, nuanced, and rife with implicit commonsense assumptions, creating a fundamental friction with the exact syntax and rigid semantics required by symbolic solvers. When LLMs perform auto-formalization, they frequently introduce malformed predicates, omitted premises, flipped negations, or quantifier scope misalignments. In standard SMT formulations, even a minor translation inconsistency renders the entire logical program unsatisfiable (unsat), collapsing the symbolic solving pipeline. Furthermore, offloading the entire deduction step to an opaque solver fails to yield human-interpretable reasoning traces that can be inspected, debugged, or repurposed for supervised fine-tuning.
This work challenges the standard assumption that LLM-generated formalizations should be treated as infallible logical programs, positing instead that they represent noisy preliminary evidence. By introducing soft satisfiability constraints governed by the LLM's own token-level confidence and coupling this with solver-guided targeted retrieval when multiple satisfying candidates emerge, the reasoning system retains formal verification guarantees while acquiring graceful tolerance to noise. Core idea: reframe neuro-symbolic reasoning into a progressive pipeline of syntax-level filtering, confidence-weighted MaxSAT soft relaxation, dual-system ambiguity retrieval, and verifiable forward/backward reasoning chain reconstruction, harmonizing formal rigor with semantic robustness.
Method¶
Overall Architecture¶
The SSR framework bridges neural semantic flexibility and symbolic deductive verification across several coordinated stages: restricted formal abstraction, syntax-level screening and graceful routing, confidence-weighted MaxSAT relaxation, solver-guided targeted retrieval under ambiguity, and verifiable reasoning tree compilation. Given a natural language context and question, the LLM extracts objects, facts, and target queries into a constrained single-argument predicate representation. A syntax filter cleans up malformed expressions, routing severely corrupted cases to a standard CoT fallback branch. The symbolic backend first evaluates hard SMT consistency; if inconsistent, it searches for a maximum-weight satisfiable subset of facts weighted by token entropy. If multiple candidate answers remain satisfiable due to missing conditions, the solver isolates the exact discriminator predicate needed and prompts the LLM for commonsense verification. Finally, the verified logical model is translated into explicit, human-readable forward or backward reasoning chains.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input: Natural Language Context and Question"] --> B["Restricted Unary Formalization Extraction<br/>Extract objects, facts, and queries into JSON"]
B --> C["Syntax-Level Filtering and Adaptive Fallback<br/>Placeholder substitution and severe error routing"]
C -->|Severely Corrupted| F1["CoT Autoregressive Fallback Branch"]
C -->|Syntactically Valid| D["Confidence-Weighted MaxSAT Soft Relaxation<br/>Token-entropy weighting and max-weight sat subset search"]
D -->|Multiple Satisfiable Candidates| E["Dual-System Targeted Ambiguity Retrieval<br/>Solver isolates discriminator + LLM verifies premise"]
D -->|Unique Satisfiable Candidate| G["Verifiable Forward/Backward Thinking Chain Generation<br/>Normalized rules assemble into replayable proof trees"]
E -->|Retrieval Confirmed| G
E -->|Underdetermined/Unconfirmed| G
G --> H["Output: Verifiable Answer and Human-Readable Reasoning Chain"]
F1 --> H
Key Designs¶
1. Restricted Unary Predicate Formalization and Syntax Filtering: Preventing multi-arity parser collapse and invalid tokens
Multi-argument relational predicates (such as Chase(mouse, cat) or non-entity predicates like Can(bird, fly)) routinely induce argument-order inversion and ontological hallucinations in LLMs. SSR enforces a normalized unary predicate abstraction \(\text{Predicate}(\text{object})\), where auxiliary relation entities are merged directly into the predicate name (e.g., Chase_mouse(cat)), partitioned into Numeric Sort and Boolean Sort under open-world semantics. Before invoking the SMT backend, a syntax-level filter replaces malformed expressions, invalid predicate structures, or raw natural-language fragments with an uninformative placeholder \(\text{BoolVal}(\text{True})\). Only when more than one fact is corrupted or the query itself fails does the system cleanly fall back to CoT prompting, shielding the symbolic parser while maximizing solver engagement.
2. Confidence-Weighted MaxSAT Soft Relaxation: Mitigating over-constrained contradictions from noisy translation
In conventional SMT inference, any contradiction in the generated fact set \(\Phi = \bigwedge_{i=1}^n \varphi_i\) leads to unsatisfiability (unsat). SSR recasts the inference problem into a confidence-weighted Maximum Satisfiability (MaxSAT) formulation, assigning each translated fact \(\varphi_i\) an importance weight \(w(\varphi_i) > 0\). When model logit probabilities are accessible, SSR derives an entropy-based certainty score:
$\(w(\varphi_i) = \exp(-H(\varphi_i))\)$
where \(H(\varphi_i)\) is the length-normalized entropy of the tokens generating \(\varphi_i\), naturally measuring model certainty. When \(\Phi\) is unsatisfiable, SSR searches across each candidate answer assignment \(q = q_j\) for a satisfiable sub-theory \(\Phi'_j \subseteq \Phi\) that maximizes the aggregate confidence weight \(\sum_{\varphi \in \Phi'_j} w(\varphi)\). This optimization prunes noisy, contradictory, or hallucinatory assertions while preserving the highest-confidence core premises.
3. Dual-System Targeted Retrieval under Ambiguity: Resolving unstated commonsense and missing premises without unguided search When soft relaxation leaves multiple candidates satisfiable (such as both \(q\) and \(\neg q\) possessing valid satisfying models), the root cause is typically omitted context or implicit commonsense knowledge. Rather than prompting the LLM for unstructured self-correction, SSR tasks the SMT solver with systematically enumerating predicate-function assignments to find a minimal discriminator condition \(a = \text{value}\) such that: $\(\Phi \wedge (a = \text{value}) \wedge (q = q_j) \text{ is sat}\)$ produces a uniquely determined answer. The algorithm recursively backtracks to identify derivable parent premises \(a' = \text{value}'\). This localized premise is then presented to the LLM to verify whether it holds in the input narrative or basic world knowledge. If confirmed, it is integrated into the constraint set; if unconfirmed, SSR preserves the candidate set and conservatively returns UNKNOWN, forestalling ungrounded extrapolation.
4. Structured Forward and Backward Verifiable Reasoning Trees: Overcoming black-box solver opacity with explainable traces Raw SMT satisfaction yields truth assignments but lacks human-readable deductive explanations. SSR normalizes the verified logical program into atomic properties and implication rules (\(P \to Q\)), executing deterministic search along two directions: forward deduction applies rule implications iteratively from known base properties to derive new facts until the query is reached, while backward deduction treats the query as a goal and recursively retrieves matching rule antecedents as sub-goals. The resulting deduction trees (upright for forward, inverted for backward) are translated into natural-language CoT traces, ensuring every deductive step is mechanically replayable and free of logical leaps, providing scalable and automatically verifiable rationale supervision.
Key Experimental Results¶
Main Results¶
The authors evaluated SSR alongside Direct answering, standard Chain-of-Thought (CoT), Formal CoT, Logic-LM, and VeriCoT across four representative reasoning benchmarks (PrOntoQA, ProofWriter, FOLIO, and BigBench LogicalDeduction) using four diverse LLMs (Qwen2.5-7B-Instruct, DeepSeek-R1, GPT-4o, and GPT-5.4). Accuracy is averaged over five runs across 200 sampled questions per dataset.
| Model | Dataset | Direct | CoT | Formal CoT | Logic-LM | VeriCoT | SSR (Ours) |
|---|---|---|---|---|---|---|---|
| Qwen-2.5-7B | PrOntoQA | 67.5±0.00 | 86.1±0.37 | 84.9±0.20 | 91.7±0.24 | 88.1±0.20 | 97.4±0.20 |
| Qwen-2.5-7B | ProofWriter | 37.0±0.00 | 58.1±0.37 | 50.9±0.20 | 77.9±0.20 | 73.4±0.49 | 86.0±0.32 |
| Qwen-2.5-7B | FOLIO | 55.5±0.00 | 64.5±0.45 | 56.1±0.20 | 62.2±0.24 | 66.0±0.32 | 64.6±0.20 |
| Qwen-2.5-7B | Logical Deduction | 46.0±0.00 | 63.2±0.40 | 41.8±0.24 | 72.0±0.32 | 66.5±0.40 | 75.0±0.32 |
| DeepSeek-R1 | PrOntoQA | 86.5±0.00 | 96.0±0.00 | 91.7±0.24 | 92.0±0.32 | 95.4±0.20 | 100.0±0.00 |
| DeepSeek-R1 | ProofWriter | 56.0±0.00 | 72.5±0.32 | 73.5±0.77 | 89.0±0.00 | 80.1±0.20 | 98.9±0.20 |
| DeepSeek-R1 | FOLIO | 58.5±0.00 | 68.0±0.37 | 56.2±0.24 | 69.5±0.00 | 64.4±0.37 | 71.5±0.32 |
| DeepSeek-R1 | Logical Deduction | 74.5±0.00 | 84.0±0.20 | 83.5±0.49 | 88.7±0.40 | 85.6±0.20 | 90.2±0.24 |
| GPT-4o | PrOntoQA | 83.5±0.00 | 94.5±0.00 | 86.0±0.00 | 88.5±0.00 | 96.5±0.00 | 100.0±0.00 |
| GPT-4o | ProofWriter | 52.5±0.00 | 74.0±0.37 | 68.2±0.24 | 90.0±0.00 | 80.6±0.20 | 98.0±0.00 |
| GPT-4o | FOLIO | 64.5±0.00 | 70.5±0.32 | 57.7±0.24 | 76.1±0.20 | 66.2±0.24 | 75.2±0.24 |
| GPT-4o | Logical Deduction | 63.5±0.00 | 72.0±0.00 | 64.4±0.49 | 86.0±0.00 | 72.6±0.24 | 88.4±0.24 |
| GPT-5.4 | PrOntoQA | 97.0±0.00 | 98.5±0.00 | 90.0±0.32 | 100.0±0.00 | 97.4±0.24 | 100.0±0.00 |
| GPT-5.4 | ProofWriter | 79.5±0.00 | 87.1±0.20 | 78.4±0.20 | 95.0±0.40 | 89.2±0.24 | 98.6±0.58 |
| GPT-5.4 | FOLIO | 69.5±0.00 | 74.5±0.32 | 64.8±0.40 | 76.4±0.49 | 72.3±0.24 | 78.1±0.49 |
| GPT-5.4 | Logical Deduction | 71.0±0.00 | 76.6±0.20 | 69.8±0.24 | 88.7±0.40 | 79.9±0.37 | 90.0±0.32 |
Ablation Study and Execution Branch Attribution¶
To dissect how soft relaxation, solver retrieval, and fallback routing contribute to performance, the authors conducted component ablations on GPT-5.4 and contingency table analyses of execution branches on Qwen2.5-7B-Instruct.
Table 1: Final-answer accuracy (%) of component ablations on GPT-5.4
| Dataset | SSR Full Model | - MaxSAT (No Soft Relaxation) | - Retrieval (No Ambiguity Retrieval) | - Fallback (No CoT Fallback) |
|---|---|---|---|---|
| PrOntoQA | 100.0 | 100.0 | 100.0 | 99.5 |
| ProofWriter | 98.6 | 98.5 | 99.0 | 97.0 |
| FOLIO | 78.1 | 76.5 | 74.5 | 63.0 |
| LogicalDeduction | 90.0 | 89.5 | 89.5 | 84.5 |
Table 2: Correct/Wrong (r/w) sample distribution across symbolic solver vs CoT fallback branch in Qwen2.5-7B-Instruct (\(\chi^2\) test)
| Dataset | Symbolic Branch (r / w) | CoT Fallback Branch (r / w) | Contingency \(\chi^2\) Value |
|---|---|---|---|
| PrOntoQA | 194 / 4 | 1 / 1 | 18.70 |
| ProofWriter | 149 / 9 | 23 / 19 | 43.09 |
| FOLIO | 74 / 19 | 63 / 43 | 9.36 |
| LogicalDeduction | 124 / 28 | 26 / 22 | 14.62 |
Key Findings¶
- Symbolic execution dramatically outperforms the fallback branch: Across all datasets, instances successfully solved by the Z3 symbolic backend exhibited significantly higher accuracy (e.g., 149 correct vs 9 wrong on ProofWriter, 94.3%) than those diverted to CoT due to parser rejection (23 correct vs 19 wrong, 54.8%), with \(\chi^2\) tests confirming statistical significance (\(p < 0.01\)). Samples that fail symbolic translation represent inherently more difficult linguistic and logical tasks for the base LLM.
- CoT fallback acts as an essential safety valve on complex benchmarks: On FOLIO, where premise lengths are extensive and syntactic structures complex, disabling the CoT fallback plummeted accuracy from 78.1% to 63.0% (-15.1%), highlighting that pure symbolic formalization without fallback collapses when linguistic complexity exceeds translation capacity.
- Superior robustness under contextual perturbations: Under \(-1\) and \(-2\) premise deletions/modifications and \(+1\) and \(+2\) distractor fact injections, SSR maintained a markedly smoother degradation slope than Logic-LM and VeriCoT, confirming that confidence-weighted MaxSAT successfully filters out spurious premises while tolerating minor premise corruption.
- Massive improvement in generating verifiable thinking chains: In terms of fully correct, loop-free, and verifiable thinking chains, SSR Forward (SSR-F) attained 89.7%–94.9% on PrOntoQA and 71.4%–73.1% on ProofWriter across models, whereas VeriCoT reached only 51.7%–68.3% and Formal CoT hovered below 36.6%.
Highlights & Insights¶
- Turning unsatisfiability into a weighted optimization problem: Rather than treating SMT satisfiability as a binary pass/fail barrier, framing translation noise within a confidence-weighted MaxSAT formulation allows the solver to preserve the maximum-likelihood logical core, fundamentally increasing fault tolerance.
- Solver-guided targeted retrieval replaces unguided self-correction: Instead of asking an LLM to blindly "rethink" why a reasoning chain failed, the SMT solver mathematically deduces the exact missing condition required to break ambiguity, directing the LLM to verify a single targeted factual claim.
- Bi-directional translation between symbolic proofs and natural CoT: Grounding natural language thinking chains in formally verified forward/backward deduction trees eliminates reasoning hallucinations and cycles, offering a scalable synthetic data generation engine for reasoning-oriented SFT and RL.
Limitations & Future Work¶
- Constrained retrieval bandwidth: The targeted retrieval mechanism is currently bound to single-condition missing premises; when an LLM omits multiple interconnected facts or generates structural relation errors, retrieval fails and the system defaults to CoT fallback.
- Expressiveness trade-offs in unary predicate normalization: Flattening relations into unary predicates reduces argument-swapping bugs but hampers compact representation of complex n-ary relations, temporal sequences, and higher-order logic.
- Cumulative latency overhead: Although SMT solving itself requires only milliseconds, multiple LLM passes for initial formalization, syntax filtering, targeted premise verification, and CoT compilation increase total wall-clock runtime by roughly 1.5x to 2x over standard CoT.
Related Work & Insights¶
- vs Logic-LM (Pan et al., 2023): Logic-LM translates context directly to symbolic code and executes an SMT solver deterministically. If the translation contains any minor syntactic flaw, contradiction, or omission, Logic-LM immediately fails with
unsat. SSR adds syntax-level filtering, MaxSAT relaxation, and targeted ambiguity retrieval, significantly bolstering robustness. - vs VeriCoT (Feng et al., 2025a): VeriCoT relies on post-hoc verification to check natural language CoT steps using a solver, frequently suffering from error propagation where a valid final answer is overturned due to imperfect step verification. SSR embeds symbolic solving and relaxation directly into the reasoning loop, constructing verifiably sound reasoning trees directly from satisfied constraints.
Rating¶
- Novelty: ⭐⭐⭐⭐☆ Reformulates neuro-symbolic auto-formalization via confidence-weighted MaxSAT relaxation and solver-guided discriminator retrieval.
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ Rigorous evaluation across 4 open- and closed-source LLMs and 4 logic benchmarks, backed by contingency tables, component ablations, and perturbation robustness analyses.
- Writing Quality: ⭐⭐⭐⭐⭐ Exceptionally organized, clear mathematical formulation, explicit algorithm pseudocode, and thorough failure categorization.
- Value: ⭐⭐⭐⭐☆ Sets a practical standard for verifiable neuro-symbolic reasoning and trustworthy synthetic thinking-chain data synthesis.