PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Budget Allocation for LLM Evaluation under Hard Resource Constraints

Shai Feldman, Yaniv Romano

arXiv:2610.07362v1cs.LG

TL;DR

Multi-turn LLM evaluation can leave event times censored, while existing allocation methods may exceed a fixed budget on a particular run. HARP reallocates budget under a deterministic constraint and provides guarantees for predictive bounds and metric estimates despite dependent acquisition; experiments report effective budget use and low-variance estimates.

  • Problem

    Existing time-to-event allocation methods can exceed the available budget on a particular run, while unknown trajectory costs make deterministic resource control difficult.

    Source: §1 · pp. 1–2

  • Method

    HARP uses dependent acquisition and adaptive budget reallocation to construct predictive bounds and estimate evaluation metrics under hard resource constraints.

    Source: §1.1 · p. 2, §3.2 · p. 5

  • Results

    Across experiments, HARP’s predictive bounds and metric estimates retain finite-sample guarantees, with effective budget use and low-variance estimates.

    Source: §5 · p. 10

  • Takeaways & Limitations

    The authors recommend HARP-D with depth for predictive bounds and without depth for metric estimation, because depth lowers median LPB coverage variance but raises metric-estimate variance.

    Source: §5 · p. 10

    Guarantees require i.i.d. calibration and test data with correct audit labels; HARP also bounds a single event time and requires B ≥ K(1 + η)M.

    Source: §5 · p. 10

Abstract

from arXiv · show

We evaluate large language models (LLMs) in multi-turn interactions through their time-to-event: the number of interaction steps required to produce an event of interest, such as a successful jailbreak or agentic task completion. Under limited compute, interactions may be terminated before the event occurs, so that event times are only partially observed (censored). Existing allocation methods for calibrating time-to-event bounds satisfy the budget only in expectation and can exceed the available budget on a particular evaluation run. Enforcing a hard constraint is particularly challenging as the cost of a trajectory is initially unknown. We introduce Hard-budget Allocation with Reflow for Predictive calibration (HARP), a budget allocation that satisfies hard resource constraints and adaptively reallocates unused budget. We show how to use HARP to construct lower predictive bounds (LPBs) on the time-to-event and to estimate evaluation metrics such as the jailbreak rate on a fixed benchmark. Although HARP induces dependence in acquisition decisions across different trajectories, we prove that HARP never exceeds the target budget, that its LPBs have finite-sample coverage guarantees, and that its metric estimates are unbiased. Experiments on agentic task success, LLM jailbreaks, toxic content generation, and RAG hallucinations show that HARP achieves coverage close to the nominal level with low variance, while never exceeding the given budget.

1 Introduction

Multi-turn time-to-event evaluation can capture behavior missed by one-turn success rates, but unknown trajectory costs make hard-budget allocation difficult. HARP addresses this with deterministic budget control and guarantees for predictive bounds and metric estimates under dependent acquisition.

1 Introduction

  • Time-to-event evaluation captures multi-turn behaviors that one-turn success rates do not measure.Examples include eventual compliance after refusals and eventual coding success after initial failures.Source: §1 · p. 1
  • Unknown stochastic trajectory costs, dependent allocations, and saved budget from early events make deterministic reallocation challenging.Reflow must preserve feasibility for remaining trajectories throughout execution.Source: §1 · pp. 1–2
  • Earlier methods [3] [4] provide informative bounds and metric estimates but satisfy the budget only in expectation.Reserving maximum lengths can waste budget, while acquiring until exhaustion can invalidate guarantees through distribution shift.Source: §1 · pp. 1–2

1.1 Our contribution

  • HARP provides finite-sample coverage guarantees and unbiased metric estimates despite acquisition dependence across samples.Prior guarantees [3] [4] assume independence across samples, while HARP deliberately couples decisions within groups.Source: §1.1 · p. 2
  • HARP formally satisfies the deterministic budget constraint and empirically uses more of the budget than prior methods [4].Lower variance is also valued because evaluations typically use a single realized dataset.Source: §1.1 · p. 2, §1 · p. 2
  • The depth rule empirically reduces coverage variance, and HARP is evaluated on agentic success, toxic content, jailbreaks, and RAG hallucinations.Experiments report deterministic budget compliance and low variance under this more restrictive resource constraint.Source: §1.1 · p. 2

2 Background

The paper frames multi-turn evaluation as observing event times that may be right-censored, then calibrating predictive bounds from calibration trajectories. Its background also describes random acquisition and the expected-budget DAPRO approach.

2 Background

  • An interaction tracks prompts, responses, and audit annotations until the event occurs or the interaction ends.The time-to-event is the first event turn, and censoring before that turn leaves the event time unobserved.Source: §2 · p. 3
  • A pre-trained conditional-quantile model supplies nondecreasing time-to-event predictions, trimmed to the maximum allowed sequence length.The calibration goal is a predictive bound with miscoverage at most α up to a finite-sample deviation.Source: §2 · p. 3
  • The stated coverage probability averages over calibration trajectories and acquisition randomization, with an independent test point inside the probability.The paper distinguishes this guarantee from marginal coverage averaged over repeated calibration runs.Source: §2 · p. 3
  • Random acquisition uses resolution indicators and conditional resolution probabilities in a Horvitz–Thompson estimator.The estimator’s denominator includes all calibration samples, including prompts with unobserved event times.Source: §2 · p. 3
  • DAPRO [4] learns an allocation policy on one data split, deploys it on another, and uses conformal risk control for an expected-budget guarantee.It dynamically updates continuation decisions from trajectory history, extending the static allocation of Davidov et al. [3].Source: §2 · pp. 3–4

3 Proposed Method and Theory

HARP allocates a fixed budget across groups, commits and reflows resources using realized costs, and offers static or dynamic acquisition with optional depth restrictions. Its guarantees cover deterministic budget control and finite-sample predictive bounds under stated conditions.

3 Proposed Method and Theory

  • HARP divides calibration samples into groups and iteratively allocates each group from the remaining budget.Randomized censoring times are chosen so worst-case group cost fits the remaining allowance, then the ledger is updated using actual turns spent.Source: §3 · p. 4

3.1 Reservations, commitments, and reflow

  • A reference set supplies predictions without acquisition cost, but excluding it from calibration reduces the estimation sample.In experiments, the total cap is scaled by the number of working and reference prompts.Source: §3.1 · p. 4
  • The allowance reserves turns for later groups while the pacing budget distributes remaining resources, and actual underspend reflows to the next group.Weighted pivotal rounding selects commitments under a cap; turns saved by early events or randomized stopping become available to later groups.Source: §3.1 · pp. 4–5

3.2 Completion, continuation, and depth

  • HARP-Dynamic adapts within trajectories using history-based miscoverage scores and remaining-cost estimates, while HARP-Commit runs committed samples to event or horizon.Continuation draws are independent across samples; depth restricts candidates and shortens resolution horizons, saving budget at the cost of limiting the largest selectable LPB.Source: §3.2 · pp. 5–6

3.3 Theoretical coverage and budget guarantees

  • HARP satisfies the deterministic budget constraint for every realization, even with inaccurate predictions or non-i.i.d. data.The theorem’s budget guarantee is stated under condition (4).Source: §3.3 · p. 6
  • With probability at least 1 − δ, the selected LPB has population miscoverage at most α + Δ under the stated i.i.d. and variance-envelope conditions.The guarantee holds despite dependent censoring times, with dependence entering the correction through v⋆.Source: §3.3 · pp. 6–7
  • The UPB PAC result requires i.i.d. calibration and test data, nonincreasing effective reach weights, and a positive lower bound on those weights.The result uses a suffix-envelope selector with an infinite fallback.Source: §3.3 · p. 7

4 Experiments

Across four target models, HARP stays within the hard budget while using more of it than DAPRO. Predictive-bound coverage deviations are similar on toxicity, DAPRO is closer on AutoIF, and HARP reduces event-rate estimate variance on red teaming.

Experimental setup

  • Experiments used four target models, twenty random-split runs, and a pre-trained survival model; calibration budgets were 20 turns per sample for toxicity LPBs and metrics, and 10 for other LPBs.The survival model was trained on 4,000 independent samples and predicted event time through M = 200; training had a separate budget.Source: §4 · p. 7

Predictive bounds

  • 1.08 versus 1.05 percentage points was the mean absolute coverage deviation for DAPRO and HARP on toxicity; on AutoIF, DAPRO had smaller LPB and UPB deviations.On Qwen 2.5 14B AutoIF, LPB deviations were 1.025 versus 1.245 pp and UPB deviations were 1.160 versus 1.225 pp for DAPRO and HARP, respectively.Source: §4 · p. 8, Figure 1 · p. 8, Figure 2 · p. 9

Population metrics

  • 60.65% lower variance across four target models was achieved by HARP for red-team marginal event-rate estimates than by the comparison methods.Both calibration methods recover the correct metric in expectation.Source: §4 · p. 8, Figure 3 · p. 9

Budget

  • 94.51%, 95.70%, and 97.03% of the budget was used by HARP for LPBs, UPBs, and metrics, respectively, without overruns; DAPRO used less and sometimes exceeded the budget.DAPRO used 91.58%, 69.14%, and 82.80%, with overrun frequencies of 13.00%, 3.00%, and 12.75%, respectively.Source: §4 · p. 8

5 Discussion

HARP couples sample-level censoring times to meet hard multi-turn budgets while retaining finite-sample guarantees, and the experiments motivate different depth settings for bounds and metrics. The discussion also identifies data-quality and event-scope boundaries, while related work distinguishes HARP’s allocation and inference setting from prior methods.

5 Discussion

  • HARP couples censoring times across samples yet provides finite-sample guarantees for predictive bounds and estimated metrics under hard budget constraints.Unlike DAPRO [4], it does not require a policy-learning phase or a CRC budget-calibration step.Source: §5 · p. 10
  • Guarantees require i.i.d. calibration and test data with correct audit labels, and HARP currently constructs bounds for a single event time.The discussion notes noisy or missing labels, multiple event times, heavy censoring under smaller budgets, and a minimum total budget B ≥ K(1 + η)M as boundaries or extensions.Source: §5 · p. 10
  • HARP-D with depth is recommended for predictive bounds, while HARP-D without depth is recommended for metric estimation.Depth reduces median LPB coverage variance but increases metric-estimate variance.Source: §5 · p. 10

A Additional Related Work

  • Yamin et al. [5] study fixed-treatment-count assignment with dependent rounding; HARP instead handles heterogeneous maximum trajectory reservations, event-stopped costs, and sequential reallocation.HARP’s calibration uses a reservation invariant and predictable-group analysis.Source: A Additional Related Work · p. 13
  • HARP’s sequential-ledger analysis applies weighted-rounding cylinder inequalities to sample-local continuation and subsequent predictive calibration.The proof is provided to specify the needed rounding properties, including those established in budgeted-rounding work such as Byrka et al..Source: A Additional Related Work · p. 13
  • DAPRO [4] is the direct baseline: its history-dependent score, inverse-probability correction, and augmented UPB construction remain relevant, while HARP addresses inference under coupled acquisition.The surrounding literature includes adaptive cut-offs for conformalized survival analysis and prediction-powered inference [21].Source: A Additional Related Work · p. 13

B Complete Budget and LPB Proofs

Weighted pivotal rounding updates pairs of fractional selection probabilities while preserving the weighted sum in expectation. Its proof also establishes product inequalities that do not require independent rounded coordinates.

B.1 Weighted pivotal rounding

  • Each rounding step selects two fractional coordinates and shifts their probabilities in opposite directions using a randomized increment scaled by their costs.At least one coordinate becomes integral at each step; a remaining fractional coordinate is rounded by a Bernoulli draw.Source: §B.1 · p. 13
  • The weighted sum is unchanged through pairwise updates, and the final Bernoulli rounding changes it by at most the largest cost M.This follows because each pairwise increment has conditional mean zero.Source: §B.1 · p. 13
  • For any fixed subset, products of selected or unselected coordinates have nonpositive conditional drift, yielding supermartingales without independent output coordinates.The proof extends the unselected-coordinate inequality to products involving the weights h_i by a nonnegative-coefficient expansion.Source: §B.1 · p. 14

B.2 The pathwise ledger invariant

This section develops HARP’s pointwise budget guarantee and the conditions and procedures for valid LPB inference and depth-dependent acquisition, while characterizing unused budget and specifying planning and candidate-selection rules. It also uses a range argument to bound signed updates for acquired samples, with a tighter sufficient choice under the specified D policy.

B.2 The pathwise ledger invariant

  • HARP’s ledger invariant ensures total spend never exceeds B, while positive reach is guaranteed; with Λ = 109, ω = 1/2, and M = 200, the continuation bound is 1.58 × 10^-6.The stronger bound remains too small for informative coarse uniform PAC corrections; arbitrary continuations retain the product-of-floors bound.Source: §B.2 · p. 14

B.3 A filtration that permits reflow

  • Conditioning on fixed designs and prior groups permits reflow while preserving a nonnegative-supermartingale concentration argument and a finite-sample LPB selection guarantee.The lower-tail bound applies to a nonnegative Horvitz–Thompson estimator without a bounded upper weight, given the stated second moments; selection uses the first candidate whose population risk exceeds α + ∆.Source: §B.3 · p. 15, §B.4 · pp. 15–16

B.5 Restricted moment envelopes and jumps

  • Restricted moment envelopes may replace the global envelope when they cover the risk-crossing candidate, which matters because discrete event times and quantile grids can create risk jumps.An envelope restricted to candidates with risk at most the threshold can miss the crossing candidate and does not justify the proof.Source: §B.5 · p. 16

B.6 Expected unused budget

  • The pacing-defect identity gives E[L_K] ≤ B/K under exact conditional pacing in every nonfinal group, but recycling savings cannot guarantee unconditional budget utilization.Commitment caps, forecast errors, continuation thinning, or too few useful remaining turns can reduce realized spend.Source: §B.6 · pp. 16–17

C.2 The LPB depth planner

  • Reference-set cost forecasts and planning surrogates guide LPB design and depth selection, but actual resolution depends on the ledger, pivotal commitments, and continuation.The reference cost curve uses logarithmically spaced multipliers from 10^-9 to 10^9; model error and commitment caps can prevent exact conditional pacing.Source: §C.1 · p. 17, §C.2 · p. 18

D.1 Candidate family, acquisition, and selection

  • For UPBs, the selector chooses the smallest candidate whose empirical coverage meets the target across its entire suffix, with depth versions mixing full and shallow horizons.The depth mixture uses q = .25 and retains every finite target and the reported UPB family.Source: §D.1 · pp. 19–20

D.2 Unbiasedness with depth-dependent acquisition

  • With positive depth-tail probabilities and a causal prediction path independent of sampled depth, sequential weighting is unbiased when design probabilities and resolution are correct.Depth-dependent commitment probabilities cancel in expectation, and the prediction increments telescope to the terminal contribution.Source: §D.2 · p. 20

D.3 A valid range bound for signed updates

  • Sequential augmented contributions admit a valid range bound when predictions lie in [0, 1] and update weights are nondecreasing between 1 and W.The same interval also contains the initial prediction when there are no updates.Source: §D.3 · p. 20
  • The signed-update expression lies in [1 − w_J, w_J] ⊆ [1 − W, W], a sharper bound than separately bounding all J increments by W.All but the last coefficient are nonpositive and sum to 1 − w_J; the positive coefficient contributes at most w_J.Source: §D.3 · p. 21
  • Because each observed sample is a prefix and (36) is nonincreasing along it, the range lemma applies to every acquired sample.Both G_i(t) and the conditional-depth reach are nonincreasing along the prefix.Source: §D.3 · p. 21
  • With q = 1 when depth is not used, the specified D policy improves the sufficient choice to W = (qep0)^−1.Source: §D.3 · p. 21

D.4 Signed pivotal concentration and adaptive reflow

This section develops a signed exponential comparison for HARP’s dependent, adaptively reflowed updates and uses it to obtain concentration bounds for UPBs. The sharper comparison relies on HARP’s sample-local structure, not merely bounded sums.

D.4 Signed pivotal concentration and adaptive reflow

  • HARP represents each group’s signed updates through sample-local coefficients and latent variables that are conditionally independent across samples.The representation applies to C and D, including insured depth, because each sample’s stopping and depth draw do not depend on another current sample’s history.Source: §D.4 · p. 21
  • Under the sample-local representation and two cylinder inequalities, the signed exponential comparison controls dependent group updates through their marginal conditional moments.The proof conditions on latent variables and the group past, then uses conditional independence and Jensen’s inequality to establish the comparison.Source: §D.4 · pp. 21–22
  • For a fixed candidate, conditional Hoeffding’s lemma bounds the centered update using range length 2W − 1.The proof applies this bound to the marginal conditional moment-generating functions and iterates conditional expectations over the ledger filtration.Source: §D.4 · p. 22
  • The variance-sensitive signed-UPB bound uses a variance envelope and a correction derived from a lower-tail bound with scale 2W/3.The paper permits taking the minimum of this correction and the range-only correction; the sharper comparison requires HARP’s sample-local representation and cylinder inequalities.Source: §D.4 · p. 22
  • The signed comparison does not imply negative covariance between updates, and both valid UPB bounds can be vacuous when propensities are small.Treating groups as arbitrary dependent blocks gives a less sharp range-based argument; the sharper signed comparison depends on HARP’s additional structure.Source: §D.4 · p. 22

E Population-Level Metric Estimation

This section estimates full-horizon event probability and restricted mean event time from one HARP acquisition, with conditional event time treated separately. It establishes design-unbiasedness and population bounds for bounded sequentially augmented metrics, while noting that a ratio estimator is not generally unbiased.

E Population-Level Metric Estimation

  • The targets include full-horizon event probability and restricted mean event time; conditional event time is a separate estimand.For harmful events these describe failure probability and time to failure, while AutoIF successful completion reverses the interpretation.Source: E Population-Level Metric Estimation · p. 23
  • For metric acquisition, HARP uses the event T ≤ M and full horizon M, retaining the same commitment and continuation rules for C and D.With depth, the LPB reference planner chooses a shallow horizon and a 0.25 probability of acquiring to M, optimizing a surrogate for attainable LPB size rather than metric variance.Source: E Population-Level Metric Estimation · p. 23
  • Event-rate estimation uses sequential augmentation, while restricted mean estimation uses a complement form that avoids requiring a fully observed event-free trajectory.Unobserved events contribute zero, so their unknown event propensity is not needed.Source: E Population-Level Metric Estimation · p. 23
  • HARP’s weighting identity gives design-unbiased working-sample means and, with a uniform reference split, recovers the parent-cohort mean; bounded sequentially augmented metrics also admit two-sided population bounds.With iid working trajectories, the identity gives population unbiasedness; the budget theorem applies in either the fixed-population or iid setting.Source: E Population-Level Metric Estimation · p. 23
  • The conditional event-time ratio is not generally unbiased, even though its numerator and denominator are unbiased totals.It is reported as undefined when the denominator is zero.Source: E Population-Level Metric Estimation · p. 24

F.1 Benchmarks, event definitions, and data generation

The appendix evaluates HARP on five interaction settings with defined event labels and matched target-model configurations. It documents the prediction model, acquisition budgets, variant selection, and comparison statistics.

F.1 Benchmarks, event definitions, and data generation

  • Five settings cover toxicity, red teaming with two judges, retrieval-grounded hallucination, and AutoIF, with events defined by harmfulness, ungroundedness, or successful instruction following.Event times are one-based; 201 denotes no event within the 200 paid-turn horizon.Source: §F.1 · p. 24

F.2 Prediction model

  • The prediction model embeds text histories, maps them through a Transformer and survival-logit head, and outputs a conditional time-to-event PMF over the 200-turn horizon.Cached prediction row t becomes available after acquiring t interactions; reference planning uses initial predictions as proxies for later ones.Source: §F.2 · p. 24

F.3 Acquisition settings and comparison accounting

  • LPB budgets follow the DAPRO comparison, while UPB and full-horizon metric runs use 20 turns per prompt; acquisition also specifies risk smoothing, continuation floors, and depth settings.The stated reserve is 15,960 turns, or 7.98 per parent prompt, making both prescribed budgets feasible.Source: §F.3 · p. 25

F.4 Choice of HARP variant

  • Variant selection ranks coverage deviation for bounds and normalized squared error for metrics, selecting HARP-D+depth for bounds and HARP-D without depth for metrics.The displayed comparisons include the ten runs used for selection, so they are descriptive rather than an independent held-out evaluation.Source: §F.4 · p. 25

F.5 Statistics, figures, and provenance

  • Statistics use twenty run-level values, and metric plots report event-rate error, variance, estimates, and benchmark-cohort means for acquired methods.Weighted estimates are displayed without clipping; actual spend may differ across methods.Source: §F.5 · pp. 25–26

F.6 Completion and depth ablation

The ablation compares completion variants C and D, with and without depth. Depth lowers LPB coverage-variance ratios but raises metric-variance ratios, supporting different recommended variants for bounds and metrics.

F.6 Completion and depth ablation

  • The ablation retains all four C/D and depth variants; D uses a closed-form model-based risk/cost target divided by accumulated reach, with a per-turn floor.Unlike DAPRO, D does not fit a time/score-bin policy.Source: §F.6 · p. 26, Table 2 · p. 26

F.7 Interpreting the contribution of continuation and depth

  • Depth lowers median LPB coverage-variance ratios for both C (1.935 to 1.017) and D (1.410 to 0.948), and D with depth has the smallest ratio among the four variants.For UPBs, depth lowers D’s ratio from 0.615 to 0.585 but raises C’s from 0.622 to 0.678.Source: §F.7 · p. 26, Table 2 · p. 26
  • For D, depth raises event-rate variance ratios from 0.671 to 1.200 and restricted-mean ratios from 0.457 to 0.819; normalized-MSE ranking selects D without depth over C.D’s mean rank is 1.45 versus C’s 1.90; C nevertheless has the smaller median event-variance ratio, 0.632 versus 0.671.Source: §F.7 · p. 26

G All LPB Benchmark Comparisons

The LPB comparisons show toxicity at a 20-turn budget and red-team, hallucination, and AutoIF settings at 10 turns. Each figure reports 90% coverage, twenty runs per target, and HARP-D with depth selected for LPB construction.

G All LPB Benchmark Comparisons

  • Toxicity LPBs are shown at 90% coverage and a 20-turn budget, with twenty runs per target and HARP-D with depth selected for the task.Dashed lines mark coverage and budget; methods use matched splits.Source: Figure 4 · p. 27
  • For red-team LPBs, the Qwen-judge and Llama Guard figures each report 90% coverage with a 10-turn-per-sample budget, across twenty runs per target, using HARP-D (+depth).Source: Figure 5 · p. 28, Figure 6 · p. 29
  • Hallucination and AutoIF LPBs are each reported at 90% coverage with a 10-turn budget and twenty runs per target.The figures select HARP-D with depth for LPB construction.Source: Figure 7 · p. 30, Figure 8 · p. 31

H All Population-Metric Benchmark Comparisons

The population-metric figures report toxicity, red-team, hallucination, and AutoIF settings at a 20-turn budget, with twenty runs per target. They use HARP-D without depth for metric estimation.

H All Population-Metric Benchmark Comparisons

  • Toxicity population metrics use a 20-turn budget and twenty runs per target, with harmful or ungrounded responses as the event and E[min(T, 200)] as the restricted mean.Red cost lines mark the cap; HARP-D without depth is selected for metric estimation.Source: Figure 9 · p. 33
  • Red-team population metrics are reported for both Qwen judge and Llama Guard configurations at a 20-turn budget, with twenty runs per target.HARP-D without depth is selected for metric estimation; red cost lines mark the cap.Source: Figure 10 · p. 34, Figure 11 · p. 35
  • Hallucination and AutoIF population metrics are shown at a 20-turn budget with twenty runs per target; the event is harmful or ungrounded in safety settings and successful completion for AutoIF.The restricted mean is E[min(T, 200)], and red cost lines mark the cap.Source: Figure 12 · p. 36, Figure 13 · p. 37

Related papers

Loading 2610.07362v1…