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

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 $\gamma$-regret conditional on a per-round $\gamma$-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.