AtomSearch: Evidence-Grounded Tree Search for Agent Skill Optimization

Jia Tong; Senyou Deng; Min Peng; Jianfeng Pan

cs.CLOct 14, 2026

AtomSearch: Evidence-Grounded Tree Search for Agent Skill Optimization

Authors: Jia Tong, Senyou Deng, Min Peng, Jianfeng Pan

Organizations: Security Technology Inc. Beijing, China

Abstract

Agent skills adapt frozen models through editable external instructions. Revising several rules at once makes changes difficult to inspect, while judging each local edit only by its immediate score can discard useful intermediate states. We introduce AtomSearch, which keeps revision actions local while using subsequent skill states to guide search. Contrastive atomic editing links each primitive rule edit to failed and successful executions, a behavioral hypothesis, and an intended scope. Skill-State Tree Search (STS) evaluates short edit compositions and selectively retains them as executable states that can be revisited and extended. Outcome memory supplies later proposals with observed repair and regression statistics. We evaluate AtomSearch across four tasks and five target models. With deepseek-v4-flash, it exceeds SkillOpt on three of four tasks, including a 9.68-percentage-point gain on LiveMathematicianBench, and SkillOpt's final skills contain 2.3-19.7 times as many characters. In 67% of completed searches, the best validation state passes through an ancestor that was not highest-scoring at its depth. These results show how local rule edits can support the exploration of useful revision paths and yield compact skills, with additional offline evaluations used to explore alternative states.

Figures & tables

Figure 1: Overview of AtomSearch. Contrastive atomic editing (top) contrasts failed and passed executions into edit specifications and ranked primitive edits. Skill-State Tree Search (left and bottom) applies the top-ranked edit at the node selected by UCT, also scores a short lookahead with up to two further edits, keeps the lookahead only if it beats the primitive child, and backs up the kept state’s reward. Outcome memory (right) records repairs and regressions per edit for later proposals; its counts are schematic.

Figure 2: A contrastive atomic edit from SpreadsheetBench. Failed and successful executions are contrasted into one edit specification, and the resulting add edit cites it through criterion_id . Sample IDs are SpreadsheetBench task IDs. Pattern summaries and specification fields are condensed from the recorded proposal; the added rule is paraphrased. The observed gain is on the 40-item validation panel.

Target model	Method	NDR	Spread.	SearchQA	LiveMath
GPT-5.5	SkillOpt	73.00	77.50	87.10	61.30
	AtomSearch	71.00	79.64	85.57	65.32
deepseek-v4-flash	SkillOpt	65.00	68.93	83.29	42.74
	AtomSearch	71.00	78.21	80.64	52.42
GPT-5.2	SkillOpt	66.00	57.10	83.10	36.00
	AtomSearch	72.00	57.50	82.50	41.13

Table 1: Test scores (%) across target models and tasks. Bold marks the higher score within each pair, including ties.

Task / target	$\Delta_{\mathrm{val}}$	$\Delta_{\mathrm{test}}$	$R$	$\Delta_{\mathrm{val}}$	$\Delta_{\mathrm{test}}$	$R$
	AtomSearch			SkillOpt
Spreadsheet / deepseek	42.50	38.21	90%	42.50	30.00	71%
NDR / deepseek	11.43	15.00	131%	13.33	12.00	90%
NDR / GPT-5.2	20.00	27.00	135%	20.95	20.00	95%
NDR / GPT-5.5	24.13	20.00	83%	29.52	24.00	81%
NDR / Qwen3.5-4B	12.38	20.00	162%	18.10	15.00	83%

Table 2: Validation and test gains over each run’s recorded initial skill (percentage points).

R

is the test gain divided by the validation gain, expressed as a percentage; it is not an accuracy. Ratios and medians are computed before rounding. Bold marks the larger

\Delta_{\mathrm{test}}

and the larger

R

within each pair.

Figure 3: Revision trajectories on shared validation panels. AtomSearch counts edits only along the displayed root-to-validation-argmax path, while SkillOpt follows its incumbent skill chain. All points are single recorded evaluations. Both paths include a score decrease before reaching their maxima. Edit counts exclude candidates explored off the displayed path.

Contrastive atomic editing	Skill-State Tree Search	Outcome memory	Test (%)	Characters
–	–	–	68.93	16,536
$\mathchar 0\symAMSa 058$	–	–	75.71	2,352
$\mathchar 0\symAMSa 058$	$\mathchar 0\symAMSa 058$	–	77.14	2,755
$\mathchar 0\symAMSa 058$	$\mathchar 0\symAMSa 058$	$\mathchar 0\symAMSa 058$	78.21	2,936

Table 3: Cumulative ablation on SpreadsheetBench with deepseek-v4-flash. The first row is Base, the SkillOpt run reported in Table 1 ; each later row adds one component, and the last row is full AtomSearch, whose final skill is the one reported in Table 1 . The initial skill has 1,594 characters. Bold marks the highest test score.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	Learn	Validation	Test	Minibatch
NDR	100	105	100	35
SpreadsheetBench	80	40	280	27
SearchQA	400	200	1400	134
LiveMath	35	18	124	12

Appendix

Table 4: Split sizes (items) and contrastive minibatch size per benchmark. Minibatches use approximately one third of the learn set. LiveMath: LiveMathematicianBench.

Target	Benchmark	Attempts	Item evals.	Optimizer calls	Cache hit rate
deepseek-v4-flash	NDR	20	4,345	16	65%
	SpreadsheetBench	30	3,360	29	64%
	SearchQA	20	10,600	19	64%
	LiveMath	20	923	19	65%
GPT-5.5	NDR	20	6,865	20	60%
	SearchQA	30	17,200	35	65%

Appendix

Table 5: Cost of 17 documented AtomSearch runs. Item evaluations are charged to the budget and are not necessarily individual API requests; cache hit rate is the share of evaluation requests served from the cache. LiveMath: LiveMathematicianBench.

LLM Agent Skill Learning

Large language model agent skill learning studies how agents acquire, represent, reuse, and refine procedures for multi-step tasks.

See all 398 papers

SkillOpt: Executive Strategy for Self-Evolving Agent Skills
May 22, 2026Yifan Yang, Ziyang Gong, Weiquan Huang +12Large Language Model-Guided Optimization LLM Agent Self-Improvement
Microsoft · Shanghai Jiao Tong University · Tongji University +1
GraphSkillAA: Attribution-Guided Skill-Graph Updating with Targeted Validation and Rollback
Sep 17, 2026Ziqiao Shang, Ling-Yue Ge, Lan-Zhe GuoKnowledge Augmentation for Language Models LLM Agent Skill Learning
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China · School of Intelligence Science and Technology, Nanjing University, Suzhou, China
SkillNEO: Non-Elitist Evolutionary Optimization of Agent Skills
Oct 14, 2026Enze Ma, Chunyu Miao, Yankai Chen +14LLM Agent Skill Learning LLM Agent Self-Improvement
University of Illinois at Chicago · Mohamed bin Zayed University of Artiﬁcial Intelligence · Independent Researcher +3

May 22, 2026J/K move · Enter open · S save

SkillOpt: Executive Strategy for Self-Evolving Agent Skills

Yifan Yang, Ziyang Gong, Weiquan Huang, Qihao Yang+11

Microsoft · Shanghai Jiao Tong University · Tongji University+1

Large Language Model-Guided Optimization LLM Agent Self-Improvement Agent Skill Learning

Open paper AskPDF arXiv

Agent skills today are hand-crafted, generated one-shot, or evolved through loosely controlled self-revision, none of which behaves like a deep-learning optimizer for the skill, and none of which reliably improves over its starting point under feedback. We argue the skill should instead be trained as the external state of a frozen agent, with the same discipline that makes weight-space optimization reproducible. SkillOpt is, to our knowledge, the first systematic controllable text-space optimizer for agent skills: a separate optimizer model turns scored rollouts into bounded add/delete/replace edits on a single skill document, and an edit is accepted only when it strictly improves a held-out validation score. A textual learning-rate budget, rejected-edit buffer, and epoch-wise slow/meta update make skill training stable while adding zero inference-time model calls at deployment. Across six benchmarks, seven target models, and three execution harnesses (direct chat, Codex, Claude Code), SkillOpt is best or tied on all 52 evaluated (model, benchmark, harness) cells and beats every per-cell competitor among human, one-shot LLM, Trace2Skill, TextGrad, GEPA, and EvoSkill skills. On GPT-5.5 it lifts the average no-skill accuracy by +23.5 points in direct chat, by +24.8 inside the Codex agentic loop, and by +19.1 inside Claude Code. Transfer experiments further show that optimized skill artifacts retain value when moved across model scales, between Codex and Claude Code execution environments, and to a nearby math benchmark without further optimization. Code: https://aka.ms/skillopt

Abstract

LLM Agent Skill Learning

Explore similar work

SkillOpt: Executive Strategy for Self-Evolving Agent Skills

GraphSkillAA: Attribution-Guided Skill-Graph Updating with Targeted Validation and Rollback

SkillNEO: Non-Elitist Evolutionary Optimization of Agent Skills