LLMs Explain Linear Programs: From Side Project to Microsoft Research

2025-02-10

Back in 2020, while working in Google's supply chain, the author developed a side project to help understand linear programs (LPs). When LPs become complex, understanding their results is challenging even for experts. The author's approach involved interactively modifying the model and diffing the results to explain model behavior, finding that adding semantic metadata simplified the process. Recently, Microsoft researchers published a paper using Large Language Models (LLMs) to translate natural language queries into structured queries, achieving a similar outcome. The author believes LLMs are a great fit for translating human ambiguity into structured queries, processed by a robust classical optimization system, with results summarized by the LLM. While the author's early work remained unpublished, he argues that understanding explanations of simpler systems is crucial for explaining more complex AI systems.