ReFrame: A Diagnostic Benchmark for Multilevel Representation Revision in Sequential Problem Solving

Problem-solving agents are usually evaluated with a fixed state and action representation, yet the economical response to failure may be continued search, state redescription, relational augmentation, action composition, or a change of abstraction level. We introduce ReFrame, an executable benchmark for diagnosing such failures while charging diagnosis, candidate generation, verification, and application to one task budget. A candidate-blind diagnostic ranks continued search and seven edit classes from 15 planner-trace statistics; only then does a target selector inspect candidate edits. Success is concrete goal reachability, and each non-search task admits multiple structurally distinct repairs. A nearest-centroid diagnostic trained on 640 tasks was evaluated on 1,600 held-out tasks at five budgets. At budget 500, trace-guided revision achieved 0.980 success (95% paired-seed bootstrap interval 0.973–0.987), compared with 0.779 for direct all-candidate scoring, 0.446 for budget-matched random retries, and 0.250 for raw breadth-first search. It also reduced mean deployment cost from 291.7 to 203.7 units relative to direct scoring. The advantage persisted across budgets, edit costs, classifiers, and planners. These results isolate the allocation value of failure diagnosis: it directs verification toward work able representations before counterfactual trials consume the available budget.