I thought Python passed everything by reference?

Everything is passed by value, but that value is a reference to the original object. If you modify the object, the changes are visible for the caller, but you can't reassign names. Moreover, many objects are immutable (ints, floats, strings, tuples).

Inside foo, you're binding the local name input to a different object (10). In the calling context, the name input still refers to the 5 object.

Assignment in Python does not modify an object in-place. It rebinds a name so that after input = new_val, the local variable input gets a new value.

If you want to modify the "outside" input, you'll have to wrap it inside a mutable object such as a one-element list:

def foo(input, new_val):
    input[0] = new_val

foo([input])

Python does not do pass-by-reference exactly the way C++ reference passing works. In this case at least, it's more as if every argument is a pointer in C/C++:

// effectively a no-op!
void foo(object *input, object *new_val)
{
    input = new_val;
}