SkillZip: Evaluation-Free Skill Compression for Self-Evolving Agents by Discovering Reusable Structure

SkillZip: Evaluation-Free Skill Compression for Self-Evolving Agents by Discovering Reusable Structure

Abstract Summary

The paper addresses the problem of skill bloat in self-evolving agents. These agents accumulate reusable skills by appending successful procedures and failure fixes, but over time, the same requirements are restated in multiple branches, examples, and warnings, while common action sequences are copied rather than reused. This makes the skill expensive to inject and difficult to maintain. Generic prompt compression is ill-suited because a skill is not a flat passage: its name and description define when it applies, its workflow controls execution, its tool and output contracts constrain validity, and rare exceptions may remain essential even when no sampled task activates them. Evaluation-guided compression can test these behaviors but introduces rollouts, cost, and dependence on the compression-time evaluation set.

The paper presents SkillZip, an evaluation-free method that compresses a skill by finding its shortest faithful structural explanation. The intuition is explain once, reference many: state a repeated rule once at the scope where it applies, factor a repeated action sequence into a shared procedure, and keep only the differences as explicit exceptions. This is formalized as a typed minimum-description-length objective over a skill contract and a residual, subject to a hard coverage constraint for every extracted trigger, workflow edge, tool requirement, obligation, and output field. The formulation provides simple sharing thresholds, preserves unique rare rules by construction, and supports efficient local updates. SkillZip has a one-shot mode with one structured extraction call and deterministic optimization, and a continual Zip-on-Write mode that integrates each self-evolution patch without replaying tasks or reparsing the full history. Comprehensive experimental evaluations demonstrate the effectiveness and superiority of SkillZip in compression performance, generalizability, and cost overhead.

Introduction Summary

The paper notes that a self-evolving agent improves by turning experience into reusable instructions. When a tool fails, it appends a warning; when an answer violates a format, it adds an example; when a rare branch succeeds, it records the successful procedure. Each update is locally reasonable, but the accumulated skill is usually edited as an append-only notebook rather than maintained as a coherent program. After enough rounds, never overwrite the source file may appear in the introduction, three workflow branches, and an example, while the same validate–repair–verify sequence is copied repeatedly with only minor differences.

This creates a systematic mismatch between textual growth and procedural growth. New text keeps accumulating even after the number of genuinely new requirements begins to saturate. Because a loaded skill occupies the context on every invocation, redundant text increases prefill cost and can obscure the instructions that actually govern execution. Figure 1 illustrates this phenomenon.

The paper distinguishes between different types of long skills. A conventional one-shot or community-authored skill can mix operational rules with background exposition, templates, examples, or even content unrelated to execution; deleting or deferring such material is often appropriate. A multi-round evolved skill is different. Recent systems accept bounded edits only after rollout feedback or validation, or aggregate recurrent successful and failed trajectories into updates. Its additional text is therefore usually more knowledge-dense: even a singleton warning may encode an expensive failure that the agent learned to avoid. The main redundancy is less often irrelevant topic and more often repeated representation—the same invariant copied into several branches, a workflow restated after each failure, or a general rule followed by progressively narrower exceptions. This distinction changes the compression goal from content filtering to knowledge consolidating.

The paper argues that prompt compression is the wrong abstraction. Prompt compressors typically decide which tokens are useful for a current query or likely answer, while skills should be reusable for all queries of certain tasks. More importantly, its meaning is not distributed uniformly across words. The name and description determine when the skill is selected; temporal phrases determine action order; tool arguments define valid calls; branch guards determine where a rule applies; and an output schema defines when the procedure is complete. A rare exception may be activated only once, yet deleting it can be more damaging than removing several paragraphs of rationale. Task-based validation is also not a complete solution. SkillReducer demonstrates that structure-aware rewriting and progressive disclosure can reduce skill cost, and its feedback loop uses generated tasks to recover missed content. Such validation is valuable, but it makes compression expensive and couples the compressed results to compression-time tasks. A method can repeatedly repair the branches observed by that set while still losing an untested guard or output constraint.

The paper asks a stricter question: Can a skill be shortened using only the structure already present in the skill, without observing tasks, rewards, trajectories, or verifiers?

The answer begins with a simple observation: a skill resembles a compact operating manual more than a generic prompt. It contains an interface (name, purpose, triggers, exclusions), a procedure (steps, branches, loops, fallbacks), contracts for tools and outputs, and rules whose scope can be global or branch-specific. This structure reveals redundancy that token importance cannot see. A rule repeated in every branch can be stated once before the branch. A repeated action sequence can be named once and reused. Several guarded variants can be written as one common rule plus explicit exceptions. Conversely, a unique requirement cannot be removed merely because it is short or rare.

The key compression principle of SkillZip is: prefer the shortest faithful explanation of the skill. Informally, the compressed representation pays once for every shared structure and pays separately only for genuine differences. This is the same intuition as replacing three copies of a code fragment by one function and three calls. Formally, it is an instance of minimum description length (MDL): minimize the cost of a compact skill contract plus the cost of the source details not explained by that contract, while requiring every extracted normative requirement to remain covered.

The paper designs two modes. One-shot SkillZip compresses an existing evolved skill checkpoint with one structured extraction call followed by deterministic optimization. Zip-on-Write participates in self-evolution: when a new self-evolution patch arrives, SkillZip compares it only with compatible parts of the current compact contract, then either absorbs it, refines an existing rule, adds a new requirement, or triggers a local refactoring. Periodic repacking captures patterns that become reusable only after several updates.

The main contributions are:

• Formulating evaluation-free skill compression as contract representation tailored for evolved skills.

• Deriving a shortest faithful explanation objective that unifies semantic sharing, scope lifting, workflow reuse, and exception encoding. A hard coverage constraint gives a rare-rule preservation guarantee independent of task frequency.

• Designing one-shot SkillZip and Zip-on-Write. The first uses one structured extraction call followed by deterministic optimization; the second maintains a compact state during self-evolution and avoids replaying tasks or reparsing the full history.

• Performing comprehensive empirical evaluations showing that SkillZip delivers substantial gains in compression performance, robust generalizability, and low cost overhead.

Related Work Summary

The paper reviews related work in four areas:

1. Self-Evolving Agents and Persistent Skills: Agents increasingly convert interaction experience into reflections, memories, programs, or reusable skills. Systems such as ACE, SkillRL, and SkillClaw explicitly maintain and evolve persistent skill artifacts across tasks or users; SkillRevise and SkillGrad use execution traces to diagnose and improve an existing skill. These works focus on how procedural knowledge is acquired. As the artifact grows, acquisition and maintenance become different problems: a useful new patch can still duplicate an old invariant or repeat an existing workflow. SkillZip addresses this consolidation problem without replaying the experiences that produced the skill.

2. Prompt and Context Compression: Prompt compression prunes or rewrites context using perplexity, query relevance, learned token labels, summarization, or latent representations. These techniques usually treat input as a sequence whose importance is estimated relative to a query, answer, or representative task distribution. Skills violate both assumptions: future tasks are unknown, and procedural meaning depends on typed relations such as before, branch guards, tool arguments, and required output fields. Query-conditioned compression may be effective for a single request, but a reusable skill must retain requirements that no compression-time query activates. SkillZip therefore compresses repeated procedural structure rather than low-salience tokens.

3. Skill Compression and Efficient Execution: SkillReducer is the closest textual baseline. It minimizes routing descriptions with delta debugging, classifies body content, moves supplementary material to on-demand references, and uses faithfulness checks and task-based feedback. It establishes that skill content should not be treated as homogeneous text and is especially well matched to ordinary skills that contain background, examples, and reference material. Multi-round evolved skills present a complementary regime: accepted updates are often operationally relevant, while redundancy appears as repeated constraints, overlapping workflows, and accumulated exceptions. SkillReducer's generated tasks and feedback loop participate directly in candidate selection. Repeatedly tuning an artifact on a finite evaluation sample can create sample-specific selection effects. SkillZip removes this source of dependence by never exposing compression to tasks, and it keeps a single portable text skill rather than changing the loading architecture. SKIM and TokMem encode procedural knowledge into learned soft or memory tokens, while Skill-to-LoRA transfers a textual skill into model parameters. Their representations can be compact, but they are model-dependent and less convenient to inspect, diff, or update during continual evolution. SkillZip uses a structured sidecar only while maintaining the artifact and renders an ordinary human-readable skill for deployment. Skill and SkillRT treat skills as executable or compilable artifacts, supporting the premise that a skill has an interface, control flow, and contracts, not merely topical text.

4. Minimum Description Length: The MDL principle selects the model that gives the shortest joint description of a model and the data it explains. Grammar-based methods such as SEQUITUR and Re-Pair similarly replace repeated subsequences with reusable rules. SkillZip adopts this intuitive principle—a shared explanation is useful when defining it once and referencing it is cheaper than repeating it—and adapts it to typed procedural knowledge. Unlike sequence compression, the objective may not merge identical-looking clauses if they occur under incompatible guards, and it may not delete a unique rule even when that rule has zero repetition. The hard coverage is therefore as important as the skill length.

From Skill Text to a Compact Contract Summary

The paper defines evaluation-free compression: Let S be one textual skill and Se its compressed form. During compression, a method may read S, files referenced by S, and—in the continual setting—the sequence of skill patches. It may not access downstream tasks, execution trajectories, rewards, or behavioral verifiers. These resources are used only after compression to measure generalization. Three properties are sought: (1) Se should be substantially shorter under the deployment tokenizer; (2) it should preserve what the skill requires, including rare conditions; (3) it should remain an ordinary text artifact that can be inspected, versioned, and used by different agent backbones.

The second requirement is deliberately structural. Without running tasks, the compressor cannot prove that arbitrary natural language induces identical model behavior. It can, however, require the compressor to preserve every operational element it extracts from the source, and to retain ambiguous source spans verbatim. This makes the boundary of the guarantee explicit rather than hiding it behind a finite evaluation suite.

The paper describes the contract hidden inside a skill. Figure 2 shows the representation used by SkillZip. The extracted contract is written as:

C(S) = ⟨I, G, T, C, O, E⟩

where:

• I is the interface: skill name, purpose, positive triggers, and exclusions;

• G is the workflow: actions, order, decisions, loops, fallbacks, and stop conditions;

• T is the tool protocol: tool names, required arguments, preconditions, expected observations, and error handling;

• C is the set of scoped rules: what the agent must, must not, or preferably should do, together with the scope and guard under which each rule applies;

• O is the output contract: response type, required fields, ordering, validation, and completion conditions;

• E is supporting evidence: examples, templates, and rationale linked to the contract elements they express.

This decomposition changes which compressions are safe. Two sentences about the same tool cannot merge if they require different arguments. A prohibition repeated in all branches may move to the common parent scope, but a prohibition attached to only one guarded branch may not. Two examples can be removed if they merely illustrate an explicit output schema; an example that is the sole source of a required field must first be converted into an explicit output rule.

The paper defines typed units, scope, and coverage. The parser maps source spans to typed units a ∈ A. A unit records:

a = (τ, σ, g, m, p, P)

where τ is its type, σ its scope, g an optional guard, m its modality, p its normalized content, and P the supporting source spans. A workflow unit additionally records incoming and outgoing edges; a tool unit records its argument signature; an output unit records field and validation information.

If a source span cannot be interpreted with sufficient confidence, it becomes a locked residual: it is copied verbatim and excluded from deletion. This conservative fallback is important because the structural parser, rather than the later optimizer, is the main source of semantic uncertainty.

Coverage is defined as: a ⪯ K when compact representation K covers unit a. Coverage can be direct, or structural: a branch-local copy can be covered by the same rule placed at the closest common ancestor; a repeated action sequence can be covered by a shared procedure whose expansion contains the original edges. Coverage is type-sensitive. A tool name does not cover its required arguments, and a general rule does not cover a conflicting guarded exception.

Contract coverage is formally defined: A compact representation K covers a parsed skill if ∀a ∈ Areq(S), a ⪯ K, where Areq contains interface conditions, workflow nodes and edges, tool requirements, scoped rules, and output requirements.

Theoretical Analysis Summary

The paper defines the shortest faithful explanation. A compressed skill is represented by a library K of reusable contract elements and a residual R for unique, exceptional, or uncertain content. The library may contain shared rules, workflow fragments, tool contracts, output fields, and interface entries. The residual preserves explicit exceptions that cannot be safely normalized.

SkillZip selects the shortest representation that …

Based on this paper, here are the specific improvements I can make to AI systems and what the improved systems can do:

Improvement: Implement a structural compression layer that runs after every self-evolution update, using the typed contract representation (interface, workflow, tools, rules, output) and minimum-description-length objective.

What the improved system can do:

• Detect when a new patch duplicates an existing rule, workflow, or constraint rather than adding new knowledge

• Automatically refactor repeated action sequences into shared procedures

• Move branch-local rules to common parent scopes when they apply universally

• Maintain a sidecar JSON contract while rendering a compact human-readable skill for deployment

• Prevent skill bloat from growing 5.2× on average, capping growth at 1.6–1.9× instead

Improvement: Replace evaluation-guided compression (which requires rollouts and task sampling) with a hard-coverage constraint that guarantees preservation of all extracted contract units, regardless of task frequency.

Improvement: Integrate compression directly into the self-evolution loop, processing each patch through four operations (ABSORB, REFINE, EXTEND, REFACTOR) with local optimization and periodic global repacking.

Improvement: Use explicit rules, guards, and output constraints rather than model-specific soft tokens or latent representations, making compressed skills model-agnostic.

Improvement: Use a two-phase approach: schema-constrained extraction that separates interpretation from optimization, with a locked residual for ambiguous spans.

Improvement: Activate compression from the first evolution round rather than after bloat accumulates.

Self-evolving agents accumulate reusable skills by appending successful procedures and failure fixes. Over time, the same requirement is often restated in several branches, examples, and warnings, while common action sequences are copied rather than reused. The resulting skill becomes expensive to inject and difficult to maintain. Generic prompt compression is ill-suited to this setting because a skill is not a flat passage: its name and description define when it applies, its workflow controls execution, its tool and output contracts constrain validity, and rare exceptions may remain essential even when no sampled task activates them. Evaluation-guided compression can test these behaviors, but it introduces rollouts, cost, and dependence on the compression-time evaluation set. We present SkillZip, an evaluation-free method that compresses a skill by finding its shortest faithful structural explanation. The intuition is explain once, reference many: state a repeated rule once at the scope where it applies, factor a repeated action sequence into a shared procedure, and keep only the differences as explicit exceptions. We formalize this intuition as a typed minimum description-length objective over a skill contract and a residual, subject to a hard coverage constraint for every extracted trigger, workflow edge, tool requirement, obligation, and output field. The formulation provides simple sharing thresholds, preserves unique rare rules by construction, and supports efficient local updates. SkillZip has a one-shot mode with one structured extraction call and deterministic optimization, and a continual Zip-on-Write mode that integrates each self-evolution patch without replaying tasks or reparsing the full history. Through comprehensive experimental evaluations, we demonstrate the effectiveness and superiority of SkillZip in compression performance, generalizability, and cost overhead.