智能体
arxiv.org ·
HyperMCTS：面向长时程 LLM 智能体的超图增强 MCTS
该论文提出 HyperMCTS，一种免训练方法，在有序 MCTS 树上叠加跨轨迹超图：超边表示规范决策组并累积当前任务内的观测回报，HyperUCT 选择规则将重叠超边的证据聚合为动作先验，使某一前缀下收集的结果可指导另一前缀下的选择，同时保留树中的执行历史。在 DeepPlanning 上，该方法对三个骨干模型的平均规划准确率较最强基线提升 2.3–7.3 个百分点，并使 Qwen3.6-27B 在 Shopping Planning 上超过 Claude Opus 4.6 (max)，同时 LLM 调用次数与输出 token 少于所评估的 MCTS 基线；SealQA 实验也显示问答性能提升。
AI推荐理由 arXiv 新论文，提出免训练的 HyperMCTS，用跨轨迹超图增强有序 MCTS 树，通过 HyperUCT 选择规则把不同前缀下收集的决策回报聚合为动作先验，从而复用轨迹反馈。摘要给出具体量化结果：在 DeepPlanning 上对三个骨干模型平均规划准确率提升 2.3–7.3 个百分点，使 Qwen3.6-27B 在 Shopping Planning 上超过 Claude Opus 4.6 (max)，且 LLM 调用与输出 token 少于所评估的 MCTS 基线，SealQA 上也有提升。信息密度高、方法明确，对长时程 LLM Agent 的测试时扩展有参考价值；局限是仅基于摘要，尚无第三方复现，且对比基线范围有限。
78
正文
Computer Science > Artificial Intelligence
arXiv:2609.33920 (cs)
[Submitted on 27 Sep 2026]
Title:HyperMCTS: Hypergraph-Augmented MCTS for Long-Horizon LLM Agents
Authors:Tingsong Xiao, Nithish Balachandar Moudhgalya, Chandrayee Basu, Lichao Wang, Luyang Kong, Benjamin Z. Yao, Zhe Jiang, Jie Hao
View a PDF of the paper titled HyperMCTS: Hypergraph-Augmented MCTS for Long-Horizon LLM Agents, by Tingsong Xiao and 7 other authors
View PDF
HTML (experimental)
Abstract:Long-horizon tasks require large language model (LLM) agents to coordinate decisions under constraints that span an entire solution. Monte Carlo Tree Search (MCTS) offers a promising approach to test-time scaling by exploring alternative action trajectories, but model computation and environment interaction make search costly. Efficient search therefore requires effective reuse of trajectory feedback. Standard MCTS maintains prefix-specific statistics, without explicitly accumulating outcomes for decision groups that recur across different paths. To fill this gap, we propose HyperMCTS, a training-free method that augments an ordered MCTS tree with a cross-trajectory hypergraph. Hyperedges represent groups of canonical decisions and accumulate their observed returns within the current task. Our hypergraph-guided HyperUCT selection rule aggregates evidence from overlapping hyperedges into an action prior, allowing outcomes collected under one prefix to inform selection under another while preserving execution histories in the tree. On DeepPlanning, HyperMCTS improves average planning accuracy by 2.3--7.3 percentage points over the strongest baseline for each of three backbone models. It enables Qwen3.6-27B to outperform Claude Opus 4.6 (max) on Shopping Planning, while achieving higher accuracy with fewer LLM calls and output tokens than the evaluated MCTS-based baselines. SealQA experiments further demonstrate improvements in question answering.
Subjects:
Artificial Intelligence (cs.AI)
Cite as:
arXiv:2609.33920 [cs.AI]
(or
arXiv:2609.33920v1 [cs.AI] for this version)
https://doi.org/10.48550/arXiv.2609.33920
Focus to learn more
arXiv-issued DOI via DataCite (pending registration)
Submission history
From: Tingsong Xiao [view email]
[v1]
Sun, 27 Sep 2026 20:58:40 UTC (4,992 KB)
Full-text links:
Access Paper:
View a PDF of the paper titled HyperMCTS: Hypergraph-Augmented MCTS for Long-Horizon LLM Agents, by Tingsong Xiao and 7 other authors
View PDF
HTML (experimental)
TeX Source
view license
Current browse context:
cs.AI
new
|
recent
| 2026-09
Change to browse by:
cs
References & Citations
NASA ADS
Google Scholar
Semantic Scholar
export BibTeX citation
Loading...
BibTeX formatted citation
×
loading...
Data provided by:
Bookmark
Bibliographic Tools
Bibliographic and Citation Tools
Bibliographic Explorer Toggle
Bibliographic Explorer (What is the Explorer?)
Connected Papers Toggle
Connected Papers (What is Connected Papers?)
Litmaps Toggle
Litmaps (What is Litmaps?)
scite.ai Toggle
scite Smart Citations (What are Smart Citations?)
Code, Data, Media
Code, Data and Media Associated with this Article
alphaXiv Toggle
alphaXiv (What is alphaXiv?)
Links to Code Toggle
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub Toggle
DagsHub (What is DagsHub?)
GotitPub Toggle
Gotit.pub (What is GotitPub?)
Huggingface Toggle
Hugging Face (What is Huggingface?)
ScienceCast Toggle
ScienceCast (What is ScienceCast?)
Demos
Demos
Replicate Toggle
Replicate (What is Replicate?)
Spaces Toggle
Hugging Face Spaces (What is Spaces?)
Spaces Toggle
TXYZ.AI (What is TXYZ.AI?)
Related Papers
Recommenders and Search Tools
Link to Influence Flower
Influence Flower (What are Influence Flowers?)
Core recommender toggle
CORE Recommender (What is CORE?)
Author
Venue
Institution
Topic
About arXivLabs
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Which authors of this paper are endorsers? |
Disable MathJax (What is MathJax?)