# Question Answering via Integer Programming over Semi-Structured Knowledge

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2016.

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

- [Biomedical Question Answering: A Survey of Approaches and Challenges](https://mlsanity.com/paper/2102.05281/) (2021)
- [Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts](https://mlsanity.com/paper/2204.07312/) (2022)
- [VNHSGE: VietNamese High School Graduation Examination Dataset for Large Language Models](https://mlsanity.com/paper/2305.12199/) (2023)
- [Diff-Explainer: Differentiable Convex Optimization for Explainable Multi-hop Inference](https://mlsanity.com/paper/2105.03417/) (2021)
- [On the Challenges of Evaluating Compositional Explanations in Multi-Hop Inference: Relevance, Completeness, and Expert Ratings](https://mlsanity.com/paper/2109.03334/) (2021)
- [Knowledge Graphs are all you need: Leveraging KGs in Physics Question Answering](https://mlsanity.com/paper/2412.05453/) (2024)
- [Long-context Non-factoid Question Answering in Indic Languages](https://mlsanity.com/paper/2504.13615/) (2025)
- [Going Beyond Approximation: Encoding Constraints for Explainable Multi-hop Inference via Differentiable Combinatorial Solvers](https://mlsanity.com/paper/2208.03339/) (2022)
- [A Comprehensive Survey on Multi-hop Machine Reading Comprehension Datasets and Metrics](https://mlsanity.com/paper/2212.04070/) (2022)
- [A Comprehensive Survey on Multi-hop Machine Reading Comprehension Approaches](https://mlsanity.com/paper/2212.04072/) (2022)
- [Navigating Healthcare Insights: A Birds Eye View of Explainability with Knowledge Graphs](https://mlsanity.com/paper/2309.16593/) (2023)
- [A Differentiable Integer Linear Programming Solver for Explanation-Based Natural Language Inference](https://mlsanity.com/paper/2404.02625/) (2024)
- [Automated Answer Validation using Text Similarity](https://mlsanity.com/paper/2401.08688/) (2024)

## Abstract (arXiv)

Answering science questions posed in natural language is an important AI challenge. Answering such questions often requires non-trivial inference and knowledge that goes beyond factoid retrieval. Yet, most systems for this task are based on relatively shallow Information Retrieval (IR) and statistical correlation techniques operating on large unstructured corpora. We propose a structured inference system for this task, formulated as an Integer Linear Program (ILP), that answers natural language questions using a semi-structured knowledge base derived from text, including questions requiring multi-step inference and a combination of multiple facts. On a dataset of real, unseen science questions, our system significantly outperforms (+14%) the best previous attempt at structured reasoning for this task, which used Markov Logic Networks (MLNs). It also improves upon a previous ILP formulation by 17.7%. When combined with unstructured inference methods, the ILP system significantly boosts overall performance (+10%). Finally, we show our approach is substantially more robust to a simple answer perturbation compared to statistical correlation methods.