Online LLM Inference Routing for Multi-Agent Systems under Long-Term Budget and Layered Privacy Constraints

The Cloud-Edge-End (CEE) collaborative architecture has become a key paradigm for deploying highly intelligent multi-agent systems with low latency and high energy efficiency. Existing studies on efficient task offloading in CEE, however, either overlook long-term financial budget constraints from commercial API token usage and edge computing leasing, or inadequately handle layered information-sharing and privacy restrictions in decentralized autonomous agents. This paper investigates online inference routing to minimize the computational and communication overhead of large language model (LLM) workloads under long-term budget constraints, agent intent-sharing limitations, and un-known future prompt lengths. We propose a budget-aware online optimization framework that uses Lyapunov optimization to decouple long-term financial constraints, and show that the decoupled problem forms a generalized ordinal potential game. To address heterogeneous information-sharing restrictions, we design an adaptive best response algorithm for cooperative environments with shared decision information, and a multi-agent distributed routing algorithm for limited-information environments, enabling efficient offloading without inter-agent intent sharing. Theoretical analysis provides conditional performance and queue-length bounds and establishes finite convergence of the per-slot solvers. Simulations on distributed inference testbeds show that our scheme reduces the inference overhead of heterogeneous agentic tasks while achieving a favorable trade-off between performance and actual token expenditure.