In the field of computing, a demand can be freely reformulated where it is stated independently of any incumbent implementation, but becomes impossible when the incumbent's output quietly becomes the specification. This note offers this observation as a lens on computational reformulation for modern accelerators, where posing a problem in a hardware-friendly form can yield large speed and energy gains, but only if a replacement can be judged.
Building on the test-oracle problem (Weyuker; Barr et al.), on the notion of implementation bias from requirements engineering (Zave and Jackson), and on the roofline performance model, it names the pathology "baseline capture" — the moment an incumbent stops being evidence that a demand can be met and becomes the definition of meeting it. It separates two easily confused questions: whether a reformulation can be judged (which hinges on the existence of an incumbent-independent demand) and whether its discovery can be automated (which additionally depends on the cost of evaluating that demand).
Short cases — shortest-path routing, learnable audio frontends, ZIP-215 for Ed25519 signature validation, CESM-ECT for climate models, and a single-GEMM audio frontend — illustrate the pattern and the shift of "buying a verifier": making a demand explicit, operational, and independent of the incumbent. No component is claimed novel in isolation; the contribution is the synthesis and the single question it makes easy to ask of any reformulation result — does its acceptance test mention the incumbent's output?
Blogger's Review: This paper delves into how to effectively reformulate computational problems in modern computing environments to enhance performance and efficiency. By clarifying the relationship between demands and existing implementations, it unveils potential barriers to technological advancement, which is crucial in various applications within the computing field. This perspective will significantly drive progress, especially in the design and optimization of hardware accelerators.