The Caf'e in Amsterdam: When the Incumbent Becomes the Oracle

arXiv:2607.13393 · cs.PF, cs.AI · Submitted 2026-07-15 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "The Caf'e in Amsterdam".

Jane: The paper, "The Café in Amsterdam: When the Incumbent Becomes the Oracle," proposes a conceptual framework—a "lens"—for understanding computational reformulation by distinguishing between an independent specification and its implementation,

Tom: First, who's behind it and why it matters.

Title: Tom: So, "The Café in Amsterdam: When the Incumbent Becomes the Oracle" suggests that over sixty years, our focus has shifted from defining a problem to simply finding an algorithm that matches what Dijkstra's first algorithm produced.

Jane: It’s not just about a specific programming problem; it' about a change in how we define what "correct" means for the whole field.

Lu: The authors are pointing out that this shift has created a scenario where the original, successful solution, or incumbent, has become the standard we must match.

Meng: That's huge for me because it means if I'm building a new system to solve a problem, I might not be solving the original problem at all.

Lalam: It feels like we are losing our freedom to ask whether we are truly solving a defined demand or just mimicking the past success of Dijkstra.

Tom: That is exactly what the authors mean; they' showing us that for sixty years, shortest-path computation has been reformulated without ever needing to reproduce Dijkstra’s original path.

Jane: It’s a subtle but profound difference between inventing a new method and inventing a new specification entirely.

Lu: The paper argues that this has created two types of problems: those where the solution is independently verifiable, and others where it is captured by matching the incumbent's output.

Meng: And that distinction seems to be the whole key to unlocking potential speed improvements in modern AI acceleration.

Lalam: We need to understand these two categories because they dictate whether a new way of doing things is even allowed into our systems.

Tom: Which brings us perfectly into how this shift affects our ability to improve performance, and we'll talk about that next.

Paper summary: Tom: In the summary, the authors are detailing this concept of an "implementation-independent demand."

Jane: They're contrasting it with a "captured" approach where a solution is only judged if it looks like the initial answer provided by the incumbent.

Lu: The core idea they’re presenting is that when you have an independent demand, you can have completely new algorithms that satisfy the original specification without caring about how Dijkstra first solved it.

Meng: But in a captured scenario, for example in audio processing, the community just agrees to accept whatever works as long as it matches the original pipeline's output.

Lalam: That is where it feels like the AI has become a mere imitator of history rather than an innovator on its own.

Tom: The paper suggests that this distinction is critical because modern accelerators are designed for dense, regular computation, and we can exploit them in new ways.

Jane: If the problem is independent of the incumbent, it allows us to redesign the underlying architecture to achieve huge speedups and energy savings.

Lu: They used routing problems as a great example where you can have both an independent objective—the shortest path—and a simple, linear-time certificate to prove your work.

Meng: That’s powerful because if I'm writing code, knowing I have that verifiable proof means I can optimize the hardware design around the logic itself.

Lalam: The paper is showing us that we aren't just comparing algorithms; we are comparing fundamental ways to define a task's success.

Tom: Which leads into how this concept opens up massive possibilities for improvement, and that’s what Segment four will explore.

Paper improvements: Tom: The paper is suggesting that if we can achieve an independent demand, we unlock the ability to move beyond just optimizing the incumbent's own method.

Jane: We're talking about finding totally new ways to solve a problem that still satisfy the original requirement, without being forced to reproduce the initial answer.

Lu: The authors are showing how this is possible in fields like routing or even in certain computational problems where we can declare an approximate solution with a verifiable gap.

Meng: That's incredibly practical because it means we can push our AI agents to explore solutions that are structurally different from what the first successful model ever looked like.

Lalam: Imagine the cultural shift when all the methods of old become just one option, and a new, fundamentally different approach is welcomed.

Tom: We've seen this in other fields too, like when companies start writing down explicit validation rules for things like digital signatures or climate models.

Jane: They had to make their acceptance condition explicit and independent of the existing systems to move forward.

Lu: The authors call this "buying a verifier," which is a great way of putting it—it's about making the demand answerable without pointing back at that initial solution.

Meng: From an engineering perspective, I see how much more robust and scalable that new systems are because we are not tied to the limitations of an old implementation.

Lalam: This is about creating a genuinely open space for exploration in every single field, allowing our AI to find paths it never even knew were possible.

Tom: And that brings us all together for the wrap-up, summarizing these huge implications before we move on.

Tom: So, we've covered how the shift from defining a problem to merely matching an incumbent has limited our potential for innovation in fields like computer science and AI.

Jane: We see that by establishing this concept of an implementation-independent demand, we are opening up a vast space for new methods to be judged on their own merits.

Lu: The authors' work is a powerful reminder that sometimes, asking the question first is what allows us to discover entirely new ways of solving problems.

Meng: It gives us a clear roadmap for how modern AI systems should evaluate performance—not just by looking at the old outputs but by meeting an explicitly defined standard.

Lalam: We need to remember "The Café in Amsterdam: When the Incumbent Becomes the Oracle" as it shows us how to empower our technology with a genuinely open field of possibility.

Tom: It’s a simple lens that gives us enormous freedom, and I think that's what we can all take away from this discussion.

Jane: We hope this conversation helps everyone recognize when their field has an implementation-independent demand, and how to celebrate the discovery of a genuinely new solution.

Conclusion: Tom: So, looking back at our chat about "The Café in Amsterdam: When the Incumbent Becomes the Oracle," it really boils down to this idea of proactively defining what you need before someone else sets the rules.

Jane: Exactly, Tom. It shows that just making a demand explicit, stating what you want without pointing fingers at who made it difficult for you, can fundamentally change how a system operates and how much potential is unlocked.

Meng: I keep thinking about the engineering challenge here—if you can explicitly define that demand in a portable way, does that mean the hardware or software stack has to be modular enough to accommodate it without massive overhauls?

Lu: That's where I get excited, Meng; it means we're talking about a paradigm shift from optimizing for the known constraints to optimizing for the *potential* constraints. It dramatically enlarges the search space of solutions.

Tom: Right, Lu nailed it; you’re essentially finding ways to make problems that were previously too abstract or vague suddenly quantifiable and testable.

Jane: Think of it like teaching a child a new concept; if you can teach the concept clearly and simply first, even if they don't understand the advanced math yet, they are set up for later learning.

Lalam: I think the cultural implications are huge because this suggests that clarity of thought—clarity of demand—is almost as valuable an asset as computation itself. It improves how we collaborate intellectually.

Meng: If we can treat that stated demand as a kind of specification, it changes the economics; why pay for a solution when you can pay for the improved specification first?

Lu: And if you combine that with advanced AI capabilities, we might reach a point where defining the *demand* is itself an algorithmic process—a meta-optimization.

Tom: Wow, I feel like we’re circling back to the idea that this isn't just about better code; it's about better thinking processes being captured in systems.

Jane: It gives us a framework for intellectual property that goes beyond mere algorithms, focusing instead on definitional breakthroughs.

Lalam: It suggests a cultural value placed on articulation; the ability to articulate needs precisely becomes a form of advanced skill, which is something beneficial to society overall.

Meng: So, if I were building an enterprise system based on this principle, I'd focus my initial resources on creating robust methods for capturing and verifying those non-obvious demands.

Lu: You could even build tools that help people *find* the unstated demand—that’s where the real breakthrough potential lies.

Tom: So, while "The Café in Amsterdam: When the Incumbent Becomes the Oracle" gives us this amazing theoretical framework, it really points toward a future where defining problems becomes a computational resource itself.

Jane: It's certainly given us a lot to chew on for next time; we hope you readers are ready to keep exploring these ideas with us.

University of São Paulo · Institute of Mathematics and Engineering (IME)

cs.PF, cs.AI

Submitted: 2026-07-15

Updated: 2026-08-25

Comments: 4 pages, two-column

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 24/100

The gist: The paper, "The Café in Amsterdam: When the Incumbent Becomes the Oracle," proposes a conceptual framework—a "lens"—for understanding computational reformulation by distinguishing between an

Key concepts

Independent Specification: This refers to a problem definition where the requirement is distinct from any existing solution. Having an independent specification allows for completely new algorithms to satisfy the original need without needing to reproduce the initial answer.
Captured Approach: This describes a scenario where a solution is only judged if it matches the output of an incumbent or initial successful method. This approach limits innovation because new methods are accepted only if they look like the past success.
Implementation-Independent Demand: This core idea suggests that when a demand is independent of the incumbent, completely new algorithms can be created. This distinction is critical for unlocking speed improvements in modern AI acceleration by allowing architectural redesign.
Buying a Verifier: This concept means making the demand answerable without pointing back at the initial solution. It involves creating an explicit acceptance condition that is independent of existing systems, which helps move forward with new methods.

Terminology

Verifier — 5× in this paper · explained in 2 episodes
Accuracy — 2× in this paper · explained in 1 episode
Consistency — 2× in this paper · explained in 3 episodes
AI Agents — 1× in this paper · explained in 2 episodes
Core — 1× in this paper · explained in 2 episodes
Frozen model — 1× in this paper · explained in 3 episodes
Verification — 1× in this paper · explained in 2 episodes

Summary

The paper, The Café in Amsterdam: When the Incumbent Becomes the Oracle, proposes a conceptual framework—a lens—for understanding computational reformulation by distinguishing between an independent specification and its implementation, focusing on how this distinction dictates whether a field can evolve or become constrained by its established methods.

The author begins with the historical example of Edsger Dijkstra in 1956. He solved the shortest path problem from Rotterdam to Groningen. The key insight here is that He formulated the demand first... The algorithm came second, as one way, out of many, to satisfy it. Because this initial demand (the shortest path specification) existed independently of any specific implementation, the field was free to allow subsequent algorithms—such as A*, Contraction Hierarchies, or hub labelling—to be reformulated almost beyond recognition, provided they satisfied the original specification.

The discussion then shifts to modern constraints: silicon and joules. The ability to change a computational formulation allows for significant speedup and energy reduction on modern accelerators. This speedup is only possible when the formulation is free to change.

The paper examines this dynamic in the field of audio processing, which uses a dominant pipeline (Fourier transform, Mel filterbank, logarithm). While new systems like SincNet and LEAF are structurally different and replace this traditional frontend, they are judged solely on downstream task accuracy. The author notes that while the demand side oracle (task-level criterion) exists, the substrate motive (hardware performance/efficiency) also exists.

The central problem identified is that when a field has an implementation-independent demand, the incumbent solution serves only as evidence that the demand can be met. However, if such a demand is not explicitly defined or if it lacks independence, the incumbent itself seems to become the practical oracle. This phenomenon—where an established solution dictates future success—is termed baseline capture, which is defined as the moment an incumbent stops being evidence and becomes judge.

To formalize this concept, the author introduces a notation:

D: The demand (specification).
P: A program or implementation.
Out D: An output satisfies the demand D.

Two types of acceptance tests are defined:

TD (independent): T D (Out) = 1 [Out D], representing an independent test that satisfies the original demand.
T0 (captured): T 0 (Out) = 1 [Out in R(Out 0)], where R(Out 0) is any acceptance region defined from the incumbent’s output (Out 0).

Baseline capture is the drift TD T0.

The fundamental question posed to researchers is whether the definition of T mention Out 0 ? The author notes that a field's ability to reformulate depends on two properties: whether an independent demand (T D) exists, and whether the resulting test is cheap to evaluate.

The paper concludes by arguing that the solution is not technical cleverness but explicit definition. When a community makes its acceptance condition explicit, operationally, and independent of the incumbent, reformulations that were previously unjustifiable become admissible. This process of buying a verifier allows for an expansion of the space of possible solutions, which in turn enables greater hardware performance.

The author’s final call to action is that making a field’s demand explicit—stating it without mentioning the incumbent—is one of the most effective ways to enlarge the space of admissible reformulations.

Improvements for AI systems

The following improvements are derived from applying the philosophical framework presented in The Café in Amsterdam to modern AI/ML systems, specifically targeting issues where performance metrics or acceptance criteria default to matching a specific incumbent model's output rather than satisfying an abstract requirement.

The Improvement: Before training begins, the core operational goal (the Demand, D) must be formally specified in a way that is entirely independent of any existing model or benchmark output (Out 0. This moves the system from an acceptance test based on similarity to a test based on specification.

What the Improved System Can Do:

Formal Specification of Task Success: The AI system can be guided by a formal predicate D (e.g, input in InputSet, Output(input) = D), where D defines success based on logical consistency or abstract properties, not on proximity to a specific target value.
Guaranteed Conceptual Adherence: It ensures the model is optimized for what it needs to achieve (e.g, perfect logical coherence in reasoning) rather than merely achieving a score that happens to align with the output of an older architecture (e.g, matching the specific feature representation of a legacy CNN).

Abstract

A field can reformulate its computations freely exactly where its demand is stated independently of any incumbent implementation, and finds itself unable to when the incumbent's own output has quietly become the specification. This note offers that 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 at all. Building on the test-oracle problem (Weyuker; Barr et al.), on requirements engineering's notion of implementation bias (Zave and Jackson), and on the case for judging approximate designs by acceptability rather than numerical proximity (Felzmann et al.), 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 then separates two questions that are easily confused: whether a reformulation can be judged at all, which turns on the existence of an incumbent-independent demand, and whether its discovery can be automated, which turns additionally 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 measured at 1.64x-3.29x speedup and up to 3.03x less energy -- illustrate the pattern and the move 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?