Abstract
To investigate the effect of problem presentation on LLMs' ability to solve optimization problems, we introduce the dataset of Everyday Hard Optimization Problems (EHOP), a collection of NP-hard problems expressed in natural language. EHOP includes problem formulations that could be found in computer science textbooks (e.g., graph coloring), versions that are dressed up as problems that could arise in real life (e.g., party planning), and variants with inverted rules. We find that state-of-the-art LLMs, across multiple prompting strategies, systematically solve textbook problems more accurately than their real-life and inverted counterparts. While reasoning models are more capable, they nonetheless show high variance across problem presentations, suggesting they lack a truly robust reasoning mechanism. We argue that this constitutes evidence that LLMs are still heavily dependent on what was seen in training and struggle to generalize to novel problems.
Introduction
Large Language Models (LLMs) are increasingly evaluated on their ability to solve complex mathematical and logical tasks. A central debate in the field is whether these models possess genuine reasoning capabilities or if they primarily rely on pattern matching from their extensive training data. This paper addresses this question by examining LLM performance on NP-hard optimization problems—specifically Graph Coloring (GCP), the Knapsack Problem (KSP), and the Traveling Salesman Problem (TSP)—under varying linguistic presentations.
The EHOP Benchmark
We introduce the Everyday Hard Optimization Problems (EHOP) dataset, comprising 6,800 natural language task descriptions. EHOP is designed to test the "brittleness" of LLM reasoning by presenting the same underlying mathematical constraints in three distinct formats:
- Textbook: Standard academic phrasing using terms like "nodes," "edges," and "capacity."
- Costumed: Real-world scenarios, such as assigning students to groups to avoid distractions or planning a delivery route.
- Inverted: Mathematically equivalent problems with flipped objectives, such as finding the longest path instead of the shortest.
Methodology
We benchmarked a suite of state-of-the-art models, including GPT-4o, Llama-3, and Qwen-2.5. Our evaluation spanned several prompting paradigms:
- Chain-of-Thought (CoT): One-shot and zero-shot prompts encouraging step-by-step reasoning.
- Neurosymbolic (ILP Python): A strategy where the LLM acts as a translator, converting natural language into Python code for an external Integer Linear Programming solver.
- Optimization by Prompting (OPRO): An iterative approach where the model refines its solution based on previous attempts.
- Reasoning Models: We also tested specialized models specifically trained to "think" before generating an answer to determine if explicit reasoning traces mitigate presentation bias.
Results and Analysis
Our findings demonstrate a pervasive "Textbook Bias." Models achieve their highest accuracy on problems using academic jargon, suggesting that these specific linguistic patterns are overrepresented in training sets.
Impact of Presentation and Inversion
As shown in the table below, transitioning from Textbook to Costumed or Inverted variants leads to a significant degradation in performance. For example, GPT-4o's accuracy on Graph Coloring dropped from 42% in the Textbook format to nearly 0% when rules were inverted, despite the logic remaining identical. This suggests that LLMs are often "reciting" known solutions rather than reasoning from first principles.
Comparison with Greedy Heuristics
In many instances, standard LLMs failed to outperform simple "greedy" algorithms. While greedy approaches are suboptimal, they consistently respect problem constraints. In contrast, LLMs frequently produced "erroneous" solutions that violated basic rules (e.g., assigning the same color to connected nodes), particularly in costumed or inverted settings. Performance for all models drops toward zero as the problem size increases, highlighting that LLMs are not yet a replacement for dedicated optimization software.
Conclusion
The EHOP benchmark highlights a critical gap in current LLM capabilities. While these models can solve complex optimization problems when presented in familiar academic terms, their performance is highly sensitive to linguistic framing. This brittleness suggests that LLMs lack a robust, generalized reasoning mechanism and remain heavily dependent on training data patterns. Future work should focus on developing models that can reliably map diverse natural language inputs to their underlying logical structures.
Summary updated