# A Tutorial on Dual Decomposition and Lagrangian Relaxation for Inference in Natural Language Processing

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2014.

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

- [DDCoT: Duty-Distinct Chain-of-Thought Prompting for Multimodal Reasoning in Language Models](https://mlsanity.com/paper/2310.16436/) (2023)
- [Echocardiography Segmentation with Enforced Temporal Consistency](https://mlsanity.com/paper/2112.02102/) (2021)
- [R-U-SURE? Uncertainty-Aware Code Suggestions By Maximizing Utility Across Random User Intents](https://mlsanity.com/paper/2303.00732/) (2023)
- [Efficient Vertex-Oriented Polytopic Projection for Web-scale Applications](https://mlsanity.com/paper/2103.05277/) (2021)
- [Dual Decomposition of Convex Optimization Layers for Consistent Attention in Medical Images](https://mlsanity.com/paper/2206.02761/) (2022)
- [The Integer Linear Programming Inference Cookbook](https://mlsanity.com/paper/2307.00171/) (2023)
- [CORE: Learning Consistent Ordinal REpresentations for Image Ordinal Estimation](https://mlsanity.com/paper/2301.06122/) (2023)
- [RouterWise: Joint Resource Allocation and Routing for Latency-Aware Multi-Model LLM Serving](https://mlsanity.com/paper/2604.10907/) (2026)

## Abstract (arXiv)

Dual decomposition, and more generally Lagrangian relaxation, is a classical method for combinatorial optimization; it has recently been applied to several inference problems in natural language processing (NLP). This tutorial gives an overview of the technique. We describe example algorithms, describe formal guarantees for the method, and describe practical issues in implementing the algorithms. While our examples are predominantly drawn from the NLP literature, the material should be of general relevance to inference problems in machine learning. A central theme of this tutorial is that Lagrangian relaxation is naturally applied in conjunction with a broad class of combinatorial algorithms, allowing inference in models that go significantly beyond previous work on Lagrangian relaxation for inference in graphical models.