T-TAMER: Provably Taming Trade-offs in ML Serving

## Abstract

Abstract As machine learning models continue to grow in size and complexity, efficient serving faces increasingly broad trade-offs spanning accuracy, latency, resource usage, and other objectives. Multi-model serving further complicates these trade-offs; for example, in cascaded models, each early-exit decision balances latency reduction against potential accuracy loss. Despite the pervasiveness and importance of such trade-offs, current strategies remain largely heuristic and case-specific, limiting both their theoretical guarantees and general applicability. We present a general framework, T-Tamer, which formalizes this setting as a multi-stage decision process, where the objective is to determine both when to exit and which model to consult. Our main result shows that recall (i.e., the ability to revisit earlier models) is both necessary and sufficient for achieving provable performance guarantees. In particular, we prove that strategies without recall cannot obtain any constant-factor approximation to the optimal trade-off, whereas recall-based strategies provably attain the optimal trade-off in polynomial time. We validate our analysis through experiments on synthetic datasets and early-exit workloads for vision and NLP benchmarks. The results show that recall-based strategies consistently yield efficient accuracy–latency trade-offs. We hope this work provides a principled foundation for bridging heuristic practice with theoretical guarantees in the design of early-exit and cascaded models.

## 1 Introduction

As models continue to grow in scale, relying on a single model often fails to meet all service-level objectives (SLOs), such as accuracy, latency, and cost. Deploying only the largest model for every query is both impractical and suboptimal for inference platforms, as many queries can be effectively handled without resorting to the most resource-intensive option (Nie et al., 2024; Rahmath P et al., 2024; Matsubara et al., 2022).

Motivated by this observation, *cascaded inference* has emerged as a widely adopted paradigm for efficient large-scale model serving. The central idea is to maintain a collection of sub-models with varying complexity and to invoke them adaptively in sequence. In practice, the inference platform receives a stream of queries for a classification task together with specified SLOs, such as achieving high accuracy under an average latency budget. Cascaded inference routes simple queries to lightweight models, while reserving the most complex models for the hardest cases. By adaptively selecting sub-models based on query characteristics, the up-cascade framework provides a principled mechanism for efficient inference in modern machine learning systems.

Alternatively, the inference platform can be viewed as taming the trade-offs among conflicting SLOs. While the accuracy–latency trade-off is the most prominent, similar tensions arise in accuracy–cost (where more accurate models generally incur higher computational/monetary cost) and latency–throughput (where larger batch sizes improve throughput but increase per-sample latency).

However, there is no *universally accepted* policy for sub-model routing and termination that applies across different trade-offs and use cases. Existing policies are typically developed in an *ad hoc* manner and remain largely *heuristic-driven*.(^1^11As an aside, exhaustive search is prohibitively time-consuming in most use cases.) This gives rise to two fundamental issues: (1) *limited generalizability*, as a policy designed for one use case often fails to transfer to others, and (2) *suboptimality*, as the resulting strategy is either inefficient or lacks provable efficiency guarantees.

We propose T-Tamer, a general theoretical framework for taming bi-objective trade-offs in cascaded inference. At its core, the framework computes a *theoretically optimal* strategy and instantiates it as a data-driven learner that fits this solution using input–output pairs from *all* sub-models. At inference time, given a query, T-Tamer incrementally updates its belief over sub-model performance as models are inspected and computes the optimal routing and termination policy based on this belief. Notably, the training of the T-Tamer is *agnostic* to that of the sub-models, enabling it to operate as a plug-in component rather than a case-specific solution.

Figure: (a) Directed Line
Refer to caption: graph/single_line.png

The key to T-Tamer strategy is a theoretical abstraction of routing and termination as a multi-stage costly exploration defined over a directed acyclic graph (DAG), where nodes represent sub-models and edges represent both *precedence constraints* (i.e., model A must precede model B) precedence and performance dependencies (i.e., the output of model B conditionally depends on the outputs of model A). The policies derived by T-Tamer are supported by our theoretical analysis and can be computed in polynomial time for DAG structures that commonly arise in practice (See Fig. [1](https://arxiv.org/html/2509.22992v1#S1.F1)): the directed line, its transitive closure (allowing any skip while preserving order), and the directed tree (decision-tree structure).

### 1.1 Applications and Prior Work

The DAG topologies studied here naturally arise in practical inference systems. We review models and prior work that instantiate these structures and connect them to research on multi-model inference, cascaded architectures, and adaptive computation. See App. [A](https://arxiv.org/html/2509.22992v1#A1) for a complete discussion.

Intra-Model Cascaded Inference. Existing intra-model inference methods manage trade-offs by adaptively determining whether to incorporate deeper layers of the network during inference (see surveys by (Han et al., 2021; Montello et al., 2025)). Since the layered architecture of neural networks naturally induces Markovian dependencies, these approaches can be regarded as special cases of the cascaded inference framework. Representative examples include early-exit models (Teerapittayanon et al., 2016; Xin et al., 2020; Matsubara et al., 2022; Rahmath P et al., 2024), skip networks (Wang et al., 2018), and dynamic recursive neural networks (Guo et al., 2019).

Inter-Model Cascaded Inference. More recently, inter-model cascaded inference has been adapted to large models (including LLMs), to mitigate their high inference cost. Existing works have explored how to jointly train the cascades (Varshney & Baral, 2022), how to design cascades with awareness of system-level constraints (Lebovitz et al., 2023) and how to leverage signals to route the model (Varshney & Baral, 2022). These efforts show the promise of cascaded inference for large-scale model serving, yet the absence of guarantees exposes a fundamental theoretical gap.

### 1.2 Our Results

We formulate the trade-off between the two objectives as a weighted sum of their proxy loss functions,
with weights controlled by a tunable parameter $\lambda$. More concretely, probing and consulting exactly one model on input $x$ corresponds to the objective

$$ $\theta_{\lambda}(x)=\lambda\ell_{1}(x)+(1-\lambda)\ell_{2}(x),$ $$

where $\lambda\in[0,1]$ and $\ell_{1},\ell_{2}$ are loss functions depending on $x$.
This additive formulation is (i) flexible, as it can directly incorporate standard loss functions used in
machine learning models, and (ii) stable, since $\theta_{\lambda}(x)$ is always well-defined, whereas
subtraction-based formulations may produce pathological behavior such as negative or unbounded objectives.

Building on this formulation, we note that because inputs are drawn from a distribution, the induced losses of sub-models follow a joint correlated distribution. Our T-Tamer captures this structure by assigning losses to edges and nodes, thereby reducing routing, stopping, and consulting in cascaded models to a *costly exploration* problem over a directed acyclic graph (DAG) that encodes both precedence constraints and inter-model correlations:

- $\bullet$
Optimal Stopping Under Single Line Setting(§[4](https://arxiv.org/html/2509.22992v1#S4)): We classify strategies based on whether they allow recall, that is, whether previously explored sub-models can be revisited and selected after further exploration. Specifically, we develop separate theoretical frameworks for no-recall and with-recall strategies in the single-line setting. We show that no-recall strategies fail to achieve any constant-factor approximation to the optimal utility (§[3](https://arxiv.org/html/2509.22992v1#S3)). This impossibility is *information-theoretic*, rather than computational, and thus cannot be circumvented by increased computational resources. Notably, existing confidence-based cascaded models  (Xin et al., 2020; Teerapittayanon et al., 2016; Laskaridis et al., 2021) can be viewed as no-recall strategies, and our results therefore reveal the fundamental limitations of such heuristics.
For the with-recall setting, we establish a provably optimal *dynamic indexing* strategy. At each step, the strategy computes the index of the next available model and decides whether to stop or continue based on this value. Upon stopping, it returns the best model among those inspected. Moreover, this strategy can be computed and implemented efficiently via dynamic programming.
- $\bullet$
General Costly Exploration for More General DAGs(§[5](https://arxiv.org/html/2509.22992v1#S5)): Our work generalizes the dynamic indexing strategy beyond the single-line setting, where at every iteration, the strategy computes the indices of *all* available models that remain uninspected. We prove that for both tree topologies (Fig. [1c](https://arxiv.org/html/2509.22992v1#S1.F1.sf3)) and the transitive closure of the directed-line case (Fig. [1b](https://arxiv.org/html/2509.22992v1#S1.F1.sf2)), this indexing strategy remains theoretically optimal and can be computed in polynomial time.

Finally, we evaluate our dynamic indexing strategy on synthetic datasets and early-exit workloads from standard vision and NLP benchmarks (§[6](https://arxiv.org/html/2509.22992v1#S6)). The results show that recall-based strategies consistently deliver efficient accuracy–latency trade-offs. We now present our main results:

- $\bullet$
General-Purpose Tradeoff Tamer for Up-Cascade Inference. We introduce T-Tamer, a principled framework for taming bi-objective trade-offs in cascaded inference. Unlike heuristic-driven methods, T-Tamer is model-agnostic and learns to compute the theoretically optimal routing and stopping policy across all sub-models. This makes it broadly applicable as a plug-in component for diverse cascaded inference systems without requiring case-specific tuning.
- $\bullet$
No Constant-Factor Approximation for No-Recall Policy. We prove an *information-theoretic* impossibility for no-recall strategies, showing that even in the directed-line case, such policies cannot achieve any constant-factor approximation to the optimal utility. This result shows that confidence-based heuristics (i.e., early-exit thresholds) for cascaded inference are inherently suboptimal, motivating recall-based strategies with stronger guarantees.
- $\bullet$
Provably Efficient Routing-and-Stopping Policy over DAGs. We develop a *dynamic indexing* strategy that provably achieves optimal exploration and stopping across canonical DAG structures arising in cascaded inference (directed lines, their transitive closures, and trees). Our approach is not only theoretically optimal but also computationally efficient, running in polynomial time. This bridges the gap between theory and practice by providing the first provable, efficient policies for real-world cascaded inference topologies.

## 2 Problem Formulation

In this section, we establish the notation, assumptions, and formal framework of costly exploration over general DAGs, which serves as the theoretical model for cascaded inference.

Notations. Throughout, let $n$ denote the number of sub-models in the cascade, and let $\mathcal{X}$ denote the input space with $x\in\mathcal{X}$. We use $T$ to denote the number of samples used to fit the costly inspection strategy. We use $\ell$ to denote the dominant loss function and $c$ to denote the secondary loss function, occasionally abusing notation by referring to $c$ as the (inspection) cost.

We impose two standard assumptions in supervised learning (Goodfellow et al., 2016). First, all losses are strictly positive(^2^22Loss functions that may take negative values can be shifted or transformed to satisfy this condition.). Second, inputs are drawn from a distribution.

###### Assumption 2.1 (Loss) .

For any sub-model $j\in[n]$ and input $x\in\mathcal{X}$, the losses satisfy $\ell_{j}(x)>0$ and $c_{j}>0$. Moreover, the cost loss $c_{j}$ is a constant independent of the input.

###### Assumption 2.2 (Distributional Assumption) .

Each $x_{t}$, for sample index $t\in[T]$, is assumed to be i.i.d. from a fixed distribution $\mathcal{D}$ over $\mathbb{R}^{d}$.

We distinguish between *recall* and *no-recall* strategies, depending on whether previously consulted models remain available as candidates.

###### Definition 2.3 (Recall / No-Recall Strategy) .

Given a policy that terminates after consulting sub-model $i\in[n]$, the strategy is no-recall, if the final prediction must come from sub-model $i$; with-recall, if the policy may return the prediction of any sub-model $j\leq i$.

We formalize the costly exploration problem over a DAG. Specifically, we introduce a dummy root node $v_{0}$ as the starting node of the policy, in addition to the nodes representing sub-models.

###### Problem 2.4 (Markovian Costly Exploration) .

Consider a set of $n$ nodes $\mathcal{V}=\{v_{1},\ldots,v_{n}\}$.
Each node $v_{i}$ is associated with a random loss $\ell_{i}$ drawn from a known distribution $\operatorname*{\mathcal{D}}_{i}$. We also include a designated null node $v_{0}$, which connects to $v_{1}$ but to no other node, with $\ell_{0}=0$. The nodes are organized into a directed acyclic graph $G=(\mathcal{V},E)$, where edges encode:

- $\bullet$
Partial ordering. For any edge $(v_{i},v_{j})\in E$, if node $v_{j}$ is probed, then $v_{i}$ must be probed strictly before $v_{j}$. We denote this as $v_{i}\prec v_{j}$. Note that $v_{i}$ itself need not be probed unless $v_{j}$ is selected.
- $\bullet$
Edge cost. For each edge $(v_{i},v_{j})\in E$, probing $v_{j}$ right after $v_{i}$ incurs an edge cost $c(i,j)$.
- $\bullet$
Markov property.
For any adjacent nodes $v_{i}\prec v_{j}\prec v_{k}$ along a directed path in $G$,
the node losses satisfy the conditional independence $\ell_{i}\perp\ell_{k}\mid\ell_{j}$.

A policy $\pi$ starts from $v_{0}$ and adaptively selects edges to probe subsequent nodes, deciding at each step whether to continue or stop. Let $\mathcal{O}(\pi)$ denote the set of probed nodes and $E(\pi)$ the set of edges traversed by $\pi$. The goal is to minimize the sum of node and edge losses weighted by the tradeoff parameter $\lambda$: $\mathbb{E}[\lambda\cdot f\!([\ell_{i}]_{i\in\mathcal{O}(\pi)})\;+\;(1-\lambda)\cdot\sum_{e\in E(\pi)}c(e)]$.

For no-recall, $f$ equals the loss of the last visited node; for with-recall, $f$ equals $\min_{i\in\mathcal{O}(\pi)}\ell_{1,i}$.

Finally, we describe how a general policy routes through the sub-models in the cascade (Figure [2](https://arxiv.org/html/2509.22992v1#S2.F2)).

Figure: Figure 2: Costly Exploration for Cascaded Inference

###### Assumption 2.1 (Loss) .

###### Assumption 2.2 (Distributional Assumption) .

###### Definition 2.3 (Recall / No-Recall Strategy) .

###### Problem 2.4 (Markovian Costly Exploration) .

## 3 On Costly Exploration Policies with No Recalls

In this section, we establish an information-theoretic bound showing that no-recall strategies cannot achieve a constant-factor approximation to the offline optimal loss, even in the single-line setting.

### 3.1 Connection to Sequential Cascaded Inference

The single line case corresponds to the sequential cascaded inference paradigm widely adopted in practice. In sequential CI, sub-models are arranged in a *fixed* order and must be inspected one by one (Xin et al., 2020; Dekoninck et al., 2024). A no-recall strategy in this setting amounts to always serving the most complex model inspected so far. A prominent approach is the confidence-threshold strategy, which stops and serves the current model once its prediction confidence exceeds a predefined threshold (Dai et al., 2024; Xin et al., 2020).

### 3.2 Exit with No Recall: No Constant Approximation

In the single-line case, the costly no-recall exploration problem can be formalized as an optimal stopping problem over a sequence of losses $R_{i}$ with Markovian dependencies. Specifically, $R_{i+1}\sim\lambda\ell_{i}+(1-\lambda)c(i-1,i)$ for $i\in[n]$.

###### Problem 3.1 (No Recall Exit Problem) .

Let costs $R_{1}\sim\operatorname*{\mathcal{D}}_{1},\ldots,R_{n}\sim\operatorname*{\mathcal{D}}_{n}$ be non-negative random variables drawn from known distributions $\operatorname*{\mathcal{D}}_{1},\ldots,\operatorname*{\mathcal{D}}_{n}$, with a joint distribution exhibiting Markovian dependency, i.e., for all $i\in[n]$, $R_{i+1}$ is conditionally independent of the past given $R_{i}$:

$$ $\displaystyle\Pr(R_{i+1}\mid R_{1},\ldots,R_{i})=\Pr(R_{i+1}\mid R_{i}),\quad\text{for all }i.$ $$

A decision maker sequentially observes $R_{1}$ to $R_{n}$. After observing $R_{i}$, they must either stop and pay the cost $R_{i}$ or irrevocably discard and continue. The goal is to design a stopping rule $\operatorname{ALG}$ that minimizes the expected loss.

Ideally, $\operatorname{ALG}$ is benchmarked against the optimal loss attainable with *perfect* knowledge of all $R_{i}$.

###### Definition 3.2 (Offline Optimal) .

The benchmark is an oracle who knows all realizations in advance and selects $\min_{i}R_{i}$, incurring expected cost $\operatorname{OPT}=\mathbb{E}[\min_{i}R_{i}]$.

As achieving the offline optimal loss is generally infeasible without full future information, the best attainable guarantee lies in bounding the approximation ratio.

###### Definition 3.3 (Approximation Ratio) .

We say $\operatorname{ALG}$ is an $\alpha$-approximation if for some $\alpha\geq 1$,

$$ $\displaystyle\mathbb{E}[\operatorname{ALG}]\leq\alpha\cdot\operatorname{OPT}.$ $$

We concluded by showing that no algorithm can achieve a constant approximation ratio for no recall costly exploration problem, even when the underlying distribution is bounded.

###### Theorem 3.4 (Impossibility of Constant Approximation, No-Recall Costly Exploration) .

For no-recall costly exploration problem (Prob. [3.1](https://arxiv.org/html/2509.22992v1#S3.Thmtheorem1)), no algorithm achieves a bounded $\alpha$-approximation ratio, even with $n=2$ and bounded distributions.

###### Proof Sketch.

Let $n=2$ and $\alpha>1$ be an arbitrary large constant. Consider the following random variables:

$$ $\displaystyle R_{1}=\frac{1}{\alpha^{2}}$ $\displaystyle\text{w.p. 1},$ $\displaystyle R_{2}=\left\{\begin{array}[]{ll}0&\text{w.p.}1-\frac{1}{\alpha},\\ \frac{1}{\alpha}&\text{w.p. }\frac{1}{\alpha}\end{array}\right.$ $$

Under this construction, any algorithm achieves an expected reward of exactly $1/\alpha^{2}$, but a prophet achieves $\operatorname{OPT}=\nicefrac{{1}}{{\alpha^{3}}}$. This indicates an $\alpha$-competitive ratio. This competitive ratio can be made arbitrarily large by increasing $\alpha$.
∎

This theorem establishes an *information-theoretic* impossibility: no no-recall costly exploration policy can achieve any non-trivial approximation to the offline optimum. Importantly, this limitation is not due to computational hardness (e.g., NP-hardness), but stems from the intrinsic information structure of the problem. One might ask whether it is possible to design an algorithm $\operatorname{ALG}$ that approximates a restricted class of benchmarks. However, such benchmarks can be trivial to approximate—for example, in the construction above, all strategies achieve the same expected utility.

###### Problem 3.1 (No Recall Exit Problem) .

###### Definition 3.2 (Offline Optimal) .

###### Definition 3.3 (Approximation Ratio) .

###### Theorem 3.4 (Impossibility of Constant Approximation, No-Recall Costly Exploration) .

###### Proof Sketch.

## 4 Warm-Up: Indexing over a Directed Line

While the no-recall approach is natural, it overlooks an important practical phenomenon: larger models are not always superior to smaller ones and may even “over-think,” producing worse predictions than intermediate models (Sui et al., 2025; Kaya et al., 2019). Such behavior has been observed in real systems, underscoring the practical need for recall-based strategies that can revisit earlier models and provide stronger guarantees. In this section, we introduce a theoretically optimal indexing strategy for with-recall costly exploration for single-line setting.

### 4.1 With-Recall Costly Inspection over Single Line

Motivated by the theoretical limitations of no-recall policies discussed earlier, we now turn to analyzing the efficiency of with-recall policies.
The with-recall setting admits a similar abstraction under costly exploration.
The key distinction from the no-recall formulation is that the two losses cannot be collapsed into a single objective: one loss $R_{i}=\lambda\ell_{i}$ is incurred at the nodes, while a separate cost $c_{i}:=(1-\lambda)c(i-1,i)$ is incurred along the edges when moving to the current node.

###### Problem 4.1 (With-Recall Costly Exploration) .

Let the costs of the nodes $R_{1},\ldots,R_{n}$ be non-negative random variables drawn from known distributions $\operatorname*{\mathcal{D}}_{1},\ldots,\operatorname*{\mathcal{D}}_{n}$, with a joint distribution exhibiting Markovian dependency; i.e., $R_{i+1}$ is conditionally independent of the past given $R_{i}$.

A decision maker sequentially observes $R_{1},\ldots,R_{n}$, where each node $i$ incurs a cost $\lambda c_{i}$. After observing $R_{i}$, the decision maker must either stop—incurring a total cost of $\min_{k\in[i]}R_{k}+\sum_{j\in[i]}c_{j}$ by selecting $\arg\min_{k\in[i]}R_{k}$—or continue. The goal is to minimize the expected total cost.

Since Markovian-correlated distributions with continuous support cannot be directly represented without additional assumptions (Ethier & Kurtz, 2009), we quantize them into a discrete domain and base decisions on this discretization. Such discretization is standard in practice (e.g., grid search). Hence, without loss of generality, we assume $\mathcal{D}_{1},\ldots,\mathcal{D}_{n}$ are discrete.

Note that the counterexample in Theorem [3.4](https://arxiv.org/html/2509.22992v1#S3.Thmtheorem4) continues to yield arbitrarily large approximation gaps even when recall is allowed. We therefore benchmark against a more favorable comparator with tractable guarantees.

###### Definition 4.2 (Online Optimal) .

The benchmark is the optimal online algorithm, which has access to the joint distribution $\mathcal{D}_{1},\ldots,\mathcal{D}_{n}$ and achieves the minimum possible expected loss without observing realizations in advance.

By Bellman’s principle of optimality, we derive the optimal with-recall costly exploration strategy via dynamic programming, starting from the last node and progressively extending to the first. This yields a clean structural result: the optimal policy stops once the current minimum loss falls below a dynamic index $\sigma$ determined by the current observation.

Figure: Algorithm 1 Costly Exploration via Indexing

Algorithm [1](https://arxiv.org/html/2509.22992v1#alg1) illustrates the structure of the optimal strategy. At each step, the algorithm updates the dynamic index of the next box and decides whether to stop given the current minimum loss. Thus, the stopping decision at step $i$ can be represented as a stop/continue rule table dependent on $(X,R_{i})$.

###### Problem 4.1 (With-Recall Costly Exploration) .

###### Definition 4.2 (Online Optimal) .

### 4.2 The Dynamic Index

We now introduce the dynamic index, which serves as the core of our provably efficient strategy. At a high level, the optimal policy stores, for every possible state $(X,R_{i-1},i)$, the corresponding index and the stop/continue decision. These indices can be computed efficiently via dynamic programming, proceeding backward from the last node.

Notation. Assume that each $R_{i}$ takes values in a common finite support $V=\{v_{1},\ldots,v_{k}\}$. For each $i\in[n]$, let $\mathbf{p}_{i}$ denote the probability mass function (PMF) of $R_{i}$, with $\mathbf{p}_{i}[v_{q}]=\Pr[R_{i}=v_{q}]$. Let $P_{i}\in\mathbb{R}_{+}^{k\times k}$ be the transition matrix from $\operatorname*{\mathcal{D}}_{i}$ to $\operatorname*{\mathcal{D}}_{i+1}$, such that $\mathbf{p}_{i+1}=\mathbf{p}_{i}\cdot P_{i+1}$. The optimal policy $\pi$ reduces to a stopping rule that selects the node with minimum loss, we use $\tau$ to denote it.

We now formally describe the dynamic programming procedure to compute the dynamic index function $\sigma$. Any stopping time $\tau$ depends only on the current minimum reward $X$, the most recent loss $R_{i}$, and the next candidate index $i+1$. We refer to the tuple $(X,R_{i},i{+}1)$ as the algorithm’s *state*, and proceed to derive the expected loss incurred at this state under a given stopping time $\tau$.

###### Definition 4.3 (Equivalent Loss) .

Given $\tau$ and $(x,R_{i-1},i)$, we define the expected loss of the state $(X,R_{i-1},i)$ following stopping rule $\tau$ as $\Phi^{\tau}(X,R_{i-1},i)$.

$$ $\displaystyle\Phi^{\tau}(X,R_{i-1},i):=\operatorname*{{\mathbb{E}}}[\min\{X,\min_{j=i}^{\tau(X,R_{i-1},i)}R_{j}\}+\sum_{j=i}^{\tau(X,R_{i-1},i)}c_{j}]$ $$

In addition, we use $\Phi(X,R_{i-1},i)=\Phi^{\tau^{*}}(X,R_{i-1},i)=\min_{\tau}\Phi^{\tau}(X,R_{i-1},i)$ to denote the expected future loss following the optimal strategy $\tau^{*}$ starting at state $(X,R_{i-1},i)$.

Let $\Phi$ be the expected loss of a state, then $\Phi$ can be solved inductively using Bellman’s principle of optimality: $\Phi^{\tau^{*}}(X,R_{i-1},i)=\min\Big\{X,c_{i}+\operatorname*{{\mathbb{E}}}_{R_{i}|R_{i-1}}[\phi^{\tau^{*}}(\min\{X,R_{i}\},R_{i},i+1)]\Big\}$, where the first term corresponds to stopping immediately, and the second to continuing and applying the optimal stopping time $\tau^{*}$ for the remaining boxes.

Importantly, for fixed $R_{i-1}$ and $i$, there exists a maximal $X$ such that the decision maker is *indifferent* between stopping and opening the next box. This value defines the dynamic index $\sigma$ that governs our algorithm (Alg. [1](https://arxiv.org/html/2509.22992v1#alg1)). More formally,

###### Definition 4.4 (Dynamic Index) .

Given any state $(X,R_{i-1},i)$, we define the dynamic index at the current state, denoted by $\sigma_{i}(X,R_{i-1},i)$, as the smallest solution to:

$$ $\operatorname*{{\mathbb{E}}}\Big[\Big(\sigma-\min_{j=i}^{\tau^{*}(\sigma,R_{i-1},i)}R_{j}\Big)_{+}-\sum_{j=i}^{\tau^{*}(\sigma,R_{i-1},i)}c_{j}\Big]=0,$ (1) $$

where $\tau^{*}$ is the optimal strategy.

###### Definition 4.3 (Equivalent Loss) .

###### Definition 4.4 (Dynamic Index) .

### 4.3 Provable Efficiency

Next, we establish that the dynamic index is both well-defined and optimal, thereby justifying the correctness of our algorithm (Alg. [1](https://arxiv.org/html/2509.22992v1#alg1)). Moreover, we show that the optimal strategy can be computed efficiently via dynamic programming. See Sec. [B](https://arxiv.org/html/2509.22992v1#A2) for more details.

###### Theorem 4.5 (Optimality and Efficiency of Dynamic Indexing) .

Given the current state $(X,R_{i},i{+}1)$, there exists a solution to ([1](https://arxiv.org/html/2509.22992v1#S4.E1)).
This solution is independent of the current minimum loss $X$ and can be denoted by $\sigma(R_{i},i{+}1)$. The indexing policy that stops when $\sigma>X$ and continues otherwise (Alg. [1](https://arxiv.org/html/2509.22992v1#alg1)) achieves online optimality.

Furthermore, preprocessing this policy takes $O(n\cdot|V|^{2}T)$ time and requires $O(n|V|^{2})$ space. At inference time, for each input $x$, the policy runs in $O(1)$ per node and $O(n)$ overall per input.

The intuition behind the guarantee is that the stop/continue decision for each state $(X,R_{i},i{+}1)$ can be precomputed and stored. At inference time, the algorithm queries this table in $O(1)$ per step, yielding $O(n)$ time per sample. Further details are given in Lem. [B.3](https://arxiv.org/html/2509.22992v1#A2.Thmtheorem3) and Lem. [B.4](https://arxiv.org/html/2509.22992v1#A2.Thmtheorem4).

###### Theorem 4.5 (Optimality and Efficiency of Dynamic Indexing) .

## 5 Extension: Strategies Over General DAGs

In this section, we extend the dynamic index to general DAGs. The generalized indexing policy remains optimal, but it must additionally incorporate the routing decision, i.e., which model to inspect next. We show that this policy can still be implemented efficiently via dynamic programming.

### 5.1 Directed Tree

We describe how to generalize the previous indexing strategy to the directed tree setting. One application of this setting is cost-aware binary search over domains, where the tree corresponds to a binary search tree and the loss represents the cost of acquiring feedback, as in human-in-the-loop settings such as RLHF (Xiong et al., 2023) or crowdsourcing.

Figure: (a) Subtree Identification
Refer to caption: graph/tree_step_1.png

Illustrated by Fig. [3](https://arxiv.org/html/2509.22992v1#S5.F3), the key idea of our generalized dynamic index is to define a tree contraction procedure that contracts a subtree into a single node while preserving the equivalent loss table and loss distribution of the subtree. Concretely, we first identify subtrees whose children consist only of single nodes or multi-lines, contract these into single nodes, and then repeat the process iteratively.

To carry out this indexing policy, we can still keep an if-stop matrix for each node, which only depends on the realized minimum loss and the loss of that node. The main difference is that now, when using dynamic programming, we need to combine information from all of the node’s children.

###### Theorem 5.1 (Dynamic Indexing in Directed Trees: Optimality and Efficiency) .

There exist a generalization of the dynamic indexing policy (Alg. [3](https://arxiv.org/html/2509.22992v1#alg3)), which is theoretically optimal. Furthermore, preprocessing this policy takes $O(n\cdot|V|^{2}T)$ time and requires $O(n|V|^{2})$ space. At inference time, for each input $x$, the policy runs in $O(1)$ per node and $O(n)$ overall per input.

We defer the details to
Lem. [C.13](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem13) and Thm. [C.14](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem14) in the Appendix [C](https://arxiv.org/html/2509.22992v1#A3).

###### Theorem 5.1 (Dynamic Indexing in Directed Trees: Optimality and Efficiency) .

### 5.2 Transitive Closure of A Directed Line

We extend the dynamic index to the transitive closure of a directed line. Unlike the directed line setting, where models must be evaluated strictly sequentially, the transitive closure allows skipping while preserving order, enabling cost savings by reducing the number of evaluations.

###### Theorem 5.2 (Dynamic Indexing in Skipped Inference: Optimality and Efficiency) .

There exists a generalization of the dynamic indexing policy, which is theoretically optimal. Furthermore, preprocessing this policy takes $O(n^{2}\cdot|V|^{2}T)$ time and requires $O(n|V|^{2})$ space. At inference time, for each input $x$, the policy runs in $O(1)$ per node and $O(n)$ overall per input.

We can still use dynamic programming to pre-compute the if-stop matrix and the equivalent-loss table. The key difference from the single-line case is that, when computing the equivalent loss, we must enumerate over all possible next nodes rather than just the immediate successor. This increases the preprocessing time by a factor of $n$. We defer the technical details to Section [C.3](https://arxiv.org/html/2509.22992v1#A3.SS3).

###### Theorem 5.2 (Dynamic Indexing in Skipped Inference: Optimality and Efficiency) .

## 6 Experiments

In this section, we evaluate our dynamic indexing strategy Recall over real-world CV/ NLP early exit (EE) classification workloads. Experiments of synthetic data and more details are in Appendix [D](https://arxiv.org/html/2509.22992v1#A4)

Experimental Setup. Our testbed consists of a single server equipped with two Intel Xeon Gold 6438M processors (3.90 GHz), 512 GB of DDR5 memory, and one NVIDIA RTX 4000 Ada GPU. The server runs Ubuntu 22.04 with Linux kernel 5.15, CUDA version 13.0, and Python 3.10.

Metrics We use the error rate as a metric, defined as $\text{Err}=1-\text{Acc}$, where Acc is the empirical accuracy measured against the outputs of the backbone model, which we regard as an upper bound on achievable performance given the model’s capacity.
To demonstrate latency reduction, we *normalize* the achieved latency against the original latency.

Evaluations.
In Figure [4](https://arxiv.org/html/2509.22992v1#S6.F4), we evaluate our dynamic index strategy over vision classification tasks, using the video streaming dataset collected from (Agarwal & Netravali, 2023; Hsieh et al., 2018), with VGG-{11, 13} models (Simonyan & Zisserman, 2014) as the backbone models for EE.

Figure: (a) VGG-13, Auburn
Refer to caption: x1.png

In Figure [5](https://arxiv.org/html/2509.22992v1#S6.F5), we also evaluate the dynamic index strategy on NLP classification tasks using the IMDB (Pal et al., 2020) and Amazon Review (McAuley & Leskovec, 2013) datasets, with BERT-base (Devlin et al., 2019a) and GPT-2 (Radford et al., 2019) as backbone models for EE.

Figure: (a) BertBase, IMDB
Refer to caption: x5.png

## 7 Conclusion

We introduced T-Tamer, a principled framework for taming bi-objective trade-offs in cascaded inference. By formulating routing and stopping as a costly exploration problem over DAGs, we developed a dynamic indexing strategy that achieves provable optimality with polynomial-time complexity. Experiments on synthetic data and real-world CV/NLP benchmarks confirm that T-Tamer consistently delivers favorable accuracy–latency trade-offs, providing a general-purpose and efficient foundation for modern inference platforms.

## References

- Adamczyk et al. (2016)
Marek Adamczyk, Maxim Sviridenko, and Justin Ward.
Submodular stochastic probing on matroids.
*Mathematics of Operations Research*, 41(3):1022–1038, 2016.
- Agarwal & Netravali (2023)
Neil Agarwal and Ravi Netravali.
Boggart: Towards $\{$General-Purpose$\}$ acceleration of retrospective video analytics.
In *20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23)*, pp. 933–951, 2023.
- Ailon et al. (2011)
Nir Ailon, Bernard Chazelle, Kenneth L Clarkson, Ding Liu, Wolfgang Mulzer, and C Seshadhri.
Self-improving algorithms.
*SIAM Journal on Computing*, 40(2):350–375, 2011.
- Alabi et al. (2019)
Daniel Alabi, Adam Tauman Kalai, Katrina Liggett, Cameron Musco, Christos Tzamos, and Ellen Vitercik.
Learning to prune: Speeding up repeated computations.
In *Conference on Learning Theory*, pp. 30–33. PMLR, 2019.
- Amanatidis et al. (2024)
Georgios Amanatidis, Federico Fusco, Rebecca Reiffenhäuser, and Artem Tsikiridis.
Pandora’s box problem over time.
*arXiv preprint arXiv:2407.15261*, 2024.
- Aouad et al. (2020)
Ali Aouad, Jingwei Ji, and Yaron Shaposhnik.
The pandora’s box problem with sequential inspections.
*Available at SSRN 3726167*, 2020.
- Armstrong (2017)
Mark Armstrong.
Ordered consumer search.
*Journal of the European Economic Association*, 15(5):989–1024, 2017.
- Balcan et al. (2017)
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White.
Learning-theoretic foundations of algorithm configuration for combinatorial partitioning problems.
In *Conference on Learning Theory*, pp. 213–274. PMLR, 2017.
- Balcan et al. (2018)
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik.
Learning to branch.
In *International conference on machine learning*, pp. 344–353. PMLR, 2018.
- Balcan et al. (2019)
Maria-Florina Balcan, Dan DeBlasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik.
How much data is sufficient to learn high-performing algorithms?
*Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC) 2021*, 2019.
- Bergemann et al. (2018)
Dirk Bergemann, Alessandro Bonatti, and Alex Smolin.
The design and price of information.
*American economic review*, 108(1):1–48, 2018.
- Berger et al. (2024)
Ben Berger, Tomer Ezra, Michal Feldman, and Federico Fusco.
Pandora’s problem with deadlines.
In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pp. 20337–20343, 2024.
- Bergstra & Bengio (2012)
James Bergstra and Yoshua Bengio.
Random search for hyper-parameter optimization.
*Journal of machine learning research*, 13(2), 2012.
- Beyhaghi & Cai (2023)
Hedyeh Beyhaghi and Linda Cai.
Pandora’s problem with nonobligatory inspection: Optimal structure and a ptas.
In *Proceedings of the 55th Annual ACM Symposium on Theory of Computing*, pp. 803–816, 2023.
- Beyhaghi & Kleinberg (2019)
Hedyeh Beyhaghi and Robert Kleinberg.
Pandora’s problem with nonobligatory inspection.
In *Proceedings of the 2019 ACM Conference on Economics and Computation*, pp. 131–132, 2019.
- Bhattacharya & Khanna (2012)
Sayan Bhattacharya and Sanjeev Khanna.
Prophet inequalities with limited information.
In *Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, 2012.
- Boodaghians et al. (2020)
Shant Boodaghians, Federico Fusco, Philip Lazos, and Stefano Leonardi.
Pandora’s box problem with order constraints.
In *Proceedings of the 21st ACM Conference on Economics and Computation*, pp. 439–458, 2020.
- Charikar et al. (2000)
Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, and Amit Sahai.
Query strategies for priced information.
In *Proceedings of the thirty-second annual ACM symposium on Theory of computing*, pp. 582–591, 2000.
- Chawla et al. (2010)
Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan.
Multi-parameter mechanism design and sequential posted pricing.
In *Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC)*, 2010.
- Chawla et al. (2019)
Shuchi Chawla, Shaleen Deep, Paraschos Koutrisw, and Yifeng Teng.
Revenue maximization for query pricing.
*Proceedings of the VLDB Endowment*, 13(1):1–14, 2019.
- Chawla et al. (2020)
Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang.
Pandora’s box with correlations: Learning and approximation.
In *2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)*, pp. 1214–1225. IEEE, 2020.
- Chawla et al. (2021)
Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos.
Approximating pandora’s box with correlations.
*arXiv preprint arXiv:2108.12976*, 2021.
- Chawla et al. (2024)
Shuchi Chawla, Dimitris Christou, Amit Harlev, and Ziv Scully.
Combinatorial selection with costly information.
*arXiv preprint arXiv:2412.03860*, 2024.
- Chen et al. (2015a)
Yuxin Chen, S Hamed Hassani, Amin Karbasi, and Andreas Krause.
Sequential information maximization: When is greedy near-optimal?
In *Conference on Learning Theory*, pp. 338–363. PMLR, 2015a.
- Chen et al. (2015b)
Yuxin Chen, Shervin Javdani, Amin Karbasi, J Bagnell, Siddhartha Srinivasa, and Andreas Krause.
Submodular surrogates for value of information.
In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 29, 2015b.
- Clarkson et al. (2010)
Kenneth L Clarkson, Wolfgang Mulzer, and C Seshadhri.
Self-improving algorithms for convex hulls.
In *Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms*, pp. 1546–1565. SIAM, 2010.
- Correa et al. (2019)
José Correa, Pablo D. A. Foncea, Ruben Hoeksma, and Tim Roughgarden.
Prophet inequalities for independent random variables from an unknown distribution.
In *Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, 2019.
- Correa et al. (2022)
José Correa, Anja Korol, and Ruben Hoeksma.
Prophet inequalities and posted pricing mechanisms.
*Mathematics of Operations Research*, 47(4):2580–2600, 2022.
- Dai et al. (2024)
Yinwei Dai, Rui Pan, Anand Iyer, Kai Li, and Ravi Netravali.
Apparate: Rethinking early exits to tame latency-throughput tensions in ml serving.
In *Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles*, pp. 607–623, 2024.
- Dekoninck et al. (2024)
Jasper Dekoninck, Maximilian Baader, and Martin Vechev.
A unified approach to routing and cascading for llms.
*arXiv preprint arXiv:2410.10347*, 2024.
- Derakhshan et al. (2022)
Mahsa Derakhshan, Negin Golrezaei, Vahideh Manshadi, and Vahab Mirrokni.
Product ranking on online platforms.
*Management Science*, 68(6):4024–4041, 2022.
- Devlin et al. (2019a)
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.
Bert: Pre-training of deep bidirectional transformers for language understanding.
In *Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 (long and short papers)*, pp. 4171–4186, 2019a.
- Devlin et al. (2019b)
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.
Bert: Pre-training of deep bidirectional transformers for language understanding.
In *Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 (long and short papers)*, pp. 4171–4186, 2019b.
- Ding et al. (2023)
Bolin Ding, Yiding Feng, Chien-Ju Ho, Wei Tang, and Haifeng Xu.
Competitive information design for pandora’s box.
In *Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pp. 353–381. SIAM, 2023.
- Doval (2018)
Laura Doval.
Whether or not to open pandora’s box.
*Journal of Economic Theory*, 175:127–158, 2018.
- Esfandiari et al. (2017)
Hossein Esfandiari, Mohammad Taghi Hajiaghayi, Brendan Lucier, and Morteza Zadimoghaddam.
Prophet inequalities with unknown distributions.
In *Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC)*, 2017.
- Ethier & Kurtz (2009)
Stewart N Ethier and Thomas G Kurtz.
*Markov processes: characterization and convergence*.
John Wiley & Sons, 2009.
- Feldman et al. (2016)
Michal Feldman, Thomas Kesselheim, and Brendan Lucier.
Online stochastic matching: Beating 1 - 1/e.
In *Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC)*, 2016.
- Fu et al. (2023)
Hu Fu, Jiawei Li, and Daogao Liu.
Pandora box problem with nonobligatory inspection: Hardness and approximation scheme.
In *Proceedings of the 55th Annual ACM Symposium on Theory of Computing*, pp. 789–802, 2023.
- Gatmiry et al. (2024)
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, and Yifan Wang.
Bandit algorithms for prophet inequality and pandora’s box.
In *Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pp. 462–500. SIAM, 2024.
- Gergatsouli & Tzamos (2022)
Evangelia Gergatsouli and Christos Tzamos.
Online learning for min sum set cover and pandora’s box.
In *International Conference on Machine Learning*, pp. 7382–7403. PMLR, 2022.
- Gergatsouli & Tzamos (2023)
Evangelia Gergatsouli and Christos Tzamos.
Weitzman’s rule for pandora’s box with correlations.
*arXiv preprint arXiv:2301.13534*, 2023.
- Gittins (1979)
John C. Gittins.
Bandit processes and dynamic allocation indices.
*Journal of the Royal Statistical Society: Series B (Methodological)*, 41(2):148–177, 1979.
- Gittins (1989)
John C. Gittins.
*Multi-armed Bandit Allocation Indices*.
John Wiley & Sons, Chichester, UK, 1989.
- Goel et al. (2006)
Ashish Goel, Sudipto Guha, and Kamesh Munagala.
Asking the right questions: Model-driven optimization using probes.
In *Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems*, pp. 203–212, 2006.
- Goodfellow et al. (2016)
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio.
*Deep learning*, volume 1.
MIT press Cambridge, 2016.
- Guo et al. (2019)
Qiushan Guo, Zhipeng Yu, Yichao Wu, Ding Liang, Haoyu Qin, and Junjie Yan.
Dynamic recursive neural network.
In *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pp. 5147–5156, 2019.
- Gupta & Kumar (2001)
Anupam Gupta and Amit Kumar.
Sorting and selection with structured costs.
In *Proceedings 42nd IEEE Symposium on Foundations of Computer Science*, pp. 416–425. IEEE, 2001.
- Gupta & Nagarajan (2013)
Anupam Gupta and Viswanath Nagarajan.
A stochastic probing problem with applications.
In *Integer Programming and Combinatorial Optimization: 16th International Conference, IPCO 2013, Valparaiso, Chile, March 18-20, 2013. Proceedings 16*, pp. 205–216. Springer, 2013.
- Gupta et al. (2016)
Anupam Gupta, Viswanath Nagarajan, and Sahil Singla.
Algorithms and adaptivity gaps for stochastic probing.
In *Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms*, pp. 1731–1747. SIAM, 2016.
- Gupta et al. (2017)
Anupam Gupta, Viswanath Nagarajan, and Sahil Singla.
Adaptivity gaps for stochastic probing: Submodular and xos functions.
In *Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms*, pp. 1688–1702. SIAM, 2017.
- Gupta et al. (2019)
Anupam Gupta, Haotian Jiang, Ziv Scully, and Sahil Singla.
The markovian price of information.
In *Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings 20*, pp. 233–246. Springer, 2019.
- Gupta & Roughgarden (2016)
Rishi Gupta and Tim Roughgarden.
A pac approach to application-specific algorithm selection.
In *Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science*, pp. 123–134, 2016.
- Han et al. (2021)
Yizeng Han, Gao Huang, Shiji Song, Le Yang, Honghui Wang, and Yulin Wang.
Dynamic neural networks: A survey.
*IEEE transactions on pattern analysis and machine intelligence*, 44(11):7436–7456, 2021.
- Hazan et al. (2018)
Elad Hazan, Adam Klivans, and Yang Yuan.
Hyperparameter optimization: a spectral approach.
In *International Conference on Learning Representations*, 2018.
- He et al. (2016)
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.
Deep residual learning for image recognition.
In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pp. 770–778, 2016.
- Hsieh et al. (2018)
Kevin Hsieh, Ganesh Ananthanarayanan, Peter Bodik, Shivaram Venkataraman, Paramvir Bahl, Matthai Philipose, Phillip B Gibbons, and Onur Mutlu.
Focus: Querying large video datasets with low latency and low cost.
In *13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)*, pp. 269–286, 2018.
- Jamieson & Talwalkar (2016)
Kevin Jamieson and Ameet Talwalkar.
Non-stochastic best arm identification and hyperparameter optimization.
In *Artificial intelligence and statistics*, pp. 240–248. PMLR, 2016.
- Kaya et al. (2019)
Yigitcan Kaya, Sanghyun Hong, and Tudor Dumitras.
Shallow-deep networks: Understanding and mitigating network overthinking.
In *International conference on machine learning*, pp. 3301–3310. PMLR, 2019.
- Kleinberg & Kleinberg (2018)
Jon Kleinberg and Robert Kleinberg.
Delegated search approximates efficient search.
In *Proceedings of the 2018 ACM Conference on Economics and Computation*, pp. 287–302, 2018.
- Kleinberg & Krakovski (2005)
Robert Kleinberg and Sergei M. Krakovski.
Multiple-choice prophet inequalities.
In *Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, 2005.
- Kleinberg et al. (2016)
Robert Kleinberg, Bo Waggoner, and E Glen Weyl.
Descending price optimally coordinates search.
In *Proceedings of the 2016 ACM Conference on Economics and Computation*, pp. 23–24, 2016.
- Kleinberg et al. (2017)
Robert Kleinberg, Kevin Leyton-Brown, and Brendan Lucier.
Efficiency through procrastination: Approximately optimal algorithm configuration with runtime guarantees.
In *IJCAI*, volume 3, pp.  1, 2017.
- Kotthoff et al. (2019)
Lars Kotthoff, Chris Thornton, Holger H Hoos, Frank Hutter, and Kevin Leyton-Brown.
Auto-weka: Automatic model selection and hyperparameter optimization in weka.
*Automated machine learning: methods, systems, challenges*, pp. 81–95, 2019.
- Krengel & Sucheston (1977)
Ulrich Krengel and Louis Sucheston.
Semiamarts and finite values.
1977.
- Krengel & Sucheston (1978)
Ulrich Krengel and Louis Sucheston.
On semiamarts, amarts, and processes with finite value.
*Probability on Banach spaces*, 4(197-266):1–2, 1978.
- Laskaridis et al. (2021)
Stefanos Laskaridis, Alexandros Kouris, and Nicholas D Lane.
Adaptive inference through early-exit networks: Design, challenges and directions.
In *Proceedings of the 5th International Workshop on Embedded and Mobile Deep Learning*, pp. 1–6, 2021.
- Lebovitz et al. (2023)
Luzian Lebovitz, Lukas Cavigelli, Michele Magno, and Lorenz K Muller.
Efficient inference with model cascades.
*Transactions on Machine Learning Research*, 2023.
- Li & Shi (2017)
Hao Li and Xianwen Shi.
Discriminatory information disclosure.
*American Economic Review*, 107(11):3363–3385, 2017.
- Li & Liu (2022)
Jian Li and Daogao Liu.
Multi-token markov game with switching costs.
In *Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pp. 1780–1807. SIAM, 2022.
- Li et al. (2017)
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar.
Hyperband: A novel bandit-based approach to hyperparameter optimization.
*The Journal of Machine Learning Research*, 18(1):6765–6816, 2017.
- Livanos & Mehta (2024)
Vasilis Livanos and Ruta Mehta.
Minimization is harder in the prophet world.
In *Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pp. 424–461. SIAM, 2024.
- Matsubara et al. (2022)
Yoshitomo Matsubara, Marco Levorato, and Francesco Restuccia.
Split computing and early exiting for deep learning applications: Survey and research challenges.
*ACM Computing Surveys*, 55(5):1–30, 2022.
- McAuley & Leskovec (2013)
Julian McAuley and Jure Leskovec.
Hidden factors and hidden topics: understanding rating dimensions with review text.
In *Proceedings of the 7th ACM conference on Recommender systems*, pp. 165–172, 2013.
- Montello et al. (2025)
Fabio Montello, Ronja Güldenring, Simone Scardapane, and Lazaros Nalpantidis.
A survey on dynamic neural networks: from computer vision to multi-modal sensor fusion.
*arXiv preprint arXiv:2501.07451*, 2025.
- Nie et al. (2024)
Lunyiu Nie, Zhimin Ding, Erdong Hu, Christopher Jermaine, and Swarat Chaudhuri.
Online cascade learning for efficient inference over streams.
In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), *Proceedings of the 41st International Conference on Machine Learning*, volume 235 of *Proceedings of Machine Learning Research*, pp. 38071–38090. PMLR, 21–27 Jul 2024.
- Olszewski & Weber (2015)
Wojciech Olszewski and Richard Weber.
A more general pandora rule?
*Journal of Economic Theory*, 160:429–437, 2015.
- Pal et al. (2020)
Aditya Pal, Abhilash Barigidad, and Abhijit Mustafi.
Imdb movie reviews dataset, 2020.
URL [https://dx.doi.org/10.21227/zm1y-b270](https://dx.doi.org/10.21227/zm1y-b270).
- Radford et al. (2019)
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al.
Language models are unsupervised multitask learners.
*OpenAI blog*, 1(8):9, 2019.
- Rahmath P et al. (2024)
Haseena Rahmath P, Vishal Srivastava, Kuldeep Chaurasia, Roberto G Pacheco, and Rodrigo S Couto.
Early-exit deep neural network-a comprehensive survey.
*ACM Computing Surveys*, 57(3):1–37, 2024.
- Simonyan & Zisserman (2015)
K Simonyan and A Zisserman.
Very deep convolutional networks for large-scale image recognition.
In *3rd International Conference on Learning Representations (ICLR 2015)*. Computational and Biological Learning Society, 2015.
- Simonyan & Zisserman (2014)
Karen Simonyan and Andrew Zisserman.
Very deep convolutional networks for large-scale image recognition.
*arXiv preprint arXiv:1409.1556*, 2014.
- Singla (2018)
Sahil Singla.
The price of information in combinatorial optimization.
In *Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms*, pp. 2523–2532. SIAM, 2018.
- Sivaprasad et al. (2020)
Prabhu Teja Sivaprasad, Florian Mai, Thijs Vogels, Martin Jaggi, and François Fleuret.
Optimizer benchmarking needs to account for hyperparameter tuning.
In *International conference on machine learning*, pp. 9036–9045. PMLR, 2020.
- Snoek et al. (2012)
Jasper Snoek, Hugo Larochelle, and Ryan P Adams.
Practical bayesian optimization of machine learning algorithms.
*Advances in neural information processing systems*, 25, 2012.
- Sui et al. (2025)
Yang Sui, Yu-Neng Chuang, Guanchu Wang, Jiamu Zhang, Tianyi Zhang, Jiayi Yuan, Hongyi Liu, Andrew Wen, Shaochen Zhong, Na Zou, et al.
Stop overthinking: A survey on efficient reasoning for large language models.
*arXiv preprint arXiv:2503.16419*, 2025.
- Teerapittayanon et al. (2016)
Surat Teerapittayanon, Bradley McDanel, and Hsiang-Tsung Kung.
Branchynet: Fast inference via early exiting from deep neural networks.
In *2016 23rd international conference on pattern recognition (ICPR)*, pp. 2464–2469. IEEE, 2016.
- Varshney & Baral (2022)
Neeraj Varshney and Chitta Baral.
Model cascading: Towards jointly improving efficiency and accuracy of nlp systems.
*arXiv preprint arXiv:2210.05528*, 2022.
- Wang et al. (2018)
Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph E Gonzalez.
Skipnet: Learning dynamic routing in convolutional networks.
In *Proceedings of the European conference on computer vision (ECCV)*, pp. 409–424, 2018.
- Weber (1992)
Richard R. Weber.
On the gittins index for multiarmed bandits.
*The Annals of Applied Probability*, 2(4):1024–1033, 1992.
doi: 10.1214/aoap/1177005775.
- Weisz et al. (2018)
Gellért Weisz, Andras Gyorgy, and Csaba Szepesvári.
Leapsandbounds: A method for approximately optimal algorithm configuration.
In *International Conference on Machine Learning*, pp. 5257–5265. PMLR, 2018.
- Weitzman (1979)
Martin L Weitzman.
Optimal search for the best alternative.
*Econometrica: Journal of the Econometric Society*, pp. 641–654, 1979.
- Xie et al. (2024)
Qian Xie, Raul Astudillo, Peter Frazier, Ziv Scully, and Alexander Terenin.
Cost-aware bayesian optimization via the pandora’s box gittins index.
*Advances in Neural Information Processing Systems*, 37:115523–115562, 2024.
- Xie et al. (2025)
Qian Xie, Linda Cai, Alexander Terenin, Peter I Frazier, and Ziv Scully.
Cost-aware stopping for bayesian optimization.
*arXiv preprint arXiv:2507.12453*, 2025.
- Xin et al. (2020)
Ji Xin, Raphael Tang, Jaejun Lee, Yaoliang Yu, and Jimmy Lin.
Deebert: Dynamic early exiting for accelerating bert inference.
*arXiv preprint arXiv:2004.12993*, 2020.
- Xin et al. (2021)
Ji Xin, Raphael Tang, Yaoliang Yu, and Jimmy Lin.
Berxit: Early exiting for bert with better fine-tuning and extension to regression.
In *Proceedings of the 16th conference of the European chapter of the association for computational linguistics: Main Volume*, pp. 91–104, 2021.
- Xiong et al. (2023)
Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang.
Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint.
*arXiv preprint arXiv:2312.11456*, 2023.
- Yan (2011)
Qiqi Yan.
Mechanism design via correlation gap.
*ACM Transactions on Economics and Computation*, 1(1):1–37, 2011.
- Zhou et al. (2020)
Wangchunshu Zhou, Canwen Xu, Tao Ge, Julian McAuley, Ke Xu, and Furu Wei.
Bert loses patience: Fast and robust inference with early exit.
*Advances in Neural Information Processing Systems*, 33:18330–18341, 2020.

## Appendix

## Appendix A More Details from Literature Review

Early Exit Models. Among intra-model cascaded inference methods, *early-exit* (EE) architectures have been widely adopted to accelerate inference in both computer vision and natural language processing, including ResNet (He et al., 2016), VGG (Simonyan & Zisserman, 2015), and BERT-based (Devlin et al., 2019b) models (see Rahmath P et al. (2024); Laskaridis et al. (2021) for a recent survey). The ramp architectures in these models are typically designed to align with the structural properties of the backbone. Existing exit strategies commonly rely on metrics such as label confidence (Xin et al., 2021), prediction entropy (Xin et al., 2020; Teerapittayanon et al., 2016), or more advanced mechanisms such as ramp-level counters (Zhou et al., 2020). However, these approaches do not allow for *prediction with recall*, where the system may return to the output of a previously visited exit—a setting where empirical evidence suggests that earlier exits can occasionally outperform later ones (Kaya et al., 2019).

Relation to Pandora’s Box and Prophet Inequality. The Pandora’s Box framework (Weitzman, 1979; Boodaghians et al., 2020; Chawla et al., 2020) and the Prophet Inequality framework (Krengel & Sucheston, 1977; 1978; Livanos & Mehta, 2024) are two classical models for decision making under uncertainty. Specifically, our exit-with-recall model bears structural similarity to the Pandora’s Box problem, while the no-recall variant aligns closely with the Prophet Inequality setting—both situated within a cost minimization framework. However, our setting imposes two key constraints: (i) a precedence constraint on the order in which boxes (or exits) may be inspected, and (ii) a Markovian correlation that the underlying distributions conform to. These constraints render existing algorithms for the aforementioned problems inapplicable.

Since Weitzman’s classic formulation (Weitzman, 1979), Pandora’s Box has been extended in numerous ways. Variants with order constraints (Boodaghians et al., 2020) and correlated rewards (Chawla et al., 2019; 2020; 2021; Gergatsouli & Tzamos, 2023) highlight the challenges of adaptivity, with the latter proving constant-factor approximation NP-hard in the fully adaptive case.
Online variants connect to bandits and set cover, yielding competitive or regret-minimizing algorithms (Gergatsouli & Tzamos, 2022; Gatmiry et al., 2024). Nonobligatory inspection (Doval, 2018; Beyhaghi & Kleinberg, 2019; Beyhaghi & Cai, 2023; Fu et al., 2023) further departs from Weitzman’s ranking-based solution, with NP-hardness results and PTAS guarantees.
Other extensions address partial openings (Aouad et al., 2020), generalized objectives (Olszewski & Weber, 2015), deadlines (Berger et al., 2024), time-dependent costs (Amanatidis et al., 2024), and strategic information revelation (Ding et al., 2023).

Prophet inequalities, first studied by Krengel & Sucheston (1977; 1978), compare the performance of an online stopping rule to a prophet with full foresight.
Classical results (reward maximization) guarantee a $1/2$-approximation in general settings, with improvements under additional structure.
Recent work has extended this line to matroids and combinatorial constraints (Kleinberg & Krakovski, 2005; Bhattacharya & Khanna, 2012), correlated and non-i.i.d. distributions (Correa et al., 2019; Yan, 2011), and online matching and allocation problems (Esfandiari et al., 2017; Feldman et al., 2016).
Further advances include connections to posted pricing in mechanism design (Chawla et al., 2010; Correa et al., 2022) and to multi-armed bandits (Gatmiry et al., 2024).

Data-Driven Algorithm Design. Our framework relates to data-driven algorithm design (Gupta & Roughgarden, 2016) with cost, where practitioners refine parameterized algorithms via training instances to maximize expected future performance. Data-driven algorithm design Gupta & Roughgarden (2016) includes greedy heuristic selection, self-improving algorithms (Clarkson et al., 2010; Ailon et al., 2011), and parameter tuning in optimization and machine learning Goel et al. (2006); Bergstra & Bengio (2012); Snoek et al. (2012); Jamieson & Talwalkar (2016); Balcan et al. (2017); Li et al. (2017); Kleinberg et al. (2017); Hazan et al. (2018); Weisz et al. (2018); Balcan et al. (2018); Alabi et al. (2019); Balcan et al. (2019); Kotthoff et al. (2019); Sivaprasad et al. (2020).

Gittin’s Index In particular, in the single-line and multi-line cases our adaptive index reduces to the well-known non-*discounted* Gittins index (Gittins, 1979; 1989; Weber, 1992). By contrast, for directed-tree and skip-graph structures, the indexing strategy developed here appears to be novel, as no analogous formulation has been established in prior work. Other recent studies have also leveraged Gittins indices to address efficiency challenges in machine learning, including applications such as hyperparameter tuning (Xie et al., 2024; 2025).

Other Related Work. Another relevant direction is the *stochastic probing* problem, where one must decide both which elements to probe and when to probe them. Gupta & Nagarajan (2013) introduced this setting under matroid and knapsack intersection constraints, giving the first polynomial-time $\Omega(1/k)$-approximate sequential posted price mechanism for $k$-matroid intersections. Adamczyk et al. (2016) extended the model to monotone submodular objectives, achieving a $\tfrac{1-1/e}{k_{\text{in}}+k_{\text{out}}+1}$-approximation in general and a tighter $\tfrac{1}{k_{\text{in}}+k_{\text{out}}}$ bound for linear objectives. Subsequent work (Gupta et al., 2016; 2017) investigated adaptivity gaps, quantifying the performance loss of non-adaptive strategies relative to optimal adaptive ones under prefix-closed constraints.

Beyond stochastic probing, other problems share similar information structures or solution concepts, including search (Armstrong, 2017; Kleinberg & Kleinberg, 2018), ranking (Derakhshan et al., 2022), Markov games (Li & Liu, 2022), sorting and selection (Gupta & Kumar, 2001), revenue maximization (Kleinberg et al., 2016; Chawla et al., 2019), and costly information acquisition (Charikar et al., 2000; Chen et al., 2015b; a; Li & Shi, 2017; Singla, 2018; Bergemann et al., 2018; Gupta et al., 2019; Chawla et al., 2024).

## Appendix B More Details from Single Line Costly Exploration

### B.1 More Details for the Dynamic Index

We introduce additional notation to facilitate the formal analysis of the dynamic index. Specifically, we use $\Phi$ and $\phi$ interchangeably to denote the equivalent loss.

###### Lemma B.1 (Properties of $\Phi$ and $H_{i}$ ) .

Given any state $(x,R_{i-1},i)$,

- $\bullet$
$\Phi(\cdot,R_{i-1},i)$ is 1-Lipschitz and monotone non-decreasing.
- $\bullet$
Let $H_{i}(x,R_{i-1}):=\Phi(x,R_{i-1},i)-x$, then $H_{i}(\cdot,R_{i-1})$ is nonnegative, 1-Lipschitz and monotone non-increasing.
- $\bullet$
For $\sigma_{i}$ as the index (Def. [4.4](https://arxiv.org/html/2509.22992v1#S4.Thmtheorem4)) of the $i$-th node of the hypernode, then $\Phi(x,R_{i-1},i)=x$ for any $x\geq\sigma_{i}$.

###### Proof.

Given any $a<b$,

$$ $\displaystyle\Phi(b,R_{i-1},i)-\Phi(a,R_{i-1},i)$ $\displaystyle\leq\operatorname*{{\mathbb{E}}}\Big[\min\{b,\min_{j=i}^{\tau^{*}(a,R_{i-1},i)}R_{j}\}-\min\{a,\min_{j=i}^{\tau^{*}(a,R_{i-1},i)}R_{j}\}\Big]$ $\displaystyle\leq b-a$ $$

where in the first inequality, we used that $\tau^{*}(a,R_{i-1},i)$ is a suboptimal strategy for $\Phi^{\tau}(b,R_{i-1},i)$. Using the same reasoning, we have:

$$ $\displaystyle\Phi(b,R_{i-1},i)$ $\displaystyle=\operatorname*{{\mathbb{E}}}\Big[\min\{b,\min_{j=i}^{\tau^{*}(b,R_{i-1},i)}R_{j}\}\Big]+\sum_{j=i}^{\tau^{*}(b,R_{i-1},i)}c_{j}$ $\displaystyle\geq\operatorname*{{\mathbb{E}}}\Big[\min\{a,\min_{j=i}^{\tau^{*}(b,R_{i-1},i)}R_{j}\}\Big]+\sum_{j=i}^{\tau^{*}(b,R_{i-1},i)}c_{j}$ $\displaystyle\geq\operatorname*{{\mathbb{E}}}\Big[\min\{a,\min_{j=i}^{\tau^{*}(a,R_{i-1},i)}R_{j}\}+\sum_{j=i}^{\tau^{*}(a,R_{i-1},i)}c_{j}\Big]=\Phi(a,R_{i-1},i)$ $$

Thus, $\Phi(\cdot,R_{i-1},i)$ is monotone non-decreasing. Now consider $H_{i}$, we have

$$ $H_{i}(b,R_{i-1})-H_{i}(a,R_{i-1})=\Phi(b,R_{i-1},i)-\Phi(a,R_{i-1},i)-(b-a)\leq 0$ $$

where we use that $\Phi(\cdot,R_{i-1},i)$ is 1-Lipschitz. The above inequality implies that $H_{i}(x,R_{i-1})$ is 1-Lipschitz and monotone non-increasing. Lastly, $\Phi(x,R_{i-1},i)-x=0$ for all $x\geq\sigma_{i}$ follows from the that fact that $\sigma_{i}$ is the smallest such that $H_{i}(\sigma_{i},R_{i-1})=0$ and $H_{i}$ is non-negative and monotone non-increasing.

∎

###### Lemma B.2 (Properties of the Dynamic Index) .

Given a costly exploration problem with line precedence graph $\mathcal{L}=\left[b_{1},\ldots,b_{n}\right]$, the dynamic index of every node $i\in[n]$ satisfies the following property: Given any state $R_{i-1}$ as the state of $(i-1)$-th node,

- •
$\sigma_{i}(R_{i-1},i)$ is nonincreasing as additional nodes are appended to $\mathcal{L}$.
- •
Let $\eta$ be the (random) index of the first node that has dynamic index larger than $\sigma_{i}(R_{i-1},i)$, then $\sigma_{i}(R_{i-1},i)$ depends only on the (sub)hypernode $\widehat{\mathcal{L}}:=\{b_{i},\ldots,b_{\eta}\}$. If $i=\eta$ with probability $1$, then $\sigma_{i}(R_{i-1},i)$ depends only on $b_{i}$.

###### Proof.

- $\bullet$
The first property holds because the optimal policy stops at the additional nodes only if they yield a lower expected loss. Consequently, appending nodes at the end of $\mathcal{L}$ can only decrease the expected loss for any given state. As a result, this operation leads to a nonincreasing dynamic index.
- $\bullet$
The second property is due to that the optimal stopping time will stop at $(\eta-1)$-th node, hence the dynamic index doesn’t depend on any nodes starting from $\eta$.

∎

###### Lemma B.3 .

The smallest solution to ([1](https://arxiv.org/html/2509.22992v1#S4.E1)) exists, and hence Definition [4.4](https://arxiv.org/html/2509.22992v1#S4.Thmtheorem4) is well defined.
Given current state $(x,R_{i-1},i)$, if the dynamic index $\sigma_{i}=x$, then there exists some optimal stopping time $\tau^{*}(x,R_{i-1},i)\geq i$.

###### Proof.

Given any state $(x,R_{i-1},i)$, consider function

$$ $\displaystyle H_{i}(x,R_{i-1})=\Phi(x,R_{i-1},i)-x$ $$

$H_{i}(x)$ is 1-Lipschitz and monotone non-increasing by lemma [B.1](https://arxiv.org/html/2509.22992v1#A2.Thmtheorem1). Since $H_{i}(0,R_{i-1})=\Phi(0,R_{i-1},i)\geq 0$ and $H_{i}(v_{k},R_{i-1})=0$, there exist some $\sigma_{i}\in S$, such that $H_{i}(\sigma_{i},R_{i-1})=0$. This proves the existence of $\sigma_{i}$.

Now, we show that if $x=\sigma_{i}$ is positive, then there exists an optimal stopping rule that proceeds to open $b_{i}$.
Fix any $i$ such that $\sigma_{i}>0$. Let $\widetilde{\tau}$ be the best strategy among all strategies that open $b_{i}$. To show that $\widetilde{\tau}$ is indeed optimal, we show that

$$ $\delta=\Phi(\sigma_{i},R_{i-1},i)-\Phi^{\widetilde{\tau}}(\sigma_{i},R_{i-1},i)=0$ $$

Assume towards contradiction that $\delta>0$. We have

$$ $\displaystyle 0<\delta$ $\displaystyle=\Phi(\sigma_{i},R_{i-1},i)-\Phi^{\widetilde{\tau}}(\sigma_{i},R_{i-1},i)$ $\displaystyle\leq\Phi(\sigma_{i},R_{i-1},i)-\Phi^{\tau^{*}(\sigma_{i}-\epsilon,R_{i-1},i)}(\sigma_{i},R_{i-1},i)$ $\displaystyle=(\Phi(\sigma_{i},R_{i-1},i)-\Phi(\sigma_{i}-\epsilon,R_{i-1},i))+(\Phi(\sigma_{i}-\epsilon,R_{i-1},i)-\Phi^{\tau^{*}(\sigma_{i}-\epsilon,R_{i-1},i)}(\sigma_{i},R_{i-1},i))$ $\displaystyle\leq 2\epsilon$ $$

where we used Lipschitzness of $\Phi$ for the last inequality, and the first inequality comes from the fact that $\tau^{*}(\sigma_{i}-\epsilon,R_{i-1},i)$ is a sub-optimal policy that opens $b_{i}$. We have $\tau^{*}(\sigma_{i}-\epsilon,R_{i-1},i)\geq i$ since $\sigma_{i}$ is the smallest such that $H_{i}(\sigma_{i},R_{i-1})=0$, this implies that $H_{i}(\sigma_{i}-\epsilon,R_{i-1})=\Phi^{\tau^{*}(\sigma_{i}-\epsilon,R_{i-1},i)}(\sigma_{i}-\epsilon,R_{i-1},i)-(\sigma_{i}-\epsilon)>0$ meaning the optimal policy will accumulate more reward than current best, thus it has to open $b_{i}$. As $\epsilon\rightarrow 0$, we get a contradiction. On the other hand, $H_{i}(\sigma_{i},R_{i-1})=\Phi(\sigma_{i},R_{i-1},i)-\sigma_{i}=0$ implies that the strategy that stops at $b_{i-1}$ is also optimal. Thus, $\sigma_{i}$ is indeed the value for which we are indifferent between stopping and proceeding optimally.
∎

###### Lemma B.1 (Properties of Φ \Phi and H i H_{i} ) .

###### Proof.

###### Lemma B.2 (Properties of the Dynamic Index) .

###### Proof.

###### Lemma B.3 .

###### Proof.

### B.2 Payoff Table

Figure: Algorithm 2 Expected Equivalent Reward Computation, Single Line

###### Lemma B.4 (Efficient Computation of Payoff Table) .

There is an efficient algorithm that computes $\phi(x,s,i)$ for all $i$, $x$ and $s$.

###### Proof.

Now we give an efficient algorithm for computing the dynamic index. In fact, we will give an algorithm that uses dynamic programming to compute $\Phi(x,R_{i-1},i)$ for all triples $(x,R_{i-1},i)$. Then, given the current state of the algorithm $(x,R_{i-1},i)$, the dynamic index $\sigma_{i}$ for node $i$ is the smallest $x$ in the table where $\Phi(x,R_{i-1},i)=x$.

Denote by $T(x,R_{i-1},i)$ our three dimensional dynamic programming table. Each entry $T(x,R_{i-1},i)$ will store the following information:

- 1.
Expected future loss: $\Phi(x,R_{i-1},i)$
- 2.
Indicator: $\mathds{1}(x,R_{i-1},i)$ indicating whether the optimal policy will open $b_{i}$ in this state
- 3.
The distribution of future random min reward(^3^33The randomness comes from both random stopping time $\tau^{*}$ and correlated random variables $R_{i}$’s,): $R_{\textsc{FRM}}(x,R_{i-1},i):=\min_{j=i}^{\tau^{\star}(x,R_{i-1},i)}R_{j}$ where $R_{j}$’s are the correlated random rewards for mininodes that are yet to be opened given that the algorithm is at state $(x,R_{i-1},i)$.
- 4.
The distribution of future random cost(^4^44The randomness comes from $\tau^{*}$ being a random stopping time.): $c_{\text{FR}}(x,R_{i-1},i):=\sum_{j=i}^{\tau^{\star}(x,R_{i-1},i)}c_{j}$

Algorithm [2](https://arxiv.org/html/2509.22992v1#alg2) describes how to fill in the dynamic programming table. Since all random variables that appear in Algorithm [2](https://arxiv.org/html/2509.22992v1#alg2) has finite support with size bounded by $\operatorname{poly}(K,n)$, and any $\min$ operation for random variables only has three or less arguments, it follows that algorithm [2](https://arxiv.org/html/2509.22992v1#alg2) takes polynomial time and space.
∎

###### Lemma B.4 (Efficient Computation of Payoff Table) .

###### Proof.

## Appendix C More Details Costly Exploration Over Tree

Notations In our analysis, $\lambda c_{i}$ always appears as a whole. Notice that in our analysis, $\lambda$ is not used as the tradeoff parameter but is applied for other purposes throughout our analysis on the indexing policy. For graphs with a directed-tree constraint, since each node has exactly one parent, we can allocate the edge cost to the node itself. In this way, inspecting a node $i$ reveals both its loss $\ell_{i}$ and its inspection cost $c_{i}$. Please see Fig. [6](https://arxiv.org/html/2509.22992v1#A3.F6) as an example.

We first define the notion of a hypernode, namely a directed-line subgraph of the DAG that, under suitable conditions,
can be reparameterized as a single node with aggregated loss and cost.

###### Definition C.1 (Hypernode) .

Given an instance of the costly exploration problem with $n$ nodes $\mathcal{V}$ organized in a directed acyclic graph (DAG) $G=(\mathcal{V},E)$, a *hypernode* is a subset of nodes $\mathcal{H}:=\{v_{1},\ldots,v_{m}\}\subseteq\mathcal{V}$ such that the subgraph of $G$ induced by $\mathcal{H}$, denoted by $\mathcal{L}$, forms a directed path.
That is, for each $i\in[m-1]$, the edge $(v_{i},v_{i+1})$ belongs to $E$.

###### Definition C.1 (Hypernode) .

### C.1 Costly Exploration Over Multi Lines

Before presenting our solution for the tree case, we first introduce the solution for the multi-line setting. We begin by introducing the problem definition of the multi-line setting.

###### Definition C.2 (Multi-Line Costly Exploration) .

Given an instance of the Markovian costly exploration problem (Prob. [2.4](https://arxiv.org/html/2509.22992v1#S2.Thmtheorem4)),
we say it is in a *multi-line setting* if the induced subgraph of $G$, excluding the dummy root node $v_{0}$,
can be decomposed into a collection of disjoint directed lines:

$$ $\mathcal{L}=\{L_{1},L_{2},\ldots,L_{k}\},\quad L_{j}=(v^{j}_{1}\to v^{j}_{2}\to\cdots\to v^{j}_{m_{j}}),$ $$

such that every node $v\in\mathcal{V}$ belongs to exactly one line $L_{j}$.
Each line $L_{j}$ can then be reparameterized as a sequence of hypernodes (Def. [C.1](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem1)),
so that the costly exploration problem reduces to choosing among multiple directed lines.

Figure: (a) Pipeline for Early Exit Models
Refer to caption: graph/multi_line.png

We now show that in the multi-line case, the optimal strategy is to probe each hypernode according to the dynamic index of its first unopened node.

We begin by presenting the definition of a node with random cost, with reward and cost correlated.

###### Definition C.3 (Node with Random Cost) .

A node $v$ is classified as a *node with random cost* if it is associated with a loss $\ell$ and an inspection cost $c$,
where both $\ell$ and $c$ are *random variables* drawn from known distributions $\mathcal{D}_{\ell}$ and $\mathcal{D}_{c}$, respectively.
The inspection cost $c$ may vary and can be *correlated* with the loss $\ell$; we denote their joint distribution as $\Gamma$.

Next, we introduce how to equivalently represent a hypernode as a single node with random cost, where the dynamic index of the hypernode equals that of the equivalent node.

###### Lemma C.4 (Equivalent Single Node for Hypernode) .

For a stopping time $\tau$ and a hypernode $\mathcal{H}:=\{v_{1},\ldots,v_{n}\}$,
there exists a node $\widehat{v}$ with random cost (Def. [C.3](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem3)) such that
following $\tau$ over $\mathcal{H}$ yields the same loss distribution as inspecting $\widehat{v}$.

###### Proof.

Let $L=(\ell_{1},\ldots,\ell_{n})$ be a realization of the joint loss distribution in hypernode $\mathcal{H}$.
For each realization of $L$, the stopping time $\tau$ uniquely determines the effective loss and cumulative cost of the hypernode.

To construct the distribution of the equivalent single node,
we define a coupling between the realizations of $L$ and the resulting loss and cost.
When the joint loss is $L$, we assign the single node’s loss as $\min_{i=1}^{\tau}\ell_{i}$
and the single node’s cost as $\sum_{i=1}^{\tau}c_{i}$, where $\tau$ is the stopping time.
The probability of each outcome matches the probability of $L$ under the original hypernode’s joint distribution.
∎

From our construction of the equivalent node, we obtain the following lemma: the dynamic index remains well-defined
for a node with random cost, even when the nodes inside a hypernode have stochastic costs.

###### Lemma C.5 (Extending Dynamic Index to Hypernodes with Random Cost) .

Given a hypernode $\mathcal{H}:=\{v_{1},\ldots,v_{n}\}$, where each node has a stochastic inspection cost
that may be correlated with its loss distribution, the dynamic index of each node with random cost is well-defined
and can be computed in polynomial time.

Moreover, if the dynamic index $\widehat{\sigma}$ of individual nodes—i.e., the index when there is only one node with random cost—satisfies

$$ $\displaystyle\widehat{\sigma}(v_{1})\leq\widehat{\sigma}(v_{2}\mid\ell_{1})\leq\cdots\leq\widehat{\sigma}(v_{n}\mid\ell_{n-1}),$ $$

for any realized losses $\ell_{1},\ldots,\ell_{n}$, then the dynamic index of $v_{i}$ within the hypernode depends only on $v_{i}$ itself.

###### Proof.

Since the $\phi$ and $H$ functions remain well-defined and preserve their properties,
the dynamic index remains well-defined for hypernodes with nodes of random cost.
The second claim follows from Lem. [B.2](https://arxiv.org/html/2509.22992v1#A2.Thmtheorem2).
∎

We begin by presenting a key lemma for our main theorem, which establishes that under certain Markovian correlations, the dynamic index remains an optimal decision rule. We show this lemma by first principles, where we compare the utility of the ordering $A\prec B\prec C$ with that of $B\prec A\prec C$ through a case-by-case analysis of 9 outcomes from the joint distribution of $A$, $B$, and $C$ and aggregate them by the law of total expectation.

###### Lemma C.6 (Probing Equivalent Nodes) .

Consider three nodes $A,B,C$ with random cost (Def. [C.3](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem3)) satisfying the following properties:

- $\bullet$
The loss and cost of $B$ are independent of the loss and cost of $A$;
- $\bullet$
The loss and cost (hence effective outcome) of $C$ depend on both $A$ and $B$ in a Markovian fashion;
- $\bullet$
The dynamic indices satisfy $\sigma(A)<\sigma(B)<\sigma(C)$ given any realizations of $A$ and $B$(^5^55Here, $\sigma(C)$ is a random variable that depends on $A$ and $B$.), i.e., for any possible value $x$ of $A$ and value $y$ of $B$,
$\displaystyle\sigma(A)\leq\sigma(B)\leq[\sigma(C)\mid\ell_{A}=x,\,\ell_{B}=y];$
- $\bullet$
A precedence constraint that $A$ and $B$ must be probed before $C$;

then, conditioned on any competing loss $X$, the optimal probing strategy is $A\prec B\prec C$.

###### Proof.

It’s sufficient to compare two strategies: 1) $D_{1}:B\to A\to C$, and 2) $D_{2}:A\to B\to C$. Notice that if $X<\sigma(A)$, then it’s optimal to not probe any node, then the ordering of the node doesn’t matter. WLOG, we may assume $X>\sigma(A)$.

We first write down the expected loss according to ordering strategy $D_{1}$, if we use notation as in Table. [1](https://arxiv.org/html/2509.22992v1#A3.T1), we have that this loss is equivalent to:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[c_{B}]+\operatorname*{{\mathbb{E}}}[R_{B}|\pi_{B}]\Pr[\pi_{B}]$ $\displaystyle+\lambda_{B}[\operatorname*{{\mathbb{E}}}[c_{A}]+\operatorname*{{\mathbb{E}}}[R_{A}|\pi_{A}]\pi_{A}+\operatorname*{{\mathbb{E}}}[\min\{R_{A},R_{B},y\}|\lambda_{B}\cap\lambda_{A}]\lambda_{A}]+\operatorname*{{\mathbb{E}}}[\min\{R_{B},y|\rho_{A},\lambda_{B}\}\rho_{A}]]$ $\displaystyle+\rho_{B}[\operatorname*{{\mathbb{E}}}[c_{A}]+\operatorname*{{\mathbb{E}}}[R_{A}|\pi_{A}]\pi_{A}+\operatorname*{{\mathbb{E}}}[\min\{y,R_{A}|\lambda_{A}\}\lambda_{A}+\operatorname*{{\mathbb{E}}}[\phi_{C}(\{R_{A},R_{B},X\}|\rho_{A}\cap\rho_{B})]]]$ $$

Here, we abuse the notation $\rho,\pi,\lambda$ to denote both events and their probabilities,
with the intended meaning clear from context; we use $\phi$ as similar definition to $\Phi$ (Lem. [B.1](https://arxiv.org/html/2509.22992v1#A2.Thmtheorem1)), which denote the equivalent loss of probing $C$ based on the observation. We also use $E\cap F$ to denote the event that both $E$ and $F$ occur.

Similarly, using the notations in Table [2](https://arxiv.org/html/2509.22992v1#A3.T2), we have that the expected loss according to strategy $D_{2}$ is:

$$ $\displaystyle E[c_{A}]+\pi_{A}\operatorname*{{\mathbb{E}}}[R_{A}|\pi_{A}]+\lambda_{A}\operatorname*{{\mathbb{E}}}[\min\{X,R_{A}\}|\lambda_{A}]$ $\displaystyle+\rho_{A}[\operatorname*{{\mathbb{E}}}[c_{B}]+\pi_{B}\operatorname*{{\mathbb{E}}}[R_{B}|\pi_{B}]+\lambda_{B}\operatorname*{{\mathbb{E}}}[\min\{X,R_{B}\}|\lambda_{B}\cap\rho_{A}]+\rho_{B}\phi_{C}(\min\{X,R_{B},R_{A}\}|\rho_{A}\cap\rho_{B})]$ $$

Notice that the last term of both payoffs can be cancelled out. Also notice that the reservation value for box $A$ and $B$ satisfies:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[(\sigma_{B}-R_{B})_{+}-c_{B}]=0$ $$

Plugging in the appropraite values of $\rho,\pi,\lambda$, we have:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[c_{A}]$ $\displaystyle=\pi_{A}\sigma_{A}-\pi_{A}\operatorname*{{\mathbb{E}}}[R_{A}|\pi_{A}]$ $\displaystyle\operatorname*{{\mathbb{E}}}[c_{B}]$ $\displaystyle=(\pi_{B}+\lambda_{B})\sigma_{B}-\pi_{B}\operatorname*{{\mathbb{E}}}[R_{B}|\pi_{B}]-\lambda_{B}\operatorname*{{\mathbb{E}}}[R_{B}|\lambda_{B}]$ $$

Now, plugging the value of the expected cost and after simplification, we have that:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[\textsc{Util}(D_{2})-\textsc{Util}(D_{1})]$ $\displaystyle=\pi_{B}\pi_{A}(\sigma_{A}-\sigma_{B})$ $\displaystyle+\pi_{A}\lambda_{B}[\operatorname*{{\mathbb{E}}}[R_{B}|\lambda_{B}]-\sigma_{B}]+\lambda_{A}\pi_{B}[\operatorname*{{\mathbb{E}}}[\min\{X,R_{A}|\lambda_{A}\}-\sigma_{B}]]]$ $\displaystyle+\lambda_{B}\lambda_{A}[-\operatorname*{{\mathbb{E}}}[\min\{R_{A},R_{B}.X\}|\lambda_{B}\cap\lambda_{A}]-\sigma_{B}$ $\displaystyle+\operatorname*{{\mathbb{E}}}[R_{B}|\lambda_{B}]+\operatorname*{{\mathbb{E}}}[\min\{y,R_{A}\}|\lambda_{A}]]$ $\displaystyle<\lambda_{B}\lambda_{A}[-\operatorname*{{\mathbb{E}}}[\min\{R_{A},R_{B}.X\}|\lambda_{B}\cap\lambda_{A}]-\sigma_{B}+\operatorname*{{\mathbb{E}}}[R_{B}|\lambda_{B}]+\operatorname*{{\mathbb{E}}}[\min\{y,R_{A}\}|\lambda_{A}]]$ $$

where the last inequality follows by the property that $\operatorname*{{\mathbb{E}}}[A|A\leq X]<X$.

Finally, we show that the last term is negative. Notice that:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[\min\{R_{A},R_{B},X\}|\lambda_{B}\cap\lambda_{A}]$ $\displaystyle=\sigma_{B}+\operatorname*{{\mathbb{E}}}[\min\{\min\{R_{A},X\}-\sigma_{B},R_{B}-\sigma_{B}\}|\lambda_{B}\cap\lambda_{A}]$ $\displaystyle\leq\sigma_{B}+\operatorname*{{\mathbb{E}}}[\min\{R_{A},X\}-\sigma_{B}+R_{B}-\sigma_{B}|\lambda_{B}\cap\lambda_{A}]$ $\displaystyle=\operatorname*{{\mathbb{E}}}[R_{B}|\lambda_{B}]+\operatorname*{{\mathbb{E}}}[\min\{X,R_{A}\}|\lambda_{A}]-\sigma_{B}<0$ $$

where the last equality follows from the independence of box $A$ and $B$. Aggregating all of the above we have:

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[\textsc{Util}(D_{2})-\textsc{Util}(D_{1})]<0.$ $$

Hence it’s optimal to probe according to policy $D_{2}$.
∎

**Table 1: Table for Expected Payoff according to Strategy $D_{1}$. This table presents the expected total payoff for every possible joint distribution of box $A$ and $B$. In addition, $\rho_{A}=1-\pi_{A}-\lambda_{A}$.**
|  | $R_{A}\leq\sigma_{A}$ | $R_{A}\in(\sigma_{A},\sigma_{B})$ | $R_{A}\geq\sigma_{B}$ |
| --- | --- | --- | --- |
|  | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi_{A}}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\lambda_{A}}$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\rho_{A}}$ |
| $R_{B}\leq\sigma_{A}$ | $\operatorname*{{\mathbb{E}}}[R_{B}|\pi_{B}]$ | $\operatorname*{{\mathbb{E}}}[R_{B}|\pi_{B}]$ | $\operatorname*{{\mathbb{E}}}[R_{B}|\pi_{B}]$ |
| ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi_{B}}$, stop at $B$. | $+\operatorname*{{\mathbb{E}}}[c_{B}|\pi_{B}]$ | $+\operatorname*{{\mathbb{E}}}[c_{B}|\pi_{B}]$ | $+\operatorname*{{\mathbb{E}}}[c_{B}|\pi_{B}]$ |
| $R_{B}\in(\sigma_{A},\sigma_{B})$ | $\operatorname*{{\mathbb{E}}}[R_{A}|\pi_{A}]$ | $\operatorname*{{\mathbb{E}}}[\min\{R_{A},R_{B},X|\lambda_{A}\cap\lambda_{B}\}]$ | $\operatorname*{{\mathbb{E}}}[\min\{R_{B},y\}|\lambda_{B}]$ |
| ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\lambda_{B}}$, open $A$. | $+\operatorname*{{\mathbb{E}}}[c_{B}|\lambda_{B}]+\operatorname*{{\mathbb{E}}}[c_{A}|\pi_{A}]$ | $+\operatorname*{{\mathbb{E}}}[c_{B}|\lambda_{B}]+\operatorname*{{\mathbb{E}}}[c_{A}|\lambda_{A}]$ | $+\operatorname*{{\mathbb{E}}}[c_{B}|\lambda_{B}]+\operatorname*{{\mathbb{E}}}[c_{A}|\rho_{A}]$ |
| $R_{B}\geq\rho_{B}$ | $\operatorname*{{\mathbb{E}}}[R_{A}|\rho_{B}]$ | $\operatorname*{{\mathbb{E}}}[\min\{X,R_{A}\}|\lambda_{A}]$ | $\operatorname*{{\mathbb{E}}}[\phi_{C}(\{R_{A},R_{B},X\}|\rho_{A}\cap\rho_{B})]$ |
| ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\rho_{B}}$ | $+\operatorname*{{\mathbb{E}}}[c_{B}|\rho_{B}]+\operatorname*{{\mathbb{E}}}[c_{A}|\pi_{A}]$ | $+\operatorname*{{\mathbb{E}}}[c_{B}|\rho_{B}]+\operatorname*{{\mathbb{E}}}[c_{A}|\lambda_{A}]$ | $+\operatorname*{{\mathbb{E}}}[c_{B}|\rho_{B}]+\operatorname*{{\mathbb{E}}}[c_{A}|\rho_{A}]$ |

**Table 2: Table for Expected Payoff according to Strategy $D_{2}$. This table presents the expected total payoff for every possible joint distribution of box $A$ and $B$. In addition, $\rho_{B}=1-\pi_{B}-\lambda_{B}$.**
|  | $R_{A}\leq\sigma_{A}$ | $R_{A}\in(\sigma_{A},\sigma_{B})$ | $R_{A}\geq\sigma_{B}$ |
| --- | --- | --- | --- |
|  | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi_{A}}$, stop at $A$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\lambda_{A}}$, stop at $A$ | ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\rho_{A}}$ |
| $R_{B}\leq\sigma_{A}$ | $\operatorname*{{\mathbb{E}}}[R_{A}|\pi_{A}]$ | $\operatorname*{{\mathbb{E}}}[\min\{X,R_{A}\}|\lambda_{A}]$ | $\operatorname*{{\mathbb{E}}}[R_{B}|\pi_{B}]$ |
| ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\pi_{B}}$ | $+\operatorname*{{\mathbb{E}}}[c_{A}|\pi_{A}]$ | $+\operatorname*{{\mathbb{E}}}[c_{A}|\lambda_{A}]$ | $+\operatorname*{{\mathbb{E}}}[c_{A}|\rho_{A}]+\operatorname*{{\mathbb{E}}}[c_{B}|\pi_{B}]$ |
| $R_{B}\in(\sigma_{A},\sigma_{B})$ | $\operatorname*{{\mathbb{E}}}[R_{A}|\pi_{A}]$ | $\operatorname*{{\mathbb{E}}}[\min\{X,R_{A}\}|\lambda_{A}]$ | $\operatorname*{{\mathbb{E}}}[\min\{X,R_{B}\}|\lambda_{B}\cap\rho_{A}]$ |
| ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\lambda_{B}}$ | $+\operatorname*{{\mathbb{E}}}[c_{A}|\pi_{A}]$ | $+\operatorname*{{\mathbb{E}}}[c_{A}|\lambda_{A}]$ | $+\operatorname*{{\mathbb{E}}}[c_{B}|\lambda_{B}]+\operatorname*{{\mathbb{E}}}[c_{A}|\rho_{A}]$ |
| $R_{B}\geq\rho_{B}$ | $\operatorname*{{\mathbb{E}}}[R_{A}|\pi_{A}]$ | $\operatorname*{{\mathbb{E}}}[\min\{X,R_{A}\}|\lambda_{A}]$ | $\phi_{C}(\min\{y,R_{B},R_{A}\}|\rho_{A}\cap\rho_{B})$ |
| ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\rho_{B}}$ | $+\operatorname*{{\mathbb{E}}}[c_{A}|\pi_{A}]$ | $+\operatorname*{{\mathbb{E}}}[c_{A}|\lambda_{A}]$ | $+\operatorname*{{\mathbb{E}}}[c_{B}|\rho_{B}]+\operatorname*{{\mathbb{E}}}[c_{A}|\rho_{A}]$ |

Proof Of Corretness and Time Complexity
We now establish the optimality of the dynamic index in the multi-line setting, showing that probing nodes in the order of their current dynamic indices maximizes the expected utility.

###### Theorem C.7 (Dynamic Index for Multi-Line Costly Exploration) .

Given a Markovian multi-line costly exploration instance with $m$ lines, the optimal strategy for minimizing expected loss is to probe the uninspected but available nodes with the minimum dynamic index.

###### Proof.

Let $n^{*}$ denote the node with the smallest dynamic index before any nodes are probed, and let $\sigma^{0}_{n^{*}}$ be the value of this index.
Let $n\neq n^{*}$ denote another node. Without loss of generality, we treat the dynamic index of a node as the index of its first unopened child, conditioned on realized losses.
Let $\pi^{*}$ denote the policy that always probes the node with the smallest current dynamic index.

We prove that no strategy outperforms $\pi^{*}$ by induction on the number of nodes.

Base Case. For two nodes, it is immediate that $\pi^{*}$ is optimal.

Induction Step. Assume $\pi^{*}$ is optimal for $q-1$ nodes; we show it remains optimal for $q$ nodes.
If the optimal strategy begins by probing $n^{*}$, then by induction $\pi^{*}$ is already optimal.

Suppose instead that the best alternative strategy $\widehat{\pi}$ begins with node $n$ whose index $\sigma^{0}_{n}$ is larger than $\sigma^{0}_{n^{*}}$.
By the induction hypothesis, after probing $n$, strategy $\widehat{\pi}$ must follow $\pi^{*}$.
Thus $\widehat{\pi}$ proceeds as: probe $n$ until its index exceeds $\sigma^{0}_{n^{*}}$, then switch to $n^{*}$, and continue optimally.

Now construct a new strategy $\bar{\pi}$ that starts with $n^{*}$, switches to $n$ once its index exceeds $\sigma^{0}_{n^{*}}$, and then continues as in $\widehat{\pi}$.
Both $\widehat{\pi}$ and $\bar{\pi}$ explore the same nodes, but in different orders.
Since $\sigma^{0}_{n^{*}}<\sigma^{0}_{n}$, Lemma [C.6](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem6) implies that $\bar{\pi}$ achieves strictly less expected loss than $\widehat{\pi}$, contradicting the optimality of $\widehat{\pi}$.

Thus, by induction, $\pi^{*}$ is optimal for any number of nodes.
∎

Finally, we note that the dynamic index can be implemented in polynomial time and space.

###### Theorem C.8 (Polynomial-Time Implementation of Dynamic Indexing, Multi-Line) .

The dynamic index for the multi-line setting can be implemented in polynomial time and space.
Furthermore, preprocessing this policy takes $O(n\cdot|V|^{2}T)$ time and requires $O(n|V|^{2})$ space. At inference time, for each input $x$, the policy runs in $O(1)$ per node and $O(n)$ overall per input.

###### Proof.

Implementation. One can still use the idea of the dynamic index lookup table as in the single-line setting, since the loss function $\ell$ across lines is independent. Note that the optimal strategy, characterized by the dynamic index, visits at most a finite number of nodes, since the total number of nodes is finite. For each hypernode visit, it suffices to store the dynamic indices of the competing nodes and the index when the strategy last entered this hypernode.

Complexity.The space complexity of multi-line case is the same as the single-line setting, in that the space complexity is linear in the number of nodes. Similarly, the time complexity of preprocessing and during inference is the same as the single-line setting.
∎

###### Definition C.2 (Multi-Line Costly Exploration) .

###### Definition C.3 (Node with Random Cost) .

###### Lemma C.4 (Equivalent Single Node for Hypernode) .

###### Proof.

###### Lemma C.5 (Extending Dynamic Index to Hypernodes with Random Cost) .

###### Proof.

###### Lemma C.6 (Probing Equivalent Nodes) .

###### Proof.

###### Theorem C.7 (Dynamic Index for Multi-Line Costly Exploration) .

###### Proof.

###### Theorem C.8 (Polynomial-Time Implementation of Dynamic Indexing, Multi-Line) .

###### Proof.

### C.2 Extension to Directed Tree

Next, we introduce how to generalize the previous indexing policies from the multi-line setting in order to achieve theoretical optimal performance. Note that the directed tree case is equivalent to the directed forest setting (where each root has only outward edges), since we can add a dummy root node connecting all roots in the forest.

Graph Basics. We introduce some basics from graph theory in order to formally define tree contraction.

###### Definition C.9 (Component) .

Given an undirected graph $G=(V,E)$, a component of $G$ is a maximal connected subgraph $C=(V_{C},E_{C})$ such that:

- •
$C$ is connected: There exists a path between any two vertices in $V_{C}$.
- •
$C$ is maximal: No additional vertex $v\in V\setminus V_{C}$ can be included without losing connectivity.

A graph is said to be connected if it consists of a single component.

###### Definition C.10 (Induced Subgraph) .

Given a graph $G=(V,E)$ and a subset of vertices $V^{\prime}\subseteq V$, the *induced subgraph* $G[V^{\prime}]$ is the graph $(V^{\prime},E^{\prime})$ where:

$$ $\displaystyle E^{\prime}=\{(u,v)\in E\mid u,v\in V^{\prime}\}$ $$

That is, $G[V^{\prime}]$ contains all edges from $G$ whose endpoints are both in $V^{\prime}$.

We next define a minimal tree.

###### Definition C.11 (Directed Tree, Branch Vertex, Minimal Tree) .

A directed *tree* $\mathcal{T}$ is a connected DAG equipped with an orientation such that there exists a designated root vertex $r$ with the following properties:

- $\bullet$
every edge is oriented away from dummy root $v_{0}$ and root $r$.
- $\bullet$
for every vertex $v\in\mathcal{T}$, there exists a unique directed path from $r$ to $v$.

A *branch vertex* in a directed tree is a vertex with at least two outgoing edges.
A *minimal tree* is a directed tree whose proper subgraphs contain no branch vertices.

Generalizing Dynamic Indexing to Directed Tree. The key intuition behind our algorithm is that, after probing the root $r$ in a minimal tree, the remaining costly exploration problem reduces to exploring multiple lines, enabling us to apply our solutions in Section [C.1](https://arxiv.org/html/2509.22992v1#A3.SS1). We formally define the dynamic index for the directed tree setting.

###### Definition C.12 (Dynamic Index, Directed Tree) .

Consider a Markovian costly exploration problem with precedence graph $G=(\mathcal{V},E)$ structured as a directed tree.
Let $\mathcal{V}_{o}$ denote the set of opened nodes, and let the information set on the realized losses be
$\mathcal{I}_{o}:=\{v_{i}=\ell_{i}\;|\;i\in\mathcal{V}_{o}\}$.

For any unopened node $v_{i}$, its dynamic index is derived by applying Alg. [3](https://arxiv.org/html/2509.22992v1#alg3)
on the component of the induced subgraph $G[\mathcal{V}\setminus\mathcal{V}_{o}]$, conditioned on the current information set $\mathcal{I}_{o}$.

###### Proof.

When computing the dynamic index for a node inside the algorithm, the node is either the root of a minimal tree,
or the current graph reduces to a collection of disjoint lines. It suffices to show that the index is well-defined in both cases.

From the multi-line results, we know that if the graph(^6^66In our modeling, the structure of the graph is determined by the induced subgraph obtained after removing the dummy root $r$.) is a line or a set of isolated nodes, then the dynamic index is well-defined.
Moreover, the entire graph can be contracted into a single equivalent node with random cost (Lem. [C.4](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem4)).

We now define the dynamic index of the root $r$ of a minimal tree.
First, we contract the induced subgraph consisting of all vertices other than $r$ into a single equivalent node $\widehat{v}$ with random cost.
Given the current observed loss $x$, the equivalent loss for $r$ is computed as:

$$ $\displaystyle\Phi(x,r)=\min\Big\{x,\;\operatorname*{{\mathbb{E}}}[\min\{\ell_{r},x\}]+c_{r},\;\operatorname*{{\mathbb{E}}}[\min\{\ell_{r},x,\ell_{\widehat{v}}\}]+c_{r}+c_{\widehat{v}}\Big\}.$ $$

The three terms correspond to: (i) stopping without opening $r$,
(ii) opening $r$ only, and
(iii) opening $r$ while optimally exploring the remaining nodes.

Consequently, we define the dynamic index of $r$ as the smallest $x$ satisfying $\Phi(x,r)=x$.
This index is well defined since the minimal tree can be equivalently treated as a hypernode with $r$ as the first node and $\widehat{v}$ as the second node.
By Lem. [C.5](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem5), the dynamic index is therefore guaranteed to be well defined.
∎

In addition, we present our algorithm for computing the dynamic index for every node. The algorithm iteratively identifies and contracts the minimal subtrees of the underlying graph into directed lines,
thereby eliminating all branch vertices step by step. Notice that after inspecting a new node, we need to partially update the dynamic index of each of its children. (^7^77In the presence of already probed nodes, for any unopened node $i$, we apply the algorithm to the subtree rooted at $i$ to compute its dynamic index.) Please see Figure [3](https://arxiv.org/html/2509.22992v1#S5.F3) for an illustration.

Figure: Algorithm 3 Updating Dynamic Index in Forests

Proof of Correctness and Complexity.

###### Lemma C.13 (Time and Space Complexity of Dynamic Index, Directed Tree) .

The dynamic index for the directed tree setting (Algorithm [3](https://arxiv.org/html/2509.22992v1#alg3)) can be implemented in polynomial time and space. Furthermore, preprocessing this policy takes $O(n\cdot|V|^{2}T)$ time and requires $O(n|V|^{2})$ space. At inference time, for each input $x$, the policy runs in $O(1)$ per node and $O(n)$ overall per input.

###### Proof.

Preprocessing.
During the execution of the algorithm, each minimal tree can be identified using either a *BFS* or *DFS* traversal, both of which run in $O(n)$. Each tree traversal and possible contraction only needs to be performed once.

Similar to the multi-line case, we maintain an if-stop table based on the minimum loss and the loss of the current box. The main difference is that the computation of the dynamic index for a node now proceeds from the leaf nodes. Consequently, the preprocessing time remains $O(n\cdot|V|^{2}T)$, since each leaf has only one parent.

Space complexity.
We store the $\phi$-table for all possible states of each node, together with the graph structure required by the algorithm.
As argued in earlier sections, storing the $\phi$-table requires $O(n\cdot|V|^{2})$ space.

Time complexity.
At inference time, the complexity per input is $O(n)$, since we only need to perform table lookups.
∎

Since probing according to the latest dynamic index can probe at most all the nodes,
Algorithm [3](https://arxiv.org/html/2509.22992v1#alg3) is invoked at most once per node in the forest.
Thus, the overall runtime is still polynomial.

###### Theorem C.14 (Optimality of Dynamic Index, Directed Tree) .

The dynamic index defined in Def. [C.12](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem12) is optimal for probing in the forest setting.

###### Proof.

Each contraction step preserves the *equivalent loss table* and the *loss distribution* of probing the minimal tree.
Since the algorithm updates $\phi$ for the root of a minimal tree using the strategy that minimizes expected loss,
the $\phi$ values—and thus the dynamic indices—of its parent nodes remain unchanged under contraction.

This allows us to reduce the graph $\widehat{G}$ to one consisting only of *multiple lines and isolated nodes*,
on which the $\phi$ table and dynamic indices $\sigma$ can be computed directly.
Applying Thm. [C.7](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem7) to $\widehat{G}$ then establishes the optimality of the dynamic index in forests.
∎

###### Definition C.9 (Component) .

###### Definition C.10 (Induced Subgraph) .

###### Definition C.11 (Directed Tree, Branch Vertex, Minimal Tree) .

###### Definition C.12 (Dynamic Index, Directed Tree) .

###### Proof.

###### Lemma C.13 (Time and Space Complexity of Dynamic Index, Directed Tree) .

###### Proof.

###### Theorem C.14 (Optimality of Dynamic Index, Directed Tree) .

###### Proof.

### C.3 Costly Exploration with Skip

Next, we introduce the costly exploration setting that allows skipping, which corresponds to the graph structure given by the transitive closure of a directed line. We can still use dynamic programming to pre-compute the if-stop matrix and the equivalent-loss table. The difference is that, when computing the equivalent loss, we must enumerate over all possible next nodes rather than just one. More formally,

$$ $\displaystyle\Phi(X,R,v_{i})=\min\Big\{X,\min_{v\in C(v_{i})}c(v)+\operatorname*{{\mathbb{E}}}_{R_{v}|R}[\phi(\min\{X,R_{i}\},R_{i},v)]\Big\}$ $$

where $C(v_{i})$ denotes the set of nodes that are immediate children of $v_{i}$. Here, our definition of $\phi$ differs from that in the other sections: its third argument denotes the *current* node, its first argument denotes the minimum loss, and its second argument denotes the current loss.

Proof of Correctness and Complexity. Note that the only difference between our algorithm and the single-line case is that the set of candidate nodes to inspect grows from $O(1)$ to $O(n)$, which increases the preprocessing time by a factor of $n$. The inference time, however, remains the same as before, since we still only need to store, for each state, whether to stop at each possible value. Hence, we obtain the following lemma:

###### Lemma C.15 (Time and Space Complexity of Dynamic Index, Transitive Closure of Directed Line) .

The dynamic index for the transitive closure of a directed line can be implemented in polynomial time and space. In particular, preprocessing this policy takes $O(n^{2}\cdot|V|^{2}T)$ time and requires $O(n|V|^{2})$ space. At inference time, for each input $x$, the policy runs in $O(1)$ per node and $O(n)$ overall per input.

By Bellman’s principle of optimality, the equivalent loss is minimized at every step, from which the following result directly follows.

###### Theorem C.16 (Optimality of Dynamic Index, Transitive Closure of Directed Line) .

The dynamic index defined in Def. [C.12](https://arxiv.org/html/2509.22992v1#A3.Thmtheorem12) is optimal for probing in the transitive closure of a directed line.

###### Lemma C.15 (Time and Space Complexity of Dynamic Index, Transitive Closure of Directed Line) .

###### Theorem C.16 (Optimality of Dynamic Index, Transitive Closure of Directed Line) .

## Appendix D More Details from the Experiments

In this section, we provide additional experimental details omitted from the main text due to space constraints, along with background information on the early exit inference model.

### D.1 Background on Early Exit Models

Early-exit (EE) models extend standard deep neural networks by introducing multiple intermediate exit points, enabling inference to terminate early on “easy” inputs. An EE model typically consists of three components:
(1) a *backbone model*, corresponding to the original single-exit architecture;
(2) a set of *ramps*, i.e., intermediate exits attached to selected layers of the backbone; and
(3) an *exit decision policy*, which determines whether to stop at a given ramp and return its prediction. Importantly, only the exit policy remains controllable at inference time.

Figure: (a) Pipeline for Early Exit Models
Refer to caption: graph/Early_Exit.png

Thresholding.
A common exit policy is thresholding. Each ramp is associated with a fixed threshold. During inference, if the task-specific loss (or, equivalently, if the prediction confidence from the softmax output) at a ramp surpasses the threshold, inference halts and the prediction is returned. See Figure [7](https://arxiv.org/html/2509.22992v1#A4.F7)(b) for an illustration under classification tasks.

Markovian dependency.
EE models are typically designed to place ramps at “natural breakpoints,” such as layer groups in CNNs or transformer blocks. This induces a Markovian structure: the output distribution at each ramp depends only on its immediate predecessor, making the sequence of ramps analogous to a single directed line. This observation underlies our theoretical abstraction, where EE corresponds to the *single-line setting* of our indexing framework.

Notation.
Let $n$ denote the number of exits (with the final exit being the backbone output). For an input $x$, let $\ell_{i}(x)$ denote the task-specific loss at the $i$-th exit. We abstract each ramp as an *node*, which will serve as the atomic unit in our theoretical model.

### D.2 More Details on Early Exit Experiments

To capture the trade-off between accuracy and efficiency for EE models, we employ a latency-aware loss. The FLOP-based cost can be replaced with any hardware-invariant measure of latency, ensuring consistent policies across platforms.

###### Definition D.1 (Latency-Aware Loss) .

Given an input $x$, the latency-aware loss of using exit $j\leq i$ after evaluating $i$ exits is

$$ $\displaystyle\theta_{\lambda}(j,i)[x]:=(1-\lambda)\,\ell_{j}(x)\;+\;\lambda\sum_{k=1}^{i}c_{k},$ $$

where $c_{k}:=\textsc{FLOP}(m_{k})\geq 0$ is a proxy for the computation cost of sub-model $m_{k}$. The hyperparameter $\lambda\geq 0$ balances accuracy and latency.

Specifically, $\lambda$ is a tunable parameter, and the latency cost is measured as the ratio $\text{FLOPs(node)}/\text{FLOPs(backbone)}$. The accuracy component is defined as $1-\text{confidence}$, where confidence is the softmax probability of the predicted class.

The experimental traces employed in our study are taken from Dai et al. (2024), where data were collected on dedicated servers equipped with NVIDIA RTX A6000 GPUs (48GB memory), AMD EPYC 7543P 32-Core CPUs, and 256GB DDR4 RAM. The hardware configuration of our own experiments is specified in the main text. The model specifics and data characteristics of EE workloads are specified in Table. [3](https://arxiv.org/html/2509.22992v1#A4.T3).

**Table 3: Model Specifics and Dataset Characteristics of EE models.**
| Model | Dataset |
| --- | --- |
| Vision Models<br>VGG-11,13,16 | Object classification on 8 one-hour urban videos Agarwal & Netravali (2023); Hsieh et al. (2018),<br>sampled at 30 fps across day/night. Data are shuffled to discard temporal order and treated as independent images. |
| Language Models<br>BERT-base<br>GPT2-medium | Sentiment analysis on Amazon product reviews McAuley & Leskovec (2013)<br>and IMDB movie reviews Pal et al. (2020). |

###### Definition D.1 (Latency-Aware Loss) .

### D.3 Synthetic Experiments

The purpose of our synthetic experiments is to demonstrate that confidence thresholding strategies are not optimal for general distributions. Specifically, we visualize the if-stop matrices under various distributions to validate this claim. More specifically, the loss sequences are generated by independently sampling each loss from several independent distributions over $[0,1]$, with the latency cost at each ramp fixed to $0.1$ milliseconds.

Here, the purpose is not to emulate practical workloads—where ramp losses are typically positively correlated—but rather to illustrate the general structure of the optimal strategy through the analysis of the resulting if-stop matrices. As shown in the figure, the optimal policy does not coincide with any fixed thresholding rule that is oblivious to the current ramp state. Instead, the decision to stop or continue depends jointly on the realized losses at earlier ramps and the minimum loss across inspected nodes. This highlights the inherent limitation of threshold-based strategies, which, by construction, ignore such dependencies and are therefore provably suboptimal in the general setting.

Figure: (a) Truncated Normal $\mathcal{N}(0.5,0.5)$
Refer to caption: x9.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Q1. From what I gather, deploying T‑Tamer requires estimating the loss distributions Dᵢ and transition matrices Pᵢ  from a limited dataset, as well as discretizing the continuous loss space. These implementation steps appear essential for the policy’s effectiveness in practical settings, yet the paper doesn’t seem to discuss them in depth. What are your thoughts on this?
soundness: 3
strengths: S1. Original Problem Formulation:
This paper's most original contribution is the critical distinction between "no-recall" and "with-recall" strategies, which re-frames how efficiency trade-offs are understood and optimized.

S2. Theoretical Contributions:
The work provides strong theoretical guarantees, including an information-theoretic proof that "no-recall" policies are inherently suboptimal (cannot achieve any constant‑factor approximation to the offline optimal), and the development of a provably optimal dynamic indexing strategy for "with-recall" settings, which extends efficiently to complex DAG structures.

S3. Generality and Empirical Validation:
The T-TAMER framework is a general, model-agnostic "plug-in" solution, and its practical effectiveness is thoroughly validated through empirical experiments on CV/NLP benchmarks, demonstrating significant latency reductions with minimal accuracy loss.
summary: This paper explores balancing accuracy, latency, and cost in serving large ML models. Traditional cascaded inference runs models from simple to complex, exiting early for easy queries. The authors point out a flaw: once a complex model is used, systems must accept its output (“no-recall”). They propose T-Tamer, a framework viewing inference as a multi-stage decision process. Its key insight: allowing a “with-recall” strategy—choosing the best output at any stage—achieves an optimal trade-off.
weaknesses: W1. Theory–Reality Gap:
The paper's central claim of "provable optimality" rests on strong assumptions that may not hold in practice. The most critical is the Markov property, which assumes a model's loss at one stage only depends on the loss of the immediately preceding stage. In deep neural networks, dependencies are far more complex and long-range, mediated by high-dimensional hidden states.

W2. Limited Experiments and Baselines:
Although results show better accuracy–latency trade-offs, comparisons are mostly against weak “no-recall” baselines. The paper omits tests against state-of-the-art heuristics like confidence- or entropy-based early exits and evaluates only simple linear cascades, leaving complex DAG performance unverified.

---

confidence: 2
contribution: 2
initial_rating: 4
presentation: 3
questions: I would appreciate the authors’ responses to the four weaknesses outlined above.
soundness: 2
strengths: 1.	The paper provides theoretical foundations, particularly through its information-theoretic impossibility result for no-recall strategies. 
2.	By abstracting cascaded inferences as costly explorations over DAGs, the framework naturally captures diverse topologies (from linear cascades to tree structures).
3.	The work delivers strong theoretical guarantees through its dynamic indexing strategy, proving polynomial-time optimality for multiple DAG structures.
summary: This paper presents a theoretical framework designed to optimize bi-objective trade-offs in cascaded inference. The work includes a powerful information-theoretic proof demonstrating that common no-recall confidence-thresholding heuristics are fundamentally suboptimal. The central solution is the Dynamic Indexing Strategy, which the authors prove is both polynomial-time computable and provably optimal for making adaptive inference decisions across various DAG structures.
weaknesses: 1. The experimental evaluation is insufficient. It lacks comparison against critical baselines (e.g., standard thresholding, other learned routers) on the same Pareto frontier plots. Furthermore, the practical implementation and advantage of the core DAG-based routing mechanism remain unclear.
2. The theoretical guarantees presented in the paper appear to rely on strong assumptions, most notably the Markov property of the loss sequences. Could you please discuss how these assumptions might influence the experimental results and their generalizability?
3. Although inference is fast, the preprocessing time for the dynamic indexing policy can be computationally expensive. Could you explain how to solve the system with numerous sub-models (large $n$) requiring fine-grained discretization (large $|V|$).
4. There are some instances of missing punctuation. For example, the first paragraph and entry with "metrics" in Section 6 lacks necessary punctuation marks.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Can you show one setting where recall is not implementable and quantify the loss?
2. How robust is the policy to mild mis-specification of the loss distributions?
soundness: 3
strengths: - Clear formalization of cascaded inference as costly exploration over DAGs (line, transitive closure, tree).
- Strong, easy-to-communicate message: no-recall is information-theoretically too weak; recall fixes it.
- Algorithm has polynomial-time preprocessing and 𝑂(𝑛) per-query inference, so it’s not just theory.
summary: The paper studies accuracy, latency (more generally, bi-objective) trade-offs in cascaded / early-exit ML serving. It models routing + stopping over a DAG and shows a clean result: policies without recall cannot achieve any constant-factor approximation, while recall-based policies can achieve the optimal trade-off in polynomial time. The framework is instantiated as T-TAMER and applied to three common DAGs (line, transitive closure of a line, and directed tree), and experiments on synthetic data plus vision/NLP early-exit workloads show the expected accuracy–latency frontiers.
weaknesses: - Experiments are synthetic + standard EE workloads; no real production-style serving stack.
- Some assumptions (Markovian losses, known dists) could be made more operational for systems people.

---

confidence: 2
contribution: 3
initial_rating: 4
presentation: 3
questions: Please see my points above.

In addition, would it be possible to adapt the current framework to account for hard SLO constraints (such as serving latency / throughput) that are pervasive in real-world deployments?
soundness: 3
strengths: 1. The writing is clear. The authors abstract out the problem as a Markovian Costly Exploration and offered a principled solution to tackle this tradeoff.

2. The proposed solution also contains optimality guarantees.
summary: The paper introduces a theoretical framework to tackle trade-offs in ML serving when there are two objectives. One of the main claims is that it is impossible to achieve offline optimal performance without recall. Then the authors introduce a dynamic indexing strategy to tackle this challenge.
weaknesses: 1. It's not clear how one would attain such a loss distribution for complex data in practice in the proposed Markovian setting, the cost associated with it, and whether there is a cheap surrogate that can estimate this loss distribution.

2. This concern remains when the authors attempt to solve this via the dynamic indexing strategy. It is not clear whether discretization/quantization effort would be practical.

3. No recall is a weak baseline. What about heuristics-based approaches that don't have the theoretical optimality guarantees and does the proposed method achieve a significant improvement over them?

Minor issues:
Line 80: There is an extra precedence in the sentence.


Decision: Accept (Poster)