A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems

Alex Duchnowski, Ellie Pavlick, Alexander Koller

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

The rapid advancement of Large Language Models (LLMs) has sparked a significant debate: are these models truly reasoning through complex logical structures, or are they merely sophisticated "reciters" of patterns found in their massive training datasets? This question is particularly acute when considering NP-hard optimization problems—tasks like the Traveling Salesman Problem (TSP) or Graph Coloring where finding an optimal solution is computationally intensive. If an LLM has mastered the underlying logic of these problems, its performance should remain stable regardless of how the problem is phrased. However, if it relies on memorized templates from computer science textbooks and competitive programming sites, it will likely falter when faced with unfamiliar presentations.

Methodology: The EHOP Framework

To quantify this "vulnerability to presentation," researchers developed the Everyday Hard Optimization Problems (EHOP) benchmark. EHOP transforms three classic NP-hard problems—Graph Coloring (GCP), Knapsack (KSP), and Traveling Salesman (TSP)—into three distinct linguistic variants:

  1. Textbook: Standard mathematical phrasing typical of academic literature.
  2. Costumed: Real-world analogies, such as assigning students to groups to avoid distractions or planning a seating chart to keep ex-partners apart.
  3. Inverted: Mathematically flipped rules that maintain identical difficulty (e.g., requiring non-adjacent nodes to have different colors instead of adjacent ones).
Comparison between a standard textbook graph coloring problem and its 'costumed' real-world equivalent.

The dataset contains 6,800 task descriptions, split into EHOP-RANDOM and EHOP-HARD (instances designed to defeat simple greedy heuristics). The researchers evaluated models using various prompting strategies, including One-Shot, Zero-Shot Chain-of-Thought (CoT), and a neurosymbolic ILP Python approach where the LLM generates code for a specialized solver like Gurobi.

Results: The Presentation Gap

The study revealed a consistent "Textbook Advantage." Models performed significantly better on textbook versions than on costumed or inverted variants. This performance delta serves as a "smoking gun" for the recitation hypothesis; models appear to recognize a "template" they have encountered frequently during training rather than applying generalized reasoning.

Performance changes across problem variants, highlighting the significant accuracy drops for non-textbook presentations.

As shown in the table above, inverting a single constraint often caused performance to plummet by over 20 percentage points. Even the neurosymbolic ILP Python strategy, which offloads computation to a professional solver, suffered. The models struggled to accurately translate "messy" natural language into clean, executable code when the phrasing deviated from standard textbook norms.

Furthermore, as problem size increased (e.g., more cities in a TSP route), pure LLM accuracy dropped toward zero. In many cases, simple, non-AI "greedy" algorithms outperformed the LLMs' complex reasoning attempts. While newer "thinking" models like DeepSeek-R1 show improved capability in identifying underlying problem types, they remain volatile and susceptible to linguistic "costumes."

Discussion and Future Work

The findings suggest that current LLMs lack a robust, presentation-invariant reasoning mechanism. Their reliance on training data patterns limits their utility for novel or uniquely phrased real-world optimization tasks.

Future research should focus on:

  • Human Baselines: Determining if humans experience similar performance gaps when switching between abstract math and "costumed" word problems.
  • Collaborative Systems: Developing dialogue-based interfaces where users and LLMs can iteratively define and refine complex problem constraints.
  • Real-World Complexity: Moving beyond "toy" problems (4–9 nodes) to industrial-scale optimization challenges like airline scheduling, which involve far more intricate constraints than those found in EHOP.

Ultimately, bridging the "presentation gap" is essential if LLMs are to move beyond being sophisticated pattern matchers and become reliable partners in solving complex, real-world optimization problems.

Summary updated

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.
BibTeX
@misc{duchnowski2025knapsack,
  author = {Alex Duchnowski and Ellie Pavlick and Alexander Koller},
  title = {{A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems}},
  year = {2025},
  eprint = {2502.13776},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.13776},
}
Figure