# Predicting Task Difficulty Without Rollouts

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 43 of its 58 references that are in the map.
- First posted on arXiv 6 Aug 2026.

## Builds on (most cited first, 30 of 43)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Mind2Web: Towards a Generalist Agent for the Web](https://mlsanity.com/paper/2306.06070/) (2023)
- [Terminal-Bench: Benchmarking Agents on Hard, Realistic Tasks in Command Line Interfaces](https://mlsanity.com/paper/2601.11868/) (2026)
- [MLE-bench: Evaluating Machine Learning Agents on Machine Learning Engineering](https://mlsanity.com/paper/2410.07095/) (2024)
- [TheAgentCompany: Benchmarking LLM Agents on Consequential Real World Tasks](https://mlsanity.com/paper/2412.14161/) (2024)
- [MathArena: Evaluating LLMs on Uncontaminated Math Competitions](https://mlsanity.com/paper/2505.23281/) (2025)
- [SWE-Bench Pro: Can AI Agents Solve Long-Horizon Software Engineering Tasks?](https://mlsanity.com/paper/2509.16941/) (2025)
- [Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design](https://mlsanity.com/paper/2012.02096/) (2020)
- [Automatic Goal Generation for Reinforcement Learning Agents](https://mlsanity.com/paper/1705.06366/) (2017)
- [Automated Curriculum Learning for Neural Networks](https://mlsanity.com/paper/1704.03003/) (2017)
- [Demystifying Prompts in Language Models via Perplexity Estimation](https://mlsanity.com/paper/2212.04037/) (2022)
- [Teacher-Student Curriculum Learning](https://mlsanity.com/paper/1707.00183/) (2017)
- [Prioritized Level Replay](https://mlsanity.com/paper/2010.03934/) (2020)
- [RE-Bench: Evaluating frontier AI R&D capabilities of language model agents against human experts](https://mlsanity.com/paper/2411.15114/) (2024)
- [An Illusion of Progress? Assessing the Current State of Web Agents](https://mlsanity.com/paper/2504.01382/) (2025)
- [Evolving Curricula with Regret-Based Environment Design](https://mlsanity.com/paper/2203.01302/) (2022)
- [Cybench: A Framework for Evaluating Cybersecurity Capabilities and Risks of Language Models](https://mlsanity.com/paper/2408.08926/) (2024)
- [GDPval: Evaluating AI Model Performance on Real-World Economically Valuable Tasks](https://mlsanity.com/paper/2510.04374/) (2025)
- [Measuring AI Ability to Complete Long Software Tasks](https://mlsanity.com/paper/2503.14499/) (2025)
- [Automatic Curriculum Learning For Deep RL: A Short Survey](https://mlsanity.com/paper/2003.04664/) (2020)
- [Benchmark Data Contamination of Large Language Models: A Survey](https://mlsanity.com/paper/2406.04244/) (2024)
- [Generalization or Memorization: Data Contamination and Trustworthy Evaluation for Large Language Models](https://mlsanity.com/paper/2402.15938/) (2024)
- [Online Difficulty Filtering for Reasoning Oriented Reinforcement Learning](https://mlsanity.com/paper/2504.03380/) (2025)
- [Estimating Contamination via Perplexity: Quantifying Memorisation in Language Model Evaluation](https://mlsanity.com/paper/2309.10677/) (2023)
- [A Rosetta Stone for AI Benchmarks](https://mlsanity.com/paper/2512.00193/) (2025)
- [How Do AI Agents Spend Your Money? Analyzing and Predicting Token Consumption in Agentic Coding Tasks](https://mlsanity.com/paper/2604.22750/) (2026)
- [Reliable and Efficient Amortized Model-based Evaluation](https://mlsanity.com/paper/2503.13335/) (2025)

## Abstract (arXiv)

A fundamental challenge in evaluating and training autonomous agents is measuring the intrinsic difficulty of the tasks they attempt. Estimating this quantity can be useful for environment designers creating synthetic data or benchmarks, as well as for constructing training curricula, thereby offering a way to reduce compute costs. Such an estimation becomes increasingly important as agents (particularly LLM-based) move into longer-horizon domains, where empirical trial-and-error becomes a severe computational bottleneck. However existing work is largely confined to static tasks and relies on evaluation metrics that, as we show, can give an incomplete picture of predictive performance. In this paper we study ex ante difficulty prediction across 17 agentic benchmarks spanning coding, mathematics, machine learning, web navigation, function calling, and other domains. We find that AUC can mask poor difficulty estimates, identify token-level entropy as a useful predictive signal, and demonstrate how residuals between expected and observed difficulty can expose environment flaws such as contamination and infeasibility.