Why TeX Breaks Lines Globally: The Engineering Bet Behind Knuth-Plass

The problem with greedy line breaking

Most text layout systems break lines greedily: fill a line until the next word doesn't fit, break, repeat. It's fast, it streams, and it produces visibly uneven paragraphs — a stretched-out line followed by a cramped one, or a final line holding a single word. TeX's answer, the Knuth-Plass algorithm, makes a different bet: read the entire paragraph first, then choose the set of break points that minimizes total ugliness across all lines at once.

That bet has real consequences. It means TeX needs the whole paragraph in memory and can't typeset text as it arrives — fine for batch document production, wrong for a live editor. Understanding the model behind it explains both why TeX output looks the way it does and why the tuning knobs behave the way they do.

Boxes, glue, and penalties

TeX decomposes a paragraph into three kinds of items. Boxes are fixed-width content: characters, words, images. Glue is flexible space, declared as a natural width plus stretch and shrink components — interword glue in Computer Modern at 10pt is roughly 3.33pt plus 1.67pt minus 1.11pt. Penalties mark break desirability: a positive penalty discourages breaking there (\penalty10000 forbids it), a negative one encourages it, and hyphenation points are inserted as "discretionaries" carrying \hyphenpenalty.

Every feasible break point becomes a node in a graph, and each candidate line gets a badness score based on how much its glue must stretch or shrink. The key detail: badness is cubic in the stretch ratio — approximately 100 × r³. Stretching glue to twice its declared flexibility costs about 800 badness; three times costs 2700. This is why TeX would rather hyphenate or accept a slightly loose line than stretch one line far past its comfort zone.

Lines are also assigned a fitness class (tight, decent, loose, very loose), and adjacent lines of very different fitness incur extra demerits — the actual quantity minimized. Demerits combine line badness, the break penalty, and these inconsistency charges, so a locally acceptable line can be rejected because it sits next to a visually incompatible neighbor. A shortest-path search over the graph finds the break sequence with the lowest total demerits.

Three passes, escalating desperation

TeX doesn't always hyphenate. It runs up to three passes per paragraph:

1. First pass: no hyphenation. Succeeds if every line's badness stays below \pretolerance.
2. Second pass: hyphenation enabled, using language-specific patterns. Succeeds if badness stays below \tolerance.
3. Third pass: only if the first two fail, with \emergencystretch added as extra assumed stretch to every line, making otherwise-impossible paragraphs feasible at the cost of looser spacing.

One caution that trips people up: \tolerance is compared against badness, but the paragraph is accepted or rejected on the whole solution's feasibility — and demerits, not raw badness, decide among feasible solutions. Also note that hyphenation patterns are compiled into the format file per language; if patterns for your \language weren't preloaded, you get no hyphenation at all, not a fallback.

A worked example: taming an overfull paragraph

Suppose a narrow measure produces "Overfull \hbox" warnings. Run this in any plain TeX or LaTeX document (no special permissions needed — it's just a compile):

\tracingparagraphs=1
\emergencystretch=3em
\tolerance=2000

Compile and read the .log. With tracing on, you'll see the demerit calculations for candidate breakpoints and which pass succeeded. Compare the log and the PDF with and without \emergencystretch: the third pass typically eliminates the overfull box but produces visibly looser lines. That's the trade-off made explicit — you're telling TeX "a loose line is acceptable; an overfull one is not." To verify what actually happened rather than trusting the log summary, check the PDF visually and confirm the overfull warnings are gone from the log.

In LuaTeX you can go further: the linebreak_filter callback lets you replace the algorithm entirely, or delegate to the built-in node.linebreak(head) after modifying the node list — for example, injecting extra penalties to discourage breaks after specific words. Partial tweaks require passing a modified node list to the built-in function; there's no supported way to adjust just one parameter of the internal search.

Limitations worth knowing

• Whole-paragraph scope. The algorithm assumes a fixed line width per paragraph. \parshape and \hangindent vary width per line but are fixed when the paragraph starts — wrapping text around an inline figure mid-paragraph needs manual intervention or macro-level tricks.
• No streaming. Because the decision is global, TeX can't typeset incrementally. This is a deliberate choice favoring output quality over latency.
• Cubic badness is unforgiving. Declaring too little stretch in your glue (e.g., very tight spacing settings) makes paragraphs infeasible at low tolerance, pushing work to the emergency pass.

The takeaway

Knuth-Plass treats line breaking as a global optimization, not a local one, and the cubic badness function plus fitness-class demerits encode a specific aesthetic: even color across the paragraph matters more than any single line. When output looks wrong, don't guess — turn on \tracingparagraphs, read which pass succeeded and why, and adjust \tolerance or \emergencystretch deliberately rather than cargo-culting large values. The authoritative reference is Chapter 14 of The TeXbook (texdoc tex), and texdoc luatex for the callback interface.