STATe-of-Thoughts: Structured Action Templates for Tree-of-Thoughts

Abstract:Inference-Time-Compute (ITC) methods like Best-of-$n$ and Tree-of-Thoughts are meant to produce output candidates that are both high-quality and diverse, but their use of high-temperature sampling often fails to achieve meaningful output diversity. Moreover, existing ITC methods offer limited control over $\textit{how}$ to perform reasoning, which in turn limits their interpretability. We present $\textbf{STATe-of-Thoughts}$ (STATe), an interpretable ITC method that $\textit{searches}$ over high-level reasoning patterns. STATe branches over discrete and interpretable textual interventions rather than over token-level samples: a $\textit{controller}$ selects actions encoding high-level reasoning choices; a $\textit{generator}$ produces reasoning steps conditioned on those choices; and an $\textit{evaluator}$ scores candidates to guide search. This structured approach yields three main advantages. First, action-guided textual interventions reliably influence LLM generations and produce greater response diversity than temperature-based sampling. Second, in a case study on argument generation, STATe's explicit action sequences capture interpretable features that are highly predictive of output quality. Third, estimating the association between performance and action choices allows us to identify promising yet unexplored regions of the action space and steer generation toward them. STATe is most useful when a task admits multiple solutions and when understanding $\textit{why}$ an output succeeds matters beyond $\textit{whether}$ the output succeeds. Together, these results establish STATe as both a practical framework for diverse and controllable text generation, and as a tool for understanding the reasoning patterns that drive performance.

Accepted to COLM 2026. Version 3. 11 pages main, 85 pages total, 23 tables, 21 figures

Computation and Language (cs.CL); Machine Learning (cs.LG)

I.2.7; I.2.11; H.1.2

arXiv:2602.14265 [cs.CL]

(or arXiv:2602.14265v3 [cs.CL] for this version)

https://doi.org/10.48550/arXiv.2602.14265 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.