Logical reasoning over natural language requires both semantic interpretation and deductive search. Large language models (LLMs) can propose plausible intermediate derivations, but they often fail to compose them into a complete proof and overpredict uncertainty. Neurosymbolic methods improve search by translating an entire problem into first-order logic and handing it to a prover, but a single bad clause can make the whole translation nonexecutable. We present Hybrid Reasoning, a three-stage pipeline that decouples proposing a proof, validating its steps, and deciding a label. An LLM proposes a structured proof tree with a raw verdict; a theorem prover validates each derivation locally, keeping only the subset it can prove; and an uncertainty-gated repair attempts to re-derive the label from the premises plus the validated derivations, when the raw verdict is UNCERTAIN. Across four benchmarks (FOLIO, ProofWriter, ProverQA, PrOntoQA) and five contemporary LLMs, Hybrid Reasoning is the top-performing method on the two hardest datasets, improving on the strongest baseline by 5.3 points on FOLIO and 4.9 on ProverQA, and reaches ceiling-level accuracy on the easiest. The repair stage operates at 78-98% precision, producing 326 correct relabellings against 19 regressions.
Figures & tables
Figure 1: Hybrid Reasoning. Stage 1 an LLM proposes derivations di with supports Si and a raw verdict. Stage 2 each derivation is validated as a local entailment problem Si⊢di , yielding the validated set D+={di:Si⊢di} . Stage 3 if the raw verdict is decisive ( True / False ) the prediction is preserved; otherwise uncertainty-gated repair attempts to prove h or ¬h from P∪D+ , repairing the label only if one side is discharged.
Figure 2: Mean accuracy across the five models for each internal method, with 95%t -confidence intervals. Hybrid Final is the validated, repaired pipeline; Hybrid Raw is the LLM’s Stage-1 verdict before validation and repair. The raw verdict is not reliably better than CoT, but validation and uncertainty-gated repair lift it to the top, especially on ProverQA.
External
Internal (this work’s harness)
Dataset
Model
Logic-LM
LINC
CLOVER
Standard
CoT
Autoform.
Hybrid
FOLIO
DeepSeek V4 Flash
83.5
81.3
75.3
84.6
82.4
79.1
88.5
GPT-5 Nano
78.0
77.5
78.0
79.1
76.4
74.7
87.4
Gemini 3.1 Flash-Lite
80.8
74.2
75.8
67.0
76.9
78.0
89.0
Grok 4.3
85.7
75.8
74.7
84.1
85.2
79.7
88.5
Qwen 3.5 Flash
87.4
81.3
76.4
85.2
83.5
75.8
88.5
Table 1: Accuracy (%) by dataset and model. Bold marks the best method in each row, underline the second best. Autoform. is whole-problem autoformalization discharged by Prover9 (the monolithic neurosymbolic baseline); Hybrid is the full pipeline. PrOntoQA is saturated and serves as a sanity check.
FOLIO
ProverQA
Hybrid vs.
Δ
95% CI
Δ
95% CI
Logic-LM
+5.3
[2.3,8.5]
+4.9
[2.4,7.3]
LINC
+10.3
[5.8,15.1]
+14.0
[10.2,17.7]
CLOVER
+12.3
[8.2,16.6]
+6.2
[3.2,9.1]
Standard
+8.4
[5.9,11.0]
+13.3
[9.8,16.8]
CoT
+7.5
[5.2,9.9]
+13.7
[10.0,17.5]
Table 2: Paired tests of Hybrid against each method on the two hardest datasets, averaged over the five models. Δ : Hybrid’s accuracy minus the method’s (points); 95% CI : paired bootstrap interval over examples. All Holm-corrected sign-flip p -values are below .001 . Hybrid Raw is the Stage-1 verdict and forms its own correction family. Tests on ProofWriter and PrOntoQA and per-model McNemar tests are in Appendix G .
Dataset
Fires
Rate
Prec.
Net
Gain
FOLIO
63
6.9%
90.5%
+55
+6.0
ProofWriter
110
9.8%
98.2%
+106
+9.4
ProverQA
204
19.4%
78.4%
+145
+13.8
PrOntoQA
1
0.1%
100.0%
+1
+0.1
Table 3: Direct uncertainty-gated repair coverage and precision (pooled over models). Fires : repair invocations; Rate : firing rate; Prec. : fraction of firings that reach the gold label; Net : helpful minus harmful relabellings among repair firings; Gain : raw → final accuracy change (points).
Figure 3: Validation-status analysis, pooled across models. (a) Share of instances by how much of the proof tree validated. (b) The LLM’s raw accuracy is higher for fully than for partially validated trees, making validation status a label-free reliability signal. (c) The repaired pipeline improves accuracy at every level, most where raw reliability is lowest. Error bars are 95% Wilson intervals.
Figure 4: Row-normalised confusion before (Hybrid Raw) and after (Hybrid Final) repair, pooled over the three open-world datasets. Repair reclaims True / False cases the model had left Uncertain (recall 73→89% and 66→82% ).
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
N
Labels
#Prem.
Depth
FOLIO
182
3
5.3
—
ProofWriter
225
3
15.3
1–5
PrOntoQA
200
2
17.3
5
ProverQA
210
3
18.4
6–9
Appendix
Table 4: Evaluation splits. N : examples; Labels : size of the label space (3 = True / False / Uncertain , 2 = binary); #Prem. : mean premises per instance; Depth : gold reasoning depth (where defined). ProofWriter is depth-balanced ( 45 per depth) and all three-label sets are label-balanced except FOLIO, which keeps its natural distribution.
Backbone model
Fixed reasoning configuration
DeepSeek V4 Flash
reasoning enabled; effort high
Gemini 3.1 Flash-Lite
provider default thinking behaviour
GPT-5 Nano
reasoning effort high
Grok 4.3
reasoning effort low
Qwen 3.5 Flash
thinking enabled
Appendix
Table 5: Backbone model configurations used throughout the evaluation. Except for the LINC reproduction described below, temperature and top- p were left unspecified and provider defaults were used.
Figure 5: Execution rate, executable accuracy, and final accuracy by dataset and method. Execution rate measures the fraction of instances for which the method obtains an executable symbolic result under its own implementation. Executable accuracy is accuracy restricted to those executable cases; final accuracy includes the method’s complete decision procedure, including fallback behavior where applicable.
Dataset
Method
True
False
Uncertain
P
R
P
R
P
R
FOLIO
Autoform.
90.7
71.4
98.8
61.9
66.6
96.3
Hybrid Raw
88.3
81.3
94.7
72.2
72.2
91.7
Hybrid Final
87.9
89.5
95.0
83.7
84.3
91.1
ProofWriter
Autoform.
100.0
95.7
100.0
95.7
92.1
100.0
Hybrid Raw
99.4
82.1
100.0
80.3
72.8
99.7
Appendix
Table 6: Per-label precision/recall (%) for True , False , and Uncertain . PrOntoQA has no Uncertain label.
Dataset
Form.-only
Raw-only
Both-wrong
Net
recov.
preserv.
rescued
FOLIO
62.5%
100.0%
17.5%
+163
ProofWriter
91.3%
100.0%
11.1%
+111
ProverQA
73.9%
88.6%
20.9%
+233
PrOntoQA
100.0%
–
–
+1
All
77.7%
95.0%
19.1%
+508
Appendix
Table 7: Benefit/risk complementarity with monolithic Autoformalization, pooled over models. Form.-only recov. : of instances only the monolithic formalisation got right, the share Hybrid also gets right. Raw-only preserv. : of instances only the raw verdict got right, the share Hybrid preserves. Both-wrong rescued : of instances both got wrong, the share Hybrid rescues. Net : instances Hybrid gets right where at least one of the two was wrong, minus instances it gets wrong where both were right; distinct from the repair net in Table 3 . PrOntoQA has no raw-only or both-wrong instances.
Dataset
Model
Raw
Final
Δ
Fires
Helpful
Harmful
pHolm
FOLIO
DeepSeek V4 Flash
85.2
88.5
+3.3
6
6
0
.31
GPT-5 Nano
74.7
87.4
+12.6
26
24
1
<.001
Gemini 3.1 Flash-Lite
82.4
89.0
+6.6
14
12
0
.007
Grok 4.3
84.6
88.5
+3.8
8
7
0
.17
Qwen 3.5 Flash
84.6
88.5
+3.8
9
8
1
.32
ProofWriter
DeepSeek V4 Flash
94.7
96.4
+1.8
4
4
0
.75
Appendix
Table 8: Per-model repair breakdown. Raw / Final : accuracy (%) before and after repair; Δ : accuracy gain in points; Fires : repair invocations; Helpful / Harmful : firings that move toward or away from the gold label; pHolm : exact McNemar test of Final against Raw on the Helpful/Harmful counts, Holm-corrected within the repair family (Appendix G ).
Figure 6: Predicted label distributions for Gold, Autoformalization, Hybrid Raw, and Hybrid Final, per dataset. Hybrid Raw overpredicts Uncertain on the open-world datasets; uncertainty-gated repair shifts mass back toward determinate labels and narrows the gap with the gold distribution.
Hybrid vs.
Δ
95% CI
p
pHolm
FOLIO
Logic-LM
+5.3
[2.3,8.5]
<.001
<.001
LINC
+10.3
[5.8,15.1]
<.001
<.001
CLOVER
+12.3
[8.2,16.6]
<.001
<.001
Standard
+8.4
[5.9,11.0]
<.001
<.001
CoT
+7.5
[5.2,9.9]
<.001
<.001
Autoform.
+10.9
[6.7,15.2]
<.001
<.001
Appendix
Table 9: All tests of Hybrid’s accuracy gain averaged over the five models. Δ : Hybrid’s accuracy minus the method’s (points); 95% CI : paired bootstrap interval over examples; p : two-sided sign-flip test; pHolm : Holm-corrected within family. Baseline rows under FOLIO and ProverQA form the primary family and those under ProofWriter and PrOntoQA the secondary family; † : repair family.
DeepSeek
GPT-5
Gemini 3.1
Grok
Qwen 3.5
Dataset
Hybrid vs.
V4 Flash
Nano
Flash-Lite
4.3
Flash
FOLIO
Logic-LM
+4.9 (15/6)
+9.3∗ (21/4)
+8.2 (20/5)
+2.7 (13/8)
+1.1 (10/8)
LINC
+7.1 (19/6)
+9.9∗ (22/4)
+14.8∗ (32/5)
+12.6∗ (29/6)
+7.1 (24/11)
CLOVER
+13.2∗ (30/6)
+9.3 (22/5)
+13.2∗ (27/3)
+13.7∗ (32/7)
+12.1∗ (29/7)
Standard
+3.8 (9/2)
+8.2 (19/4)
+22.0∗ (41/1)
+4.4 (11/3)
+3.3 (8/2)
CoT
+6.0 (13/2)
+11.0∗ (22/2)
+12.1∗ (23/1)
+3.3 (9/3)
+4.9 (12/3)
Appendix
Table 10: Per-model exact McNemar tests. Each cell gives Hybrid’s accuracy minus the other method’s (points) and, in parentheses, the number of examples only Hybrid gets right / only the other method gets right. ∗ : Holm-corrected p<.05 within the test’s family (Appendix G ). The Hybrid Raw rows compare Hybrid Final with its own Stage-1 verdict; their counts equal the Helpful and Harmful columns of Table 8 .
Gated
Ungated
Dataset
Model
Raw
None
All
Validated †
None
All
Validated
FOLIO
DeepSeek V4 Flash
85.2
88.5
87.9
88.5
88.5
88.5
89.0
GPT-5 Nano
74.7
83.0
83.5
87.4
83.0
83.5
86.8
Gemini 3.1 Flash-Lite
82.4
87.9
80.2
89.0
87.4
79.7
88.5
Grok 4.3
84.6
87.9
87.9
88.5
89.0
87.9
88.5
Qwen 3.5 Flash
84.6
87.4
86.3
88.5
86.8
86.3
88.5
Appendix
Table 11: Stage-3 ablations by model: accuracy (%) of the raw Stage-1 verdict and of every repair variant. Gated repair revises only raw Uncertain verdicts; Ungated repair runs on every instance and overwrites a decisive raw verdict when it discharges the opposite side. Columns give the derivations in the repair premise set: None (repair from P alone), All proposed derivations, or Validated derivations only. † The full system. Bold : best of the six variants in each row. Mean rows average over the five models; the All datasets row averages the four dataset means.
Raw verdict (%)
Abstentions after repair (%)
Dataset
n
Correct
Abstain
Opposite
Correct
Wrong
Open
FOLIO
585
77.1
19.7
3.1
48.7
3.5
47.8
ProofWriter
750
81.2
18.7
0.1
77.1
0.0
22.9
ProverQA
700
51.1
47.4
1.4
48.2
8.7
43.1
Appendix
Table 12: Stage-1 outcomes on decidable (gold True / False ) instances, pooled over models. Opposite : the raw verdict proves the wrong side. The right block follows the abstentions through repair: relabelled correctly, relabelled wrongly, or left Uncertain ( Open ). One FOLIO instance has no raw verdict.
Pooled
Abstentions per model (of 30)
Depth
Abst.
Final
#Der.
DS
GPT
Gem.
Grok
Qwen
1
2.0
100.0
2.4
0
0
3
0
0
2
16.7
96.7
3.3
4
2
9
5
5
3
25.3
92.7
4.1
2
2
20
10
4
4
24.7
89.3
5.1
6
4
12
10
5
5
24.7
99.3
5.8
0
0
20
12
5
Appendix
Table 13: ProofWriter decidable instances by gold proof depth ( n=150 per depth, pooled over models). Abst. : raw abstention rate (%); Final : accuracy after repair (%); #Der. : mean derivations per tree. Model columns: DeepSeek V4 Flash, GPT-5 Nano, Gemini 3.1 Flash-Lite, Grok 4.3, Qwen 3.5 Flash.
Natural language understanding requires interleaving textual and logical reasoning, yet large language models often fail to perform such reasoning reliably. Existing neurosymbolic systems combine LLMs with solvers but remain limited to fully formalizable tasks such as math or program synthesis, leaving natural documents with only partial logical structure unaddressed. We introduce Logitext, a neurosymbolic language that represents documents as natural language text constraints (NLTCs), making partial logical structure explicit. We develop an algorithm that integrates LLM-based constraint evaluation with satisfiability modulo theory (SMT) solving, enabling joint textual-logical reasoning. Experiments on a new content moderation benchmark, together with LegalBench and Super-Natural Instructions, show that Logitext improves both accuracy and coverage. This work is the first that treats LLM-based reasoning as an SMT theory, extending neurosymbolic methods beyond fully formalizable domains.
Hyunseok Oh, Sam Stern, Youngki Lee +1
Seoul National University · U. Mass. Amherst · Microsoft
Large language models (LLMs) are increasingly deployed for natural-language logical reasoning, where the final answer is easy to check but the proof behind it is not. In natural-language logical reasoning, an intermediate conclusion should follow from its premises, and the resulting derivation should support the final answer. Existing methods lack machine-checkable verification of intermediate conclusions and answer-supporting proof dependencies, so they may assign credit to invalid or answer-irrelevant steps. We propose Proof-R1, an RL framework from formal verification that trains LLMs to construct verifiable proofs for natural-language logical reasoning. Proof-R1 admits a generated conclusion into the verified proof state only when the corresponding reasoning action satisfies the proof obligations through UNSAT-based machine-checkable formal verification. Proof-R1 also recovers the answer-supporting dependency closure to trace the proof structure of the final answer and align outcome credit with the proof dependencies. Experiments demonstrate that Proof-R1 improves answer accuracy across three logical reasoning benchmarks and four backbone models and outperforms training-free agents and training-based methods in terms of reasoning-process verifiability.
Qili Zhang, Qianren Mao, Hanze Cai +11
Zhongguancun Laboratory · Beihang University · Nanyang Technological University +1
Large language models (LLMs) are highly capable at language generation, but they remain unreliable when reasoning requires explicit symbolic structure, multi-step inference, and interpretable uncertainty. This paper presents a neuro-symbolic framework for translating natural-language reasoning problems into executable formal representations using first-order logic (FOL) and Narsese, the language of the Non-Axiomatic Reasoning System (NARS). To support this direction, we introduce NARS-Reasoning-v0.1, a benchmark of natural-language reasoning problems paired with FOL forms, executable Narsese programs, and three gold labels: True, False, and Uncertain. We develop a deterministic compilation pipeline from FOL to executable Narsese and validate retained examples through runtime execution in OpenNARS for Applications (ONA), ensuring that the symbolic targets are not only syntactically well formed but also behaviorally aligned with the intended answer. We further present Language-Structured Perception (LSP), a formulation in which an LLM is trained to produce reasoning-relevant symbolic structure rather than only a final verbal response. As an initial proof of concept, we also train and release a Phi-2 LoRA adapter on NARS-Reasoning-v0.1 for three-label reasoning classification, showing that the benchmark can support supervised adaptation in addition to executable evaluation. Overall, the paper positions executable symbolic generation and execution-based validation as a practical path toward more reliable neuro-symbolic reasoning systems.