  In large language model training, input documents are typically concatenated
together and then split into sequences of equal length to avoid padding tokens.
Despite its efficiency, the concatenation approach compromises data integrity
-- it inevitably breaks many documents into incomplete pieces, leading to
excessive truncations that hinder the model from learning to compose logically
coherent and factually consistent content that is grounded on the complete
context. To address the issue, we propose Best-fit Packing, a scalable and
efficient method that packs documents into training sequences through
length-aware combinatorial optimization. Our method completely eliminates
unnecessary truncations while retaining the same training efficiency as
concatenation. Empirical results from both text and code pre-training show that
our method achieves superior performance (e.g., relatively +4.7% on reading
comprehension; +16.8% in context following; and +9.2% on program synthesis),
and reduces closed-domain hallucination effectively by up to 58.3%.
