Simulating Hard Attention Using Soft Attention

@article{yang-etal-2026-simulating,
    title = "Simulating Hard Attention Using Soft Attention",
    author = "Yang, Andy  and
      Strobl, Lena  and
      Chiang, David  and
      Angluin, Dana",
    journal = "Transactions of the Association for Computational Linguistics",
    volume = "14",
    year = "2026",
    address = "Cambridge, MA",
    publisher = "MIT Press",
    url = "https://aclanthology.org/2026.tacl-1.8/",
    doi = "10.1162/tacl.a.597",
    pages = "147--166",
}

🧠 Big Picture (What is this paper about?)

Transformers use attention to decide what parts of the input to focus on.

  • Soft attention (standard): spreads focus across many positions (like probabilities).
  • Hard attention: focuses entirely on one or a few positions (like picking exactly one item).

👉 The paper asks:

Can standard soft-attention transformers behave like hard-attention ones?

⚠️ Why this matters

Hard attention is better for:

  • Logic and reasoning
  • Counting and exact computation
  • Algorithm-like tasks (e.g., parity, parentheses)

But real transformers use soft attention, which:

  • Always gives some weight to everything
  • Struggles to make sharp, discrete decisions

So the key question: 👉 Can soft attention simulate these sharp behaviors?

🔑 Main Insight

Yes—but only if you tweak the model in specific ways.

The paper shows two main tricks:

1. Temperature scaling

  • Make softmax “sharper” by lowering temperature
  • As temperature → 0, soft attention behaves more like hard attention

👉 Think: turning a blurry spotlight into a laser beam

2. Unbounded positional embeddings

  • Let position signals grow with input length
  • This helps the model distinguish positions more strongly

🚧 The core obstacle

A prior result (Hahn, 2020) says:

In standard transformers, changing one input token only slightly changes outputs (≈ 1/n effect)

But hard attention can cause big changes (constant effect).

👉 This mismatch makes simulation difficult.

So the paper circumvents this limitation by:

  • Using temperature scaling, OR
  • Using stronger positional signals

🧩 What they prove

1. Soft attention can simulate many structured computations

They show soft-attention transformers can simulate:

  • Simple patterns (like n-grams)
  • Logical rules (temporal logic)
  • Counting tasks (like parity, majority)

👉 These correspond to increasingly complex reasoning abilities.

2. Even general hard-attention transformers can be approximated

They prove:

  • If the hard-attention model has a clear margin (gap) between best and second-best choices,
  • Then soft attention can approximate it well

👉 The required sharpness depends on that gap.

3. Error can be controlled

They give bounds showing:

  • The smaller the temperature,
  • The closer soft attention gets to hard attention

🧠 Intuition in plain terms

Imagine choosing the largest number in a list:

  • Hard attention: picks it exactly
  • Soft attention: averages everything, but favors bigger numbers

👉 If you:

  • Increase contrast (temperature ↓)
  • Or exaggerate differences (positional embeddings ↑)

Then soft attention will almost always pick the max, like hard attention.

📊 Key takeaway

👉 Soft attention is more powerful than it looks.

With the right adjustments, it can:

  • Mimic discrete reasoning
  • Simulate algorithm-like behavior
  • Approximate hard attention models

⚖️ But there’s a tradeoff

To make this work, you must give up something:

  • Fixed parameters (need scaling with input length)
  • Smooth behavior (introduce sharp transitions)
  • Stability (very small temperature can be tricky)

🧾 Final takeaway

This paper shows:

Standard transformers can simulate more “symbolic” or “algorithmic” behavior—but only under specific conditions that make attention sharper or more sensitive.