PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Service Depth and Priority Design in Queueing Systems

Adam N. Elmachtoub, Yash Kanoria, Jonathan Y. Tan

arXiv:2610.33334v1cs.GTecon.THmath.OC

TL;DR

AI-assisted service systems must trade off processing quality against the congestion created by deeper reasoning, while prior fixed-priority approaches do not capture endogenous service depth. The paper analyzes joint depth and priority choices under centralized information and private-information pricing, and calibrates an AI-service case study using coding-agent trials. It finds that centralized and decentralized allocations can diverge with two types, while the continuum-type optimum can be implemented by a price menu.

  • Problem

    When service depth is endogenous, classical priority rules based on fixed primitives may be suboptimal, and deeper processing trades service quality against congestion.

    Source: §1 · p. 2, §4.1 · p. 11

  • Method

    The paper characterizes joint depth and priority policies under centralized and private-information pricing regimes, with a case study calibrated from published GPT-5.6 Sol trials.

    Source: §7.1 · p. 23, §9 · p. 32

  • Results

    The two-type centralized optimum may prioritize patient customers in a way that private-information pricing cannot implement, whereas the continuum-type optimum can be matched by a price menu.

    Source: §9 · p. 32

  • Takeaways & Limitations

    The paper identifies a trade-off between simpler mechanisms and the potentially greater efficiency of more personalized mechanisms.

    Source: §9 · p. 33

    The analysis leaves non-exponential service requirements, multi-server systems, and state-dependent policies for future study.

    Source: §9 · p. 33

Abstract

from arXiv · show

In AI-assisted service systems, the server can choose how much processing effort to spend on each job, which we call the service depth. Deeper reasoning improves output quality but occupies the server longer and increases congestion, and the realized processing time remains random because AI models are probabilistic and tasks vary in complexity. We study the joint design of service depth and priority in a single-server queue whose customers differ in delay sensitivity, with the goal of maximizing social welfare. For each customer type, the decision maker chooses a priority level and a service depth, and service times are exponential with mean equal to the chosen depth. With two customer types and linear service values, we characterize the centralized optimum. Counterintuitively, it prioritizes the patient type and gives it a smaller service depth when patient customers are sufficiently prevalent. When delay sensitivity is private, however, incentive compatibility requires the impatient type to receive a weakly shorter sojourn time, so the optimal price menu never prioritizes the patient type. Consequently, there can be a welfare gap between the centralized decision maker's optimal control policy and the optimal decentralized pricing mechanism. With a continuum of types, the centralized optimum is monotone: more delay-sensitive customers receive weakly smaller depth and higher priority, so the optimum can be implemented by a price menu with no welfare loss. Allowing randomized depths similarly closes the gap in the two-type model. Finally, we calibrate an agentic AI service system using published coding-agent trials from DeepSWE and numerically examine priority inversion, the value of joint design, and the welfare gain from personalization.

1. Introduction

The paper studies how service systems should jointly choose processing effort and priority when effort affects both customer value and congestion. It characterizes centralized and decentralized policies, showing that their compatibility depends on the distribution of customer types.

1. Introduction

  • The paper jointly designs service depth and priority because deeper processing can increase customer value while consuming capacity and delaying other customers.It models preemptive service in a single-server queue, with type-dependent service depth and exponential service times whose mean equals the chosen depth.Source: §1 · pp. 2–3

1.1. Main Contributions

  • With two types and linear service values, the centralized optimum can prioritize the patient type and assign it smaller service depth when patient customers are sufficiently prevalent.The optimal priority order can also exclude the impatient type or prioritize it; the patient-first result also occurs for nonlinear concave value functions.Source: §1.1 · p. 3
  • Under private delay sensitivity, incentive compatibility requires the impatient type to have weakly shorter sojourn time, preventing a menu from implementing a centralized allocation that prioritizes patient customers.The optimal decentralized menu achieves at least 75% of centralized welfare, and the worst-case bound is tight.Source: §1.1 · p. 3
  • With a continuum of types, the centralized optimum gives more delay-sensitive customers weakly smaller depth and higher priority, matching the ordering needed for incentive-compatible implementation.The centralized optimum can therefore be implemented by a pricing menu whenever it is attained.Source: §1.1 · pp. 3–4
  • In the DeepSWE case study, two-type experiments show incentive-compatibility welfare loss up to 53.4%, while finer personalization can outperform the coarse centralized allocation.With many types, priority alone can match joint design at lower load, whereas personalized depth sustains service near capacity.Source: §1.1 · p. 4
  • For two-type and regular continuous-type settings, the analysis also applies to revenue maximization by replacing true delay sensitivities with virtual delay sensitivities.The paper derives this welfare-like revenue objective under incentive compatibility.Source: §1.1 · p. 4

2. Literature Review

The paper connects service-rate control, priority design, pricing, and AI-service queueing. Its distinction from prior work is that service requirements are chosen and affect both customer value and congestion.

Service rate control

  • Classical service-rate control adjusts speed, capacity, or effort to manage congestion, while this model makes service depth affect customer utility and value as well.Related work includes Weber and Stidham Jr (1987), Stidham Jr and Weber (1989), Veatch and Wein (1992), George and Harrison, Anand et al. (2011), and Lin et al. (2023).Source: §2 · pp. 4–5

Priority control and design

  • Priority-control research studies scheduling order and achievable waiting times, while priority pricing lets customers trade payments for queue position.The review discusses the cµ-rule, the Gittins Policy (Scully and Harchol-Balter 2021), and priority auctions and pricing (Kleinrock 1967, Mendelson and Whang 1990).Source: §2 · pp. 5–6
  • Unlike priority-design models with primitive service requirements, this paper makes service depth a decision variable that changes both congestion and the priority order.The review identifies this endogeneity as the key difference from the priority-design literature.Source: §2 · p. 6

Queueing for AI Systems

  • AI queueing research addresses inference scheduling and congestion, while related AI-service pricing work studies routing, pricing, and capacity allocation.Abdolmaleki et al. (2026) study agentic AI services with valuation heterogeneity and service quality tied to realized time; this paper instead models delay-sensitivity heterogeneity and randomized realized times conditional on chosen depth.Source: §2 · pp. 6–7

3. Problem Formulation

The model represents service allocations through type-specific depth and expected sojourn time, then optimizes welfare subject to operational feasibility. Under private information, a contract menu must also induce truthful, voluntary participation.

3.1. Queueing Framework

  • Customers arrive to a single server according to a Poisson process, and positive service depth x yields exponentially distributed service time with mean x; zero depth means no service.Service value depends on assigned depth rather than realized service time.Source: §3.1 · p. 7
  • The value function is nonnegative, increasing, concave, and continuous, with V(0)=0; customer type θ is the cost per unit time spent in the system.Types are drawn from a known distribution, modeled as either two-point or continuous in the paper's two main settings.Source: §3.1 · p. 7
  • The welfare objective is long-run average service value minus customer delay costs, optimized over stable, operationally achievable allocations.Arrival rate, value function, and type distribution are public information.Source: §3.1 · p. 7

3.2. Centralized Benchmark

  • The centralized decision maker observes types and chooses type-dependent service depth plus a scheduling policy, including priority, randomized, or intentionally idle policies.Service depth assignments depend on type, not the current queue state.Source: §3.2 · p. 8
  • For welfare, a scheduling policy matters through the expected sojourn times it induces, so allocations can be represented by depth x(θ) and sojourn time w(θ).The pair must be consistent with a feasible priority rule under the chosen depths.Source: §3.2 · pp. 8–9
  • Feasible centralized allocations must satisfy workload stability and finite-sojourn-time conditions.The model also requires the chosen sojourn-time function to be operationally achievable under some priority rule.Source: §3.2 · pp. 8–9

3.3. Decentralized Mechanism

  • When type is private, the provider offers contracts specifying price, service depth, and expected sojourn time; the menu must satisfy individual rationality and incentive compatibility.Truthful reporting must be consistent with the steady-state queue, and indifferent customers are assumed to report truthfully.Source: §3.3 · p. 9

4. Two-Type Model

In the two-type model, endogenous service depths can make prioritizing patient customers optimal when they are sufficiently prevalent. Under private delay sensitivity, incentive compatibility rules out that priority order, creating a welfare gap that is tightly bounded.

4.1. Centralized Optimum

  • With service depths fixed, the optimal work-conserving priority rule gives precedence to the type with the smaller service-depth-to-delay-sensitivity ratio.Because service depth is chosen endogenously, the planner compares the priority regimes induced by each depth assignment.Source: §4.1 · pp. 10–11
  • With linear service values, the centralized optimum can exclude impatient customers or prioritize either type; sufficiently abundant patient arrivals can make patient-first optimal with smaller depth.Figure 1 illustrates the three policy regimes.Source: §4.1 · pp. 11–12, Figure 1 · p. 12
  • Higher arrival volume magnifies the congestion externality of service depth, so reducing a prevalent type’s depth can raise its cμ-index enough to justify prioritizing it.As the patient-to-impatient arrival-rate ratio rises, prioritizing patient customers becomes more valuable.Source: §4.1 · p. 12
  • For nonlinear value functions, similar centralized policy structure holds under Proposition 2’s stated workload condition.The provided passage identifies the proposition’s scope but does not give its full conditions.Source: §4.1 · p. 13

4.2. Optimal Decentralized Mechanism

  • Incentive compatibility for two types requires the impatient type’s expected sojourn time to be no longer than the patient type’s.For a fixed feasible allocation, such a price menu exists if and only if w1 ≤ w2.Source: §4.2 · p. 13
  • The optimal price menu always prioritizes the impatient type and gives it a lower service depth; patient-first centralized allocations violate incentive compatibility.Among the two stated incentive-compatible alternatives, prioritizing impatient customers always dominates equalizing sojourn times.Source: §4.2 · pp. 14–15
  • A welfare gap arises whenever the centralized optimum prioritizes patient customers, because the menu cannot implement that allocation while satisfying incentive compatibility.The decentralized optimum then matches the best allocation conditional on prioritizing impatient customers.Source: §4.2 · p. 15
  • In the worst case, the decentralized mechanism can lose up to 1/4 of centralized social welfare, and the bound is tight.When impatient customers are extremely rare, the menu approaches serving only patient customers, while the centralized policy still assigns rare impatient customers deep, slow service.Source: §4.2 · pp. 15–16

5. Continuous-Type Model

For a continuum of delay sensitivities, the centralized optimum can be restricted to non-increasing service depths, which aligns priority and sojourn time with incentive compatibility. When the centralized welfare supremum is attained, a pricing menu implements it without a welfare gap.

5.1. Centralized Optimum

  • The continuous-type centralized problem chooses an admissible service-depth assignment and priority rule to maximize welfare; optimal priorities follow the cμ-rule once depths are assigned.The model assumes a continuous type distribution with positive density over its support.Source: §5 · p. 16, §5.1 · p. 17
  • A non-increasing rearrangement of service depths weakly raises welfare, and under such assignments customers with larger delay sensitivity receive higher priority.Thus more delay-sensitive customers receive weakly smaller service depth and higher priority.Source: §5.1 · p. 17
  • With linear service values, the continuous-type optimum is degenerate and its welfare supremum is not attained; if marginal value eventually falls below the minimum delay cost, a continuous non-increasing optimum exists.In the linear case, the optimal assignment sends the most patient type’s depth toward infinity and assigns zero depth to other types.Source: §5.1 · p. 18

5.2. Optimal Decentralized Mechanism

  • For a continuous type, a pricing policy is incentive compatible if and only if expected sojourn time is non-increasing in delay sensitivity.The result also supplies an implementing payment rule when this condition holds.Source: §5.2 · p. 19
  • If the centralized welfare supremum is attained by an admissible assignment, a decentralized pricing menu can attain it as well, so there is no welfare gap.The centralized allocation already gives delay-sensitive customers shorter service and higher priority, aligning the allocation with incentive-compatible sojourn times.Source: §5.2 · p. 19

6. Numerical Examples

The numerical examples measure how the two-type welfare gap varies with value functions and parameters, then illustrate continuous-type depth assignments where closed-form solutions are generally unavailable. The continuous-type examples use a discrete approximation with 200 customer types.

6.1. Welfare Gap in the Two-Type Model

  • The gap is zero when λ2/λ1 ≤ 1.0, but reaches 16.2% for V(x) = 2x at λ2/λ1 = 32.0 as patient-first priority can violate incentive compatibility.For strictly concave value functions, the gap is smaller and need not increase monotonically with λ2/λ1.Source: Table 1 · p. 20, §6.1 · p. 20
  • With arrival rates fixed, similar delay sensitivities make patient-first priority attractive, while a wider sensitivity difference makes impatient-first priority valuable and removes the conflict with incentive compatibility.The gap is examined across delay-sensitivity pairs (θ1, θ2).Source: §6.1 · p. 20, Table 2 · p. 21

6.2. Examples for the Continuous-Type Model

  • Under V(x) = √x, welfare contribution first increases and then decreases with delay sensitivity as service-value loss eventually outweighs the benefit of shorter sojourn time.The welfare contribution is not monotone in θ.Source: §6.2 · pp. 21–22
  • For V(x) = √x, optimal service depth strictly decreases with delay sensitivity, yet every type receives positive depth because V′(x) diverges as x approaches zero.Figure 2 presents depth, sojourn time, welfare contribution and customer surplus, and payment across types.Source: §6.2 · p. 21, Figure 2 · p. 22
  • For V(x) = √x, payment is non-monotone in delay sensitivity because smaller depth lowers payment while shorter sojourn time raises it, with information rent separating payment from welfare contribution.The two quantities share the underlying trade-off but are not identical.Source: §6.2 · p. 22
  • For V(x) = ln(1 + x), types above a delay-sensitivity threshold receive zero depth because V′(0) is finite; welfare contribution and payment are also non-monotone.Figure 3 presents the optimal solution for the logarithmic value function.Source: Figure 3 · p. 22, §6.2 · p. 22

7. Case Study

The case study calibrates the queueing model with published coding-agent trials, then compares depth, priority, and personalization policies. Its experiments show that the value of these choices depends on demand and that fine personalization can achieve an incentive-compatible allocation with higher welfare than the coarse centralized policy.

7.1. Data

  • Calibration uses published GPT-5.6 Sol trials under the mini-swe-agent harness: the same 113 tasks were evaluated four times at each of five reasoning depths (low, medium, high, xhigh, max), totaling 2,260 trials.Source: §7.1 · p. 23

7.2. Empirical Calibration

  • From low to max reasoning effort, success rises from 45.4% to 72.3% as mean service time increases from 0.276 to 2.148.Table 3 reports the empirical calibration by reasoning effort.Source: §7.2 · p. 24, Table 3 · p. 24
  • The case study draws service times uniformly from 452 empirical observations per depth and restricts scheduling to deterministic, type-based FCFS or nonpreemptive priority.Realized service time is assumed unknown until completion, with FCFS within each type.Source: §7.2 · p. 24

7.3. Two-Type Results

  • The centralized policy prioritizes patients in three demand windows, creating gaps from the incentive-compatible menu that reach a 53.4% welfare loss.When demand grows further, it switches to serving the patient minority with larger depths.Source: §7.3 · p. 25, Figure 6 · p. 26
  • The optimal incentive-compatible menu retains impatient-customer priority, with a welfare gap reaching 3.28%; as population composition shifts, the centralized policy can instead prioritize patients.Above a ratio of approximately 1.10, the patient majority receives low effort and priority while the impatient minority receives medium effort; deeper service for the smaller group saves capacity.Source: §7.3 · pp. 25–26, Figure 7 · p. 27

7.4. Continuous-Type Results

  • At low arrival rates the four designs are nearly indistinguishable; for 0.66 ≤ λ ≤ 0.90 priority alone matches joint design, while at extremely high loads depth becomes decisive.At high loads, type-dependent depth can keep the system viable by withholding service from delay-sensitive customers.Source: §7.4 · pp. 26–27, Figure 8 · p. 28
  • At λ=1.5, joint design reaches welfare 0.589, about 7% above depth-only (0.548) and priority-only (0.547), while assigning medium effort to the 60% most patient customers.The most delay-sensitive customers' sojourn time is 0.44 under joint design, versus 0.53 under depth-only design.Source: §7.4 · p. 27, Figure 8 · p. 28
  • At λ=3.8, fine personalization serves every patient and 80% of impatient customers with an incentive-compatible allocation, reaching welfare 1.336, about 9.9% above the coarse centralized optimum.The coarse centralized policy excludes patients and attains welfare 1.215.Source: §7.4 · pp. 27–28, Figure 9 · p. 28

8. Extensions

The extensions study revenue maximization, randomized service depths, and congestion-dependent threshold control. Randomization can eliminate the two-type welfare gap, while threshold control reduces congestion and narrows that gap numerically.

8.1. Revenue Maximization

  • Under monotone virtual delay sensitivities, the continuous-type welfare structure applies after replacing true with virtual sensitivities.The regularity assumption makes the virtual-sensitivity ordering agree with the true-sensitivity ordering.Source: §8.1 · p. 29
  • Revenue maximization is equivalent to the welfare problem with delay sensitivities replaced by virtual delay sensitivities.For continuous types, this structural analysis requires virtual delay sensitivities to be monotone in type.Source: §8.1 · p. 29

8.2. Randomized Service Depth in the Two-Type Model

  • The randomized assignment can be arranged so impatient customers receive priority over patient customers under the cμ-rule.Incentive compatibility requires every option chosen by the impatient type to have a weakly shorter sojourn time than every option chosen by the patient type.Source: §8.2 · pp. 30–31
  • With randomized service depths, any welfare achievable centrally is also achievable through a price menu.The mechanism assigns each type a distribution of depths, with realized depths determining priority and expected sojourn time.Source: §8.2 · pp. 30–31

8.3. Dynamic Policies

  • At λ2/λ1 = 2, the welfare gap vanishes; for larger ratios it stays below 0.3%, versus up to 2.2% under static policies.Threshold control reduces congestion and improves welfare; the comparison uses λ = 1.0, θ1 = 0.105, θ2 = 0.1, and V(x) = log(1 + x).Source: Table 4 · p. 32, §8.3 · p. 32

9. Conclusion

The conclusion emphasizes how joint service-depth and priority choices shape welfare and the gap between centralized control and pricing. It also identifies personalization’s efficiency trade-off and extensions needed to test the framework in broader and practical settings.

9. Conclusion

  • In the two-type setting, the centralized optimum may prioritize patient customers, an allocation that a decentralized menu cannot implement.With continuous types, the price menu matches the centralized policy.Source: §9 · p. 32
  • More personalized mechanisms can substantially improve system efficiency, but are typically more complex to design and operate.Source: §9 · p. 33
  • The framework leaves open non-exponential service, multiple servers, state-dependent policies, and other forms of customer or server heterogeneity.The paper also identifies repeat requests after unsuccessful or low-quality service as a setting where depth choices may feed back into demand.Source: §9 · p. 33
  • Applying the policies to real AI-agent systems remains challenging, including validating service-quality measures and processing-time relationships.The authors call for practical validation of the theoretical insights and better understanding of processing time, service quality, and congestion.Source: §9 · p. 33

A.1. Proof of Proposition 1

The proof compares optimized welfare under the two possible priority orders and establishes a unique switching threshold. It also characterizes the candidate allocations and verifies that optimal service depths are positive and finite when both types are served.

A.1. Proof of Proposition 1

  • The proof reduces the priority comparison to two candidate rules and compares their optimized welfare values.It reformulates welfare using residual capacities before characterizing allocations under each order.Source: §A.1 · p. 37

Part 2: the case θ2

A.2. Proof of Proposition 2

The proof uses the incentive-compatible ordering of expected sojourn times and establishes a priority threshold in the population ratio.

A.2. Proof of Proposition 2

  • For r > c, type 2 customers are prioritized.Source: §A.2 · p. 45
  • Incentive compatibility requires w1 ≤ w2, the sojourn-time ordering used in the proof.Source: §A.2 · p. 45
  • The proof concludes that the resulting menu satisfies the incentive-compatibility constraints.Source: §A.2 · p. 45

A.3. Proof of Proposition 3

These proofs show that centralized and decentralized policies can diverge in the two-type setting, while rearranging service depths by delay sensitivity weakly improves welfare in the continuum setting. They also establish feasibility and tightness results used in the analysis.

A.3. Proof of Proposition 3

  • When λ1 > c, the centralized optimum prioritizes type 2; in the other case considered, type 1 is prioritized and the policy corresponds to problem (13).The proof relates this priority comparison to whether the centralized policy satisfies incentive compatibility.Source: §A.3 · pp. 45–46
  • The optimal decentralized menu gives strictly lower social welfare than the centralized optimum when the centralized policy fails incentive compatibility.The proof also states that the decentralized policy never chooses depths with x1θ1 > x2.Source: §A.3 · pp. 46–47

A.4. Proof of Proposition 4

  • The bound established in the proof of Proposition 4 is tight.The proof gives a parameter sequence for which the bound is attained in the limit.Source: §A.4 · p. 49

B.1. Proof of Lemma 3

  • Operationally achievable sojourn-time functions form a nonempty, closed, convex, upward-closed set, and the proof establishes the stated feasibility characterization.Randomization over priority and holding-delay policies yields convexity; adding nonnegative holding delays yields upward closure.Source: §B.1 · pp. 50–51

B.2. Proof of Proposition 5

  • Reassigning the same aggregate service-depth distribution so more delay-sensitive customers receive smaller depths weakly raises welfare and gives them higher priority.The value term is unchanged, while the weighted delay-cost term weakly falls.Source: §B.2 · pp. 51–52

B.3. Proof of Proposition 6

The proof of Proposition 6 establishes a continuous, non-increasing optimal service-depth assignment under its stated conditions. The following proof shows that a non-increasing centralized allocation induces non-increasing sojourn times and is implementable by a price menu.

B.3. Proof of Proposition 6

  • If V′(M) ≤ θ, any admissible non-increasing depth assignment can be replaced by one bounded by M with weakly higher welfare.The proof establishes an optimal solution that is continuous and non-increasing on the type interval.Source: §B.3 · pp. 53, 56

B.4. Proofs of Lemma 4 and Proposition 7

  • For a non-increasing centralized depth assignment, the induced sojourn-time function is non-increasing, so an incentive-compatible price menu exists.The proof states this result for cases in which the centralized optimal policy exists.Source: §B.4 · p. 57

C.1. Proofs of Proposition 8 and Proposition 9

The proofs connect decentralized revenue maximization to welfare optimization with virtual delay sensitivities and establish that randomized depth assignments can preserve welfare while matching depths to delay sensitivity. They also give an implementability condition based on sojourn-time ordering.

C.1. Proofs of Proposition 8 and Proposition 9

  • The revenue-maximization problem has the same feasible set as decentralized welfare maximization, but uses virtual delay sensitivities.The proof expresses long-term average revenue as equivalent to social welfare under those virtual sensitivities.Source: §C.1 · pp. 59–60

C.2. Proof of Proposition 10

  • Assigning smaller realized service depths to the more delay-sensitive type weakly raises welfare while leaving the value term unchanged.The proof constructs this reassignment while preserving the aggregate service-depth distribution.Source: §C.2 · pp. 60–61

C.3. Proofs of Lemma 5 and Proposition 11

  • For randomized depth assignments, implementability requires every type 1 option to have weakly shorter sojourn time than every type 2 option.The proof establishes this ordering as necessary and sufficient for the price rule it constructs.Source: §C.3 · p. 61
Loading 2610.33334v1…