- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper studies an additional cost in multi-turn LLM routing, which it calls the "switching tax". Switching models mid-trajectory discards the provider's per-model prompt cache, and the paper models this cost with a retention factor that captures how much of the cache is still usable when the router returns to an earlier model. After measuring this factor on six deployments across four API providers, the paper proposes an output-aware rule for choosing between committing to one model and following demand. The authors then prove several theorems about this policy problem and evaluate the policies with live replays.
Critical strengths
The switching tax is clearly defined and explained: Fig. 1(a) and Eq. 1 separate a first visit, which re-bills the whole prefix, from a return, which re-reads the destination's last cached prefix (§1 "The switching tax"; §3 "Four-bucket billing"). The paper also backs the policy question with proofs (§6, App. M): a downgrade threshold whose competitive ratio does not depend on the number of tiers (Thm. 1), optimality of committing to the session-maximum tier on price-flat pools (Thm. 2), and linear worst-case regret for per-step learners when retention is imperfect (Thm. 3). The empirical study in §4 motivates the problem well: on live APIs, 199 of 206 first visits to a model read nothing from the cache while returns re-read most of the old prefix, so the full-rebuild accounting used by TwinRouterBench [Yang et al., 2026] overstates the tax by about 3x (§4 "First visits and returns", Table 2). The switching tax is clearly defined and explained: Fig. 1(a) and Eq. 1 separate a first visit, which re-bills the whole prefix, from a return, which re-reads the destination's last cached prefix (§1 "The switching tax"; §3 "Four-bucket billing"). The paper also backs the policy question with proofs (§6, App. M): a downgrade threshold whose competitive ratio does not depend on the number of tiers (Thm. 1), optimality of committing to the session-maximum tier on price-flat pools (Thm. 2), and linear worst-case regret for per-step learners when retention is imperfect (Thm. 3). The empirical study in §4 motivates the problem well: on live APIs, 199 of 206 first visits to a model read nothing from the cache while returns re-read most of the old prefix, so the full-rebuild accounting used by TwinRouterBench [Yang et al., 2026] overstates the tax by about 3x (§4 "First visits and returns", Table 2).
Critical weaknesses
Presentation is a significant problem: equations appear in the abstract and on the first page of the introduction before their symbols are defined, several symbols are defined only in the appendix, and some are reused with different meanings. Observed in the abstract, Eq. 1-2 and Table 1 (§1), Fig. 1 (§3), Eq. 4-5 (§5.1, §7), §6 and App. A. The theoretical and practical contributions are thin: the main method is not clearly presented, and much of the main body is spent on the motivating measurements. The evaluation is limited in scope and does not measure the effect on agent task accuracy. There is no controlled experiment showing how switching models affects agent performance in the first place, or how performance changes when the proposed method is applied. The reference for "Learned prefix caching for efficient LLM inference" (page 13, line 654) lists the wrong authors.
Questions for authors
Detailed comments to the authors: The paper is hard to read, mainly because the notation runs ahead of the definitions. The abstract already contains the tax formula without defining its symbols, and Eq. 1 and Eq. 2 appear in §1 before §3 introduces the billing model, which in turn sends the reader to the notation table in App. A. The four basic prices (cache read, cache write, input and output) are explained only through the Fig. 1 legend and that table, "tier" is used from §1 but defined only in §6, and Table 1 reports results in terms of Psi, theta*/sigma-hat and the "peer" and "ladder" pools before any of them is introduced (the two pools are never defined in the main text at all). The recommended policies have the same problem: tax-greedy and blind-follow are defined only in App. J. Several letters are also reused with different meanings, for example lambda in Thm. 3, §7 and App. O, and epsilon in §6 and §7. Beyond the measurements, the methodological contribution is thin: the method is hard to find, and it gains little over a simple baseline. The decision rule is the ratio Psi (Eq. 4), which is the break-even horizon divided by the step budget plus an output-price term. It is read against a band of [0.2, 3] that §5.1 describes as the envelope of observed rank flips, and cases inside the band go to tax-greedy, which is defined in a single clause in App. J. All of this takes about half a page of §5.1, while a much larger share of the main text goes to the measurements and audits in §4, §5.2 and §8. The practical gain is also small: on the 250 held-out pools of Table 4 (App. J), the full rule costs 1.116x / 1.011x OPT at q=0 / q=1, against 1.121x / 1.013x for running tax-greedy everywhere and 1.162x / 1.011x for blind-follow. The theoretical results are mostly either immediate or not positioned against prior work. Table 1 counts two exact identities as evidence (the closed form in §3, and Prop. 1, which App. J confirms it is exact by construction), and Thm. 2 says that switching never pays when all models cost the same. Thm. 1 is not compared with earlier multi-state ski-rental results, and Thm. 3 is not compared with the policy-regret lower bound for adversaries with unbounded memory [Arora et al., 2012], which §2 cites only for constant switching costs. Thm. 3 also relies on q < 1 acting as a proportional loss, even though the best-fit model in App. I has q = 1, a case for which App. M.1 itself says "the reduction says nothing". The cost comparison holds accuracy fixed by assumption. Every policy must meet a per-step "lowest sufficient tier" label (§8, App. J), and §6 notes that the tier ordering is assumed rather than tested. As a result, the accuracy effect of switching models mid-trajectory (for example, one model taking over another model's history) is never measured. The one end-to-end test covers only 28 SWE-bench instances (App. I, Fig. 6): demand-following, tax-greedy and commit resolve 10, 9 and 5 of them, the difference between commit and demand-following is not significant (p = 0.12), mean bills are within 3% of each other, and there is no single-model baseline to compare against. The gate study in §7 reports small accuracy changes (-1.4 to +1.1 points), but on constructed 20-step query sessions rather than agent tasks. The evaluation is also narrow in scale. The whole live study costs $6.49 over 3,473 calls, with step budgets of 12 to 20 and capped outputs, and the replays use a fixed assistant message with 16-token outputs (§4, App. I). Three experiments are missing. First, no OpenAI, Anthropic or Google model is measured on its own provider's API (the only OpenAI model probed, gpt-4.1-mini via OpenRouter, failed the cache-stability check in App. I). This looks feasible as prior work [R1] has audited these providers' prompt caches. Second, there are no long, free-running agent runs, even though the harnesses the paper cites run up to 94 turns (Table 7) and the retention differences between deployments come mostly from cache block size and minimum cacheable prefix, which matter most for short prompts (§4, App. I). Third, the 1,785 "production" sessions behind the headline "20% of the median session's bill" are not a deployed router's log: according to the dataset card [JetBrains Research, 2026], a judge with access to the ground-truth patch picked between gpt-5.2 and gpt-5-mini at every turn, and the card has no token counts. The headline therefore is calculated based on an oracle's choices, a characters/4 token estimate and an assumed q (§5.2, §8), although the paper calls these "production sessions with the router's own decisions". One bibliography entry is wrong: "Learned prefix caching for efficient LLM inference" (page 13, line 654) is by Dongsheng Yang, Austin Li, Kai Li and Wyatt Lloyd (NeurIPS 2025, DOI: 10.52202/085713-1526), not by "Yu Shen et al." as listed in the submission.
References:
[R1] Gu, Li, Kuditipudi, Liang, Hashimoto. Auditing Prompt Caching in Language Model APIs. ICML 2025, PMLR 267:20477-20496. https://proceedings.mlr.press/v267/gu25b.html DOI: 10.48550/arXiv.2502.07776
3 comments
Response to Reviewer pG2Y, part 2 of 3
Response to Reviewer pG2Y, part 2 of 3
4. Theory.
(a) Table 1 now separates measured, computed and proved claims. The closed form is no longer listed as evidence, and the price-flat result appears as a proved guarantee.
(b) The proof of former Theorem 2 is indeed short, and it is now Proposition 1. We keep it in the main text because it is the formal reason for choosing commit above the band.
(c) Theorem 1 is now compared with multi-state power-down in §6. With additive transition costs, a 2-competitive algorithm exists for any number of states (Irani et al., 2003). With costs in both directions, Augustine et al. (2008) compute a near-optimal strategy for each system and give one that is -competitive on every system. Cache billing also charges in both directions. A downgrade pays one tax, the return to the held tier pays another of at most times the first, and both grow with the context. For this family Theorem 1 gives the competitive ratio in closed form, and as approaches 1 no deterministic online policy does better. So Theorem 1 extends power-down to two-way costs that grow with the context.
(d) Former Theorem 3, now Theorem 2, is compared with Arora et al. (2012) in §6. They show that an adversary with unbounded memory can force linear policy regret. Theorem 2 shows that the memory created by cache billing is already enough, namely the time since each model was last used.
(e) You are right that our earlier reduction gave no bound at . The revision adds a direct argument. In any sequence whose last switch is at round , the taxes add up to at least , because every return pays for the context added while that model was idle. Through Lemma 2 in Appendix M, this gives a policy-regret lower bound of at every , including and block billing. The bound for is kept. So the linear-regret result now covers the retention we measure.
5. Accuracy. The revision measures task success directly in three experiments, all scored with the official harness.
- The first is Table 3: 19 SWE-bench Verified instances, five arms and 40 steps, including each model alone. Blind-follow resolves 9 instances, as many as deepseek-v4-pro alone at and three more at . Over this run and the earlier one, commit resolves a share 0.21 lower than blind-follow, with a 95% interval of 0.08 to 0.35.
- The second is Table 4, which measures the effect of switching itself. On 28 instances with two seeds, the switching schedule is fixed in advance. Arms that alternate the two models every 20, 5 or 1 steps resolve 22, 23 and 24 of 56 runs, against 15 and 17 for each model alone. Switching every step instead of every 20 changes the resolved share by +0.04, with an interval of −0.09 to 0.18. Even when the other model takes over the history at every step, the resolved share does not fall.
- The third is the vendors' endpoints, in point 7 below.
A1 is an assumption about steps. At the level of whole runs, the weaker model alone resolves 2 of 19 instances that the stronger one misses, and 6 of 56 runs under the fixed schedule, while the same arm repeats its outcome across two seeds on only 71% to 86% of instances, as §6 reports. §7 now states that the gate sessions are built from single-turn queries, not agent tasks. So the cost comparison no longer rests on fixed requirement labels alone. Blind-follow keeps the stronger model's success, and switching itself does not lower success.
Response to Reviewer pG2Y, part 3 of 3
Response to Reviewer pG2Y, part 3 of 3
6. Scale. The new experiments are much larger and longer, and they use real replies. Table 3 has 95 trajectories of 40 steps and Table 4 has 280, with replies capped at 900 tokens. Sixteen of these runs continued to step 94, with contexts up to 98k tokens. The replays on OpenAI's and Anthropic's endpoints reach 100k tokens. The fixed assistant message with 16-token outputs was used only in the deployment replays. Those replays measure how much of the input the cache reads back. Output tokens are billed at the serving model's output price whether or not a switch occurred, so the output length does not affect the retention measurement. So the billing law holds with long contexts and real outputs, and points 7 and 8 give the read-back figures.
7. Missing experiment 1: the vendors' own APIs. We measured OpenAI's and Anthropic's own endpoints. Google's two Gemini models did not pass the cache screen. We went through OpenRouter with the official provider pinned and fallbacks disabled, checked the serving provider on every response, and registered the design and predictions before the first call. §2 now cites Gu et al. (2025).
- On Anthropic, from Haiku 5.5 to Sonnet 5.5, every registered prediction holds. The fitted retention is 1.00, and with a block of 1 token and a minimum prefix of 512 the bill error is 0.003.
- On OpenAI, from gpt-5-mini to gpt-5.2, the same pair as the corpus, the fitted retention is 0.81, and three registered predictions did not hold. With the documented constants the bill error is 0.128 against a predicted 0.10, returns read back 0.715 against a predicted 0.8, and gpt-5.2 starts reading only at about 1,800 tokens instead of the documented 1,024. All three come from one behaviour: gpt-5.2 reads back less of its prefix than documented, and about 600 tokens at the end of each prefix are never read back. With that tail fitted on the first batch and frozen at 640 tokens, a fresh batch of replays is predicted to 0.045, with 90% of bills within ±10%, against 0.202 and 38% without it.
- On replays up to 100k tokens, returns past 20k tokens read back a median 0.994 on OpenAI and 0.9999 on Anthropic.
- Table 5 gives the agents. On Anthropic, blind-follow resolves the same 5 of 6 instances as Sonnet 5.5 alone at 0.24 times its bill. On OpenAI it resolves 3 of 8, between gpt-5-mini alone with 2 and gpt-5.2 alone with 6, at 0.76 times the bill of gpt-5.2.
So the tax model holds on both vendors' endpoints once each deployment's constants are measured. The OpenAI deviation is one more deployment constant that can be measured, which is an example of the paper's point that retention belongs to the deployment, not to the model.
8. Missing experiment 2: long free-running runs. Done. Sixteen runs reached step 94 with contexts up to 98k tokens, and past 20k tokens returns read back a median 0.998. The vendors' long replays are in point 7. As you note, block size and minimum prefix matter most for short prompts. Their effect on the bill shrinks as the context grows, and they change the bill but not the policy the rule picks, as §4 states. So in long runs retention is close to 1 and the conclusions do not change.
9. Missing experiment 3: the corpus. You are right, and thank you for checking the dataset card. A judge with access to the gold patch chose each turn, and the card has no token counts. We removed "production" and "the router's own decisions" throughout, cite the corpus, count tokens with the o200k tokenizer, and re-bill with the constants measured on OpenAI's endpoint for this same pair. The tax is 16% of the median bill, with an interquartile range of 11.4% to 22.2%, against 20% at and 48% at , as §8 and Appendix J report. At the measured constants every trajectory costs less than holding the stronger model, with a median of 0.65 times. So this result no longer rests on an assumed or a character-based estimate, and the tax remains a sizable part of the bill.
10. The reference. It now lists Yang, Li, Li and Lloyd, NeurIPS 2025. We also re-checked the bibliography against the sources and corrected nine further entries.
In summary, the revision keeps the paper's question and claims, adds the three experiments you listed and a direct measurement of task success, and corrects the description of the corpus, the positioning against prior work, and the references. We hope these changes address your concerns and would be grateful if you would reconsider your assessment.
Response to Reviewer pG2Y, part 1 of 3
Response to Reviewer pG2Y, part 1 of 3
Thank you for a very detailed review. You were right about the description of the corpus, the reference, and several points of positioning, and we have corrected all of them. We answer in the order of your comments. "Former" refers to the numbering in the submission.
1. Notation ahead of definitions. We revised the presentation item by item following your list. The abstract no longer contains a formula and describes the tax in words. Eq. 1 and Eq. 2 now appear in §3, after the billing model. §3 opens with a Problem paragraph that defines the pool, the tiers, the four per-token prices, the requirement ℓt, the policy and OPT, and then lists assumptions A1 to A4. Blind-follow, commit, tax-greedy, and the peer and ladder pools are defined in the Policies and pools paragraph of §3. Table 1 no longer uses Ψ, θ⋆/σ^ or the pool names. λ now denotes only the switching-cost slope and ε only the relative price gap between two peers, and Appendix A collects all symbols. So a reader can now follow §3 to §6 in order without consulting the appendix.
2. A thin method that is hard to find. The method is now stated in one place, the paragraph The rule in §5.1, and every term it uses is defined before it. Its inputs are the price sheet, the step budget T, the output-to-context token ratio ω from the harness logs, and q read from the billed cache counts of a few returns. Eq. 4 turns these inputs into Ψ. Below 0.2 the rule follows demand, above 3 it commits, and inside the band it runs tax-greedy. Fig. 1b shows this pipeline. The rule needs no per-step labels and is computed once per deployment. The rule is simple, but each of its inputs has to be measured, and §4 is the evidence for that: the same model pair has q of 0.97, 0.81 and 0.83 on three deployments. So the measurements in §4 are not motivation beside the method. They are its inputs.
3. A small practical gain. The numbers you quote are correct. Former Table 4 is now Table 6. These averages, however, reflect the make-up of the random ensemble. Of the 250 held-out pools, 204 lie below the band, where following demand is already close to optimal, and inside the band the rule is tax-greedy by definition. That is why the average gap is small. The rule matters above the band. On 120 near-flat pools above it, Table 7 shows the rule within 1% of OPT, while tax-greedy pays 7% to 60% more and blind-follow pays 25% to 95% more at q=1. On the real peer pool at q=1, over all 77 trajectories, commit costs 1.161 times OPT, tax-greedy 1.233 times and blind-follow 1.354 times, as Appendix J shows. So the rule's gain is concentrated where following demand step by step costs the most, and the average is small because the random pools are mostly ladders.