💻 computer science

What Makes a Programming Problem Hard for a Language Model? An Empirical Study of Item Difficulty Across Code LLMs on Two Benchmarks

This paper presents an empirical study demonstrating that problem difficulty in code generation benchmarks is a stable, transferable metric driven by specification features (like examples and prompt length) on HumanEval and solution complexity on MBPP, offering critical insights for improving benchmarking, autograding, and educational tool design as aggregate model scores saturate.

Original authors: TANZIM ISLAM KHAN

Published 2026-07-13

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: TANZIM ISLAM KHAN

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, magical library of riddles, and you've invited a whole zoo of different AI "solvers" to try and crack them. Some solvers are tiny hamsters with big brains (small models), and others are giant, super-intelligent elephants (like GPT-4). Usually, when we check how smart these AIs are, we just give them a single score, like a final grade in school. But this paper argues that a single grade is boring and misleading. It's like saying a math test is "hard" just because you got a C, without asking: Which questions were the tricky ones? Was it the long word problems, or the ones with no examples?

The author, Tanzim Islam Khan, decided to stop looking at the final grade and start looking at the riddles themselves. They took two famous sets of coding riddles (called HumanEval and MBPP) and ran them through a massive experiment. They grabbed the answers from 31 different AI models (ranging from tiny 1-billion-parameter models to the giant GPT-4) and re-ran every single answer in a safe, isolated sandbox to see if it actually worked. That's 13,400 executions right there!

The Big Discovery: What Makes a Riddle Hard?

The paper found something surprising that changes how we think about "difficulty."

On the HumanEval set (the riddles with long descriptions and lots of example answers), the difficulty didn't depend on how complicated the solution code was. It depended entirely on how the riddle was written.

The Magic Clue: If the riddle included worked examples (like showing the AI: "Here is input A, here is output B"), the AI solved it easily. The more examples, the easier it was.
The Trap: If the riddle was long and wordy, or if it lacked those helpful examples, the AI struggled, even if the actual code needed to solve it was simple.
The Proof: The authors built a prediction machine. When they fed it only the text of the riddle (the prompt), it could predict how hard the riddle was with a cross-validated $R^2$ of 0.45, which matched the performance of the full model. But when they fed it only the complexity of the solution code (like counting loops or variables), it barely knew anything ( $R^2$ of 0.11).

The Twist: The Other Riddle Book

Then they looked at the MBPP set. These riddles are different; they are super short, like one-sentence whispers, with no examples at all.

Here, the rules flipped! Since every riddle looked the same (short and vague), the text didn't tell the AI what to do. Instead, the difficulty depended on how hard the solution actually was.
If the code required complex logic, the AI failed. If the code was simple, the AI succeeded.
The Lesson: A problem is hard for an AI based on whatever part of the instructions is the most variable. If the instructions vary a lot (like in HumanEval), the instructions rule. If the instructions are all the same (like in MBPP), the complexity of the answer rules.

What the Paper Clarifies

The paper explicitly argues against the idea that "harder code always equals a harder problem."

They measured the complexity of the reference solutions (using things like "cyclomatic complexity" and "Halstead volume") and found that on HumanEval, these numbers were much weaker predictors of difficulty than the prompt features. A complex solution wasn't necessarily harder to generate if the instructions were clear and full of examples.
They also ruled out the idea that difficulty is just a fluke of which AI models you happen to test. They proved that difficulty is a stable property of the problem itself. Whether you test a hamster-sized AI or an elephant-sized AI, the same riddles remain the hardest and the easiest. They even checked this by removing one model at a time, and the ranking didn't change (correlation $\rho \ge 0.99$ ).

How Sure Are We?

The authors are very confident, but they are careful with their words.

They measured this directly by running the code 13,400 times in a sandbox.
They proved the stability by testing it against a "hardened" version of the tests (which have 80 times more checks for HumanEval and 35 times more for MBPP). Even with these tougher tests, the ranking of hard vs. easy problems stayed almost the same (correlation $\rho = 0.88$ ).
They simulated (or rather, re-ran) the results with different settings (like changing the "temperature" to make the AI more random) and found the difficulty ranking stayed consistent ( $\rho = 0.87$ ).
They suggested that as AI gets smarter and starts solving almost everything on these old tests (saturation), looking at which specific problems are still hard will become even more important.

The Future Context

The paper also takes a peek at the "future" (as of June 2026 in the paper's timeline). It notes that the very newest, super-powerful AIs (like GPT-5.x and Claude Opus 4.8) have basically stopped using these old riddles because they are too easy for them now. The frontier has moved to much harder, real-world coding tasks. But the lesson remains: as the easy problems disappear, understanding why the remaining hard ones are hard becomes the key to building better tools.

In a Nutshell

If you want to know if a coding problem is hard for an AI, don't just look at the code it needs to write. Look at the instructions!

Rich instructions with examples? The AI will breeze through it, no matter how complex the code is.
Vague instructions or no examples? The AI will struggle, even if the code is simple.
Short, one-sentence instructions? Then the complexity of the code itself is what makes it hard.

The paper gives us a map to predict these struggles without even needing to run the AI, simply by reading the problem statement. It's a tool for teachers to build better exercises and for engineers to build better benchmarks, ensuring we aren't just testing if an AI can guess the answer, but if it can actually understand the riddle.

Technical Summary: What Makes a Programming Problem Hard for a Language Model?

Problem Statement

Current evaluation practices for code-generating Large Language Models (LLMs) rely heavily on aggregate metrics like pass@k on benchmarks such as HumanEval and MBPP. This approach treats all problems as interchangeable, obscuring which specific problems are difficult and why. Consequently, it fails to distinguish between a model's general capability and the specific characteristics of the items it solves. The paper addresses the need to treat the problem (item) as the unit of analysis, separating item difficulty from model ability to understand the determinants of difficulty in code generation tasks.

Methodology

The study employs a data-driven empirical approach grounded in Item Response Theory (IRT) and predictive modeling.

Data Source: The authors utilized publicly released greedy completions from the EvalPlus project. The study covers 31 distinct models (ranging from ~1B to GPT-4 scale) on HumanEval (164 problems) and 22 models on MBPP (378 problems).
Execution Harness: Rather than trusting pre-computed scores, the authors re-executed all 13,400 completions in a sandboxed Python environment with a 12-second timeout. This generated binary response matrices (31×164 for HumanEval; 22×378 for MBPP).
Difficulty Operationalization:
- Empirical Difficulty: Defined as $1 - \text{solve rate}$ (the fraction of models failing a specific problem).
- IRT Validation: A one-parameter logistic (Rasch) model was fitted to separate model ability ( $\theta$ ) from item difficulty ( $b$ ). The authors confirmed that the raw cross-model failure rate correlates almost perfectly ( $\rho \approx 1.00$ ) with the Rasch-derived difficulty, validating the use of the simpler metric.
Feature Extraction: 36 static features were extracted per problem, categorized into:
- Prompt Features: Length, readability, number of worked examples, presence of type hints, etc.
- Reference-Solution Features: Code complexity metrics (McCabe cyclomatic complexity, Halstead volume, AST node counts, nesting depth, etc.).
- Test Suite Features: Number of assertions, character count.
Analysis: The study used correlation analysis (Spearman/Pearson with Benjamini-Hochberg correction) and machine learning (Ridge regression, Random Forests, Gradient Boosting) with 10-fold cross-validation to predict difficulty. Robustness was tested via leave-one-model-out, bootstrap resampling, transfer across capability tiers, re-grading against hardened test suites (HumanEval+/MBPP+), and temperature sampling.

Key Results

1. Difficulty is a Stable, Measurable Property

Distribution: Difficulty is widely distributed, not concentrated. On HumanEval, the mean solve rate across the 31-model panel was 0.29, with some problems solved by 0% of models and others by 100%.
Stability: The difficulty ranking is highly robust. Removing any single model leaves the ranking virtually unchanged ( $\rho \ge 0.99$ ). The ranking also transfers across capability tiers (weaker vs. stronger models), with Spearman correlations of 0.78 (HumanEval) and 0.79 (MBPP).
Rasch Alignment: The Rasch model confirms that difficulty is a latent property of the item, independent of the specific solver panel used.

2. Predictive Signal Depends on Specification Style

The study identifies a critical divergence in what predicts difficulty between the two benchmarks:

HumanEval (Rich Prompts): Difficulty is primarily predicted by prompt features ( $R^2 = 0.45$ $R^{2} = 0.45$ ), which matches the performance of the full feature set ( $R^2 = 0.46$ $R^{2} = 0.46$ ).
- Strongest Predictors: The number of worked input-output examples (negative correlation with difficulty) and the presence of type hints make problems easier. Longer prompts and docstrings correlate with higher difficulty.
- Solution Complexity: Reference-solution complexity features alone explain very little variance ( $R^2 = 0.11$ ).
MBPP (Terse Prompts): Difficulty is primarily predicted by solution-complexity features ( $R^2 = 0.13$ $R^{2} = 0.13$ ).
- Context: MBPP prompts are uniformly short, single-sentence descriptions with no worked examples. Consequently, prompt features have little variance to contribute.
- Strongest Predictors: AST node count and Halstead volume are the dominant correlates. Prompt-only features yield negative $R^2$ .
Synthesis: What makes a problem hard depends on what varies most in its specification. If the prompt varies (HumanEval), the prompt drives difficulty; if the prompt is static (MBPP), the algorithmic complexity drives difficulty.

3. Robustness and Generalization

Hardened Tests: Re-grading against HumanEval+ and MBPP+ (80x and 35x more tests, respectively) reduced overall pass rates but preserved the difficulty ranking ( $\rho = 0.88$ and $0.82$) and the prompt-vs-solution predictive split.
Decoding Regime: Switching from greedy decoding to temperature-0.8 sampling preserved the difficulty ranking ( $\rho = 0.87$ ) and the predictive signal distribution.
2026 Context: Analysis of the June 2026 EvalPlus leaderboard (125 models) shows HumanEval is saturating (top models >96%). Frontier models (e.g., GPT-5.x, Claude Opus 4.8) have largely abandoned HumanEval for repository-level benchmarks (SWE-bench), where per-instance difficulty modeling remains critical as aggregate scores compress.

Key Contributions

Reproducible Execution Study: A validated dataset of ~68,000 executions across two benchmarks, converting public completions into binary response matrices and difficulty scales.
Stability Evidence: Empirical proof that item difficulty is a model-agnostic property that survives model removal, resampling, and capability tier transfer.
Predictive Analysis: Demonstration that difficulty is predictable from static features, with a crucial cross-benchmark finding: the predictive signal shifts from the natural-language specification (HumanEval) to the solution complexity (MBPP) based on the variability of the prompt.
Contextualization: A mapping of these findings to the 2026 model landscape, showing that as benchmarks saturate, difficulty-aware analysis becomes more, not less, important.

Significance and Implications

The paper argues that difficulty-aware benchmarking is essential as aggregate scores compress.

For Benchmark Design: Reports should move beyond single aggregate scores to include difficulty profiles (e.g., distribution of easy/medium/hard items) to detect saturation and ensure benchmarks remain discriminative. Static difficulty predictors offer a low-cost method for curating balanced benchmarks without running fleets of models.
For Autograding and Education: Static difficulty estimates can serve as confidence signals for LLM-assisted tutoring. If a specification is flagged as "hard" (e.g., lacking examples or having high complexity), an assistant can defer to human review or request clarification.
Educational Alignment: The finding that worked examples and type hints make problems easier for LLMs aligns with the "worked-example effect" in cognitive load theory. This suggests that scaffolding beneficial for novice programmers is also beneficial for LLMs, though it creates a trade-off: exercises designed to be easy for assistants (rich in examples) may be too easy for students to learn from, while terse exercises may challenge both.

The study concludes that difficulty is not an inherent property of the algorithm alone but is determined by the dimension of the specification that remains most variable. This insight provides a framework for understanding and predicting LLM performance across different problem settings.