Why is the 'obvious' step in a proof often harder for a computer to check than the clever idea?
Why does formalizing obvious steps take longer than formalizing key insights?
This explores why turning 'obvious' proof steps into machine-checkable form (e.g., in a proof assistant like Lean) tends to take more effort than formalizing the clever central idea, and what that says about the gap between human and formal reasoning.
This explores why, when mathematicians or AI systems turn a proof into machine-checkable form, the steps a human would call 'obvious' often eat more effort than the key insight. The collection has no paper that measures this directly, so this is a synthesis from nearby material, not a settled finding.
The clearest clue is that 'obvious' usually means 'resting on a lot of background nobody bothers to write down.' A key insight is a short, explicit move. The obvious steps lean on definitions, lemmas, and conventions that a human reader fills in silently. Can autoformalization work on individual statements alone? makes the point at the level of whole theories. Even a single theorem needs a connected web of axioms, definitions, and supporting lemmas. Formalizing one statement at a time only looks easy because tools borrow that web from prebuilt libraries like Mathlib. When the library doesn't already cover an 'obvious' step, someone has to build the missing background, and that is where the time goes.
A second angle is that formalizing is translation, and translation loses information. Why does partial formalization outperform full symbolic logic? finds that adding only selected symbolic structure to natural language beats both plain language and full formalization, because full formalization strips out meaning the reasoning relied on. Applied to proofs, the steps a human finds obvious are the ones carried most by that unspoken meaning. They are cheap in informal language and expensive in a language where every assumption must be written out.
The surprise comes from model reasoning traces. They suggest that effort tracks familiarity, not difficulty. Does longer reasoning actually mean harder problems? shows that how long a model reasons reflects how close a problem is to patterns it has seen before, not how hard the problem is. Does logical validity actually drive chain-of-thought gains? finds that models gain from the form of reasoning even when the logic is invalid. Taken together, a step can feel obvious because it matches a familiar pattern, not because it is logically small. A proof checker accepts no pattern-matching, so the steps that felt easiest can turn out to hide the most unchecked work.
If you want to go further, Where do reasoning agents actually fail during long traces? points in the same direction from agent reliability. Most failures in long reasoning chains happen in the intermediate steps, not in the headline answer. 'Obvious' is a judgment about how hard something is to understand. Formal proof checking requires every step to be spelled out, and those are different kinds of difficulty.
Sources 5 notes
Real formalization requires theory-level work: even one theorem needs a coherent web of axioms, definitions, and lemmas. Statement-level approaches only succeed by borrowing from prebuilt libraries like Mathlib, hiding the actual complexity involved.
QuaSAR and Logic-of-Thought both achieve 4-8% accuracy gains by enriching natural language with selective symbolic elements rather than replacing it. Full formalization loses semantic information; pure language lacks structure. Augmentation preserves both.
Controlled A* maze experiments show trace length correlates with difficulty only in-distribution but decouples entirely out-of-distribution. Trace length primarily reflects recall of training schemas, not adaptive computation.
Illogical chain-of-thought exemplars matched valid CoT performance on BIG-Bench Hard, showing that structural properties—not logical validity—drive the gains. The model learns the form of reasoning, not genuine inference.
Reliability for long-trace reasoning comes from checking intermediate states and policy compliance during generation, not from scoring final outputs. Adding intermediate verification raised task success from 32% to 87% because most failures are process violations, not wrong answers.
Papers this line draws on 8
The research behind the notes this line reads — ranked by how closely each paper relates.
- Think Deep, Not Just Long: Measuring LLM Reasoning Effort via Deep-Thinking Tokens
- When More is Less: Understanding Chain-of-Thought Length in LLMs
- Diagnosing Harmful Continuation in Answer-Correct Long-CoT Training Traces
- What Characterizes Effective Reasoning? Revisiting Length, Review, and Structure of CoT
- Faithful and Robust LLM-Driven Theorem Proving for NLI Explanations
- Beyond Semantics: The Unreasonable Effectiveness of Reasonless Intermediate Tokens
- Large Language Models as Planning Domain Generators
- Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning