Calibrate-Then-Act: Cost-Aware Exploration in LLM Agents

Introduction

• Exploration can improve decisions when information is incomplete, but each additional step raises API costs, interaction latency, and user burden.Source: §1 · p. 1
• Agent policies are often static, even though efficiency depends on confidence in understanding the setup and balancing exploration against action costs.Source: §1 · p. 2
• CTA separates uncertainty calibration from action selection, using explicit priors to help LLMs reason about a sequential decision problem and choose actions.The priors may be based on estimated model confidence or a trained predictor of environment state.Source: §1 · p. 2
• CTA-PROMPTED enables dynamic decision-making, and CTA training with RL further improves performance and outperforms baseline RL training.Source: §1 · p. 2
• The paper studies retrieval-optional knowledge-based QA using model confidence and coding tasks using environmental-structure priors, and shows agents prompted or trained with RL do not act optimally in these settings.On a synthetic Pandora’s Box problem, even a small thinking model (Qwen3-8B) can follow the optimal policy, suggesting the failures are not due to inability to reason correctly.Source: §1 · p. 2
• The work frames environment exploration as sequential decision-making across three settings and proposes CTA to improve cost-performance tradeoffs over baselines.Source: §1 · p. 2

2 Background: Agentic Exploration with Costs

• The task is modeled as a partially observable Markov Decision Process with a parameterized discount function that integrates exploration costs.The environment is specified by states, actions, observations, transitions, rewards, and the cost-integrating discount function.Source: §2 · p. 2
• String-valued actions and observations reveal information about latent problem-critical features, allowing the agent to update uncertainty before choosing exploration or commitment.The idealized posterior is b_t(Z) = p(Z | x, o_0:t); commitment terminates the episode with a final result.Source: §2 · p. 2
• Exploration actions incur setting-dependent costs, and the agent seeks to maximize expected discounted reward by adapting its exploration and commitment choices to uncertainty and cost constraints.The discount factor reduces the value of successful completion based on exploration actions taken before commitment.Source: §2 · p. 3

3.1 Pandora’s Box: A Minimal Setting for Cost-Aware Decisions

• Pandora’s Box has K boxes, one hiding a prize; verification discounts reward by γ, while commitment pays γ^t only for the correct box.The prize box is drawn from a prior unknown to the agent.Source: §3.1 · p. 3
• The optimal Pandora’s Box policy commits when a box’s posterior probability exceeds γ; otherwise, it verifies the highest-probability remaining box.The policy depends on knowing the prior probabilities.Source: §3.1 · p. 3

3.2 Task QA: Knowledge QA with Optional Retrieval

• In QA [15], agents choose direct answering or one retrieval round, with retrieval favored when post-retrieval accuracy times γ is at least direct-answer accuracy.The task models direct and post-retrieval answer correctness as LLM point estimates.Source: §3.2 · p. 4

3.3 Task FILEREADING: Coding with Selective Testing

• FileReading requires parsing CSVs with hidden delimiter, quote, and skipped-header attributes; without inferring them correctly, the task is unsolvable, and priors may come from conventions, experience, or a predictor.The task asks the agent to compute an answer from a file whose true schema is not specified in the input.Source: §3.3 · p. 4
• Despite the setting’s simplicity, agents fail to learn optimal FileReading behavior through RL.The format priors are not known a priori and must be learned from training on the task.Source: §3.3 · p. 4
• FileReading agents can probe attributes with UNIT_TEST, execute CODE for feedback, interleave or repeat these actions, and then commit with ANSWER.UNIT_TEST reveals a chosen attribute’s true value; code execution returns stdout and stderr.Source: §3.3 · p. 4

4 Method: Calibrating Agent Environment Exploration

• Agents should weigh exploration cost against the value of additional information, using prior beliefs about the world state and current posterior beliefs to decide when to continue or commit.The authors note that standard prompted or RL-trained agents may struggle to learn this reasoning unaided.Source: §4 · pp. 4–5
• CTA conditions the agent on an estimated prior; CTA-Prompted adds it to the baseline prompt, while CTA-RL also fine-tunes with GRPO [47].Both versions rely on a thinking LLM to use the prior; the paper reports that such models can solve Pandora’s Box with appropriate priors and perform better on its target tasks.Source: §4 · p. 5, Figure 2 · p. 5

4.1 Estimating Priors from Model Confidence (QA)

• 0.618 to 0.029: PopQA expected calibration error (ECE) after isotonic-regression calibration of verbalized confidence estimates [40], with PopQA identified as [38].The method prompts for discrete verbalized confidence and fits the isotonic regression model on validation data; the paper argues systematic recalibration is difficult to learn through end-to-end RL.Source: §4.1 · pp. 5–6

4.2 Estimating Priors from Training Data (FILEREADING)

• For FILEREADING, MBERT predicts filename-conditioned distributions for delimiter, quote character, and skiprows, reaching 67% average validation accuracy across the three attributes [51].The 4.4M-parameter BERT-tiny predictor is trained for one epoch; the format values are sampled from a soft filename-dependent prior, so the task is stochastic rather than deterministically predictable. Its marginal probabilities are supplied to the agent during RL training or testing.Source: §4.2 · p. 6

Datasets

• PopQA evaluation uses 1,000 questions, a Contriever retriever, and sampled retrieval discount factors γ ∼ U[0.1, 0.65].PopQA is a long-tail factual-knowledge QA benchmark that benefits from retrieval.Source: §5 · p. 6
• FILEREADING contains 2,000 tasks split into 1,400 training, 300 validation, and 300 test examples, with hidden file formats inferred from filename cues.Each task samples a unit-test discount du from [0.5, 1] and is duplicated across code discount settings dc = dρ, where ρ ∈ {0.5, 1.0, 2.0, 4.0}.Source: §5 · p. 6

Metrics

• Metrics cover QA retrieval rate, FILEREADING unit tests U and code attempts C, task accuracy, and reward discounted by exploration costs.Task accuracy measures whether the final output matches the ground-truth answer.Source: §5 · p. 6

Models and Baselines

• Qwen3-8B [43] is the base model for both tasks, compared against CTA-PROMPTED and CTA-RL using PROMPTED, PROMPTED-NONTHINK, and RL baselines.PROMPTED uses the task description and query; PROMPTED-NONTHINK disables thinking mode, while RL fine-tunes with GRPO [47] and a discounted reward objective.Source: §5 · p. 6
• FILEREADING duplicates each RL training instance across ρ ∈ {0.5, 1.0, 2.0, 4.0}, producing a 4× larger RL training set than MBERT’s.This exposes both RL settings to diverse relative cost trade-offs.Source: §5 · p. 7

6.1 LLMs can solve Pandora’s Box problems

• With explicit priors and thinking enabled, CTA-PROMPTED attains 94.0% optimal policy match and significantly higher reward on Pandora’s Box than settings without priors or thinking.The match rate measures whether the interaction trace aligns with the oracle strategy.Source: §6.1 · p. 7, Table 2 · p. 7

6.2 Calibrate-Then-Act enables models to make calibrated decisions

• Without explicit priors, LLMs do not naturally form calibrated decision rules from task descriptions alone, and PROMPTED and RL use static test-first policies on FILEREADING.Both PROMPTED and RL produce 0% code-first traces; RL without priors defaults to a suboptimal exploration policy.Source: §6.2 · pp. 7–8
• On QA, PROMPTED-NONTHINK retrieves almost always, while PROMPTED adapts only weakly because its qualitative reasoning rarely links confidence and costs consistently to retrieval decisions.PROMPTED often falls back on answering when a plausible candidate comes to mind and retrieving otherwise, rather than systematically adapting to discount factors and confidence.Source: §6.2 · p. 8
• As ρ rises, code attempts become relatively costlier; PROMPTED and RL show 0% code-first traces, whereas CTA-PROMPTED adapts to costs and CTA-RL retains pronounced adaptivity.The FILEREADING action-distribution figure reports action patterns across relative unit-test and code-execution cost ratios.Source: Figure 4 · p. 7, §6.2 · pp. 8–9
• 0.268 discounted reward for CTA-RL versus 0.259 for RL (+3.5%); CTA-PROMPTED also achieves the highest QA reward and adapts retrieval to costs.On QA, CTA-PROMPTED retrieves more at high discount factors and less at low ones, with the highest oracle match rate across cost constraints.Source: §6.2 · p. 8, Table 4 · p. 8, Table 3 · p. 8
• CTA-RL stays at the Pareto frontier across ρ values and consistently outperforms the RL baseline across cost regimes, even with imperfect prior estimates.The paper attributes this advantage to conditioning training on explicit estimated priors, which reinforces adaptive decision reasoning.Source: §6.2 · p. 9

Decision making under incomplete information

• LLMs address incomplete information by asking clarifying questions, querying environments, or collaborating, while this work uses explicit priors to induce abstract reasoning about optimal solutions.Prior approaches have typically focused on training or prompting strategies.Source: §7 · p. 9

Agents in cost-aware deployment

• Interactive agent tools incur latency, resource, and overhead costs, motivating work on tool planning, reducing unnecessary use, and steerable clarification policies.The cited approaches include abstention, selective search, efficiency-oriented action policies, and adapting clarification to cost coefficients.Source: §7 · p. 9
• The joint treatment of uncertainty priors and cost constraints remains underexplored, and this work proposes a unified framework in which calibrated priors induce appropriate agent decisions.The paper argues that these factors together determine Pareto-optimal decisions.Source: §7 · p. 9

• The method presents LLMs with priors over unobserved environment features to support balancing uncertainty-cost tradeoffs during interaction.Source: §8 · p. 9
• With these priors, LLMs can reason about Pareto-optimal behavior and navigate action costs effectively.Source: §8 · p. 9
• The conclusion suggests that meta-level information, such as priors about capabilities, may shape agent policies.Source: §8 · p. 9

A Limitations

• Controlled QA and FILEREADING isolate cost-aware exploration but omit richer action spaces, longer horizons, and noisier observations found in open-ended deployments.Extending CTA to more complex environments remains future work.Source: A Limitations · p. 16
• CTA is robust to moderate prior-estimation error, but performance can degrade when priors are highly miscalibrated or confidently wrong.The paper demonstrates priors from model confidence and historical task data, while reliable estimators for broader domains remain future work.Source: A Limitations · p. 16
• CTA does not guarantee optimal behavior because models must interpret priors correctly, and complex scenarios may demand stronger reasoning about updates, value of information, and latent-variable dependencies.Source: A Limitations · p. 16

B Impact Statement

• The paper presents CTA as a method for improving LLM agents’ cost-benefit tradeoffs, but it is not yet integrated into production systems.The authors envision CTA or a derived approach potentially reducing costs and increasing efficiency.Source: B Impact Statement · p. 16
• The authors foresee no specific drawbacks of CTA relative to other advances in LLMs, agents, and machine learning.Source: B Impact Statement · p. 16
• Potential broad drawbacks are those inherited from capability advances in LLMs and agents, including further propagation of AI technology in society.Source: B Impact Statement · p. 16

C Sensitivity to Prior Quality

• The study compares the learned BERT prior with progressively worse alternatives: noisy swaps 40% of predictions, uniform is uninformative, and adversarial inflates incorrect options to 95% confidence.Source: C Sensitivity to Prior Quality · p. 16
• As prior quality falls, reward and task accuracy degrade smoothly rather than sharply; imperfect priors remain useful despite the BERT prior’s 67% accuracy.Source: C Sensitivity to Prior Quality · p. 16

D Significance Testing for Pareto-Optimality in FILEREADING

• Across cost regimes, CTA-RL is never statistically worse than a baseline and remains on or near the Pareto frontier.Source: Table 6 · p. 17, D Significance Testing for… · p. 17

C Sensitivity to Prior Quality

• Being confidently wrong is substantially more harmful than being uncertain, with the adversarial prior causing the largest performance drop.Source: C Sensitivity to Prior Quality · p. 17

D Significance Testing for Pareto-Optimality in FILEREADING

• The significance analysis pairs test tasks across methods by task ID and bootstraps per-task reward differences using 10,000 resamples across ρ ∈ {0.5, 1.0, 2.0, 4.0}.Table 6 specifies 300 paired tasks per ρ.Source: D Significance Testing for… · p. 17, Table 6 · p. 17
• CTA-RL significantly outperforms the no-prior test-first baseline at ρ = 0.5, 1.0, and 2.0, and the prior-aware code-first baseline at ρ = 4.0.It is statistically indistinguishable from test-first at ρ = 4.0 and from code-first at lower ρ, where code-first already uses prior information.Source: D Significance Testing for… · p. 17
• Against the no-prior RL agent, CTA-RL gains significantly at ρ = 0.5 and 1.0 and is statistically indistinguishable at higher ρ.Source: D Significance Testing for… · p. 17

E Qualitative Trace Analysis of Pandora’s Box Problem

• With thinking disabled, CTA-PROMPTED-NONTHINK tends to verify every option regardless of the prior, causing unnecessary exploration.In the illustrated instance, it explores all bags before committing instead of prioritizing the highest-probability option.Source: E Qualitative Trace Analysis of… · p. 17, Figure 6 · p. 18
• Without access to prior probabilities, PROMPTED effectively assumes a uniform prior and follows a suboptimal verification strategy.The trace analysis attributes this behavior to a lack of calibrated uncertainty information.Source: E Qualitative Trace Analysis of… · p. 17
• With prior probabilities and thinking enabled, CTA-PROMPTED compares immediate commitment with further verification’s discounted value, producing behavior aligned with the oracle policy.The analysis attributes the improved reasoning to explicit consideration of expected reward against exploration cost.Source: E Qualitative Trace Analysis of… · p. 17

F Experiment Details for QA

• For QA, the experiments use POPQA and a retriever built on Contriever [26] [3].Source: F Experiment Details for QA · p. 17
• The retriever quality pret estimates answerability given the retrieved document using a validation set.The estimate is provided to the agent as part of input x at inference time.Source: F Experiment Details for QA · pp. 17–18
• The pret estimate depends on the retriever and agent, but not on individual questions.Source: F Experiment Details for QA · p. 18

G Dataset Construction Details for Task: Coding with Selective Testing

• Filenames combine indicative tokens such as _eu, _tab, _sas, and _cn with irrelevant strings to signal priors over possible CSV parsing configurations.For example, a _tsv token raises the probability of a tab delimiter relative to the default comma delimiter.Source: G Dataset Construction Details for… · p. 18
• The oracle maps filenames to priors over delimiter, quote character, and skipped header rows, with each factor parameterized by a log-linear model over filename features.The four binary features are has_eu, has_tsv, has_sas, and has_cn, yielding 16 feature configurations and corresponding priors.Source: G Dataset Construction Details for… · p. 21
• Each file is generated from a formatting configuration sampled from its filename-conditioned prior, and incorrect delimiter, quote, or header settings prevent access to the correct answer.The true configuration is sampled before generating the CSV content and query.Source: G Dataset Construction Details for… · pp. 18, 21
• The dataset contains 2,000 filename, CSV, and query instances, split into 1,400 training, 300 validation, and 300 test examples.Source: G Dataset Construction Details for… · pp. 18, 21

H Oracle Strategy for Pandora’s Box Problem

• At each Pandora’s Box decision, an optimal policy need only consider the remaining box with the highest posterior probability of containing the prize.Committing to a lower-posterior box is suboptimal, and verifying a higher-posterior box weakly dominates verifying a lower-posterior one.Source: H Oracle Strategy for Pandora’s Box… · p. 21
• The oracle compares immediate commitment with verification of the most likely box, which discounts reward by γ and recurses on the remaining boxes if verification fails.The recursion has the single-box base case V({i}) = 1.Source: H Oracle Strategy for Pandora’s Box… · pp. 21–22

I GRPO Training Details

• GRPO training uses veRL on Qwen3-8B with group size 8, KL coefficient 0.01, learning rate 1 × 10−6, and a single node of 8 A100 GPUs.Rollouts use temperature 1.0, global batch size 16, update micro-batch size 2, and experience micro-batch size 4.Source: I GRPO Training Details · p. 22

J Prompt Templates

• Prompt templates are provided for Pandora’s Box, QA, and FILEREADING.The FILEREADING templates include system prompts and instruction variants with and without estimated CSV-format likelihoods.Source: §J.1 · p. 22, §J.2 · p. 22, §J.3 · p. 22

K Case Study: Cost-Aware Decision Traces in FILEREADING with CTA-RL and RL

• At ρ = 4.0, RL defaults to verification-first without explicit cost reasoning, while CTA-RL reasons jointly about CSV-format uncertainty and verification costs before committing to code.The traces contrast decisions about unit tests and code execution under high relative code cost.Source: K Case Study: Cost-Aware Decision… · pp. 22–23, Figure 15 · p. 27, Figure 16 · p. 28

NeurIPS Paper Checklist: 1. Claims; 2. Limitations; 3. Theory assumptions and proofs

• The authors say the claims reflect the paper’s scope, discuss limitations in Appendix A, and provide assumptions, an optimal policy derivation, algorithm, and proof for discounted Pandora’s Box.The problem assumptions are stated in Section 3.1 and the full algorithm and proof are in Appendix H.Source: §1 · p. 29, §2 · p. 29, §3 · p. 30

NeurIPS Paper Checklist: 4. Experimental result reproducibility; 6. Experimental setting/details; 7. Experiment statistical significance; 8. Experiments compute resources

• The paper says task, dataset, prior-estimation, baseline, metric, prompt, training/test, significance-test, and compute details are documented to support reproduction.These details are located across the main paper and appendices, including Sections 5, D, G, I, and J.Source: §4 · p. 30, §6 · p. 31, §7 · p. 31

NeurIPS Paper Checklist: 5. Open access to data and code; 12. Licenses for existing assets; 13. New assets

• The authors say data are supplied in supplementary materials, relevant papers are cited, and FILEREADING, the framework, and evaluation protocol are documented, with code and data to be released.The passage on existing assets reports citations but does not specify license terms.Source: §5 · p. 31, §12 · p. 33, §13 · p. 34

NeurIPS Paper Checklist: 9. Code of ethics; 10. Broader impacts; 11. Safeguards

• The authors report ethics-code compliance, say societal impacts are discussed, and state that small LLMs are used without releasing a high-risk model or dataset.They say they do not perceive the method itself as having high misuse potential.Source: §10 · p. 32, §11 · p. 33

NeurIPS Paper Checklist: 14. Crowdsourcing and research with human subjects; 16. Declaration of LLM usage

• The work does not involve human subjects, and the authors describe LLMs as central to the methodology and evaluation, specifying models, prompting variants, evaluation settings, and RL-trained variants.Source: §14 · p. 34, §16 · p. 35