acceptodds
Under review as a conference paper at ICLR 2027

TTS-Route: Query-Adaptive Test-Time Scaling Graphs on the Fly

Abstract

Test-Time Scaling (TTS) improves large language models (LLMs) by allocating additional computation at inference time. However, existing work typically optimizes task-level compute allocation, such as using a single TTS graph across a task, overlooking substantial variation in per-query compute requirements. We therefore study a novel problem of query-adaptive TTS routing: given a weak-to-strong LLM pool and a target average compute budget, the goal is to adaptively select the model, scaling strategy, and realized TTS graph for each query. This is challenging because non-Euclidean TTS graphs are difficult to predict directly, informative configuration signals remain unclear, and global compute must be allocated adaptively across queries. To address these challenges, our pilot experiments reveal three insights: (1) TTS graphs should adapt to runtime response quality; (2) per-action success probabilities provide a stable learning target; and (3) low-cost probe responses and verifier feedback improve routing reliability. Based on these insights, we propose TTS-Route, combining a budget-aware TTS-Router for per-action success estimation and Lagrangian action selection with a training-free TTS-Planner that constructs TTS graphs on the fly using verifier feedback. Experiments on three datasets show that TTS-Route achieves the strongest performance–cost trade-off among strong baselines and generalizes to monetary budgets and out-of-distribution queries.

Primary area:
generative models
Keywords:
Large Language Models, Test-time Scaling, Compute-optimal Inference, Query Routing, Efficient ML

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_avsBOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This work studies the problem of test-time scaling. The authors show that existing TTS methods typically adopt a uniform task-level strategy across all queries and are confined to a single model and a limited scaling space, whereas different queries should be matched with different combinations of model and scaling strategy. To address this, they propose TTS-Route, in which a TTS-Router performs action selection based on the query, a low-cost probe, and the verifier score, while a TTS-Planner constructs the TTS graph on the fly according to verifier feedback and decides when to expand and when to stop. Experiments show that TTS-Route improves the performance-cost frontier over strong baselines and generalizes to out-of-distribution tasks and alternative budget metrics.

Critical strengths
  1. The design of the method is supported by clear experiments and analysis, and is solid.
  2. The proposed method achieves good performance and efficiency.
  3. Multiple budget settings and several performance-cost metrics are considered.
Critical weaknesses
  1. The preparation of training queries and scoring also appears to incur a non-trivial cost. The inference cost of this part should be analyzed separately, and both the training cost and the inference cost should be taken into account when computing the overall cost.

  2. There is no complete logical loop between the theoretical analysis and the method design. Proposition 1 demonstrates the limitation of directly predicting the oracle, but it does not explain why prediction based on success probabilities can break this ceiling, or at least outperform direct oracle prediction.

  3. Too many components and operations limit readability. A pseudocode covering the complete pipeline should be included to aid understanding.

Questions for authors

Please refer to the Weakness part.

6 comments
AuthorsOpenReview ↗

Response Part I

We sincerely thank the reviewer for the constructive feedback. We address each concern below.

Reply 1 (W1): Offline Training and Overall Compute Costs

W1. The preparation of training queries and scoring also appears to incur a non-trivial cost. The inference cost of this part should be analyzed separately, and both the training cost and the inference cost should be taken into account when computing the overall cost.

We agree and provide a separate analysis of offline training costs, followed by an evaluation of the overall cost after amortization.

Offline Cost. We account for four components across 4,604 training queries, measured in normalized compute units:

  1. Training-data generation: Action profiling for TTS-Route (Eq. (6)) and response generation for baselines, including samples used for verifier training.
  2. Verifier scoring: Scoring profiled responses (0.48 units per response).
  3. Verifier training: Teacher-verifier scoring (8B model) and proxy-verifier fine-tuning, charged fully to each method using the verifier.
  4. Router training: Router optimization, including RouteLLM's estimated pre-training cost (at least 2.3M units based on its reported training configuration).

The following table reports the offline cost per training query.

MethodData generationVerifier scoringVerifier trainingRouter trainingTotal
TTS-Route51110166<1687
RouteLLM17600506682
BEST-Route2316166<1403
FrugalGPT23121660399
AutoMix23111660398
BoN-8B23101660397
BG-MCTS23101660397
HybridLLM21200<1212

TTS-Route's offline cost is comparable to RouteLLM's, approximately 1.7× that of BEST-Route, FrugalGPT, AutoMix, BoN, and BG-MCTS, and 3.2× that of HybridLLM. This additional cost arises from profiling a broader action space, including width-lean and depth-lean strategies. We therefore evaluate whether the improved inference efficiency offsets this upfront cost.

Overall Cost. Offline training incurs a one-time cost. For a deployment serving TT queries, the amortized overhead per query is Coffline/TC_{\text{offline}}/T. We incorporate this overhead into each operating point and recompute APGR.

Each entry reports APGR1b\mathrm{APGR}_{1b} / APGR8b\mathrm{APGR}_{8b}.

MethodInference onlyT=105T=10^5T=106T=10^6T=107T=10^7
BG-MCTS56.5 / −2.042.9 / −15.855.0 / −5.256.3 / −2.0
BoN-8B63.4 / 20.749.4 / 14.362.0 / 20.163.4 / 20.7
BEST-Route76.4 / 52.558.8 / 28.074.6 / 49.676.4 / 52.3
RouteLLM78.6 / 60.447.4 / 24.275.4 / 54.278.3 / 60.1
HybridLLM78.4 / 56.768.9 / 40.677.4 / 55.378.4 / 56.6
AutoMix79.1 / 58.361.4 / 34.177.4 / 56.279.0 / 58.0
FrugalGPT81.7 / 65.963.0 / 38.479.8 / 63.481.6 / 65.7
TTS-Route86.1 / 76.053.8 / 36.282.8 / 71.985.7 / 75.5

Key findings: (i) Small deployments: At T=105T=10^5, TTS-Route is less cost-effective, with HybridLLM, FrugalGPT, AutoMix, and BEST-Route achieving higher APGR1b\mathrm{APGR}_{1b}. (ii) Break-even point: TTS-Route becomes the best method on APGR8b\mathrm{APGR}_{8b} after approximately 1.3×1051.3\times10^5 queries and on both metrics after 3.3×1053.3\times10^5 queries, when the amortized overhead is approximately 10 units per query. (iii) Large deployments: At T≥106T\geq10^6, TTS-Route leads on both metrics, approaching inference-only performance at T=107T=10^7. These results clarify that TTS-Route's higher offline cost is offset by its inference efficiency at sufficiently large deployment scales.

AuthorsOpenReview ↗

Response Part II

Reply 2 (W2): Theoretical Motivation for Success-Probability Prediction

W2. There is no complete logical loop between the theoretical analysis and the method design. ... it does not explain why prediction based on success probabilities can break this ceiling, or at least outperform direct oracle prediction.

We thank the reviewer for identifying this gap. We clarify the advantages, theoretical limitations, and motivation of success-probability prediction, supported by empirical evidence.

What are the advantages of success-probability prediction over direct oracle-label prediction? For query qq and action aa, let Yq,a∈{0,1}Y_{q,a}\in\{0,1\} denote the outcome of a stochastic execution and pq(a)=Pr⁡(Yq,a=1)p_q(a)=\Pr(Y_{q,a}=1) its success probability. The oracle label L(q)L(q) denotes the lowest-cost successful action, with πq(a)=Pr⁡(L(q)=a)\pi_q(a)=\Pr(L(q)=a). Success-probability prediction learns pq(a)p_q(a), whereas direct oracle-action prediction learns πq(a)\pi_q(a) and selects the most likely action. The former offers two advantages:

(1) Alignment with the optimization objective and sufficient information for decision-making. Our objective (Eq. (2)) is to maximize expected task success subject to an average compute budget: max⁡gEq[pq(g(xq))].\max_g \mathbb E_q[p_q(g(x_q))]. Given action costs, the success probabilities pq(a)p_q(a) provide sufficient information to determine an optimal budget-aware routing policy. In contrast, maximizing oracle-label prediction accuracy does not necessarily optimize the accuracy–cost trade-off.

(2) More informative supervision and improved learning efficiency. Oracle labels suffer from information censoring: the outcome of a higher-cost action is directly revealed only when all cheaper actions fail. For nn profiled queries, action-level supervision provides nn observations per action. Under independent outcomes and fixed success probabilities, oracle labels directly reveal the outcome of action aka_k in approximately n∏j<k(1−pq(aj))n\prod_{j<k}(1-p_q(a_j)) observations.

Can success-probability prediction overcome the theoretical ceiling? No. The ceiling Acc⋆\mathrm{Acc}^\star in Eq. (3) bounds the maximum accuracy of predicting stochastic oracle labels L(q)L(q) from query-only information. Changing the prediction target cannot eliminate the inherent randomness of oracle labels. To improve oracle-label predictability, additional informative evidence is needed. Accordingly, we introduce the probe response and its verifier score (Insight 3) to reduce uncertainty.

How does Insight 2 motivate success-probability prediction? Insight 2 reveals a fundamental instability in direct oracle-label prediction: the lowest-cost successful action for the same query may vary across stochastic executions. If oracle labels were sufficiently stable, directly predicting the oracle action could reasonably balance accuracy and cost. However, Insight 2 shows that their inherent uncertainty limits prediction reliability and learning efficiency on expensive actions. We therefore predict each action's conditional success probability pq(a)p_q(a), which better aligns with the accuracy–cost trade-off in our optimization objective and mitigates the learning inefficiency associated with oracle-label prediction. This does not eliminate execution randomness. Instead, learning expected action performance avoids reliance on unstable oracle labels and more directly supports the budget-aware optimization in Eq. (2).

Empirical Validation Our ablation study (Appendix F.1) shows that replacing success-probability prediction with direct oracle-action prediction decreases APGR1b\mathrm{APGR}_{1b} / APGR8b\mathrm{APGR}_{8b} by 11 / 17 percentage points on average, further supporting the effectiveness of our design.

Reply 3 (W3): Improving Presentation Clarity

W3. Too many components and operations limit readability. Pseudocode covering the complete pipeline should be included to aid understanding.

We appreciate this suggestion. The current submission includes pseudocode for graph execution (Algo. 1) and online inference (Algo. 2) in the appendix, but lacks a unified description of the offline and online stages. To improve readability, we will include a consolidated pipeline algorithm in the main text, e.g.,

Offline stage (executed once)
1: Train proxy verifier V via teacher distillation.  (Eq. 5)
2: For each training query q and action a = (M, S):
     Execute a using TTS-Planner;
     record Y_{q,a} and C_{q,a}. (Eq. 6)
3: Train TTS-Router on D_router to predict p_q(a). (Eq. 7)
4: Calibrate lambda(b) on D_cal for each target budget b.  (Eq. 9)

Online stage (for each query q and budget b)
... (see details in Algo.2 in the paper)

We thank the reviewer again for the valuable feedback and will incorporate these improvements into the revised manuscript. We welcome any further feedback.

Thanks for the authors' response. It appears that the offline cost of TTS-Route is noticeably higher than that of FrugalGPT (1.72x), yet its APGR does not surpass FrugalGPT's by that much even when scaled to a larger TT. For fairness and rigor, could the authors provide an APGR comparison under aligned offline costs?

Reviewer_dt3iOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces TTS-ROUTE, a query-adaptive test-time scaling framework that combines success-probability-based routing with verifier-guided online construction of test-time scaling graphs. It aims to improve the accuracy–compute trade-off by jointly adapting model selection, scaling strategy, and inference-time computation to individual queries. Experiments across multiple datasets and budget settings demonstrate promising improvements over the evaluated baselines.

Critical strengths

The paper addresses a relevant problem in efficient LLM inference and proposes a coherent framework combining budget-aware routing with adaptive graph construction. Its use of low-cost probe responses and verifier feedback is intuitively motivated and empirically investigated. The evaluation across different datasets and compute budgets provides encouraging evidence that query-adaptive allocation can improve the performance–cost trade-off.

Critical weaknesses

The proposed TTS-Planner relies on empirical observations and verifier feedback to guide graph expansion and stopping decisions. While the empirical results motivate this design, it remains unclear whether the heuristic rules are theoretically justified beyond the evaluated settings. Can the authors provide a formal analysis of when verifier-guided expansion is expected to improve task accuracy, and under what assumptions the stopping criterion is effective? In particular, can the proposed planner be shown to achieve any approximation guarantee or regret bound relative to an oracle planner under a fixed compute budget?

The framework heavily relies on the quality of the learned proxy verifier, yet its robustness to verifier miscalibration and distribution shifts remains insufficiently established. The generalization claims are supported by a relatively narrow benchmark suite, with OOD evaluation based on only 80 MT-Bench questions.

The reported compute efficiency may be overstated because the main cost accounting excludes routing and verifier overhead, which can accumulate during adaptive graph expansion.

Questions for authors

How sensitive are the width-lean and depth-lean planning heuristics to verifier miscalibration and the stopping threshold? Could the authors provide theoretical or empirical guarantees showing that these heuristics remain reliable when the relationship between verifier scores and actual task correctness changes across models or domains?

How sensitive is TTS-ROUTE to proxy-verifier errors and miscalibration, particularly when the verifier incorrectly assigns high scores to incorrect responses?

How does TTS-ROUTE perform when all inference overheads, including probe generation, proxy-verifier scoring, and routing computation, are included in the total compute budget? Can the proposed Lagrangian routing framework guarantee a strict per-query compute or monetary-cost limit, rather than only satisfying an average budget constraint?

How does the offline profiling cost scale with the number of candidate models, scaling strategies, and training queries, and how often must the router and profiling library be retrained?

3 comments
AuthorsOpenReview ↗

Response Part I

Thank you for your detailed review. For this response, we conducted additional analyses, including forced continuation after planner stopping, verifier-score perturbations, sweeps of the improvement threshold, two transfer evaluations, and evaluation accounting for all additional overheads.

Reply 1 (W1)

W1. ... Can the authors provide a formal analysis of when verifier-guided expansion is expected to improve task accuracy, and under what assumptions the stopping criterion is effective? In particular, can the proposed planner be shown to achieve any approximation guarantee or regret bound relative to an oracle planner under a fixed compute budget?

A brief answer: Yes, under two assumptions. We provide (1) a sufficient condition for an expansion to improve accuracy and (2) a regret bound relative to the best continuation from the graph at which the planner stops. We propose an approximate regret bound relative to an oracle planner.

Setup. Fix a model MM. Probabilities are defined over queries and stochastic generation. As in Eq. (4), GℓG_\ell denotes the graph after ℓ\ell layers, and R≤ℓR_{\leq\ell} denotes its candidate responses. The planner returns the highest-scored response r^ℓ=arg⁡max⁡r∈R≤ℓV(q,r)\hat r_\ell=\arg\max_{r\in R_{\leq\ell}}\mathcal V(q,r). Define

P^*(G_\ell)=\Pr(R_{\leq\ell}\ \text{contains a correct response}).$$ Thus, $P\leq P^*$. Expansion only adds candidate responses, so $P^*$ never decreases: $\Delta_\ell^*=P^*(G_\ell)-P^*(G_{\ell-1})\geq 0$ is the probability that layer $\ell$ generates the first correct response. Let $\Delta_\ell=P(G_\ell)-P(G_{\ell-1})$. **Assumption 1 (ranking reliability).** For every graph $G$ that the planner can reach, including the stopping graph, the probability that $G$ contains a correct response but the highest-scored response is incorrect is at most $\eta$, i.e., $P^*(G)-P(G)\leq\eta$. This is consistent with the verifier's pairwise Bradley–Terry training (Eq. (5)). **Assumption 2 (small gains after stopping).** The gains from TTS expansion follow a beta-Lipschitz pattern, with gains decreasing gradually (which has been empirically validated in existing work). After the planner stops because the verifier-score improvement is small, conditional on everything observed so far, the probability that any subsequent expansion generates the first correct response is at most $\gamma$, regardless of the strategy used to continue expanding the graph. Figure 2(c) supports this assumption. **(1) When expansion helps.** Under Assumption 1, $\Delta_\ell\geq\Delta_\ell^*-\eta$. Therefore, $${\Delta_\ell^*>\eta\ \Longrightarrow\ \Delta_\ell>0}$$ If the probability that an expansion generates the first correct response exceeds the ranking error rate, the expansion improves accuracy. This is a sufficient condition. Conversely, the total loss caused by expansion never exceeds $\eta$, regardless of how many layers are added, since $P(G_\ell)\geq P^*(G_0)-\eta\geq P(G_0)-\eta$ for any earlier graph $G_0$. **(2) Regret bound.** Suppose the planner stops at $G_\tau$ according to the stopping rule (Eq. (4)). Let an arbitrary strategy continue the expansion to a graph $G^\pi$, with at most $m\leq\lfloor(B_q-C_\tau)/C_{\min}\rfloor$ further expansions, where $C_{\min}$ is the minimum cost of one expansion. Subsequent expansion can provide a gain only by generating the first correct response, and the probability of this event in any expansion is at most $\gamma$. The probability that $G_\tau$ already contains a correct response but returns an incorrect one is at most $\eta$. Therefore, $${P^*(G^\pi)-P(G_\tau)\ \leq\ \gamma\,\mathbb E[m]+\eta}$$ The left-hand side uses $P^*$, so the bound also holds even if the continuation employs perfect answer selection. The bound decomposes regret into a missed-correct-solution component and a ranking-error component. The improvement threshold $\epsilon$ enters the expression only through $\gamma$, because it determines where the planner stops. **Empirical check.** On the test sets of BEST-Route-Mix, MATH, and MMLU, we selected 1,735 query–model cases (Width-lean Planner, 1B and 8B) for which the planner stopped before exhausting the query-level budget. We then forced the planner to continue expanding until the budget was exhausted. This is one continuation strategy and directly measures regret. | Forced continuation versus stopping | Result | | ----------------------------------- | ---------------------- | | Incorrect → Correct | 2.7% | | Correct → Incorrect | 1.4% | | Net accuracy improvement| +1.3 percentage points | | Generation cost | 1.01–1.32× | | || Stopping loses about one percentage point of accuracy while saving up to 24% of generation cost. This shows that although early stopping slightly affects accuracy, it saves a substantial amount of cost.
AuthorsOpenReview ↗

Response Part II

Reply 2 (W2, Q1, Q2)

W2. ... yet its robustness to verifier miscalibration and distribution shifts remains insufficiently established. The generalization claims are supported by a relatively narrow benchmark suite, with OOD evaluation based on only 80 MT-Bench questions.

Q1. How sensitive are the width-lean and depth-lean planning heuristics to verifier miscalibration and the stopping threshold? Could the authors provide theoretical or empirical guarantees showing that these heuristics remain reliable when the relationship between verifier scores and actual task correctness changes across models or domains?

Q2. How sensitive is TTS-ROUTE to proxy-verifier errors and miscalibration, particularly when the verifier incorrectly assigns high scores to incorrect responses?

These three weakeness/questions all concern the proxy verifier, so we address them together.

(a) Verifier Errors and Miscalibration (W2, Q1, Q2). To evaluate robustness to verifier errors and miscalibration, we perturb verifier scores on BEST-Route-Mix. Perturbations are applied to (i) the router's probe-score input and (ii) final-response selection in width-lean graphs. We consider two types: (1) Noise, adding Gaussian noise (σ≈2.5\sigma\approx2.5, the standard deviation of verifier scores); and (2) False-high, assigning incorrect responses scores in the top 1% with a specified probability. Results are averaged over 20 random seeds.

Verifier-score perturbationAPGR${1b}$ / APGR${8b}$Selection-only changeGraphs with changed selections
None (paper setting)86.1 / 76.0––
Noise 0.1σ0.1\sigma85.9 / 75.5−0.0 / −0.121%
Noise 0.5σ0.5\sigma83.3 / 68.5−0.2 / −0.247%
Noise 1σ1\sigma78.9 / 56.8−0.3 / −0.456%
False-high 5%83.5 / 69.0−0.2 / −0.35%
False-high 10%80.8 / 62.0−0.4 / −0.69%
False-high 20%76.3 / 50.1−0.6 / −1.016%

Key findings: (1) The framework tolerates mild noise. Small perturbations cause limited APGR degradation, while large 1σ1\sigma noise produces significant degradation, indicating tolerance to small noise. (2) False-high scores are particularly harmful. At 5%, 10%, and 20% perturbation rates, APGR${1b}$ / APGR${8b}$ decreases by 2.6 / 7.0, 5.2 / 14.0, and 9.8 / 26.0 points, respectively. These results highlight the framework's dependence on reliable verifier rankings, particularly its ability to avoid assigning high scores to incorrect responses.

(b) Improvement Threshold ϵ\epsilon (Q1). We further evaluate sensitivity to the stopping threshold ϵ\epsilon by replaying both planners with different threshold values under the same setting.

ϵ\epsilonWidth-lean APGR (1B / 8B)Depth-lean APGR (1B / 8B)
086.1 / 76.286.1 / 76.0
0.186.1 / 76.286.1 / 76.1
0.286.1 / 76.286.1 / 76.1
0.35 (Default)86.1 / 76.286.1 / 76.1
0.586.0 / 76.186.0 / 76.0
185.8 / 75.985.7 / 75.7
285.2 / 75.185.0 / 75.1
384.0 / 74.184.1 / 74.2

The results demonstrate stable performance around the default threshold (ϵ=0.35±0.15\epsilon=0.35\pm0.15). Two observations explain this behavior: (i) Smaller thresholds permit more expansions, but these are typically constrained by the query-level budget BqB_q, resulting in nearly unchanged performance. (ii) Larger thresholds encourage earlier stopping, generally reducing both accuracy and computational cost, while overall APGR tends to decline. Thus, ϵ\epsilon governs the accuracy–cost trade-off, and we select its value using the calibration set.

(c) Guarantees under Changes in Score–Correctness Relationships (Q1). We cannot provide an unconditional guarantee, as reliable correlation between verifier scores and correctness is fundamental to our method. Our analysis relies on Assumption 1; if the verifier ranks incorrect responses above correct ones in a new model or domain, both planners may become unreliable.

(d) Distribution Shift and OOD Evaluation (W2). To extend the OOD evaluation beyond the 80 MT-Bench questions, we conduct two additional transfer experiments with 500 test questions each: MATH → GSM8K and MMLU → MedQA. All methods are trained on the source task and evaluated on the target task without adaptation.

MethodMATH → GSM8K APGR$_{1b}$MATH → GSM8K APGR$_{8b}$MMLU → MedQA APGR$_{1b}$MMLU → MedQA APGR$_{8b}$
Best Fixed TTS66.716.352.92.4
RouteLLM76.348.770.247.5
AutoMix79.157.364.143.4
BEST-Route82.563.274.052.5
FrugalGPT87.977.671.445.9
TTS-Route89.381.376.758.5

TTS-Route achieves the highest APGR under both transfer settings, providing stronger evidence of its ability to generalize across tasks within the evaluated domains without target-task adaptation.

AuthorsOpenReview ↗

Response Part III

Reply 3 (W3, Q3)

W3. The reported compute efficiency may be overstated because the main cost accounting excludes routing and verifier overhead, which can accumulate during adaptive graph expansion.

Q3. How does TTS-ROUTE perform when all inference overheads, including probe generation, proxy-verifier scoring, and routing computation, are included in the total compute budget? Can the proposed Lagrangian routing framework guarantee a strict per-query compute or monetary-cost limit, rather than only satisfying an average budget constraint?

We agree: excluding these overheads makes the reported efficiency appear higher than it actually is. We recomputed APGR on BEST-Route-Mix with all inference overheads included.

  • TTS-Route: Generation of the 1B probe response (unless that response is returned as the final answer), proxy-verifier scoring of the probe and each candidate response in a graph, and routing computation (encoder and MLP). We recalibrate λ(b)\lambda(b) using the total cost, so the budget applies to the total cost.
  • Baselines: We include verifier scoring for FrugalGPT, AutoMix, BoN, and BG-MCTS; and the router forward pass for RouteLLM (whose released router is a fine-tuned Llama-3-8B, costing 8.9 units per query), HybridLLM, and BEST-Route. The costs of HybridLLM and BEST-Route already include scoring of their sampled responses.
MethodAPGR${1b}$ / APGR${8b}$ (paper protocol)APGR${1b}$ / APGR${8b}$ (all overheads)
BoN-1B36.2 / −62.234.1 / −67.1
BoN-8B63.4 / 20.763.2 / 20.1
BG-MCTS56.5 / −2.055.3 / −4.4
RouteLLM78.6 / 60.469.5 / 46.0
HybridLLM78.4 / 56.778.4 / 56.6
BEST-Route76.4 / 52.576.4 / 52.5
AutoMix79.1 / 58.378.3 / 57.2
FrugalGPT81.7 / 65.981.3 / 65.1
TTS-Route86.1 / 76.085.0 / 74.1

Key Experimental Findings. (i) Overall performance. After accounting for all inference overheads, TTS-Route's APGR decreases from 86.1 / 76.0 to 85.0 / 74.1, while remaining the best-performing method on both metrics. (ii) Overhead analysis. At b=30b=30, the overhead averages approximately 1.4 units per query (0.9 for probe generation, 0.5 for verifier scoring, and 0.02 for routing), representing only about 5% of the total budget. Verifier scoring adds about 2 units to a 1B width-lean graph with 4.2 units of generation cost. However, this overhead has limited overall impact because these graph-based actions account for a relatively small fraction of queries at b=15→75b=15→75.

Strict Per-Query Limit. The Lagrangian routing rule (Eqs. (8)–(9)) constrains the average budget over the calibration distribution rather than enforcing a strict per-query limit. This aligns with our problem definition (Eq. (2)), which aims to allocate a shared compute budget efficiently across queries of varying difficulty. We consider this setting more practical, as it allows computational resources to be shifted from easier to harder queries. For a strict per-query limit, it is a more restrictive setting and can be accommodated by imposing an explicit budget cap on each query.

Reply 4 (Q4)

Q4. How does the offline profiling cost scale with the number of candidate models, scaling strategies, and training queries, and how often must the router and profiling library be retrained?

Scaling. The action-profiling library (Eq. (6) in the paper) executes each action a=(M,S)a=(M,S) once for every training query. Thus, its cost is Cprofile=∑q∈Dtrain ∑M∈M ∑S∈SCq,(M,S).C_{\text{profile}}=\sum_{q\in\mathcal D_{\text{train}}}\ \sum_{M\in\mathcal M}\ \sum_{S\in\mathcal S} C_{q,(M,S)} . There are ∣M∣⋅∣S∣|\mathcal M|\cdot|\mathcal S| actions. The cost scales linearly with the number of training queries, and each new model or strategy adds only the cost of its own actions. For every model below the largest one, the per-query cost of each graph action is bounded by the query-level budget BqB_q (Eq. (4) in the paper).

Retraining. With a fixed training set and model pool, the profiling library and router are built only once, requiring no periodic retraining. When new models or queries are introduced, the library can be extended incrementally by profiling only the corresponding new actions or queries and training the router heads for new actions, as the router predicts success probabilities separately for each action. One exception is the model immediately below a newly added model in size: its width-lean and depth-lean actions require re-profiling because their query-level budget BqB_q is defined by the cost of one call to the next larger model.

We appreciate your valuable comments, some of which have inspired new considerations that are worth addressing in subsequent revisions. We welcome any further feedback.

Reviewer_4d8eOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper explores a problem of query-adaptive test-time-scaling (TTS) routing: given a weak-to-strong LLM pool and a target average compute budget, the goal is to adaptively select the model, scaling strategy, and realized TTS graph for each query. In order to design a method for this problem, this paper conducts pilot experiments and finds three insights:

  1. TTS graphs should adapt to runtime response quality
  2. per-action success probabilities provide a stable learning target
  3. low-cost probe responses and verifier feedback improve routing reliability

Based on these insights, the authors presents the method called TTS-ROUTE, which combines a budget-aware TTS-Router for per-action success estimation and Lagrangian action selection with a training-free TTS-Planner constructing TTS graphs on the fly using verifier feedback.

The experiments use BEST-Route-Mix, MATH, and MMLU as benchmark datasets and Llama-3-1B/8B, Gemma-3-27B, and Qwen-2.5-72B as the model pool. This paper reported that the proposed method showed the best performance–cost trade-off among baselines such as one call to each model, weak-to-strong routing/cascades (RouteLLM, Hybrid LLM, AutoMix, and FrugalGPT), fixed TTS (BoN, elf-Consistency (SC), Self-Refinement (SR), and fixed width×depth graphs), and adaptive TTS (BEST-Route and BG-MCTS).

Critical strengths
  • The novel and practical setting of test-time scaling, where we have a model pool with different inference efforts, costs, and capabilities.
  • This paper reports interesting insights that lead to the methodological design of TTS-ROUTE.
  • The strong empirical evidence with the reasonable model pool, baselines, and evaluation benchmarks.
  • This paper also reports analyses for monetary budgets and out-of-distribution queries.
Critical weaknesses
  • The description is quite dense; some important materials (e.g., Fig 7) appear in the appendices.
Questions for authors

L408: "using the same model pool as above": Does "the above" here point to the preliminary experiments?

1 comment

We sincerely thank the reviewer for the careful evaluation and positive feedback on our work.

W1. The paper is quite dense; some important materials (e.g., Figure 7) appear in the appendix.

We agree that the presentation could be improved. To enhance clarity and make the paper more self-contained, we will move the following materials from the appendix to the main text in the revised version:

  • Figure 7, illustrating parallel, sequential, and graph-structured test-time scaling;
  • Depth-lean Planner (Appendix E), enabling a side-by-side presentation of the two planning strategies;
  • Complete Pipeline Pseudocode (Algorithm 2), providing a unified overview of the framework;
  • Action Allocation Analysis (Figure 9, Appendix F.3), illustrating how actions are allocated across different settings.

Q1. L408: “using the same model pool as above”: Does “above” refer to the pilot experiments?

Yes, the phrase refers to the model pool used in the pilot experiments in Section 4, consisting of Llama-3.2-1B, Llama-3.1-8B, Gemma-3-27B, and Qwen-2.5-72B (Appendix C.2).

We thank the reviewer again for the valuable feedback, which will help us improve the clarity and accessibility of the manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.