Everything of Thoughts: Defying the Law of Penrose Triangle for Thought Generation

ArXiv: 2311.04254

🎯 Pitch

XOT breaks the long-standing tradeoff in LLM prompting by injecting pretrained MCTS plans directly into thoughts, achieving over 90% accuracy on Game of 24 with GPT-3.5 while using 23x fewer LLM calls than Tree-of-Thought. It even solves previously impossible 8-Puzzle and Pocket Cube tasks where all baselines failed, collapsing performance, efficiency, and flexibility into a single framework.

---

1. Executive Summary

This paper introduces Everything of Thoughts (XOT), a novel thought prompting framework that combines pretrained reinforcement learning with Monte Carlo Tree Search (MCTS) to inject external domain knowledge and planning capability into LLM-generated reasoning chains. Evaluated on Game of 24, 8-Puzzle, and Pocket Cube using GPT-3.5 and GPT-4, XOT achieves the three desiderata that prior paradigms—Input-Output, Chain-of-Thought, Tree-of-Thought, and Graph-of-Thought—could at most satisfy two of: performance (accuracy), efficiency (number of LLM calls), and flexibility (ability to produce chain, tree, or graph thought structures). On Game of 24, XOT reaches 90.51% accuracy with GPT-3.5 using only ~1.7 LLM calls, compared to Tree-of-Thought's 60.58% using ~40 calls; on 8-Puzzle, XOT with GPT-4 achieves 95.80% accuracy in ~1.6 LLM calls where all prompting baselines fall below 14%; and on Pocket Cube, XOT reaches 84.70% accuracy against a best baseline of 19.57%, establishing that LLMs can solve previously insurmountable spatial-reasoning tasks when MCTS-supplied thoughts are iteratively revised through a collaborative MCTS-LLM framework—but only when the underlying MCTS policy and value networks are trained on task-specific data with well-defined state transitions and reward signals.

2. Context and Motivation

The Core Problem: The "Penrose Triangle" of Thought Generation

The paper identifies a fundamental three-way tradeoff in how LLMs generate intermediate reasoning steps—called "thoughts"—when solving complex problems. The authors frame this as a kind of "Penrose triangle" constraint: existing thought generation paradigms can achieve at most two of three critical attributes, but never all three simultaneously. The three attributes are:

• Performance: the accuracy of the final solution and the correctness of intermediate reasoning steps. This is the most straightforward metric—does the method produce the right answer?
• Efficiency: the number of LLM inference calls required to solve a single problem. LLM inference is expensive (both computationally and monetarily, especially with frontier models like GPT-4), so minimizing these calls is a practical necessity for any deployable system.
• Flexibility: the diversity of thought topologies the method can express—chains (linear sequences), trees (branching exploration with backtracking), or graphs (interconnected structures where thoughts can merge, split, and form recurrent patterns). This matters because different problem types demand different reasoning structures: some problems need straightforward linear deduction, others require exploring multiple branches in parallel, and still others (like puzzles with multiple valid solutions) benefit from graph-like reasoning that mirrors human mind-mapping processes.

The paper's central claim is that no existing prompting paradigm simultaneously delivers all three. The authors map out the failure modes explicitly in Table 1:

Each paradigm's specific limitation tells a story about the tradeoffs inherent in thought generation:

IO prompting fails on performance for complex problems because it asks the LLM to answer in a single step with no intermediate reasoning. It's flexible only in the trivial sense that it imposes no structure—but that absence of structure means it can't systematically decompose hard problems.

CoT improves performance by decomposing problems into sequential steps, but this very decomposition locks it into a rigid linear chain. You cannot branch to explore alternatives mid-chain, backtrack from a dead end, or maintain multiple parallel reasoning paths. Every problem gets the same linear treatment regardless of whether a tree or graph structure would be more appropriate.

CoT-SC samples multiple independent CoT chains and selects the best output (typically by majority voting). This improves accuracy (and thus performance) but multiplies LLM calls by the number of samples (the paper uses 10), destroying efficiency. And it remains linear: each chain is independent and isolated, with no cross-pollination between parallel reasoning paths.

ToT introduces tree-structured search, where the LLM generates multiple candidate thoughts at each step and evaluates them to decide which branches to pursue. This adds genuine flexibility—the structure can branch and prune. But the evaluation itself is performed by the LLM, meaning every candidate thought requires a separate LLM inference call. For a tree with branching factor $b$ and depth $d$, the number of LLM calls scales as $O(b^d)$, which rapidly becomes prohibitive. The paper's ToT experiments with $b=3$ on Game of 24 required ~40–56 LLM calls per problem (Tables 3–8), making it an order of magnitude more expensive than XOT's ~1.5–2.3 calls.

GoT extends ToT to graph structures, allowing thoughts to be aggregated, refined, and merged during intermediate search phases. This is the most flexible paradigm—it can represent chains, trees, or arbitrary directed graphs. But it inherits ToT's fundamental efficiency problem: the LLM must evaluate intermediate thoughts to decide how to merge, refine, or aggregate them. GoT still requires tens of LLM calls per problem (e.g., ~23 calls for 8-Puzzle in the multi-solution setting), and the paper's results show it performs worse than ToT on most metrics despite the added flexibility, suggesting the LLM struggles to effectively leverage the more complex structure without additional guidance.

The "Penrose triangle" framing is more than a catchy metaphor—it captures a genuine structural constraint in how these paradigms allocate cognitive work. In IO and CoT, the LLM does everything (reasoning + evaluation) but gets no structural support. In ToT and GoT, the structure provides flexibility, but the LLM must also serve as the evaluator of intermediate states—a role it performs inconsistently and expensively. The paper's key insight is that breaking this triangle requires offloading the evaluation and search to a component other than the LLM itself, freeing the LLM to focus on what it does best (generating and revising candidate solutions) while a separate, cheaper mechanism handles the structural exploration.

Why This Problem Matters: Beyond Academic Prompt Engineering

The three-way tradeoff isn't merely a theoretical curiosity—it has significant practical implications that the paper highlights through three interconnected motivations:

1. The Inefficiency of LLM-Based Evaluation Is a Scaling Bottleneck

The fundamental cost driver in ToT and GoT is that the LLM serves double duty as both generator and evaluator of intermediate thoughts. At each step in a search tree, the LLM must (a) generate candidate next thoughts, and then (b) evaluate each candidate's quality to decide which to pursue. Each evaluation is a full LLM inference call—for GPT-4, this is expensive both in time and money.

This creates a harsh scaling ceiling: to explore more of the search space (improving performance), you need exponentially more LLM calls (destroying efficiency). The paper's experimental results make this concrete. On Game of 24 with GPT-4, ToT with $b=1$ (keeping only the top candidate at each step) achieves 34.31% accuracy using ~24 LLM calls. Increasing to $b=3$ (keeping top-3 candidates) improves accuracy to 60.58% but at the cost of ~40 LLM calls—a 66% increase in calls for a 26-percentage-point gain. Further increases in branching would likely yield diminishing returns at rapidly escalating cost.

This inefficiency places ToT and GoT in an uncomfortable regime for real-world deployment. If each GPT-4 call costs money and takes seconds, scaling to $b=5$ or $b=10$ quickly becomes impractical for applications requiring real-time response or operating at scale. The paper's XOT approach addresses this by pushing the expensive exploration offline (during training of the policy/value networks) and using cheap neural network inferences during deployment, reducing LLM calls to ~1.5–2.3 per problem regardless of search complexity.

2. LLMs Have Fundamental Weaknesses in Spatial Reasoning and Long-Term Planning

The paper deliberately chooses three tasks—Game of 24, 8-Puzzle, and Pocket Cube—that expose specific weaknesses in LLMs' native reasoning capabilities:

• Game of 24 tests combinatorial arithmetic reasoning: given four numbers, find an expression using basic operations that equals 24. While arithmetic is within LLMs' capabilities, the combinatorial search space is large (there are many ways to combine four numbers), and LLMs struggle to systematically explore it without external structure. The IO baseline achieves only 6.57% (GPT-3.5) and 10.22% (GPT-4), showing that naive single-step prompting fails badly.

• 8-Puzzle tests spatial planning over a discrete state space. The LLM receives only a textual representation of the 3×3 grid and must reason about legal moves, state transitions, and the path to the goal configuration. This is fundamentally a graph search problem (the state space forms a graph where nodes are configurations and edges are legal moves), but LLMs cannot perform systematic graph search internally—they must simulate it step by step in text. The IO baseline achieves a flat 0.00% on GPT-3.5 and only 1.68% on GPT-4. Even CoT only reaches 7.56% on GPT-4, demonstrating that step-by-step prompting alone is insufficient when the task requires maintaining and updating a spatial state representation across multiple steps.

• Pocket Cube (2×2 Rubik's Cube) is the hardest spatial reasoning task in the paper. The state space involves 3D rotations applied to colored faces, which must be mentally tracked through textual descriptions. The action space involves understanding how rotations (U, R, F and their inverses/double-turns) permute the colors on different faces—a non-trivial spatial transformation even for humans. IO achieves ~1% and CoT reaches 0–1% on both models. The best prompting baseline, ToT with $b=3$, reaches only 19.57% on GPT-4—better than zero but still failing on 80% of problems.

The consistent theme across these tasks is that LLMs lack built-in mechanisms for systematic state-space search, spatial state tracking, and long-horizon planning. They can reason about individual steps when prompted appropriately (as CoT and ToT partially demonstrate), but they cannot maintain an accurate world model across multiple reasoning steps or efficiently explore the combinatorial space of possible action sequences. The paper's XOT framework addresses this by injecting external domain knowledge—in the form of MCTS simulations guided by learned policy and value networks—that compensates for these specific LLM weaknesses.

3. The Gap Between What LLMs "Know" and What They Can Systematically Apply

There is also a deeper, more subtle motivation: LLMs may possess relevant knowledge (arithmetic, basic spatial reasoning, understanding of rules) but lack the ability to deploy that knowledge in a systematic, exhaustive way over many steps. This is the distinction between competence (what the model could theoretically do) and performance (what it actually does under typical prompting).

XOT's philosophy is not to teach the LLM new facts, but to provide a scaffold that allows it to apply its existing knowledge more systematically. The MCTS module explores the search space efficiently using learned heuristics, generates candidate thought trajectories, and presents them to the LLM. The LLM then uses its internal knowledge to review and revise these trajectories—catching errors that the MCTS made, refining suboptimal plans, and ultimately producing a final answer that synthesizes the external search with its own reasoning. The LLM is not replaced; it is augmented with a search capability it natively lacks.

This framing connects to broader research on the gap between LLM capabilities and their deployment under naive prompting strategies, and it positions XOT not as a competitor to CoT/ToT/GoT, but as a complementary approach that addresses their shared bottleneck (the LLM-as-evaluator) while preserving their strengths (the LLM as flexible reasoner and knowledge repository).

Where Existing Approaches Fall Short: A Detailed Taxonomy

The paper's critique of prior work can be organized along three dimensions: structural limitations, evaluation mechanisms, and generalization capability.

Structural Limitations of Prior Paradigms

CoT and CoT-SC are topologically constrained to linear chains. This is adequate for problems with a single clear solution path and no need for exploration, but it fails in two important regimes:

• Problems with ambiguous intermediate states where the correct next step isn't obvious. A linear chain commits to one path early and has no mechanism to backtrack if a mistake is discovered later. The paper's 8-Puzzle results illustrate this starkly: CoT achieves 7.56% on GPT-4, while even ToT ($b=3$) reaches 13.45%—the branching structure allows exploration of alternative moves when the first choice doesn't work out.

• Problems with multiple valid solutions where the goal is to find any (or all) solutions. Linear chains produce one answer and stop. To find multiple solutions with CoT-SC, you must run many independent chains and hope they produce diverse correct answers—but there's no guarantee of diversity, and many chains may converge on the same solution or produce duplicates.

ToT and GoT address the topological constraint by allowing tree and graph structures, but they introduce their own structural problems. ToT requires the tree to be pre-specified: the branching factor $b$ and depth limit must be set in advance. If the true solution lies deeper than the maximum depth, ToT cannot find it. If $b$ is too small, promising branches get pruned prematurely. If $b$ is too large, efficiency collapses. GoT adds more flexibility (merging, refining) but the complexity of managing graph operations (when to merge? which nodes to aggregate? how to score merged thoughts?) often exceeds what the LLM can handle reliably.

XOT's MCTS does not pre-specify the structure—it dynamically expands the search tree where exploration is most promising, guided by the learned value and policy functions. The resulting thought structure can be a chain, a tree, or a graph (when multiple solution trajectories share intermediate states or converge toward the goal from different paths—as shown in Figure 5's multi-solution examples where thought trajectories "intertwine during intermediate steps and converge towards the final goal state"). This emergent flexibility is a direct consequence of MCTS's exploration strategy rather than a hand-designed topology.

The Evaluation Mechanism Bottleneck

This is the paper's most pointed critique. In ToT, every candidate thought must be evaluated by the LLM to decide whether to expand it, prune it, or select it as part of the final answer. The evaluation prompt typically asks the LLM to classify thoughts as "sure," "likely," or "impossible" (Yao et al., 2023), but this is both computationally expensive (one LLM call per candidate) and unreliable (the LLM's self-evaluation is often poorly calibrated, especially for problems where it lacks deep understanding).

The consequences are visible in the paper's results:

• On Game of 24, ToT ($b=3$) uses ~40 LLM calls but achieves only 60.58% accuracy—meaning ~35 of those calls were "wasted" on generating or evaluating thoughts that didn't lead to the correct answer.
• On 8-Puzzle, ToT ($b=3$) uses ~54 LLM calls but achieves 13.45%—less than one-sixth the accuracy of the MCTS module alone (51.26%), suggesting the LLM's self-evaluation is actively harmful compared to systematic search.
• On Pocket Cube, ToT ($b=3$)'s 19.57% accuracy after ~57 calls compares poorly to MCTS's 46.44%, again indicating that LLM-based evaluation is the limiting factor.

GoT compounds this problem by requiring the LLM to perform more complex evaluation operations—aggregating thoughts, merging overlapping solutions, refining partial results—each of which is itself an LLM call. The paper's GoT results are consistently worse than ToT's despite the added flexibility, suggesting that the evaluation mechanism is so noisy that adding structural complexity actually degrades performance.

XOT's innovation is to completely remove the LLM from the evaluation loop during search. Instead, MCTS uses lightweight neural networks (policy and value heads, totaling ~$10^6$ parameters—orders of magnitude smaller than the LLM) to guide exploration. These networks are trained offline on task-specific simulation data, so the expensive learning happens once, and deployment involves only fast forward passes through a small MLP. The LLM is invoked only to (a) review the final extracted thought trajectory for errors, and (b) generate the final answer. This reduces LLM calls from dozens to ~1.5–2.3, with the MCTS module handling the heavy lifting of state-space exploration.

Generalization Limitations of Task-Specific Approaches

The paper acknowledges a limitation that applies to XOT as well: the policy and value networks must be trained on task-specific data generated through MCTS self-play. This means XOT is not a zero-shot method—it requires:

1. Access to a simulator or environment that can determine ground-truth rewards for state-action pairs.
2. Sufficient training problems to learn meaningful policy and value functions (the paper uses 1,225 problems for Game of 24, 300 for 8-Puzzle, and 1,000 for Pocket Cube).
3. Well-defined state representations and action spaces that can be enumerated and scored.

This contrasts with CoT and IO, which require no task-specific training (only in-context examples), and with ToT and GoT, which use the LLM's internal knowledge for evaluation and thus require no external training data. The tradeoff is explicit: XOT sacrifices zero-shot applicability for dramatic gains in performance and efficiency on the specific tasks it's trained for.

The paper positions this as acceptable for two reasons. First, the training cost is low relative to the deployment savings: the policy/value networks are tiny (~$10^6$ parameters) and train quickly (three iterations of 10 self-play episodes each), while deployment saves tens of LLM calls per problem. Second, many real-world applications involve repeatedly solving problems from a well-defined domain (e.g., logistics planning, game playing, puzzle solving, code generation with test suites), where the upfront training cost is amortized over many deployments.

However, the paper does not address whether the policy/value networks transfer between related tasks (e.g., training on 8-Puzzle and transferring to 15-Puzzle, or training on Pocket Cube and transferring to full 3×3 Rubik's Cube). The experiments use fixed problem distributions with identical state/action spaces for training and testing, so the generalization question remains open.

How This Paper Positions Itself

The paper situates XOT at the intersection of three research threads, explicitly claiming to combine their strengths while avoiding their individual weaknesses:

Thread 1: Structured Prompting for LLMs (CoT → ToT → GoT)

XOT is presented as the next logical step in the evolution of thought prompting paradigms, not a replacement for them. The paper's Figure 1 visualizes this progression: IO (no structure) → CoT (linear chain) → ToT (tree) → GoT (graph) → XOT (flexible structure, external evaluation). Each step in this progression added flexibility (linear → branching → interconnected) at the cost of efficiency (more LLM calls for evaluation). XOT breaks this pattern by decoupling flexibility from LLM cost—the MCTS module provides flexible exploration, while the LLM provides knowledge-grounded reasoning and error correction.

The paper positions XOT as complementary to these paradigms rather than adversarial. The final inference stage of XOT still uses prompt formats similar to CoT (the thought trajectory is linearized into step-by-step text, as shown in the prompt examples in Appendix D), and the revision process draws on LLM capabilities that are also used in ToT's evaluation step. XOT doesn't eliminate the LLM's role—it reallocates it from expensive exploration to targeted revision.

Thread 2: MCTS and RL for Search and Planning

XOT draws heavily on AlphaGo Zero's architecture (Silver et al., 2017): a combined policy and value network trained through self-play MCTS simulations, with the PUCT algorithm guiding action selection during search. The paper explicitly cites this lineage and adopts much of the training procedure:

• MCTS simulations follow the standard select → expand & evaluate → backpropagate cycle.
• The PUCT formula (Equation 1) balances exploration and exploitation using the same form as AlphaGo Zero, with the predicted prior probability $P_\theta(s, a)$ from the policy network and the visit-count-based exploration bonus.
• The loss function (Equation 2) jointly optimizes value prediction (MSE) and policy alignment (cross-entropy with MCTS visit frequencies), again following the AlphaGo Zero template.
• Training iterates: run MCTS simulations with the current networks → collect (state, policy target, value target) data → retrain networks → repeat.

Where XOT differs from standard AlphaGo Zero-style MCTS is in what it does with the search output. In AlphaGo Zero, the MCTS policy is used directly to select moves. In XOT, the MCTS output is a thought trajectory—a sequence of state-action pairs—that is converted to text and presented to the LLM. The LLM then acts as a quality filter and error corrector, examining the trajectory for mistakes that the MCTS missed and triggering additional search if needed.

This is a genuinely novel combination: MCTS provides systematic exploration and domain-specific heuristics, while the LLM provides common-sense reasoning and knowledge-grounded error detection that the MCTS's learned value function may lack. The paper frames this as a "mutually beneficial arrangement": MCTS gives the LLM a scaffold for exploring complex state spaces it couldn't navigate alone, and the LLM gives MCTS a correction mechanism that catches errors the learned networks missed.

Thread 3: LLM-MCTS Integration for Enhanced Reasoning

The paper situates XOT within a growing body of work that combines MCTS with LLMs, but claims a distinct emphasis on inference-time thought generation rather than training-time optimization. It cites several related approaches:

• RAP (Hao et al., 2023): Uses LLMs as both the world model and reasoning agent, with MCTS as a strategic explorer. This keeps the LLM heavily involved in the search process (similar to ToT's spirit), which XOT argues is inefficient.

• Value-guided decoding (Liu et al., 2023): Integrates MCTS and PPO to improve the preferability of LLM-generated text during decoding. This is primarily a training-time technique for aligning generation with preferences, whereas XOT focuses on test-time thought construction.

• AlphaZero-like tree-search for LLM decoding (Feng et al., 2023): Employs MCTS to guide token-level decoding decisions, enhancing reasoning and planning. This operates at the level of individual token selection, whereas XOT operates at the level of abstract thoughts (which may span multiple tokens or sentences).

XOT's positioning is that these prior integrations still rely on the LLM heavily during search, keeping the evaluation cost high. XOT pushes the LLM out of the search loop entirely during the exploration phase, using it only for post-search verification and revision. This is a cleaner separation of concerns: MCTS handles "how to explore the state space efficiently" (a problem MCTS is designed for), and the LLM handles "does this candidate solution make sense?" (a problem LLMs are naturally good at).

Summary of the Gap and the Positioning

The paper identifies a specific, well-motivated gap: existing thought generation paradigms cannot simultaneously deliver high accuracy, low LLM inference cost, and flexible thought structures because they all require the LLM to serve as the evaluator of intermediate reasoning steps. This creates an unavoidable tradeoff where adding flexibility (trees, graphs) multiplies cost, and reducing cost (linear chains) sacrifices flexibility and often accuracy.

XOT proposes to break this tradeoff by introducing a cheap, learned evaluation mechanism (MCTS guided by small policy/value networks) that handles systematic exploration offline, freeing the LLM to focus on knowledge-intensive verification and final answer synthesis. The approach is positioned as a natural evolution of both prompting paradigms (CoT → ToT → GoT → XOT) and MCTS-LLM integration research, combining the structural flexibility of graph-based reasoning with the efficiency of learned search heuristics. The paper's experiments on three challenging tasks—two of which (8-Puzzle and Pocket Cube) are essentially unsolvable by prior prompting methods—are designed to demonstrate that this combination empirically delivers on all three desiderata simultaneously.

3. Technical Approach

3.1 Reader Orientation

XOT is a two-component system where a lightweight Monte Carlo Tree Search (MCTS) module, guided by small neural networks trained through reinforcement learning, explores the solution space of a complex problem and produces candidate reasoning trajectories ("thoughts"), and a large language model then reviews these trajectories, corrects errors, and synthesizes the final answer. The system solves the problem of the three-way tradeoff in thought generation by removing the LLM from the expensive inner loop of exploration and evaluation—MCTS handles the heavy lifting of systematic state-space search using cheap neural network inferences, while the LLM contributes only at two targeted points: identifying errors in the MCTS output and producing the final polished answer from the revised thought trajectory.

3.2 Big-Picture Architecture (Diagram in Words)

The XOT system has five major components connected in a pipeline with an optional feedback loop:

1. Policy/Value Network ($f_\theta$) — a small multi-layer perceptron (two layers, hidden units (128, 256), total ~$10^6$ parameters) that takes a state representation as input and outputs two things: a scalar value estimate $v_\theta(s)$ predicting the expected future reward from state $s$, and a probability distribution $P_\theta(s)$ over all legal actions in state $s$. This network is trained offline on task-specific MCTS self-play data and serves as the "brain" that guides MCTS exploration efficiently during deployment.

2. MCTS Thought Search Module — the core exploration engine. Given a new problem's initial state, MCTS runs $K$ simulations (each consisting of selection, expansion & evaluation, and backpropagation phases). During simulations, it uses the policy/value network $f_\theta$ to evaluate leaf nodes and the PUCT formula to balance exploration and exploitation when choosing which branches to expand. After $K$ simulations, it extracts one or more thought trajectories—sequences of (state, action) pairs—based on visit counts at the root and subsequent states.

3. Thought-to-Prompt Parser — a deterministic converter that takes the MCTS-extracted thought trajectories and translates each (state, action) pair into natural language text describing the step and its outcome. For multi-solution problems, multiple trajectories are concatenated into a single prompt. The output is a text block formatted as structured reasoning steps (e.g., "Step 1: Choose move Left. Current State: ...").

4. LLM Thought Reviser — the LLM receives the parsed thought trajectory and is instructed to identify errors. It examines each step using its internal knowledge, and if it finds a step that it believes is incorrect (e.g., a move that doesn't lead toward the goal, an arithmetic mistake, a state that doesn't match), it flags that step as erroneous. The system extracts the parent state of the identified erroneous step and triggers additional MCTS simulations starting from that state.

5. Iterative Revision Controller — a loop that manages the back-and-forth between MCTS and the LLM. After the LLM identifies an error, MCTS runs $L$ additional simulations from the parent state of the error, producing a revised thought trajectory. This revised thought is re-presented to the LLM for verification and final answer generation. The process can repeat for multiple revision rounds (the paper experiments with 1–3 rounds). In multi-solution scenarios, each solution trajectory is revised independently.

Information flow during deployment (after training):

1. A new problem arrives → its initial state is fed to the MCTS module.
2. MCTS runs $K$ simulations, guided by $f_\theta$, to explore the state space and extract one or more thought trajectories.
3. The Thought-to-Prompt Parser converts these trajectories to structured text.
4. The LLM receives the parsed thought + the problem and is prompted to identify any erroneous steps.
5. If an error is found: MCTS runs $L$ additional simulations from the parent state of the error → the revised thought replaces the erroneous portion → the LLM receives the updated thought.
6. Steps 4–5 repeat for the specified number of revision rounds.
7. The LLM receives the final revised thought and generates the answer.

Training flow (offline, task-specific):

1. MCTS self-play runs for a fixed number of episodes, using the current $f_\theta$ (or random initial weights for the first iteration) to guide search.
2. For each state encountered during self-play, the system records: the state $s$, the MCTS visit-count distribution $\varepsilon(s)$ (which becomes the policy target), and the accumulated reward from $s$ to the end of the episode (which becomes the value target).
3. The collected data $(s, \varepsilon(s), v(s))$ is used to train $f_\theta$ via the combined loss (Equation 2).
4. The updated $f_\theta$ is used in the next iteration of self-play. The paper uses three iterations, each comprising 10 self-play episodes.

3.3 Roadmap for the Deep Dive

• First, the MDP formulation (Section 3.2 of the paper): how states, actions, rewards, and thoughts are formally defined for each task. This is the foundation—everything downstream depends on having well-defined state transitions and reward signals that MCTS can optimize over.

• Second, the MCTS thought searching mechanism (Section 3.3 of the paper): the four phases of each simulation (selection, expansion & evaluation, backpropagation), the PUCT formula that guides action selection, and how the policy/value network is trained from self-play data. Understanding the search mechanism is critical because it is the engine that produces the thought trajectories the LLM ultimately uses.

• Third, the thought inference and revision pipeline (Section 3.4 of the paper): how MCTS extracts thought trajectories from visit counts, how these trajectories are converted to text prompts, how the LLM identifies errors, and how the revision loop triggers additional MCTS simulations. This is where the MCTS and LLM components interface, and the revision loop is the key to XOT's performance gains over standalone MCTS.

• Fourth, the policy/value network architecture and training specifics: the concrete network design (shared MLP with two heads), training hyperparameters (iterations, episodes per iteration, simulation counts), and computational costs during training versus testing. This matters for understanding the practical tradeoffs of the approach.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a systems-building paper whose core idea is that offloading systematic state-space exploration to MCTS (guided by cheap learned heuristics) and reserving the LLM for knowledge-grounded error correction breaks the performance-efficiency-flexibility tradeoff that constrains prior thought-generation paradigms.

---

Markov Decision Process Formulation for Thought Searching

The paper formalizes the thought-generation process as a Markov Decision Process (MDP), which is the standard mathematical framework for sequential decision-making under uncertainty. An MDP provides a precise language for describing states, actions, transitions, and rewards—all of which are necessary for MCTS to systematically search for solution trajectories.

The MDP consists of four components:

• State $s_t$: Represents the current status of the problem at step $t$. The initial state $s_0$ corresponds to the original unsolved problem (e.g., the four numbers in Game of 24, the scrambled grid in 8-Puzzle, the scrambled cube configuration in Pocket Cube). Intermediate states are either decomposed sub-problems or the results stemming from their resolution—for example, after two moves in 8-Puzzle, the state is the new tile configuration; after one arithmetic operation in Game of 24, the state is the set of remaining numbers.

• Action $a_t$: Signifies the one-step operation applied to the current state to transition to a new state. Actions are task-specific: in Game of 24, an action is selecting two numbers and an operator to form an intermediate equation; in 8-Puzzle, an action is sliding the empty tile in one of four directions (Up, Down, Left, Right); in Pocket Cube, an action is one of nine legal rotation moves (U, U', U2, R, R', R2, F, F', F2).

• Reward $r$: A scalar signal that evaluates whether the problem has been effectively resolved. The paper defines rewards task-specifically:

  • Game of 24: $+1$ if the final equation uses each input number exactly once and evaluates to 24, and $-1$ otherwise.
  • 8-Puzzle: The negative of the minimum number of steps required to solve the current puzzle state toward the goal state. This is a dense, informative reward that penalizes being far from the solution.
  • Pocket Cube: The negative of the minimum number of moves required to solve the current cube state toward the goal state. Again, a dense reward that provides gradient information even for non-terminal states.

• Thought $\tau$: A one-step thought is defined as the combination of a state and the action taken in that state: $\tau = \{s, a\}$. A complete sequence of thoughts $T = \{\tau_1, \ldots, \tau_N\}$ forms a thought trajectory—the step-by-step decomposition of the problem into sub-tasks, each accompanied by its outcome. The goal of thought searching is to find the trajectory that maximizes accumulated reward.

Why this formulation matters: By casting thought generation as an MDP, the paper makes it amenable to standard planning algorithms like MCTS. The MDP framework provides three things that are essential for systematic search: (1) a clear definition of what constitutes a valid step forward (state transitions via actions), (2) a quantitative signal for evaluating partial progress (rewards), and (3) a formal objective (maximize cumulative reward) that can guide the search algorithm's exploration. Without this formalization, there's no principled way to compare different thought trajectories or to train a value function that predicts long-term quality from intermediate states.

The paper provides concrete instantiations of this MDP for each task in Table 2. For Game of 24, the thoughts are the three intermediate equations, the state is the set of remaining numbers (1–4 numbers), and actions involve picking two numbers and an operation. For 8-Puzzle, the thoughts are the step-by-step slide moves and the puzzle state after each move, the state is the current 3×3 number layout, and actions are the four directional moves of the empty tile. For Pocket Cube, the thoughts are the step-by-step rotations and the cube configuration after each move, the state is the colors of each face, and actions are the nine rotation moves. This task-specific instantiation is necessary because the MCTS module operates on structured state representations, not raw text—the LLM never sees these internal representations; it only receives the text-converted thought trajectories at the end.

---

Monte Carlo Tree Search for Thought Exploration

MCTS is the core search algorithm that explores the space of possible thought trajectories. The paper adopts the standard MCTS algorithm from AlphaGo Zero (Silver et al., 2017), which uses neural networks to guide search rather than relying on random rollouts. Each MCTS simulation consists of three phases: selection, expansion & evaluation, and backpropagation. The paper provides a visual illustration in Figure 2, using Pocket Cube as a running example.

Selection Phase: The PUCT Formula

The selection phase starts at the root node (the current problem state) and repeatedly chooses actions until reaching a leaf node—a state that has not yet been fully explored. At each step, the algorithm selects the action $a^*$ that maximizes the PUCT (Predictor + UCT) upper confidence bound:

$a^* = \arg\max_{a \in \mathcal{A}(s)} \left[ Q(s, a) + w \cdot P_\theta(s, a) \frac{\sqrt{N(s)}}{1 + N(s, a)} \right]$

where:

• $Q(s, a)$ is the estimated Q-value of taking action $a$ in state $s$. It represents the algorithm's current estimate of the expected cumulative reward from $(s, a)$ onward. Higher Q-values favor actions that have historically led to good outcomes.
• $P_\theta(s, a)$ is the prior probability assigned to action $a$ in state $s$ by the policy/value network $f_\theta$. This is the network's "intuition" about which actions are promising before any search has been done.
• $N(s, a)$ is the number of times action $a$ has been selected from state $s$ during previous simulations.
• $N(s) = \sum_{b} N(s, b)$ is the total number of times state $s$ has been visited across all actions.
• $w$ is a constant that controls the trade-off between exploitation (favoring actions with high $Q(s,a)$) and exploration (favoring actions with high $P_\theta(s,a)$ that haven't been tried many times).

What this equation computes: For each legal action $a$ in the current state, the formula combines two terms. The first term $Q(s,a)$ is pure exploitation—it says "pick actions that have worked well in past simulations." The second term is an exploration bonus: $P_\theta(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)}$ is high when the network thinks the action is promising ($P_\theta$ is high) AND the action has been tried relatively few times compared to other actions from this state ($N(s,a)$ is small relative to $\sqrt{N(s)}$). The denominator $1 + N(s,a)$ ensures that as an action is tried more times, its exploration bonus shrinks. The resulting $a^*$ is the action that maximizes this combined score.

Why this form: The PUCT formula is a theoretically grounded approach to the exploration-exploitation dilemma in tree search. The pure Q-value term alone would cause the algorithm to repeatedly try the same few high-reward actions, potentially missing better alternatives that happen to have lower initial Q-values. The pure prior probability term alone would ignore the evidence from actual simulations and blindly follow the network's initial guesses. The UCT-style exploration bonus proportional to $\sqrt{N(s)} / (1 + N(s,a))$ provides a principled balance: actions with high prior probability get an initial boost, but as they accumulate visits, the bonus decays, allowing other actions to be explored. The constant $w$ lets the practitioner tune this balance—higher $w$ means more exploration.

The selection process continues recursively: at the root, the algorithm picks $a^*$ using the formula; the environment transitions to the next state $s'$; at $s'$, the algorithm again picks the best action using the formula; and so on, until it reaches a leaf node that hasn't been fully expanded.

Expansion and Evaluation Phase

When the selection phase reaches a leaf node—a state $s$ that has not yet been evaluated—the algorithm expands the tree by adding a new node for $s$. The policy/value network $f_\theta$ is then called to evaluate this state:

$(P_\theta(s), v_\theta(s)) = f_\theta(s)$

where:

• $P_\theta(s)$ is a vector of prior probabilities over all legal actions from state $s$. For each action $a \in \mathcal{A}(s)$, $P_\theta(s, a)$ is the network's estimate of how promising that action is before any search.
• $v_\theta(s)$ is a scalar value estimate of state $s$—the network's prediction of the expected cumulative reward from $s$ to the end of the problem.

What this computes: The policy/value network takes the current state representation as input and simultaneously produces two outputs. The policy head outputs a probability distribution over the legal action space, and the value head outputs a single number estimating the long-term value of being in this state.

Why this form: This dual-output architecture is directly from AlphaGo Zero. The policy output $P_\theta(s)$ is used in future PUCT calculations when this state is visited again—it provides the prior probabilities that guide exploration. The value output $v_\theta(s)$ is used in backpropagation to update the Q-values of ancestor states. By sharing a common neural network body (the shared MLP), the policy and value functions can benefit from shared representations—features that are useful for predicting which actions are good are often also useful for predicting the state's value.

After evaluation, the new state $s$ is marked as "visited," and the values $P_\theta(s)$ and $v_\theta(s)$ are stored at the node for use in subsequent simulations.

Backpropagation Phase

Once a leaf node has been expanded and evaluated, the algorithm updates the Q-values and visit counts for all states and actions along the trajectory from the root to the leaf. For each state-action pair $(s, a)$ on the trajectory:

• The visit count is incremented: $N(s, a) = N(s, a) + 1$.
• The Q-value is updated to incorporate the new information. For unexplored (non-terminal) leaf nodes, the update uses the network's value estimate: the Q-value becomes the running average of $v_\theta$ over all simulations that passed through $(s, a)$. For terminal nodes (where the problem is solved or a maximum depth is reached), the update uses the true reward $r$ from the environment.
• This update propagates backward: the Q-value of a parent state-action pair is the average of the rewards/values obtained from all child states reached via that action.

What this computes: The backpropagation phase updates the search tree's memory of which actions lead to good outcomes. Each simulation's outcome (either a network value estimate or a true terminal reward) flows back up the tree, incrementally improving the Q-value estimates for all states along the path.

Why this form: Backpropagation is what makes MCTS a learning algorithm rather than just random search. Without it, each simulation would be independent, and the algorithm would never accumulate knowledge about which branches are promising. By averaging outcomes over many simulations, the Q-values converge to unbiased estimates of the true expected value of each action, assuming sufficient exploration.

Post-Simulation Action Selection

A single simulation consists of one complete select-expand-evaluate-backpropagate cycle. After running $K$ simulations (e.g., 200 for Game of 24, 20 for 8-Puzzle and Pocket Cube), the algorithm must choose which action to actually take at the root state. The paper uses a visit-count-based probability distribution:

$\varepsilon_a \propto N(s, a)^{1/\gamma}$

where:

• $N(s, a)$ is the visit count for action $a$ from state $s$ after $K$ simulations.
• $\gamma$ is a temperature parameter that controls the sharpness of the distribution. When $\gamma \to 0$, the distribution becomes deterministic (selecting the action with the highest visit count). When $\gamma = 1$, selection is proportional to raw visit counts. Intermediate values interpolate between these extremes.

What this computes: The algorithm converts raw visit counts into a probability distribution over actions, optionally sharpened by the temperature parameter. The idea is that actions that were explored more times during simulations are more likely to be good, and the visit count is a robust signal of action quality (more robust than raw Q-values, which can be noisy with few simulations).

Why this form: Using visit counts rather than Q-values for action selection is a common practice in MCTS implementations. Visit counts naturally incorporate both the value of an action (good actions get visited more often because the PUCT formula favors high-Q actions) and the uncertainty about that value (actions with high prior probability but uncertain value also get visited during exploration). The temperature parameter provides a knob to control exploitation: $\gamma < 1$ amplifies differences in visit counts (favoring the best action more aggressively), while $\gamma = 1$ maintains the natural proportion. The paper doesn't specify the exact value of $\gamma$ used in experiments, but this formulation is standard.

Simulation Budget and Computational Cost

The paper specifies different numbers of simulations for different phases:

• During normal thought searching (inference): 200 simulations per action for Game of 24, 20 simulations per action for 8-Puzzle and Pocket Cube.
• During thought revision: increased to 500 simulations for Game of 24 and Pocket Cube, and 50 simulations for 8-Puzzle. The increase during revision reflects the higher stakes—the revision process is triggered because the initial trajectory contained an error, so more thorough search is warranted to find a corrected path.

The total computational cost of MCTS during inference is $K$ times the cost of one forward pass through $f_\theta$ per leaf evaluation, plus the cost of maintaining the tree data structure. Since $f_\theta$ is a tiny MLP (~$10^6$ parameters), this is dramatically cheaper than even a single LLM call (GPT-3.5 has 175 billion parameters; GPT-4 is estimated at over 1 trillion). Table 12 in Appendix B shows that the number of $f_\theta$ calls during testing ranges from ~56 (8-Puzzle) to ~92 (Game of 24) per problem, which is essentially negligible compared to LLM inference costs.

---

Policy and Value Network Training

The policy/value network $f_\theta$ is the engine that makes MCTS efficient. Without it, MCTS would need to run random rollouts to evaluate leaf nodes, which is vastly more expensive and less informative. The paper trains $f_\theta$ through an iterative self-play procedure adapted from AlphaGo Zero.

Training Data Collection via MCTS Self-Play

In each training iteration, the system runs multiple episodes of MCTS self-play on training problems. For each state $s$ encountered during self-play, the system records three pieces of information:

• The state representation $s$: the structured encoding of the problem state at that point.
• The MCTS visit-count distribution $\varepsilon(s) = \{\varepsilon_a \mid a \in \mathcal{A}(s)\}$: the probability of selecting each action from state $s$, derived from the post-simulation visit counts using the formula $\varepsilon_a \propto N(s, a)^{1/\gamma}$. This serves as the policy target—it represents the "improved" policy that results from running MCTS search, which is typically stronger than the raw network policy.
• The ground-truth value $v(s)$: obtained by accumulating rewards along the trajectory starting from state $s$ to the end of the episode (either until the problem is solved or a maximum depth is reached). This serves as the value target—it is the actual outcome achieved from state $s$ during self-play.

The key idea is that MCTS acts as a policy improvement operator: starting from the network's raw policy $P_\theta(s)$, MCTS search produces a better policy $\varepsilon(s)$ by looking ahead and evaluating outcomes. The network is then trained to predict both the improved policy (distilling the benefits of search into the network's fast forward pass) and the actual outcomes (learning to evaluate states accurately).

The Combined Loss Function

The network $f_\theta$ is trained to minimize a loss function that jointly penalizes errors in value prediction and misalignment with the improved policy:

$\mathcal{L} = (v(s) - v_\theta(s))^2 + \varepsilon(s)^T \log P_\theta(s)$

where:

• $v(s)$ is the ground-truth value from self-play (the accumulated reward from state $s$ to episode end).
• $v_\theta(s)$ is the network's predicted value for state $s$.
• $\varepsilon(s)$ is the target policy distribution (the MCTS visit-count distribution, serving as the "teacher" policy).
• $P_\theta(s)$ is the network's predicted policy distribution over actions.

What this equation computes: The loss has two terms. The first term $(v(s) - v_\theta(s))^2$ is the mean squared error between the true value and the predicted value—standard regression loss that encourages the network to accurately evaluate states. The second term $\varepsilon(s)^T \log P_\theta(s)$ is the cross-entropy between the target policy distribution and the network's predicted policy distribution—standard classification loss that encourages the network's action probabilities to match the improved MCTS policy.

Why this form: The two-term structure follows AlphaGo Zero exactly. The MSE loss for value prediction is appropriate because $v(s)$ is a real-valued scalar (the accumulated reward, which could be positive, negative, or zero), and squared error is the standard loss for regression. The cross-entropy loss for policy prediction is appropriate because $\varepsilon(s)$ is a probability distribution over a discrete action space, and cross-entropy is the maximum-likelihood objective for categorical distributions. The joint optimization is important because the shared MLP body can learn representations that are useful for both tasks simultaneously—features that distinguish good states from bad states (value prediction) are often also useful for distinguishing good actions from bad actions (policy prediction). Training them jointly encourages transfer between the two heads.

The paper notes that the loss function uses the dot product $\varepsilon(s)^T \log P_\theta(s)$, which is mathematically equivalent to the negative log-likelihood of the target distribution under the predicted distribution. This penalizes the network more when it assigns low probability to actions that MCTS found to be promising (high $\varepsilon_a$).

Training Hyperparameters and Schedule

The paper provides specific training details:

• Architecture: A shared multi-layer perceptron (MLP) with two layers and hidden units arranged as (128, 256). Two separate heads (output layers) are connected to the shared MLP body: one for predicting the scalar value $v_\theta(s)$, and one for predicting the action probability vector $P_\theta(s)$. The total parameter count across all three tasks is approximately $10^6$.
• Training iterations: Three iterations total.
• Self-play episodes per iteration: 10 episodes.
• Optimizer and learning rate: Not explicitly specified in the main text—the paper does not mention the optimizer, learning rate, batch size, or other standard training hyperparameters for the policy/value network.

The iterative training procedure works as follows:

1. Iteration 1: MCTS self-play runs with the initial (random or pretrained) network $f_\theta$, generating training data $(s, \varepsilon(s), v(s))$. The network is trained on this data.
2. Iteration 2: MCTS self-play runs with the updated network from Iteration 1, generating new training data. The network is retrained on this new data.
3. Iteration 3: The process repeats once more, producing the final network used for deployment.

This iterative procedure is important because it creates a virtuous cycle: as the network improves, it guides MCTS to explore more intelligently, which generates better training data (higher-quality trajectories, more accurate value targets), which further improves the network. After three iterations, the network has incorporated substantial domain knowledge about the task's state space, value structure, and promising action sequences.

Why this design over alternatives: The paper could have used pure MCTS without a learned policy/value network (i.e., random rollouts to evaluate leaf nodes). This would be extremely inefficient—random rollouts in complex state spaces rarely find solutions, and the value estimates would be noisy. The learned network provides a strong prior that dramatically reduces the number of simulations needed to find good trajectories. The paper could also have used the LLM itself to provide value estimates (as ToT and GoT do), but this would reintroduce the efficiency problem—every leaf evaluation would require an expensive LLM call. By training a tiny task-specific network, XOT gets the benefits of learned heuristics at a fraction of the cost.

---

Thought Inference: Extracting Trajectories from MCTS

Once $f_\theta$ is trained, the system uses it to guide MCTS in solving new problems. After running $K$ simulations for a given problem, the system extracts the thought trajectory based on whether a single solution or multiple solutions are required.

Single-Solution Extraction

For problems where only one solution is needed, the algorithm takes a greedy approach: starting from the initial state $s_0$, at each subsequent state $s$, the action with the highest visit count $N(s, a)$ is selected. The system follows this greedy path through the search tree until it reaches a terminal state (the problem is solved) or a maximum depth.

This produces a single thought trajectory: $T^* = \{\tau_1, \tau_2, \ldots, \tau_N\}$

where each $\tau_i = (s_i, a_i)$ is a state-action pair, and the states follow the transition dynamics of the problem.

Why use visit counts rather than Q-values or network probabilities: Visit counts are a robust aggregate signal. An action accumulates many visits because it was consistently selected by the PUCT formula across many simulations—which means it had both high prior probability from the network and good Q-value estimates from backpropagation. Visit counts naturally integrate exploration and exploitation: an action that was explored heavily (many visits) and turned out to be good (high Q-values from backpropagated rewards) will dominate the visit distribution. An action with a high network prior but poor backpropagated values will get some exploratory visits but won't accumulate as many as consistently rewarding actions.

Multiple-Solution Extraction

For problems where multiple distinct solutions are desired, the algorithm samples $M$ thought trajectories (the paper uses $M = 3$ in all multi-solution experiments) following the probability distribution $\varepsilon_a \propto N(s, a)^{1/\gamma}$ at each state. This means the algorithm doesn't always take the single highest-visit-count action—it sometimes takes the second or third most-visited action, proportional to their relative visit counts.

After sampling $M$ trajectories (the paper samples a larger number—500 for Game of 24, 50 for 8-Puzzle and Pocket Cube—and then filters to the top-3 by visit count after removing duplicates), the system removes duplicate trajectories that produce identical solutions. The top $M$ distinct trajectories with the highest aggregate visit counts are retained.

This sampling approach naturally produces a graph-like thought structure when multiple trajectories share intermediate states or converge toward the same goal from different paths. The paper's Figure 5 illustrates this: in the Game of 24 example, two different solution paths share the initial state and diverge at intermediate steps; in the 8-Puzzle example, trajectories involve back-and-forth recurrent state transitions (reflection); in the Pocket Cube example, four distinct pathways lead to the goal state.

Why sampling rather than taking the top-K deterministic paths: Deterministic selection (taking the K actions with the highest visit counts at each state) would explore only a narrow beam of the search tree and would miss solutions that involve occasionally taking non-dominant actions. Sampling according to the visit distribution allows the algorithm to sometimes take less-visited but still promising branches, producing a more diverse set of candidate solutions. The paper's filtering step (removing duplicates, keeping top-3 by aggregate visit count) ensures that the returned solutions are both diverse and high-quality.

---

Thought-to-Prompt Parsing

The MCTS output is a structured sequence of state-action pairs. To provide this to the LLM (which operates on natural language), the system must convert these structured representations into text. The paper describes this as a straightforward transformation: each $\tau_i = (s_i, a_i)$ is converted into a textual description of the step and its outcome.

The exact format is task-specific and shown in the prompt examples in Appendix D. Generally, each step includes:

• The action taken (e.g., "Move: Left" for 8-Puzzle, "[Move] R" for Pocket Cube, or the intermediate arithmetic expression for Game of 24).
• The resulting state after the action (e.g., the new grid configuration for 8-Puzzle, the updated cube face colors for Pocket Cube, or the remaining numbers for Game of 24).
• A step counter or label (e.g., "Step 1:", "[Step 1]").

For multi-solution scenarios, multiple trajectories are concatenated into a single prompt. The paper does not provide explicit examples of the multi-solution prompt format, but the description in Section 3.4 states that "the thought trajectory is concatenated into a single prompt, even in the case of problems with multiple solutions." This is a significant efficiency point: regardless of how many solutions MCTS produces, the LLM receives one prompt containing all of them and produces its analysis in a single inference call. The LLM is not called separately for each solution.

The prompt format remains consistent across all baselines (CoT, ToT, GoT, XOT) for the final inference step, meaning the performance differences cannot be attributed to prompt engineering advantages—they stem from the quality of the thought trajectories themselves.

---

The Thought Revision Process

This is perhaps the most innovative component of XOT: a collaborative MCTS-LLM framework where the LLM acts as an error detector and the MCTS module acts as a trajectory corrector. The process is iterative and is illustrated in Figure 3.

Step 1: LLM Error Detection

The parsed thought trajectory is presented to the LLM with a specific prompt that instructs it to identify errors. The prompt (shown in Appendix D for all three tasks) follows a consistent pattern:

• It presents the initial state and the complete thought trajectory (step-by-step actions and resulting states).
• It states that the trajectory is incorrect because it doesn't reach the goal state (or produces the wrong answer).
• It instructs the LLM to identify the exact wrong step among the sequence.
• It provides guidance on how to reason about which step is wrong, often suggesting starting analysis from Step 1.

The LLM returns the index of the erroneous step (e.g., "Step 3 is wrong, with Move: F2" in the Pocket Cube revision example). This identifies an error state $s_e$—the state that resulted from the erroneous action—and the system extracts the parent state of $s_e$ (the state immediately before the error was made).

Why the LLM for error detection rather than the value network: The value network $v_\theta(s)$ provides a scalar estimate of state quality, and one might think it could detect errors by flagging states with low values. However, the value network is trained on self-play data from the same MCTS module—it has the same blind spots and biases. The LLM brings external knowledge (common sense, understanding of the task rules, ability to simulate consequences) that the value network may lack. The paper's ablation study on incomplete thoughts (Section 4.4.2) provides indirect evidence: when the last step of a thought trajectory is deliberately omitted, performance drops substantially, showing that the LLM relies on the completeness and correctness of the thought—and its ability to detect when something is wrong is real.

The paper reports revision success rates in Tables 9 and 10. For GPT-3.5, the success rate (proportion of errors detected among cases that would have failed without revision) ranges from 20% (8-Puzzle, 1 revision) to 75.93% (Game of 24, 3 revisions). For GPT-4, it ranges from 32.69% to 91.38%. These rates increase with the number of revision rounds, suggesting that multiple rounds of error detection and correction are genuinely effective—the LLM catches different errors in each round, or catches residual errors introduced during earlier corrections.

Step 2: MCTS Re-Search from the Error State

Once the parent state of the erroneous step is identified, the MCTS module runs $L$ additional simulations starting from that state (where $L$ is increased compared to normal search: 500 vs. 200 for Game of 24, 50 vs. 20 for 8-Puzzle and Pocket Cube). The goal is to find an alternative action sequence from the parent state that avoids the error and leads toward the solution.

The re-search uses the same $f_\theta$ network and PUCT-guided selection, but with more simulations to ensure thorough exploration—the system already knows the previous path was wrong, so it invests extra compute to find a better alternative.

Why re-search from the parent state rather than from scratch: Restarting from the initial state would discard the correct prefix of the thought trajectory. The LLM identified a specific step as erroneous, implying that the steps before it were acceptable. Re-searching only from the point of divergence is far more efficient and preserves the valid reasoning already done.

Step 3: Trajectory Revision and Iteration

The revised thought trajectory, with the erroneous portion replaced by the MCTS re-search output, is re-presented to the LLM. The paper's architecture allows for multiple revision rounds (the experiments use 0, 1, 2, or 3 rounds). In each round:

1. The LLM examines the current trajectory and either identifies a new error or declares the trajectory correct.
2. If an error is identified, MCTS re-searches from the parent of the new error.
3. The revised trajectory replaces the old one.

The process terminates when either the LLM finds no errors (implicitly accepting the trajectory as correct) or the maximum number of revision rounds is reached.

Step 4: Final Answer Generation

After the revision process, the LLM receives the final revised thought trajectory and is prompted to produce the answer. The prompt format is similar to CoT: the thought steps are provided as in-context reasoning, and the LLM synthesizes them into a final answer (e.g., the arithmetic expression for Game of 24, the move sequence for 8-Puzzle, the rotation sequence for Pocket Cube).

In multi-solution scenarios, each solution trajectory undergoes the revision process individually (as stated in Section 3.4: "In scenarios involving multiple solutions, each solution undergoes this process individually"). The LLM then receives all revised trajectories concatenated and produces the final answers.

Important nuance: the LLM does not blindly follow the MCTS thought. The paper emphasizes that the thoughts "only play a supporting role, assisting LLMs in gathering knowledge from external sources and improving its planning capability. These thoughts do not provide LLMs with definitive or error-free answers, as they may contain inaccuracies or suboptimal solutions." The LLM is expected to use its judgment—if the thought trajectory seems correct, it follows it; if it seems erroneous, it flags the error and triggers revision; and in the final synthesis, it may incorporate its own knowledge beyond what the thought trajectory provides.

The paper reports the total number of LLM invocations in Tables 3–8, which includes both the error-detection calls during revision and the final answer generation call. With 1 revision, XOT uses ~1.4–1.6 LLM calls per problem; with 3 revisions, ~1.6–2.3 calls. This is roughly 20–30× fewer LLM calls than ToT and GoT, which use 40–60 calls per problem, while achieving substantially higher accuracy.

---

Summary of Design Choices and Their Justifications

• MDP formulation with task-specific state/action/reward definitions: provides the formal structure that MCTS requires to systematically search. Without well-defined states and transitions, MCTS cannot operate. The reward definitions (especially the dense, distance-based rewards for 8-Puzzle and Pocket Cube) are critical for providing learning signal even for non-terminal states.

• PUCT-guided MCTS over simpler search algorithms (BFS, DFS, random sampling): PUCT provides principled exploration-exploitation balancing that is essential for efficient search in large state spaces. BFS/DFS would explore uniformly regardless of promise, and random sampling would be unlikely to find solutions in complex problems.

• Learned policy/value network over random rollouts or LLM-based evaluation: random rollouts are too inefficient (most random action sequences don't solve the problem). LLM-based evaluation is too expensive (one call per leaf node) and unreliable (the LLM's self-evaluation is poorly calibrated, as evidenced by ToT's weak performance). The learned network provides a "good enough" heuristic that is orders of magnitude cheaper.

• Joint policy-value training with MCTS self-play: the iterative self-play procedure creates a feedback loop where better networks → better MCTS → better training data → better networks. The joint loss ensures that the shared representation learns features useful for both value prediction and action selection.

• Visit-count-based trajectory extraction over Q-value-based or probability-based extraction: visit counts are more robust than raw Q-values (they integrate over many simulations and aren't sensitive to a single noisy evaluation) and more informative than raw network probabilities (they incorporate the results of actual lookahead search).

• LLM-based error detection over value-network-based error detection: the LLM brings external knowledge and common-sense reasoning that the value network (trained on the same MCTS self-play data) lacks. This is the key to XOT outperforming standalone MCTS—the LLM catches errors that the MCTS module is blind to.

• Targeted re-search from error states over full restart: preserves the correct prefix of the thought trajectory, making revision efficient. The increased simulation budget during revision ($L > K$) reflects the higher stakes and the desire to thoroughly explore alternatives.

• Multi-round revision over single-round: the increasing revision success rates (Tables 9–10) show that each round catches additional errors. The paper's Figure 4 shows that accuracy improves monotonically with the number of revisions across all tasks, validating the iterative approach.

• Small policy/value network (MLP, ~$10^6$ parameters) over larger models: the tiny network size ensures that the MCTS inference overhead is negligible compared to LLM calls. The paper explicitly contrasts this with GPT-3.5's 175B and GPT-4's estimated >1T parameters—the policy/value network is 5–6 orders of magnitude smaller.

• Task-specific training over zero-shot transfer: the paper accepts the cost of training per-task policy/value networks as a worthwhile tradeoff given the dramatic performance and efficiency gains. The training data requirements are relatively modest (1,225 problems for Game of 24, 300 for 8-Puzzle, 1,000 for Pocket Cube), and training is fast (three iterations of 10 self-play episodes each). For applications where problems are sampled repeatedly from a known distribution, this upfront cost is amortized over many deployments.

4. Key Insights and Innovations

Innovation 1: The "Penrose Triangle" as a Diagnostic Framework for Thought Generation Paradigms

The paper's most conceptually distinctive contribution is not a method but a diagnostic framework that explains why existing prompting paradigms have reached an impasse. The analogy of the "Penrose triangle"—an impossible object that appears coherent from any single perspective but cannot exist in three-dimensional space—captures a structural constraint that the field had implicitly accepted but never explicitly named: that performance, efficiency, and flexibility in thought generation form a trilemma where any paradigm can achieve at most two.

Prior work had identified specific weaknesses in isolation: CoT's linear rigidity (Yao et al., 2023), ToT's computational expense (Besta et al., 2023), GoT's evaluation complexity. But these critiques were made from within the paradigms themselves, usually as motivation for proposing the next structural variant. The field operated under the implicit assumption that adding flexibility (chains → trees → graphs) would eventually solve the problem, and if current methods were expensive, that was a matter of engineering refinement or model improvement.

The Penrose triangle framing makes a stronger claim: the trilemma is inherent to the architecture of LLM-based evaluation, not a contingent limitation of current implementations. When the LLM serves as both generator and evaluator of intermediate thoughts, each evaluation is an expensive inference call. Adding flexibility (branching, merging, refining) multiplies the number of evaluation points, necessarily destroying efficiency. Reducing evaluation to recover efficiency forces a return to rigid linear structures, which cap performance on problems requiring exploration. Any paradigm that uses the LLM as its own evaluator is trapped in this geometry.

This is a fundamental reframing, not an incremental observation. It changes the problem from "how do we design a better thought topology?" to "how do we break the generator-evaluator coupling?" The answer—offloading evaluation to a cheap, learned, task-specific module—follows naturally once the diagnosis is clear. The paper's Table 1 is not just a performance comparison; it is a proof of concept for the diagnostic framework itself, demonstrating that XOT achieves all three attributes precisely because it is the first paradigm to decouple the evaluator from the LLM. This framework provides a lens through which future work can be evaluated: does a proposed method unify generator and evaluator in the LLM? If yes, it will face the same trilemma. If no, it may escape it.

The significance extends beyond the specific methods in this paper. The framework implies that progress in thought generation requires architectural heterogeneity—specialized components for search and evaluation that operate at different cost scales—rather than monolithically scaling LLM capabilities. This is a conceptually distinct path from the dominant trend of making LLMs better at self-evaluation through fine-tuning or prompt engineering. It suggests that even a perfect self-evaluating LLM would still face an efficiency cost per evaluation, and that true resolution of the trilemma requires structural separation of concerns.

Innovation 2: MCTS as a Thought Generator Rather Than a Decision Maker

MCTS has been extensively applied to LLM-based reasoning, but almost always with the LLM serving as the simulator or evaluator within the search loop. In RAP (Hao et al., 2023), the LLM acts as both the world model (predicting state transitions) and the reasoning agent (evaluating states), with MCTS orchestrating the exploration. In value-guided decoding (Liu et al., 2023), MCTS guides token-level selection, but the value estimates come from the LLM's own predictions. The common pattern is: MCTS provides the search structure, and the LLM provides the intelligence that makes search meaningful.

XOT inverts this relationship. Here, MCTS provides the intelligence (via learned domain-specific heuristics in $f_\theta$), and the LLM provides a post-hoc verification and correction service. The LLM is not asked to simulate state transitions, evaluate intermediate states, or guide exploration—tasks it performs unreliably and expensively. Instead, it is asked to do something it is naturally good at: examining a structured reasoning trace and identifying steps that don't make sense, using its broad world knowledge and common-sense reasoning.

This inversion is significant because it changes the division of cognitive labor between symbolic search and neural language modeling. In prior integrations, the LLM did the "thinking" and MCTS did the "bookkeeping." In XOT, the learned policy/value network does the "searching" (systematically exploring a well-defined state space using accumulated experience), and the LLM does the "critiquing" (applying flexible, knowledge-grounded judgment to detect and correct errors). Each component does what it is best at, and the interface between them—the thought trajectory—is designed to be interpretable and correctable by the LLM.

This is a fundamental architectural shift rather than a refinement of existing MCTS-LLM integration patterns. It is enabled by a pragmatic observation: for tasks with well-defined state spaces and reward signals, a tiny neural network trained on simulation data can become a better search heuristic than an LLM that must simulate everything from scratch in natural language. The LLM's advantage—broad knowledge, flexible reasoning—becomes most valuable at the verification stage, where it can catch errors that the specialized but narrow $f_\theta$ missed.

The experimental evidence for this inversion's effectiveness is starkest in the comparison between standalone MCTS and XOT with revision. On Game of 24, standalone MCTS achieves 62.77% accuracy; adding one round of LLM revision jumps to 79.56% (GPT-3.5) and 74.45% (GPT-4), gains of ~17 and ~12 percentage points respectively (Table 3). On 8-Puzzle with GPT-4, standalone MCTS's 51.26% becomes 93.28% with one revision—a 42-percentage-point jump (Table 5). These gains are not from the LLM generating better thoughts from scratch (which ToT's poor performance shows it cannot do reliably); they are from the LLM correcting specific errors in MCTS-generated trajectories. The LLM is additive to MCTS, not a replacement for it.

This insight generalizes beyond the specific tasks in the paper. Any domain where (a) a simulator or environment can provide ground-truth rewards for training, and (b) problems require systematic search through a large state space, could benefit from training a small search module and using an LLM as a post-hoc verifier. The paper opens a design space where specialized search modules and general-purpose LLMs collaborate through structured, interpretable interfaces—a pattern that may prove broadly useful as LLMs are deployed in increasingly complex planning and reasoning domains.

Innovation 3: The Revision Loop as a Lightweight Alternative to Full Self-Correction

The paper's revision mechanism addresses a well-known problem—LLMs make errors when reasoning over multiple steps—but through a deliberately narrow, targeted intervention rather than the open-ended self-correction approaches that prior work explored. This narrowness is precisely what makes it effective.

Prior work on LLM self-correction (Huang et al., 2023; Stechly et al., 2023; Valmeekam et al., 2023) asked models to examine their own outputs and improve them, with generally disappointing results. The failure mode is well-documented: LLMs struggle to detect their own errors, often doubling down on incorrect reasoning or "correcting" already-correct answers into wrong ones. The paper itself reports that in a naive sequential revision approach, approximately 38% of correct answers get converted back to incorrect ones (Section 6.1 of the companion summary).

XOT's revision loop succeeds where open-ended self-correction fails because it constrains the LLM's role to error localization only, not full solution generation. The LLM is asked a highly specific question: "which step in this pre-computed trajectory is wrong?" It is not asked to generate an alternative, evaluate the overall quality, or produce a corrected solution from scratch. The actual correction is performed by MCTS re-search—a systematic, symbolic process that won't hallucinate or drift from the problem constraints.

This constraint transforms a hard open-ended reasoning problem ("is this correct, and if not, how do I fix it?") into a more tractable anomaly detection problem ("does any step in this sequence violate the rules or look unreasonable?"). The LLM's broad knowledge is well-suited to the latter: it can recognize that a move in 8-Puzzle leaves the empty space in an illegal position, or that an arithmetic step in Game of 24 uses a number that isn't available, or that a cube rotation doesn't produce the claimed face configuration. These are pattern-matching judgments that leverage the LLM's training on vast text corpora, not the kind of multi-step planning that LLMs struggle with.

The revision success rates reported in Tables 9 and 10 provide direct evidence for this framing. GPT-4 achieves an 85.96% success rate on 8-Puzzle error detection with one revision (Table 10)—meaning that in the vast majority of cases where MCTS's initial trajectory was wrong, the LLM correctly identified the erroneous step. GPT-3.5's lower rates (20% on 8-Puzzle, one revision) reflect its weaker capabilities, but the pattern of improving with more revision rounds holds for both models: GPT-3.5 goes from 47.17% to 75.93% on Game of 24 across 1 to 3 revisions.

This is a conceptual advance in how to use LLMs for error correction: not as autonomous self-improvers but as targeted anomaly detectors within a larger system that handles the actual correction through non-LLM mechanisms. It suggests a design principle for LLM-augmented systems: decompose the problem into subtasks where the LLM's strengths (pattern recognition, anomaly detection, knowledge-grounded judgment) are isolated from its weaknesses (multi-step planning, systematic search, state tracking). The revision loop embodies this principle cleanly.

Innovation 4: Task-Specific Learned Search Heuristics as an Inference-Time Resource

The paper demonstrates a new category of inference-time resource: small, task-specific neural networks that encode domain knowledge acquired through self-play and amortize the cost of systematic search. This sits between two well-explored extremes in the literature.

At one extreme, zero-shot prompting (IO, CoT) uses no task-specific training—the LLM relies entirely on its pretrained knowledge and in-context examples. This is maximally flexible but fails on problems requiring systematic exploration, as the paper's baselines show (0% accuracy on 8-Puzzle for GPT-3.5 with IO and CoT).

At the other extreme, fine-tuning encodes task-specific knowledge directly into the LLM's weights. The paper tests this with LLaMA-2-13B fine-tuned on the same training data used for XOT's MCTS. The result is striking: 0% accuracy on both 8-Puzzle and Pocket Cube (Tables 5 and 7). The fine-tuned model fails not because it lacks information but because it hallucinates—producing outputs that look like solutions but are factually wrong. The paper's interpretation is that fine-tuning cannot teach a model to perform systematic state-space search; it can only bias the model's next-token predictions based on patterns in the training data.

XOT's learned policy/value network $f_\theta$ occupies a third category: an inference-time resource that is trained offline on task-specific data but is not part of the LLM. It is an external module that the LLM queries during reasoning. This category has several distinctive properties:

• Cost amortization: Training is a one-time cost (Table 12 shows training requires ~787–1045 calls to $f_\theta$ per iteration, representing a few thousand forward passes through a tiny MLP). Deployment incurs only the inference cost of the trained network, which is negligible compared to LLM calls.

• Complementarity to LLM capabilities: $f_\theta$ learns what the LLM is bad at (systematic state-space search, long-horizon planning, value estimation) and leaves to the LLM what it is good at (knowledge-grounded verification, natural language generation). The two components are not substitutes but complements.

• Interpretable interface: The thought trajectory is a structured, inspectable artifact that the LLM can reason about. This contrasts with fine-tuning, where the task-specific knowledge is opaque and distributed across billions of weights.

• No hallucination risk: MCTS with $f_\theta$ performs systematic search within the defined state space. It may produce suboptimal trajectories (which the LLM can detect and correct via revision), but it cannot produce outputs that violate the state transition rules—a guarantee that LLM-based generation cannot provide.

The empirical case for this third category rests on the gap between MCTS-alone and XOT performance versus the gap between baseline prompting and any approach involving MCTS. On 8-Puzzle with GPT-4, the best prompting baseline (ToT, b=3) achieves 13.45% (Table 5). MCTS alone achieves 51.26%. XOT with one revision reaches 93.28%. The jump from 13.45% to 51.26% is the contribution of systematic search via $f_\theta$—showing that domain-specific search heuristics make previously impossible problems solvable. The jump from 51.26% to 93.28% is the contribution of LLM-based error correction—showing that the LLM adds value beyond the search module. Both components are necessary; neither alone achieves the full performance.

This is a fundamentally new design pattern for LLM-augmented systems, not an incremental improvement to existing prompting or fine-tuning approaches. It suggests that for domains with well-defined objectives and available simulators, the optimal architecture may be a heterogeneous system where small, specialized modules handle structured search and large, general-purpose modules handle flexible reasoning and verification. The paper provides a concrete blueprint for building such systems and demonstrates that the investment in training task-specific modules pays off dramatically in inference-time performance and efficiency.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The paper evaluates on three distinct tasks, each with its own dataset: (1) Game of 24: 1,362 problems sourced from 4nu, ranked by human solving time to span difficulty levels from easy to hard; 137 randomly selected for testing, 1,225 for training the policy/value networks with MCTS. (2) 8-Puzzle: 419 randomly generated solvable problems on a 3×3 grid, all solvable within 9 steps; 300 for training, 119 for testing. (3) Pocket Cube (2×2 Rubik's Cube): 1,000 training and 183 testing samples, generated by randomly applying 5 actions from the 27 legal moves to a solved cube; all test problems are solvable within 4 steps.

• Base model(s). Experiments use both GPT-3.5 (Ouyang et al., 2022) and GPT-4 (OpenAI, 2023) as the LLM reasoning engines. Temperature and top-p are set to 0.0 for all LLM invocations to ensure deterministic outputs. For comparison, the paper also fine-tunes LLaMA-2-13B (Touvron et al., 2023) on the same training data with ground-truth labels, using eight V100 GPUs (80GB each) for approximately 5 hours, with a learning rate of 2×10⁻⁵, batch size of 32, 5 epochs, and a cosine learning rate scheduler. The policy/value network fθ uses a shared MLP architecture with two layers and hidden units (128, 256), two separate output heads for vθ(s) and Pθ(s), totaling approximately 10⁶ parameters—orders of magnitude smaller than the LLMs.

• Metrics. The primary metric is test accuracy (%): the percentage of test problems for which the final answer matches the ground-truth solution. For multi-solution scenarios, two additional metrics are reported: Multi-Solution Accuracy (MultiAcc), defined as the average percentage of correctness across all solutions offered (computed as the percentage of problems for which any of the provided answers is correct), and #Sol, the total count of distinct solutions provided by each approach regardless of correctness. The maximum number of solutions is set to 3 for all multi-solution experiments. For all approaches, the paper also tracks the number of LLM invocations required to solve a single problem, and for XOT specifically, the number of fθ invocations.

• Baselines. The paper compares against seven baselines: (1) Input-Output (IO) prompting—direct question-to-answer without intermediate steps; (2) Chain-of-Thought (CoT) (Wei et al., 2022)—sequential step-by-step reasoning; (3) Self-Consistency CoT (CoT-SC) (Wang et al., 2023a)—majority voting over 10 independent CoT samples; (4) Tree-of-Thought (ToT) (Yao et al., 2023)—tree-structured search with LLM-based evaluation of intermediate thoughts, tested with branching factors b=1 and b=3; (5) Graph-of-Thought (GoT) (Besta et al., 2023)—graph-structured thought generation with LLM-based evaluation and merging of thoughts, tested with k=1 and k=3; (6) Standalone MCTS without LLM—the MCTS module alone, using the trained policy/value network to select actions but no LLM for revision or final inference; and (7) Fine-tuned LLaMA-2-13B—supervised fine-tuning on the same training data with ground-truth labels. For all prompting baselines (IO, CoT, CoT-SC, ToT, GoT), in-context examples are provided with task-specific formatting; the prompt format for the final inference step is kept consistent across all methods including XOT.

• Generation budget / compute accounting. For LLM-based baselines, "compute" is measured by the number of LLM inference calls per problem. For ToT and GoT, each candidate thought generation and evaluation counts as one LLM call; the paper reports average calls across the test set (e.g., ToT with b=3 on Game of 24 uses ~40–44 calls on GPT-4, ~44–56 on GPT-3.5). For XOT, the "LLM invoked" count includes both error-detection calls during revision and the final answer generation call. Additionally, XOT reports the number of fθ invocations (forward passes through the small policy/value network) during MCTS search and revision; these are tracked separately because fθ is 5–6 orders of magnitude smaller than the LLMs. The paper's efficiency argument rests on the observation that fθ calls are negligible compared to LLM calls: for Game of 24 with 3 revisions, XOT uses ~1.7 LLM calls plus ~93 fθ calls (GPT-3.5, Table 3), whereas ToT (b=3) uses ~44 LLM calls with zero fθ calls.

• Cross-validation / statistical protocol. No explicit cross-validation or statistical significance testing is reported. The test sets are fixed random splits: 137/1225 for Game of 24, 119/300 for 8-Puzzle, 183/1000 for Pocket Cube. All methods are evaluated on the identical test sets. The paper does not report confidence intervals, standard deviations, or any form of statistical testing. Results are reported as point estimates (single accuracy percentages) without error bars. The revision success rates in Tables 9–10 are computed as ratios of successfully detected errors to the number of failed cases without revision, but no uncertainty quantification is provided.

Main Quantitative Results

Game of 24

Single-solution performance (Table 3). XOT dramatically outperforms all prompting baselines and standalone MCTS on both GPT-3.5 and GPT-4. With GPT-3.5 and 3 revision rounds, XOT achieves 90.51% accuracy using only 1.72 LLM calls and 95.94 fθ calls on average. With GPT-4 and 3 revisions, XOT reaches 85.40% accuracy with 1.78 LLM calls and 92.48 fθ calls. For comparison, the strongest prompting baseline—ToT with b=3 on GPT-4—achieves only 60.58% accuracy while requiring 39.83 LLM calls. Standalone MCTS (no LLM revision) achieves 62.77% on both models, meaning the LLM revision process contributes approximately 23–28 percentage points of additional accuracy beyond what MCTS alone provides. The IO baseline achieves only 6.57% (GPT-3.5) and 10.22% (GPT-4); CoT reaches a mere 2.19% and 4.38% respectively—worse than IO, suggesting that step-by-step prompting without systematic search actually degrades performance on this task. CoT-SC (majority voting over 10 samples) does not improve over CoT, remaining at 2.19% and 4.38%. GoT with k=1 achieves only 2.92% (GPT-3.5) and 10.95% (GPT-4). The fine-tuned LLaMA-2-13B achieves 2.19% on both models, confirming that fine-tuning fails for this planning-intensive task. Notably, XOT with GPT-3.5 consistently outperforms XOT with GPT-4 on this task (90.51% vs. 85.40% at 3 revisions), a reversal of the typical capability ordering that the paper attributes to GPT-3.5 being more effective at the targeted error-detection task than GPT-4's more verbose or overconfident reasoning.

Multi-solution performance (Table 4). In the multi-solution scenario (maximum 3 solutions), XOT with GPT-3.5 and 1 revision achieves 62.90% MultiAcc, generating an average of 2.29 distinct solutions per problem while using 3.51 LLM calls and 116.34 fθ calls. With GPT-4, XOT achieves 76.25% MultiAcc with 2.36 solutions, 2.31 LLM calls, and 109.64 fθ calls. The best prompting baseline in this setting is GoT (k=3) with GPT-4, which achieves only 10.46% MultiAcc with 1.39 solutions and 7.00 LLM calls—producing fewer, less accurate solutions than XOT despite requiring 3× more LLM calls. ToT (b=3) on GPT-4 achieves 39.90% MultiAcc but requires 39.83 LLM calls—over 17× more expensive than XOT. The fine-tuned LLaMA-2-13B is not evaluated in the multi-solution setting. A key observation: XOT generates multiple solutions with only modest increases in LLM calls (from ~1.7 in single-solution to ~2.3–3.5 in multi-solution) and fθ calls (~93 to ~110–116), demonstrating that the MCTS module's ability to extract multiple trajectories from visit count distributions adds flexibility without proportionally increasing cost.

8-Puzzle

Single-solution performance (Table 5). The 8-Puzzle task reveals a stark capability gap: all LLM-based prompting baselines fail badly, while XOT succeeds overwhelmingly. With GPT-4 and 3 revision rounds, XOT achieves 95.80% accuracy using only 1.61 LLM calls and 62.22 fθ calls. With GPT-3.5, XOT reaches 63.03% accuracy with 2.29 LLM calls and 42.60 fθ calls. In contrast, the best prompting baseline—ToT with b=3 on GPT-4—achieves only 13.45% accuracy while consuming 54.13 LLM calls. IO prompting achieves 0.00% (GPT-3.5) and 1.68% (GPT-4). CoT reaches 0.00% and 7.56%. CoT-SC marginally improves to 0.84% and 8.40%. GoT (k=1) achieves 3.36% on both models. The fine-tuned LLaMA-2-13B scores 0.00% on both models, a striking negative result that the paper attributes to "significant hallucination issues" when attempting to generate move sequences without systematic search capabilities. Standalone MCTS achieves 51.26% on both models—showing that the MCTS module alone provides a strong baseline that no prompting method approaches, but LLM revision is essential to reach the high-90% accuracy range. The gap between GPT-4 (95.80%) and GPT-3.5 (63.03%) on this task is the largest among the three, suggesting that GPT-4's stronger common-sense reasoning and error-detection capabilities are particularly valuable for the spatial planning demands of 8-Puzzle.

Multi-solution performance (Table 6). In the multi-solution setting, XOT with GPT-4 and 1 revision achieves 76.33% MultiAcc with an average of 1.52 solutions, using 4.30 LLM calls and 66.66 fθ calls. With GPT-3.5, XOT achieves 27.45% MultiAcc with 2.85 solutions, using 4.19 LLM calls and 52.06 fθ calls. The strongest prompting baseline in this setting is GoT (k=3) with GPT-4, achieving 16.61% MultiAcc with 2.70 solutions but requiring 22.76 LLM calls—over 5× more LLM calls than XOT for less than one-quarter the accuracy. ToT (b=3) on GPT-4 achieves only 5.60% MultiAcc despite 54.13 LLM calls. A notable pattern: GPT-3.5 with XOT generates more solutions on average (2.85) than GPT-4 (1.52), but GPT-4's solutions are far more accurate (76.33% vs. 27.45% MultiAcc), suggesting that GPT-4's error detection during revision filters out incorrect trajectories more effectively, resulting in fewer but higher-quality solutions.

Pocket Cube

Single-solution performance (Table 7). The Pocket Cube represents the hardest spatial reasoning challenge, and the pattern from 8-Puzzle is amplified: prompting baselines are nearly helpless, while XOT succeeds. With GPT-3.5 and 3 revisions, XOT achieves 84.70% accuracy using 2.01 LLM calls and 103.22 fθ calls. With GPT-4, XOT reaches 83.61% accuracy with 2.00 LLM calls and 84.63 fθ calls. The best prompting baseline—ToT with b=3 on GPT-4—achieves only 19.57% accuracy with 56.58 LLM calls. GoT (k=1) on GPT-4 reaches 18.03% with 8.55 LLM calls—better efficiency than ToT but still far below XOT's accuracy. IO and CoT baselines on GPT-4 achieve 1.09% each; on GPT-3.5, IO achieves 1.09% while CoT scores 0.00%. CoT-SC scores 0.00% on GPT-3.5 and 1.09% on GPT-4—majority voting over 10 samples provides no benefit. The fine-tuned LLaMA-2-13B scores 0.00% on both models. Standalone MCTS achieves 46.44%—similar to 8-Puzzle, this is a strong baseline that no prompting method approaches, but the LLM revision adds approximately 37–38 percentage points of accuracy. Unlike Game of 24 where GPT-3.5 slightly outperformed GPT-4, on Pocket Cube the two models perform nearly identically with XOT (84.70% vs. 83.61% at 3 revisions), suggesting that the task's difficulty is dominated by the MCTS module's ability to find correct trajectories, with the LLM's revision capability being roughly equivalent across the two models.

Multi-solution performance (Table 8). In multi-solution scenarios, XOT with GPT-4 and 1 revision achieves 77.41% MultiAcc with an average of 1.72 solutions, using 4.08 LLM calls and 122.54 fθ calls. With GPT-3.5, XOT achieves 48.72% MultiAcc with 2.20 solutions, using 4.13 LLM calls and 115.73 fθ calls. The strongest prompting baseline is GoT (k=3) with GPT-4, reaching 16.85% MultiAcc with 2.77 solutions but requiring 13.36 LLM calls—over 3× more LLM calls than XOT. ToT (b=3) on GPT-4 achieves only 6.52% MultiAcc. The GPT-3.5 vs. GPT-4 gap in multi-solution XOT (48.72% vs. 77.41%) mirrors the single-solution 8-Puzzle pattern rather than the single-solution Pocket Cube pattern, suggesting that generating multiple correct solutions is a harder task that better distinguishes model capabilities.

Cross-Task Patterns

Across all three tasks, several consistent patterns emerge:

1. Revision monotonicity (Figure 4). Accuracy improves with each additional revision round for all task–model combinations. The gains are not uniform: on Game of 24 with GPT-3.5, accuracy increases from 79.56% (1 revision) to 88.32% (2 revisions) to 90.51% (3 revisions), with diminishing returns. On 8-Puzzle with GPT-4, the jump from 0 to 1 revision is massive (51.26% → 93.28%), while subsequent revisions provide smaller gains (93.28% → 94.96% → 95.80%). Pocket Cube shows more linear improvement: GPT-3.5 goes from 45.36% (0 revisions) → 74.32% → 80.33% → 84.70%. The number of LLM invocations increases modestly with revisions (~1.0 to ~2.3 across all tasks), while fθ invocations increase more substantially, particularly for Pocket Cube with GPT-4 where they jump from 75.51 (1 revision) to 146.52 (2 revisions).

2. LLM invocation efficiency. XOT consistently requires 1.4–2.3 LLM calls across all tasks and revision settings, compared to 7–57 calls for prompting baselines. This represents a 5–30× reduction in LLM inference cost. The fθ invocation counts (42–147 per problem) are orders of magnitude cheaper per call than LLM inference, making the total computational cost dominated by the few LLM calls rather than the many fθ calls.

3. Standalone MCTS as a lower bound. Across all three tasks, standalone MCTS achieves 62.77% (Game of 24), 51.26% (8-Puzzle), and 46.44% (Pocket Cube)—all substantially above the best prompting baselines (60.58%, 13.45%, 19.57% respectively). This establishes that the MCTS module with learned policy/value networks is already a powerful problem solver on its own, and that the LLM revision process provides significant but incremental improvements, particularly on the spatial reasoning tasks (8-Puzzle and Pocket Cube) where the LLM's knowledge is most complementary to MCTS's search.

4. Fine-tuning failure. The fine-tuned LLaMA-2-13B scores 2.19% on Game of 24 and 0.00% on both 8-Puzzle and Pocket Cube—despite being trained on the same data used for MCTS self-play. This is a critical negative result: it demonstrates that supervised learning on (problem, solution) pairs cannot teach a model to perform the kind of systematic search and planning that MCTS provides. The paper attributes this to hallucination—the fine-tuned model generates outputs that look like solutions but don't actually solve the problem, a failure mode that MCTS's symbolic state-space exploration avoids.

Ablation Studies and Robustness Checks

Number of revisions (Section 4.4.1, Tables 9–10, Figure 4): This is the most extensively studied ablation. Figure 4 plots accuracy, LLM invocations, and fθ invocations as functions of revision count (0, 1, 2, 3) for all three tasks and both models. On Game of 24, GPT-3.5 benefits more from revisions than GPT-4 (90.51% vs. 85.40% at 3 revisions), while on 8-Puzzle, GPT-4 benefits dramatically more (95.80% vs. 63.03% at 3 revisions). Pocket Cube shows roughly equal benefit (84.70% vs. 83.61%). The LLM invocation count increases approximately linearly with revisions but remains low (1.0 at 0 revisions to ~2.0–2.3 at 3 revisions), while fθ invocations grow more rapidly, particularly on Pocket Cube where they reach 103–147 at 2–3 revisions. The revision success rate (Tables 9–10) quantifies how often the LLM correctly identifies an erroneous step among cases that would have failed without revision. For GPT-3.5, success rates start at 47.17% (Game of 24), 20.00% (8-Puzzle), and 53.00% (Pocket Cube) with 1 revision, and improve to 75.93%, 26.67%, and 72.00% respectively with 3 revisions. For GPT-4, success rates are consistently higher: 32.69% → 60.00% (Game of 24), 85.96% → 91.38% (8-Puzzle), and 58.59% → 70.00% (Pocket Cube). The 8-Puzzle results are striking: GPT-4 detects errors with ~86–91% success rate, while GPT-3.5 manages only ~20–27%, explaining the large performance gap between the two models on this task.

Incomplete thoughts (Section 4.4.2, Table 11): This ablation tests robustness to imperfect MCTS output by deliberately omitting the last step of the thought trajectory before presenting it to the LLM. The comparison is between ToT (b=1), GoT (k=1), and XOT (without revision). On Game of 24, XOT without revision achieves 17.52% (GPT-3.5) and 43.07% (GPT-4)—far below full XOT (79.56% / 74.45% with 1 revision) but still substantially above ToT (b=1) at 3.65% / 40.88% and GoT (k=1) at 2.19% / 9.49%. This suggests that even incomplete MCTS trajectories provide useful guidance that the LLM can partially compensate for. On 8-Puzzle, the drop is severe: XOT without revision falls to 2.52% (GPT-3.5) and 40.34% (GPT-4), compared to 51.26% for standalone MCTS and 59.66+% for XOT with revision. ToT and GoT score 0.00–6.72%. The most dramatic collapse occurs on Pocket Cube: XOT without revision drops to 5.46% (GPT-3.5) and 6.01% (GPT-4), from 74.32% / 77.60% with full revision—a near-total failure. The paper interprets this as evidence that "for very complex tasks, LLMs are highly sensitive to the completeness of the thoughts provided," and that the LLM relies on the thought trajectory as a scaffold; when the final step is missing, the LLM cannot independently bridge the gap.

Multi-solution vs. single-solution scaling (Tables 3–8): While not presented as a formal ablation, the comparison between single-solution and multi-solution performance reveals how XOT's efficiency scales with output diversity. On Game of 24 with GPT-4, moving from single-solution (74.45% with 1 revision, 1.38 LLM calls) to multi-solution (76.25% MultiAcc, 2.31 LLM calls) increases LLM calls by ~67% but also increases accuracy—the multi-solution accuracy can exceed single-solution accuracy because the system can provide multiple attempts. On 8-Puzzle, multi-solution XOT with GPT-4 achieves 76.33% MultiAcc vs. 93.28% single-solution accuracy, showing that generating multiple diverse correct solutions is harder than finding a single correct solution—a non-trivial observation about the task structure. On Pocket Cube, the gap is smaller: 77.41% MultiAcc vs. 77.60% single-solution.

GPT-3.5 vs. GPT-4 capability inversion (Table 3, Figure 4a): The paper notes an unusual finding on Game of 24: GPT-3.5 with XOT consistently outperforms GPT-4 (90.51% vs. 85.40% at 3 revisions). This is not presented as a formal ablation but is a significant result that the paper does not fully explain. It speculates that GPT-3.5 may be more effective at the specific error-detection format used in the revision prompts, or that GPT-4's tendency toward more elaborate reasoning may introduce errors during revision. This finding challenges the assumption that stronger base models always benefit more from XOT's framework.

Document Merging (Appendix C, Table 13): As a preliminary test of generalization beyond game-like tasks, the paper evaluates XOT on the Document Merging task from GoT (Besta et al., 2023), where the goal is to merge multiple overlapping documents into a non-disclosure agreement while minimizing duplication and maximizing information retention. Using GPT-3.5, XOT achieves a score of 8.168 with an average token cost of 15,270.80, compared to ToT's 7.715 (51,486 tokens) and GoT's 7.559 (27,685 tokens). This task differs from the main three in that the LLM itself provides the reward signal for MCTS training (rather than a ground-truth simulator), demonstrating that XOT can be applied to NLP tasks where LLMs serve as both reward designers and final output generators.

Critical Assessment

The experiments provide strong evidence for XOT's central claim—that offloading systematic search to MCTS with learned heuristics and using the LLM only for error correction breaks the performance-efficiency-flexibility tradeoff. However, the experimental design has several limitations that constrain the generality of the conclusions.

Claim: XOT achieves all three desiderata (performance, efficiency, flexibility) simultaneously. The experiments convincingly demonstrate performance and efficiency: XOT achieves 84–96% accuracy across tasks while using ~1.5–2.3 LLM calls, compared to 13–61% accuracy for prompting baselines using 7–57 calls. The efficiency advantage is unambiguous and large. The flexibility claim is supported primarily by the multi-solution experiments and the qualitative examples in Figure 5, which show graph-like thought structures emerging from MCTS exploration. However, the flexibility demonstration is somewhat narrow: all three tasks are search/planning problems with well-defined state spaces, and the "flexibility" amounts to producing different sequences of discrete actions. The paper does not demonstrate flexibility in the sense of adapting thought topology to fundamentally different problem types (e.g., switching between chain reasoning for arithmetic and tree search for planning within a single task), nor does it show that the emergent graph structures from MCTS actually provide benefits over simply taking the top-K most-visited paths. A comparison where XOT's graph-structured output is pitted against a version that linearizes the top-K trajectories into independent chains would clarify whether the graph structure itself adds value.

Claim: XOT enables LLMs to solve problems previously unsolvable by prompting methods. This claim is strongly supported for 8-Puzzle and Pocket Cube, where baselines achieve near-zero accuracy and XOT reaches 84–96%. The experiments clearly demonstrate that LLMs alone, even with sophisticated prompting (ToT, GoT), cannot solve these spatial reasoning tasks, while the MCTS module makes them tractable. However, "previously unsolvable" requires qualification: the claim is relative to the specific prompting baselines tested, not to all possible approaches. The paper does not test whether a substantially larger number of ToT samples (e.g., b=5 or b=10 with correspondingly more LLM calls) could approach XOT's accuracy—the diminishing returns curve of ToT is not characterized. Given that ToT (b=3) on GPT-4 achieves 13.45% on 8-Puzzle with 54 LLM calls, it is plausible that scaling ToT to the equivalent computational cost of training XOT's policy/value network (which requires thousands of self-play episodes) might close some of the gap, though the trend suggests diminishing returns per additional branch.

Test set sizes and composition. The test sets are relatively small: 137 problems for Game of 24, 119 for 8-Puzzle, and 183 for Pocket Cube. Accuracy differences of a few percentage points (e.g., the 90.51% vs. 85.40% GPT-3.5 vs. GPT-4 comparison on Game of 24) correspond to differences of 7 problems out of 137, which could be influenced by sampling noise. The paper reports no confidence intervals or statistical tests, making it difficult to assess whether observed differences are significant. Additionally, all generated test problems for 8-Puzzle are solvable within 9 steps, and for Pocket Cube within 4 steps—these are relatively shallow solution depths. The paper does not evaluate whether XOT's advantage persists or diminishes on deeper problems (e.g., 8-Puzzle instances requiring 15–20 steps, or Pocket Cube instances requiring 7–8 moves), where the search space is exponentially larger and the MCTS module's heuristics may be less reliable.

The ToT and GoT baseline implementations. The paper describes ToT and GoT implementations that follow the original papers but with task-specific adaptations. However, several details suggest these baselines may not be optimally tuned. For ToT, the paper solicits one-step thought candidates from the LLM at each step and instructs the LLM to categorize each candidate for intermediate selection—this is a relatively simple implementation that may underperform more sophisticated versions with better evaluation prompts or iterative refinement. For GoT, the paper's results are consistently worse than ToT's on most metrics (e.g., 2.92% vs. 10.22% on Game of 24 with GPT-4, single-solution), which is surprising given that GoT is designed to be a more flexible superset of ToT. This suggests either that the GoT implementation is suboptimal for these tasks, or that the LLM struggles with the complexity of GoT's merge and refine operations—the paper does not analyze which. A more thorough baseline comparison would include hyperparameter sweeps over branching factors, evaluation prompts, and temperature settings for ToT/GoT, but the paper reports only single configurations (b=1 and b=3 for ToT, k=1 and k=3 for GoT).

Missing baseline: XOT without the policy/value network. The paper does not ablate the learned fθ network by comparing to MCTS with random rollouts (no learned heuristics). This is a significant omission because it would isolate the contribution of task-specific training from the contribution of MCTS as a search framework. It is possible that random-rollout MCTS (with sufficient simulations to match the compute budget of training fθ) could also generate useful thought trajectories, and that the LLM revision process would similarly improve them. Without this ablation, we cannot assess whether the policy/value network is essential or merely an efficiency optimization.

Missing baseline: LLM-only revision without MCTS. The paper does not test whether the LLM could perform the entire solve-revise loop on its own—i.e., generate an initial solution attempt, detect its own errors, and retry—using the same structured prompt format but without the MCTS module providing the initial trajectory. This would clarify whether XOT's gains come from the MCTS module providing better initial thoughts, or from the revision framework itself. The fine-tuned LLaMA-2-13B result (0% on spatial tasks) suggests that LLMs cannot solve these tasks independently, but a prompted GPT-4 self-revision loop (without MCTS) would be a stronger test of whether the LLM can self-correct in these domains.

Generalization evidence is limited. The paper's Appendix C presents a single preliminary result on Document Merging (Table 13), using LLM-based rewards rather than ground-truth simulators. While this is promising, it is a single data point with minimal detail about the training setup. The paper does not evaluate whether the policy/value network trained on one task transfers to related tasks (e.g., 8-Puzzle training → 15-Puzzle testing, or Pocket Cube → 3×3 Rubik's Cube), which would be the most direct test of the claim that the learned heuristics capture generalizable domain knowledge rather than memorizing specific problem distributions.

Training cost is underanalyzed. Table 12 reports the number of fθ calls during training (~787–1045 per iteration, with three iterations), but this is not contextualized against the cost of the LLM calls that baselines require. For example, training XOT on Game of 24 requires approximately 3 × 1045 = 3135 forward passes through a 10⁶-parameter MLP. During testing, ToT (b=3) on GPT-4 uses ~40 LLM calls per problem; at 137 test problems, that's ~5480 LLM calls. The training cost of XOT is thus a small fraction of the inference cost of the strongest baseline, even on a modest test set, and would be amortized to near-zero in a production deployment solving thousands of problems. However, this analysis is not provided in the paper, leaving the efficiency argument incomplete.

The Pocket Cube results show a fθ invocation anomaly. On Pocket Cube with GPT-4 and 2 revisions, fθ invocations spike to 146.52 (Table 7) but drop back to 84.63 at 3 revisions. This non-monotonic pattern is unusual (revision rounds are expected to add simulations, not subtract them) and is not discussed or explained in the paper. It may indicate a reporting error, a bug in the experimental setup, or a legitimate phenomenon where additional revisions reduce the need for extensive re-search (e.g., if the LLM identifies errors earlier in the trajectory, requiring shallower re-search). Without explanation, it raises questions about the reliability of the reported fθ invocation counts.

The "Penrose triangle" framing is a conceptual claim, not an experimentally tested hypothesis. The paper does not design experiments to test whether the trilemma is truly inescapable for LLM-evaluator paradigms—it simply observes that existing paradigms exhibit the tradeoff and demonstrates that XOT does not. A stronger test would systematically vary the number of LLM evaluation calls in ToT (e.g., by using smaller models or distilled evaluators) and measure whether the performance-efficiency tradeoff curve is truly Pareto-dominated by XOT. As presented, the Penrose triangle serves as an effective framing device but is not empirically validated as a fundamental constraint.

6. Limitations and Trade-offs

Limitation 1: The Policy/Value Network Requires Task-Specific Training Data with a Ground-Truth Simulator

The assumption or constraint. XOT's MCTS module relies on a learned policy/value network fθ trained through self-play reinforcement learning. This training requires (a) a well-defined state space, action space, and transition function; (b) dense, informative reward signals for non-terminal states; and (c) a simulator that can generate training episodes and compute ground-truth rewards. The paper explicitly defines such rewards for each task—the negative minimum distance to the goal state for 8-Puzzle and Pocket Cube, and +1/−1 terminal rewards for Game of 24—and generates training data through MCTS self-play episodes (three iterations, 10 episodes each). The paper does not test XOT on any task lacking these properties.

The consequence. This requirement fundamentally restricts XOT's applicability. The method cannot be applied to domains where state transitions are not enumerable, where reward signals are sparse or subjective (e.g., creative writing, dialogue quality, argument persuasiveness), or where no simulator exists to generate training rollouts. The paper provides only one extension beyond game-like domains: the Document Merging task in Appendix C, where it uses the LLM itself as the reward function. However, this introduces circularity (the LLM both provides rewards for training and consumes the MCTS output at inference) that the paper does not analyze for robustness or calibration issues. A practitioner facing a novel reasoning task must either have an existing simulator or build one—a non-trivial engineering effort that may be impossible for open-ended domains. The paper's headline results (84–96% accuracy) cannot be extrapolated to tasks without these properties, and the paper provides no guidance on the minimum simulator fidelity or reward density needed for effective training.

What evidence exists in the paper. The paper's task selection embodies this constraint: all three tasks are deterministic puzzles with fully observable state spaces, enumerable action spaces, and computable ground-truth optimal solutions against which reward signals can be defined. The dense reward definitions (negative distance to goal for 8-Puzzle and Pocket Cube) provide informative learning signals that are essential for training the value function to generalize to unseen states. The paper does not ablate reward density to test whether XOT remains effective with sparse terminal-only rewards. The Document Merging result (Table 13, Appendix C) relaxes the simulator requirement but introduces the LLM as reward provider, which is a different—and potentially unreliable—source of training signal.

Mitigation status. The paper acknowledges this limitation in Section 6 (Discussion): "The implementation of XOT necessitates the training of additional policy and value models to expedite the inference process. This training process requires the acquisition of datasets from real-world environments, introducing supplementary costs and efforts." It argues that the policy/value networks are "considerably smaller and more computationally efficient than the underlying LLMs" and that costs are "deemed low, particularly in the context of tasks featured in this study, where the thought steps and objectives are well-defined." It proposes future work on "scenarios where the objectives are less straightforward, such as multi-agent planning and code generation tasks," but provides no concrete approach for extending XOT to such domains.

---

Limitation 2: Difficulty Estimation and Hard Problem Failure Are Not Addressed—XOT Cannot Help When MCTS Itself Fails

The assumption or constraint. XOT assumes that MCTS, guided by the trained fθ, can find a thought trajectory that is at least partially correct—close enough to a valid solution that the LLM's revision process can fix remaining errors. The method provides no mechanism for recognizing when MCTS has failed to find any useful trajectory, nor for escalating to a different strategy. The paper does not include a difficulty estimation component (unlike the compute-optimal test-time scaling framework in the comparison paper, which bins problems by difficulty and adapts strategy accordingly). XOT applies the same MCTS + revision pipeline uniformly to all problems regardless of their intrinsic difficulty.

The consequence. When MCTS fails to generate a useful trajectory—either because the problem is too hard for the current fθ or because the training distribution did not cover similar states—the LLM is presented with an erroneous or nonsensical trajectory, asked to detect errors, and may either miss the errors (producing a wrong answer) or correctly identify errors but trigger revisions that also fail to converge. The paper does not measure how often MCTS produces trajectories that are so poor that even multiple revision rounds cannot salvage them. The performance numbers for the hardest subsets of problems are not reported separately. For example, on 8-Puzzle with GPT-3.5, XOT with 3 revisions reaches 63.03% (Table 5)—meaning approximately 37% of problems remain unsolved even after maximum revision. The paper does not analyze whether these failures are due to MCTS producing irredeemably bad trajectories, the LLM failing to detect errors, or the LLM revising incorrectly. Without difficulty stratification, a practitioner cannot know whether XOT's failures are concentrated on a predictable subset of problems (e.g., those requiring more steps or deeper search) that could be routed to a different solver.

What evidence exists in the paper. The incomplete thought ablation (Section 4.4.2, Table 11) provides indirect evidence of this limitation. When the last step of the MCTS trajectory is deliberately omitted, performance collapses: on Pocket Cube, XOT without revision drops from 74–78% to 5.5–6.0%. This shows that the LLM relies heavily on the MCTS trajectory being substantially complete; when it is not, the LLM cannot compensate. Inferring from this: if MCTS produces a trajectory with a critical error early on (not just a missing final step), the LLM may similarly fail. The paper does not report per-difficulty accuracy breakdowns or analyze the correlation between MCTS trajectory quality (e.g., distance to a valid solution, number of correct steps) and final XOT accuracy.

Mitigation status. Not addressed. The paper does not propose any difficulty estimation mechanism, any confidence score for MCTS trajectories, or any fallback strategy when MCTS produces low-quality output. The revision loop is the only corrective mechanism, and it relies on the LLM being able to identify errors—but if the entire trajectory is nonsense, the LLM may flag "all steps are wrong" (as allowed by the revision prompt format in Appendix D for 8-Puzzle and Pocket Cube), and MCTS would need to re-search from the initial state, effectively starting over with no guarantee of better results. The paper does not report how often this occurs or whether additional simulation budget during re-search improves outcomes.

---

Limitation 3: The Method Has Only Been Validated on a Single Model Family (GPT-3.5/GPT-4) with a Narrow Class of Deterministic Puzzle Tasks

The assumption or constraint. All XOT experiments use GPT-3.5 and GPT-4 as the LLM reasoning engines. The paper does not evaluate XOT with any open-weight models (e.g., LLaMA-2-70B, Mixtral, Claude) or with models from other providers. Furthermore, all three primary tasks—Game of 24, 8-Puzzle, and Pocket Cube—are deterministic puzzles with a single correct answer (or a set of equally valid move sequences), fully observable state spaces, and well-defined optimal solutions. The tasks require no external knowledge retrieval, no natural language understanding beyond rule comprehension, and no reasoning about ambiguity or uncertainty.

The consequence. The paper cannot make claims about XOT's effectiveness across different model architectures, sizes, or training distributions. The unusual finding that GPT-3.5 outperforms GPT-4 on Game of 24 with XOT (90.51% vs. 85.40% at 3 revisions, Table 3) suggests that the LLM's role in error detection interacts with model-specific characteristics in non-obvious ways—GPT-4's tendency toward more elaborate reasoning may introduce errors during revision that GPT-3.5's more constrained outputs avoid. If this pattern generalizes, practitioners using other model families may observe unpredictable performance. More critically, the restriction to deterministic puzzles means the paper provides no evidence that XOT works for tasks requiring: (a) probabilistic reasoning, (b) natural language generation quality assessment, (c) integration of retrieved knowledge, (d) reasoning under ambiguity, or (e) tasks where correctness is graded on a continuous scale rather than binary match. The Document Merging result (Appendix C) partially addresses the last point by using a multi-dimensional score, but this is a single preliminary experiment with no ablation or error analysis.

What evidence exists in the paper. The task descriptions in Table 2 explicitly define all three tasks in terms of deterministic state transitions and binary/ordinal reward signals. The GPT-3.5 vs. GPT-4 performance inversion on Game of 24 (Table 3) is commented on but not explained: the paper notes "the revision process in XOT mitigates the performance gap attributable to the modeling ability in this task" without specifying why a weaker model would benefit more from revision. The fine-tuned LLaMA-2-13B results (0% on 8-Puzzle and Pocket Cube, 2.19% on Game of 24) provide a single data point on open-weight models, but this is a much smaller model (13B vs. GPT-3.5's 175B) and was evaluated in a fine-tuning setup, not as the LLM component within XOT's revision framework—so it cannot speak to whether LLaMA-2-13B could serve as an effective error detector within XOT.

Mitigation status. The paper does not claim broader model compatibility, and the Discussion section (Section 6) frames future work on extending to code generation and multi-agent planning but does not commit to evaluating on diverse model families. The paper acknowledges in Section 6: "XOT is presently utilized for reasoning and search problems, its applicability can be extended to a broader spectrum of problem domains characterized by decomposable tasks with well-defined objectives." However, this acknowledges the scope limitation without mitigating it.

---

Limitation 4: The Revision Success Rates Are Far Below 100%, and LLM Error Detection Is Inherently Unreliable

The assumption or constraint. XOT's revision loop depends on the LLM correctly identifying which step in an MCTS-generated trajectory is erroneous. The paper reports revision success rates—the proportion of failure cases where the LLM correctly detects the error—in Tables 9 and 10. These rates vary dramatically by task and model. For GPT-3.5 on 8-Puzzle, the success rate is only 20.00% with one revision, improving to only 26.67% after three revisions. For GPT-4, the rates are higher (85.96–91.38%) but still leave 8.6–14% of errors undetected. On Game of 24 with GPT-4, even after three revisions, 40% of errors go undetected (60.00% success rate). The paper provides no analysis of what happens when the LLM fails to detect an error: does it confidently assert the trajectory is correct (leading to a wrong final answer), or does it flag the wrong step (leading MCTS to re-search from an incorrect point)?

The consequence. The revision loop is not a guaranteed improvement mechanism—it is a probabilistic error detector with task- and model-dependent reliability. For tasks and models where the revision success rate is low (e.g., GPT-3.5 on 8-Puzzle at 20–27%), additional revision rounds provide minimal benefit because the LLM cannot reliably identify what to fix. This explains the performance plateau on 8-Puzzle with GPT-3.5 (63.03% even after 3 revisions, Table 5) compared to GPT-4 (95.80%)—the gap is largely driven by GPT-3.5's inability to detect errors in a domain requiring spatial reasoning that the model fundamentally lacks. A practitioner cannot assume that adding more revision rounds will monotonically improve accuracy; if the LLM lacks the knowledge to evaluate trajectory quality in a domain, the revision loop provides little or no benefit beyond standalone MCTS. Furthermore, the paper does not report whether the LLM sometimes identifies correct steps as erroneous (false positives), which would cause MCTS to re-search from an unnecessarily early point, potentially degrading the trajectory. The 38% correct-to-incorrect reversion rate mentioned in the companion summary's discussion of naive sequential revision suggests this is a real risk, though not quantified within XOT's specific revision framework.

What evidence exists in the paper. Tables 9 and 10 provide the revision success rates. The large gap between GPT-3.5 and GPT-4 on 8-Puzzle (20% vs. ~86–91%) is the most revealing data point—it shows that the revision mechanism's effectiveness is gated by the LLM's domain competence, which varies dramatically. Figure 4 shows that accuracy improves with revision count for all tasks, confirming that the mechanism works on average, but the per-task variance in success rates suggests that the average masks substantial heterogeneity across individual problems. The incomplete thought ablation (Table 11) shows that when MCTS output is deliberately degraded, performance collapses, confirming that the LLM cannot compensate for poor trajectories—but it does not isolate whether this is due to failure to detect the error or failure to solve the remaining step independently.

Mitigation status. The paper does not propose any mechanism to improve revision reliability beyond increasing the number of revision rounds. It does not explore alternative prompts that might improve error detection, ensemble approaches (multiple LLM calls voting on which step is wrong), or combining the LLM's error detection with the value network's state evaluation (which could flag states with anomalously low vθ(s) as error candidates). The revision process is treated as a black box whose reliability is accepted as given, with no attempt to characterize when it will fail or to build safeguards against false positives.

---

Limitation 5: The FLOPs and Latency Accounting Is Incomplete—Training Cost, MCTS Overhead, and Serial Dependencies Are Not Fully Measured

The assumption or constraint. The paper measures efficiency primarily through the number of LLM invocations per problem, arguing that fθ calls are negligible because fθ is ~10⁶ parameters versus GPT-3.5's 175×10⁹ and GPT-4's estimated >10¹². However, the paper does not provide a full end-to-end compute accounting that includes: (a) the training cost of fθ (Table 12 reports call counts but not FLOPs or wall-clock time), (b) the inference FLOPs of fθ relative to LLM inference FLOPs, (c) the wall-clock latency of the serial MCTS simulation loop (which cannot be parallelized across the K simulations within a single MCTS invocation), or (d) the latency cost of the revision loop (each round requires an LLM call followed by additional MCTS simulations—a serial dependency).

The consequence. A practitioner cannot accurately compare the total cost of XOT against baselines without knowing the full compute picture. The LLM invocation count (~1.5–2.3 for XOT vs. 40–57 for ToT) suggests a dramatic advantage, but this comparison ignores the training cost of fθ and the cumulative inference cost of ~42–147 fθ forward passes per problem. If fθ requires 3 iterations × 10 episodes × ~1000 states per episode = ~30,000 forward passes for training on Game of 24, and the test set has only 137 problems, the amortized training cost per test problem is non-trivial—approximately 30,000 / 137 ≈ 219 equivalent fθ forward passes per test problem, on top of the 88–96 fθ inference calls reported in Table 3. The paper's argument that fθ is "considerably smaller" than the LLM is a qualitative comparison, not a quantitative one. Without FLOP counts, one cannot determine the cross-over point where XOT's total compute (training + inference) becomes cheaper than ToT's inference-only cost.

More importantly for deployment feasibility: MCTS search and the revision loop are inherently serial processes. The K simulations per action cannot be parallelized because each simulation depends on the updated Q-values and visit counts from previous simulations (backpropagation updates the tree state). The revision loop requires LLM call → MCTS re-search → LLM call, a serial chain with no parallelism. For a production system with latency constraints (e.g., an interactive assistant that must respond within seconds), the ~1.5–2.3 LLM calls may take 3–10 seconds each for GPT-4, plus the MCTS simulation time. The paper reports no wall-clock latency measurements for any component. A ToT baseline with 40 LLM calls would be slower if run serially, but many of those calls (e.g., evaluating different branches at the same tree depth) can be parallelized—the paper does not explore this possibility.

What evidence exists in the paper. Table 12 reports training call counts for fθ: 1044.70, 834.70, and 787.00 per iteration for Game of 24, 8-Puzzle, and Pocket Cube respectively. With 3 iterations, total training fθ calls are ~3134, ~2504, and ~2361. The testing fθ call counts are 88.20, 55.66, and 75.51 (Table 12, bottom row—these appear to be for the 1-revision setting based on comparison with Tables 3, 5, 7). The paper does not report: FLOPs per fθ forward pass, FLOPs per LLM forward pass, wall-clock time for MCTS simulations, wall-clock time for LLM calls, or total end-to-end latency. The paper's statement in Appendix B that "the computational cost of these recurring calls during testing exceeds the pretraining cost of the policy/value model in XoT" is made qualitatively without numerical FLOP comparison.

Mitigation status. Partially addressed in Appendix B, which argues qualitatively that "methods like ToT and GoT, which rely solely on the LLMs' internal knowledge, do not require pretraining but necessitate frequent calls to LLM during testing" and that the recurring LLM calls during testing exceed the one-time pretraining cost of fθ. This argument is based on LLM call count, not on FLOPs, and it does not address latency or the amortization question for small test sets. The paper does not propose any latency-reduction strategies (e.g., parallelizing MCTS simulations through root parallelization, caching fθ evaluations for revisited states, or speculatively running multiple revision rounds in parallel).

---

Limitation 6: The Baseline Implementations Are Not Optimized and the Comparison May Overstate XOT's Advantage

The assumption or constraint. The paper compares XOT against IO, CoT, CoT-SC, ToT (b=1, b=3), and GoT (k=1, k=3), using fixed prompt templates and hyperparameters. The ToT and GoT implementations follow the original papers but are not tuned for the specific tasks beyond basic adaptations (e.g., setting maximum step limits). The paper does not report hyperparameter sweeps over branching factors beyond b=1 and b=3, over evaluation prompt designs, or over search algorithms (ToT supports both BFS and DFS; the paper appears to use only one, though it does not specify which). The fine-tuned LLaMA-2-13B baseline uses a fixed learning rate and 5-epoch training schedule with no reported hyperparameter optimization.

The consequence. The comparison may systematically disadvantage the baselines in ways that inflate XOT's apparent advantage. ToT with b=3 uses ~40–57 LLM calls but the paper does not test b=5 or b=10 to characterize the scaling behavior—if ToT accuracy improves with more branches but at a slower rate, the reported numbers represent only one point on the scaling curve. Similarly, GoT's consistently poor performance (often worse than ToT) suggests the implementation may be suboptimal—the paper does not analyze why GoT underperforms despite being designed as a more flexible superset of ToT. The fine-tuned LLaMA-2-13B baseline uses a model that is two orders of magnitude smaller than GPT-3.5/4, making it an apples-to-oranges comparison for evaluating whether fine-tuning is competitive with XOT. The paper interprets the 0% accuracy as evidence that "finetuning is not suitable for planning tasks," but a 13B model fine-tuned with simple (problem, solution) pairs is a weak baseline; a fine-tuned 70B model with chain-of-thought fine-tuning data might perform substantially better.

The positive framing of the "GPT-3.5 outperforms GPT-4" result on Game of 24—presented as evidence that XOT "mitigates the performance gap attributable to modeling ability"—could alternatively be interpreted as evidence that the GPT-4 baseline is poorly tuned for this task, since we would expect a stronger LLM to be at least as good at error detection as a weaker one. Without a systematic study of prompt sensitivity and LLM-specific optimization for the baselines, the paper cannot rule out that the ToT and GoT numbers could be substantially improved with better prompting.

What evidence exists in the paper. The prompt examples in Appendix D show the CoT prompt format used across all methods; the ToT and GoT implementations are described briefly in Sections 4.1.2, 4.2.2, and 4.3.2. The paper does not report: hyperparameter sweeps for any baseline; experiments varying the number of in-context examples (ToT and GoT use the same prompts as CoT but with additional evaluation steps—the effect of in-context example count and selection is unexplored); or any attempt to optimize baselines for specific tasks. The GoT results are consistently poor: on Game of 24 single-solution with GPT-4, GoT (k=1) achieves 10.95% while ToT (b=1) achieves 34.31%—a counterintuitive result given that GoT should be able to replicate ToT's tree structure.

Mitigation status. The paper does not claim that the baselines are optimally tuned, but it also does not discuss this as a limitation. The prompt formats are made available in Appendix D for reproducibility, and the paper uses standard implementations from the original ToT and GoT papers. The weakness of the baselines—particularly GoT—is not analyzed or explained. A more robust evaluation would include sensitivity analysis of baseline performance to key hyperparameters (branching factor, evaluation prompt, temperature) and would test at least one larger open-weight model as the LLM component within XOT to verify that the approach is not GPT-3.5/4-specific.

7. Implications and Future Directions

How This Work Changes the Landscape

XOT introduces a fundamental architectural shift in how we think about augmenting LLMs for complex reasoning: rather than asking the LLM to serve as both generator and evaluator of intermediate thoughts (the unified architecture underlying CoT, ToT, and GoT), XOT decouples systematic search from language-based reasoning and allocates them to different components operating at radically different cost scales. This is not an incremental improvement to prompting—it is a re-architecting of the problem-solving pipeline that changes the division of cognitive labor between symbolic search and neural language modeling.

The magnitude of this shift is best understood through the lens of the paper's own "Penrose triangle" diagnostic. Prior to XOT, the field implicitly accepted that performance, efficiency, and flexibility formed an inescapable trilemma for thought-generation paradigms—you could have any two, but never all three. ToT and GoT demonstrated that flexibility could be achieved through tree and graph structures, but at the cost of multiplying LLM calls for evaluation. CoT and its variants preserved efficiency by avoiding evaluation, but at the cost of rigid linear structure and capped performance on exploration-heavy problems. The trilemma seemed structural: as long as the LLM was both proposer and evaluator of thoughts, each unit of flexibility cost one unit of LLM inference, and there was no way around this.

XOT breaks this trilemma not by making LLMs better at evaluation, but by eliminating LLM-based evaluation from the search loop entirely. The MCTS module, guided by a tiny learned policy/value network ($f_\theta$ with ~10⁶ parameters—five to six orders of magnitude smaller than GPT-3.5's 175B), handles the heavy lifting of systematic state-space exploration. The LLM is reserved for two targeted, knowledge-intensive tasks: detecting errors in MCTS-generated trajectories and synthesizing the final answer. This reallocation of cognitive work means that the cost of flexibility—exploring multiple branches, backtracking from dead ends, producing graph-like thought structures—is now borne by cheap neural network forward passes rather than expensive LLM inference calls. The LLM's role shifts from "search engine" to "quality control inspector and final assembler."

This reframing has several concrete consequences for how the field should think about LLM-augmented reasoning:

First, it establishes that systematic search and flexible reasoning are separable concerns that can be implemented in different components at different cost tiers. The dramatic gap between standalone MCTS performance and the best prompting baselines on spatial reasoning tasks—51.26% vs. 13.45% on 8-Puzzle, 46.44% vs. 19.57% on Pocket Cube (Tables 5 and 7)—shows that even a simple MLP trained on self-play data can outperform GPT-4 with sophisticated tree-search prompting when the task requires systematic state-space exploration. The LLM's strength is not in exhaustive search but in flexible, knowledge-grounded judgment—and XOT's architecture respects this distinction rather than papering over it with more expensive prompting.

Second, it demonstrates that the LLM's value in a reasoning pipeline can be additive rather than substitutive relative to traditional search methods. The jump from standalone MCTS to MCTS + LLM revision is substantial and task-dependent: +17–12 percentage points on Game of 24 (62.77% → 79.56% / 74.45%, Table 3), +42 percentage points on 8-Puzzle with GPT-4 (51.26% → 93.28%, Table 5), +31 percentage points on Pocket Cube with GPT-3.5 (46.44% → 77.60%, Table 7). The LLM is not replacing MCTS—it is fixing specific errors that MCTS's learned heuristics missed. This is a fundamentally different model of LLM-search integration than prior work, which typically used the LLM as the intelligence inside the search loop.

Third, it redirects research attention from "how do we make LLMs better at self-evaluation?" toward "how do we train cheap, specialized modules that handle the parts of reasoning LLMs are bad at?" The paper's negative result on fine-tuning—LLaMA-2-13B achieving 0% on both 8-Puzzle and Pocket Cube despite training on the same data used for MCTS self-play (Tables 5 and 7)—is particularly instructive. It suggests that some reasoning capabilities (systematic search, state tracking, long-horizon planning) cannot be effectively compressed into LLM weights through supervised learning on input-output pairs. They require architectural support—a search mechanism with explicit state representations and value-guided exploration. This finding should temper enthusiasm for pure fine-tuning approaches to planning and search problems and motivate investment in heterogeneous architectures.

Fourth, it reconciles the apparent contradiction between ToT/GoT's theoretical flexibility and their empirically modest performance. The paper's GoT results are consistently worse than ToT's despite GoT being designed as a more flexible superset (e.g., 2.92% vs. 10.22% on Game of 24 single-solution with GPT-4, Table 3). This is not a failure of the graph concept—it is a failure of using the LLM as the mechanism for managing graph operations. When the LLM must decide when to merge thoughts, which nodes to aggregate, and how to score merged results, the complexity of these meta-reasoning tasks exceeds its reliability, and the added flexibility becomes a liability. XOT's graph-structured outputs (Figure 5) emerge naturally from MCTS's exploration strategy without the LLM needing to reason about graph topology—the graph is a byproduct of visit-count-based trajectory extraction, not something the LLM constructs through explicit merge/refine operations. This resolves the paradox: graph structures are valuable, but they should be emergent from search rather than constructed by LLM reasoning about graph operations.

Fifth, the work opens up a new category of inference-time resource—task-specific learned search modules—that sits between zero-shot prompting and full model fine-tuning. This category has no established name or design space in the current LLM literature. It is not prompt engineering (it requires training), not fine-tuning (it doesn't modify the LLM), and not retrieval-augmented generation (it doesn't retrieve from a corpus). It is closer in spirit to the "system 1 / system 2" distinction from cognitive science: a fast, specialized, experience-based module handles the routine exploration, and a slow, flexible, knowledge-based module handles verification and error correction. The paper provides a concrete architecture and training recipe for this new category, which may inspire a broader class of systems where small neural networks amortize the cost of search across many inference queries.

Follow-Up Research This Work Enables

1. Characterizing the performance frontier of learned search heuristics vs. LLM-based evaluation. The paper demonstrates that a tiny MLP ($f_\theta$) trained on MCTS self-play outperforms GPT-4-based evaluation for spatial reasoning tasks, but it does not systematically vary model size, training data quantity, or search budget to map out the performance frontier. A natural follow-up would train policy/value networks of increasing capacity (from the paper's ~10⁶ parameters up to ~10⁹ parameters, still tiny relative to LLMs) on increasing amounts of self-play data, and measure at what point the learned heuristics saturate relative to LLM-based evaluation. The key question: is there a cross-over where a large enough $f_\theta$ makes LLM revision unnecessary (approaching 100% standalone MCTS accuracy), or does the LLM always provide additive value because it brings knowledge that the simulator cannot provide? The paper's results suggest the latter—standalone MCTS plateaus at 46–63% while LLM revision pushes to 84–96%—but without scaling $f_\theta$ capacity, we cannot distinguish between "the current network is too small" and "the LLM contributes irreplaceable knowledge." A strong experiment would train policy/value networks at 10⁶, 10⁷, and 10⁸ parameters on Game of 24 and 8-Puzzle, measure standalone MCTS accuracy and XOT accuracy with 0–3 revisions at each scale, and report the diminishing returns curve.

2. Transfer learning between related search tasks. The paper trains separate policy/value networks for each task from scratch. A critical open question is whether knowledge transfers: if you train $f_\theta$ on 8-Puzzle (3×3 grid, up to 9-step solutions), does it accelerate training or improve performance on 15-Puzzle (4×4 grid, deeper solutions), or on 8-Puzzle instances requiring 15–20 steps? The state and action representations would differ (larger grid, more tiles), but the underlying search dynamics—sliding tiles toward a goal configuration—share structure. A follow-up study would pre-train $f_\theta$ on one puzzle variant, fine-tune on another, and compare sample efficiency (number of self-play episodes needed to reach a target accuracy) against training from scratch. This would test whether the learned heuristics capture generalizable "puzzle-solving skill" or merely memorize patterns specific to the training distribution. A negative result—no transfer at all—would suggest that XOT's approach requires per-task engineering and cannot amortize training across related domains. A positive result would open the door to pre-trained "search modules" that can be rapidly adapted to new planning tasks.

3. The LLM error detection bottleneck: when does it fail and how can it be improved? The paper reports revision success rates ranging from 20% (GPT-3.5 on 8-Puzzle) to 91% (GPT-4 on 8-Puzzle, 2 revisions)—a massive gap that is correlated with the final performance gap between models on the same task. This identifies LLM error detection as the critical bottleneck for XOT's applicability to domains where the LLM lacks deep understanding. A systematic follow-up would characterize which types of errors the LLM detects well and which it misses. For 8-Puzzle, GPT-3.5's 20% success rate means it misses 80% of errors—are these errors concentrated at specific depths (early vs. late in the trajectory), specific move types, or specific state configurations? By instrumenting the revision process to log (a) the ground-truth error location, (b) the LLM's identified error location, and (c) whether the LLM's identification was correct, one could build a confusion matrix of error detection. This would enable targeted improvements: if the LLM misses early-step errors but catches late-step errors, the revision prompt could be modified to emphasize early-step scrutiny. If errors in certain action types (e.g., cube rotations that affect multiple faces) are systematically missed, the prompt could include explicit guidance for analyzing those action types.

4. Combining MCTS-guided search with LLM-generated candidate actions. The paper's MCTS module explores a fixed action space defined by the task rules. The LLM is used only for post-hoc error detection, not for proposing actions during search. A natural extension would let the LLM expand the action space during MCTS by proposing novel actions or sequences that the task definition didn't enumerate. For example, in Game of 24, the LLM might recognize arithmetic patterns (e.g., "when you have two numbers that multiply to 24, look for ways to make the remaining numbers evaluate to 1") that the fixed action space of "pick two numbers and an operator" doesn't capture at the meta-level. These LLM-proposed actions could be added to the MCTS action set at specific states, with the policy network learning to select among them based on outcomes. This would blur the current clean separation between MCTS (exploration) and LLM (verification) and test whether LLM-generated heuristics can improve search efficiency beyond what self-play alone discovers. The key metric would be whether adding LLM-proposed actions reduces the number of MCTS simulations needed to find a solution, and whether the quality of LLM-proposed actions improves with stronger models.

5. XOT for code generation with test-suite-based rewards. The paper mentions code generation as a future direction (Section 6) but provides no results. Code generation is a natural fit for XOT because (a) the state space (partial programs, intermediate outputs) can be represented, (b) the action space (adding lines, editing functions) is defined, and (c) test suites provide ground-truth reward signals for training $f_\theta$. A concrete experiment would target competitive programming problems (e.g., from Codeforces or APPS) where the goal is to produce a program that passes hidden test cases. The MCTS state would be the current partial program and any intermediate execution results; actions would be token-level or line-level edits; rewards would be the fraction of visible test cases passed at each compilation. The LLM would serve as both the action proposer (generating candidate edits) and the error detector (identifying which part of a failing program is wrong). The key comparison would be against pure LLM-based approaches (sampling multiple programs and selecting by test pass rate) and against MCTS without the policy/value network (random or heuristic-guided search). The open question is whether XOT's efficiency advantage on puzzles translates to code, where the state space is vastly larger and the reward signal (test pass rate) is sparser.

6. Stress-testing XOT with adversarial or out-of-distribution problems. The paper evaluates on problems drawn from the same distribution as the training data (e.g., 8-Puzzle instances solvable within 9 steps, Pocket Cube instances generated by 5 random rotations). A critical stress test would evaluate XOT on problems that are systematically harder or different from training: 8-Puzzle instances requiring 20+ steps, Pocket Cube instances scrambled with 8–10 moves, or Game of 24 problems using numbers outside the 1–13 range. This would reveal whether $f_\theta$ has learned generalizable search strategies or has overfit to the depth and difficulty characteristics of the training distribution. A negative result—catastrophic performance degradation on deeper problems—would indicate that XOT's strong results are partly an artifact of shallow problem distributions and that the approach doesn't scale to harder instances. This is particularly important because the paper's claims about "enabling LLMs to solve previously unsurmountable problems" are relative to the specific test set difficulty, not to all instances of the underlying computational problem (8-Puzzle and Pocket Cube are NP-complete in their generalized forms).

Practical Applications and Downstream Use Cases

1. Automated puzzle and game solving for educational technology. The paper's three tasks—Game of 24, 8-Puzzle, and Pocket Cube—are directly relevant to educational applications that teach mathematical reasoning, spatial planning, and systematic problem-solving. A tutoring system built on XOT could demonstrate not just the correct answer but the thought process (the MCTS-generated trajectory) that leads to it, helping students understand how to approach similar problems. The multi-solution capability (Tables 4, 6, 8) is particularly valuable here: a tutor could show multiple valid solution paths, illustrating that complex problems often have more than one correct approach. The efficiency numbers matter for real-time interactivity—XOT's ~1.5–2.3 LLM calls per problem (vs. 40–57 for ToT) make it feasible to generate solutions with low enough latency for a responsive tutoring interface. A deployment would pre-train $f_\theta$ on a large bank of problems offline, then serve real-time solutions to students with minimal LLM inference cost.

2. Planning and scheduling systems with well-defined state spaces. Many industrial planning problems—job shop scheduling, vehicle routing, resource allocation—share the structural properties that make XOT effective: discrete state spaces, defined action sets, and computable cost/reward functions. In a logistics setting, the state would represent current package locations and vehicle positions, actions would be routing decisions, and rewards would be negative delivery time or cost. The MCTS module with a trained $f_\theta$ could explore the scheduling space efficiently, generating candidate plans that an LLM then reviews for feasibility (e.g., "does this route respect driver hours regulations?" or "is this delivery sequence physically possible given loading constraints?"). The key advantage over pure OR/SAT solvers is the LLM's ability to incorporate soft constraints and common-sense knowledge that are difficult to formalize. The key advantage over pure LLM approaches (as ToT/GoT on 8-Puzzle showed) is that systematic search reliably finds solutions that LLM-based exploration misses entirely. The paper's demonstration that even simple MLPs can learn effective search heuristics for NP-complete problems (8-Puzzle, Pocket Cube) suggests that similar approaches could work for industrially relevant NP-hard problems, provided a simulator exists for training.

3. Verification and debugging pipelines for structured outputs. XOT's revision loop—LLM identifies errors, MCTS re-searches from the error point—maps naturally to debugging workflows where a system produces a structured artifact (a program, a proof, a plan) and an LLM reviews it for correctness. In a code review setting, an automated system could generate candidate patches for a bug through MCTS search over edit actions, present the patched code to an LLM for review, and iterate if the LLM identifies remaining issues. The paper's results on the incomplete thought ablation (Table 11) are cautionary but informative: when MCTS output is significantly flawed (missing the last step), the LLM cannot salvage it alone. This suggests that such a system would need the MCTS module to produce "close enough" candidates—the LLM is a corrector, not a generator. The training cost (~3,000 forward passes through a tiny MLP per task) is negligible compared to the cost of LLM-based debugging (which might require dozens of calls per bug), making the approach economically attractive for high-volume debugging pipelines.

4. Game AI and simulation-based testing environments. XOT's architecture—MCTS with learned policy/value networks plus LLM verification—is directly applicable to game-playing agents where the game rules are known and a simulator exists. Beyond the toy puzzles in the paper, this could extend to more complex games (e.g., Sokoban, Rush Hour, non-trivial chess endgames) where optimal play requires lookahead search that LLMs cannot perform internally. The LLM's role would shift from post-hoc verification to strategic guidance—proposing high-level plans ("try to clear the top-right corner first") that the MCTS module then operationalizes through search. This hybrid architecture could outperform both pure MCTS (which lacks strategic insight) and pure LLM approaches (which lack systematic lookahead) on games requiring both long-term strategy and tactical precision. The paper's results on Pocket Cube and 8-Puzzle—where LLM revision added 30–40 percentage points over standalone MCTS—provide initial evidence that this hybrid approach is viable.