# Going Beyond Approximation: Encoding Constraints for Explainable Multi-hop Inference via Differentiable Combinatorial Solvers

arXiv: https://arxiv.org/abs/2208.03339 · HTML: https://mlsanity.com/paper/2208.03339/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 43 references that are in the map.
- First posted on arXiv 5 Aug 2022.

## Builds on (most cited first, 27 of 27)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [ConceptNet 5.5: An Open Multilingual Graph of General Knowledge](https://mlsanity.com/paper/1612.03975/) (2016)
- [MPNet: Masked and Permuted Pre-training for Language Understanding](https://mlsanity.com/paper/2004.09297/) (2020)
- [RACE: Large-scale ReAding Comprehension Dataset From Examinations](https://mlsanity.com/paper/1704.04683/) (2017)
- [UnifiedQA: Crossing Format Boundaries With a Single QA System](https://mlsanity.com/paper/2005.00700/) (2020)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Transformers as Soft Reasoners over Language](https://mlsanity.com/paper/2002.05867/) (2020)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [WorldTree: A Corpus of Explanation Graphs for Elementary Science Questions supporting Multi-Hop Inference](https://mlsanity.com/paper/1802.03052/) (2018)
- [Quick and (not so) Dirty: Unsupervised Selection of Justification Sentences for Multi-hop Question Answering](https://mlsanity.com/paper/1911.07176/) (2019)
- [PRover: Proof Generation for Interpretable Reasoning over Rules](https://mlsanity.com/paper/2010.02830/) (2020)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [A Survey on Explainability in Machine Reading Comprehension](https://mlsanity.com/paper/2010.00389/) (2020)
- [Answering Complex Questions Using Open Information Extraction](https://mlsanity.com/paper/1704.05572/) (2017)
- [Dynamic Semantic Graph Construction and Reasoning for Explainable Multi-hop Science Question Answering](https://mlsanity.com/paper/2105.11776/) (2021)
- [Hybrid Autoregressive Inference for Scalable Multi-hop Explanation Regeneration](https://mlsanity.com/paper/2107.11879/) (2021)
- [Exploiting Explicit Paths for Multi-hop Reading Comprehension](https://mlsanity.com/paper/1811.01127/) (2018)
- [multiPRover: Generating Multiple Proofs for Improved Interpretability in Rule Reasoning](https://mlsanity.com/paper/2106.01354/) (2021)
- [Question Answering as Global Reasoning over Semantic Abstractions](https://mlsanity.com/paper/1906.03672/) (2019)
- [Question Answering via Integer Programming over Semi-Structured Knowledge](https://mlsanity.com/paper/1604.06076/) (2016)
- [Learning to Attend On Essential Terms: An Enhanced Retriever-Reader Model for Open-domain Question Answering](https://mlsanity.com/paper/1808.09492/) (2018)
- [KG^2: Learning to Reason Science Exam Questions with Contextual Knowledge Graph Embeddings](https://mlsanity.com/paper/1805.12393/) (2018)
- [Diff-Explainer: Differentiable Convex Optimization for Explainable Multi-hop Inference](https://mlsanity.com/paper/2105.03417/) (2021)
- [The limits of SDP relaxations for general-valued CSPs](https://mlsanity.com/paper/1612.01147/) (2016)

## Built on by (most cited first, 1 of 1)

- [Accountable and Explainable Methods for Complex Reasoning over Text](https://mlsanity.com/paper/2211.04946/) (2022)

## Abstract (arXiv)

Integer Linear Programming (ILP) provides a viable mechanism to encode explicit and controllable assumptions about explainable multi-hop inference with natural language. However, an ILP formulation is non-differentiable and cannot be integrated into broader deep learning architectures. Recently, Thayaparan et al. (2021a) proposed a novel methodology to integrate ILP with Transformers to achieve end-to-end differentiability for complex multi-hop inference. While this hybrid framework has been demonstrated to deliver better answer and explanation selection than transformer-based and existing ILP solvers, the neuro-symbolic integration still relies on a convex relaxation of the ILP formulation, which can produce sub-optimal solutions. To improve these limitations, we propose Diff-Comb Explainer, a novel neuro-symbolic architecture based on Differentiable BlackBox Combinatorial solvers (DBCS) (Poganvci'c et al., 2019). Unlike existing differentiable solvers, the presented model does not require the transformation and relaxation of the explicit semantic constraints, allowing for direct and more efficient integration of ILP formulations. Diff-Comb Explainer demonstrates improved accuracy and explainability over non-differentiable solvers, Transformers and existing differentiable constraint-based multi-hop inference frameworks.