How is type compatibility checked between call signatures?

You are assuming covariant types, but function arguments are contravariant. (see this article for some depth on this.)

Change your example a bit to this, and you start to see the problem:

type Add = (a: number | string, b: number | string) => number | string;

function hof(cb: Add) {
  return cb
}

const addNum = (a: number, b: number): number => Math.round(a) + Math.round(b);
const addStr = (a: string, b: string): string => `${a.toLowerCase()}${b.toLowerCase}`;

hof(addNum)('a', 'b'); // should error because addNum can't take strings
hof(addStr)(123, 456); // should error because addStr can't take numbers

Here hof returns the callback function you pass it. So if you pass it addNum then strings would crash. And if you pass it addStr then numbers would crash.

So for a function to be assignable to a function type it must take the superset of all argument types and not a subset.

Playground

However, if you make hof generic then you can create a function type from the arguments. For example:

type Add<T extends number | string> = (a: T, b: T) => T;

function hof<T extends number | string>(cb: Add<T>): Add<T> {
  return cb
}

const addNum = (a: number, b: number): number => Math.round(a) + Math.round(b);
const addStr = (a: string, b: string): string => `${a.toLowerCase()}${b.toLowerCase}`;

hof(addNum)(123, 456); // fine
hof(addStr)('a', 'B'); // fine

hof(addNum)('a', 'b'); // should error because addNum can't take strings
hof(addStr)(123, 456); // should error because addStr can't take numbers

Playground

To understand what's happening here, we to need understand the ways in which the hof function is allowed to use the cb that is passed to it.

What arguments can be passed?

Let's consider a simpler example, consisting of only a single argument.

function hof(cb: (a: number | string) => number | string) {}

So, hof is stating that it expects a callback function, cb, that takes in a single argument that can be a number or a string, and it returns a string or a number.

Now, think of the restrictions that TS would apply on hof in terms of what it can pass to cb. So, hof is allowed to call cb with either a number or a string and this is okay because hof has stated that the cb that it receives should be able to handle both a number and a string.

But, if you pass the following double function to hof, TS would complain:

function double(a: number): number {
  return 2 * a
}

And this makes sense because hof can call this double function with a string which might break the double function because it's meant to accept only numbers.

Also notice the place where the error is thrown, it's thrown right where hof is invoked with double, indicating that something is wrong with how hof is being called and not with how it's implemented.

function hof(cb: (a: number | string) => number | string) {}

function double(a: number): number {
  return 2 * a
}

// @ts-expect-error
hof(double)

So, the callbacks passed to hof should be able to handle a superset of arguments that hof is allowed to pass to the callback.

How can the return type be used?

Now let's see the ways in which hof can use the value returned by cb.

Because cb can return either a number or a string, it's hof's responsibility to use the return value wisely, meaning that hof should not assume that the returned value is always a number or a string, hof needs to put appropriate type guards before making any such assumptions.

function hof(cb: (a: number | string) => number | string) {
  // @ts-expect-error
  const fixed = cb(100).toFixed() // wrong assumption that the returned value is always a number
}

function hof(cb: (a: number | string) => number | string) {
  const ret = cb(100)
  if (typeof ret === "number") { // appropriate check to make sure that it's a number
    const fixed = ret.toFixed();
  }
}

And again notice the place where the error is thrown, it's thrown inside the function body indicating that there's a problem with the implementation of the function.

The callback passed to hof can also just return a number and TS would be absolutely fine with that.

function hof(cb: (a: number | string) => number | string) {}

function double(a: number | string): number {
  return 2 * Number(a)
}

hof(double)

So, the callbacks passed to hof should only return a subset of values that hof expects the callback to return.

Overload Signatures

The behavior with overload signatures is different, the purpose of overloading is to restrict the behavior of a function.

So, arguments and return values of overload signatures should always be a subset of the arguments and return values of the implementation signature.

TL;DR: hof needs the callback to cover more cases than either of these functions can handle alone.

You got it the wrong way around in this case.

hof specifies that its callback will be called with two arguments, either of which may be a string or a number. That means that a function only capable of handling two number arguments is not sufficient (since it might also get passed a string).

So, something the other way around would work:

function hof(cb: (a: number, b: number) => number) {}

function add(a: number | string, b: number | string): number | string {
  return 1;
}

hof(add);

Because in this case add is guaranteed to be able to handle two numbers passed to it (at least based on its signature).

So why does the overload signature work then? Because the context is an entirely different one. As overloads of the function, they are perfectly correct as they are more specific signatures of the more general one. But that is the wrong direction for function arguments where you need to pass a function with parameters as specific as required by the function or less specific. You passed a function with more specific parameters.