acceptodds
Under review as a conference paper at ICLR 2027

Truthful Online Procurement from Multi-Tier LLM Providers Under Budget Constraints

Abstract

Procuring services from external large language model (LLM) providers allows AI platforms to exploit quality–cost trade-offs across service tiers. Doing so under a hard budget requires both eliciting providers' private tier-specific costs and learning their unknown request-dependent qualities. We formulate this joint problem as repeated procurement with vector-valued private costs, contextual quality feedback, and per-round payment budgets. For known qualities, we propose TRIP, a deterministic mechanism that combines bid-independent posted menus with leave-one-out payment caps to ensure truthfulness, individual rationality, and budget feasibility. We establish an approximation certificate under explicit conditions on realized budget utilization and winner payment rates. For unknown qualities, we develop TRIP-MC, which learns from contextual semi-bandit feedback and supplies TRIP with optimistic quality estimates that respect tier ordering. The online mechanism preserves history-conditioned, current-round truthfulness and per-round budget feasibility. Under a linear contextual model, we prove sublinear contextual -regret conditional on a per-round -approximate oracle, and using TRIP as this oracle requires its certificate conditions to hold in the compared rounds. Experiments in procurement markets constructed from MMLU rollout traces show gains in procurement value and cumulative reward over truthful baselines.

Primary area:
optimization
Keywords:
Mechanism Design, Online Learning, Language Model

Reviews

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

This paper considers an AI platform that repeatedly buys LLM services from several providers under a hard budget for each request. Each provider offers multiple service tiers. Providers privately know their cost for each tier and may misreport it, and the platform does not know how well each tier performs on a given request. For known qualities, the authors propose TRIP. TRIP offers each provider a price menu over its tiers and caps every payment so that the total stays within the budget. The paper shows that TRIP is truthful, individually rational, and budget feasible, and that it approximates the optimum when the realized payment uses most of the budget. For unknown qualities, TRIP-MC plugs optimistic LinUCB estimates into TRIP. It achieves sublinear regret under the assumption that TRIP is an approximation oracle in every round. Experiments on markets built from MMLU rollouts show gains over several truthful baselines. The problem is relevant, but the motivation for strategic cost reporting is weak, the theoretical guarantees can fail in simple markets, and the paper is difficult to read.

Critical strengths
  1. TRIP is truthful, individually rational, and budget feasible in every round for every bid profile, and the proofs are correct. The learning component only changes the quality estimates, so these properties carry over to the online setting.

  2. The paper is open about what it does not prove. Theorem 3 identifies a real limitation of deterministic mechanisms when providers have a different cost for each tier.

Critical weaknesses
  1. The paper is hard to understand. Many technical terms and symbols appear without being defined, which makes the mechanism and the results difficult to follow.

  2. The paper assumes that providers privately know their tier costs and report them strategically. However, LLM providers today publish fixed per-token prices for each model and service level, and a platform simply pays these prices. It is unclear in which practical market a provider would bid a cost for every request. The paper should describe such a scenario, for example negotiated enterprise contracts or decentralized compute markets, and explain why public posted prices are not sufficient there. In addition, the objective adds up the qualities of all answers purchased for the same request, although in question answering a second correct answer adds little value. The costs in the experiments are synthetic functions of prompt length rather than private information, which further weakens the link to the motivation.

  3. The offline mechanism combines known components. Truthfulness comes from offering each provider a price menu that does not depend on its own bid. The prices come from the threshold payments of proportional-share budget-feasible mechanisms (Singer, 2010). Budget feasibility comes from capping each payment at a fixed share of the budget. The online part inserts optimistic estimates into this mechanism and follows the standard analysis of contextual combinatorial bandits with an approximation oracle (Chen et al., 2013; Qin et al., 2014). The paper does not discuss closely related work on posted-price procurement under budgets (Badanidiyuru et al., 2012; Anari et al., 2014). The paper should explain what is technically new in the multi-tier setting beyond combining these components.

  4. The approximation guarantee for TRIP (Theorem 2) holds only if the mechanism ends up spending most of the budget. This is a property of the outcome rather than the input, and it fails exactly when TRIP performs poorly. Because each payment is capped at a fixed share of the budget, TRIP can buy nothing even in very simple markets. For example, take seven identical providers, each costing 15% of the budget. The optimum buys six of them, and so does the classical mechanism of Singer (2010), but TRIP buys none. The regret bound for TRIP-MC (Theorem 4) assumes that TRIP achieves a constant fraction of the optimum in every round, so the same example shows that this bound does not apply to the proposed method. A guarantee stated in terms of the market, rather than the realized payment, is needed.

  5. The experiments do not show where the gains come from. Several baselines behave unexpectedly. Offline RSBF and SSPM obtain less value as more providers are added (Figure 2), and online FM-BwK and O-RP barely respond to the budget (Figure 4). STBF picks a random tier for each provider, which makes it a weak single-tier baseline. The text mentions a "repaired" implementation and a "tuned" configuration that removed a "previously observed long-horizon reversal". It does not say whether the baselines were tuned in the same way. TRIP also performs worst at tight budgets, which is the regime where budget feasibility matters most. The paper should report which tiers are actually purchased and how far TRIP-MC falls short of TRIP with known qualities.

Questions for authors
  1. The candidate pool contains one provider beyond the budget-feasible prefix, and the payment caps of all other candidates are lowered to leave room for it. Under variants A and C, which the paper uses, this extra provider is never offered a price above its cost, so it never profits from trading. The budget reserved for it is therefore wasted. Is this provider necessary, and how much value would the mechanism gain without it?

  2. When the budget is ample, the main variant C caps several tiers at the same price, and the provider then chooses its cheapest tier. Please report the distribution of purchased tiers for TRIP, TRIP-MC, and the optimum. This would show whether the gain over STBF comes from trading off quality against cost across tiers, or simply from letting each provider pick its cheapest tier.

  3. The truthfulness definition in Eq. (4) already allows randomized mechanisms. On the instances used in Theorem 3, a simple lottery between two posted offers is truthful and budget feasible. It obtains half of the optimum regardless of the quality gap between tiers. Why restrict to deterministic mechanisms? Could randomization remove the dependence of Theorem 2 on the quality ratio?

Reviewer_Mk4aOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper considers a platform that to achieve a task can employ different LLM providers, each with several tiers reflecting different qualities. The platform has a fixed budget per task that it can allocate across provider-tier pairs with the aim to maximise its reward. However, the providers' cost is unknown and they may have an incentive to overreport their costs. Furthermore, given a task the quality of a tier is a priori unknown. The paper formulates this setting as a repeated procurement problem. For a fixed round with known tier qualities they design a mechanism that is truthful, individually rational, budget feasible and that optimal up to a problem-dependent constant. For the repeated procurement setting with unknown task-specific qualities, they leverage the above mechanism within each round and develop a no-regret algorithm from contextual linear stochastic bandit feedback. The paper then validates its theoretical results in styleiszed LLM procurement markets.

Critical strengths

For the offline procurement problem, the paper introduces a mechanism, termed "TRIP", that is truthful, individually rational, and budget-feasible. It furthermore, ensures that the platform selects a feasible set of provider-tier pairs that generate expected value within a problem-dependent fraction of the expected optimal value. The mechanism seems novel and applicable beyond the procurement problem of multi-tier LLM providers.

Critical weaknesses
  • To move from offline to online procurement, the authors assume the unknown task-specific rewards for a provider-tier pair follow a linear stochastic bandit model. The algorithm they then provide resembles classical linear stochastic bandit models, where within each round they apply TRIP based on optimistic estimates rather than the true unknown task-specific rewards to select the next feasible set of provider-tier pairs. To prove their regret bounds they rely on classical confidence for linear stochastic bandits. In particular, they mention LinUCB without providing a reference. The novelty of this approach seems limited. It seems rather as if the authors are wrapping their novel mechanism TRIP in existing linear stochastic bandit algorithms.
  • Theorem 2, proving that under TRIP the platform selects a feasible set of provider-tier pairs that generate expected value within a problem-dependent fraction of the expected optimal value, relies on two assumptions, namely that P≥(1−η)BP\geq (1-\eta)B and λˉi≤B/Vmin\bar{\lambda}_i\leq B/V_{min}. These two assumptions are not discussed in the paper, so it is unclear under which conditions these assumptions hold and whether they are realistic in real-world applications.
  • In the AI Use Statement the authors disclose the usage of AI, however, it seems that in some places the manuscript was not manually checked. For example, lines 341-345 seem to be related to the experiments but appear out of context in the theoretical section on the contextual linear model. There are also some notational typos and acronyms that were not introduced, for example, lines 420-422 introduces baseline comparison methods without providing any references or how these methods work. The acronym MMLU is never introduced.
Questions for authors

To get a better understanding of the novelty of the work, the addressing the questions below would help:

  • Can you explain what the advantages of TRIP are compared to the well-known VCG mechanism? In particular, can you contrast how your differs from this work "Eliciting Truthful Feedback for Preference-Based Learning via the VCG Mechanism" by Landolt et al.
  • The authors reference Singer (2010) and state that budget-feasible procurement handles strategic costs and hard payment constraints, but typically assumes known values, static allocations, and scalar seller types. Can you contrast TRIP against the work of Singer (2010) beyond having vector-valued costs compared to scaler-costs to give a better understanding of the novelty. What are the challenges of having vector-valued costs compared to scalar costs?
  • Can you elaborate on how your work differs from Biswas et al. (2015); Bhat et al. (2019); Liu et al. (2025) cited in the paper. What is the challenge added by considering heterogeneous tiers? Where is this captured in the theoretical results?

Parts of the paper that were unclear to me:

  • You consider a setting with request-dependent qualities but in (1) you assume the ordering of rewards across all tires is the same for all requests. Doesn't this assumption reduce the problem to considering a single request rather than heterogeneous requests?
  • Lines 186-187: Can you elaborate why the per-round offline procurement problem is NP-hard. How does this effect the results of Theorem 2?
  • The section "The main mechanism (TRIP)": would benefit from additional explanations and intuition. It is hard to follow how and why the three posted-menu variants were constructed in this way and why there are three variants. In Equation (9), I thought from the problem formulation, the platform would select a tier, but by Equation (9) it seems provider i chooses the tier. Can you further explain this?
  • Can you give intuition and connect to the theory in what sense TRIP is bid-independent and how you achieve this?
Reviewer_okjGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper models a platform that repeatedly buys services from nn LLM providers, each offering several tiers at privately known tier-specific costs, under a per-round budget and unknown request-dependent tier quality. For known qualities it proposes TRIP, a deterministic mechanism combining bid-independent posted menus with leave-one-out caps, and proves truthfulness, individual rationality, and budget feasibility, together with a conditional approximation certificate. For unknown qualities it proposes TRIP-MC, which supplies monotone optimistic quality estimates to TRIP from contextual semi-bandit feedback and has a conditional sublinear contextual γ\gamma-regret bound. Experiments on procurement markets built from MMLU rollouts report gains in procurement value and cumulative reward over truthful baselines.

Critical strengths
  1. The problem sits at a sensible intersection of budget-feasible procurement, strategic bandits, and cost-aware routing, and the budget enforcement is simple and airtight: the leave-one-out caps qi=B/(m−i+2)q_i = B/(m_{-i}+2) sum to strictly below BB over the candidate pool, so feasibility needs no adaptive remaining-budget tracking.

  2. The truthfulness argument in Theorem 1 is clean. Because the posted menu, the cap, and the admissible set depend only on the leave-one-out market, a provider faces a fixed menu regardless of its report, and the argument for providers outside the truthful candidate pool is also correct.

  3. The monotone backward sweep is a neat way to inject the tier-order prior into an otherwise standard LinUCB layer, and the lower bound in Theorem 3 identifies a genuine DSIC limitation rather than an artifact of the analysis.

Critical weaknesses
  1. The paper's only approximation guarantee is conditional. Theorem 2 requires the realized payment to satisfy P≥(1−η)BP \ge (1-\eta)B and every winner rate to satisfy λˉi≤B/Vmin⁡\bar\lambda_i \le B/V_{\min}, but neither condition follows from the mechanism, and the caps make them hard to satisfy since each winner is capped at B/(m−i+2)B/(m_{-i}+2) and underpaid providers are skipped. Both quantities are measurable, yet neither is reported. The bound is also 1−η1+2/α\frac{1-\eta}{1+2/\alpha} with α=μmin⁡/μmax⁡\alpha = \mu_{\min}/\mu_{\max} over all arms, which in the paper's own 21-arm market is close to vacuous. The authors should either give an explicit market where these conditions hold and report the realized utilization and winner rates, or scope the guarantee to what the theory actually delivers.

  2. The multi-parameter claim is nominal. T-BF reduces each cost vector to one scalar ratio, sorts by it, and runs a scalar rule, so the vector type only re-enters through menu self-selection, which is the single-parameter argument. The experiments also contain no private information: cost is a fixed public formula, so no agent can misreport and truthfulness is proved but never tested. The authors may need to justify the model against the public posted prices of real LLM APIs, or add a misreporting or best-response experiment.

  3. The comparison is weak and partly re-tuned. STBF randomly keeps one tier per provider, so the strongest baseline is handicapped, and the other baselines are untuned heuristics. The online results follow a "repaired" protocol and a "tuned" confidence setting introduced after a long-horizon reversal, while only TRIP-MC is swept. Finally, variant B is also truthful and budget feasible and scores higher than the chosen variant C (88.57 vs 87.77), so selecting C for its certificate needs justification. The authors should keep a best-ratio single-tier control, give the baselines the same tuning budget, and explain the choice of variant C over B.

Questions for authors

Please explain the raised weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.