Probing LLMs on Optimization Problems: Can They Recall and Interpret Problem Features?

In this study, we explore the ability of Large Language Models (LLMs) to understand and recall features associated with combinatorial optimization problems in both Natural Language Processing (NLP) and structured contexts. By probing LLMs using a diverse set of optimization problem instances, we aim to evaluate the models’ ability to accurately extract and reason about key attributes, such as parameters and features. Our methodology involves both structured and extended NLP-based prompts for the models and instructing these models to identify specific features from the provided problem instances. The results reveal that while LLMs exhibit some capacity to identify and extract information, they fail to recall 100% of even the simplest features consistently present within the text. This limitation underscores the current challenges LLMs face in precise reasoning and feature extraction tasks, suggesting the need for further refinement in their interpretability and understanding capabilities when applied to structured problem-solving domains. (Relevant data and code are available at the following link: https://osf.io/fw6ta/?view_only=d8e63cdda6bd409b83aa3d9a4b025b06).