The reason for this, is that these invocations are in fact, invocations to two different overloaded methods available in ExecutorService; each of these methods taking a single argument of different types:

1. <T> Future<T> submit(Callable<T> task);
2. Future<?> submit(Runnable task);

Then what happens is that the compiler is converting the lambda in the first case of your problem into a Callable<?> functional interface (invoking the first overloaded method); and in the second case of your problem converts the lambda into a Runnable functional interface (invoking therefore the second overloaded method), requiring because of this to handle the Exception thrown; but not in the previous case using the Callable.

Although both functional interfaces don't take any arguments, Callable<?> returns a value:

1. Callable: V call() throws Exception;
2. Runnable: public abstract void run();

If we switch to examples that trim the code to the relevant pieces (to easily investigate just the curious bits) then we can write, equivalently to the original examples:

    ExecutorService executor = Executors.newSingleThreadExecutor();    // LAMBDA COMPILED INTO A 'Callable<?>'    executor.submit(() -> {        while (true)            throw new Exception();    });    // LAMBDA COMPILED INTO A 'Runnable': EXCEPTIONS MUST BE HANDLED BY LAMBDA ITSELF!    executor.submit(() -> {        boolean value = true;        while (value)            throw new Exception();    });

With these examples, it may be easier to observe that the reason why the first one is converted to a Callable<?>, while the second one is converted to a Runnable is because of compiler inferences.

In both cases, the lambda bodies are void-compatible, since every return statement in the block has the form return;.

Now, in the first case, the compiler does the following:

1. Detects that all execution paths in the lambda declare throwing checked exceptions (from now on we will refer as 'exception', implying only 'checked exceptions'). This includes the invocation of any method declaring throwing exceptions and the explicit invocation to throw new <CHECKED_EXCEPTION>().
2. Concludes correctly that the WHOLE body of the lambda is equivalent to a block of code declaring throwing exceptions; which of course MUST be either: handled or re-thrown.
3. Since the lambda is not handling the exception, then the compiler defaults to assume that these exception(s) must be re-thrown.
4. Safely infers that this lambda must match a functional interface cannot complete normally and therefore is value-compatible.
5. Since Callable<?> and Runnable are potential matches for this lambda, the compiler selects the most specific match (to cover all scenarios); which is the Callable<?>, converting the lambda into an instance of it and creating an invocation reference to the submit(Callable<?>) overloaded method.

While, in the second case, the compiler does the following:

1. Detects that there may be execution paths in the lambda that DO NOT declare throwing exceptions (depending on to-be-evaluated logic).
2. Since not all execution paths declare throwing exceptions, the compiler concludes that the body of the lambda is NOT NECESSARILY equivalent to a block of code declaring throwing exceptions - compiler doesn't care/pay attention if some portions of the code do declare that they may, only if the whole body does or not.
3. Safely infers that the lambda is not value-compatible; since it MAY complete normally.
4. Selects Runnable (as it is the only available fitting functional interface for the lambda to be converted into) and creates an invocation reference to the submit(Runnable) overloaded method. All this coming at the price of delegating to the user, the responsibility of handling any Exceptions thrown wherever they MAY occur within portions of the lambda body.

This was a great question - I had a lot of fun chasing it down, thanks!

Briefly

ExecutorService has both submit(Callable) and submit(Runnable) methods.

1. In the first case (with the while (true)), both submit(Callable) and submit(Runnable) match, so the compiler has to choose between them
   • submit(Callable) is chosen over submit(Runnable) because Callable is more specific than Runnable
   • Callable has throws Exception in call(), so it is not necessary to catch an exception inside it
2. In the second case (with the while (tasksObserving)) only submit(Runnable) match, so the compiler chooses it
   • Runnable has no throws declaration on its run() method, so it is a compilation error to not catch the exception inside the run() method.

The full story

Java Language Specification describes how the method is chosen during program compilation in $15.2.2 :

1. Identify Potentially Applicable Methods ($15.12.2.1) which is done in 3 phases for strict, loose and variable arity invocation
2. Choose the Most Specific Method ($15.12.2.5) from the methods found on the first step.

Let's analyze the situation with 2 submit() methods in two code snippets provided by the OP:

ExecutorService executor = Executors.newSingleThreadExecutor();    executor.submit(() -> {        while(true)        {            //DO SOMETHING            Thread.sleep(5000);        }    });

and

ExecutorService executor = Executors.newSingleThreadExecutor();    executor.submit(() -> {        while(tasksObserving)        {            //DO SOMETHING            Thread.sleep(5000);        }    });

(where tasksObserving is not a final variable).

Identify Potentially Applicable Methods

First, the compiler has to identify the potentially applicable methods: $15.12.2.1

If the member is a fixed arity method with arity n, the arity of the method invocation is equal to n, and for all i (1 ≤ i ≤ n), the i'th argument of the method invocation is potentially compatible, as defined below, with the type of the i'th parameter of the method.

and a bit further in the same section

An expression is potentially compatible with a target type according to the following rules:

A lambda expression (§15.27) is potentially compatible with a functional interface type (§9.8) if all of the following are true:

The arity of the target type's function type is the same as the arity of the lambda expression.

If the target type's function type has a void return, then the lambda body is either a statement expression (§14.8) or a void-compatible block (§15.27.2).

If the target type's function type has a (non-void) return type, then the lambda body is either an expression or a value-compatible block (§15.27.2).

Let's note that in both cases, the lambda is a block lambda.

Let's also note that Runnable has void return type, so to be potentially compatible with Runnable, a block lambda must be void-compatible block. At the same time, Callable has a non-void return type, so to be potentially comtatible with Callable, a block lambda must be value-compatible block.

$15.27.2 defines what a void-compatible-block and value-compatible-block are.

A block lambda body is void-compatible if every return statement in the block has the form return;.

A block lambda body is value-compatible if it cannot complete normally (§14.21) and every return statement in the block has the form return Expression;.

Let's look at $14.21, paragraph about while loop:

A while statement can complete normally iff at least one of the following is true:

The while statement is reachable and the condition expression is not a constant expression (§15.28) with value true.

There is a reachable break statement that exits the while statement.

In borh cases, lambdas are actually block lambdas.

In the first case, as it can be seen, there is a while loop with a constant expression with value true (without break statements), so it cannot complete normallly (by $14.21); also it has no return statements, hence the first lambda is value-compatible.

At the same time, there are no return statements at all, so it is also void-compatible. So, in the end, in the first case, the lambda is both void- and value-compatible.

In the second case, the while loop can complete normally from the point of view of the compiler (because the loop expression is not a constant expression anymore), so the lambda in its entirety can complete normally, so it is not a value-compatible block. But it is still a void-compatible block because it contains no return statements.

The intermediate result is that in the first case the lambda is both a void-compatible block and a value-compatible block; in the second case it is only a void-compatible block.

Recalling what we noted earlier, this means that in the first case, the lambda will be potentially compatible both with Callable and Runnable; in the second case, the lambda will only be potentially compatible with Runnable.

Choose the Most Specific Method

For the first case, the compiler has to choose between the two methods because both are potentially applicable. It does so using the procedure called 'Choose the Most Specific Method' and described in $15.12.2.5. Here is an excerpt:

A functional interface type S is more specific than a functional interface type T for an expression e if T is not a subtype of S and one of the following is true (where U1 ... Uk and R1 are the parameter types and return type of the function type of the capture of S, and V1 ... Vk and R2 are the parameter types and return type of the function type of T):

If e is an explicitly typed lambda expression (§15.27.1), then one of the following is true:

R2 is void.

First of all,

A lambda expression with zero parameters is explicitly typed.

Also, neither of Runnable and Callable is a subclass of one another, and Runnable return type is void, so we have a match: Callable is more specific than Runnable. This means that between submit(Callable) and submit(Runnable) in the first case the method with Callable will be chosen.

As for the second case, there we only have one potentially applicable method, submit(Runnable), so it is chosen.

So why does the change surface?

So, in the end, we can see that in these cases different methods are chosen by the compiler. In the first case, the lambda is inferred to be a Callable which has throws Exception on its call() method, so that sleep() call compiles. In the second case, it's Runnable which run() does not declare any throwable exceptions, so the compiler complains about an exception not being caught.