Online Linear Contract Learning for Adaptive LLM Selection
Large language model (LLM) routing platforms provide users with access to multiple LLMs that differ in cost and quality. We study the problem of learning contracts in such settings. A principal repeatedly offers a scalar linear contract to an agent, who selects one of several candidate LLMs to answer the query. The qualities of the LLMs are initially unknown, while their costs are known. Under mild assumptions, an optimal contract exists in the classical setting when the LLM qualities are known.
Since the qualities are unknown in our setting and are observed by the user only through the realized responses, we formulate this interaction as an online principal--agent bandit problem. We propose the Three-Phase Successive Contract Elimination (TSCE) algorithm, which induces LLMs through contracts.
We provide finite-sample query-complexity guarantees for TSCE to identify an ε-optimal contract. We further demonstrate empirically that the proposed method reliably identifies near-optimal contracts across a wide range of problem instances.