Pith. sign in

REVIEW 5 major objections 6 minor 102 references

This paper proves that recall—the ability to revisit earlier models in a cascade—is both necessary and sufficient for provably optimal online trade-offs in ML serving, and gives a polynomial-time dynamic-index policy that achieves it.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-04 14:47 UTC pith:J34VM3Y3

load-bearing objection The paper's only solid content is the single-line result, which the authors admit is the Gittins index; the tree and transitive-closure generalizations are not established and one is internally contradictory. the 5 major comments →

arxiv 2509.22992 v2 pith:J34VM3Y3 submitted 2025-09-26 cs.LG cs.GT

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

Yuanyuan Yang , Ruimin Zhang , Jamie Morgenstern , Haifeng Xu This is my paper
classification cs.LG cs.GT
keywords cascaded inferenceearly exitdynamic indexrecallcostly explorationoptimal stoppingMarkovian dependenceaccuracy-latency trade-off
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

T-Tamer formalizes accuracy–latency trade-offs in cascaded machine learning as a Markovian costly-exploration problem over a DAG of sub-models, and argues that the ability to recall earlier models is what separates provably good serving from inherently poor serving. For no-recall policies, which must return the last model consulted, the paper proves an information-theoretic impossibility: no algorithm, even with full knowledge of the loss distributions and unlimited computation, can achieve a constant-factor approximation to the offline-optimal trade-off, even with only two models. For recall-based policies, it constructs a dynamic-index stopping and routing rule—computed by backward dynamic programming over a quantized loss alphabet—and proves it is optimal among all online policies for directed lines, directed trees, and transitive closures of directed lines, with polynomial preprocessing and linear per-query runtime. The paper validates the policy on synthetic data and on early-exit vision and language workloads, showing consistent accuracy–latency improvements over threshold heuristics. If the proofs hold, the practical consequence is that recall is not a luxury but a necessary ingredient for provable guarantees in cascaded serving.

Core claim

The central claim is a classification result: in the paper's model of cascaded inference, recall is both necessary and sufficient for provable performance. Necessity comes from a two-node construction in which every no-recall stopping rule incurs expected loss 1/α² while a prophet who knows all losses pays 1/α³, so the approximation ratio can be made arbitrarily large; this is information-theoretic, not computational. Sufficiency comes from the dynamic-index policy: for each state—the current minimum loss, the most recent loss, and the next candidate node—a threshold σ is precomputed so that stopping exactly when the current minimum falls below σ is online-optimal. The paper proves this for

What carries the argument

The dynamic index σ(R_i, i+1) is a stopping threshold for each state of the Markovian loss process: it is the smallest loss value x at which the expected cost of continuing (future node losses plus edge inspection costs) exactly equals x, making the decision maker indifferent between stopping and probing. The full policy is built backward by dynamic programming over a quantized support of the loss distributions: at each state the algorithm stores the expected future loss, whether to open the next node, and the distribution of the future minimum loss and cumulative cost. For directed trees, subtrees that are minimal lines are contracted into equivalent single nodes with random cost; for the t

Load-bearing premise

The optimality and impossibility proofs both depend on the assumption that ramp losses form a Markov chain along every directed path—ℓ_i ⊥ ℓ_k | ℓ_j—which the paper asserts from network architecture rather than verifies empirically; if real cascade losses have longer-range dependencies, the dynamic-index policy's guarantees no longer follow.

What would settle it

Measure the conditional mutual information I(ℓ_3; ℓ_1 | ℓ_2) on a real early-exit model (e.g., BERT or VGG with exits at three layers); a nonzero value on a nontrivial fraction of inputs falsifies the Markovian premise. Alternatively, run any no-recall stopping rule on the paper's two-node construction with α large; if its expected loss is within a constant factor of E[min(R1,R2)], Theorem 3.4 is false.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Confidence-threshold early-exit and cascade heuristics, which are no-recall policies, cannot have any constant-factor approximation to the offline-optimal trade-off under the paper's model; deployments relying on them inherit an unbounded worst-case gap.
  • A recall-based serving policy can be precomputed in polynomial time—O(n·|V|²T) for lines and trees, O(n²·|V|²T) for transitive closures—and runs in O(n) per query, so the optimal guarantee does not require sacrificing serving latency.
  • For the three DAG families, the dynamic-index policy is the best possible online policy for the weighted accuracy–latency objective; no other online algorithm can achieve lower expected loss.
  • The policy is learned from input–output pairs of all sub-models and is agnostic to their internal design, so it can be added as a plug-in routing/stopping component to existing cascades.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The Markovian conditional-independence assumption (ℓ_i ⊥ ℓ_k | ℓ_j along every path) is asserted from the layered architecture of early-exit models, not measured; if real ramp losses violate it, the optimality proofs would need modification. A natural next step is to measure conditional dependence on actual early-exit backbones.
  • Section 5.2's 'skipping' semantics for the transitive closure of a line sits uneasily with Problem 2.4, which defines every edge as a precedence constraint requiring the predecessor to be probed; interpreting one consistently would restrict the DAG class covered by the optimality result or require redefining edge semantics.
  • The impossibility theorem is against the offline prophet benchmark; it remains open whether no-recall policies could achieve constant-factor guarantees against a weaker online benchmark, or whether a bounded-memory recall buffer (last k models) would restore constant factors.
  • The dynamic-index construction is a natural relative of classical optimal-search index rules; the paper's contraction and enumeration techniques may transfer to other sequential decision problems with precedence constraints and Markovian correlations, though that transfer is not established here.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

5 major / 6 minor

Summary. The paper proposes T-TAMER, a framework for routing and stopping in cascaded inference, formalized as a Markovian costly-exploration problem over DAGs. It proves that no-recall strategies cannot achieve any constant-factor approximation to the offline optimum (Theorem 3.4), and develops dynamic-index policies claimed to be online-optimal for directed lines (Theorem 4.5), directed trees (Theorem 5.1), and transitive closures of directed lines (Theorem 5.2), all with polynomial-time preprocessing. Experiments on early-exit vision/NLP workloads show Pareto frontiers of the proposed policy. This review focuses on whether the DAG generalizations and the associated optimality proofs are formally established.

Significance. If the DAG results were correct, this would be a substantial contribution: it would provide a unified, provably optimal indexing framework for common cascaded-inference topologies, with an information-theoretic separation between recall and no-recall strategies. The paper also connects to the Gittins/Weitzman literature and provides a concrete dynamic-programming instantiation. However, as detailed below, the two advertised DAG extensions are not currently established: the transitive-closure model is inconsistent with the paper's own precedence definition, and the exchange lemma underpinning the tree/multi-line optimality proof contains an invalid step and an unstated independence assumption. The single-line with-recall result is plausible and useful, but it is a considerably weaker contribution than the abstract and introduction claim.

major comments (5)
  1. [Problem 2.4 and §5.2] The transitive-closure model is internally inconsistent. Problem 2.4 states that every edge is a precedence constraint: if v_j is probed, then v_i must be probed strictly before v_j. In the transitive closure of a line, every earlier node has an edge to every later node, so probing v_j forces all v_1,...,v_{j-1} to be probed. Section 5.2 claims this graph 'allows skipping while preserving order,' which is the opposite. Thus Theorem 5.2 and Lemmas C.15/C.16 analyze a problem that is not the one defined in Problem 2.4. The paper must either redefine the edge semantics (e.g., distinguish precedence edges from optional jump edges) or withdraw the skipping claim.
  2. [Lemma C.6] The exchange proof contains an invalid inference. In the final displayed chain, the authors show E[min{RA,RB,X}|λB∩λA] ≤ E[RB|λB]+E[min{X,RA}|λA]−σB, and then conclude the right-hand side is <0. This does not follow from E[RB|λB] < σB and E[min{X,RA}|λA] < σB: the sum of two numbers each below σB need not be below σB. The inequality direction is also opposite to what is needed for the bracketed term to be negative. Since Lemma C.6 is the engine for Theorems C.7 and 5.1, this gap undermines the optimality proof for the multi-line and directed-tree settings.
  3. [Lemma C.6 and Problem 2.4] The lemma assumes that the loss and cost of B are independent of the loss and cost of A. Problem 2.4's Markov property only asserts conditional independence along a directed path (ℓ_i ⊥ ℓ_k | ℓ_j for v_i ≺ v_j ≺ v_k); it says nothing about independence between sibling branches or across disjoint lines. The multi-line and tree theorems therefore rely on a structural assumption that is neither stated in Problem 2.4 nor argued for in the applications. Without it, the claimed generality of the DAG extensions is unsupported.
  4. [Algorithm 2 and Theorem 4.5] The DP pseudocode does not implement the stated Bellman recursion under Markovian dependence. In the base case (line 4), z is computed with the unconditional distribution Pr(R_n=y), independent of the conditioning state s; the recursive case (line 16) also uses Pr(R_i=y) rather than a transition probability conditional on the previous realized loss. The transition matrices P_i introduced in §4.2 are never used. Additionally, Theorem 4.5 states the policy 'stops when σ > X and continues otherwise,' reversing Algorithm 1's stopping rule (while X > σ continue). These issues call into question the claimed O(n·|V|^2T) implementation and the correctness of the indexing policy as written.
  5. [Abstract, Theorems 3.4 and 4.5] The 'necessary and sufficient' framing conflates two different benchmarks. Theorem 3.4 is a lower bound against the offline prophet optimum, whereas Theorem 4.5 establishes optimality against the online optimal policy with known distributions. These are not the same object; with nonzero inspection costs, even a with-recall online-optimal policy can be far from the offline optimum, as the paper itself notes in §4.2. The abstract's statement that recall is 'both necessary and sufficient' for constant-factor or exact optimality is therefore overclaimed unless the comparator is stated precisely.
minor comments (6)
  1. [Definition 4.4 and Algorithm 1] The notation for the dynamic index is inconsistent: Definition 4.4 uses σ_i(X,R_{i-1},i), while Algorithm 1 calls σ(i+1,R_i) and the text interchangeably writes σ(R_i,i+1). Please unify the state representation.
  2. [Appendix C and Algorithm 2] Algorithm 2's title says 'Expected Equivalent Reward Computation' although the objective is loss; the terminology should be 'Loss' or 'Cost.' Also, the heading 'Proof Of Corretness' contains a typo.
  3. [Appendix C, Lemma C.6] The symbol λ is overloaded: in the main text it is the tradeoff parameter, while in Lemma C.6's tables λ_A and λ_B denote events. This is very confusing and should be renamed (e.g., E_A, E_B).
  4. [Section 6] Figures 4 and 5 show only the proposed policy's Pareto frontier, with no comparison to thresholding/no-recall baselines and no error bars. The experimental section cannot substantiate the claim that recall-based strategies 'consistently yield efficient accuracy-latency trade-offs' without such a comparison.
  5. [Theorems 4.5, 5.1, 5.2] The preprocessing bound 'O(n·|V|^2T)' includes T, described as the number of training samples, but Algorithms 2 and 3 do not take T as input. The role of T in the complexity statement should be clarified or removed.
  6. [Section 3.2] There is a typo: 'we concluded by showing' should be 'we conclude by showing.'

Circularity Check

1 steps flagged

Benchmark equivocation makes the 'recall necessary and sufficient' headline circular; the DP/index derivation itself is self-contained.

specific steps
  1. other [Abstract; §3 (Def. 3.2, Thm. 3.4); §4.1 (Def. 4.2, Thm. 4.5)]
    "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. ... Note that the counterexample in Theorem 3.4 continues to yield arbitrarily large approximation gaps even when recall is allowed."

    The impossibility half is benchmarked against the offline prophet optimum OPT = E[min_i R_i] (Def. 3.2), while the with-recall optimality half is benchmarked against the 'online optimal' algorithm that knows the joint distribution but not the realizations (Def. 4.2). These are different notions of 'optimal trade-off.' Section 4.1 explicitly concedes that the offline gap persists even with recall, so recall is not necessary for constant-factor approximation to the offline optimum. The sufficiency claim holds only for the paper's self-defined online-optimal benchmark, i.e., the optimum of the very DP the paper solves. The headline 'necessary and sufficient' therefore reduces to an equivocation between two benchmarks rather than a derived equivalence, making the recalled-based 'attainment' tr

full rationale

The paper's theoretical core is a finite-horizon Markovian optimal-stopping dynamic program. Definition 4.4 defines the dynamic index via the optimal policy τ*, and the appendices prove existence and the threshold property through Lipschitz/monotonicity arguments; this is a representation theorem for the DP value function rather than a cyclic derivation. The optimality proof does not rest on any self-citation: the Gittins-index reduction in App. A is an acknowledgment, not a load-bearing appeal, and the cited prior work is independent. The experiments fit empirical transition distributions and then evaluate; that is a statistical/validation gap, not a fitted-parameter-called-prediction circularity. The main circularity is the benchmark equivocation in the headline claim: no-recall impossibility is against the offline prophet, while with-recall optimality is against the online-optimal benchmark, which is by Definition 4.2 the best policy in the exact model the DP solves. Since §4.1 concedes the offline gap persists with recall, the 'necessity and sufficiency' dichotomy is not a derived equivalence but an equivocation. Separately, the §5.2 'skipping' claim contradicts Problem 2.4's precedence semantics, and Lemma C.6 assumes sibling independence absent from the model; these are correctness gaps, not circularity, and do not raise the circularity score further.

Axiom & Free-Parameter Ledger

4 free parameters · 5 axioms · 1 invented entities

The theoretical results assume known Markovian loss distributions, positive input-independent costs, a hand-chosen λ, and a finite quantization grid. The empirical implementation additionally fits transition matrices from data. The hypernode contraction is a new algorithmic device used to extend the index to trees.

free parameters (4)
  • Tradeoff weight λ = user-tuned in [0,1]
    Balances accuracy against latency in the scalarized objective; any 'optimal trade-off' frontier is parameterized by this hand-chosen value.
  • Quantization support V = not specified
    Continuous losses are discretized to a finite support; the DP complexity O(n|V|^2T) and the resulting policy depend on this arbitrary grid, with no error analysis.
  • Latency cost proxy c_k = FLOPs(m_k)/FLOPs(backbone)
    Chosen by hand to approximate latency; not measured wall-clock time, and hardware-dependent effects are asserted away.
  • Estimated transition matrices P_i = empirical frequencies from T samples
    The optimality theorem assumes known distributions; in practice the DP consumes empirically fitted transition probabilities, and no sample-complexity or regret bound is provided.
axioms (5)
  • domain assumption All losses are strictly positive and costs are input-independent (Assumption 2.1)
    Underlies the well-defined objective and the DP; may fail for calibrated confidence scores and input-length-dependent latency.
  • domain assumption Inputs are i.i.d. from a fixed distribution (Assumption 2.2)
    Needed for the distributional learning story; real serving workloads exhibit drift and temporal correlation.
  • domain assumption Ramp losses form a Markov chain: ℓ_i ⊥ ℓ_k | ℓ_j along paths (Problem 2.4)
    Load-bearing for the entire dynamic-index derivation; asserted from layered architecture without empirical verification.
  • domain assumption The fitted distribution equals the true distribution
    The optimality guarantee is stated for known distributions; the gap introduced by estimating P_i from T samples is not analyzed.
  • ad hoc to paper Finite support after quantization is sufficient
    The theory assumes discrete losses; the quantization grid is chosen without an error bound, so optimality holds only for the quantized chain.
invented entities (1)
  • Hypernode no independent evidence
    purpose: Contracts a directed-line subgraph into a single node with equivalent loss and cost distributions, enabling tree dynamic programming
    An algorithmic construct rather than a physical entity. Its validity rests on Lemma C.4, which is asserted via a coupling argument rather than a fully formal proof.

pith-pipeline@v1.3.0-alltime-deepseek · 25484 in / 20261 out tokens · 146052 ms · 2026-08-04T14:47:16.703182+00:00 · methodology

0 comments
read the original 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.

Figures

Figures reproduced from arXiv: 2509.22992 by Haifeng Xu, Jamie Morgenstern, Ruimin Zhang, Yuanyuan Yang.

Figure 1
Figure 1. Figure 1: 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 computational/monetary cost) and latency–throughput (where larger batch sizes improve throughput but increase per-sample latency). However, there is no universally accepted policy for… view at source ↗
Figure 2
Figure 2. Figure 2: Costly Exploration for Cascaded Inference 2Loss functions that may take negative values can be shifted or transformed to satisfy this condition. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An Illustration on Node Contraction Illustrated by [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Pareto Frontiers across Vision Classification tasks. The frontiers highlight regions where latency is 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. In [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Pareto Frontier for Language Models. The frontier shows a sharp accuracy–latency trade-off region, where latency is reduced by up to 90%. 7 CONCLUSION We introduced T-Tamer, a principled framework for taming bi-objective trade-offs in cascaded in￾ference. By formulating routing and stopping as a costly exploration problem over DAGs, we de￾veloped a dynamic indexing strategy that achieves provable optimalit… view at source ↗
Figure 6
Figure 6. Figure 6: Hypernode View of multi-line setting. (a) illustrates how to allocate the edge cost [PITH_FULL_IMAGE:figures/full_fig_p021_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Exit decisions in early-exit models. (a) shows the pipeline of an early-exit model; (b) [PITH_FULL_IMAGE:figures/full_fig_p028_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Visualization of the If Stop matrix for Synthetic Data [PITH_FULL_IMAGE:figures/full_fig_p029_8.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

102 extracted references · 1 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Submodular stochastic probing on matroids

    Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular stochastic probing on matroids. Mathematics of Operations Research, 41 0 (3): 0 1022--1038, 2016

    2016

  3. [3]

    Boggart: Towards \ General-Purpose \ acceleration of retrospective video analytics

    Neil Agarwal and Ravi Netravali. Boggart: Towards \ General-Purpose \ acceleration of retrospective video analytics. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23), pp.\ 933--951, 2023

    2023

  4. [4]

    Self-improving algorithms

    Nir Ailon, Bernard Chazelle, Kenneth L Clarkson, Ding Liu, Wolfgang Mulzer, and C Seshadhri. Self-improving algorithms. SIAM Journal on Computing, 40 0 (2): 0 350--375, 2011

    2011

  5. [5]

    Learning to prune: Speeding up repeated computations

    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

    2019

  6. [7]

    The pandora's box problem with sequential inspections

    Ali Aouad, Jingwei Ji, and Yaron Shaposhnik. The pandora's box problem with sequential inspections. Available at SSRN 3726167, 2020

    2020

  7. [8]

    Ordered consumer search

    Mark Armstrong. Ordered consumer search. Journal of the European Economic Association, 15 0 (5): 0 989--1024, 2017

    2017

  8. [9]

    Learning-theoretic foundations of algorithm configuration for combinatorial partitioning problems

    Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning-theoretic foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pp.\ 213--274. PMLR, 2017

    2017

  9. [10]

    Learning to branch

    Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International conference on machine learning, pp.\ 344--353. PMLR, 2018

    2018

  10. [11]

    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

    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

    2021

  11. [12]

    The design and price of information

    Dirk Bergemann, Alessandro Bonatti, and Alex Smolin. The design and price of information. American economic review, 108 0 (1): 0 1--48, 2018

    2018

  12. [13]

    Pandora’s problem with deadlines

    Ben Berger, Tomer Ezra, Michal Feldman, and Federico Fusco. Pandora’s problem with deadlines. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp.\ 20337--20343, 2024

    2024

  13. [14]

    Random search for hyper-parameter optimization

    James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13 0 (2), 2012

    2012

  14. [15]

    Pandora’s problem with nonobligatory inspection: Optimal structure and a ptas

    Hedyeh Beyhaghi and Linda Cai. Pandora’s problem with nonobligatory inspection: Optimal structure and a ptas. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp.\ 803--816, 2023

    2023

  15. [16]

    Pandora's problem with nonobligatory inspection

    Hedyeh Beyhaghi and Robert Kleinberg. Pandora's problem with nonobligatory inspection. In Proceedings of the 2019 ACM Conference on Economics and Computation, pp.\ 131--132, 2019

    2019

  16. [17]

    Prophet inequalities with limited information

    Sayan Bhattacharya and Sanjeev Khanna. Prophet inequalities with limited information. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012

    2012

  17. [18]

    Pandora's box problem with order constraints

    Shant Boodaghians, Federico Fusco, Philip Lazos, and Stefano Leonardi. Pandora's box problem with order constraints. In Proceedings of the 21st ACM Conference on Economics and Computation, pp.\ 439--458, 2020

    2020

  18. [19]

    Query strategies for priced information

    Moses Charikar, Ronald Fagin, Venkatesan Guruswami, Jon Kleinberg, Prabhakar Raghavan, and Amit Sahai. Query strategies for priced information. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp.\ 582--591, 2000

    2000

  19. [20]

    Hartline, David L

    Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 2010

    2010

  20. [21]

    Revenue maximization for query pricing

    Shuchi Chawla, Shaleen Deep, Paraschos Koutrisw, and Yifeng Teng. Revenue maximization for query pricing. Proceedings of the VLDB Endowment, 13 0 (1): 0 1--14, 2019

    2019

  21. [22]

    Pandora's box with correlations: Learning and approximation

    Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang. Pandora's box with correlations: Learning and approximation. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 1214--1225. IEEE, 2020

    2020

  22. [23]

    Approximating pandora's box with correlations

    Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos. Approximating pandora's box with correlations. arXiv preprint arXiv:2108.12976, 2021

    Pith/arXiv arXiv 2021

  23. [24]

    Combinatorial selection with costly information

    Shuchi Chawla, Dimitris Christou, Amit Harlev, and Ziv Scully. Combinatorial selection with costly information. arXiv preprint arXiv:2412.03860, 2024

    Pith/arXiv arXiv 2024

  24. [25]

    Sequential information maximization: When is greedy near-optimal? In Conference on Learning Theory, pp.\ 338--363

    Yuxin Chen, S Hamed Hassani, Amin Karbasi, and Andreas Krause. Sequential information maximization: When is greedy near-optimal? In Conference on Learning Theory, pp.\ 338--363. PMLR, 2015 a

    2015

  25. [26]

    Submodular surrogates for value of information

    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, 2015 b

    2015

  26. [27]

    Self-improving algorithms for convex hulls

    Kenneth L Clarkson, Wolfgang Mulzer, and C Seshadhri. Self-improving algorithms for convex hulls. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\ 1546--1565. SIAM, 2010

    2010

  27. [28]

    José Correa, Pablo D. A. Foncea, Ruben Hoeksma, and Tim Roughgarden. Prophet inequalities for independent random variables from an unknown distribution. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019

    2019

  28. [29]

    Prophet inequalities and posted pricing mechanisms

    José Correa, Anja Korol, and Ruben Hoeksma. Prophet inequalities and posted pricing mechanisms. Mathematics of Operations Research, 47 0 (4): 0 2580--2600, 2022

    2022

  29. [30]

    Apparate: Rethinking early exits to tame latency-throughput tensions in ml serving

    Yinwei Dai, Rui Pan, Anand Iyer, Kai Li, and Ravi Netravali. Apparate: Rethinking early exits to tame latency-throughput tensions in ml serving. In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles, pp.\ 607--623, 2024

    2024

  30. [31]

    A unified approach to routing and cascading for llms

    Jasper Dekoninck, Maximilian Baader, and Martin Vechev. A unified approach to routing and cascading for llms. arXiv preprint arXiv:2410.10347, 2024

    Pith/arXiv arXiv 2024

  31. [32]

    Product ranking on online platforms

    Mahsa Derakhshan, Negin Golrezaei, Vahideh Manshadi, and Vahab Mirrokni. Product ranking on online platforms. Management Science, 68 0 (6): 0 4024--4041, 2022

    2022

  32. [33]

    Bert: Pre-training of deep bidirectional transformers for language understanding

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 (long and short papers), pp.\ 4171--4186, 2019 a

    2019

  33. [34]

    Bert: Pre-training of deep bidirectional transformers for language understanding

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 (long and short papers), pp.\ 4171--4186, 2019 b

    2019

  34. [35]

    Competitive information design for pandora's box

    Bolin Ding, Yiding Feng, Chien-Ju Ho, Wei Tang, and Haifeng Xu. Competitive information design for pandora's box. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\ 353--381. SIAM, 2023

    2023

  35. [36]

    Whether or not to open pandora's box

    Laura Doval. Whether or not to open pandora's box. Journal of Economic Theory, 175: 0 127--158, 2018

    2018

  36. [37]

    Prophet inequalities with unknown distributions

    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

    2017

  37. [38]

    Markov processes: characterization and convergence

    Stewart N Ethier and Thomas G Kurtz. Markov processes: characterization and convergence. John Wiley & Sons, 2009

    2009

  38. [39]

    Online stochastic matching: Beating 1 - 1/e

    Michal Feldman, Thomas Kesselheim, and Brendan Lucier. Online stochastic matching: Beating 1 - 1/e. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016

    2016

  39. [40]

    Pandora box problem with nonobligatory inspection: Hardness and approximation scheme

    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

    2023

  40. [41]

    Bandit algorithms for prophet inequality and pandora's box

    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

    2024

  41. [42]

    Online learning for min sum set cover and pandora’s box

    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

    2022

  42. [43]

    Weitzman's rule for pandora's box with correlations

    Evangelia Gergatsouli and Christos Tzamos. Weitzman's rule for pandora's box with correlations. arXiv preprint arXiv:2301.13534, 2023

    Pith/arXiv arXiv 2023

  43. [44]

    John C. Gittins. Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society: Series B (Methodological), 41 0 (2): 0 148--177, 1979

    1979

  44. [45]

    John C. Gittins. Multi-armed Bandit Allocation Indices. John Wiley & Sons, Chichester, UK, 1989

    1989

  45. [46]

    Asking the right questions: Model-driven optimization using probes

    Ashish Goel, Sudipto Guha, and Kamesh Munagala. Asking the right questions: Model-driven optimization using probes. In Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp.\ 203--212, 2006

    2006

  46. [47]

    Deep learning, volume 1

    Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT press Cambridge, 2016

    2016

  47. [48]

    Dynamic recursive neural network

    Qiushan Guo, Zhipeng Yu, Yichao Wu, Ding Liang, Haoyu Qin, and Junjie Yan. Dynamic recursive neural network. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.\ 5147--5156, 2019

    2019

  48. [49]

    Sorting and selection with structured costs

    Anupam Gupta and Amit Kumar. Sorting and selection with structured costs. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp.\ 416--425. IEEE, 2001

    2001

  49. [50]

    A stochastic probing problem with applications

    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

    2013

  50. [51]

    Algorithms and adaptivity gaps for stochastic probing

    Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and adaptivity gaps for stochastic probing. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pp.\ 1731--1747. SIAM, 2016

    2016

  51. [52]

    Adaptivity gaps for stochastic probing: Submodular and xos functions

    Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Adaptivity gaps for stochastic probing: Submodular and xos functions. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\ 1688--1702. SIAM, 2017

    2017

  52. [53]

    The markovian price of information

    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

    2019

  53. [54]

    A pac approach to application-specific algorithm selection

    Rishi Gupta and Tim Roughgarden. A pac approach to application-specific algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp.\ 123--134, 2016

    2016

  54. [55]

    Dynamic neural networks: A survey

    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 0 (11): 0 7436--7456, 2021

    2021

  55. [56]

    Hyperparameter optimization: a spectral approach

    Elad Hazan, Adam Klivans, and Yang Yuan. Hyperparameter optimization: a spectral approach. In International Conference on Learning Representations, 2018

    2018

  56. [57]

    Deep residual learning for image recognition

    Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp.\ 770--778, 2016

    2016

  57. [58]

    Focus: Querying large video datasets with low latency and low cost

    Kevin Hsieh, Ganesh Ananthanarayanan, Peter Bodik, Shivaram Venkataraman, Paramvir Bahl, Matthai Philipose, Phillip B Gibbons, and Onur Mutlu. Focus: Querying large video datasets with low latency and low cost. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pp.\ 269--286, 2018

    2018

  58. [59]

    Non-stochastic best arm identification and hyperparameter optimization

    Kevin Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Artificial intelligence and statistics, pp.\ 240--248. PMLR, 2016

    2016

  59. [60]

    Shallow-deep networks: Understanding and mitigating network overthinking

    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

    2019

  60. [61]

    Delegated search approximates efficient search

    Jon Kleinberg and Robert Kleinberg. Delegated search approximates efficient search. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp.\ 287--302, 2018

    2018

  61. [62]

    Krakovski

    Robert Kleinberg and Sergei M. Krakovski. Multiple-choice prophet inequalities. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005

    2005

  62. [63]

    Descending price optimally coordinates search

    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

    2016

  63. [64]

    Efficiency through procrastination: Approximately optimal algorithm configuration with runtime guarantees

    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

    2017

  64. [65]

    Auto-weka: Automatic model selection and hyperparameter optimization in weka

    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

    2019

  65. [66]

    Semiamarts and finite values

    Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. 1977

    1977

  66. [67]

    On semiamarts, amarts, and processes with finite value

    Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. Probability on Banach spaces, 4 0 (197-266): 0 1--2, 1978

    1978

  67. [68]

    Adaptive inference through early-exit networks: Design, challenges and directions

    Stefanos Laskaridis, Alexandros Kouris, and Nicholas D Lane. Adaptive inference through early-exit networks: Design, challenges and directions. In Proceedings of the 5th International Workshop on Embedded and Mobile Deep Learning, pp.\ 1--6, 2021

    2021

  68. [69]

    Efficient inference with model cascades

    Luzian Lebovitz, Lukas Cavigelli, Michele Magno, and Lorenz K Muller. Efficient inference with model cascades. Transactions on Machine Learning Research, 2023

    2023

  69. [70]

    Discriminatory information disclosure

    Hao Li and Xianwen Shi. Discriminatory information disclosure. American Economic Review, 107 0 (11): 0 3363--3385, 2017

    2017

  70. [71]

    Multi-token markov game with switching costs

    Jian Li and Daogao Liu. Multi-token markov game with switching costs. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\ 1780--1807. SIAM, 2022

    2022

  71. [72]

    Hyperband: A novel bandit-based approach to hyperparameter optimization

    Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. The Journal of Machine Learning Research, 18 0 (1): 0 6765--6816, 2017

    2017

  72. [73]

    Minimization is harder in the prophet world

    Vasilis Livanos and Ruta Mehta. Minimization is harder in the prophet world. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\ 424--461. SIAM, 2024

    2024

  73. [74]

    Split computing and early exiting for deep learning applications: Survey and research challenges

    Yoshitomo Matsubara, Marco Levorato, and Francesco Restuccia. Split computing and early exiting for deep learning applications: Survey and research challenges. ACM Computing Surveys, 55 0 (5): 0 1--30, 2022

    2022

  74. [75]

    Hidden factors and hidden topics: understanding rating dimensions with review text

    Julian McAuley and Jure Leskovec. Hidden factors and hidden topics: understanding rating dimensions with review text. In Proceedings of the 7th ACM conference on Recommender systems, pp.\ 165--172, 2013

    2013

  75. [76]

    A survey on dynamic neural networks: from computer vision to multi-modal sensor fusion

    Fabio Montello, Ronja G \"u ldenring, Simone Scardapane, and Lazaros Nalpantidis. A survey on dynamic neural networks: from computer vision to multi-modal sensor fusion. arXiv preprint arXiv:2501.07451, 2025

    Pith/arXiv arXiv 2025

  76. [77]

    Online cascade learning for efficient inference over streams

    Lunyiu Nie, Zhimin Ding, Erdong Hu, Christopher Jermaine, and Swarat Chaudhuri. Online cascade learning for efficient inference over streams. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 o...

    2024

  77. [78]

    A more general pandora rule? Journal of Economic Theory, 160: 0 429--437, 2015

    Wojciech Olszewski and Richard Weber. A more general pandora rule? Journal of Economic Theory, 160: 0 429--437, 2015

    2015

  78. [79]

    Imdb movie reviews dataset, 2020

    Aditya Pal, Abhilash Barigidad, and Abhijit Mustafi. Imdb movie reviews dataset, 2020. URL https://dx.doi.org/10.21227/zm1y-b270

    work page doi:10.21227/zm1y-b270 2020

  79. [80]

    Language models are unsupervised multitask learners

    Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1 0 (8): 0 9, 2019

    2019

  80. [81]

    Early-exit deep neural network-a comprehensive survey

    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 0 (3): 0 1--37, 2024

    2024

Showing first 80 references.