Order Sensitivity in Sequential Cost Partitioning

20 concepts14 papers2 proposals

Imagine you have a $10 budget to distribute among a panel of experts to estimate the cost of a complex project. Each expert requires a certain amount of funding to perform their analysis and provide a lower-bound estimate. If you process the experts sequentially, giving the first expert everything they ask for, they might greedily consume the entire $10 while providing only a mediocre estimate. This leaves $0 for the remaining experts, completely starving them and preventing them from contributing their insights. If you simply change the order in which you consult these experts, the first might only need $3, leaving $7 for the others to dramatically tighten the global estimate.

This scenario illustrates the core intuition behind sequential greedy partitioning. When an algorithm evaluates subproblems, heuristics, or constraints one after another, early decisions greedily consume a shared resource pool (such as action costs, physical space, or variance budgets). This sequential consumption creates an extreme sensitivity to the processing order: an optimal sequence yields a highly accurate global state or bound, while a poor sequence starves subsequent components and leads to catastrophic performance drops.

The Mechanism of Saturated Cost Partitioning

The most rigorous formalization of this problem occurs in optimal AI planning, where solvers must combine multiple heuristics (estimates of the remaining distance to a goal) without overestimating the true cost. To keep the combined heuristic admissible, planners use cost partitioning, dividing the actual costs of actions among the individual heuristics.

In Saturated Cost Partitioning (SCP), introduced by Jendrik Seipp et al. in Diverse and Additive Cartesian Abstraction Heuristics, this distribution happens sequentially:

[Remaining Cost Pool] ───► Heuristic 1 (Takes its "Saturated" Cost)
                                 │
                                 ▼
[Reduced Cost Pool]   ───► Heuristic 2 (Takes its "Saturated" Cost)
                                 │
                                 ▼
[Starved Cost Pool]   ───► Heuristic 3 (Left with little or no budget)

Each heuristic is exposed to the remaining cost pool one by one. It takes the minimum cost it needs to preserve its maximum estimation quality—a process called saturation—and passes whatever is left to the next heuristic.

As Thomas Keller et al. explain in State-Dependent Cost Partitionings for Cartesian Abstractions in Classical Planning, this greedy allocation creates a severe sequence dependency. If an early heuristic consumes the cost of a critical, high-yield action, it prevents all subsequent heuristics from utilizing that action, even if those later heuristics could have leveraged it to contribute a far more informative bound to the global search tree.

The Extreme Variance of Sequences

How much does the order actually matter? In Narrowing the Gap Between Saturated and Optimal Cost Partitioning for Classical Planning, the authors demonstrate that the choice of sequence is the single most critical determinant of heuristic quality. They show that a suboptimal sequence can cause the combined estimate to collapse to near zero, whereas an optimal sequence of the exact same components provides a perfect lower bound.

This sensitivity persists even when moving to advanced variations, such as the state-dependent methods explored by Dominik Drexler et al. in Subset-Saturated Transition Cost Partitioning. Because finding the absolute optimal sequence is a hard combinatorial challenge, researchers have engineered several distinct strategies to mitigate order sensitivity:

A Ubiquitous Pathological Pattern

While heavily studied within AI planning, order sensitivity in greedy sequential processing is a fundamental mathematical pathology that manifests across a wide variety of computer science domains.

Discrete Optimization and Constraint Satisfaction

In Weighted Constraint Satisfaction Problems (WCSPs), finding tight lower bounds traditionally requires moving discrete costs between constraints. Martin C. Cooper et al. show in Optimal Soft Arc Consistency that local heuristic cost movements are highly sensitive to the order of operations, which often traps local solvers in suboptimal local minima.

Physical Resource Placement

The same phenomenon governs physical space allocation. In Rack Position Optimization in Large-Scale Heterogeneous Data Centers, Changlin Chen et al. observe that the sequence in which different rack types are placed dictates the final system flexibility. Poor early choices consume prime physical locations and overly constrain the remaining available space, preventing subsequent high-demand requirements from being fulfilled.

Sequential Sampling and Classification

In statistical analysis, Yuguo Chen et al. highlight in Sequential Monte Carlo Methods for Statistical Analysis of Tables that the ordering of row and column processing in Sequential Importance Sampling (SIS) dictates the variance of the estimator, making heuristic ordering rules essential for accuracy. Similarly, in Multi-Stage Classifier Design, Kirill Trapeznikov et al. demonstrate that the sequence of sensors used for data collection determines whether early, cheap stages unnecessarily starve the information budget of more expensive, accurate downstream classifiers.

Game Theory and Mechanism Design

When inspection costs are present, the order of evaluation dictates economic survival. Bo Waggoner et al. prove in Matching with Nested and Bundled Pandora Boxes that selecting the wrong party to initiate a match inspection can completely destroy positive welfare when values are negative. Even in linear-time budget mechanisms, Kai Han et al. show in Triple Eagle: Simple, Fast and Practical Budget-Feasible Mechanisms that while single-pass scans are highly efficient, the specific sequence of processing participants heavily influences the final approximation ratio and total utility.

Across all these fields, the core lesson remains the same: when resources are allocated or evaluated greedily and sequentially, the sequence is the strategy.

Key Foundational Work

Optimal Soft Arc Consistency (2007) — contributed 1 concept elements to this direction.
Sequential Monte Carlo Methods for Statistical Analysis of Tables (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_order_sensitivity_in_greedy_partitioning_686b5c37,
  title = {order sensitivity in greedy partitioning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/order-sensitivity-in-greedy-partitioning/rdr_686b5c375fad4266ad213f314a02b2fa},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_order_sensitivity_in_greedy_partitioning_686b5c37_v1,
  title = {order sensitivity in greedy partitioning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/order-sensitivity-in-greedy-partitioning/rdr_686b5c375fad4266ad213f314a02b2fa/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake