Playing Psychic: Using Thought Trees to Predict Reasoning Models Accuracy on Coding Tasks

Recent advances in large language models (LLMs) have shown that test-time scaling can substantially improve model performance on complex tasks, particularly in the coding domain. Under this paradigm, models use a larger token budget during inference to generate intermediate reasoning traces before producing a final answer. However, current evaluations primarily rely on competitive programming benchmarks, which may not capture the full range of reasoning abilities. In this work, we perform a systematic study of frontier reasoning models to understand their performance on real-world coding benchmarks. To gain more insights into the performance of such models, we devise a programmatic way to automatically generate coding tasks of arbitrary difficulty and structure from existing benchmarks. Using this framework, our analysis reveals that the structure of a reasoning trace, not just its contents, carries interpretable signal about correctness. Motivated by this, we propose structured thought-trees as a representation for reasoning traces, and train a lightweight classifier on features extracted from them to predict trace correctness. A classifier trained only on simple problems transfers to unseen, more deeply composed ones, and ablations show the signal comes from the structure of the thought-tree rather than trace length alone. We further show these structural signals can guide targeted retries that recover a share of failures.