T-TAMER: Provably Taming Trade-offs in ML Serving
Authors: Yuanyuan Chloe Yang
Ruimin Zhang
Jamie Heather Morgenstern
Haifeng Xu
Venue: ICLR 2026 Poster (2026)
Keywords: Cascaded Inference
Early-Exit Models
Multi-Model Serving
Provable Optimality
Primary area: optimization
TL;DR: T-Tamer optimally balances accuracy–latency trade-offs in cascaded inference using recall-based dynamic indexing.

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.

Published as a conference paper at ICLR 2026
T-TAMER: PROVABLY TAMING TRADE-OFFS IN ML SERVING
Yuanyuan Yang*
Ruimin Zhang
Department of Computer Science & Engineering University of Washington
Department of Computer Science University of Chicago
Jamie Morgenstern
Haifeng Xu"
Department of Computer Science & Engineering University of Washington
Department of Computer Science University of Chicago
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 impor- tance 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 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 can- not 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 principled foundation for bridging heuristic practice with theo- retical guarantees the design of early-exit and cascaded models.
INTRODUCTION
As models continue to grow in scale, relying on a single model often fails to meet service-level objectives (SLOs), such 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.) (022).
Motivated by this observation, cascaded inference has emerged efficient large-scale model serving. The central idea is to maintain a collection of sub-models with varying complexity and invoke them adaptively in sequence. In practice, the inference platform receives stream of queries for a classification task together with specified SLOs, such as achiev- ing 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 princi- pled mechanism for efficient inference in modern machine learning systems.
widely adopted paradigm for
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 ac-
"Coresponding author.

---

Published as a conference paper at ICLR 2026
A
B
C
B
C
D
F
(a) Directed Line
(b) Transitive Closure of Directed Line
(c) Directed Trec
Figure I: DAG structures considered in this work: the directed line, its transitive closure, and the directed tree, which capture common topologies in up-cascade inference.
curacy-cost (where more accurate models generally incur higher computationaal/oonetayy 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 heuristie-drivert -riisiee- This gives rise to two fundamental issues: (1) lim- ited generalizability, as policy designed for one use case often fails to transfer to others, and (2) suboptimality, 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 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 the T-Tamer is agnostic that of the sub-models, enabling to operate plug-in component rather than a case-specific solution.
The key to T-Tamer strategy is a theoretical abstraction of routing and termination as multi- 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) and perfor- mance 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, [ the directed line, its transitive closure (allowing any skip while preserving order), and the directed tree (decision-tre) structure).
1.1 APPLICATIONS AND PRIOR WORK
The DAG topologies studied here naturally arise in practical inference systems. We review mod- els and prior work that instantiate these structures and connect them to research on multi-model inference, cascaded architectures, and adaptive computation. See App. A 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 net- works naturally induces Markovian dependencies, these approaches can be regarded as special cases of the cascaded inference framework. Representative examples include early-exit models (Teer- apittayanon 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 ex- plored how jointly train the cascades (Varshney Baral 2022), how design cascades with awareness of sestem-level constraints (Lebovitz et al. (202)) 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 fundamental theoretical gap.
As an aside, exhaustive search prohibitively time-consuming
cases.
2

---

Published as a conference paper at ICLR 2026
1.2 OUR RESULTS
We formulate the trade-off between the two objectives as a weighted sum of their proxy loss func- tions, with weights controlled by a tunable parameter X. More concretely, probing and consulting exactly one model on input x corresponds to the objective
(x(x) = (x) + (1- x)6((x)
where e [0. 1] and l2 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 (x) is always well-defined, whereas subtraction-ban 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 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 costly exploration problem over directed acyclic graph (DAG) that encodes both prece- dence constraints and inter-moder correlations:
Optimal Stopping Under Single Line Setting( $ We classify strategies based whether they allow recall, that is, whether previously explored sub-models can be revisited and selected after further exploration. Specifically, with-recall strategies in the single-line setting. We show that no-recall strategies fail to achieve any constant-factor approximation the optimal utility ($3) This impossibility is information-
develop separate theoretical frameworks for no-recall and
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.
General Costly Exploration for More General ( 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 topolo- gies (Fig. [c) and the transitive closure of the directed-ling case (Fig. lb). 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). The results show that recall-based strategies con- sistently deliver efficient accuracy-latency trade-offs. We now present our main results:
General- Purpose Tradeoff Tamer for Up-Cascade Inference. We introduce T-Tamer, princi- pled framework for taming bi-objective trade-offs in cascaded inference. Unlike heuristic-driven methods, T-Tamer is manel-ag 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.
No Constant-Factor Approximation for No-Recall Policy. We prove an ceermation-theoretie impossibility for no-recall strategies, showing that even in the directed-line case, such policies cannot achieve any constant-facto approximation to the optimal utility. This result shows that confidence- based heuristics (i.e., early-exit thresholds) for cascaded inference are inherently sub- optimal, motivating recall-based strategies with stronger guarantees.
aeetiinganddStooppiin 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.
Provably Efficient
3

---

Published as a conference paper at ICLR 2026
2 PROBLEM FORMULATION
In this section, we establish the notation, assumptions, and formal framework of costly exploration general DAGs, which serves the theoretical model for cascaded inference.
Notations.
Throughout, let n denote the number of sub-models in the cascade, and let X' denote the input space with E X. We use T to denote the number of samples used to fit the costly inspection strategy. We use & to denote the dominant loss function and to denote the secondary loss function, occasionally abusing notation by referring
the (inspection) cost.
We impose two standard assumptions in supervised learning (Goodfellow et al. 2016). First, all losses are strictly positive Second, inputs are drawn from distribution.
Assumption 2.1 (Loss). For any sub-model j E [n]] and input æ E X. the losses satisfy {z(x) > 0 and eg > Moreover, the cost loss 0j a constant independent of the input.
Assumption 2.2 (Distributional Assumption). Each T4, for sample index E (T], is assumed to be i..d. from a fixed distribution D over R
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 E [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 any sub-model j Si.
We formalize the costly exploration problem over a DAG. Specifically, we introduce a dummy root node vn the starting node of the policy, in addition the nodes representing sub-models.
Problem 2.4 (Markovian Costly Exploration). Consider set of n nodes V = { J. Each node v; is associated with a random loss t, drawn from a known distribution D, We also include designated null node vo, which connects to but to no other node, with to = 0. The nodes are organized into a directed acyclic graph G = =V,E), where edges encode:
Partial ordering. For any edge (vi, U2) E E,, if node vy is probed, then must be probed strictly before Ey. We denote this as 0 - Uj. Note that vs itself need not be probed unless Vj is selected.
Edge cost. For each edge (ve, U;) E E, probing vi right after incurs edge cost cli,j).
Markov property. For any adjacent nodes vs 4 Vj on along a directed path in G, the node losses satisfy the conditional independence E, L Eg lg.
policy a starts from uo and adaptively selects edges to probe subsequent nodes, deciding at each step whether to continue or stop. Let O(x)) denote the set of probed nodes and E(T) the set of edges traversed by т. The goal is to minimize the sum of node and edge losses weighted by the tradeoff parameter A: E[[ f((Es)ie0(m)) + =11 (1- -.eE(x) c(e)).
For no-recall, f equals the loss of the last visited node; for with-recall, equals mingeo()) l1
Finally, we describe how a general policy routes through the sub-models in the cascade (Figure
For each input Xx:
1. The policy observes the input and sets i +- 1.
2. The policy queries sub-model and observes its loss (x)
3. The policy decides whether to stop or continue:
Continue: Among the sub-models available after sub-model i, choose the next sub-model j to probe, incur edge cost (1 A)o(i, .j and return Step 2.
Stop: Return the prediction of a selected sub-model.
Figure 2: Costly Exploration for Cascaded Inference
Loss functions that may take negative values can be shifted transformed to satisfy this condition.
4

---

Published as a conference paper at ICLR 2026
3 ON COSTLY EXPLORATION POLICIES WITH NO RECALLS
In this section, we establish an coemmation-thhooeee bound showing that no-recall strategies cannot achieve 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 arranged in 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 predefined threshold (Dai 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 Rg with Markovian dependencies. Specifically, Ri+1 Xe; + (1 A)c(i 1, i) for E [n].
Problem 3.1 (No Recall Exit Problem). Let costs Rí Di:-... Dr be non-negative random variables drawn from known distributions Di...., Dr. with joint distribution exhibiting Marko- vian dependency, i.e., for all E [n), R4+1 conditionally independent of the past given R₃:
Pr( R1, ......: R.) Pr(Re+1 Ra), for all i.
decision maker sequentially observes R₁ to R,, After observing RS, they must either stop and pay the cost R3 irrevocably discard and continue. The goal is to design stopping rule ALG that minimizes the expected loss.
Ideally, ALG is benchmarked against the optimal loss attainable with perfect knowledge of all R. Definition 3.2 (Offline Optimal). The benchmark an oracle who knows all realizations in advance and selects min; R, incurring expected cost OPT = E/min, R²).
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 ALG is a-approximation for some 1.
E[ALG] S 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.1y no algorithu achieves bounded a-approximation ratio, even with n and bounded distributions.
Proof Sketch. Let and >> be arbitrary large constant. Consider the following random variables:
0 w.p.1 1
R1 =
w.p. 1.
R₂
a
w.p.
Under this construction, any algorithm achieves an expected reward of exactly 1/a², but a prophet achieves OPT 1/a3. This indicates an a-competitive ratio. This competitive ratio can be made arbitrarily large by increasing a.
This theorem establishes an information-theoretic impossibility: no no-recall costly exploration pol- icy can achieve any non-trivial approximation to the offline optimum. Importantly, this limitation not due to computational hardness (e.g., NP-hardnesss, but stems from the intrinsic information structure of the problem. One might ask whether it is possible to design algorithm ALG that approximates a restricted class of benchmarks. However, such benchmarks can be trivial to approx- imate-for example, in the construction above, all strategies achieve the same expected utility.
5

---

Published as a conference paper at ICLR 2026
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 pre- dictions 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 no-recall policies discussed earlier, we now turn to an- alyzing the efficiency of with-recall policies. The with-recall setting admits similar abstraction under costly exploration. The key distinction from the no-recall formulation is that the two losses cannot be collapsed into single objective: one loss R₂ Xe; is incurred at the nodes, while separate cost C: == (1 - A)e(i 1, is incurred along the edges when moving to the current node.
Problem 4.1 (With-Recal Costly Exploration). Let the costs of the nodes Rı...., Rr be non- negative random variables drawn from known distributions Di....; Dn. with joint distribution exhibiting Markovian dependency; i.e., Ri+1 is conditionally independent of the past given R4.
decision maker sequentially observes Rı,..., Ra, where each node i incurs cost Acz. After observing R2, the decision maker must either inccuricu total cost of minke(1) (t) Rx +x++(ee( Cj by selecting arg minge(1] Rk- continue. The goal is to minimize the expected total cost.
Since Markovian-corrchee distributions with continuous support cannot be directly represented without additional assumptions (Ethier & Kurtz 2009). we quantize them into a discrete domain and base decisions this discretization. Such discretization is standard in practice (e.g., grid search).
Hence, without loss of generality, we assume D D,,...,D. D, are discrete.
Note that the counterexample in Theorem 3.4 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 ac- cess to the joint distribution Pi....,D. Dn and achieves the minimum possible expected loss without observing realizations in advance.
By Bellman's principle of optimality, we derive 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 dynamic index determined by the current observation.
Algorithm 1 Costly Exploration via Indexing
Require: Nodes (ui,..., vn), edge costs {cI...., Cn). dynamic index a s) (Def. 4.4 for all and 8 E V.
1: Initialize minimum loss X co, i 1, (),
2: while > a do
3:
Pay to inspect node v; observe loss R,.
4:
X + min(X, R.}. a + 1, R.). i+i+1.
Update minimum loss. Update threshold.
5:
6:
7:
end while
8: Return node v, that has been inspected with the minimum loss.
Algorithm I 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 step can be represented stop/continue rule table dependent on (X, Rz).

---

Published as a conference paper at ICLR 2026
4.2 THE DYNAMIC INDEX
We now introduce the dynamic index, which serves as the core of our provably efficient strategy. At high level, the optimal policy stores, for every possible state (X, 1),, the correspond- ing 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 Rt takes values in a common finite support V = [UI,.... Uk For each i [n]], let p; denote the probability mass function (PMF) of RG with pi[Uy] Pr[ ug]- Let P; E Be the transition matrix from D, to Di+1. such that P++1 = P, P++1 The optimal policy π reduces to stopping rule that selects the node with minimum loss, use to denote it.
We now formally describe the dynamic programming procedure to compute the dynamic index function Any stopping time depends only the current minimum reward X, the most recent loss R,, and the next candidate index i + 1. We refer to the tuple (X, R,, i+1) as the algorithm's state, and proceed to derive the expected loss incurred at this state under a given stopping time T.
Definition 4.3 (Equivalent Loss). Given and (x. R we define the expected loss of the state (X, R,,1, following stopping rule T as t7 R4)
=(X.
-(X min ==1
('(X,
R; 1) SXX,R,11
(X,,
R2 +
Σ
cj]
2=1
In addition, (XX, R, x- R4-1,) min, 4 (X, 1,) denote the pected future loss following the optimal strategy T" starting at state (X, R2-1,
Let & be the expected loss of state, then & can be solved inductively using Bellman's principle of optimality: "5" (X, R,- = min xx + ER,RR__, (min X, Rs), RG, i + 1)]} where the first term corresponds to stopping immediately, and the second continuing and applying the optimal stopping time r* for the remaining boxes.
Importantly, for fixed R and i, there exists maximal X such that the decision maker indifferent between stopping and opening the next box. This value defines the dynamic index that governs our algorithm (Alg. [ More formally,
Definition 4.4 (Dynamic Index). Given any state (X, R4-1, 8), we define the dynamic index at the current state, denoted by (X, R,,1,)), as the smallest solution to:
T'
E
[
+ (a.1111..)
min j=1
R₂)
Σ j=
Cj = 0,
(1)
where T is the optimal strategy.
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, [T. Moreover, we show that the optimal strategy can be computed efficiently via dynamic programming. See Sec. for more details.
Theorem 4.5 (Optimality and Efficiency of Dynamic Indexing). Given the current state (X, RG, 1+), there exists a solution (1). This solution independent of the current minimum loss X and can be denoted by (R,, i+1). 1.).... The indexing policy that stops when a > X and contin- ues otherwise (Alg. [ achieves online optimality.
Furthermore, preprocessing this policy takes O(n (V) time and requires (n)) space. At inference time, for each input x, the policy runs in O(1) per node and (n)) overall per input.
The intuition behind the guarantee is that the stop/continue decision for each state (X, R2 i+1) can be precomputed and stored. At inference time, the algorithm queries this table in O(1) per step, yielding (()) time per sample. Further details are given in Lem. B.3 and Lem. B.4
Remark. In the single directed line setting, routing decisions required each step involves only a binary choice whether to proceed or not. Consequently, by Bellman's principle of optimal- ity, indexing strategy remains optimal under arbitrary correlation structures.
7

---

Published as a conference paper at ICLR 2026
5 EXTENSION: STRATEGIES OVER GENERAL DAGS
In this section, we extend the dynamic index to general DAGs. The generalized indexing policy re- mains 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 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-ine -nttn-- settings such as RLHF (Xiong al. 2023 crowdsourcing.
A
F
(a) Subtree Identification
(b) 1st Contraction
(c) 2nd Contraction
(d) Collapsed Line
Figure An Illustration on Node Contraction
Illustrated by Fig- the key idea of our generalized dynamic index is define contraction procedure that contracts a subtree into single node while preserving the equivalent loss table and loss distribution of the subtree. Concretely, 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 of the node's children.
Theorem 5.1 (Dynamic Indexing in Directed Trees: Optimality and Efficiency). There exist a gen- eralization of the dynamic indexing policy (Alg. B. which is theoretically optimal. Furthermore, preprocessing this policy takes O(n (V(T)) time and requires ((n)V(²²) space. At inference time, for each input x, the policy runs in O(1) per node and O(r) overall per imput.
We defer the details to Lem. C.13 and
and Thm. C.14 in the Appendix
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 generalization of the dynamic indexing policy, which is theoretically optimal. Furthermore, prepro- cessing this policy takes O(n² [T) time and requires O [[)) space. Ar inference time, for each input x. the policy in O(1) per node and (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, must enumerate over all possible next nodes rather than just the immediate successor. This increases the preprocessing time by factor of n. We defer the technical details to Section C.3
8

---

Published as a conference paper at ICLR 2026
EXPERIMENTS
In this section, we evaluate our dynamic indexing strategy RECALL, over real-world CV/ NI. early exit (EE) classification workloads. Early exit workloads selected as the primary experimental setting, corresponding to a dynamic indexing strategy over single directed line. The evaluation includes standard computationally efficient offline early exit benchmarks, which do not update their policies at runtime. The results demonstrate the generality of T-tamer, showing that it consistently matches exceeds the performance of the benchmark algorithms, particularly in high accuracy regimes, even though the best performing benchmark varies across workloads.
More details in Appendix D
6.1 IMPLEMENTATION DETAILS
We use the emror rate as a metric, defined as Err 1- Acc, where Ace is the empirical ac- curacy measured against the outputs of the backbone model, which regard upper bound achievable performance given the model's capacity. To demonstrate latency reduction, we normalize the achieved latency against the original latency.
Metrics.
Benchmarks. We compare the following baselines in our experiments:
(i) Score-based methods, where EE inference terminates once sub-model's score exceeds or falls below specified threshold. In our experiments, we adopt a confidence-based approach (Xin al. 2021), in which meffidennc-mmauuredd as the softmax probability of the predicted -tigger an exit when surpasses a predefined threshold. Since the latency of this algorithm strictly decreases the loss threshold increases, the threshold that meets a given latency requirement.
binary search to find
(ii) Rule-based methods, in which EE termination is governed by heuristic criteria. We adopt methods (Zhou et al. 20i0) trigger an
theoretically motivated exit once K consecutive sub-models produce sufficiently similar predictions. This consistency is measured by the change in predictive confidence/loss between adjacent sub-models; If this change below a threshold т, the stability counter C' is incremented. If C reaches K during inference, the model exits at the current sub-model; otherwise, it exits at the final sub-model. In our experiments, we set K 2, to obtain the fastest possible early exit.
6.2 EVALUATIONS
Pareto Frontier. In Figure 4 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. Our method attains approximately 95% accuracy with about 50% latency savings on CV workloads, and achieves around 75% accuracy with roughly 90% latency savings on NLP workloads. For detailed experimental settings, we defer to Appendix D.3 and for additional NLP workload results, defer to Appendix D.4
0.14
0.129
Error Rate
0.13
Error Rate
Error Rate
0.11
0.10
0.10
0.126
0.09
Error
0.07
0.06
0.06
0.123
0.05
25
55
0.02
20
40
60
30
0.120
0.122.9
26.2
26.5
Norm. Lat. (%))
Norm.
Lat. (%)
Norm. Lat. (%)
Norm. Lat. (%)
(a) VGG-13, Aubum
(b) VGG-13, Oxford
(c) VGG-11, Auburn
(d) VGG-11, Oxford
Figure 4: Pareto Frontiers for Vision Models. The frontiers highlight regions where latency
significantly reduced with only limited accuracy degradation. For instance, Fig. 4a shows that latency is reduced to 45% of the original, while sacrificing less than 7% accuracy.

---

Published as a conference paper at ICLR 2026
Comparison with Benchmark Models. Figure shows that T-Tamer consistently identifies the best points in the high-accuracy region relative to other benchmarks, while remaining competitive with the 1-threshold baseline for GPT-2 models and staying within 10% for BERT-based models in lower-accuracy regimes. It also consistently outperforms patience-based methods across NLP workloads. Notably, for BERT-based workloads, the Pareto front produced by 1-thresholding vio- lates monotonicity, indicating that deeper exits are not uniformly beneficial.
In such cases, adding recall provides a more effective signal, which aligns directly with our motiva- tion for designing t-tamer as recall-driven strategy.
0.30
0.35
1-Thr.
1-Thr. T-lamer K-1
1-Thr,
Error Rate
0.20
K=1
Error Rate
0.20
Error Rate
0.30
T-lmmr
K-1
Error Rate
0.25
K=1
T.hmeer
K=2
K=
0.10
0.15
0.10
0.10
0.05
0.00
0.00
0.00
40.0
80.0
40.0
80.0
20
60
Norm. Lat. (%)
Norm. Lat. (%)
Norm. Lat. (%)
Norm. Lat. (%)
(a) GPT-2, IMDB
(b) GPT-2, Amazon
(c) BertBase, IMDB
(d) BertBase, Amazon
Figure 5: Benchmark Comparison. The plot reports T-Tamer accuracy on the NLP tasks with additive discretization 0.001. X-axis: Normalized Latency of the backbone model; Y-axis: Error.
SSA Approximation Quality. Next, we present experimental results using soft state aggregation (SSn)(Duan et al. (019) based T-TAMER, introduced to accelerate its matrix- multipiillliiiiiinonnn step. The SSA parameter the number meta-states g. Under a fixed latency requirement, we ran T- TAMER for q E 50, 100, ... 800. We find that once g > 100, the accuracy remains within +0.02 of that achieved with the exact transition matrix. Details are deferred to App.
D.2
1.000
1.000
1,000
1.000
Accuracy
0.975
Accuracy
0.975
Accuracy
0.975
Accuracy
0.975
0.950
0.950
0.950
0.925
0.925
0.925
0.925
0.900
5 7
0.900
2 3
0.900
800
0.900
400 800
Estimation Error
Estimation Error
of Meta States
of Meta States
(a) 1.5ms (50%)
(b) 2.0 ms (66.7%)
(c) 1.5ms (50%)
(d) 2.0ms (66.7%)
Figure 6: Effect of SSA Approximation Granularity on Accuracy. The plot reports T-Tamer accuracy the Auburn dataset using a VGG-13 backbone with additive discretization 0.001. The horizontal line gives the true accuracy, and the shaded band shows the +0.02 margin. X-axis: # of Meta-states; Y-axis: Accuracy. Each caption indicates the latency in ms (% of time saved).
Figure illustrates the dependence of accuracy the number of meta-states and the estimation eтror. The performance remains largely stable across meta-state configurations. When the number of meta states reaches approximately 300, the SSA-based T-Tamer closely matches the performance of vanilla T-Tamer using the true transition matrices (i.e., up to 0.02%). This suggests that the SSA formulation provides an efficient surrogate for regimes with large transition matrices (i.e., 1000 x 1000 in our setting).
7 CONCLUSION
We introduced T-Tamer, a principled framework for taming bi-objective trade-off's in cascaded in- ference. By formulating routing and stopping costly exploration problem over DAGs, we devel- oped a dynamic indexing strategy that achieves provable optimality with polynomial ity. Experiments synthetic data and real-worlk CV/NLP benchmarks confirm that T-Tamer sistently delivers generality and favorable accuracy latency trade-offs, providing a purpose and efficient foundation for modern inference platforms.
complex-
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENT
We sincerely thank the anonymous reviewers of ICLR 2026 for their thoughtful feedback and con- structive suggestions, which motivated to incorporate soft state aggregation methods and addi- tional experiments, thereby substantially improving this work. This project was supported by NSF CCF-2045402 and NSF CCF-2019844.
A theoretical, TCS-oriented version of this work appears on arXiv as Markovian Pandora's 's Box and is released solely as technical report (not under submission). In contrast, this paper emphasizes the application and ML systems perspective and studies the minimization formulation of Pandora's 's box, whereas the arviv version considers the maximization setting. An earlier version appeared as Hold That Exit: Near Optimal Early-Exit Inference via Recall at the NeurIPS SPIGM 2025 Workshop.
YY gratefully acknowledges helpful discussions with Linda Cai, Li Chen, and Shuchi Chawla. YY also notes that portions of the system-level insights in this work were inspired by the Learning Directed Operating System (LDOS) NSF Expedition summer school.
REFERENCES
Marek Adamezyk, Maxim Sviridenko, and Justin Ward. Submodular stochastic probing on matroids. Mathematics of Operations Research, 1222:1002,,, 2016.
Neil Agarwal and Ravi Netravali. Boggart: Towards [General-Purpost acceleration of retrospec- tive video analytics. In 20th USENIX Symposium Networked Systems Design and Implemen- tation (NSDI 23), pp. 933-951, 2023.
Nir Ailon, Bernard Chazelle, Kenneth L Clarkson, Ding Liu, Wolfgang Mulzer, and C Seshadhri. Self-improving algorithms. SIAM Journal Computing, 40(2):350-375, 2011.
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.
Georgios Amanatidis, Federico Fusco, Rebecca Reiffenhäuser, and Artem Tsikiridis. Pandora's box problem over time. arXiv preprint arXivv2407. /5261, 2024.
Ali Aouad, Jingwei Ji, and Yaron Shaposhnik. The pandora's box problem with sequential inspec- tions. Available at SSRN 3726167, 2020.
Mário César Ugulino Araújo, Teresa Cristina Bezerra Saldanha, Roberto Kawakami Harrop Galvao, Takashi Yoneyama, Henrique Caldas Chame, and Valeria Visani. The successive projections algorithm for variable selection in spectroscopic multicomponent analysis. Chemometrics and intelligent laboratory systems, 57(2):65-73, 2001.
Mark Armstrong. Ordered consumer search. Journal of the European Economic Association, 15(5): 989-1024, 2017.
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning-theoreet foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pp. 213-274. PMLR, 2017.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning branch. In International conference machine learning, pp. 344-353. PMLR, 2018.
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.
Dirk Bergemann, Alessandro Bonatti, and Alex Smolin. The design and price of information. Amer- ican economic review, 108(1): (18(1)11488 2018.
Ben Berger, Tomer Ezra, Michal Feldman, and Federico Fusco. Pandora's 's'o problem with deadlines. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 20343, 2024.
11

---

Published as a conference paper at ICLR 2026
James Bergstra and Yoshua Bengio. Random search for prper-parameter optimization. Journal of machine learning research, 13(2), 2012.
Hedyeh Beyhaghi and Linda Cai. Pandora's problem with nonobligatory inspection: Optimal struc- ture and ptas. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp- 803-816, 2023.
Hedych Beyhaghi and Robert Kleinberg. Pandora's problem with nonobligatory inspection. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 131 1.31-132 132, 2019.
Sayan Bhattacharya and Sanjeev Khanna. Prophet inequalities with limited information. In Pro- ceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.
Shant Boodaghians, Federico Fusco, Philip Lazos, and Stefano Leonardi. Pandora's 's box problem with order constraints. In Proceedings of the 21st ACM Conference on Economics and Computa- tion, pp. 439 -5844588000 2020.
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 2000.
ACM symposium on Theory of computing, pp.
Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-paramert mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 2010.
Shuchi Chawla, Shaleen Deep, Paraschos Koutrisw, and Yifeng Teng. Revenue maximization for query pricing. Proceedings of the VLDB Endowment, 13(1):1-14, 2019.
Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang. Pan- dora's box with correlations: Learning and approximation. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pp. 1214-1225. IEEE, 2020.
Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos. Approximating pandora's 's box with correlations. arXiv preprint arXiv:2108, 12976, 2021.
Shuchi Chawla, Dimitris Christou, Amit Harlev, and Ziv Scully. Combinatorial selection with costly information. arXiv preprint arXiv:2412.03866 2024.
Yuxin Chen, S Hamed Hassani, Amin Karbasi, and Andreas Krause. Sequential information max- imization: When greedy near-optimal? In Conference on Learning Theory, pp. 338-363. PMLR, 2015a.
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.
Kenneth Clarkson, Wolfgang Mulzer, and C Seshadhri. Self-improving algorithms for convex hulls. In Proceedings of the First Annual ACM-SIAM Symposium Discrete Algorithms, pp. 1546-1565. SIAM, 2010.
José Correa, Pablo D. A. Foncea, Ruben Hocksma, and Tim Roughgarden. Prophet inequalities for independent random variables from an unknown distribution. In Proceedings of the 30th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), 2019.
José Correa, Anja Korol, and Ruben Hoeksma. Prophet inequalities and posted pricing mechanisms. Mathematics of Operations Research, (7()):2580-260) 2022.
Yinwei Dai, Rui Pan, Anand Iyer, Kai Li, and Ravi Netravali. Apparate: Rethinking early exits to tame latency- throouy- tensions in ml serving. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, pp. 607-623, 2024.
Jasper Dekoninck, Maximilian Baader, and Martin Vechev. unified approach to routing and cas- cading for llms. arXiv preprint arXiv:2410. 10347, 2024.
12

---

Published as a conference paper at ICLR 2026
Mahsa Derakhshan, Negin Golrezaei, Vahideh Manshadi, and Vahab Mirrokni. Product ranking on online platforms. Management Science, 68(6):4024 404410444444,,, 2022.
Jacob Devlin, Ming-Wes 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 (long and short papers), pp. 4171-4186, 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 (long and short papers), pp. 4171-4186, 2019b.
Bolin Ding, Yiding Feng, Chien-Ju Ho, Wei Tang, and Haifeng Xu. Competitive information de- sign for pandora's box. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 353-381, SIAM, 2023.
Laura Doval. Whether or not to open pandora's box. Journal of Economic Theory, 175:127-158, 2018.
Yaqi Duan, Tracy Ke, and Mengdi Wang- State aggregation learning from markov transition data. Advances in Neural Information Processing Systems, 32, 2019.
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.
Stewart N Ethier and Thomas G Kurtz. Markov processes: characterization and convergence. John Wiley & Sons, 2009.
Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Online stochastic matching: Beating 1 l/e. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016.
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.
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.
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.
Evangelia Gergatsouli and Christos Tzamos. Weitzman's rule for pandora's box with correlations.
arXiv preprini arXiv:2301. 00t33001.33344 13334, 2023.
John C. Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society: Series B (Methodological), 41(2):148-177, 1979.
John C. Gittins. Multi-armed Bandit Allocation Indices. John Wiley & Sons, Chichester, UK, 1989.
Ashish Goel, Sudipto Guha, and Kamesh Munagala. Asking the right questions: Model-driven optimization using probes. In Proceedings of the twenry-fitth ACM HCMOD-SIGACT-SICA. symposium on Principles of database systems, pp. 203-212, 2006.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1.
MIT press Cambridge, 2016.
Qiushan Guo, Zhipeng Yu, Yichao Wu, Ding Liang, Haoyu Qin, and Junjie Yan. Dynamic recursive neural network. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 5147-5156, 2019.
Anupam Gupta and Amit Kumar. Sorting and selection with structured costs. In Proceedings 42nd IEEE Symposium Foundations of Computer Science, pp. 416-425. IEEE, 2001.
13

---

Published as a conference paper at ICLR 2026
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.
Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and adaptivity gaps for stochas- tic probing. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pp. 1731-1747. SIAM, 2016.
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 Sympo- sium on Discrete Algorithms, pp. 1688-1702. SIAM, 2017.
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.
Rishi Gupta and Tim Roughgarden. A pac approach to application-specife algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 123-134, 2016.
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.
Elad Hazan, Adam Klivans, and Yang Yuan. Hyperparameter optimization: spectral approach. In International Conference on Learning Representations, 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Kevin Hsieh, Ganesh Ananthanarayanan, Peter Bodik, Shivaram Venkataraman, Paramvir Bahl, Matthai Philipose, Phillip Gibbons, and Onur Mutlu. Focus: Querying large video datasets with low latency and low cost. In 13th USENIX Symposium Operating Systems Design and Implementation (OSDI 18), pp. 269-286,77 2018.
Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Artificial intelligence and statistics, pp. 240-248 PMLR, 2016.
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.
Jon Kleinberg and Robert Kleinberg. Delegated search approximates efficient search. In Proceed- ings of the 2018 ACM Conference on Economics and Computation, pp. 287-302, 2018.
Robert Kleinberg and Sergei M. Krakovski. Multipl-chooiee prophet inequalities. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.
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.
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.
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.
Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. 1977.
Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. Prob- ability on Banach spaces, 4(197-266):1-2, 1978.
14

---

Published as a conference paper at ICLR 2026
Stefanos Laskaridis, Alexandros Kouris, and Nicholas D Lane. Adaptive inference through early- exit networks: Design, challenges and directions. Proceedings of the Sth International Work- shop Embedded and Mobile Deep Learning, pp. 1-6, 2021.
Luzian Lebovitz, Lukas Cavigelli, Michele Magno, and Lorenz K Muller. Efficient inference with model cascades. Transactions Machine Learning Research, 2023.
Hao Li and Xianwen Shi. Discriminatory information disclosure. American Economic Review, 107 (11):3363-3385, 2017.
Jian Li and Daogao Liu. Multi-token markov game with switching costs. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1780-1807. SIAM, 2022.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel fandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18(1) (8(1):6765668 2017.
Vasilis Livanos and Ruta Mehta. Minimization harder in the prophet world. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 424466, SIAM, 2024.
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.
Julian McAuley and Jure Leskovec. Hidden factors and hidden topics: understanding rating dimen- sions with review text. In Proceedings of the 7th ACM conference on Recommender systems, pp. 165-172, 2013.
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.0745/ 2025.
Lunyiu Nie, Zhimin Ding, Erdong Hu, Christopher Jermaine, and Swarat Chaudhuri. Online cas- cade 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 Machine Learning, volume 235 of Proceedings of Ma- chine Learning Research, pp. 38071-38090 PMLR, 21-27 Jul 2024.
Wojciech Olszewski and Richard Weber. A more general pandora rule? Journal of Economic Theory, 160:429-437, 2015.
Aditya Pal, Abhilash Barigidad, and Abhijit Mustafi. Imdb movie reviews dataset, 2020. URL
https: 21227/2m1y22m
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
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.
Horst D Simon and Hongyuan Zha. Low-rank matrix approximation using the lanezos bidiago- nalization process with applications. SIAM Journal Scientific Computing, 21(6):2257-22744 2000.
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.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
15

---

Published as a conference paper at ICLR 2026
Sahil Singla. The price of information in combinatorial optimization. In Proceedings of the twenty- ninth annual ACM-SIAM symposium on discrete algorithms, pp. 2523-25255552 2532. SIAM, 2018.
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 ma- chine learming, pp. 9036-9045 PMLR, 2020.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
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.
Surat Teerapittayanon, Bradley McDanel, and Hsiang-Tsung Kung. Branchynet: Fast inference via early exiting from deep neural networks. In 2016 23rd international conference on patlern recognition (ICPR), pp. 2464-2469. IEFE, 2016.
Neeraj Varshney and Chitta Baral. Model cascading: Towards jointly improving efficiency and accuracy of nlp systems. arXiv preprint arXiv:2210.05528, 2022.
Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph Gonzalez. Skipnet: Learning dy- namic routing in convolutional networks. In Proceedings of the European conference on computer vision (ECCV), pp. 409-424, 2018.
Richard R. Weber. On the gittins index for multiarmed bandits. The Anmals of Applied Probability, 2(4):1024-1033, 1992. doi: 10. 10. 4a0.211775
Gellért Weisz, Andras Gyorgy, and Csaba Szepesvári. Leapsandbounds: A method for approxi- mately optimal algorithm configuration. In International Conference on Machine Learning, pp- 5257-5265. PMLR, 2018.
Martin L Weitzman. Optimal search for the best alternative. Econometrica: Journal of the Econo- metric Society. pp. 641-654, 1979.
Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winngradd.. In Proceed- ings of the forty-fourth annual ACM symposium on Theory of computing, pp. 887-898, 2012.
Qian Xie, Raul Astudillo, Peter Frazier, Ziv Scully, and Alexander Terenin. Cost-aware bayesian optimization via the pandora's 's box gittins index. Advances in Neural Information Processing Systems, 37:1 15523-115562 2024.
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, Raphael Tang, Jaejun Lee, Yaoliang Yu, and Jimmy Lin. Deebert: Dynamic early exiting for accelerating bert inference. arXiv preprint arXiv:2004.12999 12993. 2020.
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 chupter of the association for computational linguistics: Main Volume, pp. 91-104, 2021.
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 rihf under kl-constraint. arXiv preprint arXiv:2312.11455 2023.
Qiqi Yan. Mechanism design via correlation gap. ACM Trunsactions on Economics and Computa- lion, 1(1):1-37, 2011.
Wangchunshu Zhou, Canwen Xu, Tao Ge, Julian McAuley, Ke Xu, and Furu Wei. Bert loses pa- tience: Fast and robust inference with early exit. Advances in Neural Information Processing Systems, 18:18330-1888 2020.
16

---

Published as a conference paper at ICLR 2026
LLM USAGE DISCLOSURE
The use large language models (LLMs) is permitted as a general-purpon assistive tool. In prepar- ing this paper, we used LLM (OpenAI's ChatGPT) to assist with polishing the exposition, includ- ing improving grammar, conciseness, and style in several sections of the manuscript. The LLM was not used for research ideation, technical contributions, or generation of novel results. All conceptual development, proofs, and experiments were conducted by the authors.
ETHICS STATEMENT
This work studies dynamic indexing strategies for cascaded inference. It does not involve human subjects, sensitive personal data, or proprietary datasets, and therefore raises direct ethical con- cerns. We believe the contributions align with the ICLR Code of Ethics, and we are not aware of any issues regarding fairness, privacy, security, or potential misuse beyond those generally applicable to large-scale machine learning research.
17

---

Published as a conference paper at ICLR 2026
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 (2024); Laskaridis et al. (2021) for 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 label confi- dence (Xin et al. 2202T), prediction entropy (Xin et al. 20200) 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 vis- ited exit- a setting where empirical evidence suggests that earlier exits can occasionally outperform later ones (Kaya et al., 2019).
Relation Pandora's 's Box and Prophet Inequality. The Pandora's Box framework (Weitzman, 1979 BBodaghians 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 un- der uncertainty. Specifically, our exit-with-recks model bears structural similarity to the Pandora's ''s Box problem, while the no-recall variant aligns closely with the Prophet Inequality setting- both sit- uated within cost minimization framework. However, precedence constraint on the order in which boxes (or exits) may be inspected, and (ii) a Markovian correlation that the underlying distributions conform to. for the aforementioned problems inapplicable.
setting imposes two key constraints: (i)
These constraints render existing algorithms
Since Weitzman's classic formulation (Weitzman 1979), Pandora's Box has been extended in numerous ways. Variants with order constraints (Boodaghians et al. (020) and correlated re-
wards (Chawla al., 2019; 2020 2021, Gergatsouli & Tzamos| (023) highlight the challenges
of adaptivity, with the latter proving constant- approximation NP-hard in the fully adaptive case. Online variants connect to bandits and set cover, yielding competitive or regret-minimizinn
algorithms (Gergatsouli & Tzamos 2022; Gatmiry et al. 2024). Nonobligatory inspection (Doval, 2018 Beyhaghi Kleinberg, 2019; Beyhaghi Cail [023] Fu et al.] 2023) further departs from Weitzman's ' ranking-based solution, with NP-hardness results and PTAS guarantees. Other exten- sions address partial openings (Aouad et al., 2220), generalized objectives (Olszewski & Weber, 2013). deadlines (Berger et al. (2024), time-dependent costs (Amanatidis et al. 2024). and strategic
information revelation (Ding et al. (023)..
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 maximiza- tion) guarantee //2-approximation in general settings, with improvements under additional struc- ture. Recent work has extended this line to matroids and combinatorial constraints (Kleinberg & Krakovski 2005 Bhhattchharaa & Khanna 2012), correlated and non-i.i.d. distributions (Correa
ct al.] [019: Yan 2011). and online matching and allocation problems (Esfandiari et al. 2017
Feldman et al. (016)) Further advances include connections to posted pricing in mechanism de-
sign (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 & Rough-
garden (2066) includes greedy heuristic selection, self-improving algorithms (Clarkson et al. 2010
Ailon et al., 201 T), and parameter tuning in optimization and machine learning Goel et al.
(2006):
Bergstra & Bengio (2012); Snock et al. (2012); Jamicson & Talwalkar (2016); Balcan et al.
2017
al. (2017); Kleinberg et al. (2017) : Hazan et al. (2018); Weisz et al. (2018) 8): Balcan et al.
2018);
Alabi al. (019); Balcan et al. (2019) Kotthoff et al. (2019); Sivaprasad et al. (2020).
Gittin's '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-tre ttre and skip-graph structures, the indexing strategy developed here appears to be novel, no analogous formulation has been established in prior work. Other recent studies have also
18

---

Published as a conference paper at ICLR 2026
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. Guupta & Nagarajan (2013) intro- duced this setting under matroid and knapsack intersection constraints, giving the first polynomial- time (2(1/k -appoxiiaap sequential posted price mechanism for k-matroid intersections. Adam-
czyk et al. (2016) extended the model to monotone submodular objectives, achieving tort approximation in general and a tighter t bound for linear objectives. Subsequent work Guupt (ct al. 2016 2017) investigated adaptivity gaps, quantifying the performance loss of non-adaptive strategies relative to optimal adaptive ones under prefix-closed constraints.
1/e
1
Beyond stochastic probing, other problems share similar information structures or solution concepts. including search (Armstrong) [0177; Kleinberg & Kleinberg, 2018), ranking (Derakhshan et al., 2022). Markov games (Li & Liu| 20 sorting and selection (Gupta & Kumar [200]). revenue max-
imization (Kleinberg al.) 2016 Chawla al. (019), and costly information acquisition (Charikar
et al. 2000;JChen et al. 2015b a
& Shi 2017 Singla 2018 |erggemann et al. 2018 Gupta et al.
2019
Chawla et al. 2024
19

---

Published as a conference paper at ICLR 2026
B MORE DETAILS FROM SINGLE LINE COSTLY EXPLORATION
B. MORE DETAILS FOR THE DYNAMIC INDEX
We introduce additional notation facilitate the formal analysis of the dynamic index. Specifically, we use + and & interchangeably to denote the equivalent loss.
Lemma B.1 (Properties of & and H,). Given any state (I, R,,
( &, is I-Lipschitz and monotone non-decreasing. Let H2(o, R(-1) = (xr, i2 -I, then Hc(-, R2-1) is nonnegative, 1- I-Lipschitz and monotone non-increasing.
For as the index (Def. 4.4 of the i-th node of the hypernode, then Φ(x, Ri-1, i) = I for any 2 02
Proof. Given any < b,
(b, R D(a, R1,, 2,
(a.
(a. min 3=1
2 min(b,
min ==
R2} - minfa,
I 6
where in the first inequality, we used that r" (a, 1, i) is suboptimal strategy for TT (b, Ri Ri-1, 1). Using the same reasoning, we have:
7'
(b,
(b,R, 1.5) min j=z
(bb R, = E min
R₂} +
Σ
Cj
(b..Ri-1.))
(b 1.5) min j=
E
min a
R3}
Σ C
R=
(a.R:-10
E
min
a,
min j=i
R₂}
+
Σ
cj = =(a (i-,,,
j=i
Thus, $ R2 is monotone non-decreasing. Now consider H;, we have
H. Ra-1) Hi R,-1) (bb, Ri-1, ((a, (o R;-1, - (b a) 0
where we use that (.-,R,,,,1 is I-Lipschitz. The above inequality implies that Hz 1) is I-Lipschitz and monotone non-increasing. Lastly, (nx, RG-1, i) x for all x Z a, follows from the that fact that a; is the smallest such that H, R = and H; is non-negative and monotone non-increasing.
Lemma B.2 (Properties of the Dynamic Index). Given a costly exploration problem with line prece- dence graph C [b....., bn), the dynamic index of every node E [n]] satisfies the following property: Given any state R;-1 the state of (i-1--th node,
oz(Ri-1,1) is nonincreasing as additional nodes are appended to L.
Let be the (random) index of the first node that has dynamic index larger than az (R;-1, i), then (,,,,1,)) depends only the (sub) hypernode E := (bi....,b b If 17 with probability 1, then a (R depends only on b;.
Proof. The first property holds because the optimal policy stops at the additional nodes only they yield lower expected loss. Consequently, appending nodes at the end of L can only de- crease the expected loss for any given state. Consequently, this operation leads to a nonincreasing dynamic index.
20

---

Published as a conference paper at ICLR 2026
The second property is due to that the optimal stopping time will stop (n 1)-th node, hence the dynamic index doesn't 't depend on any nodes starting from 1).
Lemma B.3, The smallest solution to 7 exists, and hence Definition 4.4 is well defined. Given current state (x, Ri-1, i), if the dynamic index o; I, then there exists some optimal stopping time T" (I, 1
Proof. Given any state (a, R4-1, 8), consider function
H1(x, R4-1) = (x, R, -
H.(x) is I-Lipschitz and monotone non-increasing by lemma B.1 Since H₂(O, R4-1) (0, R 2 and (t,,,, ((-1)) = 0, there exist some o; S. such that Hi RB-1) O.
This proves the existence of o,
Now, we show that if x = o, is positive, then there exists an optimal stopping rule that proceeds to open be Fix any such that Ø; >> Let 7 be the best strategy among all strategies that open b; To show that is indeed optimal, we show that
8 (o Ri-1, x (o,, i2 0
Assume towards contradiction that 5 0. We have
0 8 (6;, R4-1; ( R
I $ R4 g6 (a, (a.-6. e. Ri 1 (o,, R;-1,
= (D(as, R R, - ((a; R i)) + (6(0) R2-1, -x- 1r' (R R,)1,
2E
where we used Lipschitzness of & for the last inequality, and the first inequality comes from the fact that T" "a, -e, R2-1, i) is sub-optimal policy that opens by We have T" R2-1, 2 i since 0, is the smallest such that Ho, R4-1) = O. this implies that H1(o; e, R2 = 4 (a - e, R; i) - (a; - <) > meaning the optimal policy will accumulate more reward than current best, thus has to open b;- As c O, we get contradiction. On the other hand, Ha, R5-1) o6 R;-1, a; = 0 implies that the strategy that stops at b;-1 is also optimal. Thus, oe is indeed the value for which optimally.
indifferent between stopping and proceeding
B.2 PAYOFF TABLE
Lemma B.4 (Efficient Computation of Payoff Table), There is an efficient algorithm that computes ((z,8, 8, for all i, and s.
Proof. Now we give an efficient algorithm for computing the dynamic index. fact, we will give an algorithm that uses dynamic programming to compute ((r, Rą-1, for all triples (a, R4-1, i). Then, given the current state of the algorithm (z, R.),, the dynamic index a; for node is the smallest in the table where (xx, R;
Denote by T(x, R, three dimensional dynamic programming table. T(x, R4-1,4) i) will store the following information:
Each entry
1. Expected future loss: (xx, 14
2. Indicator: 1(x, 22 indicating whether the optimal policy will open in this state
3. The distribution of future random min reward RFRM (x. R; min (n, 1.() R where R 's are the correlated random rewards for mininodes that are yet to be opened given that the algorithm is at state (x, R i).
'The randomness comes from both random stopping time -" and correlated random variables R,
21

---

Published as a conference paper at ICLR 2026
Algorithm 2 Expected Equivalent Reward Computation, Single Line
Require: Ordered set of nodes {bi...., bn probing cost (ci..... Cn distributions of the random
payoff of nodes
1: Initialize 2
2: for E S do
D Base case: filling in T(s:n))
3: for E S do
4:
- Eyes [minn[, y} + c,) Pr(Rn = y)
5: if = > r then
6:
( sn 2, (z. 8,
7:
else
8:
( 8, z, (x,, 8, 8, =
9: end if
RERM (I. 8, n) = (z,, s, n) RR, and (pR( s, n) (x,,,,)) on
11: end for
12: end for
13: for i n 1.... do
Filling in T(:;;; for all i 1,..,,11
14:
for E do
15:
for E do
2 2 EE
Eyes
min {a, y, (FRM Sy, s 1)} + t. Crk sy Pr((
w)}
where By is the state that gives R, realization R₁ =
17:
if then 8x = 2, (xx s, =
18:
19:
else
20:
(x, x. (x, 8, =0
end if
22:
Calculate RFRM(Z, 9, and (FR 8, as follows: with probability Pr(ft = y), (F s, is (2,,,, s, min RERM (z, Sy, 1)} and (, is 1 s, (a +
(HR(I, Sy. +++1) end for 24: end for
end for
26: Return s,), for all x S. E S and i [n]
4. The distribution of future random cos
CpR (z, R4-1, Σ (a, Cj
Ej=i
Algorithm describes how to fill the dynamic programming table. Since random variables that appear in Algorithm 2 has finite support with size bounded by poly n), and any min operation
for random variables only has three or less arguments, follows that algorithm 2 takes polynomial time and space.
*The randomness comes from 7" being random stopping time.
22

---

Published as a conference paper at ICLR 2026
C MORE DETAILS COSTLY EXPLORATION OVER TREE
Notations In our analysis, Ae; always appears as a whole. Notice that our analysis, À not used as the tradeoff parameter but is applied for other purposes throughout our analysis the indexing policy. For graphs with a directed-tree constraint, since each node has exactly one parent, we can allocate the edge cost the node itself. In this way, inspecting node i reveals both its loss f and its inspection cost Q. Please see Fig. ass an example.
We first define the notion of hypernode, namely 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 instance of the costly exploration problem with nodes organized in a directed acyelic graph (DAG) G = (V, E), a hypernode is a subset of nodes H. := {UI,... (....... Um J S V such that the subgraph of G induced by H. denoted by L, forms directed path. That is, for each E [m 1m--1. 1}, the edge (Ve, U/+1) belongs to E.
C.I 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-Ling Costly Exploration). Given instance of the Markovian costly explo- ration problem ( (Prob. 2.4). we say is in a multi-line setting if the induced subgraph of G, excluding the dummy root node uo can be decomposed into collection of disjoint directed lines:
L [2,, Ls), L = [ - 12 -3
such that every node V belongs exactly line L5. Each line L, then be reparameterized as a sequence of hypernodes (Def. C.I. so that the costly exploration problem reduces to choosing among multiple directed lines.
c(H1)
V0
c(H2)
(A22)
CIA3)
c(A1)
A1
A2
A3
v0
e222)
CB33)
H1
H2
cB1
(a) Pipeline for Early Exit Models
(b) Exit by Thresholding
Figure 7: Hypernode View of multi-line setting. (a) illustrates how to allocate the edge cost as the inspection cost of the node (b) depicts they way we treat. During inference, the decision rule (0) is the only component that can be modified.
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 node with random cost, with reward and cost correlated. Definition C.3 (Node with Random Cost). node v is classified as a node with random cost if it is associated with a loss i and an inspection cost where both E and c are random variables drawn from known distributions D; and De, respectively. The inspection cost e may vary and can be correlated with the loss E; we denote their joint distribution as T.
Next, introduce how to equivalently represent hypernode where the dynamic index of the hypernode equals that of the equivalent node.
single node with random cost,
Lemma C.4 (Equivalent Single Node for Hypernode). For stopping time and hypernode H. : {Ur...., J, there exists a node with random cost (Def. CC3) such that following over H. yields the same loss distribution as inspecting G.
23

---

Published as a conference paper at ICLR 2026
Proof. Let L (fi,..., fn) be realization of the joint loss distribution in hypernode H. For each realization of L, the stopping time T 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 realiza- tions of L and the resulting loss and cost. When the joint loss is L, we assign the single node's 's loss as min & and the single node's 's cost as Σi- 1 Ci. where is the stopping time. The probability of each outcome matches the probability of L under the original hypernode's 's joint distribution.
From 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 H = {Ui,...,0o, ), where each node has 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 ā of individual nodes the index when there is only one node with random cost satisffiseies
o(1)) S ((02 (000 (n-1).
for any realized losses f Eu then the dynamic index of Us within the hypernode depends only on uy itself.
Proof. Since the e and 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.
We begin by presenting key lemma for our main theorem, which establishes that under certain Markovian correlations, the dynamic index remains optimal decision rule. We show this lemma by first principles, where we compare the utility of the ordering B C with that of B A < C' through case-by-case analysis of 9 outcomes from the joint distribution of A, B, and C and aggregate them by the law total expectation.
Lemma C.6 (Probing Equivalent Nodes). Consider three nodes A, B,C with random cost (Def. C.3 satisfying the following properties:
The loss and cost of are independent of the loss and cost of A;
The loss and cost (hence effective outcome) Cf depend on both A and B in Markovian fashion;
The dynamic indices satisfy (A) (B) < (CC) given any realizations of and B i.e., for any possible value x of A and value of B.
a(A) S (B) S (C() | la = =x, ln = v):
precedence constraint that A and must be probed before C:
then, conditioned on any competing loss X, the optimal probing strategy is A x B - C.
Proof. It's sufficient to compare two strategies: 1) DI B - A + C, and 2) D2 : A + B C. Notice that if X (A), then it's optimal to probe any node, then the ordering of the node doesn't 't matter. WLOG, we may assume X > o(A).
We first write down the expected loss according to ordering strategy Dj. we use notation in Table. D we have that this loss is equivalent to:
E(cgl + E[Rg TT. Pr[mø]
+ A E [ccl] E AAAAAAAA E/min ( RA, RB, vil AAAAal E[min{Ra: vlea. A Alll E [c]] + E[RA|=A|TA + Rmmin (y, RAlAAJAA + E[óc([ RA, RB, XYlea O px)]]]
+ +B
'Here, (CC) is random variable that depends A and B.
24

---

Published as a conference paper at ICLR 2026
Here, abuse the notation p. π À to denote both events and their probabilities, with the intended meaning clear from context; we use ó as similar definition to Φ (Lem. B.I). which denote the equivalent loss of probing C based on the observation. We also E n F denote the event that both and F oecur.
Similarly, using the notations in Table 2 we have that the expected loss according strategy D2 is:
B(cA] + TA B[Ra|Ta] + Xa [[min RA][
+ PA E cpl B E B TBl
AB [ X, R RB Opal (aoc(min RB, RAllPA O PB)
Notice that the last term of both payofts can be cancelled out, Also notice that the reservation value for box A and B satisfies:
El(an RRa)+ - cnl=0 =0
Plugging in the appropraite values of p; क. have:
E[ca] A T AT
E|ca| = (TB + AB)OB TB [[ - Aø B[R
Now, plugging the value of the expected cost and after simplification. we have that:
E[UTIL(22) - UTI.(D:)
TTBTA(O (a - ØB)
+ E Au σBl + (a RAlMA TBll
+ + - E min R., X3.X) A Aaal OB
R As (y, RA) [AA]
< A A R, X HAB nv OB + E[R + E[min (v. RA [AAl
where the last inequality follows by the property that [E[A/A S X <
Finally, we show that the last term is negative. Notice that:
E min RA, RB. X n AA]
on min (min [Ra, X} -on, Rn - Rn-onn)AaaaMn
I oB + m RA, X] оB + Rg 0B AB A
R AB] FEmmin(X, RA)AAl 0B <0
where the last equality follows from the independence of box A and B. Aggregating all of the above we have:
ElUTIL(D:)) UTIL(D;)) <.
Hence it's optimal to probe according to policy D2-
RA S GA AA
RA E (σA.O)) Xa
RA 2 OB PA
Rg S OAA
[[RB[TB] + ElcB TB)]
E E [T] E[cB [T
E [T]] + [E[cB|TB]
TB. stop at B.
RB E A. XB, open A.
E[RAITA
Eimin RA,, Rp, X X n ABH
Emmin y As
+ +EcB AB B[CA|TA]
+ LEcB + E[cA|AA]
|[cp//A] + 18 [CAA
RB 2 PB PB
E E[cn|pn]] [ [[
iiin X, RAHAA
E[ RR. X |P 0 Px)] +E|cn pn) cAlpa
((cnlen) + E(ca|AA]
Table 1: Table for Expected Payoff according to Strategy D₁. This table presents the expected total payoff for every possible joint distribution of box A and B. In addition, PA R AA-
25

---

Published as a conference paper at ICLR 2026
RA S σA TA stop A
RA E (A),OB)
RA 2 OB
AA, stop at A
PA
RB SAA
[ + +B(CA| [
[[min RA), MA)
B R T
TB
+ B[cAldal
+ E[cAlPA PAl
CB
RB E OB).
[[
E [[min RA HAAA
E[min X, R3 AB 0 PAA
AB
+ +E(cA| |TA
-EccaAAl
+ Ay + E(cAlPA
RB 2 PB PB
EIRA Aa + T
E [lmin (X, RA AAl
Φc {y. , Rg. RA |PA A PB) + +B|cgle + EE PAa
+Ecca|AA
Table 2: Table for Expected Payoff according to Strategy D2- This table presents the expected total payoff for every possible joint distribution of box A and B. In addition, PB
B XB.
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 o2e be the value of this index. Let n # n² denote another node. Without loss of generality, we treat the dynamic index of node as the index of its first unopened child, conditioned on realized losses. Let x² denote the policy that always probes the node with the smallest current dynamic index.
We prove that no strategy outperforms π by induction on the number of nodes.
Base Case. For two nodes, it immediate that π is optimal.
Induction Step. Assume n² is optimal for 1 nodes; we show remains optimal for nodes. If the optimal strategy begins by probing n² then by induction '² already optimal.
Suppose instead that the best alternative strategy म begins with node n whose index o is larger than o- By the induction hypothesis, after probing n, strategy must follow л². Thus proceeds as: probe until its index exceeds oQ.,, then switch to nz", and continue optimally.
Now construct new strategy that starts with n", switches to n once index exceeds of. and then continues as in 7. Both 7े and स explore the same nodes, but in different orders. Since og- < 0 Lemma Cmplies that र achieves strictly less expected loss than म, contradicting the optimality of Ā.
Thus, by induction, x² optimal for any number of nodes.
Finally, we note that the dynamic index can be implemented in polynomial time and space.
Theorem C.8 (Polynonial-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 (VT time and requires ((n)V(²) space. At inference time, for each input x, the policy runs in O(1) per node and (()) 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 across lines is independent. Note that the optimal strat- egy, 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 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 the single-line setting.
26

---

Published as a conference paper at ICLR 2026
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 equivalent 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 con- traction.
Definition C.9 (Component). Given undirected graph G (V, E.), a component of G is maximal connected subgraph = (Vc, Ec) such that:
C is connected: There exists path between any two vertices in Vc.
C is maximal: No additional vertex VVCc can be included without losing connectivity.
graph is said to be connected if consists of a single component.
Definition C.10 (Induced Subgraph). Given graph G (V, E) and subset of vertices V C V, the induced subgraph G[V') is the graph (V', E') where:
E' {(u, v) E E u.EEV)
That G[V'] contains all edges from G whose endpoints are both V
We next define a minimal tree.
Definition C.11 (Directed Tree, Branch Vertex, Minimal Tree). directed tree T connected DAG equipped with an orientation such that there exists designated root vertex r with the following properties:
every edge is oriented away from dummy root vo and root
for every vertex E there exists a unique directed path from T to U.
A branch vertex in a directed tree is a vertex with at least two outgoing edges. A minimal tree is directed tree whose proper subgraphs contain no branch vertices.
Generalizing Dynamic Indexing to Directed Tree. The key intuition behind algorithm is that, after probing the root r a minimal tree, the remaining costly exploration problem reduces to exploring multiple lines, enabling to apply our solutions in Section C.1 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 = (V, E) structured as a directed tree. Let V, denote the set of opened nodes, and let the information set on the realized losses be I, == {v:
v.).
For any unopened node Us its dynamic index is derived by applying Alg. 3n the component of the induced subgraph G[V Vol, conditioned on the current information set Io.
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 disjoint lines. It suffices to show that the index is well-defined in both cases.
From the multi-line results, we know that the graph is a line or a set isolated nodes, then the dynamic index is well-defined. Moreover, the entire graph can be contracted into single equivalent node with random cost (Lem. C.4).
We define the dynamic index of the root of minimal tree. First, contract the induced subgraph consisting of all vertices other than r into a single equivalent node T with random cost. Given the current observed loss v, the equivalent loss for is computed as:
(σx, r) = min E[min((pr x1 + cr, Elmin(&,, 4ill + o + +
In our modeling, the structure of the graph is determined by the induced subgraph obtained after removing the dummy
27

---

Published as a conference paper at ICLR 2026
The three terms correspond to: (i) stopping without opening (ii) opening only, and (iii) opening r while optimally exploring the remaining nodes.
Consequently, define the dynamie index of the smallest satisfying (2 r) This index well defined since the minimal tree can be equivalenty treated as a hypernode with r as the first node and i as the second node. By Lem. C.5 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 algo- rithm iteratively identifies and contracts the minimal subtrees of the underlying graph into directed lines, thereby climinating all branch vertices step by step. Notice that after inspecting new node, need to partially update the dynamic index of each of its children. Please see Figure 3 for an illustration.
Algorithm 3 Updating Dynamic Index in Forests
Require: An instance of a Markovian costly exploration problem with precedence graph G struc- tured as forest.
1: G f- G, 1.
2: while there exist minimal trees in G do
3:
for each minimal tree T; with root r3 do for every possible loss realization e, r; do Condition on lyp, compute & and the dynamic index o for all states of nodes in
4:
5:
T (rs).
6:
Contract T \ {ri} into a single node C and compute its loss and cost distribution
conditioned lr.-
7: end for
8: Update G accordingly.
9: end for
end while
11:
Compute the dynamic index for the remaining nodes.
Proof of Correctness and Complexity.
Lemma C.13 (Time and Space Complexity of Dynamic Index, Directed Tree). The dynamic in- dex for the directed setting (Algorithm 3 can be implemented in polynomial time and space. Furthermore, preprocessing this policy takes Onn -V("T) time and requires (n)) space. At inference time, for each input z, the policy runs in ((1) per node and (n)) overall per imput.
Proof. Preprocessing. During the execution of the algorithm, each minimal tree can be identified using either BFS or DFS traversal, both which run in O(n). Each tree traversal and possible contraction only needs 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 node now proceeds from the leaf nodes. Consequently, the preprocessing time remains On IV[TT), since each leaf has only one parent.
Space complexity. We store the o-table for all possible states of each node, together with the graph structure required by the algorithm. As argued in earlier sections, storing the ø-table requires O(n [V122 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 invoked most once per node in the forest. Thus, the overall runtime is still polynomial.
In the presence of already prohed nodes, for any unopened node i, apply the algorithm to the subtree rooted i compute its dynamic index.
28

---

Published as a conference paper at ICLR 2026
Theorem C.14 (Optimality of Dynamic Index, Directed Tree). The dynamic index defined in Def. C.12 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 ø for the root of minimal tree using the strategy that minimizes expected loss, the & values and thus the dynamic indices- of its parent nodes remain unchanged under contraction.
This allows to reduce the graph & to one consisting only of multiple lines and isolated nodes, on which the e table and dynamic indices can be computed directly. Applying Thm. C.7 G then establishes the optimality of the dynamic index in forests.
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 directed line. We can still use dynamic program- ming to pre-compute the if-stop matrix and the equivalent-loss table. The difference is that, when computing the equivalent loss, must enumerate over all possible next nodes rather than just one. More formally,
+ (X, 0z) = min {x.
min c(v) + E R,
(ommnn (X, RR}, R₁, v)]
vEC(o.)
R.
where C(s)) denotes the set of nodes that are immediate children of v;. Here, our definition of 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 candidate nodes to inspect grows from ((1) to O(n), which increases the preprocessing time by 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, 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² -V("T) time and requires ( 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 '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 is optimal for probing in the transitive closure of a directed line.
29

---

Published as a conference paper at ICLR 2026
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.I PRELIMINARIES 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) 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.
Candidate Exits
Input
Laver
Layers
Layers,
Layers
Layyar
(OI)) Ramps
Hiddon
Off-Ramp
Exit Decision
Ramp:
Rump:
Ramps
Ramp-
Logits
Hidden Layers
Logits) p
Exit
Input Layers
Pass Next Layer
(a) Pipeline for Farly Exit Models
(b) Exit by Thresholding
Figure 8: Exit decisions in early-exit models. (a) shows the pipeline of an early-exit model; (b) illustrates the exit decision process under thresholding strategy. During inference, the decision rule (0) is the only component that can be modified.
Thresholding, A common exit policy is thresholding. Each ramp is associated with fixed thresh- old. During inference, if the task-specific loss (or, equivalently, if the prediction confidence from the softmax output) at ramp surpasses the threshold, inference halts and the prediction is returned. See Figure (b) for an illustration under classification tasks.
Confidence and entropy based thresholding strategies arise as natural variants of "no-recall" poli- cies, under the directed line T-TAMER setting. T-TAMER maintains stop/no-stop table indexed by the loss at each submodel. If the table assigns "no-stop" to loss values above given loss threshold, we recover the usual confidence-based rule by setting loss = confidence. Similarly, we recover the entropy based rule by setting loss entropy, for nonnegative entropy functions.
Markovian dependency. EE models are typically designed to place ramps at "natural breakpoints," such layer groups in CNNs transformer blocks. This induces Markovian structure: the output distribution at each ramp depends only on its immediate predecessor, making the sequence ramps analogous single directed line. This observation underlies our theoretical abstraction, where EE corresponds to the single-line setting of our indexing framework.
Notation. Let denote the number of exits (with the final exit being the backbone output). For an input x, let (xx denote the task-specific loss at the i-th exit. We abstract each ramp as an node, which will serve the atomic unit in our theoretical model.
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-invarian 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 S i after evaluating exits is
0x 0x(i,) :1 x)) +
Cke
1=
30

---

Published as a conference paper at ICLR 2026
where c₁ FLOP(ma) is proxy for the computation cost of sub-model my. The hyperpa- rameter balances accuracy and latency.
Specifically, X is tunable parameter, and the latency cost is measured the ratio FLOPs(node)/FLOPSS) FLOPsbbackoone). The accuracy component defined as 1 confidence, where confidence is the softmax probability of the predicted class.
D.2 ACCELERATING T-TAMER VIA SOFT STATE AGGREGATION
In this section, we provide an overview of how to use soft state aggregation, a common technique in Markov decision processes for accelerating computations the transition matrix when the state space contains a large number of discrete values.
To begin with, we briefly outline the existing algorithmic implementation and pinpoint its runtime bottleneck. For the implementation, we employ matrix-based variant of T-TAMER for the sin- gle directed-line setting (Algorithm 2). formalized in Algorithm 4 The procedure first discretizes the loss distribution, and estimates the transition matrix over the discretization support V at each ramp. Then, performs a backward dynamic- progriimrogggmninggggg step that employs matrix operations to compute the equivalent losses table by comparing the losses incurred under continuation versus stopping. This yields the optimal stop/no-stop decision rule at every state of the algorithm, which subsequently applied to all trajectories to determine their exit points. In this algorithm, the dominant computational cost arises in line which requires multiplying two [V] x [V] matrices.
Algorithm T-Tamer Learning Phase
Require: N samples of loss trajectories over n ramps; discretization set V of loss values, costs
{c} [c]]-.
Discretize all accuracy values into [V] bins.
O(Nn) D O(N)
2: Accumulate empirical joint counts over N samples.
3: For each ramp i, construct transition matrix P; E RVXX/V
D +
4: Define matrices X, S E [V][X as follows:
X x
S = for all x, V,
compute 4, == min
(X min(X, as the element wise minimum of and
@([V)9) to form both matrices
5: for iuri=n n - ,,....I. do
6:
Compute continuation value via matrix multiplication:
C = P. 0 + ci11
D @((V)) (Matrix Multiplication)
7: Compute stopping value:
S = S.
b (((V))
8: Elementwise minimization and policy extraction:
Φ = min Ct),
stop; 1[S C.).
P e((V))
9:
end for
10:
Evaluate policy on all N trajectories to determine exits.
> O(Nn)
This algorithm runs efficiently when [ is small. When our additive discretization parameter satisfics < 0.001, we typically have V| ~ 1000. In this regime, approximating the transition matrix using the product of two low-rank matrices can substantially accelerate the computation.
Remark. the algorithm 4, we estimate the cost each matrix multiplication (MM) as ((())s) In fact. modern fast matrix multiplication algorithms reduce this runtime to ((VV)) for some exponent w E [2, 2.38); see Williams (2012) for a general discussion how the exponent w used in algorithmic runtime analyses.
31

---

Published as a conference paper at ICLR 2026
Next, present the intuition behind soft state aggregation. In our setting, state corresponds to an index of the transition matrix- equivalently.ly.. discretized loss level in the support V. The intuition of state aggregation is to reduce the size of the state space by clustering together states of the transition matrix that behave similarly. We adapt the soft state aggregation (SSA) mechanism Duan et al. (2019), to replace the transition matrix in line SSA provides a probabilistie, model- based refinement of the classical idea: instead of assigning each state to single cluster, it associates each state with multiple meta states through a membership distribution. The transition matrices are then expressed in terms of these meta states of much smaller rank.
The soft aggregation model is parameterized by d = |V rggregation distributions and q disaggre- gation distributions, where d is the total number of states (i.e., discrete loss value) in a Markov chain and y < is the number of (latent) meta states. The model is parameterized by an aggregation map U E Rdxa, where each row specifies how a raw state distributes its probability mass over the meta- states, and disaggregation map V E Roxd, where each row gives distribution from meta-state back to the original states. Under this formulation, the transition kernel admits the approximation
P P UVT, where U1, = ld, and
V = 1g
In the above formula, bp l stands for an all one vector of dimension d and g. respectively.
Algorithm& 5 Soft State Aggregation for Transition Matrix (Duan et al. 2019)
Require: Empirical count matrix N, number of meta-states q, threshold 6n = 10-6
1: Estimate the matrix V.
(i) Form N = [ddia((N") (N (NT1,)) 1,)]-1/2, Apply truncated singular value decomposition (Simon
& Zha 2000 N and extract the top q right singular vectors hi..... hag Construct
D [diag(h) h1 - hgg E [dx((-1),
> (
(ii) Apply a vertex-finding algorithm to the rows of H to obtain y extreme points by.... b >> O(dg") via succesive projection algorithm (SPA) (Araújo et al. 2001
(ii) For each 1 j S d, compute
arg min rERe
(1
Σ rk
Clip negative entries 0, renormalize to unit nn-nomm, and denote the result by wy Let W [ T E Rdx Compute (diag(?) [[diia((" 1,)12/27,, normalize each
V. column to have unit formm, let the resulting matrix be D ((dg²) via Least Square.
2: Estimate the matrix U.
Form empirical transition probability matrix P = [diag (11,)1 NN and compute
-= PV PPPD()
> (dd.))
3: return matrices V. O.
Next, we outline the intuition of algorithm for estimating the factors U and V from the empirical state-transition counts N. This method has two stages: 1) apply spectral methods to extract the top d left and right singular vectors. 2) introduce a linear reparameterization that transforms these singular vectors into consistent estimators of U and V. The resulting estimates yield an approximate transition model that integrates directly into the downstream components of T-TAMER.
Remark. Our implementation differs from Duan et al. (2019) in two ways: we do not compute the full SVD in Step (i), and we use successive projection instead of vertex hunting in Step (ii). Both choices reduce the overall time complexity. Diagonal-matriss operations merely perform row- or column-wise scaling and therefore do not incur the cost of full matrix multiplications.
Forr simplicity of presentation, reuse the symbol V to represent both the loss-value support and the disaggregation matrix; the distinction should be clear from context.
32

---

Published as a conference paper at ICLR 2026
D.3 EXPERIMENT SETUP
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.
Dataset. The experimental traces employed this work are sourced from Dai et (2024), where data were collected on dedicated servers equipped with NVIDIA RTX A6000 GPUs (48GB mem- ory), 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 Table. 3
Model
Dataset
Vision Models 1GG-11,13,16
Object classification 8 one-hour urban videos (Agarwal & Netravali 2023 Hsich et al. 2018), sampled at 30 fps across day/night. Data are shuffled to discard temporal order and treated independent images.
Language Models
Sentiment analysis Amazon product reviews MccAuley & Leskovec 2013) and IMDB movie reviews (Pal et al. 2020
BERT-base
GPT2-medium
Table 3: Model Specifics and Dataset Characteristics of EE models.
Hyperparameters for Pareto Front. In our experiments for plotting the Pareto Front, we quantize the stochastic loss component using an additive discretization with step size 0.1 from [0, 1], and estimate the corresponding transition matrix from the induced discrete loss support. The cost term is retained in its continuous form and integrated directly into the objective. Furthermore, accuracy is evaluated on the same dataset for fitting the dynamics. To construct the Pareto frontier, we perform logarithmic grid search over range of À values and evaluate the resulting accuracy-latency trade- offs, yielding an empirical approximation of the frontier.
Hyperparameters for Benchmark Comparison. For benchmark comparisons with single- threshold and patience-based based baselines, we discretize the stochastic loss component using an ad- ditive scheme with step size 0.001 over j0. 1], and estimate the corresponding transition matrix from the induced discrete loss trajectory. We adopt an 80/20 split: 80% the data is randomly selected for fitting the T-tamer and the benchmarks, and the remaining 20% is used for generating the plot. All other settings follow the previously specified hyperparameters the Pareto frontier.
Hyperparameters for SSA Approximation. For the SSA implementation, adapted from Duan et al. (2019). For SSA augmented T-tamer, we replace the matrix multiplication step in the T-tamer fitting with first compute G = VT 6, and then compute UG. More details are in App. D.2
the version
low-rank matrices. The product is computed in stages:
We discretize the stochastic loss component using an additive scheme with step size 0.001 over the interval [0, 1], and we estimate the corresponding transition matrix from the induced discrete loss trajectory. We use an 80/20 split, as described previously.
The SSA hyperparameter is the number of meta-states q. Under a fixed latency requirement, we fit SSA augmented T-tamer with q E (50, 100,... 800). To quantify the estimation quality, we use the t.x norm between the estimated transition matrix and the true transition matrix as the x-axis. This error may exceed 2 because the estimated matrix not necessarily row-stochastic.
Hyperparameters for If-Stop Matrix. In our experiment for visualizing the if-stop matrix, we quantize the stochastic loss component using an additive discretization with step size 0.1 from [0, 1], and estimate the corresponding transition matrix from the induced discrete loss support. The re- maining iistribution-relatte hyperparameters are specified the subtitle of Fig. TO
33

---

Published as a conference paper at ICLR 2026
D.4 MORE DETAILS ON PARETO FRONT
In Figure 9 we also evaluate the dynamic index strategy on NLP classification tasks using the IMDB (Pal al. 2020) and Amazon Review (McAuley & Leskoved, 2013) datasets. with BERT- base
(Devlin et al. 2019a) and GPT-2 (Radford et al. 2019) as backbone models for EE.
Error Rate
0.36
0.32
0.28
0.32
Error Rate
0.30
0.29
Error Rate
0.252
0.256
0.28
0.248
0.24
0.28
0.20
0.20
0.240
15
25
35
35
9.0
9.8 10.6
9.2 9.3 9.5 9.6 Norm. Lat. (%)
Norm, Lat. (%)
Norm. Lat. (%)
Norm. Lat. (%)
(a) BertBase, IMDB
(b) BertBase, Amazon
(c) GPT-2, IMDB
(d) GPT-2, Amazon
Figure 9: Pareto Frontier for Language Models. The frontier shows sharp accuracy-latency
trade-off region, where latency is reduced by to 90%.
D.5 VISUALIZING IF-STOP MATRIX
The purpose of our synthetic experiments is to demonstrate that confidence thresholding strategies are not optimal for general distributions. Specifically, we visualize the it- matrices under various distributions to validate this claim. More specifically, the loss sequences are generated by indepen- dently 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-wwere ramp losses are typically positively correlated-but rather to illustrate the general structure of the optimal strategy through the analysis of the resulting it-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 harshhld-bbssed strategies, which, by construction, ignore such dependencies and are therefore provably suboptimal in the general setting.
Min Loss Realized
Stop
Min Loss Realized
0:
Stop
Min Loss Realized
Stop Continue
0.2
Continue
0.2
Continue
0.2
0.4
0.4
0.4
0.6
0.6
0.6
0.8
0.8
0.8
1.0
1.0
1.0
0.2
0.40.6 0.8 1.0
0.2
4.. 0.8 1.0
0.2
0.40.6 0.8 1.0
Current Ramp State
Current Ramp State
Current Ramp State
(a) Truncated Normal (V(05, 0.5)
(b) Truncated LogNormal (N 1)
(c) Uniform (0, 0.5)
Figure 10: Visualization of the If Stop matrix for Synthetic Data
34


Reviews:
[{"review_id": "KYjXT6iElH", "reviewer": "Reviewer_nhrK", "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.", "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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. Original Problem Formulation:\nThis 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.\n\nS2. Theoretical Contributions:\nThe 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.\n\nS3. Generality and Empirical Validation:\nThe 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.", "weaknesses": "W1. Theory–Reality Gap:\nThe 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.\n\nW2. Limited Experiments and Baselines:\nAlthough 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mY8zD8iHcV", "reviewer": "Reviewer_nk36", "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.", "questions": "I would appreciate the authors’ responses to the four weaknesses outlined above.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tThe paper provides theoretical foundations, particularly through its information-theoretic impossibility result for no-recall strategies. \n2.\tBy abstracting cascaded inferences as costly explorations over DAGs, the framework naturally captures diverse topologies (from linear cascades to tree structures).\n3.\tThe work delivers strong theoretical guarantees through its dynamic indexing strategy, proving polynomial-time optimality for multiple 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.\n2. 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?\n3. 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|$).\n4. There are some instances of missing punctuation. For example, the first paragraph and entry with \"metrics\" in Section 6 lacks necessary punctuation marks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fhhtYPFc5X", "reviewer": "Reviewer_m2Vw", "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.", "questions": "1. Can you show one setting where recall is not implementable and quantify the loss?\n2. How robust is the policy to mild mis-specification of the loss distributions?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clear formalization of cascaded inference as costly exploration over DAGs (line, transitive closure, tree).\n- Strong, easy-to-communicate message: no-recall is information-theoretically too weak; recall fixes it.\n- Algorithm has polynomial-time preprocessing and 𝑂(𝑛) per-query inference, so it’s not just theory.", "weaknesses": "- Experiments are synthetic + standard EE workloads; no real production-style serving stack.\n- Some assumptions (Markovian losses, known dists) could be made more operational for systems people.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Sz6T70bF0A", "reviewer": "Reviewer_kRkc", "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.", "questions": "Please see my points above.\n\nIn 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?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 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.\n\n2. The proposed solution also contains optimality guarantees.", "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.\n\n2. 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.\n\n3. 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?\n\nMinor issues:\nLine 80: There is an extra precedence in the sentence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)