DTS: Enhancing Large Reasoning Models via Decoding Tree Sketching

Large Reasoning Models (LRMs) achieve remarkable inference-time improvements through parallel thinking. However, existing methods rely on redundant sampling of reasoning trajectories, failing to effectively explore the reasoning space to uncover high-quality solutions. To address these limitations, we propose **D**ecoding **T**ree **S**ketching (DTS), a plug-and-play decoding framework for structural multi-trajectory exploration and reasoning selection. For reasoning exploration, DTS sketches a backbone tree of the reasoning space by selectively branching at decision tokens. For reasoning selection, guided by length-accuracy anti-correlation, DTS designs an early termination to prioritize short and reliable trajectories during decoding. Experimental results across four LRMs and datasets demonstrate that DTS significantly enhances accuracy by **14\%** and reduces repetitive generation by **8\%** on average. Notably, DTS enables smaller models to outperform larger models with 10$\times$ the size, highlighting its potential to strengthen reasoning capabilities.

When reasoning models tackle hard problems, such as competition math or science questions, they often think out loud through long chains of steps before arriving at an answer. Recently, a common way to improve their performance is to have the model think through the problem multiple times and make a majority vote. However, these multiple attempts tend to be nearly identical, wasting computation without exploring different ways to solve the problem. We propose Decoding Tree Sketching (DTS), a method that guides reasoning models to think more strategically. Instead of independently repeating similar reasoning chains, DTS builds a structured thinking tree by identifying key decision points, moments where the model is undecided between different meaningful directions, and exploring these branches in parallel. We also show that shorter reasoning chains tend to be more accurate, so DTS prioritizes the first completed reasoning paths rather than waiting for all chains to finish. DTS requires no additional training and plugs directly into existing models. Across four reasoning models and four challenging benchmarks, DTS improves accuracy by 14% and reduces repetitive generation by 7% on average. Moreover, DTS enables smaller models to outperform larger models with 10 times the size, highlighting its potential to strengthen reasoning capabilities.