Repository: pytorch
Issue: Custom sampler for Seq2Seq models to avoid padding
Labels: module: dataloader,triaged

## 🚀 Feature
<!-- A clear and concise description of the feature proposal -->
As proposed in this [PyTorch forum post](https://discuss.pytorch.org/t/using-batches-for-seq2seq-models/55205): Custom sampler for Sequence-to-Sequence models (but also for sequence classification, sequence tagging, autoencoders, etc.) that forms homogeneous batches, i.e., in the same batch all input sequences have the same length, and all target sequences have the same length. For example a batch might contain 32 pairs with all input sequences having length 12 and all target sequences having length 15.

## Motivation
<!-- Please outline the motivation for the proposal. Is your feature request related to a problem? e.g., I'm always frustrated when [...]. If this is related to another GitHub issue, please link here too -->

Most Sequence-to-Sequence tutorials assume batch sizes of 1, since target sequences typically and with a end-of-sequence (EOS) token without padding. Thus, random batches of larger would include target sequences with different length. Batches of size 1, of course, show poor performance w.r.t. to training time compared the larger batches

While padding of input sequences is common (at least for sequence classification), it's effects on the accuracy are not always clear. Optional packing using `PackedSequence` arguably mitigates this but also adds noticeable overhead to the performance of the training (anecdotal bservation: up 10% longer training)

## Pitch

<!-- A clear and concise description of what you want to happen. -->
A custom sampler organizes all data items, here: pairs of sequences, into batch, so that each batch contains only pairs with equal inputs lengths and equal output lengths. For example a batch might contain 32 pairs with all input sequences having length 12 and all target sequences having length 15. The benefits are:

* Obviously, larger batches that yield better training times compared to batches of size 1
* No padding and optional packing need (potentially avoid all involved side effects)

## Alternatives

<!-- A clear and concise description of any alternative solutions or features you've considered, if any. -->
`torchtext` has its own `BucketIterator` that organizes batches to minimize padding (not completely avoiding it). 

## Additional context

<!-- Add any other context or screenshots about the feature request here. -->

To see how the combination of input and target lengths are distributed, I’ve made a test with a real-world dataset for machine translation. I’ve set the batch size to 32. The figure below shows the distribution of the sizes of all batches. As one can see, the vast majority of batches is indeed full (i.e., 32 sequence pairs). This shouldn’t really be surprising since:

* Batch sizes (e.g., 32 or 64) are is essentially nothing given large datasets of millions of sequences pairs or more. Thus, the chance that enough pairs share the same input and target lengths is high.
* The combination of input and target lengths is typically not independent. For example, an input of length 5 generally does not have a target length of 20 but in a similar range.

![bucketbatchsample-batch-size-distribution](https://user-images.githubusercontent.com/22168190/64392082-c79dae80-d07d-11e9-8a5a-9be614350457.png)


cc @SsnL