Layout Optimization

When creating an optimized keyboard layout, we want to find the arrangement of keys that minimizes bad typing patterns like Same-Finger Bigrams. But how do we find the best layout among the 400+ septillion possible arrangements of just the 26 letters? The answer lies in optimization algorithms—systematic ways to improve a layout step by step.

Consider just the 26 English letters on a keyboard. There are 26! (26 factorial) ways to arrange them:

$26! = 26 \times 25 \times 24 \times ... \times 2 \times 1 \approx 4.03 \times 10^{26}$

That’s about 400 septillion possible layouts. Even if a computer could test 1 billion layouts per second, it would take 12.8 billion years to check them all—nearly the age of the universe! Clearly, we need a smarter approach than checking every possibility.

Instead of checking every layout, optimization algorithms work by starting with one layout and gradually improving it. Think of it like rearranging furniture in a room: you don’t try every possible arrangement, you move one piece at a time and keep changes that make the room better.

Here’s the basic optimization process:

1. Start with an existing layout (like QWERTY) or a random arrangement
2. Swapping a key to create a new layout
3. Analyze the new layout using n-gram frequencies
4. Decide whether to keep or reject the swap based on the algorithm’s strategy
5. Repeat thousands of times

For example, let’s say we’re starting with QWERTY and we try swapping the d and h keys. We calculate the fitness score for this new layout using our pre-computed n-gram frequencies. The algorithm needs a single number to determine whether the swap is an improvement, so it combines multiple metrics like Same-Finger Bigrams, Lateral Stretch, Scissors, and Rhythm into one fitness score.

The choice of which metrics to include and how heavily to weight each one fundamentally determines what kind of layout the optimizer creates. This is where layout design becomes as much art as science—there’s no universally “correct” way to balance competing constraints like finger comfort versus typing speed.

Hill Climbing

The simplest optimization approach is hill climbing (also called greedy search). The strategy is straightforward: if a key swap improves the fitness score, keep it; if it makes the score worse, reject it and try a different swap. This mimics climbing a hill by always taking steps upward.

Hill climbing is fast and intuitive, but it has a critical limitation: it gets stuck in local optima. A local optimum is a layout that’s better than any single key swap, but not necessarily the globally best layout. It’s like reaching the top of a small hill when there’s a much taller mountain nearby—you can’t get there by only taking upward steps.

Simulated Annealing

To overcome the local optima problem, most layout optimizers use simulated annealing. Unlike hill climbing, simulated annealing occasionally accepts worse layouts, especially early in the optimization process. This allows the algorithm to “jump out” of local optima and explore different regions of the layout space.

Simulated annealing uses a “temperature” parameter that starts high and gradually decreases. At high temperatures (early stages), the algorithm accepts many worse layouts to explore widely. At low temperatures (later stages), it becomes more selective and only accepts clear improvements. The probability of accepting a worse layout follows: $P(\text{accept}) = e^{-\Delta\text{score} / T}$, where $\Delta\text{score}$ is how much worse the new layout is and $T$ is the current temperature.

For example, early in optimization, the algorithm might accept a layout that increases SFB from 4.2% to 4.5% if the temperature is high enough. Later, it would reject such a change. This allows the search to escape local optima and find globally better solutions.

Success in Practice

These optimization approaches have been remarkably successful. The CarpalX project pioneered simulated annealing for keyboard optimization and demonstrated that systematically swapping keys could dramatically improve typing metrics. Many modern alternative layouts like MTGAP were created or refined using variants of these techniques.

The key insight is that while we can’t check every possible layout, we don’t need to. The layout optimization landscape is generally well-behaved: reasonably good layouts tend to be near other reasonably good layouts. This makes iterative improvement practical and effective, whether using simulated annealing for a first pass at optimizing a particular fitness function or hill climbing to refine an already-good layout candidate.