🤖 AI

HMAF: A Hierarchical Multi-Slot GD-RTB Allocation Framework

The paper proposes HMAF, a unified hierarchical framework that integrates offline constraint optimization with online listwise decision-making to effectively balance long-term Guaranteed Delivery contract fulfillment and short-term Real-Time Bidding revenue maximization in complex multi-slot advertising environments, achieving significant performance improvements in Meituan's marketing scenarios.

Original authors: Tianxing Bu, Zhaoqi Zhang, Linyou Cai, Miao Xie, Shengri Xue, Tan Qu, Qianlong Xie, Xingxing Wang, Siqiang Luo, Gao Cong

Published 2026-06-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Tianxing Bu, Zhaoqi Zhang, Linyou Cai, Miao Xie, Shengri Xue, Tan Qu, Qianlong Xie, Xingxing Wang, Siqiang Luo, Gao Cong

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy restaurant (the advertising platform) that has two types of customers:

The VIPs (GD Contracts): These are big advertisers who have signed a contract months ago. They paid a fixed price and said, "We must get 10,000 table reservations (ad impressions) over the next month, no matter what." If the restaurant fails to seat them, it has to pay a penalty.
The Walk-ins (RTB Ads): These are advertisers who show up every day and say, "I'll pay whatever the current market price is for a table right now." The restaurant wants to fill these tables with the highest bidders to make as much money as possible today.

The Problem:
The restaurant has a limited number of tables (ad slots) on each page. Sometimes, the VIPs need a table, but the Walk-ins are offering a huge amount of money for that same table.

If you give the table to the Walk-in, you make more money today, but you might fail to seat enough VIPs by the end of the month.
If you give the table to the VIP, you keep your contract happy, but you might miss out on a huge cash windfall from a Walk-in.

Previous systems tried to solve this by either ignoring the VIPs until the end of the month (risky) or using simple, rigid rules like "VIPs always go first" (which wastes money).

The Solution: HMAF (The Smart Restaurant Manager)
The paper introduces a new system called HMAF (Hierarchical Multi-Slot Allocation Framework). Think of it as a three-step management team that runs the restaurant perfectly.

Step 1: The Planner (The "Plan" Phase)

Before the restaurant even opens for the day, the Planner looks at the entire month's schedule.

What they do: They calculate exactly how many tables the VIPs need and how many are available. They figure out the "shadow price" of every table.
The Analogy: Imagine the Planner realizes, "Table 4 on the second floor is very popular, but we only have 5 of them. If we give Table 4 to a VIP, it costs us a lot of potential Walk-in money. But if we give it to a Walk-in, we might miss the VIP contract."
The Output: The Planner creates a set of "rules of thumb" (called dual variables) that tell the staff: "Table 4 is expensive right now; only give it to a VIP if they are really urgent. Otherwise, save it for high-paying Walk-ins."

Step 2: The Calibrator (The "Calibrate" Phase)

When a customer arrives (a user opens the app), the Calibrator takes the Planner's rules and adjusts the scores of the ads in real-time.

What they do: It looks at the VIPs and the Walk-ins. If a VIP contract is falling behind on its delivery goal, the Calibrator gives that VIP a "boost" in their score, making them more likely to get a table. If a VIP is already ahead, the boost is removed.
The Analogy: It's like a traffic cop at the door. If the VIP section is empty, the cop waves the VIPs in faster. If the VIP section is full, the cop lets the high-paying Walk-ins in. It balances the two groups dynamically, second by second.

Step 3: The Executor (The "Execute" Phase)

This is the final decision-maker who actually assigns the tables.

What they do: In a modern restaurant, you don't just have one table; you have a whole row of tables (a "multi-slot" page). The Executor doesn't just pick the best single table; it picks the best arrangement for the whole row.
The Analogy: Imagine the Executor is a chef arranging a platter. They don't just put the most expensive dish in the middle; they arrange the whole plate so that the VIPs get their specific spots without blocking the view of the Walk-ins, ensuring the whole "platter" (the user's screen) looks good and makes the most money.
The Magic: This part uses a "Generator-Evaluator" network. The Generator creates a few possible seating arrangements (e.g., "What if we put the VIP here and the Walk-in there?"). The Evaluator acts like a judge, looking at all those options and picking the one that makes the most money while keeping the VIPs happy.

The Results

The paper says this system was tested at Meituan, a massive food delivery platform in China (think of it as a giant digital restaurant).

The Outcome: By using this three-step manager, Meituan managed to seat 3.72% more VIPs (fulfilling more contracts) AND make 1.59% more total money from Walk-ins.
Why it's surprising: Usually, if you seat more VIPs, you make less money because you can't charge the Walk-ins as much. But because HMAF is so smart about which tables to give to whom (using the "shadow prices" from the Planner), it found a way to do both at the same time.

In Summary:
HMAF is like a super-smart restaurant manager who doesn't just react to customers as they walk in. Instead, it plans the whole month, adjusts the door policy in real-time based on how full the VIP section is, and arranges the tables perfectly to ensure everyone gets what they need while the restaurant makes the maximum possible profit.

Technical Summary: HMAF – A Hierarchical Multi-Slot GD-RTB Allocation Framework

1. Problem Formulation

The paper addresses the complex challenge of impression allocation in large-scale online advertising ecosystems where Guaranteed Delivery (GD) contracts coexist with Real-Time Bidding (RTB) auctions. Specifically, the authors focus on multi-slot environments (e.g., content feeds), where a single page view contains multiple ad slots.

The core problem is formulated as a unified allocation task to maximize total platform revenue (sum of RTB auction values and GD contractual values) subject to strict constraints:

GD Delivery Constraints: Ensuring contracts meet minimum and maximum impression volumes ( $B_j$ ) to avoid penalties.
Supply Constraints: Each request (page view) can be allocated to at most one ad per slot.
Page View (PV) Constraints: Fine-grained limits on the number of impressions a specific request can contribute across multiple slots to prevent ad fatigue and over-exposure.

The authors identify three fundamental challenges in solving this problem:

NP-Hardness: The problem generalizes the Multidimensional Knapsack Problem (MKP) under fine-grained PV constraints, making global optimization computationally intractable for millions of requests.
eCPM-Fulfillment Trade-off: Balancing short-term revenue maximization (high eCPM) with long-term contract delivery guarantees is difficult; aggressive fulfillment often hurts revenue, while pure revenue focus risks under-delivery.
Weak Supervision: Unlike standard CTR prediction, hybrid ranking lacks explicit ground-truth labels for the optimal list, requiring the system to learn from implicit, delayed feedback derived from aggregate delivery states.

2. Methodology: The HMAF Framework

The authors propose HMAF (Hierarchical Multi-Slot Allocation Framework), which decomposes the intractable problem into a Plan–Calibrate–Execute paradigm. This framework tightly couples offline constraint optimization with online neural decision-making.

A. Plan Stage: Page View-Constrained Allocation Module

This module formulates the allocation problem as a constrained optimization problem offline.

Objective: Minimizes a loss function that balances contract fulfillment, user interest, and a novel Page View (PV) constraint to limit exposure per slot.
Mechanism: The problem is solved using Lagrangian relaxation and KKT conditions. Instead of solving the primal problem directly, the system iteratively updates dual variables ( $\alpha, \beta, \delta$ $α, β, δ$ ) via projected gradient steps.
- $\alpha_j$ : Shadow price for contract demand (delivery pressure).
- $\beta_i$ : Shadow price for request capacity.
- $\delta_{ij}$ : Shadow price for slot-level PV constraints.
Output: These dual variables act as "shadow prices" encoding global resource scarcity and delivery pressure, serving as compact control signals for downstream stages.

B. Calibrate Stage: Dual-Guided Pre-Ranking Module

This module bridges offline planning with online execution by injecting the dual variables into the ranking score.

Unified Scoring: It defines a ranking score ( $rs_j$ ) for both GD and RTB candidates.
Dual-Guided Modulation: For GD ads, the score is adjusted by a term $x_{ij} \cdot PID_{Error}$ , where $x_{ij}$ is the allocation confidence derived from the offline optimization. This dynamically adjusts competitiveness based on context-specific delivery pressure rather than applying uniform PID control.
Function: This stage performs coarse filtering and ranking, significantly reducing the decision space while preserving allocation quality.

C. Execute Stage: Generator-Evaluator Listwise Allocation Module

This stage handles the final listwise ranking across multiple slots, addressing the position-dependent nature of multi-slot ads.

Dual-Augmented Feature Space: The offline dual variables ( $\alpha, \beta, \delta$ ) are injected as global state features into the neural network, providing "foresight" on system constraints.
Generator: A Transformer-based encoder models candidate-position interactions, outputting a probability matrix for assigning candidates to slots. It generates a primary list and perturbed lists for exploration.
Evaluator: A listwise supervisor selects the optimal ranking list from the generated candidates by estimating a reward ( $R(S_k)$ ) that aggregates predicted metrics and delivery constraints.
Training Objective: The model is trained using a combined loss function:
- $L_{ce}$ : Cross-entropy loss aligning predictions with the evaluator's optimal assignment.
- $L_{re}$ : Reward-aware loss penalizing deviations between predicted and realized eCPM, correcting systematic biases.

3. Key Contributions

Unified Framework: The proposal of HMAF, a hierarchical framework that integrates offline constraint optimization with online neural decision-making, providing a robust architectural foundation for multi-slot GD-RTB allocation.
Three Core Components:
- A Page View-Constrained Optimization module that captures fine-grained supply-side constraints and derives dual signals.
- A Dual-Guided Unified Ranking module that calibrates online scoring using offline dual variables to balance eCPM and fulfillment.
- A Generator-Evaluator module that enables listwise ranking by jointly modeling candidate-position interactions under global guidance.
Empirical Validation: Large-scale experiments and online A/B tests demonstrating statistically significant improvements in both delivery rates and total revenue.

4. Experimental Results

The framework was evaluated using a dataset from Meituan's production environment (123M+ impressions, 32 days) and deployed in online A/B tests.

Offline Performance:

HMAF outperformed baselines (including CF, PID, AUAF, CONFLUX, and LIBRA) across all metrics.
Group AUC (GA): 0.8984 (vs. 0.8538 for the best baseline, LIBRA).
Delivery Rate (DR): 0.9638 (vs. 0.9554 for LIBRA).
Utility Rate (UR): 0.9812 (vs. 0.9513 for LIBRA).
RTB eCPM: Achieved the highest normalized score (1.0000).

Online A/B Testing (2 months, 50/50 traffic split):

GD Delivery Rate: Increased by 3.72% (statistically significant, p-value 0.018).
Total Advertisement Revenue: Increased by 1.59% (statistically significant, p-value 0.024).
System Efficiency: The offline planning runs in ~2 hours on 20 machines; online inference is lightweight (<50ms per page view).
Significance of Results: The authors note that achieving simultaneous gains in delivery and revenue is counter-intuitive. They attribute this to the GE model's ability to intelligently shift GD impressions to non-premium slots (using $\delta_{ij}$ signals), thereby freeing high-value inventory for RTB.

5. Significance and Claims

The paper claims that HMAF successfully addresses the inherent conflict between short-term revenue efficiency and long-term delivery guarantees in hybrid advertising markets. By introducing a Plan–Calibrate–Execute paradigm, the framework moves beyond heuristic priority rules or decoupled pipelines.

The authors emphasize that the framework's ability to handle fine-grained multi-slot constraints and NP-hard combinatorial optimization through a dual-guided neural approach is its primary innovation. They state that HMAF provides a "reliable architectural foundation" for GD-RTB allocation and has been successfully deployed in Meituan's production system, yielding measurable business value. The paper concludes that the framework is adaptable to other platforms with similar GD-RTB settings, relying only on guaranteed delivery requirements, real-time bidding values, and multi-slot exposure constraints.