PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zachary Bamberger, Till R. Saenger, Gilad Morad, Ofra Amir, Brandon M. Stewart, Amir Feder

arXiv:2602.14265v3cs.CLcs.LG

TL;DR

Existing inference-time compute methods struggle to produce meaningful diversity and expose how reasoning choices are made. STATe searches over explicit textual action interventions with a controller, generator, and evaluator, yielding more diverse and higher-quality outputs while making reasoning patterns analyzable. The paper also identifies promising unexplored action sequences, but its action–outcome analysis remains associative and its applicability is constrained by prefilling and intervention-design limitations.

  • Problem

    Existing inference-time compute methods provide limited meaningful diversity and limited control or insight into the high-level decisions behind reasoning.

  • Method

    STATe searches over sequences of discrete textual action templates, with a controller selecting actions, a generator producing conditioned reasoning, and an evaluator guiding search.

  • Results

    STATe produces more diverse and higher-quality outputs than standard ITC branching and identifies promising unexplored action sequences for high-quality generation.

  • Takeaways & Limitations

    STATe makes step-level reasoning decisions explicit and auditable while supporting diverse text generation and analysis of reasoning patterns associated with performance.

  • Takeaways & Limitations

    STATe requires prefilling unavailable in many closed-source APIs, and its action–outcome analysis is associative rather than causal.

Abstract

from arXiv · show

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.

1 Introduction

STATe addresses limited diversity and interpretability in inference-time compute by searching over explicit, high-level reasoning actions. Its controller, generator, and evaluator support controllable branching, and experiments report diverse, higher-quality outputs alongside interpretable action–quality patterns.

  • Existing ITC methods use token-level, temperature-based branching that yields limited meaningful variation and leaves reasoning decisions implicit.
  • STATe searches over discrete textual action templates that encode high-level choices such as rhetorical structure and content themes.The controller selects actions, the generator conditions reasoning steps on them, and the evaluator scores candidates to guide search.
  • STATe’s branching mechanism produces outputs that are more diverse and higher quality than standard ITC branching on NoveltyBench.
  • In argument generation, interventions reliably manifest in reasoning steps and responses, while sequential action features predict held-out argument quality.
  • STATe provides a controllable ITC framework, a diversity mechanism beyond high-temperature sampling, and an action-based framework for analyzing reasoning quality.Its explicit text prefixes are directly auditable, unlike latent interventions.

2 Background

Inference-time compute improves LLM reasoning by allocating additional generation and search, but conventional approaches face diversity, control, and fixed-depth limitations. Tree of Thoughts combines breadth and depth through branching, evaluation, and pruning.

  • Inference-time compute allocates additional reasoning tokens or candidate responses to improve robustness and reasoning quality.
  • Chain-of-Thought generates intermediate reasoning steps before a final answer but lacks a principled mechanism to revisit decisions or explore alternatives.
  • Best-of-n generates independent candidate outputs and selects the best according to a criterion, scaling breadth rather than reasoning depth.
  • Tree of Thoughts reframes generation as search over partial reasoning states, branching at each step, evaluating branches, and pruning unpromising paths.
  • Traditional ToT suffers from clustered branches under high-temperature sampling and predetermined reasoning depth that can cause overthinking or insufficient reasoning.

3 Methods

STATe performs tree search over explicit action interventions: a controller selects actions, a generator extends trajectories, and evaluators retain promising states or finish early. Logged action sequences then support associational analysis of outcome quality.

  • STATe overview: STATe replaces temperature-based branching with discrete action templates so neighboring branches explore different reasoning strategies and can stop early.
  • Search procedure: At each layer, the controller selects interventions, the generator produces completions, and the evaluator retains the top-k states for the next layer.
  • Controller: Each action is a tool call chosen from a fixed template set, with argument values specifying dimensions such as rhetorical structure and content.
  • Controller: The controller can select FINISH when reasoning is sufficient, allowing final-answer synthesis before the predefined maximum depth.
  • Evaluator: Process and outcome evaluators score intermediate and complete states using PRM- or ORM-style value functions before the highest-scoring final state is returned.
  • Outcome attribution: STATe logs action sequences and models action presence, positions, transitions, and cross-dimensional interactions to identify associations with better or worse outcomes.

4 Experiments

STATe is evaluated for diversity, controllability, action-sequence predictability, and targeted exploration in creative writing and argument generation. Across these settings, structured interventions improve diversity and quality, reliably manifest in outputs, and support quality-guided exploration.

  • 4.1 Improving Diversity and Quality in Creative Writing: 42% higher diversity at T=0.5, 37% at T=0.7, and 31% at T=1.0 versus the best non-STATe baseline.STATe scores 4.24 versus 2.98, 4.57 versus 3.33, and 4.94 versus 3.76, respectively, on NoveltyBench.
  • 4.1 Improving Diversity and Quality in Creative Writing: 30% higher quality at T=0.5, 21% at T=0.7, and 16% at T=1.0 versus the strongest baseline.The corresponding quality scores are 3.36 versus 2.59, 3.52 versus 2.90, and 3.73 versus 3.23.
  • 4.2.1 Granular Control of Argumentative Reasoning: Structure adherence reaches 99.7% at the reasoning-step level, while subtopic adherence reaches 87.8%.At the response level, structure and subtopic pass rates are 96.2% and 93.5%, and prescribed ordering is preserved at 87.9%.
  • 4.2.2 Predicting the Quality of Arguments through Action Sequences: Action sequences are mapped to argument quality using attribution models across 5 topics and 3 LLM judges on held-out data.The models range from a length-only baseline to sequential features encoding step position and content–structure combinations.
  • 4.2.2 Predicting the Quality of Arguments through Action Sequences: The human-validation study reports 84.1% advantage probability and 72.0% agreement with the human majority vote for the LLM judge.The study included 288 Prolific participants and focused on one topic.
  • 4.2.4 Discovering Promising Unexplored Action Sequences: Targeted trajectories achieve a 78.7% win rate against random exploration, 63.3% against topic-presence guidance, and 68.0% against the original top 5% baseline.Comparisons use length-matched arguments and 5,000 pairwise comparisons per baseline.

5 Discussion

The discussion presents STATe as a controllable and auditable ITC framework that improves diversity and quality while exposing reasoning patterns for analysis and targeted search.

  • 5 Discussion: STATe makes step-level decisions explicit and auditable through intervention-based branching over discrete action templates.Its logged action sequences support analysis of controllable reasoning patterns and downstream outcomes.
  • 5 Discussion: STATe improves semantic diversity and output quality without the typical quality degradation associated with high-temperature sampling.The discussion connects this result to the NoveltyBench evaluation.
  • 5 Discussion: Scoring previously unseen trajectories lets STATe explore under-visited action-space regions and surface strong candidates rather than repeatedly sampling near-duplicates.The discussion describes this as an operational use of learned action–outcome associations.

6 Limitations

STATe’s practical scope is constrained by intervention access, non-causal attribution, limited intervention expressivity, synthesis trade-offs, and single-turn tool-free operation.

  • 6 Limitations: Closed-source APIs that do not expose prefilling cannot directly support STATe’s intervention mechanism.The limitation specifically names GPT, Claude, and Gemini as examples.
  • 6 Limitations: The action–outcome analysis is associative rather than causal because sequential confounding is not addressed by current attribution models.Actions are selected conditional on prior actions in the same sequence.
  • 6 Limitations: STATe only adds new reasoning steps, without interventions that alter existing content or affect final-output generation.This constrains the expressivity of the intervention space.
  • 6 Limitations: Strict synthesis preserves faithfulness and predictability but can produce stilted prose, whereas flexible synthesis improves fluency at those costs.The paper characterizes this as a control–quality trade-off.
  • 6 Limitations: The framework supports only single-turn interactions and does not support external tool calls such as retrieval or code execution.

7 Future Work

Future work proposes causal analysis of action trajectories and stronger optimization methods for exploring high-performing regions under constrained evaluation budgets.

  • 7 Future Work: Randomized interventions could estimate per-step causal effects of action trajectories instead of relying only on associations.The proposed formulation treats action trajectories as sequential treatments.
  • 7 Future Work: Monte Carlo Tree Search could replace fixed beam search to adapt exploration toward high-performing action-space regions under constrained evaluation budgets.
  • 7 Future Work: Weight-based optimization through reinforcement learning is proposed as another way to optimize STATe.The passage gives PPO as an example.

8 Ethical Implications

The paper acknowledges that argument-generation systems can enable large-scale manipulation and emphasizes both the prosocial uses of persuasion and the need to analyze harmful patterns.

  • Argument-generation systems can be misused to create misleading, coercive, phishing, or otherwise harmful messages at scale.
  • The study does not make causal claims because its trajectory-processing procedure creates analytical constraints, not because of the STATe framework itself.
  • Persuasion also supports prosocial communication, including public-health guidance, charitable giving, and democratic participation.
  • STATe can help uncover argumentative patterns associated with emotional abuse or misuse and steer models away from employing them.

9 Disclosure of LLM Use

The authors disclose using LLMs and AI coding tools to assist with paper production, while verifying generated tables and figures against preserved raw results.

  • The authors used Claude, ChatGPT, and AI code editors for LaTeX, tables, figures, draft feedback, and an LLM-as-a-Judge experiment.

A.1 Social Science Experiments with Text

The paper positions STATe as an inference-time search method for exploring structured reasoning strategies, addressing limitations of existing text-based analyses and token-level diversity methods.

  • Persuasion research treats text as a treatment variable for studying how linguistic features affect downstream behavior.
  • Topic models capture content themes but struggle with structural and stylistic variation and restrict analysis to features already present in corpora.
  • Inference-time compute allocates additional post-training computation through greater reasoning depth, more candidates, or both.
  • Chain-of-Thought elicits intermediate reasoning steps, but its explanations may be post-hoc rationalizations and can become misleading under prompt manipulation.
  • STATe complements depth-oriented reasoning by controlling what the model reasons about at each step through explicit action templates.
  • Breadth-oriented methods improve robustness by generating multiple candidates, but meaningful diversity remains difficult to induce with token-level sampling.
  • STATe uses discrete, interpretable action templates and a controller to select semantically distinct branches without relying on high-temperature sampling.
  • Unlike standard ToT, STATe makes branching decisions auditable by replacing token-level stochasticity with explicit actions and logging action sequences.

C STATe Modules

STATe modules implement tree search through controller-selected actions, generator-produced interventions, and evaluator-based selection, with task-dependent assumptions about action spaces and evaluation.

  • Search loop: STATe’s tree-search loop plans actions, generates candidate trajectories, evaluates them, selects a beam, and expands the next layer.
  • Controller and generator: At each layer, the controller selects up to n actions for each beam state, and each action becomes a structured prefix and context intervention for generation.
  • Interventions: Illustrative interventions show successive generation states progressing from a single claim to multiple claims and then a complete argument.
  • Action space: The controller’s action space encodes rhetorical structure and content dimensions, while open-ended argument generation is the paper’s primary setting.
  • Controller and generator: The generative controller chooses a tool and its arguments, can use chain-of-thought, and may select FINISH to produce the final output early.
  • Evaluator: The evaluator uses an LLM judge with weighted rubric criteria to score reasoning or outputs, while cross-encoders can score candidate states directly.
  • Programmatic evaluator: Programmatic evaluation can verify correctness or structural validity and prune invalid trajectories, but requires additive action spaces and reliable prefix-level validation.

D Beam-Search Complexity

STATe instantiates beam search over structured reasoning actions, retaining beam-search-style complexity while improving diversity, quality, utility, controllability, and action-sequence interpretability. Its main practical cost is additional controller latency, while controllability and predictability depend on how faithfully interventions are preserved and how concretely subtopics are specified.

  • Complexity: Under pruning, logical search cost grows linearly in depth and beam width rather than exponentially in depth.STATe adds first-layer beam width, action-space size, and final-response count as method-specific complexity factors.
  • Diversity and quality: STATe achieves the highest diversity across seven models and three temperature regimes, with a mean +95% improvement over I/O Best-of-n at medium temperature.Across models, gains range from +49% for Qwen3-8B (4.63 vs. 3.11) to +153% for Gemma-3-27B (4.35 vs. 1.72).
  • Diversity and quality: STATe achieves the highest raw quality across all seven models and temperature settings, with a mean +60% improvement over I/O Best-of-n at medium temperature.The reported medium-temperature quality gains range from +13% for Qwen3-8B (3.29 vs. 2.90) to +89% for Gemma-3-27B (3.46 vs. 1.83).
  • Utility: STATe improves utility over I/O Best-of-n at medium temperature and ranks first on five of seven models across most temperatures.Reported utility gains include +33% for Ministral-3-14B (6.53 vs. 4.90) and Qwen3-30B (5.12 vs. 3.84).
  • Efficiency: STATe’s reranker controller raises mean runtime to 13.48 seconds versus 3.20 seconds for ToT despite similar total token volumes.Approximately 93.4% of STATe input tokens are cache hits, close to ToT’s approximately 94.4% rate.
  • Controllability and interpretability: Sequential controller actions predict argument quality beyond presence-based and length-only features, with strongest predictability generally under strict synthesis.Generic subtopics reduce adherence from 87.8% to 49.8% at the step level and from 93.5% to 52.4% at the response level, while structure adherence remains comparable.

E.4.3 Results

The human validation study finds that the LLM judge aligns meaningfully with human preferences despite low human agreement on persuasive arguments. Its advantage probability remains high across score-gap strata.

  • 56.0% human pairwise agreement and Krippendorff’s α = 0.118 indicate substantial subjectivity in persuasiveness judgments.
  • 72.0% LLM agreement with the human majority vote exceeds the 56.0% human pairwise baseline.
  • 0.841 advantage probability means the LLM matches or exceeds an excluded human’s agreement with remaining annotators in 84.1% of comparisons.
  • 0.82–0.86 advantage probability across Bradley-Terry score-gap strata suggests similarly reliable LLM judgments for close and clearly different pairs.
  • LLM choices correlate significantly with human preference rates, with Pearson r = 0.493 overall and r = 0.657 for large-gap pairs.

F Limitations

STATe’s current deployment and interpretation are constrained by model-access requirements, engineered action spaces, synthesis trade-offs, and limited scope. Its action–outcome analysis remains associative rather than causal.

  • STATe currently requires assistant-prefill support, making deployment most straightforward with open-source or self-hosted models.
  • Fixed textual prefixes can create stylistic artifacts, while action spaces require task-specific engineering and granularity choices.
  • Strict synthesis preserves action–output coupling but may produce stilted prose, whereas flexible synthesis improves eloquence while weakening predictability.
  • Multiple realizations of one trajectory currently rely on random seeds and achieve only limited diversity.
  • STATe focuses on single-turn, multi-step generation and does not explicitly model multi-turn conversations or general tool calling.
  • Action–outcome relationships are analyzed associatively, so the reported predictability does not establish causal effects.

G.2 Human evaluation and behavioral outcomes

The paper evaluates human alignment, action-space design, and potential extensions for behavioral outcomes. STATe’s discrete action sequences are positioned as a way to increase semantic diversity while preserving quality.

  • Human evaluation and behavioral outcomes: Argument evaluation relies on LLM judges that are broadly correlated with human judgments but do not substitute for rigorous human experimentation.
  • Human evaluation and behavioral outcomes: STATe’s sequential, multidimensional action traces could support controlled studies of belief or behavior changes using pre- and post-intervention measurements.
  • Human evaluation and behavioral outcomes: Group-wise policy optimization can suffer mode collapse, whereas sampling discrete interpretable action sequences increases semantic diversity while preserving quality.
  • Human evaluation and behavioral outcomes: Structured action spaces can diversify reflective prompt-evolution strategies by representing sequential prompt edits and searching for configurations that maximize a provided metric.
  • Human evaluation and behavioral outcomes: STATe’s NoveltyBench action space combines Big Five personality traits with target-audience age demographics.

H.2 Argument generation action spaces

The argument-generation action spaces organize reasoning around domain-specific topical lenses and discourse moves. Their construction includes concrete subtopics, internal reasoning prompts, and a cost–benefit perspective, with application-specific tuning expected.

  • Argument generation action spaces: Argument-generation topics are represented through domain-specific subtopics, including plastic pollution, social-media age restriction, universal basic income, standardized testing, and meat taxation.
  • Argument generation action spaces: The social-media age-restriction space covers adolescent development, addictive design, online safety, cyberbullying, attention, and academic performance.
  • Argument generation action spaces: Universal-basic-income actions address poverty reduction, administrative waste, funding, entrepreneurship, innovation, mental health, and wellbeing.
  • Argument generation action spaces: Standardized-testing actions examine validity, inequality, curriculum effects, test-taking ability, and socioeconomic disparities.
  • Argument generation action spaces: Meat-tax actions consider emissions, land and water use, and systematic cost–benefit, rights, privacy, and autonomy consequences.
  • Argument generation action spaces: Action-space and synthesis choices require domain-specific exploration and iteration based on early experimental results.
Loading 2602.14265v3…