🤖 machine learning

PACE: Prune-And-Compress Ensemble Models

The paper introduces PACE, a two-phase framework that alternates between the theoretical generation and pruning of learners to create compact, powerful ensemble models while enabling principled control over fidelity to the original ensemble.

Original authors: Fabian Akkerman, Julien Ferry, Théo Guyard, Thibaut Vidal

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Fabian Akkerman, Julien Ferry, Théo Guyard, Thibaut Vidal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Problem: The Overcrowded Orchestra

Imagine a musical orchestra (an ensemble model) tasked with predicting the weather. To get the most accurate forecast, you have hired 100 different musicians (learners). Although this group is incredibly precise, it is a logistical nightmare. It requires enormous space, is slow to rehearse, and if you need to explain why it predicted rain, you must listen to 100 different opinions.

In the world of machine learning, these "musicians" are often decision trees. When trained with standard methods, you end up with many redundant players—musicians who play exactly the same notes as their neighbors. This makes the model too large for mobile phones or fast computers and difficult to understand.

The Old Solutions: Cutting or Replacing

Scientists have tried two main approaches to fix this:

Pruning (The Scissors): You look at the 100 musicians and fire those who contribute nothing new. You keep the original group but remove only the redundant players.
- The Flaw: You are limited by the people already hired. If the original group is bad at a specific task, firing people won't solve the problem; you just have fewer people doing the same bad job.
Compression (The Remake): You fire everyone and hire a brand-new, smaller group of musicians from scratch to imitate the original 100.
- The Flaw: To make the new small group sound exactly like the large one, the new musicians often have to be incredibly complex (like a virtuoso playing 10 instruments simultaneously). This undermines the purpose of simplification.

The New Solution: PACE (The Intelligent Rehearsal)

The authors introduce PACE, a framework that combines both ideas in a clever two-step strategy. Think of it as a "Prune-and-Compress" rehearsal.

Phase 1: The "Fill-in" Band (Active Generation)

Instead of just firing people, PACE first asks: "Is there a note missing in our song that no one in the current band can play?"

The Analogy: Imagine the orchestra is missing a specific sound. PACE actively recruits a new musician who can perfectly play that missing note. It continues adding new, diverse musicians to the band until the group is "rich" enough to cover every possible scenario.
The Goal: This creates an "enriched" ensemble. It might be larger than the original, but it has better potential because it covers all aspects.

Phase 2: The Great Fire (Pruning)

Now that the band is full of diverse, high-quality musicians, PACE picks up the "scissors" again.

The Analogy: Since the band is now so versatile, you can fire many more people than before and still make the song sound perfect. You are left with a tiny, efficient group that can do everything the original 100 could do.
The Result: You end up with a much smaller ensemble than if you had tried to simply prune the original group.

The Rule of "Fidelity": Don't Change the Song

A major concern with this process is: "If we change the band, will they still predict the weather in the same way?"

The Old Way: Some methods required the new band to imitate the old one on every single possible day, even on days that never occur in reality (like a blizzard in the desert). This made it impossible to shrink the band.
The PACE Way: PACE is smarter. It only requires the new band to imitate the old one on days that are actually important.
- It ignores "outliers" (strange, impossible weather data).
- It ignores days with "low confidence," where the original band was just guessing anyway.
- The Advantage: By ignoring strange, irrelevant days, PACE can shrink the band much further without losing accuracy on the days that count.

Why It Works (The Results)

The paper tested this method with real data (such as predicting credit risk or diagnosing diseases). They found that:

It is faster to verify: They used a special mathematical "search engine" (Constraint Programming) to find differences between the old and new bands. This was much faster than previous methods.
It shrinks more: By first adding new musicians and then pruning, PACE consistently produced smaller, more efficient models than methods that only prune or only compress.
It is flexible: You can tell PACE how strict to be. If you want the new band to sound exactly like the old one, it will. If you want it smaller and are okay with slight differences on strange days, it can shrink the band even further.

Summary

PACE is like a music director who realizes that to get a small, perfect band, you shouldn't just fire people. Instead, you should first hire a few great new players to fill the gaps, and then fire the redundant ones. The result is a tiny, efficient orchestra that plays the song perfectly without the chaos of the original huge group.

Technical Summary: PACE (Prune-And-Compress Ensemble Models)

Problem Statement

Ensemble models, particularly those based on decision trees (e.g., Random Forests, Boosting), achieve state-of-the-art predictive performance but often suffer from excessive size due to the aggregation of a large number of weak learning algorithms. This redundancy creates significant barriers to deployment in latency-sensitive and resource-constrained environments, increases memory requirements, and complicates downstream tasks such as robustness verification and interpretability.

Existing solutions generally fall into two categories:

Pruning: The removal of redundant learning algorithms from a trained ensemble through reweighting or elimination. Although effective, pruning is limited because it cannot generate new learning algorithms to replace the removed ones, potentially capping the compression potential.
Compression: The generation of new learning algorithms from scratch to approximate the original ensemble. Although this can achieve high compression, many methods either lose fidelity (exact match of predictions) or require generating learning algorithms that are more complex than the original family, thereby breaking the structural constraints of the model.

The core challenge lies in unifying these paradigms to achieve strong compression while maintaining rigorous guarantees for fidelity (preservation of the original ensemble's predictions) without being overly constrained by irrelevant data regions.

Methodology: The PACE Framework

PACE (Prune-And-Compress Ensemble) introduces a two-phase strategy that links the active generation of learning algorithms with pruning, united under a fidelity-control framework.

1. Two-Phase Strategy

Phase 1: Active Generation of Learning Algorithms (Compression): Instead of starting with a fixed set of learning algorithms, PACE actively generates new learning algorithms to enrich the initial ensemble. This phase utilizes Column Generation. The goal is to find "improving learning algorithms" that reduce the optimal value of a relaxed pruning problem (using an $\ell_1$ $ℓ_{1}$ -norm surrogate).
- The process identifies learning algorithms $h$ that have the potential to improve downstream sparsification.
- A pricing problem is solved to determine whether a new learning algorithm exists that can strictly improve the relaxation. If no such learning algorithm exists ( $L(h) = \emptyset$ ), the generation phase ends, guaranteeing that the enriched ensemble contains all necessary learning algorithms to achieve the best possible relaxation value.
Phase 2: Pruning: Once the ensemble is enriched, PACE solves the original pruning problem (minimization of the $\ell_0$ -norm of weights) on this expanded set. This enables the selection of a sparse subset of weights from a larger, more diverse pool of learning algorithms, often resulting in a smaller final ensemble than pruning the original set alone.

2. Fidelity Management

PACE introduces a nuanced definition of fidelity that goes beyond enforcing an exact match over the entire sample space or a fixed empirical set. It enforces fidelity only over a region of practical interest, $X_\eta \cap X_\delta$ , defined by two parameters:

Confidence Region ( $X_\eta$ ): Samples where the original ensemble predicts with a confidence margin $\eta$ greater than alternative classes. This avoids enforcing fidelity in low-confidence regions where the original model's choice may be arbitrary.
Plausibility Region ( $X_\delta$ ): Samples with a plausibility value $\ge \delta$ relative to the data distribution, calculated via an Isolation Forest. This excludes outliers and out-of-distribution samples where preserving the original prediction is of limited practical interest.

To enforce this, PACE employs Constraint Programming (CP) to iteratively search for "separating samples" (samples where the current model does not match the original). If a separating sample is found within the defined region, it is added to the constraint set, and the weights are re-optimized. This cycle repeats until no separating samples exist in the target region.

Main Contributions

Unified Framework: The work demonstrates that pruning and compression are complementary. PACE unifies them by first enriching the ensemble through active generation and then pruning the result, leveraging the strengths of both approaches.
Column Generation for Enrichment: The authors present a principled strategy using column generation to generate new learning algorithms. This includes a theoretical termination criterion ensuring that no further improving learning algorithms exist, thereby maximizing the potential for subsequent pruning.
Flexible Fidelity: The work expands the concept of fidelity to address only meaningful regions (high confidence and high plausibility). This trade-off enables stronger compression than enforcing exact fidelity while avoiding the pitfalls of arbitrary approximations.
Constraint-Based Separation: PACE utilizes a constraint-based formulation for finding separating samples, which the authors claim is computationally superior to object-based formulations used in prior work.

Experimental Results

The authors evaluated PACE on various datasets (e.g., COMPAS, FICO, Diabetes, Ionosphere) using Random Forest and AdaBoost ensembles.

Compression Performance: PACE consistently outperforms previous purely pruning methods (such as FIPE) and ablated variants (generation only or pruning only). In many cases, the final ensemble consists almost entirely of newly generated learning algorithms rather than the original ones.
Fidelity Control: Relaxing fidelity via parameters $\eta$ and $\delta$ significantly reduces the size of the final ensemble. For example, on the FICO dataset, increasing $\eta$ reduced the ensemble from 58 trees to 3, a reduction unachievable with strict fidelity.
Computational Performance: The constraint-based separation approach used in PACE achieves significant speedups (up to 37-fold in specific Random Forest configurations) compared to the object-based separation used in state-of-the-art methods like FIPE.
Ablation Studies: Experiments confirm that neither generation nor pruning alone achieves the performance of the full PACE framework, validating the necessity of the two-phase approach.

Significance and Claims

The work claims that PACE offers a principled and flexible approach to ensemble compression. Its primary significance lies in:

Superior Compression: Achieving smaller ensemble sizes than existing methods while maintaining predictive accuracy in relevant regions.
Theoretical Guarantees: Providing rigorous guarantees for fidelity within specific, user-defined regions rather than relying on heuristic approximations.
Computational Advances: Demonstrating that Constraint Programming is a highly efficient tool for the separation problem inherent in ensemble pruning and that it outperforms traditional mixed-integer linear programming (MILP) approaches in this context.

The authors acknowledge limitations, noting that PACE incurs higher computational costs than purely pruning methods due to the combinatorial nature of the $\ell_0$ -norm and the generation phase. They also point to the current restriction to tree-based learning algorithms, although the framework is theoretically extensible to other families provided suitable mathematical models can be established. Future work is proposed to optimize the pricing problem for learning algorithm generation and to refine complexity metrics beyond simple learning algorithm counts.