# NPHardEval4V: Dynamic Evaluation of Large Vision-Language Models with Effects of Vision

arXiv: https://arxiv.org/abs/2403.01777 · HTML: https://mlsanity.com/paper/2403.01777/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Placed in Multimodal reasoning, one of 17 directions in LLM reasoning.
- Builds on 19 of its 51 references that are in the map.
- First posted on arXiv 4 Mar 2024.

## Placed in

- LLM reasoning / [Multimodal reasoning](https://mlsanity.com/lr/multimodal-reasoning/)
- Multimodal LLMs / vision-language models / [VLM benchmarks and visual reasoning](https://mlsanity.com/mllm/vlm-benchmarks-and-visual-reasoning/)

## Builds on (most cited first, 19 of 19)

- [Making the V in VQA Matter: Elevating the Role of Image Understanding in Visual Question Answering](https://mlsanity.com/paper/1612.00837/) (2016)
- [VQA: Visual Question Answering](https://mlsanity.com/paper/1505.00468/) (2015)
- [MMBench: Is Your Multi-modal Model an All-around Player?](https://mlsanity.com/paper/2307.06281/) (2023)
- [MMMU: A Massive Multi-discipline Multimodal Understanding and Reasoning Benchmark for Expert AGI](https://mlsanity.com/paper/2311.16502/) (2023)
- [MME: A Comprehensive Evaluation Benchmark for Multimodal Large Language Models](https://mlsanity.com/paper/2306.13394/) (2023)
- [SEED-Bench: Benchmarking Multimodal LLMs with Generative Comprehension](https://mlsanity.com/paper/2307.16125/) (2023)
- [Multimodal Few-Shot Learning with Frozen Language Models](https://mlsanity.com/paper/2106.13884/) (2021)
- [Towards Reasoning in Large Language Models: A Survey](https://mlsanity.com/paper/2212.10403/) (2022)
- [A Survey on Multimodal Large Language Models for Autonomous Driving](https://mlsanity.com/paper/2311.12320/) (2023)
- [Exploring the Reasoning Abilities of Multimodal Large Language Models (MLLMs): A Comprehensive Survey on Emerging Trends in Multimodal Reasoning](https://mlsanity.com/paper/2401.06805/) (2024)
- [Language Models with Image Descriptors are Strong Few-Shot Video-Language Learners](https://mlsanity.com/paper/2205.10747/) (2022)
- [NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes](https://mlsanity.com/paper/2312.14890/) (2023)
- [ControlLLM: Augment Language Models with Tools by Searching on Graphs](https://mlsanity.com/paper/2310.17796/) (2023)
- [A Bibliometric Review of Large Language Models Research from 2017 to 2023](https://mlsanity.com/paper/2304.02020/) (2023)
- [A Challenger to GPT-4V? Early Explorations of Gemini in Visual Expertise](https://mlsanity.com/paper/2312.12436/) (2023)
- [LLaVA-Interactive: An All-in-One Demo for Image Chat, Segmentation, Generation and Editing](https://mlsanity.com/paper/2311.00571/) (2023)
- [Towards Generic Anomaly Detection and Understanding: Large-scale Visual-linguistic Model (GPT-4V) Takes the Lead](https://mlsanity.com/paper/2311.02782/) (2023)
- [Gemini Goes to Med School: Exploring the Capabilities of Multimodal Large Language Models on Medical Challenge Problems & Hallucinations](https://mlsanity.com/paper/2402.07023/) (2024)
- [Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging](https://mlsanity.com/paper/2010.00412/) (2020)

## Built on by (most cited first, 5 of 5)

- [ProLLM: Protein Chain-of-Thoughts Enhanced LLM for Protein-Protein Interaction Prediction](https://mlsanity.com/paper/2405.06649/) (2024)
- [What do MLLMs hear? Examining reasoning with text and sound components in Multimodal Large Language Models](https://mlsanity.com/paper/2406.04615/) (2024)
- [RegexPSPACE: A Benchmark for Evaluating LLM Reasoning on PSPACE-complete Regex Problems](https://mlsanity.com/paper/2510.09227/) (2025)
- [From Perception to Reasoning: Deep Thinking Empowers Multimodal Large Language Models](https://mlsanity.com/paper/2511.12861/) (2025)
- [FATHOMS-RAG: A Framework for the Assessment of Thinking and Observation in Multimodal Systems that use Retrieval Augmented Generation](https://mlsanity.com/paper/2510.08945/) (2025)

## Abstract (arXiv)

Large Vision-Language Models (LVLMs) have demonstrated impressive capabilities in multimodal understanding, yet their reasoning abilities remain underexplored. Existing benchmarks tend to focus on perception or text-based comprehension, offering limited insight into how well these models perform on structured, logic-driven tasks that require both visual and linguistic reasoning. To address this gap, we introduce NPHardEval4V, a multimodal benchmark suite grounded in four classical NP-hard problems: Knapsack, Set Cover, Traveling Salesperson, and Vertex Cover. Each task is presented through a combination of structured visual layouts and textual prompts, designed to assess the ability of LVLMs to perform combinatorial reasoning under visual-linguistic constraints. We evaluate a set of advanced open-source and closed-source vision-language models under a unified prompting and problem representation framework. This enables fair comparison across models and task types, while isolating key variables affecting performance. Our results show that while these models perform reasonably well on perception-based inputs, they struggle with global optimization, abstraction, and constraint satisfaction. No single model demonstrates consistent reasoning capability across all problem types, and common failure patterns reveal fundamental limitations in current architectures. By leveraging the structure and complexity of NP-hard problems, NPHardEval4V provides a scalable, interpretable, and challenging testbed for diagnosing reasoning behaviors in LVLMs. We hope this benchmark can support the community in building more robust, inference-capable multimodal systems. The benchmark dataset and code are available at https://github.com/lizhouf/NPHardEval4.