Evaluating AI agents for complex software like Microsoft Excel is a massive engineering challenge. A single full-benchmark run for a new agent configuration can take hours and cost upwards of $1,000 in LLM tokens. To iterate quickly, developers need "benchmark reduction"—selecting a small, representative subset of tasks that can accurately predict how an agent would perform on the full suite.
In their paper, "A Taxonomy and Taxonomy-Guided Benchmark Reduction for Spreadsheet Tasks," researchers from Carnegie Mellon, Microsoft, and MIT present a systematic way to shrink these benchmarks without losing sight of the diverse ways people actually use spreadsheets.
TL;DR
The authors developed a comprehensive taxonomy for spreadsheet tasks and a selection algorithm that balances predictive accuracy with taxonomic diversity. They found that picking a diverse set of tasks doesn't just ensure better "coverage"—it actually acts as a regularizer, helping the reduced benchmark better predict the performance of entirely new agent configurations.
What Problem Does This Paper Address?
AI spreadsheet agents (like those powered by GPT-4) are evaluated on thousands of tasks involving formulas, pivot tables, and data cleaning. Simply picking the "most informative" tasks based on past performance (a common approach in machine learning) can lead to a "coverage gap." You might end up with a subset that is great at predicting formula performance but completely ignores how the agent handles messy data or ambiguous instructions.
The challenge is twofold:
- Lack of Structure: There was no systematic, domain-grounded taxonomy to define what "coverage" even means for spreadsheet AI.
- The Accuracy-Diversity Trade-off: Does picking a more diverse set of tasks make the benchmark less accurate at predicting overall scores?
Methods
The researchers tackled this using a two-step approach:
1. Building the Taxonomy
Following an iterative development method, they created a taxonomy covering three tiers:
- Table Properties: Size, structure (flat vs. hierarchical), and data types.
- Workbook Properties: The primary intent or industry domain (e.g., Financial Management, Risk Assessment).
- Task Properties: Instruction clarity, number of steps required, and specific operations (e.g., "Filtering & Selection").
2. Taxonomy-Guided Reduction
They treated benchmark reduction as a feature selection problem. If tasks are "features" and agent configurations are "data points," the goal is to find a subset of tasks ($k$) that maximizes the $R^2$ (predictive power) for the full benchmark score.
Their novel twist is the Diversity Tie-breaker. Instead of a pure greedy selection, they look at a "tolerance band" ($\epsilon$) of the best-performing tasks. Within that band, the algorithm chooses the task that most increases the taxonomic diversity of the subset.
Datasets
The study utilized two primary sources:
- SpreadsheetBench: A public benchmark of over 900 real-world spreadsheet tasks, used to validate the taxonomy's descriptive power.
- Microsoft Industrial Logs: Real-world pass/fail data from the development of Microsoft’s Excel Agent. This included 126 execution IDs across 67 different agent configurations.
Key Insights and Ideas
- The Long Tail of Tasks: As shown in Figure 1, spreadsheet tasks are highly skewed. A few categories like "Formulas" dominate, while critical areas like "Data Cleaning" or "Ambiguous Instructions" are sparsely populated. Without a taxonomy, random sampling would likely miss these "tail" categories entirely.

- Diversity as Regularization: This is the "aha moment." The researchers found that pushing for diversity often improved predictive accuracy on new, unseen agent configurations. By not overfitting to the most "informative" tasks of the past, the diverse subset became more robust to changes in the agent's underlying model or prompts.
- Auditing Gaps: Beyond reduction, the taxonomy allowed Microsoft teams to audit their own benchmarks against production traffic, identifying specific regions (like "noisy workbooks") where their evaluations were lacking.
Key Results
- Accuracy vs. Diversity: Taxonomy-guided selection achieved near-complete coverage of the task space with almost zero cost to predictive accuracy.
- Generalization: In "honest" validation (testing on configurations not used for selection), the diversity tie-breaker significantly reduced overfitting. In some noisy data scenarios, it turned a negative $R^2$ (worse than guessing the mean) into a positive, useful prediction.
- Efficiency: The method successfully reduced benchmarks from roughly 1,000 tasks down to just 10–30 tasks while maintaining strong predictive rankings.
Limitations and Future Work
- Temporal Shift: The reduced benchmarks are not "set and forget." As agent configurations evolve significantly over time, the predictive power of a static subset eventually degrades. The authors recommend "refreshing" the subset periodically.
- Cost Heterogeneity: Currently, the model treats all tasks as equal in "cost." However, some tasks use far more tokens or compute time than others. Future iterations could include a cost-aware selector.
- Labeling: The taxonomy labels were assigned by an LLM (GPT-4). While spot-checks were positive, more rigorous human-in-the-loop validation of these labels is a suggested next step.
For engineers building AI agents, this paper provides a practical framework: don't just pick the "hardest" or "most predictive" tests—pick the ones that span the map of what your users actually do.
Summary updated