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:
- 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.
- 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.
- 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.
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.
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