A new benchmark called NPHardEval is taking a fundamentally different swing at measuring how well large language models actually reason. Instead of relying on static question sets that models can eventually memorize, it generates 900 algorithmic problems across nine different algorithms and ten difficulty levels, then refreshes the entire dataset every month. The questions are grounded in computational complexity theory, spanning P, NP-complete, and NP-hard classes, which gives researchers a rigorous, quantifiable way to map a model’s logical reasoning rather than just its ability to recall training data.
Early results follow a familiar pattern. Closed-source models outperform open-source ones, with GPT-4 Turbo coming out on top overall. But the more interesting finding is how performance shifts across complexity classes. Models handle less-complex questions better, as you’d expect, yet the decline isn’t always linear. That irregularity suggests LLMs don’t process computational difficulty the way a human computer scientist would—they’re not walking through algorithms step by step, but doing something messier under the hood.
The benchmark’s design choices are deliberate. It excludes numerical computation entirely because LLMs are notoriously bad at arithmetic, and including it would muddy the assessment of pure logical reasoning. It also uses two metrics: Weighted Accuracy, which gives harder problems proportionally more credit, and Failure Rate, which tracks how often a model produces unparseable output across up to ten attempts per problem. That second metric matters more than it sounds—a model that gets the right answer half the time but crashes the other half is less useful in practice than one that’s consistently mediocre.
NPHardEval’s automatic generation and checking pipeline is arguably its biggest contribution. Since the problems are algorithmically computable, correctness can be verified without human judges, which makes the monthly refresh cycle feasible. That dynamic approach is a direct response to the benchmark contamination problem that has plagued static evaluations like MMLU and GSM8K, where models trained on leaked test data post inflated scores. Whether monthly updates are frequent enough to stay ahead of training pipelines is an open question, but it’s a meaningful step toward evaluations that measure reasoning rather than memorization.
