File size: 15,227 Bytes
0ca529a
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
"""Dynamic batch size utilities for KDFlow.

Given a global_batch (list of micro-batches), rearrange samples into new
micro-batches such that each micro-batch's total token count is bounded by
max_token_len.

The Karmarkar-Karp partitioning algorithm and first-fit estimation are adapted
from verl:
  https://github.com/volcengine/verl/blob/main/verl/utils/seqlen_balancing.py
  (Apache-2.0 License, Copyright 2024 Bytedance Ltd. and/or its affiliates)
"""

import heapq
from typing import Dict, List, Optional, Tuple

import ray
import torch
import numpy as np
import torch.distributed as dist
from kdflow.utils.logging_utils import init_logger
from torch.nn.utils.rnn import pad_sequence

logger = init_logger(__name__)

# Keys whose tensors are 2-D [batch, seq_len] and need unpad / repad
_SEQ_KEYS = {"stu_input_ids", "stu_attn_mask", "stu_loss_mask",
             "tea_input_ids", "tea_attn_mask", "tea_loss_mask"}

# Keys whose tensors are 1-D scalars per sample (e.g. response_length)
_SCALAR_KEYS = {
    "response_length",
    "total_length",
    "kd_sample_weight",
}

# Keys that are plain python lists (one element per sample)
_LIST_KEYS = {"tea_feed_input_ids", "stu_prompts", "stu_responses", "tea_prompts",
              "labels", "images", "stu_multi_modal_inputs", "tea_multi_modal_inputs",
              "teacher_routing_key"}

# Keys whose values are concatenated response-level tensors [total_resp_tokens, ...]
# that must be split per sample using tea_loss_mask counts.
_CONCAT_HIDDEN_KEYS = {"teacher_hiddens"}


def rearrange_global_batch(
    global_batch: List[Dict[str, torch.Tensor]],
    max_token_len: int,
    token_len_key: str = "stu_attn_mask",
    dp_size: Optional[int] = None,
    dp_group=None,
) -> List[Dict[str, torch.Tensor]]:
    """Rearrange a global_batch into dynamic micro-batches.

    Steps:
        1. Unpack all micro-batches into individual samples (remove padding).
        2. Estimate the number of micro-batches needed via first-fit.
        3. Use Karmarkar-Karp to balance samples across micro-batches.
        4. Re-collate each partition with right-padding.

    Args:
        global_batch: List of micro-batches, each is a dict of tensors.
        max_token_len: Maximum total *real* tokens per micro-batch.
        token_len_key: Key used to measure each sample's token count
            (via attention_mask.sum()).
        dp_size: If set, ensure the number of new micro-batches is divisible
            by ``dp_size``.  This is needed when the caller (e.g. off-policy /
            on-policy KD trainer) distributes the rearranged global_batch
            evenly across DP ranks via ``async_run_distill``.
        dp_group: ``torch.distributed`` process group for data-parallel sync.
            When provided, an ``all_reduce(MAX)`` is performed so that every
            DP rank ends up with the same number of micro-batches (needed by
            SFT trainer where each rank holds its own global_batch).
            Ranks with fewer micro-batches are padded with dummy batches.

    Returns:
        A new list of micro-batches (may differ in count from the input).
    """
    # Step 1: unpack into single samples
    samples = _unpack_global_batch(global_batch)
    if not samples:
        return global_batch

    # Step 2: compute per-sample token lengths
    token_lens = [s[token_len_key].sum().item() for s in samples]

    # Step 3: estimate number of partitions via first-fit
    num_partitions = _first_fit_num_partitions(token_lens, max_token_len)
    num_partitions = max(num_partitions, 1)
    num_partitions = min(num_partitions, len(samples))

    # Step 3.1: ensure divisibility by dp_size (for off-policy / on-policy KD)
    if dp_size is not None and dp_size > 1:
        num_partitions = _roundup_divisible(num_partitions, dp_size)
        num_partitions = min(num_partitions, len(samples))

    # Step 3.2: cross-GPU sync (for SFT trainer where each rank has its own data)
    if dp_group is not None and dist.is_initialized():
        num_partitions_t = torch.tensor([num_partitions], device=torch.cuda.current_device())
        dist.all_reduce(num_partitions_t, op=dist.ReduceOp.MAX, group=dp_group)
        num_partitions = int(num_partitions_t.item())

    # Step 4: balanced partitioning
    if num_partitions >= len(samples):
        # Each sample is its own micro-batch
        partitions = [[i] for i in range(len(samples))]
    else:
        partitions = _karmarkar_karp(token_lens, num_partitions)

    # Step 5: re-collate each partition
    new_global_batch = []
    for partition in partitions:
        batch_samples = [samples[i] for i in partition]
        micro_batch = _collate_samples(batch_samples)
        new_global_batch.append(micro_batch)

    # Step 5.1: pad with dummy micro-batches if needed (for dp_group sync)
    while len(new_global_batch) < num_partitions:
        # Create a dummy micro-batch by cloning the last one with zeroed loss_mask
        dummy = {k: v.clone() if isinstance(v, torch.Tensor) else v
                 for k, v in new_global_batch[-1].items()}
        for k in ("stu_loss_mask", "tea_loss_mask"):
            if k in dummy and isinstance(dummy[k], torch.Tensor):
                dummy[k] = torch.zeros_like(dummy[k])
        new_global_batch.append(dummy)

    return new_global_batch


def unpack_global_batch(global_batch: List[Dict[str, torch.Tensor]]) -> List[Dict]:
    """Public wrapper for converting collated micro-batches to single samples."""
    return _unpack_global_batch(global_batch)


def repartition_global_batch(
    global_batch: List[Dict[str, torch.Tensor]],
    num_partitions: int,
    token_len_key: str = "stu_attn_mask",
    pad_with_zero_weight: bool = False,
) -> List[Dict[str, torch.Tensor]]:
    """Balance samples into an exact number of micro-batches.

    When there are fewer real samples than partitions, execution-only copies
    can be appended with ``kd_sample_weight=0``. They keep distributed
    collectives synchronized but contribute no gradient.
    """
    if num_partitions <= 0:
        raise ValueError(f"num_partitions must be positive, got {num_partitions}")

    samples = _unpack_global_batch(global_batch)
    if not samples:
        return []

    real_partition_count = min(num_partitions, len(samples))
    if real_partition_count == len(samples):
        partitions = [[index] for index in range(len(samples))]
    else:
        token_lens = [sample[token_len_key].sum().item() for sample in samples]
        partitions = _karmarkar_karp(token_lens, real_partition_count)

    result = [
        _collate_samples([samples[index] for index in partition])
        for partition in partitions
    ]
    if len(result) < num_partitions and not pad_with_zero_weight:
        raise ValueError(
            f"Cannot create {num_partitions} non-empty partitions from "
            f"{len(samples)} samples"
        )

    if len(result) < num_partitions:
        source = min(result, key=lambda batch: batch[token_len_key].sum().item())
    while len(result) < num_partitions:
        dummy = {
            key: value.clone() if isinstance(value, torch.Tensor) else value
            for key, value in source.items()
        }
        if "kd_sample_weight" not in dummy:
            raise ValueError(
                "Zero-weight padding requires `kd_sample_weight` in the batch"
            )
        dummy["kd_sample_weight"] = torch.zeros_like(dummy["kd_sample_weight"])
        result.append(dummy)

    return result


def _unpack_global_batch(
    global_batch: List[Dict[str, torch.Tensor]],
) -> List[Dict]:
    """Unpack all micro-batches into a flat list of single-sample dicts.

    For sequence tensors (2-D), each sample is extracted and un-padded
    (trailing padding removed based on attention_mask).
    """
    samples = []
    for mb in global_batch:
        # Determine batch size from any seq key present
        bs = None
        for k in _SEQ_KEYS:
            if k in mb and isinstance(mb[k], torch.Tensor) and mb[k].dim() == 2:
                bs = mb[k].shape[0]
                break
        if bs is None:
            # Fallback: treat the whole micro-batch as one sample
            samples.append(mb)
            continue

        # Determine real lengths per sample from attention masks
        stu_mask = mb.get("stu_attn_mask")
        tea_mask = mb.get("tea_attn_mask")
        stu_lens = stu_mask.sum(dim=1).tolist() if stu_mask is not None else [None] * bs
        tea_lens = tea_mask.sum(dim=1).tolist() if tea_mask is not None else [None] * bs

        # Split concatenated hidden-state tensors by per-sample response token counts
        tea_loss_mask = mb.get("tea_loss_mask")
        per_sample_resp_lens = tea_loss_mask.bool().sum(dim=1).tolist() if tea_loss_mask is not None else None
        split_hiddens = {}
        for k in _CONCAT_HIDDEN_KEYS:
            v = mb.get(k)
            if v is None:
                continue
            if isinstance(v, ray.ObjectRef):
                v = ray.get(v)
            if isinstance(v, np.ndarray):
                v = torch.from_numpy(v)
            if per_sample_resp_lens is not None:
                split_hiddens[k] = torch.split(v, per_sample_resp_lens, dim=0)
            else:
                split_hiddens[k] = [v]

        for i in range(bs):
            sample = {}
            for k, v in mb.items():
                if k in _SEQ_KEYS and isinstance(v, torch.Tensor) and v.dim() == 2:
                    # Determine the real length for this key
                    if k.startswith("tea_"):
                        real_len = int(tea_lens[i]) if tea_lens[i] is not None else v.shape[1]
                    else:
                        real_len = int(stu_lens[i]) if stu_lens[i] is not None else v.shape[1]
                    sample[k] = v[i, :real_len]  # 1-D tensor, no padding
                elif k in _SCALAR_KEYS and isinstance(v, torch.Tensor):
                    if v.dim() >= 1 and v.shape[0] == bs:
                        sample[k] = v[i]
                    else:
                        sample[k] = v
                elif k in _LIST_KEYS and isinstance(v, list) and len(v) == bs:
                    sample[k] = v[i]
                elif k in _CONCAT_HIDDEN_KEYS:
                    if k in split_hiddens and i < len(split_hiddens[k]):
                        sample[k] = split_hiddens[k][i]
                    # else: skip (no hidden for this sample)
                elif k in {"avg_micro_batch_token_num", "avg_micro_batch_sample_num"}:
                    # Will be recomputed later; skip
                    continue
                else:
                    # Unknown key: just copy as-is for the first sample
                    sample[k] = v
            samples.append(sample)

    return samples


def _roundup_divisible(a: int, b: int) -> int:
    """Round *a* up to the nearest multiple of *b*.

    Adapted from verl ``roundup_divisible``.
    """
    return ((a + b - 1) // b) * b


def _first_fit_num_partitions(token_lens: List[int], max_token_len: int) -> int:
    """Estimate the minimum number of partitions using first-fit decreasing."""
    sorted_lens = sorted(token_lens, reverse=True)
    bins = []
    for l in sorted_lens:
        placed = False
        for i in range(len(bins)):
            if bins[i] + l <= max_token_len:
                bins[i] += l
                placed = True
                break
        if not placed:
            bins.append(l)
    return len(bins)


def _karmarkar_karp(
    seqlen_list: List[int],
    k_partitions: int,
) -> List[List[int]]:
    """Karmarkar-Karp multi-way partitioning (largest differencing method).

    Partitions ``seqlen_list`` into ``k_partitions`` groups such that the
    maximum group-sum is minimized (i.e., balanced workload).

    Adapted from verl ``karmarkar_karp``:
      https://github.com/volcengine/verl/blob/main/verl/utils/seqlen_balancing.py

    Returns:
        List of k_partitions lists, each containing sample indices.
    """

    class _Set:
        __slots__ = ("total", "items")

        def __init__(self):
            self.total = 0
            self.items = []  # list of (idx, val)

        def add(self, idx: int, val: int):
            self.items.append((idx, val))
            self.total += val

        def merge(self, other: "_Set"):
            self.items.extend(other.items)
            self.total += other.total

        def __lt__(self, other: "_Set"):
            if self.total != other.total:
                return self.total < other.total
            if len(self.items) != len(other.items):
                return len(self.items) < len(other.items)
            return self.items < other.items

    class _State:
        __slots__ = ("k", "sets")

        def __init__(self, items: List[Tuple[int, int]], k: int):
            self.k = k
            self.sets = [_Set() for _ in range(k)]
            for i, (idx, val) in enumerate(items):
                self.sets[i % k].add(idx, val)
            self.sets.sort(reverse=True)

        @property
        def spread(self) -> int:
            return self.sets[0].total - self.sets[-1].total

        def merge(self, other: "_State"):
            for i in range(self.k):
                self.sets[i].merge(other.sets[self.k - 1 - i])
            self.sets.sort(reverse=True)

        def get_partitions(self) -> List[List[int]]:
            return [sorted(idx for idx, _ in s.items) for s in self.sets]

        def __lt__(self, other: "_State"):
            if self.spread != other.spread:
                return self.spread > other.spread  # max-heap by spread
            return self.sets[0] > other.sets[0]

    sorted_items = sorted(enumerate(seqlen_list), key=lambda x: x[1])
    pq = []
    for idx, val in sorted_items:
        heapq.heappush(pq, _State(items=[(idx, val)], k=k_partitions))

    while len(pq) > 1:
        s0 = heapq.heappop(pq)
        s1 = heapq.heappop(pq)
        s0.merge(s1)
        heapq.heappush(pq, s0)

    partitions = pq[0].get_partitions()
    # Remove empty partitions (shouldn't happen, but be safe)
    partitions = [p for p in partitions if p]
    return partitions


def _collate_samples(samples: List[Dict]) -> Dict[str, torch.Tensor]:
    """Collate a list of single-sample dicts into one micro-batch dict.

    Sequence tensors are right-padded to the longest in the batch.
    """
    batch = {}
    keys = samples[0].keys()

    for k in keys:
        values = [s[k] for s in samples if k in s]
        if not values:
            continue

        v0 = values[0]
        if k in _SEQ_KEYS and isinstance(v0, torch.Tensor) and v0.dim() == 1:
            # Right-pad variable-length 1-D tensors
            pad_val = 0
            batch[k] = pad_sequence(values, batch_first=True, padding_value=pad_val)
        elif k in _SCALAR_KEYS and isinstance(v0, torch.Tensor):
            batch[k] = torch.stack(values)
        elif k in _LIST_KEYS:
            batch[k] = values
        elif k in _CONCAT_HIDDEN_KEYS and isinstance(v0, torch.Tensor):
            batch[k] = torch.cat(values, dim=0)
        else:
            # Default: keep first value (shared metadata)
            batch[k] = v0

    return batch