A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911218720047104 |
|---|---|
| author | Duchnowski, Alex Pavlick, Ellie Koller, Alexander |
| author_facet | Duchnowski, Alex Pavlick, Ellie Koller, Alexander |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13776 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems Duchnowski, Alex Pavlick, Ellie Koller, Alexander Computation and Language Computational Complexity 68Q15 I.2.7 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. |
| title | A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems |
| topic | Computation and Language Computational Complexity 68Q15 I.2.7 |
| url | https://arxiv.org/abs/2502.13776 |