CompSkill: Compiling Execution Experience for Skill Retrieval

Qi Shen, Ziyue Zhu, Yongqing Jiang, Zhen Xia, Li Shengjie, Shuai Zhao, Bo Cheng, Xiaobao Wu, Anh Tuan Luu, Haoran LuoarXiv 2026 · arXiv

TL;DR

CompSkill is a new framework that teaches LLM agents to retrieve the "skills" (documentation or API guides) that actually lead to success, rather than just those that sound relevant. By "compiling" past execution experience into compact, editable retrieval keys, it significantly improves agent performance on complex tasks while reducing storage and latency.

What Problem Does This Paper Address?

Large Language Model (LLM) agents typically solve tasks by retrieving "skills"—documents that explain how to use a specific API or database. Standard retrieval systems (like RAG) rely on semantic similarity: they rank documents based on how well their descriptions match the user's query.

However, the authors point out a critical gap: a skill that sounds perfectly relevant can actually cause an agent to fail. For example, a guide for "single-record lookup" might be a top semantic match for a query about "average prices," but if the agent follows it, it will fail to perform the necessary aggregation. Current retrievers ignore these execution outcomes, leading to "near-miss" errors where the agent chooses a "sibling" guide (one for the same database but the wrong procedure) that induces hallucinations or execution failure.

Methods

CompSkill introduces an architecture that learns from experience without needing to retrain the underlying LLM or edit the skill documents themselves. It consists of three main components:

  1. Compact Semantic Indexing: It compresses high-dimensional embeddings (4096-d) into learned 512-d keys. This not only makes retrieval 3.5x faster and 8x smaller in storage but also creates a space where "relevance" can be fine-tuned based on outcomes.
  2. Matched Feedback Calibration (KeyOpt): This is the system's "brain." It looks at "matched comparisons"—instances where the same executor tried two different skills on the same task. By focusing on discordant pairs (where one skill worked and the other didn't), it learns to adjust retrieval scores. It calculates a reliability offset ($\beta$) and a query-conditional residual ($\Delta k$) to nudge the retriever toward skills that historically work for that specific executor.
  3. Experience Hypergraph: This component stores past execution events as hyperedges. It allows the system to perform "conditional recall"—finding useful skills that semantic search missed—and provides evidence to a "Cited Reviewer" (a frozen LLM) that double-checks the final selection against past successes.
Figure 3: CompSkill links compact keys, KeyOpt calibration, attributed hypergraph evidence and native execution; cited review selects an original document and the bottom loop updates only from support tasks. The center shows how a query reads one key and what experience writes into each part (Recall@10 inset: SRA library).

Datasets

The authors evaluated CompSkill across several diverse benchmarks:

  • SkillRet: A large-scale benchmark for skill retrieval.
  • ToolQA: A challenging dataset for question answering using external tools. The authors generated 332 new tasks to test generalization.
  • AppWorld: A benchmark for interactive coding agents in a simulated digital world.
  • ALFWorld: A text-based environment for embodied agents.

Key Insights and Ideas

  • Discordance is the Signal: The authors prove that in a world of varying task difficulty, "concordant" outcomes (where both skills fail or both succeed) tell you nothing about skill utility—they only reflect task ease. Only discordant pairs provide the signal needed to calibrate a retriever.
  • Selection Matters More Than Volume: On ToolQA, supplying just one correct document via CompSkill outperformed supplying four documents via standard vector search. In fact, adding a "sibling" guide (a near-miss) often hurts performance more than adding a completely unrelated document because it confuses the agent.
  • Calibration Transfers: Interestingly, calibration fits learned on one model (e.g., GPT-5.5) transferred effectively to a newer version (GPT-5.6-luna) without refitting, suggesting that execution utility is somewhat consistent across model families.
Figure 2: Three challenges, CompSkill components and empirical evidence: SkillRet Recall@10 (compact keys: three-seed mean), a ToolQA Coffee ranking example, GPT-5.6-luna Hit@1 on the 332 ToolQA evaluation tasks, and paired review outcomes (9 wins, 3 losses) on the 332 newly generated tasks.

Key Results

  • Superior Accuracy: On ToolQA, CompSkill completed 256/332 tasks (GPT-5.6-luna), significantly outperforming strong baselines like BM25, Tool2Vec, and RankGPT.
  • Efficiency Gains: The 512-d compact keys raised SkillRet NDCG@10 from 64.0 to 70.9 while being 8x smaller and 3.5x faster to look up than native 4096-d vectors.
  • Generalization: Over a total of 844 ToolQA tasks, CompSkill completed 24 more tasks than the strongest baseline, proving its robustness across different task sets.

Limitations and Future Work

  • Data Requirements: KeyOpt requires "support runs" (past executions) to learn. If an environment is so easy that every skill works, or so hard that none do, there is no "discordance" to learn from.
  • Reviewer Overhead: The "Cited Review" step adds one LLM call per task, which, while grounded in evidence, increases the computational cost compared to pure vector lookup.
  • Future Directions: The authors suggest moving toward online learning (updating keys in real-time) and operation-level indexing, where skills are retrieved based on the specific tool operations (like "cumulative filtering") they enable.

Summary updated

Abstract

LLM agents increasingly rely on skill documents, yet most retrievers rank them by description alone and ignore what earlier executions revealed, even though a relevant skill can hurt execution. We present CompSkill, which indexes skills with learned 512-d keys and compiles matched same-task comparisons into skill offsets and capped key residuals (KeyOpt), so experience changes which document the executor receives, never its text. Under a logistic outcome model with unknown task difficulty, matched comparisons cancel that difficulty and only discordant ones carry information; on support executions, predictions improve with each discordant task. An experience hypergraph keeps each comparison with its executor and document versions, recalls missed skills and grounds a cited review. Compact keys raise SkillRet NDCG@10 from 64.0 to 70.9 at one eighth of the dimension. With one document, CompSkill completes 256 and 260 of 332 ToolQA tasks with GPT-5.6-luna and DeepSeek-V4.1-Flash, respectively, more than every baseline, and stays on par with the strongest baselines on AppWorld and ALFWorld. On 332 newly generated ToolQA tasks, it completes 256 with GPT-5.6-luna, significantly more than BM25, SkillRet-8B, Tool2Vec and RankGPT; over all 844 ToolQA tasks, it completes 24 more than the strongest baseline. Selection matters beyond relevance: pairing the right guide with a same-database sibling instead of another database's guide costs 8 of 96 tasks. Code, models and support data: https://github.com/satoshinji2992/CompSkill
BibTeX
@misc{shen2026compskill,
  author = {Qi Shen and Ziyue Zhu and Yongqing Jiang and Zhen Xia and Li Shengjie and Shuai Zhao and Bo Cheng and Xiaobao Wu and Anh Tuan Luu and Haoran Luo},
  title = {{CompSkill: Compiling Execution Experience for Skill Retrieval}},
  year = {2026},
  eprint = {2611.01115},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01115},
}
Figure