acceptodds
Under review as a conference paper at ICLR 2027

Spend Where It Counts: Dynamic Budget Allocation for Multi-Turn LLM Evaluation

18 views

Abstract

Evaluating and predicting the performance of large language models (LLMs) in multi-turn conversational settings is critical yet computationally expensive; key events—e.g., jailbreaks or successful task completion by an agent—often emerge only after repeated interactions. These events might be rare and, under any feasible computational budget, remain unobserved. Recent conformal survival frameworks construct reliable lower predictive bounds (LPBs) on the number of iterations to trigger the event of interest, but rely on static budget allocation that prohibits adaptivity in multi-turn setups. To address this, we introduce Dynamic Allocation via PRojected Optimization (DAPRO), a theoretically valid dynamic budget allocation framework for bounding the time-to-event in multi-turn LLM interactions. We prove that DAPRO satisfies the expected budget constraint and provides distribution-free, finite-sample coverage guarantees without requiring the conditional independence between censoring and event times assumed by prior conformal survival approaches. A key theoretical contribution is a novel coverage bound that scales with the square root of the mean censoring weight over only a subset of the samples rather than the worst-case weight, yielding tighter guarantees than prior work. Furthermore, DAPRO can be employed to obtain unbiased estimates of population-level evaluation metrics, such as the jailbreak rate, under limited computing resources. Comprehensive experiments across agentic task success, LLM jailbreaks, toxic content generation, and RAG hallucinations demonstrate that DAPRO achieves coverage closer to the nominal level with lower variance than static baselines, while not exceeding the budget constraint in expectation.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Conformal Prediction, Survival Analysis, Dynamic Budget Allocation, LLM Evaluation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_yJjvOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes DAPRO, a dynamic budget allocation method for multi-round LLM evaluation. This method adjusts the probability of continuing to run based on interaction history, and combines inverse probability weighting and statistical calibration to estimate the prediction bound of event occurrence time and overall event rate under a limited budget. Experiments cover scenarios such as toxic generation, jailbreaking, and instruction following.

Critical strengths

The problem has practical significance, combining adaptive budget allocation with statistical validity, and providing theoretical analysis in terms of coverage and expected budget.

Critical weaknesses

(1) The only substantive external baseline is Static, while Uncalibrated and DAPRO w/o CRC serve as a basic control and an ablation, respectively. These comparisons cannot substitute for comparisons with alternative budget allocation strategies. Consequently, the current results do not distinguish whether the gains arise from using interaction history, dynamic stopping, or the proposed optimization procedure.

(2) The main experiments emphasize coverage deviations and estimator variance, but these metrics are insufficient to establish that the predictive bounds are more informative in practice. Moreover, the experiments rely on 4,000 additional training trajectories to construct the predictor, while excluding their acquisition cost from the main calibration budget.

(3) The limited experimental presentation in the main text substantially weakens readability and persuasiveness. The main text presents results primarily through a few box plots, while several important diagnostics, robustness analyses, and experimental details are deferred to the appendix. The metrics and model coverage also vary across tasks, and the absence of a compact summary table makes it difficult to assess the consistency and scope of the improvements. The authors should integrate experiments that directly support the main claims into the main text in a more compact format, rather than leaving essential evidence scattered throughout the appendix.

Questions for authors

(1) Can the authors include comparisons with more recent related methods for budget allocation and budget-constrained evaluation, beyond the Static baseline?

(2) Does DAPRO still offer an overall cost advantage when accounting for training trajectory collection, predictor training, policy learning, and online scoring? Please report the total cost of the complete evaluation pipeline.

(3) Can the authors move the key ablation studies, robustness analyses, and results under different budgets from the appendix into the main text, and provide a unified summary table? The current presentation makes it difficult to assess the consistency of the improvements and the scope of the method’s effectiveness.

3 comments

Dear Reviewer yJjv,

Thank you again for your careful review. As the discussion period ends on November 18, we wanted to check whether our response addressed your concerns. We implemented each of your three requests:

  • Baselines: To our knowledge, Static is the only prior method that provides predictive-bound guarantees in this setting. We added Active Statistical Inference (Appendix F.4.14) for metric estimation, a simple monotone-rule baseline, and ablations isolating dynamic stopping, the history score and the optimization (Table 2).
  • Summary: We added a main-text table showing that DAPRO lowers variance in 18/20 LPB, 17/20 UPB, 19/20 event-rate, and 20/20 RMTTE configurations with comparable bound sizes (informativeness) (Table 1). The ablation summary and the budget sweep are now also in the main text (Tables 2 and 3).
  • Cost: we added full-pipeline accounting (Appendix E.5), and DAPRO maintains its advantage with a 20k-turn training budget (Appendix F.4.10).

Do these additions address your main concerns? If any issue remains unresolved, we would appreciate your feedback and the opportunity to clarify it before the discussion closes.

Thank you again for your time and consideration.

Thanks for the response and additional experiments. The evaluation still relies heavily on Static, while alternative comparisons remain limited and mainly in the appendix. I also find the manuscript difficult to follow as a human reviewer, making its contribution hard to assess. I will keep my original score.

Dear Reviewer yJjv,

Thank you for reading our response and for your reply.

On the comparisons: to our knowledge, Static (Davidov et al., 2026) is the only existing method that constructs bounds on the time-to-event with coverage guarantees in this setting, which is why it is our primary baseline. We therefore designed additional comparisons specifically for this setting. Table 2 in the main text compares DAPRO with a Uniform+CRC policy, a random-score variant and a uniform-reference objective. The revision also includes a sweep over the weight of our optimization objective and compares DAPRO with a simple monotone rule and Active Statistical Inference. In the final version, we will move the monotone-rule and ASI comparisons into the main text as well.

On assessing the contribution: Section 1.1 summarizes our four main contributions: a tighter coverage guarantee that does not require conditional independence between censoring and event times, a budget-validity guarantee, population-level metric estimation, and a comprehensive empirical evaluation. Table 1 in the main text summarizes the comparison with Static across all evaluated configurations. DAPRO lowers variance in 74 of 80 configurations, with mean variance reductions of 58.5% for lower bounds, 27.2% for upper bounds, 52.6% for event-rate estimation and 66.4% for RMTTE estimation, while keeping bound sizes broadly comparable (a mean change of at most 0.4 turns).

On readability: Section 3.3 explains both theorems in plain language. To make the paper easier to follow, the final version will add an overview figure of the DAPRO pipeline.

Thank you again for your time.

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

The paper evaluates multi-turn LLM interactions through the turn T at which an event (jailbreak, toxic response, hallucination, task success) first occurs, under an expected budget E[Σ_i min(T_i, C_i)] ≤ B (eq. 1). DAPRO splits the calibration set into a policy-fitting fold, an optional conformal-risk-control (CRC) fold and a deployment fold; deployed trajectories are continued by Bernoulli draws whose probabilities are a learned two-bin monotone map of a survival-model score, yielding known inverse-probability weights for the LPB calibration of Davidov et al. (2026). Theorems 4/5 give a PAC coverage gap of order sqrt(ν̄/N) with ν̄ bounding the mean weighted error rather than the maximum weight; Theorem 2 shows the CRC-calibrated policy meets the expected budget; Appendix B extends to upper bounds via a sequential augmented Horvitz–Thompson estimator, and F.2 reuses the weights for benchmark-level event-rate estimation. Experiments on four PAIR-generated datasets × four target models (50 calibration/test splits, one survival model per dataset) compare DAPRO with/without CRC to the static allocation of Davidov et al. and an uncalibrated predictor.

Critical strengths
  1. A valid, implementable sequential-design route to known censoring weights. Proposition 2/Theorem 5 replace C ⊥ T | X by eq. (31), which holds because the algorithm draws the continuation coins itself; the bookkeeping in C.1 is careful and the CRC selector (eq. 6; risk_controlled_budget.py:108-206) matches the proof in C.2 exactly. This makes history-adaptive allocation compatible with distribution-free coverage, which the static method cannot offer.
  2. Large, well-controlled empirical study with clean code. 50 paired splits, four datasets, four targets, eleven ablations, and figure code (src/paper_figures/config.py) that reproduces the appendix configuration keys. The LPB coverage-variance reductions on Toxicity/Red-Team/AutoIF (Fig. 6, 8, 14: roughly 3–8×) are large enough to survive moderate confounds.
Critical weaknesses
  1. The budget axis measures different quantities for Static and DAPRO, so the "same budget" claims are not established. Eq. (1) constrains realised turns and p.57 says figures report "realized budget", but src/paper_figures/data.py:201-204 states: "Static is charged its assigned censoring horizon sum(C_i)/n even when an event terminates generation earlier. DAPRO is charged the actual event-stopped turns" (also optimized_allocators.py:46-47: "deliberately does not refund the unused suffix when T_i < C_i"). So in every budget panel (Fig. 2, 3, 5–19, 21–32) Static's true consumption lies below the plotted ≈B̄, most strongly where events occur early (p.49), while DAPRO w/o CRC runs at ≈B̄. The paper does not disclose this, does not report Static's realised cost (logged as actual_event_stopped_budget_per_sample), and omits the natural budget-matched static baseline (π_i scaled with the same model's E[min(T, f_prior) | X]). Since the main evidence is "more events and lower variance at the same budget" (Fig. 2, 4, 6), this determines how much of the gain is adaptivity rather than extra realised budget.
  2. Several theoretical and empirical claims are stronger than the appendix supports. (a) Theorem 4 needs a ν̄ independent of D_cal1, D_crc; by construction only ν̄ ≤ 1/ε = 200 is guaranteed (Remark 1; ε = 0.005, p.43), giving Δ ≈ 0.63 at N = 3000, δ = 0.05. The 5–24 pp gaps of Fig. 20 plug the realised split mean into Δ (analysis/plot_toxicity_lpb_coverage_gaps.py:78-104; eq. 144 reads "ν̄ = E[...] ≤ ν̄"), which the theorem does not license. (b) "Without requiring the conditional independence" (abstract) and "a broad class of survival analysis tasks" (p.7) describe designed censoring whose propensities are known given T_i (eq. 31); for observational censoring this is the same assumption restated. (c) Theorem 2 (p.7) omits the CRC/feasibility conditions of C.2, and §3.1's "as formally shown in Appendix C.3" rests on Assumptions 3 (pathwise oracle fit) and 5 (vanishing cross-term moments, exact only "if the coordinates of the score vector are mutually independent"); the authors' own note reads "Do not claim that median K2 makes the raw Phase-I empirical constraint a theorem" (analysis/diagnostics/k2_crc_free_budget_report.md). (d) "lowest coverage deviation and variance among the tested methods" (p.51) is contradicted by Fig. 12 (Llama3.1: Static 0.61 vs DAPRO 0.63; Phi-4: DAPRO w/o CRC 1.00 > Static 0.95); "Across all these five benchmarks, DAPRO with CRC has lower empirical variance than Static" (p.57) by Fig. 16 Phi-4 (≈14 vs ≈11.5 pp²); and Fig. 15's caption describes a panel the figure lacks. These prevent me from taking the contribution list at face value.
Questions for authors
  1. For each dataset/target in Fig. 2–19, what is Static's realised budget Σ_i min(T_i, C_i)/N, and how do observed events and coverage variance compare against a static allocation whose π_i is scaled so that its realised expected cost equals B?
  2. Can a non-trivial, calibration-independent ν̄ be certified before seeing D_cal1 (e.g. from D_train and the policy family), and what is Δ at N = 3000 under that certificate?
  3. UPB: the code configuration (src/paper_figures/config.py:102-108) runs UPB at 80% on all five datasets with Phase-I size 200, yet the paper reports only AutoIF (Fig. 3) and the Toxicity estimator ablation (Fig. 30). Could you report the remaining UPB cells and state which estimator (ordinary HT vs terminal AHT) Static uses in Fig. 3?
  4. How were N_1 (50 LPB / 100 metrics / 200 UPB), K = 2, C_max = 2B̄ and the soft-prefix objective chosen, given that Fig. 21 shows coverage variance increasing monotonically with Phase-I size and analysis/diagnostics/all_results_method_selection/README.md compares 720/1584/773 configurations on the same 50 splits?
  5. With M = t_max = 200, does the trimming of §2 do anything, i.e. is the maximum weight controlled only by ε?
3 comments

Dear Reviewer uKWE,

Thank you again for your detailed review and for examining our code. As the discussion period ends on November 18, we wanted to ask whether our response addressed your main concerns.

To separate the effect of extra realized spend from the allocation itself, we employed DAPRO with an allowance equal to Static's realized spend (Appendix F.4.13). On Toxicity/Qwen, DAPRO's LPB coverage variance is 0.22 pp$^2$ versus 2.74 pp$^²$ for Static, while spending 12.8 versus 13.4 realized turns per sample. Static's realized spend is now reported for all configurations (Table 7), and Section 4 states which part of DAPRO's advantage comes from budget use.

On the theory, we agree that the certificate at ε=0.005\varepsilon = 0.005 is conservative, yet tighter than prior bounds. The empirical diagnostics in Appendix F.3 suggest the gap is considerably tighter in practice. We also moved the feasibility condition into Theorem 2.

Does this address your main concerns? If any concern remains, we would be glad to clarify it before the discussion ends.

Thank you again for your careful evaluation.

Thank you for your detailed responses and additional experiments. They have addressed my main concerns and I decide to keep my positive score unchanged. Good luck!

Dear Reviewer uKWE,

Thank you for your engagement throughout the discussion. Your detailed review improved and strengthened the paper.

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

DAPRO allocates a limited interaction budget across multi-turn LLM trajectories. A policy learned on a pilot split maps scores from the observed history to continuation probabilities. The method records these probabilities and uses inverse-probability weighting to correct for censoring. It can also use conformal risk control (CRC) to control expected expenditure, subject to feasibility conditions. The paper derives a coverage bound for this adaptive acquisition scheme, including a finite-sample gap, and extends the approach to event-rate estimation on a fixed benchmark. The main experiments cover toxicity, instruction following, and jailbreaks. The supplement includes further tasks and ablations.

Critical strengths
  1. Coverage analysis for acquisition that uses conversation history DAPRO adjusts continuation decisions as a conversation develops and keeps the acquisition probabilities needed for weighting. Theorem 1 allows censoring and event times to depend on one another given the initial prompt. The bound depends on a weighted-error moment, which can give a more informative guarantee than a bound based on the largest weight. This extends the statistical treatment beyond static allocation.
  2. Evidence across prediction and event-rate estimation Figures 2 and 3 examine coverage deviation and budget use on toxicity and instruction following. On Toxicity, DAPRO improves on Static in both mean absolute coverage deviation and coverage variance. Figure 4 reports about 72% lower variance on average for event-rate estimation. The supplementary objective, score, Uniform+CRC, and mapper ablations provide further support.
Critical weaknesses
  1. The guarantees need a more usable statement For Theorem 1 on page 7, I would like to see the coverage lower bound at the experimental size of 3000 calibration examples. The theorem already includes a finite-sample gap. The floor on cumulative acquisition probability gives a general bound on the conditional weighted-error moment, but that bound may be conservative. Are the smaller moment values used in the numerical evaluation valid upper bounds for certification, or diagnostics computed from more complete data? Coverage observed near the target does not answer this question. Theorem 2 should state the feasibility condition given in Appendix C.2. Paying for the initial observation phase in Section 3.1 is not sufficient to ensure that Equation (6) has a feasible candidate. If the condition fails, does the procedure stop and report an infeasible budget, or use a fallback? If it uses a fallback, the authors should explain when the positive acquisition probabilities required for weighting are retained.
  2. The sources of the experimental gains are not fully separated The objective, score, Uniform+CRC, and mapper-capacity ablations address several design choices. To assess the learned mapping itself, I would still like a comparison with a simple monotone continuation rule that uses the same history score and CRC calibration. Matching total acquisition costs in one representative setting would help distinguish the benefit of optimizing the mapping from the benefit of using an informative score. For the AutoIF UPB result in Figure 3 on page 8, which miscoverage estimator is used with Static and with DAPRO? Appendix F.4.9 shows on Toxicity that augmented estimation also improves Static. I cannot tell from the main AutoIF comparison how much of the gain comes from allocation and how much comes from the estimator. A comparison using the same estimator, or a reference to an existing one, would help resolve this.
Questions for authors
  1. With 3000 calibration examples, what coverage does Theorem 1 certify after accounting for the finite-sample gap? Which bound on the weighted-error moment can be justified, and which reported values are experimental diagnostics?
  2. What feasibility conditions should accompany Theorem 2? Please specify what happens when Equation (6) has no feasible candidate, including the conditions under which any fallback preserves positive acquisition probabilities.
  3. Could one representative experiment compare the learned mapping with a simple monotone rule, using the same history score, CRC calibration, and total acquisition budget?
  4. Please identify the miscoverage estimator used by each method in Figure 3's AutoIF UPB comparison and report or point to a comparison using the same estimator.
1 comment

Dear Reviewer w8Jq,

Thank you again for your thoughtful review. As the discussion period ends on November 18, we wanted to check whether our response addressed your questions. We ran the two experiments you requested:

  • A simple monotone rule using the same history score, CRC calibration, and budget: DAPRO attains lower variance (event rate 6.4 vs 9.9 pp²; RMTTE 9.4 vs 13.0 turns²).
  • AutoIF UPB with the same Terminal AHT estimator for both methods: DAPRO still reduces coverage variance by 40.5% (Appendix F.4.9).

We also reported the certified gap at N = 3000, separated it from the empirical diagnostics (Appendix F.3), and moved the feasibility condition into Theorem 2.

Do these resolve your main concerns? If any point remains unclear, we would be glad to clarify before the discussion ends. Thank you again for your time and feedback.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.