Skip to main content

References

📍 Where we are: The evidence base for the whole volume, gathered in one place.

Every inline marker like [1] in a chapter resolves here. References are grouped by chapter, and the numbering is local to each chapter — each chapter’s list restarts at [1], so find the chapter heading first, then the number. Each entry gives the author, title, venue, and year, is annotated with what it supports, and closes with a bracketed evidence-tier tag.

Justifications: Minimal Proofs and Pinpointing​

  1. Reiter, R. "A Theory of Diagnosis from First Principles." Artificial Intelligence, 1987. — The hitting-set tree and the diagnosis/repair duality this chapter implements. [Evidence tier: peer-reviewed]
  2. Schlobach, S., and Cornet, R. "Non-Standard Reasoning Services for the Debugging of Description Logic Terminologies." IJCAI, 2003. — Axiom pinpointing named and motivated: MinA/MUPS for ontology debugging. [Evidence tier: peer-reviewed]
  3. Kalyanpur, A., Parsia, B., Horridge, M., and Sirin, E. "Finding All Justifications of OWL DL Entailments." ISWC/ASWC, 2007. — The practical all-justifications algorithm: black-box search with hitting sets. [Evidence tier: peer-reviewed]
  4. Baader, F., and Peñaloza, R. "Axiom Pinpointing in General Tableaux." Journal of Logic and Computation, 2010. — Glass-box pinpointing: the pinpointing formula and its complexity. [Evidence tier: peer-reviewed]
  5. Horridge, M., Parsia, B., and Sattler, U. "Laconic and Precise Justifications in OWL." ISWC, 2008. — Sub-axiom granularity: justifications refined below the axiom level. [Evidence tier: peer-reviewed]
  6. Baader, F., Peñaloza, R., and Suntisrivaraporn, B. "Pinpointing in the Description Logic EL+." KI, 2007. — Pinpointing brought to the EL family: the linear-size TBox family with exponentially many MinAs, and the NP-completeness of finding a MinA within a size bound. [Evidence tier: peer-reviewed]
  7. Suntisrivaraporn, B., Qi, G., Ji, Q., and Haase, P. "A Modularization-Based Approach to Finding All Justifications for OWL DL Entailments." ASWC, 2008. — Locality-based modules provably contain every justification of the target entailment; extract the module, then pinpoint inside it. [Evidence tier: peer-reviewed]
  8. Kazakov, Y., Krötzsch, M., and Simančík, F. "The Incredible ELK: From Polynomial Procedures to Efficient Reasoning with EL Ontologies." Journal of Automated Reasoning, 2014. — Consequence-based proofs as the substrate for proof-driven justification tooling. [Evidence tier: peer-reviewed]
  9. Kazakov, Y., and Skočovský, P. "Enumerating Justifications Using Resolution." IJCAR, 2018. — Proof-driven enumeration: justifications mined by resolution from the inferences a consequence-based reasoner records. [Evidence tier: peer-reviewed]

Faithfulness: When an Explanation Is Honest​

  1. Jain, S., and Wallace, B. C. "Attention Is Not Explanation." NAACL, 2019. — Adversarial attention distributions: attention weights need not report the computation. [Evidence tier: peer-reviewed]
  2. Wiegreffe, S., and Pinter, Y. "Attention Is Not Not Explanation." EMNLP, 2019. — The rebuttal: what the adversarial construction does and does not show. [Evidence tier: peer-reviewed]
  3. DeYoung, J., Jain, S., Rajani, N. F., Lehman, E., Xiong, C., Socher, R., and Wallace, B. C. "ERASER: A Benchmark to Evaluate Rationalized NLP Models." ACL, 2020. — Comprehensiveness and sufficiency standardized; the erasure benchmark. [Evidence tier: peer-reviewed]
  4. Turpin, M., Michael, J., Perez, E., and Bowman, S. R. "Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting." NeurIPS, 2023. — Measured unfaithfulness of free-form reasoning at the frontier. [Evidence tier: peer-reviewed]
  5. Hooker, S., Erhan, D., Kindermans, P.-J., and Kim, B. "A Benchmark for Interpretability Methods in Deep Neural Networks." NeurIPS, 2019. — ROAR: retraining on erased inputs to separate information loss from off-manifold shock. [Evidence tier: peer-reviewed]
  6. Lipton, Z. C. "The Mythos of Model Interpretability." Communications of the ACM, 2018. — The conceptual map: plausibility, transparency, and post-hoc explanation disentangled. [Evidence tier: peer-reviewed]

Rule Extraction: Reading Rules Out of Weights​

  1. Andrews, R., Diederich, J., and Tickle, A. B. "Survey and Critique of Techniques for Extracting Rules from Trained Artificial Neural Networks." Knowledge-Based Systems, 1995. — The taxonomy (decompositional/pedagogical/eclectic) and the fidelity criterion. [Evidence tier: peer-reviewed]
  2. Quinlan, J. R. "Induction of Decision Trees." Machine Learning, 1986. — ID3: the information-gain decision-tree learner the pedagogical exhibit runs. [Evidence tier: peer-reviewed]
  3. McCluskey, E. J. "Minimization of Boolean Functions." Bell System Technical Journal, 1956. — The Quine–McCluskey prime-implicant minimization behind the exhibit's exhaustive pass. [Evidence tier: peer-reviewed]
  4. Craven, M., and Shavlik, J. "Extracting Tree-Structured Representations of Trained Networks." NeurIPS, 1996. — TREPAN: pedagogical extraction with membership queries and fidelity-driven growth. [Evidence tier: peer-reviewed]
  5. Towell, G. G., and Shavlik, J. W. "Knowledge-Based Artificial Neural Networks." Artificial Intelligence, 1994. — KBANN: the insert and refine legs of the round trip (theory insertion, then backpropagation refinement). [Evidence tier: peer-reviewed]
  6. Towell, G. G., and Shavlik, J. W. "Extracting Refined Rules from Knowledge-Based Neural Networks." Machine Learning, 1993. — The extraction leg of the KBANN round trip: MofN rules read out of the refined network, measured to outperform the inserted theory. [Evidence tier: peer-reviewed]
  7. Yang, F., Yang, Z., and Cohen, W. W. "Differentiable Learning of Logical Rules for Knowledge Base Reasoning." NeurIPS, 2017. — Neural-LP's attention-unrolling extraction, reused here on Volume 4's trained model. [Evidence tier: peer-reviewed]
  8. Sadeghian, A., Armandpour, M., Ding, P., and Wang, D. Z. "DRUM: End-to-End Differentiable Rule Mining on Knowledge Graphs." NeurIPS, 2019. — Confidence-carrying rule readout via low-rank attention chains; the rank-1 entanglement theorem. [Evidence tier: peer-reviewed]

Reasoning Shortcuts: Right Answer, Wrong Reason​

  1. Marconato, E., Teso, S., Vergari, A., and Passerini, A. "Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts." NeurIPS, 2023. — The definition, the counting theorem over relabelings, the four factors, and the mitigation levers. [Evidence tier: peer-reviewed]
  2. Geirhos, R., Jacobsen, J.-H., Michaelis, C., Zemel, R., Brendel, W., Bethge, M., and Wichmann, F. A. "Shortcut Learning in Deep Neural Networks." Nature Machine Intelligence, 2020. — The broader shortcut phenomenon this chapter's formal version instantiates. [Evidence tier: peer-reviewed]
  3. Marconato, E., Bortolotti, S., van Krieken, E., Vergari, A., Passerini, A., and Teso, S. "BEARS Make Neuro-Symbolic Models Aware of Their Reasoning Shortcuts." UAI, 2024. — Shortcut awareness via calibrated concept ensembles; the detection line. [Evidence tier: peer-reviewed]
  4. Manhaeve, R., Dumančić, S., Kimmig, A., Demeester, T., and De Raedt, L. "Neural Probabilistic Logic Programming in DeepProbLog." Artificial Intelligence, 2021. — The distant-supervision predictor shape whose fine print this chapter reads. [Evidence tier: peer-reviewed]

Identifiability: Why Accuracy Never Certifies Meaning​

  1. Marconato, E., Teso, S., Vergari, A., and Passerini, A. "Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts." NeurIPS, 2023. — Definition 1, Theorem 2, and Propositions 4–5: the characterization and count of reasoning-shortcut optima, with mitigations, that this chapter recasts as a symmetry group. [Evidence tier: peer-reviewed]
  2. Locatello, F., Bauer, S., Lucic, M., Rätsch, G., Gelly, S., Schölkopf, B., and Bachem, O. "Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations." ICML, 2019. — The impossibility of unsupervised disentanglement: the same fiber argument in representation learning. [Evidence tier: peer-reviewed]
  3. Khemakhem, I., Kingma, D. P., Monti, R. P., and Hyvärinen, A. "Variational Autoencoders and Nonlinear ICA: A Unifying Framework." AISTATS, 2020. — Identifiability restored by conditioning: the auxiliary-variable escape route in latent-variable models. [Evidence tier: peer-reviewed]
  4. D'Amour, A., et al. "Underspecification Presents Challenges for Credibility in Modern Machine Learning." Journal of Machine Learning Research, 2022. — Many optima, identical test metrics, divergent deployment behavior: the phenomenon at industrial scale. [Evidence tier: peer-reviewed]
  5. Koh, P. W., Nguyen, T., Tang, Y. S., Mussmann, S., Pierson, E., Kim, B., and Liang, P. "Concept Bottleneck Models." ICML, 2020. — The architecture family whose concept semantics this mathematics governs. [Evidence tier: peer-reviewed]

Measuring Shortcuts: rsbench and Concept Quality​

  1. Bortolotti, S., Marconato, E., Carraro, T., Morettin, P., van Krieken, E., Vergari, A., Teso, S., and Passerini, A. "A Neuro-Symbolic Benchmark Suite for Concept Quality and Reasoning Shortcuts." NeurIPS Datasets and Benchmarks, 2024. — rsbench: generators, the count-rss #SAT counter, and the concept-quality metric panel. [Evidence tier: peer-reviewed]
  2. Marconato, E., Teso, S., Vergari, A., and Passerini, A. "Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts." NeurIPS, 2023. — The theory the suite operationalizes. [Evidence tier: peer-reviewed]
  3. Chakraborty, S., Meel, K. S., and Vardi, M. Y. "A Scalable Approximate Model Counter." CP, 2013. — The approximate #SAT counting behind shortcut counting at scale. [Evidence tier: peer-reviewed]
  4. Koh, P. W., Nguyen, T., Tang, Y. S., Mussmann, S., Pierson, E., Kim, B., and Liang, P. "Concept Bottleneck Models." ICML, 2020. — The concept-supervised baseline family in the suite's harness. [Evidence tier: peer-reviewed]
  5. Geirhos, R., Jacobsen, J.-H., Michaelis, C., Zemel, R., Brendel, W., Bethge, M., and Wichmann, F. A. "Shortcut Learning in Deep Neural Networks." Nature Machine Intelligence, 2020. — Why OOD evaluation is the general-purpose shortcut alarm. [Evidence tier: peer-reviewed]
  6. Marconato, E., Bortolotti, S., van Krieken, E., Vergari, A., Passerini, A., and Teso, S. "BEARS Make Neuro-Symbolic Models Aware of Their Reasoning Shortcuts." UAI, 2024. — Ensemble disagreement across independently trained models as the shortcut-awareness signal when gold concepts are unavailable. [Evidence tier: peer-reviewed]

Calibration: Confidence That Means Something​

  1. Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. "On Calibration of Modern Neural Networks." ICML, 2017. — Modern networks miscalibrate; temperature scaling as the minimal effective repair. [Evidence tier: peer-reviewed]
  2. Naeini, M. P., Cooper, G. F., and Hauskrecht, M. "Obtaining Well Calibrated Probabilities Using Bayesian Binning." AAAI, 2015. — ECE as the binned calibration summary; the estimator this chapter implements. [Evidence tier: peer-reviewed]
  3. Brier, G. W. "Verification of Forecasts Expressed in Terms of Probability." Monthly Weather Review, 1950. — The Brier score and the origin of probabilistic forecast verification. [Evidence tier: peer-reviewed]
  4. DeGroot, M. H., and Fienberg, S. E. "The Comparison and Evaluation of Forecasters." The Statistician, 1983. — The calibration-plus-refinement reading of forecast scores; the source of the two-part decomposition this chapter derives. [Evidence tier: peer-reviewed]
  5. Niculescu-Mizil, A., and Caruana, R. "Predicting Good Probabilities with Supervised Learning." ICML, 2005. — Which learners miscalibrate and how: margin maximizers' sigmoid-shaped too-moderate distortion, naive Bayes' too-extreme one, and the Platt/isotonic repairs. [Evidence tier: peer-reviewed]
  6. Tabacof, P., and Costabello, L. "Probability Calibration for Knowledge Graph Embedding Models." ICLR, 2020. — KGE models measured as uncalibrated out of the box; post-hoc repair with Platt scaling and isotonic regression. [Evidence tier: peer-reviewed]
  7. Marconato, E., Bortolotti, S., van Krieken, E., Vergari, A., Passerini, A., and Teso, S. "BEARS Make Neuro-Symbolic Models Aware of Their Reasoning Shortcuts." UAI, 2024. — Calibration meeting the shortcut problem: confidence that tracks concept uncertainty. [Evidence tier: peer-reviewed]

Abstention: Knowing When You Do Not Know​

  1. Chow, C. K. "On Optimum Recognition Error and Reject Tradeoff." IEEE Transactions on Information Theory, 1970. — The cost-optimal rejection rule this chapter derives. [Evidence tier: peer-reviewed]
  2. El-Yaniv, R., and Wiener, Y. "On the Foundations of Noise-free Selective Classification." Journal of Machine Learning Research, 2010. — Selective prediction formalized: coverage, selective risk, and the perfect-selective regime. [Evidence tier: peer-reviewed]
  3. Geifman, Y., and El-Yaniv, R. "Selective Classification for Deep Neural Networks." NeurIPS, 2017. — Risk-coverage curves for deep models; the selective-risk practice this chapter implements. [Evidence tier: peer-reviewed]
  4. Hendrycks, D., and Gimpel, K. "A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks." ICLR, 2017. — Maximum softmax probability as the default confidence signal and its limits. [Evidence tier: peer-reviewed]
  5. Geifman, Y., Uziel, G., and El-Yaniv, R. "Bias-Reduced Uncertainty Estimation for Deep Neural Classifiers." ICLR, 2019. — AURC and E-AURC defined: the risk-coverage area summary this chapter computes. [Evidence tier: peer-reviewed]
  6. Marconato, E., Bortolotti, S., van Krieken, E., Vergari, A., Passerini, A., and Teso, S. "BEARS Make Neuro-Symbolic Models Aware of Their Reasoning Shortcuts." UAI, 2024. — Abstaining on concept uncertainty, not just label confidence. [Evidence tier: peer-reviewed]

Materialization versus Rewriting: Two Ways to Scale​

  1. Motik, B., Nenov, Y., Piro, R., Horrocks, I., and Olteanu, D. "Parallel Materialisation of Datalog Programs in Centralised, Main-Memory RDF Systems." AAAI, 2014. — Semi-naive parallel materialization: the by-triple partitioning and lock-light design. [Evidence tier: peer-reviewed]
  2. Nenov, Y., Piro, R., Motik, B., Horrocks, I., Wu, Z., and Banerjee, J. "RDFox: A Highly-Scalable RDF Store." ISWC, 2015. — The materialization engine at scale: reported multicore scaling and throughput. [Evidence tier: peer-reviewed]
  3. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., and Rosati, R. "Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family." Journal of Automated Reasoning, 2007. — FO-rewritability: the fragment where rewriting is complete by theorem. [Evidence tier: peer-reviewed]
  4. Motik, B., Nenov, Y., Piro, R., and Horrocks, I. "Incremental Update of Datalog Materialisation: the Backward/Forward Algorithm." AAAI, 2015. — Deletion without over-deleting: the alternative-derivation check. [Evidence tier: peer-reviewed]
  5. Gupta, A., Mumick, I. S., and Subrahmanian, V. S. "Maintaining Views Incrementally." SIGMOD, 1993. — DRed: the classical delete-and-rederive discipline. [Evidence tier: peer-reviewed]
  6. Libkin, L. Elements of Finite Model Theory. Springer, 2004. — The locality argument behind the imported theorem: transitive closure is not first-order expressible. [Evidence tier: textbook]
  7. Steigmiller, A., Liebig, T., and Glimm, B. "Konclude: System Description." Journal of Web Semantics, 2014. — Absorption in a tableau reasoner: general axioms rewritten to trigger lazily; this chapter's analogy for the rewriting instinct beyond Horn. [Evidence tier: peer-reviewed]

GPU Reasoning: Batching the Fixpoint​

  1. Baader, F., Lutz, C., and Suntisrivaraporn, B. "CEL — A Polynomial-Time Reasoner for Life Science Ontologies." IJCAR, 2006. — The EL completion calculus whose saturation this chapter vectorizes. [Evidence tier: peer-reviewed]
  2. Kazakov, Y., Krötzsch, M., and Simančík, F. "The Incredible ELK: From Polynomial Procedures to Efficient Reasoning with EL Ontologies." Journal of Automated Reasoning, 2014. — The optimized CPU saturation baseline: what worklist engineering achieves before vectorization. [Evidence tier: peer-reviewed]
  3. Motik, B., Nenov, Y., Piro, R., Horrocks, I., and Olteanu, D. "Parallel Materialisation of Datalog Programs in Centralised, Main-Memory RDF Systems." AAAI, 2014. — Parallel fixpoints at scale: the multicore anchor for the batching thesis. [Evidence tier: peer-reviewed]
  4. Nenov, Y., Piro, R., Motik, B., Horrocks, I., and Wu, Z. "RDFox: A Highly-Scalable RDF Store." ISWC, 2015. — The parallel-materialization line's system report: speedups up to 87-fold at 128 cores, sustaining millions of triples per second. [Evidence tier: peer-reviewed]
  5. Hohenecker, P., and Lukasiewicz, T. "Ontology Reasoning with Deep Neural Networks." Journal of Artificial Intelligence Research, 2020. — The mature neural emulation of a Datalog materialization reasoner (RDFox): inferable-relation F1 0.916–0.999, trained per ontology (the accuracy side of the trade). [Evidence tier: peer-reviewed]
  6. Hohenecker, P., and Lukasiewicz, T. "Deep Learning for Ontology Reasoning." arXiv:1705.10342, 2017. — The earlier report in the emulation line: up to two orders of magnitude faster than RDFox at F1 near 0.95 (the speed side of the trade). [Evidence tier: preprint]
  7. Maene, J., Derkinderen, V., and Zuidberg Dos Martires, P. "KLay: Accelerating Arithmetic Circuits for Neurosymbolic AI." ICLR, 2025. — The sibling move one layer down: circuit evaluation layerized for accelerators (Volume 4's chapter, revisited as systems kin). [Evidence tier: peer-reviewed]

The Work-Depth Trilemma​

  1. JáJá, J. An Introduction to Parallel Algorithms. Addison-Wesley, 1992. — Work, depth, and the PRAM toolkit: the textbook frame this chapter counts in. [Evidence tier: textbook]
  2. Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, 1995. — P-complete problems and why they resist polylog depth: the wall named precisely. [Evidence tier: textbook]
  3. Merrill, W., and Sabharwal, A. "The Parallelism Tradeoff: Limitations of Log-Precision Transformers." TACL, 2023. — The same trilemma inside neural architectures: constant depth as a complexity class. [Evidence tier: peer-reviewed]
  4. Immerman, N. Descriptive Complexity. Springer, 1999. — Transitive closure, NC, and the logical view of parallel complexity classes. [Evidence tier: textbook]
  5. Baader, F., Brandt, S., and Lutz, C. "Pushing the EL Envelope." IJCAI, 2005. — The PTIME membership theorem for the EL family: the polynomial-time completion algorithm behind the depth floor (the hardness half of PTIME-completeness rides on Horn satisfiability; see [2]). [Evidence tier: peer-reviewed]

The Transformer Depth Ceiling: TC⁰ and P​

  1. Merrill, W., and Sabharwal, A. "The Parallelism Tradeoff: Limitations of Log-Precision Transformers." TACL, 2023. — The TC⁰ containment for log-precision transformers; the ceiling theorem. [Evidence tier: peer-reviewed]
  2. Merrill, W., Sabharwal, A., and Smith, N. A. "Saturated Transformers are Constant-Depth Threshold Circuits." TACL, 2022. — The saturated-attention circuit class: how attention shape sets the class. [Evidence tier: peer-reviewed]
  3. Hao, Y., Angluin, D., and Frank, R. "Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity." TACL, 2022. — Hard unique attention inside AC⁰; the ladder's lower rung. [Evidence tier: peer-reviewed]
  4. Furst, M., Saxe, J. B., and Sipser, M. "Parity, Circuits, and the Polynomial-Time Hierarchy." Mathematical Systems Theory, 1984. — PARITY outside AC⁰: the unconditional separation anchoring the ladder. [Evidence tier: peer-reviewed]
  5. Strobl, L., Merrill, W., Weiss, G., Chiang, D., and Angluin, D. "What Formal Languages Can Transformers Express? A Survey." TACL, 2024. — The map of transformer expressiveness results this chapter samples from. [Evidence tier: peer-reviewed]
  6. Barrington, D. A. M., and Thérien, D. "Finite Monoids and the Fine Structure of NC¹." Journal of the ACM, 1988. — Solvable-group word problems lie in ACC⁰ ⊆ TC⁰: why the S₃ task can never witness the separation. [Evidence tier: peer-reviewed]
  7. Barrington, D. A. "Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹." Journal of Computer and System Sciences, 1989. — Barrington's theorem: iterated composition in the non-solvable S₅ is NC¹-complete; the table's conditional-exclusion row. [Evidence tier: peer-reviewed]

Chain-of-Thought: Recovering P at Decode Time​

  1. Merrill, W., and Sabharwal, A. "The Expressive Power of Transformers with Chain of Thought." ICLR, 2024. — The ladder: decode-step budgets as complexity classes, poly steps reaching P. [Evidence tier: peer-reviewed]
  2. Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., and Wang, L. "Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective." NeurIPS, 2023. — CoT's expressiveness gain formalized; arithmetic and DP tasks separated with and without steps. [Evidence tier: peer-reviewed]
  3. Nye, M., et al. "Show Your Work: Scratchpads for Intermediate Computation with Language Models." arXiv:2112.00114, 2021. — Training on intermediate computation: the scratchpad precedent. [Evidence tier: preprint]
  4. Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q., and Zhou, D. "Chain-of-Thought Prompting Elicits Reasoning in Large Language Models." NeurIPS, 2022. — The prompting result that made the loop famous. [Evidence tier: peer-reviewed]
  5. Merrill, W., and Sabharwal, A. "The Parallelism Tradeoff: Limitations of Log-Precision Transformers." TACL, 2023. — The no-decoding baseline the ladder is measured against. [Evidence tier: peer-reviewed]

Reinforcement Learning and Verifier-Gated Reasoning​

  1. Cobbe, K., et al. "Training Verifiers to Solve Math Word Problems." arXiv:2110.14168, 2021. — Learned verifiers reranking solutions: the modern verifier line's opening. [Evidence tier: preprint]
  2. Lightman, H., et al. "Let's Verify Step by Step." ICLR, 2024. — Process supervision beating outcome supervision; per-step judgment as the useful signal. [Evidence tier: peer-reviewed]
  3. Zelikman, E., Wu, Y., Mu, J., and Goodman, N. D. "STaR: Bootstrapping Reasoning with Reasoning." NeurIPS, 2022. — Expert iteration on self-generated, answer-checked rationales. [Evidence tier: peer-reviewed]
  4. Yang, K., Deng, J., and Chen, D. "Generating Natural Language Proofs with Verifier-Guided Search." EMNLP, 2022. — Verifier-guided stepwise proof search; the bottleneck aggregation of step scores. [Evidence tier: peer-reviewed]
  5. DeepSeek-AI. "DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning." arXiv:2501.12948, 2025. — Verifiable-reward RL at frontier scale, and its documented reward-model cautions. [Evidence tier: preprint]

The Seven Difficulty Axes Beyond Completeness​

  1. Clark, P., Tafjord, O., and Richardson, K. "Transformers as Soft Reasoners over Language." IJCAI, 2020. — Depth stratification and balanced question banks: the controlled-rulebase lineage. [Evidence tier: peer-reviewed]
  2. Poulis, A., Tsalapati, E., and Koubarakis, M. "Transformer-Based Language Models for Reasoning in the Description Logic ALCQ." NeLaMKRR@KR, 2024. — The depth-by-linguistic-complexity factorial grid with held-out levels. [Evidence tier: peer-reviewed]
  3. Sanyal, S., Liao, Z., and Ren, X. "RobustLR: A Diagnostic Benchmark for Evaluating Logical Robustness of Deductive Reasoners." EMNLP, 2022. — The logic-changing rule-edit probes, relabeled by the prover, that the flip probe restages. [Evidence tier: peer-reviewed]
  4. Saparov, A., and He, H. "Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought." ICLR, 2023. — Controlled ontology generation with per-axis knobs (hops, ordering, distractors). [Evidence tier: peer-reviewed]
  5. Li, B., et al. "LogiCity: Advancing Neuro-Symbolic AI with Abstract Urban Simulation." NeurIPS Datasets and Benchmarks, 2024. — Simulator difficulty modes: abstraction complexity, horizon, and compositional splits. [Evidence tier: peer-reviewed]
  6. Sinha, K., Sodhani, S., Dong, J., Pineau, J., and Hamilton, W. L. "CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text." EMNLP, 2019. — Length/compositional generalization as the diagnostic axis. [Evidence tier: peer-reviewed]

NeSy Benchmark Suites and Simulators​

  1. Bortolotti, S., Marconato, E., Carraro, T., Morettin, P., van Krieken, E., Vergari, A., Teso, S., and Passerini, A. "A Neuro-Symbolic Benchmark Suite for Concept Quality and Reasoning Shortcuts." NeurIPS Datasets and Benchmarks, 2024. — The concept-quality suite: generators, counters, metric panel. [Evidence tier: peer-reviewed]
  2. Li, B., et al. "LogiCity: Advancing Neuro-Symbolic AI with Abstract Urban Simulation." NeurIPS Datasets and Benchmarks, 2024. — The FOL simulator: tunable abstraction, long-horizon tasks, compositional splits. [Evidence tier: peer-reviewed]
  3. Lorello, L. S., Lippi, M., and Melacci, S. "The KANDY Benchmark: Incremental Neuro-Symbolic Learning and Reasoning with Kandinsky Patterns." Machine Learning, 2025 (earlier preprint: arXiv:2402.17431, 2024). — Procedural curricula with known symbolic rules and sparse supervision. [Evidence tier: peer-reviewed]
  4. Lorello, L. S., Manginas, N., Lippi, M., and Melacci, S. "LTLZinc: A Benchmarking Framework for Continual Learning and Neuro-Symbolic Temporal Reasoning." arXiv:2507.17482, 2025. — Temporal-constraint streams: LTL-over-constraints with continual metrics. [Evidence tier: preprint]
  5. Herron, D., Jiménez-Ruiz, E., Tarroni, G., and Weyde, T. "NeSy4VRD: A Multifaceted Resource for Neurosymbolic AI Research Using Knowledge Graphs in Visual Relationship Detection." arXiv:2305.13258, 2023. — Vision aligned to a real OWL ontology; materialization as supervision. [Evidence tier: preprint]

The Entailment-Benchmark Gap​

  1. Sanyal, S., Liao, Z., and Ren, X. "RobustLR: A Diagnostic Benchmark for Evaluating Logical Robustness of Deductive Reasoners." EMNLP, 2022. — Perturbation-consistency diagnostics over deductive rulebases. [Evidence tier: peer-reviewed]
  2. Ribeiro, M. T., Wu, T., Guestrin, C., and Singh, S. "Beyond Accuracy: Behavioral Testing of NLP Models with CheckList." ACL, 2020. — Invariance and directional-expectation testing as a methodology. [Evidence tier: peer-reviewed]
  3. Han, S., et al. "FOLIO: Natural Language Reasoning with First-Order Logic." EMNLP, 2024. — Prover-verified three-way entailment: the gold-standard protocol the gap is measured against. [Evidence tier: peer-reviewed]
  4. Poulis, A., Tsalapati, E., and Koubarakis, M. "Transformer-Based Language Models for Reasoning in the Description Logic ALCQ." NeLaMKRR@KR, 2024. — Controlled entailment with OWA labels and compositional generalization. [Evidence tier: peer-reviewed]
  5. Guo, Y., Pan, Z., and Heflin, J. "LUBM: A Benchmark for OWL Knowledge Base Systems." Journal of Web Semantics, 2005. — Query completeness and soundness as benchmark metrics: the ontology world's version of the invariance principle. [Evidence tier: peer-reviewed]

Symbolic Attention: Reasoning as a Single Burst​

  1. Baader, F., Brandt, S., and Lutz, C. "Pushing the EL Envelope." IJCAI, 2005. — The completion rules the operator renders as attention. [Evidence tier: peer-reviewed]
  2. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. "Attention Is All You Need." NeurIPS, 2017. — The attention machinery being repurposed: softmax relevance and the scaled-dot-product temperature; the fixed-depth layer stack, which this chapter additionally weight-ties. [Evidence tier: peer-reviewed]
  3. Hájek, P. Metamathematics of Fuzzy Logic. Kluwer, 1998. — The Gödel t-norm semantics that makes softmin/softmax a logic and not a heuristic. [Evidence tier: textbook]
  4. Rocktäschel, T., and Riedel, S. "End-to-End Differentiable Proving." NeurIPS, 2017. — The ancestral fusion of proof search with differentiable scoring; what the burst architecture replaces backward chaining with. [Evidence tier: peer-reviewed]
  5. Kazakov, Y., Krötzsch, M., and Simančík, F. "The Incredible ELK: From Polynomial Procedures to Efficient Reasoning with EL Ontologies." Journal of Automated Reasoning, 2014. — The saturation discipline (fire rules to fixpoint, order-independent) that justifies lockstep layers. [Evidence tier: peer-reviewed]

The SATORI Architecture: One Operator, Four Properties​

  1. Xiong, B., Potyka, N., Tran, T.-K., Nayyeri, M., and Staab, S. "Faithful Embeddings for EL++ Knowledge Bases." ISWC, 2022. — The box substrate for ontologies: containment as subsumption, the faithful-embedding line. [Evidence tier: peer-reviewed]
  2. Ren, H., Hu, W., and Leskovec, J. "Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings." ICLR, 2020. — The same geometry as query space: the substrate unifier. [Evidence tier: peer-reviewed]
  3. Green, T. J., Karvounarakis, G., and Tannen, V. "Provenance Semirings." PODS, 2007. — The annotation algebra the substrate carries through inference. [Evidence tier: peer-reviewed]
  4. Merrill, W., and Sabharwal, A. "The Parallelism Tradeoff: Limitations of Log-Precision Transformers." TACL, 2023. — The depth physics governing the scaling law's honest tier. [Evidence tier: peer-reviewed]
  5. Minervini, P., Riedel, S., Stenetorp, P., Grefenstette, E., and Rocktäschel, T. "Learning Reasoning Strategies in End-to-End Differentiable Proving." ICML, 2020. — Query-conditioned rule selection: the routing property's nearest ancestor. [Evidence tier: peer-reviewed]

The Eight Claims: C1–C8 and the Wedge​

  1. Ren, H., and Leskovec, J. "Beta Embeddings for Multi-Hop Logical Reasoning in Knowledge Graphs." NeurIPS, 2020. — The C1 baseline family and its evaluation protocol. [Evidence tier: peer-reviewed]
  2. Yang, F., Yang, Z., and Cohen, W. W. "Differentiable Learning of Logical Rules for Knowledge Base Reasoning." NeurIPS, 2017. — The C2 contrast class: differentiable rule learning by recurrent attention over relation operators, chain-shaped and length-capped rather than enumerated. [Evidence tier: peer-reviewed]
  3. DeYoung, J., Jain, S., Rajani, N. F., Lehman, E., Xiong, C., Socher, R., and Wallace, B. C. "ERASER: A Benchmark to Evaluate Rationalized NLP Models." ACL, 2020. — The C3 instrument: erasure-based faithfulness. [Evidence tier: peer-reviewed]
  4. Guo, C., Pleiss, G., Sun, Y., and Weinberger, K. Q. "On Calibration of Modern Neural Networks." ICML, 2017. — The C5 baseline instrument: temperature scaling and the fitted temperature. [Evidence tier: peer-reviewed]
  5. Naeini, M. P., Cooper, G. F., and Hauskrecht, M. "Obtaining Well Calibrated Probabilities Using Bayesian Binning." AAAI, 2015. — The binned ECE estimator C5's calibration number is computed with; Part III's source for the same formula. [Evidence tier: peer-reviewed]
  6. Nenov, Y., Piro, R., Motik, B., Horrocks, I., Wu, Z., and Banerjee, J. "RDFox: A Highly-Scalable RDF Store." ISWC, 2015. — The C4 prior art: CPU-parallel materialization throughput to beat. [Evidence tier: peer-reviewed]
  7. Aditya, D., et al. "PyReason: Software for Open World Temporal Logic." AAAI Spring Symposium Series, 2023. — The C4 baseline carrying open-world generalized-annotated (interval) semantics; its parallelism constraints keep the engine CPU-bound. [Evidence tier: peer-reviewed]
  8. Li, Z., Huang, J., and Naik, M. "Scallop: A Language for Neurosymbolic Programming." PLDI, 2023. — The C4 baseline with provenance-semiring reasoning over a CPU symbolic core. [Evidence tier: peer-reviewed]
  9. Jackermeier, M., Chen, J., and Horrocks, I. "Dual Box Embeddings for the Description Logic EL++." WWW, 2024. — Box2EL: the box-embedding line whose containment losses encode TBox structure; C6's geometric evidence at ontology scale. [Evidence tier: peer-reviewed]
  10. Yang, H., Chen, J., and Sattler, U. "TransBox: EL++-closed Ontology Embedding." WWW, 2025. — TransBox: EL++-closure and soundness for the same box-embedding line; with Box2EL, where C6's ablation grid would run. [Evidence tier: peer-reviewed]
  11. Hohenecker, P., and Lukasiewicz, T. "Ontology Reasoning with Deep Neural Networks." Journal of Artificial Intelligence Research, 2020. — The C7 contrast: per-ontology retraining that transfer claims must improve on. [Evidence tier: peer-reviewed]

Open Problems: The G1–G8 Gaps​

  1. Garcez, A. d'Avila, and Lamb, L. C. "Neurosymbolic AI: The 3rd Wave." Artificial Intelligence Review, 2023. — The field-level gap analysis the eight-gap map refines. [Evidence tier: peer-reviewed]
  2. Kautz, H. "The Third AI Summer: AAAI Robert S. Engelmore Memorial Lecture." AI Magazine, 2022. — The taxonomy of neural-symbolic integration patterns behind the wedge's family map. [Evidence tier: peer-reviewed]
  3. Marra, G., Dumančić, S., Manhaeve, R., and De Raedt, L. "From Statistical Relational to Neurosymbolic Artificial Intelligence: A Survey." Artificial Intelligence, 2024. — The design-space survey mapping which combinations of logic, probability, and learning have been built; the source of G1's two-corner framing and G3's inference-cost statement. [Evidence tier: peer-reviewed]
  4. van Harmelen, F., and ten Teije, A. "A Boxology of Design Patterns for Hybrid Learning and Reasoning Systems." Journal of Web Engineering, 2019. — The pattern language for hybrid systems; its meta-reasoning-for-control pattern is the nearest named pattern to G8's routing artifact. [Evidence tier: peer-reviewed]
  5. Marconato, E., Teso, S., Vergari, A., and Passerini, A. "Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts." NeurIPS, 2023. — G7's theoretical floor: what calibration must track. [Evidence tier: peer-reviewed]
  6. Minervini, P., Riedel, S., Stenetorp, P., Grefenstette, E., and Rocktäschel, T. "Learning Reasoning Strategies in End-to-End Differentiable Proving." ICML, 2020. — The CTP itself: query-conditioned rule-subset selection, G2's second partial answer. [Evidence tier: peer-reviewed]
  7. Merrill, W., and Sabharwal, A. "The Parallelism Tradeoff: Limitations of Log-Precision Transformers." TACL, 2023. — The depth physics constraining G3's ambitions. [Evidence tier: peer-reviewed]
  8. Colelough, B. C., and Regli, W. "Neuro-Symbolic AI in 2024: A Systematic Review." LNSAI Workshop, CEUR Vol-3819, 2024. — The census behind G8's five-percent figure: meta-cognition as the least-explored category, 8 of 167 papers reviewed. [Evidence tier: peer-reviewed]

Doing the Next Research: Blind Spots and First Steps​

  1. Lipton, Z. C., and Steinhardt, J. "Troubling Trends in Machine Learning Scholarship." ACM Queue, 2019. — The failure patterns the self-audit checklist defends against. [Evidence tier: position paper (ACM Queue magazine; ICML 2018 Debates workshop)]
  2. Ruffinelli, D., Broscheit, S., and Gemulla, R. "You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings." ICLR, 2020. — Protocol rigor changing conclusions: the methods lesson this series inherited in Volume 3. [Evidence tier: peer-reviewed]
  3. Bortolotti, S., Marconato, E., Carraro, T., Morettin, P., van Krieken, E., Vergari, A., Teso, S., and Passerini, A. "A Neuro-Symbolic Benchmark Suite for Concept Quality and Reasoning Shortcuts." NeurIPS Datasets and Benchmarks, 2024. — Instrument-building as a research contribution in its own right. [Evidence tier: peer-reviewed]
  4. Pineau, J., et al. "Improving Reproducibility in Machine Learning Research: A Report from the NeurIPS 2019 Reproducibility Program." Journal of Machine Learning Research, 2021. — The reproducibility discipline institutionalized: checklists, seeds, and code. [Evidence tier: peer-reviewed]

The Honest Verdict: The State of Neuro-Symbolic AI​

  1. Kautz, H. "The Third AI Summer: AAAI Robert S. Engelmore Memorial Lecture." AI Magazine, 2022. — The integration taxonomy the series' architectures populate. [Evidence tier: peer-reviewed]
  2. Garcez, A. d'Avila, and Lamb, L. C. "Neurosymbolic AI: The 3rd Wave." Artificial Intelligence Review, 2023. — The field-level case the verdict weighs. [Evidence tier: peer-reviewed]
  3. Marra, G., Dumančić, S., Manhaeve, R., and De Raedt, L. "From Statistical Relational to Neurosymbolic Artificial Intelligence: A Survey." Artificial Intelligence, 2024. — The design-space map five volumes walked. [Evidence tier: peer-reviewed]
  4. Merrill, W., and Sabharwal, A. "The Parallelism Tradeoff: Limitations of Log-Precision Transformers." TACL, 2023. — The depth physics in the settled column. [Evidence tier: peer-reviewed]
  5. Marconato, E., Teso, S., Vergari, A., and Passerini, A. "Not All Neuro-Symbolic Concepts Are Created Equal: Analysis and Mitigation of Reasoning Shortcuts." NeurIPS, 2023. — The trust mathematics in the settled column. [Evidence tier: peer-reviewed]