# Learning to Speed Up Structured Output Prediction

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2018.

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

- [The Integer Linear Programming Inference Cookbook](https://mlsanity.com/paper/2307.00171/) (2023)
- [Machine Learning for Combinatorial Optimisation of Partially-Specified Problems: Regret Minimisation as a Unifying Lens](https://mlsanity.com/paper/2205.10157/) (2022)
- [Lazy-k: Decoding for Constrained Token Classification](https://mlsanity.com/paper/2312.03367/) (2023)

## Abstract (arXiv)

Predicting structured outputs can be computationally onerous due to the combinatorially large output spaces. In this paper, we focus on reducing the prediction time of a trained black-box structured classifier without losing accuracy. To do so, we train a speedup classifier that learns to mimic a black-box classifier under the learning-to-search approach. As the structured classifier predicts more examples, the speedup classifier will operate as a learned heuristic to guide search to favorable regions of the output space. We present a mistake bound for the speedup classifier and identify inference situations where it can independently make correct judgments without input features. We evaluate our method on the task of entity and relation extraction and show that the speedup classifier outperforms even greedy search in terms of speed without loss of accuracy.