Самый простой вариант (при котором не надо менять остальной код) - это сделать тень наверх.
Другой вариант - разместить фон в псевдоэлементе, который и расположить на всю высоту.
PS: 100vh уходит вниз за экран - это может быть нехорошо.
Вот реализация с псевдоэлементом:
html, body, nav {
height: 100%;
margin: 0;
}
nav {
position: relative;
overflow: hidden;
line-height: 1.5em;
color: white;
}
ul {
position: absolute;
margin: 0;
padding: 0;
list-style: none;
width: 8em;
}
ul::before {
content: "";
position: absolute;
z-index: -1;
top: -100vh;
width: 100%;
height: 200vh;
background: linear-gradient(to right, black, #555);
}
li ul {
margin: -1.5em 0 0 8em;
display: none;
}
li:hover > ul {
display: block;
}
a {
display: block;
padding: 0 .5em;
cursor: pointer;
}
li:hover > a {
background: silver;
}
a:not(:last-child)::before {
content: "►";
float: right;
}
<nav>
<ul>
<li><a>First</a>
<li><a>Second</a>
<li><a>Nested</a>
<ul>
<li><a>Nested 1</a>
<li><a>Nested 2</a>
<li><a>Nested again</a>
<ul>
<li><a>Inermost 1</a>
<li><a>Inermost 2</a>
<li><a>Inermost 3</a>
<li><a>Inermost 4</a>
</ul>
<li><a>Nested 4</a>
</ul>
<li><a>Fourth</a>
</ul>
</nav>