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

May 22, 2026

SkillOpt: Executive Strategy for Self-Evolving Agent Skills

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

Yifan Yang, Ziyang Gong, Weiquan Huang +12

Microsoft · Shanghai Jiao Tong University · Tongji University +1

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

Ask PDF

Sep 17, 2026

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

External skills provide domain knowledge and procedures without updating model parameters, but flat collections obscure skill applicability, dependencies, and composition. Graphs organize skills into addressable nodes and explicit relations, supporting selection and composition. Yet existing skill-graph methods use this structure mainly for retrieval, rather than to localize updates, scope retesting, or precisely roll back rejected changes. We introduce GRAPHSKILLAA (GraphSkill Abductive Attribution), which uses one addressable graph for skill selection, execution, failure attribution, targeted updating, validation, and rollback. Nodes separate applicability, execution, and exclusion conditions; typed edges encode prerequisite and enhancement relations. The frozen student records used nodes and edges, while the teacher contrasts related successes and failures to route each supported repair to the smallest relevant field or relation; execution lapses or insufficient evidence leave the graph unchanged. A Local Gate retests affected examples, while a Big Gate evaluates the merged graph on the complete update pool; rejected changes are rolled back. With GPT-5.6-sol, GRAPHSKILLAA reaches 81.5%, 66.7%, and 91.2% on SearchQA, LiveMath, and DocVQA, respectively, and attains the highest observed mean in every main setting. These results show that object-level attribution and graph-scoped validation make a skill graph a locally optimizable, testable, and reversible external state.

Ziqiao Shang, Ling-Yue Ge, Lan-Zhe Guo

National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China · School of Intelligence Science and Technology, Nanjing University, Suzhou, China

Knowledge Augmentation for Language Models LLM Agent Skill Learning

Ask PDF

Oct 14, 2026

SkillNEO: Non-Elitist Evolutionary Optimization of Agent Skills

Agent skills turn procedural knowledge into reusable artifacts, allowing LLM agents to accumulate and refine expertise through experience. Building on this, skill evolution iteratively improves skills using execution feedback. However, improvement may require several interdependent edits, so low-reward versions can still be worth developing. Requiring immediate reward gains can discard useful partial repairs before their benefits emerge. Non-elitist evolution allows new versions to receive further edits despite scoring below earlier ones. For agent skills, this calls for evidence of what to preserve and repair next. We introduce SkillNEO (Non-Elitist Evolutionary Optimization for Agent Skills), which separately selects a version to use and versions to keep improving. Comparing how related versions perform the same task reveals working steps to preserve and remaining failures to fix. It can also revisit and revise earlier versions using later evidence. Across 86 SkillsBench tasks in eight domains, including software engineering and office work, SkillNEO raises GPT-5.4 Mini's average reward from 49.1% to 66.4%, within GPT-5.5 and GPT-5.6 Luna's original-skill range. Mini executes tasks, proposes revisions, and edits skills; final evaluation uses the same task instances. Gains span all eight domains. The same skills improve stronger models without further editing. On the 41 tasks with modified skills, reuse improves Luna by 10.5 percentage points and places GPT-5.5 10.6 points above its published original-skill reference. Execution records show these skills can benefit stronger models even when Mini still fails some task requirements. Search histories also show lower-scoring versions leading to skills ultimately selected for use. Together, these findings show that skill evolution can turn a weaker model's partial progress into reusable procedural knowledge for improving more capable agents.

Enze Ma, Chunyu Miao, Yankai Chen +14

University of Illinois at Chicago · Mohamed bin Zayed University of Artiﬁcial Intelligence · Independent Researcher +3

LLM Agent Skill Learning LLM Agent Self-Improvement Evolutionary Optimization

Ask PDF

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