TsuGO: Probing Search Efficiency in LLM Reasoning via Go Life-and-Death Problems

• URL: http://arxiv.org/abs/2608.13221v1
• Date: Thu, 13 Aug 2026 13:24:47 GMT
• Title: TsuGO: Probing Search Efficiency in LLM Reasoning via Go Life-and-Death Problems
• Abstract summary: We introduce TsuGO, a process-level reasoning benchmark for evaluating Search Efficiency in LLM reasoning through Go life-and-death problems.<n>These problems provide closed and verifiable solution spaces with an inherent adversarial structure, making candidate generation, response checking, branch comparison, and backtracking necessary parts of reasoning rather than incidental trace patterns.<n>By constraining the solution space, TsuGO disentangles domain knowledge from search organization, parses CoT into a structured search tree, and reports Search Efficiency together with Token Efficiency and other diagnostic metrics and visualizations.
• Score: 18.691569868742754
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The evaluation of LLM reasoning is moving from final-answer accuracy to process-level assessment, yet existing methods still fail to capture how models plan reasoning paths and allocate reasoning resources--that is, how they organize search. Prior process-level methods focus on the coherence and redundancy of chain-of-thought (CoT), and most benchmark tasks have a single objective solvable by static capabilities such as derivation and tool use, leaving search organization unmeasured. We introduce TsuGO, a process-level reasoning benchmark for evaluating Search Efficiency in LLM reasoning through Go life-and-death problems. These problems provide closed and verifiable solution spaces with an inherent adversarial structure, making candidate generation, response checking, branch comparison, and backtracking necessary parts of reasoning rather than incidental trace patterns. By constraining the solution space, TsuGO disentangles domain knowledge from search organization, parses CoT into a structured search tree, and reports Search Efficiency together with Token Efficiency and other diagnostic metrics and visualizations. Experiments show that current LLMs remain far from stable tsumego solving: stronger models succeed by finding the correct candidate earlier and sustaining effort on productive branches, but most models still behave much closer to unguided search algorithms than to neural-guided KataGo. Longer CoT or higher Token Efficiency does not necessarily imply better search. Our results identify search organization and reasoning-resource allocation as missing dimensions in LLM reasoning evaluation.

Related papers

• Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces [63.82675722580452]
  OPT* is a family of optimization-style tasks for training and evaluating LLM step-by-step optimization-like reasoning.<n>Each task provides a feasibility checker and evaluator, while a complexity parameter expands the search space without requiring new human labels.<n>We show that training on OPT* improves step-by-step optimization-like reasoning.
  arXiv  Detail & Related papers  (2026-06-03T21:43:38Z)
• LinTree: Improving LLM Reasoning with Explicitly Structured Search Histories [38.39348916777905]
  Large language models (LLMs) often solve reasoning problems by generating intermediate traces that explore and revise partial solutions.<n>From a search perspective, these traces can be viewed as linearized search trees, where the model extends a partial solution and backtracks to try alternatives.<n>We show that adding simple parent pointers to explicitly represent the linearized tree (LinTree) structure improves both task efficiency relative to implicit reasoning models and LLM-heuristic-guided search.
  arXiv  Detail & Related papers  (2026-05-29T16:13:19Z)
• Reinforced Efficient Reasoning via Semantically Diverse Exploration [73.41112984160992]
  Reinforcement learning with verifiable rewards (RLVR) has proven effective in enhancing the reasoning of large language models (LLMs)<n>We propose reinforced efficient reasoning via semantically diverse explorations, i.e., ROSE, for LLMs.<n>Our method incorporates a semantic-entropy-based branching strategy and an $varepsilon$-exploration mechanism.
  arXiv  Detail & Related papers  (2026-01-08T15:56:44Z)
• Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries [5.268207922548829]
  We show how probabilities assigned to thoughts by Language Models (LMs) can serve as a to guide search within the ToT framework.<n>We adapt a search algorithm, Levin Tree Search (LTS), to the ToT framework.<n>These findings highlight the efficacy of LTS on ToT, particularly in enabling cost-effective and time-efficient problem-solving.
  arXiv  Detail & Related papers  (2026-01-07T05:35:16Z)
• Adaptive Test-Time Reasoning via Reward-Guided Dual-Phase Search [62.1546099504045]
  We propose a dual-phase test-time scaling framework that separates reasoning into planning and execution.<n>Specifically, we decompose reasoning trajectories and develop reward models for each phase, enabling the search to explore and prune plans and executions separately.<n> Experiments on both mathematical reasoning and code generation benchmarks demonstrate that our approach consistently improves accuracy while reducing computation redundant.
  arXiv  Detail & Related papers  (2025-09-29T19:27:23Z)
• LLM-First Search: Self-Guided Exploration of the Solution Space [29.780554400938335]
  Large Language Models (LLMs) have demonstrated remarkable improvements in reasoning and planning through increased test-time compute.<n>We propose textbfLLM-First Search (LFS), a novel textitLLM Self-Guided Search method.
  arXiv  Detail & Related papers  (2025-06-05T16:27:49Z)
• Stepwise Reasoning Checkpoint Analysis: A Test Time Scaling Method to Enhance LLMs' Reasoning [81.50681925980135]
  We propose Stepwise Reasoning Checkpoint Analysis (SRCA), a framework that introduces checkpoints between reasoning steps.<n>It incorporates two key strategies: (1) Answer-Clustered Search, which groups reasoning paths by their intermediate checkpoint answers to maintain diversity while ensuring quality, and (2) Checkpoint Candidate Augmentation, which leverages all intermediate answers for final decision-making.<n>Our approach effectively reduces path homogenization and creates a fault-tolerant mechanism by utilizing high-quality intermediate results.
  arXiv  Detail & Related papers  (2025-05-23T12:42:50Z)
• Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models [49.61246073215651]
  Large Language Models (LLMs) have demonstrated remarkable capabilities in complex tasks.<n>Recent advancements in OpenAI o1 and DeepSeek-R1 have further improved performance in System-2 reasoning domains.<n>However, they also introduce significant computational overhead due to verbose and redundant outputs.
  arXiv  Detail & Related papers  (2025-03-20T17:59:38Z)
• Token-Supervised Value Models for Enhancing Mathematical Problem-Solving Capabilities of Large Language Models [56.32800938317095]
  Existing verifiers are sub-optimal for tree search techniques at test time.<n>We propose token-supervised value models (TVMs)<n>TVMs assign each token a probability that reflects the likelihood of reaching the correct final answer.
  arXiv  Detail & Related papers  (2024-07-12T13:16:50Z)
• Chain of Preference Optimization: Improving Chain-of-Thought Reasoning in LLMs [37.147529569445396]
  Tree-of-thought (ToT) method employs tree-searching to extensively explore the reasoning space and find better reasoning paths that CoT decoding might overlook. Fine-tuning language models (LLMs) leveraging the search tree constructed by ToT allows CoT to achieve similar or better performance. This is achieved through Chain of Preference Optimization (CPO), where LLMs are fine-tuned to align each step of the CoT reasoning paths with those of ToT.
  arXiv  Detail & Related papers  (2024-06-13T14:07:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.